An agent-oriented multiagent planning system

ABSTRACT

this paper describes a multiagent planning system, MuPAC, that formulates cooperative plans efficiently. It contains three features: meta-level planning, breakable and unbreakable action representations, and an integrated agent screening and assignment procedure. The meta-level planning transforms an original goal statement into a skeletal plan, which is easier to follow and helps reduce the chance of conflicts at low-level actions. The breakable/unbreakable action representation specifies specific agent-action requirements. It also specifies concurrency and cooperation possibilities among actions. It makes plan generation and agent assignment straight forward, thus reducing the reasoning time of finding parallelism and cooperation among agents. The integrated agent screening and assignment procedure formulates plans following the skeletal plan. The performance of MuPAC has been discussed along four aspects: planning efficiency, planning flexibility, agent cooperation, and plan quality. Results have shown that significant improvement has been achieved.

REFERENCES

• 1: K.-H. Chang , W. G. Wee, A Planning Model with Problem Analysis and Operator Hierarchy, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.5, p.672-675, September 1988 [doi>10.1109/34.6775]
• 2: P.R. Cohen and E. A. Feigenbmttn, "The Handbook of Artificial Intelligear.~", Vol. 3, William Kaufmann Inc., Los Altos, California, 1982, pp. 515-562.
• 3: R. E. Fikcs and N. J. Nilsson, "STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving," Artificial Intelligence, Vol. 2, 1971, pp. 189-208.
• 4: M. Georgeff, "Commtn~eation and Interaction in Multiagent Planning", Proceedings of AAAI, 1983, pp. 125-129.
• 5: K. Konolige and N. J. Nilssort, "Multiple Agent Planning System", Proceedings of AAAI, 1980, pp.138-142.
• 6: A. L. Lamky, 'q.,a:alized Event-BaseA Reasoning for Multiagent Domains", Technical Note 423, 1988, SRI International, Menlo Park, Califomia.
• 7: E. P. D. Pednault, "Formulating Multiagent Dynamic- World Problems in the Classical Planning Framework", in Reasoning about Actions and Plans: Proceedings of the 1986 Workshop, Morgan Kaufmmm Publishers, San Mateo, CA, 1987, pp. 4%$2.
• 8: Suebskul Phiphobmongkol, A multiagent planner using agent constraints, Auburn University, Auburn, AL, 1992
• 9: J. S. Rosenschein, "Synchronization of Multiagent Plan", Proceedings of AAAI, 1982, pp. 115-119.
• 10: E. D. Sacerdoti, 'Planning in a Hierarchy of Abstraction Space", Artificial Intelligence, 1974(5), pp. 115-135.
• 11: C. Stuart, "An Implementation of a Multiagent Plan Synchronizer", Proceedings of IJCAI, 1985, Vol. 2, pp. 1031-1033.
• 12: David E. Wilkins, Domain-independent planning: representation and plan generation, Artificial Intelligence, v.22 n.3, p.269-301, April 1984 [doi>10.1016/0004-3702(84)90053-5]
• 13: D. E. Wilkins, "Can AI Planners Solve Practical Problems?",Technical Note 468R, November 1989, SRI International, Menlo Park, California

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Performance