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.
Plan-merging techniques are not very well suited for coping with tightly-coupled tasks as they may introduce exponentially many ordering constraints in problems that require great coordination effort @cite_24 . In general, plan merging is not an effective method for attaining cooperative goals since this resolution scheme generally assumes that each agent is able to solve a subset of the task's goals by itself. However, some approaches use plan merging to coordinate local plans of specialized agents. In this case, the effort is placed on discovering the interaction points among agents through the public information that they share. For instance, Planning First @cite_5 introduces a cooperative MAP approach for loosely-coupled tasks, in which specialized agents carry out planning individually through a state-based planner. The resulting local plans are then coordinated by solving a distributed Constraint Satisfaction Problem (CSP) @cite_29 . This combination of CSP and planning to solve MAP tasks was originally introduced by the MA-STRIPS framework @cite_35 .
@cite_24 @cite_5 @cite_29 @cite_35
1697381716 1616569656 2124254247
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. We present a fully distributed multi-agent planning algorithm. Our methodology uses distributed constraint satisfaction to coordinate between agents, and local planning to ensure the consistency of these coordination points. To solve the distributed CSP efficiently, we must modify existing methods to take advantage of the structure of the underlying planning problem, m multi-agent planning domains with limited agent interaction, our algorithm empirically shows scalability beyond state of the art centralized solvers. Our work also provides a novel, real-world setting for testing and evaluating distributed constraint satisfaction algorithms in structured domains and illustrates how existing techniques can be altered to address such structure. Loosely coupled multi-agent systems are perceived as easier to plan for because they require less coordination between agent sub-plans. In this paper we set out to formalize this intuition. We establish an upper bound on the complexity of multi-agent planning problems that depends exponentially on two parameters quantifying the level of agents' coupling, and on these parameters only. The first parameter is problem-independent, and it measures the inherent level of coupling within the system. The second is problem-specific and it has to do with the minmax number of action-commitments per agent required to solve the problem. Most importantly, the direct dependence on the number of agents, on the overall size of the problem, and on the length of the agents' plans, is only polynomial. This result is obtained using a new algorithmic methodology which we call "planning as CSP+planning". We believe this to be one of the first formal results to both quantify the notion of agents' coupling, and to demonstrate a multi-agent planning algorithm that, for fixed coupling levels, scales polynomially with the size of the problem.