Models of Action Concurrency in Temporal Planning

Jussi RintanenIJCAI 2015

Introduction

Temporal planning is a critical discipline in artificial intelligence, focused on determining not only the sequence of actions required to achieve a goal but also the precise timing of those actions. For over a decade, the Planning Domain Definition Language (PDDL 2.1) has served as the industry standard for modeling these problems. However, recent research suggests that the semantics of PDDL 2.1 may be inadvertently hindering the performance of modern constraint-based solvers. By forcing artificial "temporal gaps" between actions, PDDL creates unnecessary complexity that sabotages the efficiency of Satisfiability Modulo Theories (SMT) and SAT-based planners.

The "Temporal Gap" Problem

The core issue lies in how PDDL 2.1 handles action interference. If an action's starting effect modifies a state variable that another action requires as a precondition, the two actions cannot occur at the exact same time. This necessitates a small, discrete interval between them—a "temporal gap." For example, if a robot moves from room A to room B, and then immediately from room B to room C, PDDL requires the robot to "finish" its presence in A and "start" its presence in B in a way that avoids overlap.

For modern planners that translate these problems into logical constraints, these gaps are computationally expensive. In an SMT encoding, a sequence of $n$ interdependent actions requires $2n$ discrete time steps to represent the necessary transitions. Because the complexity of these solvers grows exponentially with the number of steps, this modeling choice acts as a significant bottleneck, effectively doubling the search space for the solver.

Modeling Philosophies: PDDL vs. NDL

This paper compares the standard PDDL approach with a resource-based modeling philosophy known as NDL (Numeric Domain Language).

  1. PDDL-Style (Action Exclusion): This approach relies on implicit exclusions. If Action A negates a variable that Action B requires, they are deemed mutually exclusive at a specific timestamp, forcing the aforementioned gaps.
  2. NDL-Style (Explicit Resources): This approach utilizes an explicit notion of resources. For instance, instead of relying on state variable changes to prevent overlap, a model might specify that "only one robot can occupy this hallway at a time."

By shifting to explicit resource constraints, researchers can eliminate the need for temporal gaps. In NDL, the same sequence of $n$ actions that required $2n$ steps in PDDL can be represented in just $n+1$ steps. This allows actions to be packed tighter, significantly reducing the depth of the search required by the solver.

Methods and Formalization

The author, Jussi Rintanen, formalizes both modeling styles into SMT encodings. SMT is a generalization of SAT that allows solvers to handle both logical propositions and linear numeric constraints, such as time and resource levels.

A key contribution of this work is Theorem 1, which provides a mathematical framework for translating PDDL models into NDL. The translation involves delaying "at start" effects until the end of an action and using explicit resource "locks" to ensure that no other action can exploit a state change prematurely. This ensures that the physical constraints of the problem are maintained without the overhead of artificial temporal steps.

Experimental Results

The approach was evaluated using standard benchmark problems from the 2008 and 2011 International Planning Competitions (IPC), including domains like logistics (Elevators, Transport), puzzles (Sokoban, Pegsol), and industrial services (Floortile, Storage). The PDDL benchmarks were manually translated into NDL and tested using the Z3 SMT solver.

Performance comparison between PDDL and NDL models using the Z3 SMT solver. The log-log plot shows that NDL models consistently solve problems faster, often by multiple orders of magnitude.

The results were dramatic. The NDL-based models achieved performance gains of one to three orders of magnitude (10x to 1000x faster) compared to their PDDL counterparts. Furthermore, the NDL approach demonstrated significantly higher success rates across the benchmark set.

Comparison of solved instances across IPC benchmarks for NDL and PDDL models. NDL significantly outperforms PDDL in total solved instances.

As shown in the data, the NDL-based planner solved 86 instances within a 30-minute time limit, while the PDDL-based version solved only 50. In complex domains like Elevators and Transport, the PDDL models failed to solve a single instance that the NDL models handled with ease.

Conclusion

The findings suggest that the limitations of current temporal planners are often not a result of weak search algorithms, but rather the modeling languages used to describe the problems. By adopting resource-based models like NDL, researchers can unlock massive performance improvements in constraint-based planning. Future work will focus on fully automating the translation from PDDL to NDL and extending these insights to handle continuous changes, such as fuel consumption or fluid dynamics.

Summary updated

BibTeX
@inproceedings{rintanen2015models,
  author = {Jussi Rintanen},
  title = {{Models of Action Concurrency in Temporal Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure