The Deterministic Part of IPC-4: An Overview

Jörg Hoffmann, Stefan Edelkamp

TL;DR

The 4th International Planning Competition (IPC-4) showcased significant advancements in automated planning, introducing new language features like derived predicates and timed initial literals. The competition highlighted the growing scalability of satisficing planners, particularly those employing novel heuristics and domain analysis techniques, while also demonstrating the challenges of optimal planning.

What Problem Does This Paper Address?

This paper provides an overview of the deterministic part of the 4th International Planning Competition (IPC-4). The core problem addressed is the evaluation and comparison of automated planning systems. The authors aim to:

  • Introduce the IPC and its evolution: Explain the purpose and history of the International Planning Competition as a platform for assessing the state-of-the-art in AI planning.
  • Detail the IPC-4 deterministic track: Describe the specific organization, language features, and benchmarks used in this particular competition.
  • Present the results and insights: Summarize the performance of competing systems across various domains and language subsets, highlighting key trends and findings.
  • Explain the award decisions: Outline the criteria used to determine the winners, emphasizing scaling behavior and plan quality.

The paper aims to provide a comprehensive account of the deterministic planning landscape as reflected in IPC-4, serving as a valuable resource for researchers and practitioners in the field.

Methods

The paper details several key methodological aspects of IPC-4:

  • PDDL2.2 Language: The competition utilized PDDL2.2, an extension of PDDL2.1. The primary new features introduced were:
  • Derived Predicates: These allow for the definition of predicates whose truth values are inferred from other predicates using rules, essentially acting as domain axioms. This feature was motivated by real-world applications and has theoretical justification due to the potential infeasibility of compiling them away.
  • Timed Initial Literals: This feature allows for specifying literals that become true or false at specific time points, independent of actions. This is crucial for modeling real-world temporal constraints like time windows.
  • Application-Oriented Benchmarks: A significant effort was made to create benchmark domains that closely resemble real-world applications, including Airport, Pipesworld, Promela, PSR, and UMTS. These domains were designed to test various aspects of planning, such as temporal reasoning, numeric variables, and complex interactions.
  • Domain Compilations: To encourage broader participation, PDDL2.2 features were compiled into simpler PDDL subsets (e.g., ADL to STRIPS, derived predicates to actions). This allowed planners that only supported simpler languages to compete.
  • Optimal vs. Satisficing Tracks: IPC-4 explicitly separated planners into "optimal" (guaranteeing solution quality) and "satisficing" (finding any correct solution) tracks. This distinction was made because optimal planning is theoretically harder and often exhibits a significant performance gap with satisficing planning.
  • Evaluation Metrics: Performance was evaluated based on runtime, plan quality (number of actions, makespan, or metric value), and the percentage of instances solved. Graphs were used to visualize scaling behavior, with a focus on how planners handled larger instances.

Datasets

The paper describes several newly introduced benchmark domains for IPC-4, designed to be application-oriented:

  • Airport: Models airport ground traffic control.
  • Pipesworld: Deals with transporting oil derivatives through pipeline networks.
  • Promela: Based on model checking of communication protocols, specifically the Dining Philosophers and Optical-Telegraph protocols.
  • PSR (Power Supply Restoration): A PDDL adaptation for reconfiguring a faulty power distribution system.
  • UMTS: Models the setup of applications on mobile devices, involving scheduling and dependencies.

Additionally, the Satellite and Settlers domains from IPC-3 were re-used and extended with new features like time windows.

