Multiagent planning through plan repair

ABSTRACT

We present a novel approach to multiagent planning for self-interested agents. The main idea behind our approach is that multiagent planning systems should be built upon (single-agent) plan repair systems. In our system agents can exchange goals and subgoals through an auction, using their own (planning) heuristics and utility functions to determine when to auction and what to bid. Some experimental results for a logistics domain show that this system can be used to support the coordination of self-interested agents.

REFERENCES

• 1: F. Bacchus, H. Kautz, D. Smith, D. Long, H. Geffner, and J. Koehler. The 5th AIPS Planning Competition. http://www.cs.toronto.edu/aips2000/, 2000.
• 2: J. Collins, M. Tsvetovatyy, M. Gini, and B. Mobasher. MAGNET: A multi-agent contracting system for plan execution. In Proc. of SIGMAN, 1998.
• 3: Keith Decker , Jinjiang Li, Coordinating Mutually Exclusive Resources using GPGP, Autonomous Agents and Multi-Agent Systems, v.3 n.2, p.133-157, June 2000 [doi>10.1023/A:1010074611407]
• 4: M. DesJardins, E. Durfee, C. Ortiz, and M. Wolverton. A survey of research in distributed, continual planning. AI Magazine, 20(4):13--22, 2000.
• 5: K. Kleinmann, R. Lazarus, and R. Tomlinson. An infrastructure for adaptive control of multi-agent systems. In IEEE Int. Conf. on Integration of Knowledge Intensive Multi-Agent Systems, pages 230--236, 2003.
• 6: Thomas W. Malone , Kevin Crowston, The interdisciplinary study of coordination, ACM Computing Surveys (CSUR), v.26 n.1, p.87-119, March 1994 [doi>10.1145/174666.174668]
• 7: Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, v.135 n.1-2, p.1-54, 02/01/2002 [doi>10.1016/S0004-3702(01)00159-X]
• 8: R. van der Krogt and M. de Weerdt. Plan repair as an extension of planning. In Proc. of the Int. Conf. on Automated Planning and Scheduling, 2005.
• 9: R. van der Krogt and M. de Weerdt. Self-interested planning agents using plan repair. In Proc. of the ICAPS Workshop on Multiagent Planning and Scheduling, 2005.
• 10: William E. Walsh , Michael P. Wellman, A Market Protocol for Decentralized Task Allocation, Proceedings of the 3rd International Conference on Multi Agent Systems, p.325, July 03-07, 1998
• 11: H. L. S. Younes and R. G. Simmons. VHPOP: Versatile heuristic partial order planner. JAIR, 20:405--430, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Design

Keywords:
multiagent planning