Agent programming via planning programs

ABSTRACT

We imagine agent "planning" programs as programs built from achievement and maintenance goals. Their executions require the ability to meet such goals while respecting the programs' control flow. The question then is: can we always guarantee the execution of such programs? In this paper, we define this novel planning-programming problem formally, and propose a sound, complete and optimal wrt computational complexity technique to actually generate a solution by appealing to recent results in LTL-based synthesis of reactive systems.

References

1. A. Cimatti, M. Pistore, M. Roveri, and P. Traverso. Weak, Strong, and Strong Cyclic Planning via Symbolic Model Checking. Artificial Intelligence, 147(1--2):35--84, 2003.
2. G. De Giacomo, R. De Masellis, and F. Patrizi. Composition of partially observable services exporting their behaviour. In Proc. of ICAPS'09, 2009.
3. K. Erol, J. A. Hendler, and D. S. Nau. Complexity Results for HTN Planning. Annals of Mathematics and Artificial Intelligence, 18(1):69--93, 1996.
4. M. Ghallab, D. S. Nau, and P. Traverso. Automated Planning: Theory and Practice. Morgan Kaufmann, 2004.
5. K. V. Hindriks and T. Roberti. GOAL as a planning formalism. In Proc. of MATES, volume 5774 of LNCS, pages 29--40. Springer, 2009.
6. S. Kerjean, F. Kabanza, R. St.-Denis, and S. Thiébaux. Analyzing LTL model checking techniques for plan synthesis and controller synthesis (work in progress). Electronic Notes Theoretical Comput. Science, 149(2):91--104, 2006.
7. O. Kupferman and M. Y. Vardi. Synthesis with incomplete information. In D. G. Howard Barringer, Michael Fisher and G. Gough, editors, Advances in Temporal Logic, pages 109--127. Kluwer Academic Publishers, Jan. 2000.
8. Y. Lespérance, H. J. Levesque, F. Lin, D. Marcu, R. Reiter, and R. B. Scherl. Foundations of a Logical Approach to Agent Programming. In Proc. of Int. Workshop ATAL. 1995.
9. H. J. Levesque and R. Reiter. High-level Robotic Control: Beyond Planning. A Position Paper. In AIII 1998 Spring Symposium: Integrating Robotics Research: Taking the Next Big Leap, Mar. 1998.
10. R. Milner. An algebraic definition of simulation between programs. In Proc. of IJCAI, pages 481--489, 1971.
11. N. Piterman, A. Pnueli, and Y. Sa'ar. Synthesis of Reactive(1) Designs. In VMCAI, pages 364--380, 2006.
12. A. Pnueli and R. Rosner. On the Synthesis of a Reactive Module. In Proc. of POPL, pages 179--190, 1989.
13. A. S. Rao. Agentspeak(L): BDI agents speak out in a logical computable language. In Proc. of MAAMAW, volume 1038 of LNCS, pages 42--55. Springer, 1996.
14. J. Rintanen. Complexity of planning with partial observability. In Proc. of ICAPS, pages 345--354, 2004.
15. S. Sardina and G. De Giacomo. Realizing multiple autonomous agents through scheduling of shared devices. In Proc. of ICAPS, pages 304--312, 2008.
16. S. Sardina, G. De Giacomo, Y. Lespérance, and H. J. Levesque. On the Limits of Planning over Belief States. In Proc. of KR, pages 463--471, 2006.
17. S. Sardina, L. P. de Silva, and L. Padgham. Hierarchical planning in BDI agent programming languages: A formal approach. In Proc. of AAMAS, pages 1001--1008, 2006.
18. Y. Shoham. Agent-oriented programming. Artificial Intelligence Journal, 60:51--92, 1993.
19. B. van Riemsdijk, M. Dastani, and J.-J. Meyer. Semantics of declarative goals in agent programming. In Proc. of AAMAS, pages 133--140, 2005.
20. M. Y. Vardi. An automata-theoretic approach to linear temporal logic. In Logics for Concurrency: Structure versus Automata, volume 1043 of LNCS, pages 238--266, 1996.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

• Theory of computation

  • Logic