|dc.contributor.author||Crosby, Matthew David||
|dc.description.abstract||Classical planning problems consist of an environment in a predefined state; a set of
deterministic actions that, under certain conditions, change the state of the environment;
and a set of goal conditions. A solution to a classical planning problem is a sequence of
actions that leads from the initial state to a state satisfying the problem’s goal conditions.
There are many methods for finding solutions to classical planning problems, and a
popular technique is to exploit structures that commonly occur. One such structure,
apparent in many planning domains, is a breakdown of the problem into multiple agents.
However, methods for finding and exploiting multiagent structures are not prevalent in
the literature and are currently not competitive.
This thesis sets out to rectify this problem. Its first main contribution, is to introduce
a domain independent algorithm for extracting multiagent structure from classical
planning problems. The algorithm relies on identifying a generalisable property of
agents in planning; namely, that agents are entities with an internal state, a part of the
planning problem that, under a certain distribution of actions, only they can modify.
Once this is appropriately formalised, the decomposition algorithm is introduced and
is shown to produce identifiably multiagent decompositions over all of the classical
planning domains used in the International Planning Competitions, even finding more
detailed decompositions than are used by humans in certain cases.
Solving multiagent planning problems can be challenging because a solution may
require complex inter-agent coordination. The second main contribution of the thesis
is a heuristic planning algorithm that effectively exploits the structure of decomposed
domains. The algorithm transforms the coordination problem into a process of subgoal
generation that can be solved efficiently under a well-known relaxation in planning. The
generated subgoals guide the search so that it is always performed by one single-agent
subproblem at a time. The algorithm is evaluated and shown to greatly outperform
current state-of-the-art planners over decomposable domains.
The thesis also includes discussion of the possible extensions of this work, to include
the multiagent concepts of self-interested agents and concurrent actions. Results from
the multiagent planning literature are improved upon and a new solution concept is
presented that accounts for the ‘farsightedness’ inherent in planning. A method is
then presented that can find stable solutions for a certain class of multiagent planning
problems. A new method is introduced for modelling concurrent actions that allows
them to be written without requiring knowledge of each other agent in the domain, and
it is shown how such problems can be solved by a translation to single-agent planning.||en_US
|dc.contributor.sponsor||Engineering and Physical Sciences Research Council (EPSRC)||en_US
|dc.publisher||The University of Edinburgh||en_US
|dc.relation.hasversion||Crosby, M. and Rovatsos, M. (2011). Heuristic multiagent planning with self-interested agents. Autonomous Agents and Multi-Agent Systems, 22:1213–1214.||en_US
|dc.relation.hasversion||Crosby, M., Rovatsos, M., and Petrick, R. (2013). Automated agent decomposition for classical planning. International Conference on Automated Planning and Scheduling, 23:46–54.||en_US
|dc.title||Multiagent classical planning||en_US
|dc.type||Thesis or Dissertation||en_US
|dc.type.qualificationname||PhD Doctor of Philosophy||en_US