This paper proposes FMAP (Forward Multi-Agent Planning), a fully-distributed multi-agent planning method that integrates planning and coordination. Although FMAP is specifically aimed at solving problems that require cooperation among agents, the flexibility of the domain-independent planning model allows FMAP to tackle multi-agent planning tasks of any type. In FMAP, agents jointly explore the plan space by building up refinement plans through a complete and flexible forward-chaining partial-order planner. The search is guided by @math , a novel heuristic function that is based on the concepts of Domain Transition Graph and frontier state and is optimized to evaluate plans in distributed environments. Agents in FMAP apply an advanced privacy model that allows them to adequately keep private information while communicating only the data of the refinement plans that is relevant to each of the participating agents. Experimental results show that FMAP is a general-purpose approach that efficiently solves tightly-coupled domains that have specialized agents and cooperative goals as well as loosely-coupled problems. Specifically, the empirical evaluation shows that FMAP outperforms current MAP systems at solving complex planning tasks that are adapted from the International Planning Competition benchmarks.
There is a large body of work on plan-merging techniques. The work in @cite_24 introduces a distributed coordination framework based on partial-order planning that addresses the interactions that emerge between the agents' local plans. This framework, however, does not consider privacy. The proposal in @cite_22 is based on the iterative revision of the agents' local plans. Agents in this model cooperate by mutually adapting their local plans, with a focus on improving their common or individual benefit. This approach also ignores privacy and agents are assumed to be fully cooperative. The approach in @cite_27 uses multi-agent plan repair to solve inconsistencies among the agents' local plans while maintaining privacy. @math -SATPLAN @cite_18 extends a satisfiability-based planner to coordinate the agents' local plans by studying positive and negative interactions among them.
@cite_24 @cite_27 @cite_18 @cite_22
1697381716 1506509683 2167131933
Coordination can be required whenever multiple agents plan to achieve their individual goals independently, but might mutually benefit by coordinating their plans to avoid working at cross purposes or duplicating effort. Although variations of such problems have been studied in the literature, there is as yet no agreement over a general characterization of them. In this paper, we formally define a common coordination problem subclass, which we call the Multiagent Plan Coordination Problem, that is rich enough to represent a wide variety of multiagent coordination problems. We then describe a general framework that extends the partial-order, causal-link plan representation to the multiagent case, and that treats coordination as a form of iterative repair of plan flaws between agents. We show that this algorithmic formulation can scale to the multiagent case better than can a straightforward application of the existing plan coordination techniques, highlighting fundamental differences between our algorithmic framework and these earlier approaches. We then examine whether and how the Multiagent Plan Coordination Problem can be cast as a Distributed Constraint Optimization Problem (DCOP). We do so using ADOPT, a state-of-the-art system that can solve DCOPs in an asynchronous, parallel manner using local communication between individual computational agents. We conclude with a discussion of possible extensions of our work. In dynamic environments, agents have to deal with changing situations. In these cases, repairing a plan is often more efficient than planning from scratch, but existing planning techniques are more advanced than existing plan repair techniques. Therefore, we propose a straightforward method to extend planning techniques such that they are able to repair plans. This is possible, because plan repair consists of two different operations: (i) removing obstructing constraints (such as actions) from the plan, and (ii) adding actions to achieve the goals. Adding actions is similar to planning, but as we demonstrate, planning heuristics can also be used for removing constraints, which we call unrefinement. We present a plan repair template that reflects these two operations, and we present a heuristic for unrefinement that can make use of an arbitrary existing planning technique. We apply this method to an existing planning system (VHPOP) resulting in POPR, a plan repair system that performs much better than replanning from scratch, and also significantly better than another recent plan repair method (GPG). Furthermore, we show that the plan repair template is a generalisation of existing plan repair methods. Abstract In order to model plan coordination behavior of agents we develop a simple framework for representing plans, resources and goals of agents. Plans are represented as directed acyclic graphs of skills and resources that, given adequate initial resources, can realize special resources, called goals. Given the storage costs of resources, application costs of skills, and values of goals, it is possible to reason about the profits of a plan for an agent. We then model two forms of plan coordination behavior between two agents, viz. fusion , aiming at the maximization of the total yield of the agents involved, and collaboration , which aims at the maximization of the individual yield of each agent. We argue how both forms of cooperation can be seen as iterative plan revision processes. We also present efficient polynomial algorithms for agent plan fusion and collaboration that are based on this idea of iterative plan revision. Both the framework and the fusion algorithm will be illustrated by an example from the field of transportation, where agents are transportation companies.