Theoretic study of distributed graph planning

ABSTRACT

In situations where it needs the actions of different agents to accomplish a task, the planning for the task involves selecting and organizing the actions belonging to multiple agents. Most existing multi-agent planning approaches to solving such a planning problem rely on the global knowledge of the capabilities of the agents, and are confronted with difficulties when the availability of the global knowledge is impossible or undesirable. Previously, we have proposed a distributed multi-agent planning algorithm Dis-graph planning to address the difficulties, which enables multiple agents to cooperate in generating a plan without relying on the global knowledge. In the work of this paper, we performed a theoretical study of Dis-graph planning approach, discussing its critical features such as completeness, soundness and terminability.

REFERENCES

• 1: Avrim L. Blum , Merrick L. Furst, Fast planning through planning graph analysis, Artificial Intelligence, v.90 n.1-2, p.281-300, Feb. 1997 [doi>10.1016/S0004-3702(96)00047-1]
• 2: M. de Weerdt, A. ter Mors, and C. Witteveen. Multi-agent planning: An introduction to planning and coordination. In Handouts of the European Agent Summer School, pages 1--32, 2005.
• 3: Edmund H. Durfee, Distributed problem solving and planning, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
• 4: Dana Nau , Malik Ghallab , Paolo Traverso, Automated Planning: Theory & Practice, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 5: M. P. Papazoglou , D. Georgakopoulos, Introduction, Communications of the ACM, v.46 n.10, October 2003 [doi>10.1145/944217.944233]
• 6: Jian Feng Zhang , Ryszard Kowalczyk, Agent-based Dis-graph Planning Algorithm for Web Service Composition, Proceedings of the International Conference on Computational Inteligence for Modelling Control and Automation and International Conference on Intelligent Agents Web Technologies and International Commerce, p.258, November 28-December 01, 2006 [doi>10.1109/CIMCA.2006.37]
• 7: Jian Feng Zhang , Xuan Thang Nguyen , Ryszard Kowalczyk, Graph-based multiagent replanning algorithm, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329275]

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

Keywords:
distributed planning graph, multi-agent planning