Dealing with Numeric and Metric Time Constraints in PDDL3 via Compilation to Numeric Planning

Luigi Bonassi, Alfonso Emilio Gerevini, Enrico ScalaAAAI 2024 · DOI

TL;DR

This paper introduces NTCORE, a novel compilation technique that translates complex PDDL3 planning problems with numeric and metric time constraints into simpler numeric planning problems. This allows existing, highly optimized numeric planners to solve these previously intractable problems, setting a new state-of-the-art in this domain.

What Problem Does This Paper Address?

Traditional AI planning often deals with discrete states and actions. However, real-world problems frequently involve continuous quantities (like fuel levels or distances) and temporal specifications that go beyond simple start/end conditions. PDDL3 was developed to handle these "trajectory constraints" – properties that a plan must satisfy over time. While PDDL3 can express these constraints, existing planners struggle to efficiently handle them, especially when combined with numeric variables. This paper tackles the challenge of planning with PDDL3 constraints that involve both numeric conditions (e.g., "fuel must be above 100 units") and metric time constraints (e.g., "an event must occur within 5 minutes"). The core problem is that existing planners are not well-equipped to reason about these mixed constraints simultaneously.

Methods

The paper's core contribution is a compilation approach called NTCORE. It works by transforming a PDDL3 problem with trajectory constraints into an equivalent numeric planning problem without these constraints. This is achieved through a sophisticated "regression" mechanism that effectively "unwinds" the constraints backward through the actions.

Here's a breakdown of the key techniques:

  • Regression: This is the central idea. For each action, NTCORE computes a "regressed" version of the constraints. This means determining what must be true before an action occurs for the constraint to be satisfied after the action. This process is extended to handle both Boolean and numeric variables, as well as complex arithmetic expressions.
  • Introducing New Variables: To track the satisfaction of various constraints over time, NTCORE introduces new Boolean and numeric variables. For instance, new Boolean variables might track whether a specific constraint has been met, and new numeric variables might record the time at which a condition was last satisfied.
  • Action Transformation: Each original action is transformed into a new action with potentially modified preconditions and effects. These modifications ensure that the new actions, when executed in the compiled problem, implicitly satisfy the original trajectory constraints.
  • Optimized Compilation (NTCORE+): A significant improvement, NTCORE+, is introduced. It leverages the concept of "achievers" – actions that can potentially satisfy or violate a constraint. By identifying actions that are not achievers for certain constraints, NTCORE+ can avoid adding unnecessary preconditions and effects, leading to much smaller compiled problems. This optimization is crucial for performance.
  • Metric Time Constraint Handling: Specific techniques are used to translate metric time constraints (like within, hold-after, hold-during) into equivalent forms that can be managed by the regression and compilation process, often by introducing a dedicated "time" variable.

Datasets

The authors generated a new set of benchmarks by extending ten well-known numeric planning domains (COUNTERS, ROVERS, DEPOTS, TPP, ZENOTRAVEL, FARMLAND, PLANTWATERING, SAILING, and BLOCKGROUPING). They specifically added PDDL3 trajectory constraints, including numeric conditions and metric time constraints, to these existing domains. This created a diverse suite of 512 instances to evaluate their approach.

Key Insights and Ideas

  • Compilation as a Unifying Strategy: The paper demonstrates that by compiling complex PDDL3 problems into standard numeric planning problems, a wide range of existing, highly optimized numeric planners can be leveraged. This avoids the need to develop specialized planners for every new type of constraint.
  • The Power of Regression for Mixed Constraints: The core innovation is extending the regression technique to effectively handle both Boolean and numeric variables simultaneously within trajectory constraints. This is a significant step beyond previous work that focused on only one type.
  • The "Achiever" Concept for Optimization: Identifying which actions can actually influence a constraint (achievers) is key to pruning the search space. The NTCORE+ optimization, by focusing on actions that cannot affect a constraint, drastically reduces the size of the compiled problem, leading to substantial performance gains.
  • Bridging the Gap: The work directly addresses a noted gap in the literature concerning planning with both numeric state variables and trajectory constraints.

Key Results

NTCORE and its optimized version, NTCORE+, significantly outperform existing state-of-the-art planners that natively support PDDL3 trajectory constraints (OPTIC, SGPLAN, MIPS).

  • Coverage: NTCORE+ achieved approximately five times the coverage of the best native PDDL3 planner (OPTIC), solving most of the generated benchmark instances.
  • Performance: NTCORE+ demonstrated substantial speedups, often being an order of magnitude faster than the basic NTCORE compilation. This is attributed to the significantly smaller compiled problems generated by NTCORE+.
  • Solution Quality: Plans generated by NTCORE+ were comparable in length to those from native PDDL3 planners, with some instances showing NTCORE+ producing shorter plans.

Limitations and Future Work

  • Equality Constraints: The paper notes that dealing with exact equality conditions (=) in numeric constraints is challenging at compilation time, as it requires reasoning about specific state values. The current regression mechanism is less effective for these.
  • New Benchmark Generation: While the authors created new benchmarks, they acknowledge that there were no existing domains featuring PDDL3 trajectory constraints with numeric terms and metric time constraints.
  • Future Work: The authors suggest extending their approach to more complex temporal constraints, such as those expressible in Linear Temporal Logic (LTL) modulo theory, and exploring its application in more general temporal planning scenarios. They also plan to investigate the adoption of numeric state variables in more complex temporal constraints.

Summary updated

BibTeX
@inproceedings{bonassi2024dealing,
  author = {Luigi Bonassi and Alfonso Emilio Gerevini and Enrico Scala},
  title = {{Dealing with Numeric and Metric Time Constraints in PDDL3 via Compilation to Numeric Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.29981},
}
Figure