On Reversing Actions: Algorithms and Complexity

Thomas Eiter, Esra Erdem, Wolfgang FaberIJCAI 2007 · OpenReview

Abstract

Reversing actions is the following problem: After executing a sequence of actions, which sequence of actions brings the agent back to the state just before this execution (an action reversal). Notably, this problem is different from a vanilla planning problem since the state we have to get back to is in general unknown. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. It has applications related to plan execution and monitoring in nondeterministic domains, such as recovering from a failed execution by partially undoing the plan, dynamically switching from one executed plan to another, or restarting plans. We formalize action reversal in a logic-based action framework and characterize its computational complexity. Since unsurprisingly, the problem is intractable in general, we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) on-line computation of action reversals. Our results for the generic framework can be easily applied for expressive action languages such as C+ or κ.

Introduction

In autonomous agent research, the ability to "undo" actions is a critical component of robust plan execution. Whether recovering from a non-deterministic failure or pivoting to a new strategy based on updated information, agents frequently need to backtrack. Traditional planning typically focuses on reaching a known goal state from a known current state. However, "action reversal" presents a unique challenge: returning to the specific state that existed prior to a sequence of actions, often without a complete record of what that state was.

This problem is fundamentally distinct from standard planning because the target state is effectively a "moving target." A successful reverse plan must be guaranteed to work regardless of the initial state's specific configuration, provided the original actions were executable. This capability has significant implications for robotics, database management, and dynamic plan monitoring.

Formalizing Action Reversal

The authors utilize a logic-based, transition-based framework to represent actions and fluents. Within this framework, they define several core concepts:

  • Reverse Action: A single action $A'$ that perfectly restores the state prior to action $A$.
  • Reverse Plan: A sequence of actions $R$ that undoes a sequence of actions $AS$.
  • Conditional Reversals: Reversal plans that are contingent upon specific conditions ($ϕ$ and $ψ$) holding true in the current or target states.

A key insight is the identification of involutory actions, such as a light switch toggle, where an action serves as its own reverse.

Computational Complexity

The paper provides a rigorous characterization of the problem's complexity, demonstrating that finding "undo" sequences is generally intractable. The difficulty scales based on the length of the reversal sequence ($|R|$) and the specific task (recognition vs. search).

Table 1: Computational complexities of recognizing (P1) and finding (P2, P3) reverse plans.

As illustrated in Table 1, recognizing if a given plan is a reversal (P1) is coNP-complete for single actions and rises to $\Pi^p_2$ for longer sequences. Finding a reverse plan (P2, P3) is even more demanding, reaching $\Sigma^p_3$-completeness. This high level of complexity explains why naive search methods are unsuitable for real-time agent responses.

Knowledge Compilation for Efficient Reversal

To circumvent these complexity hurdles, the authors propose a Knowledge Compilation approach. The strategy involves shifting the heavy computational burden to an offline phase where a "Reverse Plan Library" is constructed. This library consists of pre-verified "Reverse Plan Items" (RPIs).

At runtime, the agent uses a REVERSE algorithm to assemble these RPIs into a complete reversal sequence. This process can be achieved in $O(|AS| \cdot |L|)$ time—linear relative to the original plan length and the library size—provided the library is sufficiently comprehensive and percepts are simple. This allows for efficient, real-time "undo" capabilities despite the underlying problem's theoretical hardness.

Conclusion and Future Work

While the library-based approach offers a path to efficiency, it is limited by the library's coverage. If the offline phase fails to include the necessary building blocks for a specific sequence, the agent will be unable to find a reversal. Furthermore, generating the library itself remains a $\Sigma^p_3$-hard task.

Future research directions include the automatic generation of these libraries and extending the framework to support more expressive action languages that incorporate complex non-deterministic effects. Standard AI domains like the blocks world and logistics serve as ongoing benchmarks for these developments.

Summary updated

Abstract

Reversing actions is the following problem: After executing a sequence of actions, which sequence of actions brings the agent back to the state just before this execution (an action reversal). Notably, this problem is different from a vanilla planning problem since the state we have to get back to is in general unknown. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. It has applications related to plan execution and monitoring in nondeterministic domains, such as recovering from a failed execution by partially undoing the plan, dynamically switching from one executed plan to another, or restarting plans. We formalize action reversal in a logic-based action framework and characterize its computational complexity. Since unsurprisingly, the problem is intractable in general, we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) on-line computation of action reversals. Our results for the generic framework can be easily applied for expressive action languages such as C+ or κ.
BibTeX
@inproceedings{eiter2007reversing,
  author = {Thomas Eiter and Esra Erdem and Wolfgang Faber},
  title = {{On Reversing Actions: Algorithms and Complexity}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=rJZlCEzOWS},
}
Figure