Efficient Temporal Planning Using Metastates

Amanda Jane Coles, Andrew Coles, J. Christopher BeckAAAI 2019 · DOI

Abstract

Temporal planning is computationally intensive due to the "state-space explosion" caused by the need to track all unique paths to a state to satisfy temporal constraints. We present a novel search framework based on metastates, which groups logically identical states and explores alternative paths lazily. This approach maintains completeness while significantly reducing the search space. Evaluation on IPC benchmarks shows that metastates increase problem coverage and reduce node expansions by orders of magnitude in temporally complex domains.

Introduction

In classical AI planning, state memoisation is a powerful tool: if two paths lead to the same logical state, one can be discarded. However, in temporal planning, the path taken determines the remaining time to meet deadlines. A state reached via a longer path might be a dead-end, whereas the same state reached via a shorter path could lead to a solution.

Figure 1: A simple planning graph where paths A-B-C and A-D-C lead to the same logical state C but with different cumulative durations (6 vs 4).

To remain complete, traditional planners often expand multiple copies of the same logical state if they have different temporal constraints. This leads to a massive explosion in the search space, rendering many real-world problems unsolvable.

Methodology: The Metastate Framework

The proposed framework decouples logical state from temporal constraints using a container called a metastate.

Weak vs. Strong Equality

The authors distinguish between two types of state equality:

  • Weak Equality: States share the same facts, variable values, and currently executing actions.
  • Strong Equality: Requires the actual plans (paths) to be isomorphic.

Lazy Expansion and On-Demand Backtracking

Instead of treating every weakly equal state as a new node, the planner groups them into a single metastate. The search algorithm (a modified WA*) initially expands only one member of a metastate, assuming the first path found is sufficient.

Figure 4: Comparison of search trees. (a) Standard search expands multiple paths to state C, while (b) the metastate approach prunes redundant paths, expanding only the first valid one.

If the chosen path later leads to a temporal inconsistency (e.g., a missed deadline), the algorithm triggers a "re-expansion." It looks for alternative members within the metastate or recursively traverses back to parent metastates to generate new paths that were previously ignored via the FindAnotherMember algorithm. This "lazy" approach preserves completeness while avoiding redundant work.

Experimental Evaluation

The approach was implemented in the OPTIC planner and evaluated on 14 domains, including IPC benchmarks (Rovers, Elevators) and temporally "interesting" domains (Cafe, Driverlog Shift) characterized by required concurrency and tight constraints.

Key Results

  • Increased Coverage: The metastate-enabled planner solved 189 problems, compared to 164 for the state-of-the-art OPTIC using standard memoisation.
  • Search Reduction: In challenging domains like "Driverlog Shift," node expansions dropped by orders of magnitude, solving problems in seconds that previously timed out.
  • Statistical Significance: A Wilcoxon signed-rank test confirmed performance improvements with $P > 0.99$.
  • Minimal Overhead: The bookkeeping required for metastates did not significantly impact execution time, with speedups closely matching node-expansion reductions.

Conclusion

Metastates offer a powerful way to manage the complexity of temporal planning by separating logical possibilities from temporal constraints. By being "lazy" about exploring alternative paths, the planner achieves significant efficiency gains without sacrificing completeness. Future work includes applying this logic to hybrid numeric planning and problems with complex interval constraints. While the approach may occasionally produce sub-optimal makespans, its ability to find solutions in previously intractable domains marks a significant advancement in the field.

Summary updated

BibTeX
@inproceedings{coles2019efficient,
  author = {Amanda Jane Coles and Andrew Coles and J. Christopher Beck},
  title = {{Efficient Temporal Planning Using Metastates}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017554},
}
Figure