Temporal Planning with Temporal Metric Trajectory Constraints

Andrea Micheli, Enrico ScalaAAAI 2019 · DOI

Introduction

Automated planning has traditionally excelled at causal reasoning—determining the sequence of actions needed to achieve a goal. However, industrial applications often require strict adherence to complex temporal constraints that span multiple actions. In their AAAI-19 paper, Micheli and Scala introduce Timed Planning Problems (TPP), a formalism that integrates quantified temporal metric constraints into classical planning. Their proposed solver, TPACK, utilizes an "eager" search strategy and temporally-aware heuristics to address problems that were previously intractable for general-purpose planners.

The Challenge of Cross-Action Constraints

Standard planning languages like PDDL 2.1 are effective at modeling action durations but struggle with constraints that link the timing of separate actions. A classic example is the Hoist Scheduling Problem (HSP) in an electroplating plant. Here, an item must remain in a chemical bath for a precise window (e.g., 10 to 12 minutes). Deviating from this window results in a defective product.

Figure 1: Illustration of the Hoist Scheduling Problem (HSP), where items must be moved between tanks according to strict temporal "recipes."

Modeling such constraints in PDDL often requires "clip-action" workarounds—artificial actions that significantly expand the search space. While timeline-based planning handles these constraints naturally, it lacks the robust causal reasoning of action-based systems. TPP bridges this gap by treating temporal "recipes" and causal goals with equal priority.

Formalism: Timed Planning Problems (TPP)

The TPP framework extends classical planning with Temporal Knowledge (TK). TK consists of axioms expressed in first-order logic that predicate over the execution times of action instances. For instance, an axiom can specify that every load action must be followed by an unload action within a specific time interval. This approach allows for the expression of complex protocols more naturally than state-based trajectory constraints.

The TPACK Solver

The authors developed TPACK, a heuristic forward-search planner featuring two primary search strategies:

  1. LAZY-SEARCH: This strategy finds a causally valid plan first and subsequently verifies temporal feasibility.
  2. EAGER-SEARCH: This "eager" approach anticipates future temporal requirements during the search process. If an axiom dictates a future action, the planner maintains this as a "commitment." If these commitments become impossible to satisfy, the search branch is pruned immediately.

To guide this search, the authors introduced the $h_{dtk}$ heuristic. Unlike standard "temporally blind" heuristics, $h_{dtk}$ incorporates future temporal commitments into its calculations, forcing the planner to account for the preconditions of actions that are mandated by temporal axioms but have not yet occurred.

Experimental Evaluation

The effectiveness of TPACK was evaluated across several challenging benchmarks, most notably the Hoist Scheduling Problem (HSP) and Multi-Agent Job-Shop Scheduling (MAJSP).

Hoist Scheduling Problem (HSP)

In the HSP domain, TPACK demonstrated a significant performance leap over state-of-the-art temporal planners. Using the $h_{dtk}$ heuristic, TPACK solved 90 out of 100 instances, whereas competitors like OPTIC and ITSAT could only solve a maximum of two instances.

Figure 3: Cactus plot showing the number of HSP instances solved over time. The TPACK variant with the $h_{dtk}$ heuristic significantly outperforms other configurations.

MAJSP and IPC Benchmarks

In the MAJSP domain, TPACK solved between 133 and 144 instances, far exceeding OPTIC's 22. Furthermore, on IPC-14 benchmarks augmented with complex temporal patterns (intermediate effects), TPACK solved nearly four times as many instances as ITSAT, proving its robustness in the face of intricate temporal requirements.

Conclusion

The introduction of TPP and the TPACK solver represents a significant advancement in temporal planning. By intertwining planning and scheduling through EAGER-SEARCH and informed heuristics, the authors provide a scalable solution for industrial problems with strict temporal constraints. Future work aims to address the state-space explosion inherent in branching on existential quantifiers and to extend the formalism to continuous-time patterns and durative actions.

Summary updated

BibTeX
@inproceedings{micheli2019temporal,
  author = {Andrea Micheli and Enrico Scala},
  title = {{Temporal Planning with Temporal Metric Trajectory Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017675},
}
Figure