A model of contingent planning for agent programming languages

ABSTRACT

In this paper, we develop a formal model of planning for an agent that is operating in a dynamic and incompletely known environment. We assume that both the agent's task and the behavior of the agents in the environment are expressed as high-level nondeterministic concurrent programs in some agent programming language (APL). In this context, planning must produce a deterministic conditional plan for the agent that can be successfully executed against all possible executions of the environment program. We handle actions with nondeterministic effects, as well as sensing actions, by treating them as actions that trigger an environmental reaction that is not under the planning agent's control. Our model of contingent planning is specified for a generic APL with a transition semantics. Within this model, we devise a general procedure for computing the contingent plans. We also show how the model can be instantiated in the situation calculus with programs for the agent and the environment expressed in ConGolog, and we describe an implementation of the planning mechanism in this case.

REFERENCES

• 1: J. Baier and S. McIlraith. On planning with programs that sense. In Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR06), pages 492--502, Lake District, UK, June 2006.
• 2: J. A. Baier, C. Fritz, and S. A. McIlraith. Exploiting procedural domain control knowledge in state-of-the-art planners. In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007), Providence, Rhode Island, USA, September 22 - 26 2007.
• 3: A. Bouguerra and L. Karlsson. PC-SHOP: A probabilistic-conditional hierarchical task planner. Intelligenza Artificiale, 2(4):44--50, 2005.
• 4: Giuseppe de Giacomo , Yves Lespérance , Hector J. Levesque, ConGolog, a concurrent programming language based on the situation calculus, Artificial Intelligence, v.121 n.1-2, p.109-169, Aug. 2000 [doi>10.1016/S0004-3702(00)00031-X]
• 5: G. De Giacomo and H. J. Levesque. An incremental interpreter for high-level programs with sensing. In H. J. Levesque and F. Pirri, editors, Logical Foundations for Cognitive Agents, pages 86--102. Springer-Verlag, 1999.
• 6: G. De Giacomo, S. Sardiña, Y. Lespérance, and H. J. Levesque. On deliberation under incomplete information and the inadequacy of entailment and consistency-based formalizations. In Working Notes of the 1st Int. Workshop on Programming Multiagent Systems (PROMAS-2003), Melbourne, July 2003.
• 7: A. Farinelli, A. Finzi, and T. Lukasiewicz. Team programming in Golog under partial observability. In M. M. Veloso, editor, IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007, pages 2097--2102, 2007.
• 8: Koen V. Hindriks , Frank S. De Boer , Wiebe Van Der Hoek , John-Jules Ch. Meyer, Agent Programming in 3APL, Autonomous Agents and Multi-Agent Systems, v.2 n.4, p.357-401, November 1999 [doi>10.1023/A:1010084620690]
• 9: H. J. Levesque, R. Reiter, Y. Lespérance, F. Lin, and R. B. Scherl. GOLOG: A logic programming language for dynamic domains. Journal of Logic Programming, 31(59--84), 1997.
• 10: G. Plotkin. A structural approach to operational semantics. Technical Report DAIMI-FN-19, Computer Science Dept., Aarhus University, Denmark, 1981.
• 11: Anand S. Rao, AgentSpeak(L): BDI agents speak out in a logical computable language, Proceedings of the 7th European workshop on Modelling autonomous agents in a multi-agent world : agents breaking away: agents breaking away, p.42-55, February 1996, Einhoven, The Netherlands
• 12: Sebastian Sardina , Giuseppe De Giacomo , Yves Lespérance , Hector J. Levesque, On the Semantics of Deliberation in Indigolog—from Theory to Implementation, Annals of Mathematics and Artificial Intelligence, v.41 n.2-4, p.259-299, August 2004 [doi>10.1023/B:AMAI.0000031197.13122.aa]
• 13: S. Sardiña, G. De Giacomo, Y. Lespérance, and H. J. Levesque. On the limits of planning over belief states under strict uncertainty. In P. Doherty, J. Mylopoulos, and C. A. Welty, editors, Principles of Knowledge Representation and Reasoning, Proc. of the 10th Int. Conf. (KR2006), pages 463--471, Windemere, UK, June 2006. AAAI Press.
• 14: Sebastian Sardina , Lavindra de Silva , Lin Padgham, Hierarchical planning in BDI agent programming languages: a formal approach, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160813]
• 15: Sebastian Sardina , Lin Padgham, Goals in the context of BDI plan failure and planning, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329134]
• 16: S. Sardiña and S. Vassos. The Wumpus World in IndiGolog: A preliminary report. In Working Notes of the 6th Workshop on Nonmonotonic Reasoning, Action, and Change (at IJCAI-05), Edinburgh, 2005.

INDEX TERMS

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

General Terms:
Languages

Keywords:
agent programming languages, contingent planning