Project: Answer Set Programming for Reactive Planning and Execution Monitoring
supported by the Austrian Science Funds (FWF) under project number P16536)
Contents
Project team
Motivation and Background
Planning plays an important role in many relevant areas of AI. However, in real world applications the classical planning problem (i.e., finding a sequence of actions to execute in order to reach a certain goal) is often only of limited relevance as soon as exogenous events can change the state of the world or unforeseen effects can arise from taking an action during execution.
On the other hand, especially in robotics and software agents, approaches with pure reactive behavior and no planning capabilities are often inflexible and allow only for executing hard-coded ``plans'' from a fixed library. Obviously, hybrid approaches are necessary, where planning, monitoring and reacting to the real world are interleaved. In particular, this plays a role when planning for collaborative tasks of agents.
Goal of the project
The main target of this project is to combine and extend logic based approaches on planning and monitoring in a common framework based on answer set programming, which is a growing field in declarative logic programming. Fundamental research in the areas of planning, diagnosis and belief revision has shown promising and competitive results by use of logic programming for elementary tasks and problem solving in the respective fields separately. However, all these fields are important for a reactive agent environment. Integrating respective methods from these fields is essential for successful applications of planning in real world environments.
To this end, we can take advantage of the knowledge and experience that we have gained in previous projects, including the FWF projects P11580-MAT, P14781-INF and P13871-INF. We intend to use the DLV system and the planning system DLVK based on DLV, that have been developed in the quoted projects.
Tools developed
During the course of the project, several tools have been developed.- KDiagnose -- computes diagnosis of a plan execution discrepancy.
- KMonitor -- uses KDiagnose to monitor a plan execution according to some monitoring plan.
- RevPlan -- computing reverse plans from a reverse plan library for undoing the effects of action sequences.
- AD-Query -- gives answer to various consistency checks about an action description, helping the user find mistakes in it.
Publications
- T. Eiter, E. Erdem, W. Faber "Undoing the Effects of Action Sequences". Journal of Applied Logic, 36 pp., 2007. In press. (... ScienceDirect)
- T. Eiter, E. Erdem, W. Faber, and J. Senko "A Logic-Based Approach to Finding Explanations for Discrepencies in Optimistic Plan Execution". Fundamenta Informaticae, 79(1-2):25-69, 2007. (... Ios Press)
- T. Eiter, E. Erdem, M. Fink, and J. Senko
"Comparing action descriptions based on semantic preferences".
Annals of Mathematics and Artificial Intelligence, 50(3-4):273-304, 2007.
(... ACM) - T. Eiter, E. Erdem, W. Faber "On Reversing Actions: Algorithms and Complexity". In M. Veloso, editor, Proceedings 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pages 336-341, 2007. (... .pdf)
- D. Van Nieuwenborgh, T. Eiter, and D. Vermeir "Conditional Planning with External Functions". In C. Baral, G. Brewka, and J. Schlipf, editors, Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2007), number 4483 in Lecture Notes in Computer Science, pages 214-227. Springer, 2007. (... .pdf)
- T. Eiter, E. Erdem, M. Fink, and J. Senko "Comparing Action Descriptions Based on Semantic Preferences". Technical report INFSYS RR-1843-06-06, July 2006. Also appeared in M. Fisher et al., editors, Proceedings 8th European Conference on Logics in Artificial Intelligence (JELIA 2006), pages 124-137, 2006. (... .pdf)
- T. Eiter, M. Fink, and J. Senko "A Tool for Answering Queries on Action Descriptions". In M. Fisher et al., editors, Proceedings 8th European Conference on Logics in Artificial Intelligence (JELIA 2006), pages 473-476, 2006. (... .pdf)
- T. Eiter, E. Erdem, M. Fink, and J. Senko "Resolving conflicts in action descriptions". In G. Brewka and S. Coradeschi and A. Perini and P. Traverso, editors, Proceedings of the 17th Eureopean Conference on Artificial Intelligence (ECAI'2006), pages 367-371, 2006. (... .pdf)
- T. Eiter, E. Erdem, M. Fink, and J. Senko "Comparing action descriptions based on semantic preferences". In U. Junker and W. Kießling, editors, Informal Proceedings Multidisciplinary Workshop on Advances in Preference Handling, ECAI 2006, pages 15--22, 2006. Preliminary version.
- T. Eiter, E. Erdem, M. Fink, and J. Senko "Resolving conflicts in action descriptions". In J. Dix and A. Hunter, editors, Proceedings 11th International Workshop on Nonmonotonic Reasoning (NMR-2006), Reasoning About Actions and Change Track, pages 353-360, May 2006. Preliminary version.
- T. Eiter, W. Faber, G. Pfeifer, and A. Polleres "Declarative Planning and Knowledge Representation in an Action Language". In I. Vlahavas and D. Vrakas, editors, Intelligent Techniques for Planning, chapter 1, pages 1-34. Idea Group, Inc., 2005. (... IGI Global)
- T. Eiter, M. Fink, and J. Senko "KMonitor - A Tool for Monitoring Plan Execution in Action Theories". In Chitta Baral and Gianluigi Greco and Nicola Leone and Giorgio Terracina, editors, Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2005), pages 416-421, 2005. (... .pdf)
- T. Eiter, E. Erdem, M. Fink and J. Senko "Updating action domain descriptions". In Leslie Pack Kaelbling and Alessandro Saffiotti, editors, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI'05), pages 418-423, 2005. (... .pdf)
- C. Baral, T. Eiter, and J. Zhao "Using SAT and LP to Design Polynomial-Time Algorithms for Planning in Non-deterministic Domains". In Proceedings 20th National Conference on Artificial Intelligence (AAAI 2005), pages 578-583, 2005.
- T. Eiter, E. Erdem, W. Faber "Undoing the Effects of Action Sequences". Technical report INFSYS RR-1843-04-05, December 2004. (... .ps.gz)
- T. Eiter, E. Erdem, W. Faber "Plan Reversals for Recovery in Execution Monitoring". In J. P. Delgrande and T. Schaub, editors, Proceedings 10th Internation Workshop on Nonmonotonic Reasoning (NMR 2004), Action and Causality Track, pages 147-154, June 2004. (... .pdf)
- C. Baral and T. Eiter "Polynomial time algorithm for constructing k-maintainable policies". In S. Zilberstein, J. Koehler, and S. Koenig, editors, Proceedings 14th International Conference on Automated Planning and Scheduling (ICAPS 2004), pages 111-121, 2004. Reprinted in Proc. KR 2004, pp. 720-730.
- C. Baral, T. Eiter, M. Bjäreland, and M. Nakamura "Maintenance Goals of Agents in a Dynamic Environment: Formulation and Policy Construction". Technical Report INFSYS RR-1843-04-04, Institut für Informationssysteme, Technische Universität Wien, A-1040 Vienna, Austria, Oct. 2004. Accepted for publication in Artificial Intelligence. (... .pdf)
- T. Eiter, E. Erdem, W. Faber "Diagnosing Plan Execution Discrepancies in a Logic-Based Action Framework". Technical report INFSYS RR-1843-04-03, August 2004. (... .ps.gz)
- T. Eiter, E. Erdem, W. Faber "Report on State of the Art in Logic-Based Execution Monitoring". Technical Report FWF P-16536-N04-D1, Februar 2004. (... .pdf)