A Logic-Based Approach to Finding Explanations for Discrepancies in Optimistic Plan Execution

• Autorzy: Eiter T. , Erdem E. , Faber W. , Senko J.
• Języki publikacji: EN

Abstrakty

EN

Consider an agent executing a plan with nondeterministic actions, in a dynamic environment, which might fail. Suppose that she is given a description of this action domain, including specifications of effects of actions, and a set of trajectories for the execution of this plan, where each trajectory specifies a possible execution of the plan in this domain. After executing some part of the plan, suppose that she obtains information about the current state of the world, and notices that she is not at a correct state relative to the given trajectories. How can she find an explanation (a point of failure) for such a discrepancy? An answer to this question can be useful for different purposes. In the context of execution monitoring, points of failure can determine some checkpoints that specify when to check for discrepancies, and they can sometimes be used for recovering from discrepancies that cause plan failures. At the modeling level, points of failure may provide useful insight into the action domain for a better understanding of the domain, or reveal errors in the formalization of the domain. We study the question above in a general logic-based knowledge representation framework, which can accommodate nondeterminism and concurrency. In this framework, we define a discrepancy and an explanation for it, and analyze the computational complexity of detecting discrepancies and finding explanations for them. We introduce a method for computing explanations, and report about a realization of this method using DLV^K, which is a logic-programming based system for reasoning about actions and change.

Słowa kluczowe

EN

knowledge representation; reasoning about actions; logic-based planning; explanations; execution monitoring; computational complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 1-2
• Strony: 25--69
• Opis fizyczny: bibliogr. 48 poz., wykr.

Twórcy

autor

Eiter T.

autor

Erdem E.

autor

Faber W.

autor

Senko J.

• Institut für Informationssysteme, Technische Universität Wien, Favoritenstr. 9-11, A-1040 Wien, Austria,

Bibliografia

