Practical undoability checking via contingent planning

Jeanette Daum, Álvaro Torralba, Jörg Hoffmann, Patrik Haslum, Ingo Weber

Research output: Contribution to journalConference article in JournalResearchpeer-review

14 Citations (Scopus)

Abstract

We consider a general concept of undoability, asking whether a given action can always be undone, no matter which state it is applied to. This generalizes previous concepts of invertibility, and is relevant for search as well as applications. Naïve undoability checking requires to enumerate all states an action is applicable to. Extending and operationalizing prior work in this direction, we introduce a compilation into contingent planning, replacing such enumeration by standard techniques handling large belief states. We furthermore introduce compilations for checking whether one can always get back to an at-least-as-good state, as well as for determining partial undoability, i. e., undoability on a subset of states an action is applicable to. Our experiments on IPC benchmarks and in a cloud management application show that contingent planners are often effective at solving this kind of problem, hence providing a practical means for undoability checking.

Original languageEnglish
JournalProceedings International Conference on Automated Planning and Scheduling, ICAPS
Volume2016-January
Pages (from-to)106-114
Number of pages9
ISSN2334-0835
Publication statusPublished - 2016
Externally publishedYes
Event26th International Conference on Automated Planning and Scheduling, ICAPS 2016 - London, United Kingdom
Duration: 12 Jun 201617 Jun 2016

Conference

Conference26th International Conference on Automated Planning and Scheduling, ICAPS 2016
Country/TerritoryUnited Kingdom
CityLondon
Period12/06/201617/06/2016

Keywords

  • Planning and scheduling

Fingerprint

Dive into the research topics of 'Practical undoability checking via contingent planning'. Together they form a unique fingerprint.

Cite this