Proceedings

On Reversing Actions: Algorithms and Complexity

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 336-340.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

Reversing actions is the following problem: After executing a sequence of actions, which sequence of actions brings the agent back to the state just before this execution (an action reversal). Notably, this problem is different from a vanilla planning problem since the state we have to get back to is in general unknown. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. It has applications related to plan execution and monitoring in nondeterministic domains, such as recovering from a failed execution by partially undoing the plan, dynamically switching from one executed plan to another, or restarting plans. We formalize action reversal in a logic-based action1 framework and characterize its computational complexity. Since unsurprisingly, the problem is intractable in general, we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) online computation of action reversals. Our results for the generic framework can be easily applied for expressive action languages such as C+ or K.

  1. [Agrawal et al., 1991] H. Agrawal, R. A. DeMillo, and E. H. Spafford. An execution backtracking approach to program debugging. IEEE Software, 8(3):21-26, 1991.
  2. [Baral et al., 2000] C. Baral, V. Kreinovich, and R. Trejo. Computational complexity of planning and approximate planning in the presence of incompleteness. Artificial In- telligence, 122(1-2):241-267, 2000.
  3. [Cadoli and Donini, 1997] M. Cadoli and F. M. Donini. A Survey on Knowledge Compilation. AI Communications, 10(3-4):137-150, 1997.
  4. [De Giacomo et al., 1998] G. De Giacomo, R. Reiter, and M. Soutchanski. Execution monitoring of high-level robot programs. In Proc. KR, pp. 453-465, 1998.
  5. [Eiter et al., 2006] T. Eiter, E. Erdem, and W. Faber. Undo- ing the effects of action sequences. Tech. Report INFSYS RR-1843-04-05, TU Wien, A-1040 Vienna, Austria, 2006.
  6. [Eiter et al., 2004] T. Eiter, W. Faber, N. Leone, G. Pfeifer, and A. Polleres. A logic programming approach to knowl- edge-state planning: Semantics and complexity. TOCL, 5(2):206-263, 2004.
  7. [Fichtner et al., 2003] M. Fichtner, A. Großmann, and M. Thielscher. Intelligent execution monitoring in dy- namic environments. Fund. Inform., 57(2-4), 2003.
  8. [Gelfond and Lifschitz, 1998] M. Gelfond and V. Lifschitz. Action Languages. ETAI, 2(3-4):193-210, 1998.
  9. [Giunchiglia et al., 2004] E. Giunchiglia, J. Lee, V. Lifs- chitz, N. McCain, and H. Turner. Nonmonotonic Causal Theories. Artificial Intelligence, 153(1-2):49-104, 2004.
  10. [Hayashi et al., 2002] H. Hayashi, K. Cho, and A. Ohsuga. Mobile agents and logic programming. In Proc. MA, pp. 32-46, 2002.
  11. [Hayashi et al., 2004] H. Hayashi, K. Cho, and A. Ohsuga. A new HTN planning framework for agents in dynamic environments. In Proc. CLIMA, pp. 108-133, 2004.
  12. [Liberatore, 1997] P. Liberatore. The complexity of the lan- guage A. Electron. Trans. Artif. Intell., 1:13-38, 1997.
  13. [Papadimitriou, 1994] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  14. [Rintanen, 1999] J. Rintanen. Constructing Conditional Plans by a Theorem-Prover. JAIR, 10:323-352, 1999.
  15. [Son and Baral, 2001] T.C. Son and C. Baral. Formalizing Sensing Actions -A Transition Function Based Approach. Artificial Intelligence, 125(1-2):19-91, 2001.
  16. [Soutchanski, 1999] M. Soutchanski. Execution monitoring of high-level temporal programs. In Proc. IJCAI Workshop on Robot Action Planning, 1999.
  17. [Soutchanski, 2003] M. Soutchanski. High-level robot pro- gramming and program execution. In Proc. ICAPS Work- shop on Plan Execution, 2003.
  18. [Turner, 2002] H. Turner. Polynomial-length planning spans the polynomial hierarchy. In Proc. JELIA, pp. 111-124.
  19. [Zelkowitz, 1973] M. V. Zelkowitz. Reversible execution. Communications of ACM, 16(9):566, 1973.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards