Decommitting in multi-agent execution in non-deterministic environment: experimental approach

ABSTRACT

The process of planning in complex, multi-actor environment depends strongly on the ability of the individual actors to perform intelligent decommitment upon specific changes in the environment. Reasoning about decommitment alternatives during the planning process contributes to flexibility and robustness of the resulting plan. In this article we formally introduce and discuss three specific decommitment rules: (i) relaxation, (ii) delegation and (iii) full decommitment. We argue that appropriate selection, setting and preference ordering of the decommitment rules contributes to robustness (measured as a number of failures) of the overall plans. The presented claims are supported by empirical experiments.

REFERENCES

• 1: Anthony Barrett , Daniel S. Weld, Partial-order planning: evaluating possible efficiency gains, Artificial Intelligence, v.67 n.1, p.71-112, May 1994 [doi>10.1016/0004-3702(94)90012-4]
• 2: C. Boutilier, T. Dean, and S. Hanks. Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1--94, 1999.
• 3: E. Allen Emerson , Jai Srinivasan, Branching time temporal logic, Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, School/Workshop, p.123-172, May 30-June 03, 1988
• 4: Maria Fasli, On Commitments, Roles, and Obligations, Revised Papers from the Second International Workshop of Central and Eastern Europe on Multi-Agent Systems: From Theory to Practice in Multi-Agent Systems, p.93-102, September 26-29, 2001
• 5: H. Levesque, P. Cohen, and J. Nunes. On acting together. In AAAI-90 Proceedings, Eighth National Conference on Artificial Intelligence, volume 2, pages 94--99, Cambridge, MA, USA, 1990. MIT Press.
• 6: S. M. Majercik and M. L. Littman. MAXPLAN: A new approach to probabilistic planning. In Artificial Intelligence Planning Systems, pages 86--93, 1998.
• 7: A. Mallya, P. Yolum, and M. Singh. Resolving commitments among autonomous agents. In F. Dignum, editor, Advances in Agent Communication. International Workshop on Agent Communication Languages, ACL 2003, volume 2922 of LNCS, pages 166--82. Springer-Verlag, Berlin, Germany, 2003.
• 8: D. J. Musliner, E. H. Durfee, and K. G. Shin. CIRCA: A cooperative intelligent real time control architecture. IEEE Transactions on Systems, Man, and Cybernetics, 23(6):1561--1574, -- 1993.
• 9: Munindar P. Singh , Anand S. Rao , Michael P. Georgeff, Formal methods in DAI: logic-based representation and reasoning, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
• 10: R. G. Smith, The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver, IEEE Transactions on Computers, v.29 n.12, p.1104-1113, December 1980 [doi>10.1109/TC.1980.1675516]
• 11: M. Veloso and P. Stone. Flecs: Planning with a flexible commitment strategy. Journal of Artificial Intelligence Research, 3:25--52, 1995.
• 12: M. Wooldridge. Reasoning about Rational Agents. Intelligent robotics and autonomous agents. The MIT Press, 2000.
• 13: M. Wooldridge and N. Jennings. Cooperative problem solving. Journal of Logics and Computation, 9(4):563--594, 1999.
• 14: Ping Xuan , Victor R. Lesser, Incorporating Uncertainty in Agent Commitments, 6th International Workshop on Intelligent Agents VI, Agent Theories, Architectures, and Languages (ATAL),, p.57-70, July 15-17, 1999

INDEX TERMS

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

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

General Terms:
Experimentation, Measurement, Performance, Reliability, Verification

Keywords:
commitments based planning, decommitment rule, non-deterministic environment, social commitment