On reversing actions: algorithms and complexity

Warning The system is temporarily closed to updates for reporting purpose.

Eiter, Thomas and Erdem, Esra and Faber, Wolfgang (2007) On reversing actions: algorithms and complexity. In: The Twentieth International Joint Conference on Artificial Intelligence (IJCAI'07) , Hyderabad, India

Full text not available from this repository.

Official URL: http://www.ijcai.org/papers07/contents.php


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 action 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.

Item Type:Papers in Conference Proceedings
Additional Information:IJCAI-07 Proceedings; Twentieth International Joint Conference on Artificial Intelligence
Subjects:Q Science > QA Mathematics
ID Code:1249
Deposited By:Esra Erdem
Deposited On:24 Jun 2007 03:00
Last Modified:09 Jun 2008 13:11

Repository Staff Only: item control page