Undoing the effects of action sequences. Eiter, T., Erdem, E., & Faber, W. Technical Report INFSYS RR-1843-04-05, Vienna University of Technology, 2004. ![Undoing the effects of action sequences [link]](https://bibbase.org/img/filetypes/link.svg "link")
Link abstract bibtex 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.
@techreport{EitErdFab04,
author = {Thomas Eiter and
Esra Erdem and
Wolfgang Faber},
title = {Undoing the effects of action sequences},
institution = {Vienna University of Technology},
year = {2004},
number = {INFSYS RR-1843-04-05},
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.}
}
Downloads: 0
{"_id":{"_str":"53424e050e946d920a000679"},"__v":11,"authorIDs":["5456f0758b01c81930000081","5457257c2abc8e9f370000e3","548a76d12e5d16b0750003dc","5df0b7a08367c8de010000ce","5df87bbedb7d9ddf01000044","5e4957a916841dde01000031","u493trvfaXuB4g9PZ"],"author_short":["Eiter, T.","Erdem, E.","Faber, W."],"bibbaseid":"eiter-erdem-faber-undoingtheeffectsofactionsequences-2004","bibdata":{"bibtype":"techreport","type":"techreport","author":[{"firstnames":["Thomas"],"propositions":[],"lastnames":["Eiter"],"suffixes":[]},{"firstnames":["Esra"],"propositions":[],"lastnames":["Erdem"],"suffixes":[]},{"firstnames":["Wolfgang"],"propositions":[],"lastnames":["Faber"],"suffixes":[]}],"title":"Undoing the effects of action sequences","institution":"Vienna University of Technology","year":"2004","number":"INFSYS RR-1843-04-05","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.","bibtex":"@techreport{EitErdFab04,\nauthor = {Thomas Eiter and\n\t\t Esra Erdem and\n\t\t Wolfgang Faber},\ntitle = {Undoing the effects of action sequences},\ninstitution = {Vienna University of Technology},\nyear = {2004},\nnumber = {INFSYS RR-1843-04-05},\nee = {http://www.kr.tuwien.ac.at/research/reports/rr0405.ps.gz},\nabstract = {When an agent has executed a single action or a sequence of actions, it may\nsometimes be desirable that the effects of this execution are undone and the agent gets back\nto the previous state. A prototypical scenario for this is in the context of plan execution in\na nondeterministic environment. Upon detecting that after some steps an unintended state\nhas been reached, backtracking by taking appropriate undo actions can be useful for error\nrecovery. In this paper, we thus consider the problem of undoing the effects of an action\nsequence by means of a reverse plan, in a general logic-based action representation framework\nthat can accommodate nondeterminism and concurrency. Intuitively, by executing a\nreverse plan for an action sequence ASat the state Sreached after AS, she can always\nreach the state Sshe was at before executing AS. We formally define the notion of a reverse\nplan in terms of a logical specification and determine the computational complexity\nof the major reasoning tasks on it, namely the existence and recognition problem. Guided\nby these results, we then present algorithms for constructing reverse plans. Since this is\nintractable in general, we develop a knowledge compilation approach in which a reverse\nplan library is built offline by finding reverse plans for action sequences, and then a reverse\nplan for a given action sequence is efficiently constructed online using this library. For the\nformer part, we describe methods based on conformant planning; for the latter, we present\na polynomial time algorithm.}\n}\n\n","author_short":["Eiter, T.","Erdem, E.","Faber, W."],"key":"EitErdFab04","id":"EitErdFab04","bibbaseid":"eiter-erdem-faber-undoingtheeffectsofactionsequences-2004","role":"author","urls":{"Link":"http://www.kr.tuwien.ac.at/research/reports/rr0405.ps.gz"},"downloads":0,"html":""},"bibtype":"techreport","biburl":"http://193.255.135.175/papers/krrpublications.bib","downloads":0,"keywords":[],"search_terms":["undoing","effects","action","sequences","eiter","erdem","faber"],"title":"Undoing the effects of action sequences","year":2004,"dataSources":["WeBGfagwiP89ve7hM"]}