• [1] Ambrose-Ingerson, J. A., Steel, S.: Integrating planning, execution and monitoring, Proc. of the 7th National Conference on Artificial Intelligence (AAAI-88), St. Paul, MN, August 21-26, 1988.
• [2] Balduccini, M., Gelfond, M.: Diagnostic reasoning with A-Prolog, Journal of Theory and Practice of Logic Programming, 3(4-5), 2003, 425-461.
• [3] Baral, C., Kreinovich, V., Trejo, R.: Computational complexity of planning and approximate planning in the presence of incompleteness, Artificial Intelligence, 122(1-2), 2000, 241-267.
• [4] Baral, C., McIlraith, S. A., Son, T. C.: Formulating diagnostic problem solving using an action language with narratives and sensing, Proceedings Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR-00), Breckenridge, Colorado, USA (A. Cohn, F. Giunchiglia, B. Selman, Eds.), Morgan Kaufmann, 2000.
• [5] Baral, C., Tran, N., Tuan, L.: Reasoning about actions in a probabilistic setting, Proc. of the Eighteenth National Conference on Artificial Intelligence (AAAI-02), July 28 - August 1, 2002, Edmonton, Alberta, Canada, 2002.
• [6] Bastié, C., Régnier, O.: SPEEDY: Monitoring the execution in dynamic environments, Proc. Workshop on Reasoning about Actions and Planning in Complex Environments, International Conference on Formal and Applied Practical Reasoning (FAPR'96), Bonn, Germany, 1996, Available as Technical Report AIDA-9611, Fachgebiet Intellektik, Technische Hochschule Darmstadt, Germany.
• [7] Beetz, M., McDermott, D.: Improving robot plans during their execution, Proc. of the Second International Conference on Artificial Intelligence Planning Systems (AIPS-94), June 13-15, 1994, University of Chicago, 1994.
• [8] Chen, Z.-Z., Toda, S.: The complexity of selecting maximal solutions, Information and Computation, 119, 1995, 231-239.
• [9] Cimatti, A., Pistore, M., Roveri, M., Traverso, P.: Weak, strong, and strong cyclic planning via symbolic model checking., Artificial Intelligence, 147(1-2), 2003, 35-84.
• [10] De Giacomo, G., Reiter, R., Soutchanski, M.: Execution monitoring of high-level robot programs, Proceedings 6th International Conference on Principles of Knowledge Representation and Reasoning (KR-98), Trento, Italy, 1998.
• [11] Eiter, T., Erdem, E., Faber,W.: Diagnosing plan execution discrepancies in a logic-based action framework, Technical Report INFSYS RR-1843-04-03, Vienna University of Technology, 2004.
• [12] Eiter, T., Erdem, E., Faber, W.: Plan reversals for recovery in execution monitoring, Proceedings 10th International Workshop on Nonmonotonic Reasoning (NMR-2004), Action and Causality Track (J. P. Delgrande, T. Schaub, Eds.), 2004.
• [13] Eiter, T., Erdem, E., Faber, W.: Undoing the Effects of Action Sequences, Technical Report INFSYS RR-1843-04-05, Institut für Informationssysteme, Technische Universität Wien, A-1040 Vienna, Austria, December 2004.
• [14] Eiter, T., Erdem, E., Faber, W.: On reversing actions: Algorithms and complexity, Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07), Hyderabad, India, January 6-12, AAAI Press/IJCAI, 2007,
• [15] Eiter, T., Faber, W., Leone, N., Pfeifer, G., Polleres, A.: A logic programming approach to knowledge-state planning, II: The DLVK system, Artificial Intelligence, 144(1-2), 2002, 157-211.
• [16] Eiter, T., Faber, W., Leone, N., Pfeifer, G., Polleres, A.: A logic programming approach to knowledge-state planning: Semantics and complexity, ACM Transactions on Computational Logic, 5(2), 2004, 206-263.
• [17] Eiter, T., Fink, M., Senkö, J.: KMonitor - A tool for monitoring plan execution in action theories, Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2005) (C. Baral, G. Greco, N. L. nad Giorgio Terracina, Eds.), number 3662 in LNCS, Springer, 2005.
• [18] Eiter, T., Lukasiewicz, T.: Probabilistic reasoning about actions in nonmonotonic causal theories, Proceedings Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI-2003), August 7-10, 2003, Acapulco, Mexico (C. Meek, U. Kjærulff, Eds.), Morgan Kaufmann Publishers, San Francisco, CA, 2003.
• [19] Ferraris, P., Giunchiglia, E.: Planning as satisfiability in nondeterministic domains, Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI'00), July 30 - August 3, 2000, Austin, Texas USA, AAAI Press / The MIT Press, 2000.
• [20] Fichtner, M., Großmann, A., Thielscher, M.: Intelligent execution monitoring in dynamic environments, Fundamenta Informaticae, 57(2-4), 2003, 371-392.
• [21] Fikes, R. E., Hart, P. E., Nilsson, N. J.: Learning and executing generalized robot plans, Artificial Intelligence, 3(4), 1972, 251-288.
• [22] Gelfond, M., Lifschitz, V.: Action languages, Electronic Transactions on AI, 3, 1998, 195-210.
• [23] Giunchiglia, E.: Planning as satisfiability with expressive action languages: Concurrency, constraints and nondeterminism, Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2000), April 12-15, Breckenridge, Colorado, USA (A. G. Cohn, F. Giunchiglia, B. Selman, Eds.), Morgan Kaufmann, 2000.
• [24] Giunchiglia, E., Lee, J., Lifschitz, V., McCain, N., Turner, H.: Nonmonotonic causal theories, Artificial Intelligence, 153(1-2), 2004, 49-104.
• [25] Haigh, K. Z., Veloso, M.: Interleaving planning and robot execution for asynchronous user requests, Autonomous Robots, 5(1), 1998, 79-95.
• [26] Hayashi, H., Cho, K., Ohsuga, A.: Mobile agents and logic programming, Proceedings of the Sixth International Conference on Mobile Agents (MA 2002), Barcelona, Spain, October 22-25, 2002 (N. Suri, Ed.), 2535, Springer, 2002.
• [27] Hayashi, H., Cho, K., Ohsuga, A.: A new HTN planning framework for agents in dynamic environments, Computational Logic in Multi-Agent Systems, 4th InternationalWorkshop (CLIMA IV), Fort Lauderdale, FL, USA, January 6-7, 2004, Revised Selected and Invited Papers (J. Dix, J. A. Leite, Eds.), 3259, Springer, 2004.
• [28] Kautz, H., Selman, B.: Planning as satisfiability, Proc. 10th European Conference on Artificial Intelligence (ECAI-92), Vienna, Austria, August 3-7, 1992.
• [29] Koenig, S., Furcy, D., Bauer, C.: Heuristic search-based replanning, Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS), 2002.
• [30] Kushmerick, N., Hanks, S., Weld, D. S.: An algorithm for probabilistic planning, Artificial Intelligence, 76(1-2), 1995, 239-286.
• [31] Levesque, H. J., Reiter, R., Lesperance, Y., Lin, F., Scherl, R. B.: GOLOG: A logic programming language for dynamic domains, Journal of Logic Programming, 31(1-3), 1997, 59-83.
• [32] Littman,M. L.: Probabilistic propositional planning: Representations and complexity, Proc. AAAI-97, 1997.
• [33] McCain, N., Turner, H.: Satisfiability planning with causal theories, Proceedings Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR-98) (A. G. Cohn, L. Schubert, S. C. Shapiro, Eds.), Morgan Kaufmann Publishers, 1998.
• [34] McCarthy, J.: Elaboration tolerance, 1999, In progress.
• [35] Nebel, B., Koehler, J.: Plan reuse versus plan generation: A theoretical and empirical analysis, Artificial Intelligence, 76(1-2), 1995, 427-454.
• [36] Onaindia, E., Sapena, O., Sebastia, L., Marzal, E.: SimPlanner: An execution-monitoring system for replanning in dynamic worlds, Proceedings 10th Portuguese Conference on Artificial Intelligence (EPIA-2001), 2001.
• [37] Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994.
• [38] Reiter, R.: Knowledge in action: Logical foundations for specifying and implementing dynamical systems, MIT Press, 2001.
• [39] Rintanen, J.: Constructing conditional plans by a theorem-prover, Journal of Artificial Intelligence Research, 10, 1999, 323-352.
• [40] Rosenbloom, P., Laird, J., Newell, A.: The SOAR papers: Readings on integrated intelligence, MIT Press, 1993.
• [41] Son, T. C., Pontelli, E.: Planning with preferences using logic programming, Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2004) (I. Niemelä, V. Lifschitz, Eds.), number 2923 in LNCS, Springer, 2004.
• [42] Soutchanski,M.: Execution monitoring of high-level temporal programs, Proc. of IJCAI Workshop on Robot Action Planning, 1999.
• [43] Soutchanski, M.: High-level robot programming and program execution, Proc. of ICAPS Workshop on Plan Execution, 2003.
• [44] Thielscher, M.: The concurrent, continuous Fluent Calculus, Studia Logica, 67(3), 2001, 315-331.
• [45] Thielscher, M.: FLUX: A logic programming method for reasoning agents, Theory and Practice of Logic Programming, 5(4-5), 2005, 533-565.
• [46] Turner, H.: Polynomial-length planning spans the polynomial hierarchy, Proc. of Eighth European Conf. On Logics in Artificial Intelligence (JELIA'02), 2002.
• [47] van der Krogt, R., de Weerdt, M.: Plan repair as an extension of planning, Proc. Fifteenth International Conference on Planning and Scheduling (ICAPS-05), 2005.
• [48] Wilkins, D.: Practical planning: Extending the classical AI planning paradigm, Morgan Kaufmann Publishers, 1988.