Key Insights and Ideas

  • Scalability of Satisficing Planners: The competition demonstrated a significant leap in the scalability of satisficing planners, largely driven by novel heuristics and domain analysis techniques. This suggests a maturing of the field in tackling complex, real-world problems.
  • Value of New PDDL Features: Derived predicates and timed initial literals proved to be practically motivated and useful for modeling real-world scenarios, leading to their adoption by a considerable number of competing systems.
  • Optimal vs. Satisficing Performance Gap: The explicit separation of optimal and satisficing tracks confirmed the theoretical and practical difficulty of optimal planning. Optimal planners generally solved fewer instances and were slower, though some exceptions existed.
  • Benchmark Design Matters: The focus on application-oriented benchmarks led to more realistic and challenging test cases, pushing the boundaries of current planning capabilities.
  • Compilation Strategies are Crucial: The use of compilation techniques to make PDDL2.2 features accessible to simpler planners was essential for broad participation and highlighted the trade-offs between expressiveness and tractability.
  • The "Flaw" Construct's Impact: The UMTS-flaw domain demonstrated how introducing seemingly minor, practically motivated constructs could significantly confuse heuristic-based planners, revealing vulnerabilities in current approaches.

Key Results

  • High Planner Participation: IPC-4 saw 19 competing systems (21 with different versions), an increase from previous competitions.
  • Dominance of Satisficing Planners: Satisficing planners generally outperformed optimal planners in terms of the number of instances solved and speed.
  • Top Performers:
    • Satisficing: SGPlan, LPG-TD, FDD, and YAHSP showed strong performance across various domains and language subsets. SGPlan, in particular, exhibited excellent scalability and coverage.
  • Optimal: SATPLAN and CPT were among the top performers in the optimal track, though their overall success rate was lower than the leading satisficing planners.
  • Language Feature Adoption: While STRIPS remained a core feature, there was significant adoption of PDDL2.1/2.2 features like ADL, numeric variables, and durations. Derived predicates and timed initial literals saw moderate adoption.
  • Domain-Specific Challenges: Certain domains, like Pipesworld with tankage restrictions and Optical-Telegraph, proved particularly challenging, even for the best planners.
  • Plan Quality: While runtime was a primary focus, plan quality was also evaluated. In some cases, satisficing planners found comparable or even better plans than optimal planners, often due to differences in how temporal actions were modeled.

Limitations and Future Work

  • Data Interpretation Complexity: The sheer volume of data generated by IPC-4 made a full presentation impossible, necessitating a focus on summaries and plots. The authors acknowledge that a detailed examination of the online appendix is crucial for a complete understanding.
  • Simplifications in Analysis: For readability, certain planner versions and distinctions (e.g., between different optimization criteria for optimal planners) were omitted from the graphs. The authors emphasize that these omissions do not imply a lack of importance.
  • Hand-Tailored Track Challenges: The hand-tailored track was discontinued due to a lack of participation and difficulties in objectively evaluating "effort." The authors suggest alternative formats like online competitions for future consideration.
  • PDDL Extensions: The paper notes that derived predicates and timed initial literals are "first steps" and suggests future work could explore more complex interactions for derived predicates and more general forms of exogenous events.
  • Competition Organization: The authors suggest that the growing scale of IPC may necessitate distributing organizational workload among a larger group and potentially establishing a permanent IPC council.
  • Benchmark Re-use: The authors advocate for re-using existing benchmarks in future IPC editions to better measure progress and consolidate performance, rather than constantly introducing new ones.

Summary updated

Abstract

We provide an overview of the organization and results of the deterministic part of the 4th International Planning Competition, i.e., of the part concerned with evaluating systems doing deterministic planning. IPC-4 attracted even more competing systems than its already large predecessors, and the competition event was revised in several important respects. After giving an introduction to the IPC, we briefly explain the main differences between the deterministic part of IPC-4 and its predecessors. We then introduce formally the language used, called PDDL2.2 that extends PDDL2.1 by derived predicates and timed initial literals. We list the competing systems and overview the results of the competition. The entire set of data is far too large to be presented in full. We provide a detailed summary; the complete data is available in an online appendix. We explain how we awarded the competition prizes.
BibTeX
@article{hoffmann2005deterministic,
  author = {Jörg Hoffmann and Stefan Edelkamp},
  title = {{The Deterministic Part of IPC-4: An Overview}},
  journal = {J. Artif. Intell. Res.},
  year = {2005},
  url = {https://openreview.net/forum?id=zAc4xma2zmM},
}
Figure