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.
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.
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