Taming Numbers and Durations in the Model Checking Integrated Planning System

Stefan Edelkamp

TL;DR

This paper introduces MIPS, a planning system that integrates model checking techniques to handle complex planning problems involving numerical variables and action durations. MIPS achieves high performance by employing novel algorithms for generating optimal parallel plans and efficiently detecting object symmetries, significantly improving planning efficiency.

What Problem Does This Paper Address?

Traditional AI planning systems often struggle with problems that involve continuous numerical values (like fuel levels or distances) and actions that take time to complete. These "temporal" and "numerical" aspects add significant complexity, making it difficult to find efficient and optimal plans. The authors tackle this challenge by extending their existing planning system, MIPS, to handle these richer problem descriptions, which were introduced in recent planning competitions (PDDL2.1). The core problem is to efficiently search through vast state spaces while considering these numerical and temporal constraints to produce high-quality, time-stamped schedules.

Methods

MIPS employs a multi-faceted approach:

  • Object-Oriented Workbench Architecture: This provides a flexible framework for combining various heuristics, search algorithms, and data structures.
  • Static Analyzer: This component preprocesses planning problems by grounding parameters, inferring static information, minimizing state descriptions, and detecting object symmetries.
  • Critical Path Analysis (PERT Scheduling): A key innovation is the use of PERT scheduling to convert sequentially generated plans into optimal parallel plans in linear time. This bypasses NP-hard problems associated with partial ordering by efficiently scheduling actions based on their dependencies.
  • Heuristic Search: MIPS utilizes various heuristic search algorithms, including A and IDA, enhanced with novel numerical relaxed planning heuristics (RPH) to guide the search more effectively in numerical domains.
  • Object Symmetry Detection: The system automatically identifies and exploits symmetries in the planning problem (e.g., indistinguishable objects) to prune the search space and reduce exploration.
  • Temporal Model: MIPS handles durative actions by flattening temporal modifiers (start, over all, end) into a unified representation, enabling efficient sequential plan generation.

Datasets

The paper uses the Zeno-Travel domain as a running example to illustrate its techniques. It also refers to benchmark domains from planning competitions, including those involving:

  • Pure propositional planning
  • Planning with numerical resources
  • Planning with numerical resources and constant action durations
  • Planning with numerical resources and variable action durations
  • Complex problems combining time and numbers

Key Insights and Ideas

  • PERT Scheduling for Parallel Plans: The paper demonstrates that PERT scheduling can be efficiently applied to derive optimal parallel plans from sequential ones, overcoming known NP-hardness results for partial ordering. This is a significant algorithmic contribution.
  • Object Symmetry as a Search Pruning Technique: Automatically detecting and exploiting object symmetries in the planning problem (e.g., if two trucks are interchangeable) can drastically reduce the search space and improve performance, especially in domains with many similar objects.
  • Integrating Model Checking Concepts: The system's architecture and techniques are heavily influenced by model checking, particularly in its static analysis and exploration strategies, highlighting the synergy between these fields.
  • Numerical Heuristics are Crucial: Developing effective heuristics that can handle numerical variables and their interactions is essential for efficient planning in complex domains.

Key Results

  • MIPS achieved distinguished performance in the last two international planning competitions, performing remarkably well across all tracks, including those with numerical variables and action durations.
  • The system was the only fully automated planner to produce solutions in every track of every benchmark domain in one competition.
  • The critical path analysis algorithm computes optimal parallel plans in linear time with respect to the number of operators and dependencies.
  • Object symmetry detection significantly reduces the number of expanded states, leading to performance gains of over an order of magnitude in some cases. For example, in the Desert Rats domain, symmetry reduction yielded performance gains of more than one order magnitude for larger problems.

Limitations and Future Work

  • Performance Compromises: The competition version of MIPS made some performance compromises, including the use of floating-point arithmetic, inadmissible heuristic search estimates, and parameterized optimization.
  • Completeness and Optimality: While MIPS aims for optimality, the use of inadmissible heuristics means it cannot always guarantee optimal plans, especially in the competition version. The paper discusses an "any-time" extension that could improve optimality but was not used in the competition.
  • Generalizing Temporal Models: The paper notes that the current temporal model has limitations for exploiting parallelism, especially in scenarios requiring true concurrency beyond simple precedence. Future work could explore more sophisticated temporal models.
  • Heuristic Development: The authors acknowledge that developing competitive and admissible heuristics for parallel plans remains an open challenge.
  • Infinite State Spaces: The paper briefly touches upon the challenges of planning in infinite state spaces and suggests that further research is needed to handle such scenarios effectively.

Summary updated

Abstract

The Model Checking Integrated Planning System (MIPS) is a temporal least commitment heuristic search planner based on a flexible object-oriented workbench architecture. Its design clearly separates explicit and symbolic directed exploration algorithms from the set of on-line and off-line computed estimates and associated data structures. MIPS has shown distinguished performance in the last two international planning competitions. In the last event the description language was extended from pure propositional planning to include numerical state variables, action durations, and plan quality objective functions. Plans were no longer sequences of actions but time-stamped schedules. As a participant of the fully automated track of the competition, MIPS has proven to be a general system; in each track and every benchmark domain it efficiently computed plans of remarkable quality. This article introduces and analyzes the most important algorithmic novelties that were necessary to tackle the new layers of expressiveness in the benchmark problems and to achieve a high level of performance. The extensions include critical path analysis of sequentially generated plans to generate corresponding optimal parallel plans. The linear time algorithm to compute the parallel plan bypasses known NP hardness results for partial ordering by scheduling plans with respect to the set of actions and the imposed precedence relations. The efficiency of this algorithm also allows us to improve the exploration guidance: for each encountered planning state the corresponding approximate sequential plan is scheduled. One major strength of MIPS is its static analysis phase that grounds and simplifies parameterized predicates, functions and operators, that infers knowledge to minimize the state description length, and that detects domain object symmetries. The latter aspect is analyzed in detail. MIPS has been developed to serve as a complete and optimal state space planner, with admissible estimates, exploration engines and branching cuts. In the competition version, however, certain performance compromises had to be made, including floating point arithmetic, weighted heuristic search exploration according to an inadmissible estimate and parameterized optimization.
BibTeX
@article{edelkamp2003taming,
  author = {Stefan Edelkamp},
  title = {{Taming Numbers and Durations in the Model Checking Integrated Planning System}},
  journal = {J. Artif. Intell. Res.},
  year = {2003},
  url = {https://openreview.net/forum?id=D0S4M2Ulbxja},
}
Figure