Affiliations: Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109, USA | [x] Delft University of Technology, PO Box 5031, 2600 GA Delft, The Netherlands | [y] Jet propulsion Laboratory, 4800 Oak Grove Dr., Pasadena, CA 91750, USA
Abstract: 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.
