Undoing the effects of action sequences

Eiter, Thomas and Erdem, Esra and Faber, Wolfgang (2007) Undoing the effects of action sequences. (Accepted/In Press)

WarningThere is a more recent version of this item available.

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B758H-4NRK4KC-2&_user=691258&_coverDate=05%2F16%2F2007&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000038658&_version=1&_urlVersion=0&_userid=691258&md5=d3cd0241aa9e3a78b577165bd98ec303


In this paper, we study the following basic problem: After having executed a sequence of actions, find a sequence of actions that brings the agent back to the state just before this execution. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. A prototypical scenario is in the context of plan execution in a nondeterministic environment: Upon detecting that after executing some steps of the plan, an unintended state has been reached, backtracking to an earlier state by taking appropriate undo actions can be useful for recovery. In this paper, we consider the problem of undoing the effects of an action sequence by means of a reverse plan. Intuitively, by executing a reverse plan for an action sequence AS at the state S' reached after AS, the agent can always reach the state S she was at just before executing AS, possibly subject to conditions on the current state and S. Notably, this problem is different from a vanilla planning problem, since the state we have to get back to is in general unknown. We study this problem in a general logic-based action representation framework that can accommodate nondeterminism and concurrency. We formally define the notion of a reverse plan and determine the computational complexity of the existence and the recognition of such a plan. Guided by these results, we then present algorithms for constructing reverse plans. Unsurprisingly, the problem is intractable in general, and 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 adapted for expressive action languages such as C+ or K.

Item Type:Article
ID Code:8564
Deposited By:Esra Erdem
Deposited On:04 Jun 2008 10:08
Last Modified:06 Nov 2008 20:46

Repository Staff Only: item control page