Efficiently Reasoning with Interval Constraints in Forward Search Planning

Amanda Jane Coles, Andrew Coles, Moisés Martínez, Emre Savas, Juan Manuel Delfa, Tomás de la Rosa, Yolanda E-Martín, Angel García OlayaAAAI 2019 · DOI

Abstract

PDDL-based temporal planners traditionally struggle with complex interval constraints, often relying on inefficient compilation methods that bloat the search space. This paper introduces a "native reasoning" approach that integrates these constraints directly into the planner's internal Mixed Integer Program (MIP) solver. By representing Allen’s Interval Algebra relations as linear inequalities and utilizing zero-duration "dummy steps," the authors demonstrate performance gains of up to three orders of magnitude over traditional methods while maintaining the search efficiency of forward-search planning.

Introduction

In automated planning, a significant gap exists between PDDL planners—optimized for large-scale state-space search—and timeline planners, which are designed for complex temporal synchronization. PDDL planners typically lack native support for interval constraints, such as requiring one action to occur strictly during another. Previous attempts to bridge this gap involved "compiling" these constraints into standard PDDL actions, a process that significantly increases the branching factor and degrades performance. This research proposes a native integration within the OPTIC planner to provide timeline-like expressiveness without the associated "compilation tax."

The Problem: The Compilation Tax

The primary challenge in handling interval constraints within PDDL is the explosion of the search space. Compiling a constraint like "Action A must happen during Action B" requires the introduction of numerous auxiliary predicates and dummy actions to track the state of intervals. This approach creates a massive number of "dummy" states, causing planners to fail on even moderately complex problems. The goal of this work is to move this reasoning from the search process into a dedicated mathematical solver.

Methodology: Native Reasoning via MIP

The authors extended the OPTIC forward-search temporal planner to handle interval constraints natively. This approach moves away from state-space compilation and relies on three core components:

1. Temporal Anchor Points

The planner inserts zero-duration "dummy steps" into the plan at every point where a relevant fact changes. These steps act as precise anchors for the start and end of intervals, allowing the solver to precisely define the boundaries of temporal constraints.

2. Modeling Interval Relations

Logical relationships from Allen’s Interval Algebra, such as Before, Overlaps, and During, are translated into linear inequalities. These are visualized as "Struts"—temporal links that enforce lower and upper bounds on the duration between anchor points.

Visual representation of how various interval relations (Before, Overlaps, During) are modeled as temporal struts with duration bounds.

3. MIP Integration and Big-M Constraints

OPTIC utilizes a Mixed Integer Program (MIP) to ensure temporal consistency. The authors extended this MIP with binary decision variables, enabling the solver to choose which specific occurrence of a fact satisfies a given constraint. To handle the logical "either-or" nature of these choices, "Big-M" notation is used to formulate linear inequalities that the solver can process efficiently.

The internal representation of duration constraints using 'Clips' and 'Struts' within the MIP solver.

Evaluation and Results

The proposed method was evaluated against standard compilation techniques and other temporal planners (like MTP and APSI) across several domains, including a new "Concrete" mixing domain and a Mars Rover domain from the European Space Agency (ESA).

Key Results

  • Orders of Magnitude Speedup: The native approach consistently outperformed compilation by 10x to 1000x. Problems that were unsolvable within 30 minutes using compilation were often solved in under two seconds.
  • Continuous vs. Discrete Time: Unlike the MTP planner, which discretizes time and failed on tight intervals, the authors' continuous-time MIP approach handled complex timing constraints with ease.
  • Competitive with Timeline Planners: On the ESA Mars Rover domain, the extended OPTIC planner was competitive with APSI, a dedicated timeline planner, particularly in scenarios with high goal-ordering complexity.

Conclusion and Future Work

Native reasoning for interval constraints significantly enhances the capability of PDDL planners. By offloading temporal logic to a MIP solver, the planner avoids the search space explosion associated with compilation. Future research will focus on making the planner's reachability heuristics aware of these constraints to prune invalid paths earlier in the search and extending the system to optimize for plan metrics such as makespan.

Summary updated

BibTeX
@inproceedings{coles2019efficiently,
  author = {Amanda Jane Coles and Andrew Coles and Moisés Martínez and Emre Savas and Juan Manuel Delfa and Tomás de la Rosa and Yolanda E-Martín and Angel García Olaya},
  title = {{Efficiently Reasoning with Interval Constraints in Forward Search Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017562},
}
Figure