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. (Request a copy)


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
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Esra Erdem
Date Deposited: 24 Jun 2007 03:00
Last Modified: 26 Apr 2022 08:33
URI: https://research.sabanciuniv.edu/id/eprint/1249

Actions (login required)

View Item
View Item