Deciding Unsolvability in Temporal Planning under Action Non-Self-Overlapping

Stefan Panjkovic, Andrea Micheli, Alessandro CimattiAAAI 2022 · DOI

Introduction

In the field of AI Planning, the primary objective is typically to find a sequence of actions that achieves a specific goal. However, in many industrial and real-world scenarios—such as resource-constrained scheduling or oversubscription problems—it is equally critical to determine when a goal is mathematically impossible to reach.

Traditional Temporal Planners (TP) are often "semi-decision" procedures. While they are effective at finding plans when they exist, they frequently diverge and run indefinitely when faced with unsolvable problems. This occurs because the search space, involving continuous time and overlapping actions, is theoretically infinite. This paper addresses this gap by introducing the first practical, sound, and complete decision procedures for Temporal Planning under the Action Non-Self-Overlapping (ANSO) assumption. In ANSO, two instances of the same specific action cannot execute simultaneously. This constraint, which aligns with most industrial use cases, makes the planning problem PSPACE-complete and decidable.

Methodology

The authors propose two distinct computational approaches to exploit the decidability of ANSO planning:

1. Symbolic Model Checking (nuXmv)

This approach translates the planning problem into a Timed Transition System (TTS). Actions are modeled using clocks to track duration, while a global clock manages timed events like deadlines. The planner utilizes the nuXmv model checker to verify an invariant: "Is it always true that the goal is NOT reached?" If the model checker finds a counter-example, it constitutes a valid plan. If the invariant is proven to hold, the problem is formally declared unsolvable.

2. Heuristic Search with DBMs (TAMER-CTP)

Unlike traditional planners that use Simple Temporal Networks (STNs), the forward-chaining planner TAMER-CTP utilizes Difference Bound Matrices (DBMs). DBMs provide a canonical representation of temporal regions, which is essential for proving that a search space has been fully explored.

Example of DBM state transitions and normalization in TAMER-CTP.

As shown in Figure 1, DBMs allow for "subsumption checking," enabling the planner to determine if a new state is already contained within a previously visited state. By applying "k-normalization" to keep the number of possible DBM states finite, the search algorithm can prune redundant branches and guarantee termination on unsolvable instances.

Experimental Evaluation

The proposed tools were evaluated against standard International Planning Competition (IPC) benchmarks and new, intentionally unsolvable industrial domains (MAJSP and PAINTER). These unsolvable versions included impossible battery requirements or synchronization constraints. The performance was compared against state-of-the-art planners like OPTIC and TPACK, as well as an optimized encoding for the timed automata tool UPPAAL.

Experimental results comparing various planners on solvable and unsolvable instances.

Key Results

As detailed in Figure 5, the proposed methods significantly outperform existing baselines in proving unsolvability:

  • Unsolvability Coverage: nuXmv solved 151 unsolvable instances, and TAMER-CTP solved 110. In contrast, the best existing planner, OPTIC, solved only 6 instances, primarily through simple heuristic pruning.
  • Solvable Performance: TAMER-CTP remains highly competitive on solvable benchmarks, solving 390 instances, nearly matching the 398 instances solved by the specialized TAMER-FTP planner.
  • Search Efficiency: The cactus plots in Figure 5 illustrate that while existing planners like TPACK and OPTIC solve many instances quickly, they fail to scale or terminate on harder unsolvable problems, whereas TAMER-CTP and nuXmv provide robust termination guarantees.

Discussion and Conclusion

The core "secret sauce" for proving unsolvability in this context is the transition from STNs to DBMs. While STNs are efficient for finding a single plan, DBMs allow for the state comparison necessary to confirm that the entire search space has been exhausted.

While the ANSO constraint is common in practice, it remains a limitation for highly parallel domains requiring self-overlapping actions. Future work will focus on scaling these methods to larger domains by optimizing clock management, potentially sharing clocks between actions that are mutually exclusive in time. This research marks a significant step toward making temporal planners reliable tools for both plan generation and formal impossibility proofs.

Summary updated

BibTeX
@inproceedings{panjkovic2022deciding,
  author = {Stefan Panjkovic and Andrea Micheli and Alessandro Cimatti},
  title = {{Deciding Unsolvability in Temporal Planning under Action Non-Self-Overlapping}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21225},
}
Figure