טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentNus Yevgeni
SubjectAutomated Problem Decomposition for Multi-Agent Planning
Systems
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Carmel Domshlak
Full Thesis textFull thesis text - English Version


Abstract

Automated, domain-independent planning aims to build algorithms able to synthesize a course of actions to achieve certain goals. In general, planning algorithms perform reachability analysis in automated-scale state spaces that are implicitly described in a concise manner via some intuitive declaration language. The classical case attempts to transform a system with deterministic dynamics from a given initial state into a goal state. The state space of such a planning task is typically huge, exponential in the number of state variables. As such, planning is considered to be a complicated and difficult. Decomposing the problem is one way to reduce its difficulty.

In our work we present a new method for problem decomposition, designed specifically for multiple-agent real time strategy (RTS) domains. The basic idea is to divide the sub-goals of the original problem between different groups of agents. Each such group becomes responsible for achieving its designated set of sub-goals. Thus, we actually decompose the main planning task into several independent planning sub-tasks, each of which can be solved independently and the solutions then combined into a plan for the original task. Decomposing the problem can facilitate its solution by reducing search complexity, thus helping the planner produce a more balanced work load between the units. Moreover, a decomposed planning task can be solved in parallel by a distributed system, thus greatly reducing system response time to a given problem. In our research, we worked very closely with an industrial RTS simulation system. For such a working environment, the response time of the planner is crucial, as the true state of the simulated world is constantly changing. Working with an actual commercial simulator enabled us to explore and exploit the potential advantages of our proposal theoretically and empirically.