On the Reversibility of Actions in Planning

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00344948" target="_blank" >RIV/68407700:21230/20:00344948 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.24963/kr.2020/65" target="_blank" >https://doi.org/10.24963/kr.2020/65</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/kr.2020/65" target="_blank" >10.24963/kr.2020/65</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Reversibility of Actions in Planning

Popis výsledku v původním jazyce

Checking whether action effects can be undone is an important question for determining, for instance, whether a planning task has dead-ends. In this paper, we investigate the reversibility of actions, that is, when the effects of an action can be reverted by applying other actions, in order to return to the original state. We propose a broad notion of reversibility that generalizes previously defined versions and investigate interesting properties and relevant restrictions. In particular, we propose the concept of uniform reversibility that guarantees that an action can be reverted independently of the state in which the action was applied, using a so-called reverse plan. In addition, we perform an in-depth investigation of the computational complexity of deciding action reversibility. We show that reversibility checking with polynomial-length reverse plans is harder than polynomial-length planning and that, in case of unrestricted plan length, the PSPACE-hardness of planning is inherited. In order to deal with the high complexity of solving these tasks, we then propose several incomplete algorithms that may be used to compute reverse plans for a relevant subset of states.

Název v anglickém jazyce

On the Reversibility of Actions in Planning

Popis výsledku anglicky

Checking whether action effects can be undone is an important question for determining, for instance, whether a planning task has dead-ends. In this paper, we investigate the reversibility of actions, that is, when the effects of an action can be reverted by applying other actions, in order to return to the original state. We propose a broad notion of reversibility that generalizes previously defined versions and investigate interesting properties and relevant restrictions. In particular, we propose the concept of uniform reversibility that guarantees that an action can be reverted independently of the state in which the action was applied, using a so-called reverse plan. In addition, we perform an in-depth investigation of the computational complexity of deciding action reversibility. We show that reversibility checking with polynomial-length reverse plans is harder than polynomial-length planning and that, in case of unrestricted plan length, the PSPACE-hardness of planning is inherited. In order to deal with the high complexity of solving these tasks, we then propose several incomplete algorithms that may be used to compute reverse plans for a relevant subset of states.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning

ISBN

978-0-9992411-7-2

ISSN

2334-1033

e-ISSN

—

Počet stran výsledku

10

Strana od-do

652-661

Název nakladatele

International Joint Conferences on Artificial Intelligence Organization

Místo vydání

—

Místo konání akce

Rhodes

Datum konání akce

12. 9. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—