Classical Planning with Avoid Conditions

Marcel Steinmetz, Jörg Hoffmann, Alisa Kovtunova, Stefan BorgwardtAAAI 2022 · DOI

Introduction

In automated planning, the objective is typically to reach a goal state. However, many real-world scenarios require staying away from "bad" states—such as a robot avoiding a dangerous puddle or a delivery truck avoiding restricted road segments. These are known as "avoid conditions" ($\phi$), state formulas that must remain false throughout a plan's execution. While the PDDL3 language supports such temporal constraints, standard "compilation" methods—which bake these conditions into action preconditions—often suffer from a massive "grounding" overhead. This paper introduces specialized algorithmic techniques to handle avoid conditions directly within the search algorithm, demonstrating significant performance gains, especially in proving goal unreachability.

Methodology

The authors propose two primary techniques to predict when a state is "$\phi$-unsolvable" (meaning any path to the goal will eventually violate the avoid condition $\phi$):

  1. Avoid-Prediction via Traps: A "trap" is a set of states that, once entered, cannot be left and contains no goal states. The authors extend this to $\phi$-traps: sets of states where every path to a goal must pass through a state satisfying $\phi$. These traps are learned from search experience, allowing the planner to prune dead-end branches early.
  2. Cartesian Abstraction Refinement: Using Counter-Example Guided Abstraction Refinement (CEGAR), the authors simplify the state space into "blocks." They introduce a new refinement trigger: if an abstract path hits a state satisfying $\phi$, the abstraction is refined to better distinguish between safe and forbidden regions.

These methods are compared against three baseline compilations: Condition-based, LTL-based, and Axiom-based.

Experimental Setup

The methods were evaluated on two benchmark categories:

  • REDONE: Six standard planning domains (e.g., CaveDiving, Miconic, Trucks) with manually extracted implicit constraints turned into explicit avoid conditions.
  • ROAD: New benchmarks based on transportation maps (Driverlog, Rovers, TPP, Transport) with systematically generated avoid conditions for road segments.

Key Results and Insights

The experimental results highlight the limitations of standard compilation, which often requires converting formulas into Disjunctive Normal Form (DNF), leading to an exponential blow-up in task description size. In contrast, the proposed $\phi$-predictors offer superior performance.

Comprehensive results showing coverage and search reduction factors across satisficing, optimal, and unsolvability benchmarks.

As shown in the table above, the new techniques achieved significantly higher coverage than compilation methods. In domains like Miconic-REDONE and Transport-ROAD, the $\phi$-predictors reduced the number of states visited by factors of thousands or even millions. The techniques were particularly dominant in proving unsolvability; for instance, in the Transport-ROAD unsolvability benchmarks, the trap-learning method solved 64 instances compared to only 25-32 for the compilations.

Limitations and Future Work

Despite their success, these methods still rely on a DNF representation of the avoid condition $\phi$, which can be a bottleneck for extremely complex formulas. Additionally, in domains where avoid conditions do not create many new dead ends (like Fridge), the overhead of building traps or abstractions may not be justified. Future research could explore using Binary Decision Diagrams (BDDs) for more compact representation and extending these techniques to non-deterministic or probabilistic planning environments.

Summary updated

BibTeX
@inproceedings{steinmetz2022classical,
  author = {Marcel Steinmetz and Jörg Hoffmann and Alisa Kovtunova and Stefan Borgwardt},
  title = {{Classical Planning with Avoid Conditions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21232},
}
Figure