Propositional planning in BDI agents

ABSTRACT

This paper aims to describe the relationship between propositional planning systems and the process of means-end reasoning used by BDI agents. To show such relationship, we define a mapping from BDI mental states to propositional planning problems and from propositional plans back to mental states. In order to test the viability of such mapping, we have implemented it in an extension of a BDI agent model through the use of Graphplan as the propositional planning algorithm. The implementation was applied to model a case study of an agent controlled production cell.

REFERENCES

• 1: Jose Julio Alferes , Luis Moniz Pereira , J. Siekmann , J. G. Carbonell, Reasoning with Logic Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 2: 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]
• 3: Rafael H. Bordini , Michael Fisher , Carmen Pardavila , Michael Wooldridge, Model checking agentspeak, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860641]
• 4: M. E. Bratman. Intention, Plans and Practical Reason. Harvard University Press, 1987.
• 5: M. E. Bratman, D. J. Israel, and M. E. Pollack. Plans and resource-bounded practical reasoning. Computational Intelligence, 4(4):349--355, 1988.
• 6: Tom Bylander, The computational complexity of propositional STRIPS planning, Artificial Intelligence, v.69 n.1-2, p.165-204, Sept. 1994 [doi>10.1016/0004-3702(94)90081-7]
• 7: David Chapman, Planning for conjunctive goals, Artificial Intelligence, v.32 n.3, p.333-377, July 1987 [doi>10.1016/0004-3702(87)90092-0]
• 8: Philip R. Cohen , Hector J. Levesque, Intention is choice with commitment, Artificial Intelligence, v.42 n.2-3, p.213-261, March 1990 [doi>10.1016/0004-3702(90)90055-5]
• 9: W. V. der Hoek and M. Wooldridge. Towards a logic of rational agency. Logic Journal of the IGPL, 11(2):133--157, 2003.
• 10: M. d'Inverno and M. Luck. Engineering AgentSpeak(L): A formal computational model. Journal of Logic and Computation, 8(3):233--260, 1998.
• 11: Francois F. Ingrand , Michael P. Georgeff , Anand S. Rao, An architecture for Real-Time Reasoning and System Control, IEEE Expert: Intelligent Systems and Their Applications, v.7 n.6, p.34-44, December 1992 [doi>10.1109/64.180407]
• 12: Nicholas R. Jennings, On agent-based software engineering, Artificial Intelligence, v.117 n.2, p.277-296, March 2000 [doi>10.1016/S0004-3702(99)00107-1]
• 13: Henry Kautz , Bart Selman, Planning as satisfiability, Proceedings of the 10th European conference on Artificial intelligence, p.359-363, August 1992, Vienna, Austria
• 14: J. Köhler. Solving complex planning tasks through extraction of subproblems. In R. Simmons, M. Veloso, and S. Smith, editors, Proc. of the 4th AIPS, pages 62--69, 1998. AAAI Press.
• 15: R Kowalski , M Sergot, A logic-based calculus of events, New Generation Computing, v.4 n.1, p.67-95, 1986 [doi>10.1007/BF03037383]
• 16: Nick Lacey , Henry Hexmoor , Gordon Beavers, Planning at the Intention Level, Proceedings of the Fifteenth International Florida Artificial Intelligence Research Society Conference, p.8-12, May 14-16, 2002
• 17: D. Long and M. Fox. Efficient implementation of the plan graph in STAN. Journal of Artificial Intelligence Research, 10:87--115, 1999.
• 18: D. Long and M. Fox. Automatic synthesis and use of generic types in planning. In S. Chien. S. Kambhampati, and C. A. Knoblock, editors, Proc of the 5th AIPS, pages 196--205, 2000. AAAI Press.
• 19: M. C. Móra, J. G. Lopes, R. M. Viccari, and H. Coelho. BDI models and systems: Reducing the gap. In Proc. of the 5th International Workshop of Intelligent Agents, 1999. Springer.
• 20: B. Nebel. On the compilability and expressive power of propositional planning formalisms. Journal of Artificial Intelligence Research (JAIR), 12:271--315, 2000.
• 21: NIDE Naoyuki , Shiro Takata, Deduction systems for BDI logics using sequent calculus, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544955]
• 22: A. S. Rao and M. P. Georgeff. Formal models and decision procedures for multi-agent systems. Technical Report 61, AAII, 1995. Technical Note.
• 23: Martijn Schut , Michael Wooldridge, The control of reasoning in resource-bounded agents, The Knowledge Engineering Review, v.16 n.3, p.215-240, September 2001 [doi>10.1017/S0269888901000157]
• 24: David E. Smith , Daniel S. Weld, Temporal Planning with Mutual Exclusion Reasoning, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.326-337, July 31-August 06, 1999
• 25: A. M. Turing. Intelligent machinery. Machine Intelligence, 5:3--23, 1948.
• 26: Peter Wegner, Why interaction is more powerful than algorithms, Communications of the ACM, v.40 n.5, p.80-91, May 1997 [doi>10.1145/253769.253801]
• 27: D. S. Weld. Recent advances in AI planning. AI Magazine, 20(2):93--123, 1999.
• 28: The Computational Complexity of Agent Design Problems, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.341, July 10-12, 2000
• 29: M. Wooldridge. Reasoning about Rational Agents. The MIT Press, 2000.

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

Keywords:
BDI, BDI Model, X-BDI, planning, propositional planning