Continual collaborative planning for mixed-initiative action and interaction

ABSTRACT

Multiagent environments are often highly dynamic and only partially observable which makes deliberative action planning computationally hard. In many such environments, however, agents can take a more proactive approach and suspend planning for partial plan execution, especially for active information gathering and interaction with others. This paper presents a new algorithm for Continual Collaborative Planning (CCP) that enables agents to deliberately interleave planning, acting, perception and communication. Our implementation of CCP has been evaluated with MAPSIM, a tool that automatically generates multiagent simulations from formal multiagent planning (MAP) domains. For different such simulations, we show how CCP leads to collaborative planning and acting and, despite minimal linguistic capabilities, to fairly natural dialogues between agents.

REFERENCES

• 1: N. Blaylock, J. Allen, and G. Ferguson. Managing communicative intentions with collaborative problem solving. In Current and New Directions in Dialogue. Kluwer, 2003.
• 2: M. Brenner. Situation-aware interpretation, planning and execution of user commands by autonomous robots. In Proceedings of IEEE RO-MAN 2007, 2007.
• 3: M. Brenner. The multiagent planning language MAPL. Technical report, Albert-Ludwigs-Universität, Institut für Informatik, Freiburg, Germany, 2008.
• 4: Michael Brenner , Bernhard Nebel, Continual planning and acting in dynamic multiagent environments, Proceedings of the 2006 international symposium on Practical cognitive agents and robots, November 27-28, 2006, Perth, Australia [doi>10.1145/1232425.1232431]
• 5: M. DesJardins, E. Durfee, J. C. Ortiz, and M. Wolverton. A survey of research in distributed, continual planning. The AI Magazine, 1999.
• 6: O. Etzioni, S. Hanks, D. Weld, D. Draper, N. Lesh, and M. Williamson. An approach to planning with incomplete information. In Proc. KR-92, 1992.
• 7: M. Fox and D. Long. PDDL 2.1: an extension to PDDL for expressing temporal planning domains. JAIR, 2003.
• 8: K. Golden. Leap before you look: Information gathering in the PUCCINI planner. In Proc. AIPS-98, 1998.
• 9: Barbara J. Grosz , Sarit Kraus, Collaborative plans for complex group action, Artificial Intelligence, v.86 n.2, p.269-357, Oct. 1996 [doi>10.1016/0004-3702(95)00103-4]
• 10: M. Helmert. The Fast Downward planning system. JAIR, 26:191--246, 2006.
• 11: C. A. Knoblock. Planning, executing, sensing, and replanning for information gathering. In Proc. IJCAI-95, 1995.
• 12: Karen E. Lochbaum, A collaborative planning model of intentional structure, Computational Linguistics, v.24 n.4, p.525-572, December 1998
• 13: S. Thiebaux, J. Hoffmann, and B. Nebel. In defense of axioms in PDDL. In Proc. IJCAI, 2003.
• 14: Makoto Yokoo , Katsutoshi Hirayama, Algorithms for Distributed Constraint Satisfaction: A Review, Autonomous Agents and Multi-Agent Systems, v.3 n.2, p.185-207, June 2000 [doi>10.1023/A:1010078712316]

INDEX TERMS

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

General Terms:
Algorithms, Design, Languages

Keywords:
BDI, distributed problem solving, multiagent planning, reactive vs deliberative behaviour, speech act theory