Endomorphisms of Classical Planning Tasks

Rostislav Horcík, Daniel FiserAAAI 2021 · DOI

Introduction

In classical planning, the objective is to find a sequence of actions that leads from an initial state to a goal. However, many planning problems are cluttered with redundant operators—actions that, while reachable, are never part of an optimal plan because a more efficient or equivalent alternative always exists.

Existing pruning techniques, such as $h^m$ reachability analysis, often fail to identify these sub-optimal but reachable actions. Similarly, traditional symmetry breaking requires perfect, reversible (bijective) matches, missing "near-symmetries" where one action might simply dominate another. This paper introduces a novel method for identifying and removing such redundancies using endomorphisms—structure-preserving self-maps borrowed from model theory.

Methodology: LTS Endomorphisms

The authors propose using Labeled Transition System (LTS) Endomorphisms. An LTS represents states and the actions (labels) that transition between them. An endomorphism is a function that maps the LTS back onto itself while preserving its structure: if a transition exists between two states in the original system, a corresponding transition must exist between their mapped versions in the image, with the cost of the new action being less than or equal to the original.

An endomorphism mapping a larger transition system (left) to a smaller, equivalent "core" (right).

Factored and FDR Endomorphisms

To combat the "state explosion" problem, where the full state space is too large to compute directly, the researchers introduce two concise approaches:

  1. Factored LTS Endomorphisms: Endomorphisms are computed on "factors"—smaller, localized pieces of the transition system.
  2. FDR (Finite Domain Representation) Endomorphisms: Mappings are defined directly on the variables and operators of the planning task, offering a faster but slightly less powerful pruning method.
Factored transition systems $\Theta_{V_1}$ and $\Theta_{V_2}$ used to identify redundancies without materializing the full state space.

CSP Formulation

The search for these mappings is translated into a Constraint Satisfaction Problem (CSP). By using a standard solver (IBM ILOG CP Optimizer), the system can find the smallest possible set of operators, effectively reducing the planning task to its mathematical "core."

Experimental Evaluation

The method was evaluated using the standard benchmark set from the International Planning Competitions (1998–2018), covering 65 different planning domains. The researchers compared their endomorphism-based pruning against standard $h^2$ reachability analysis.

Key Results

  • Redundancy Detection: The factored LTS approach found non-trivial redundant operators in 20 out of 65 domains, even after tasks had already been pruned by industry-standard $h^2$ heuristics.
  • Performance Boost: Removing these operators significantly increased the number of tasks solved by state-of-the-art optimal planners (e.g., LM-Cut). In the blocks domain, the number of solved tasks jumped significantly across multiple configurations.
  • Search Reduction: Data indicates that for many tasks, the number of states expanded during the search was reduced by orders of magnitude after pruning.
  • Exposing Hidden Symmetries: Pruning redundant operators often "uncovers" symmetries that were previously hidden by clutter, allowing subsequent symmetry-breaking algorithms to perform even better.

Discussion and Future Work

Endomorphisms provide a solid theoretical bridge between model theory and existing planning heuristics, essentially serving as a functional version of "goal-respecting cost-simulations." Unlike symmetries, endomorphisms do not have to be reversible, allowing the system to recognize when one state is simply "better than or equal to" another.

While effective, the computational overhead of solving the CSP can be high in large domains. Future work will explore more specialized algorithms for finding endomorphisms and investigate loosening constraints for satisficing planning, which could allow for even more aggressive pruning.

Summary updated

BibTeX
@inproceedings{horcik2021endomorphisms,
  author = {Rostislav Horcík and Daniel Fiser},
  title = {{Endomorphisms of Classical Planning Tasks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17406},
}
Figure