On reversing actions: algorithms and complexity
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.
Repository Staff Only: item control page