KR2021Proceedings of the 18th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning

Online event. November 3-12, 2021.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-99-7

Sponsored by
Published by

Copyright © 2021 International Joint Conferences on Artificial Intelligence Organization

Universal and Uniform Action Reversibility

  1. Lukáš Chrpa(Czech Technical University in Prague)
  2. Wolfgang Faber(University of Klagenfurt)
  3. Michael Morak(University of Klagenfurt)

Keywords

  1. Reasoning about actions and change, action languages

Abstract

The problem of action reversibility studies whether effects of a given action can be reversed (or undone) by a sequence of (other) actions. For example, actions whose effects can be reversed cannot lead to dead-ends. In the usual settings, the problem of action reversibility is PSPACE-complete, that is, as hard as deciding plan existence.

In this paper, we focus on subclasses of the action reversibility problem, universal and uniform action reversibility, where the former considers all states in which the action in question is applicable, while the latter requires a single reverting action sequence, independent of the considered states. Specifically, we study the relations between projection abstractions and the subclasses of the action reversibility problem and we show that universal uniform reversibility of a given action can be decided on projection consisting of only the variables present in the schema of the action in question.