Technion, IEM faculty - Information Systems seminar
Speaker: Yevgeni Nus
Title: Automatic Problem Decomposition for Multi-Agent Planning
Date: 12/04/2011
Time: 13:00
Place: Bloomfield-527
Abstract:  <>
Or read this below:
The field of automated, domain-independent planning aims at building 
algorithms able to synthesize a course of actions to achieve certain 
goals. In general, planning algorithms perform reachability analysis in 
large-scale state modules 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 task. One 
of the methods used to reduce its difficulty is problem decomposition.
In our work we present a new method for problem decomposition, designed 
especially for multiple-agent (unit) real time strategy games (RTS) 
domains. The central idea is to divide the sub-goals of the original 
problem between the different groups of agents. Each such group becomes 
responsible for achieving its designated set of sub-goals. By doing so, 
we actually decompose the main planning task into several independent 
sub-planning task. Each sub-task can be solved independently and then 
all the solutions can be combined into a plan for the original task. 
Decomposing the problem can facilitate problem solving, by reducing 
search complexity, and help the planner to produce a more balanced work 
load between the units. Moreover, a decomposed planning task can be 
solved in a parallel manner by a distributed system, thus significantly 
reducing the response time of a system 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 critical, as the true state of the simulated world is constantly 
M.Sc. seminar; advisor: Carmel Domshlak (Technion).
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>