@techreport{ EitErdFab04,
  title = {Undoing the effects of action sequences}
}
,
  ee = {http://www.kr.tuwien.ac.at/research/reports/rr0405.ps.gz}
}
,
  abstract = {When an agent has executed a single action or a sequence of actions, it may sometimes be desirable that the effects of this execution are undone and the agent gets back to the previous state. A prototypical scenario for this is in the context of plan execution in a nondeterministic environment. Upon detecting that after some steps an unintended state has been reached, backtracking by taking appropriate undo actions can be useful for error recovery. In this paper, we thus consider the problem of undoing the effects of an action sequence by means of a reverse plan, in a general logic-based action representation framework that can accommodate nondeterminism and concurrency. Intuitively, by executing a reverse plan for an action sequence ASat the state Sreached after AS, she can always reach the state Sshe was at before executing AS. We formally define the notion of a reverse plan in terms of a logical specification and determine the computational complexity of the major reasoning tasks on it, namely the existence and recognition problem. Guided by these results, we then present algorithms for constructing reverse plans. Since this is intractable in general, we develop a knowledge compilation approach in which a reverse plan library is built offline by finding reverse plans for action sequences, and then a reverse plan for a given action sequence is efficiently constructed online using this library. For the former part, we describe methods based on conformant planning; for the latter, we present a polynomial time algorithm.}
}
,
  author = {Thomas Eiter and Esra Erdem and Wolfgang Faber}
}
,
  number = {INFSYS RR-1843-04-05}
}
,
  year = {2004}
}
,
  institution = {Vienna University of Technology}
}