State-Space Planning by Integer Optimization

AAAI 1999

TL;DR

This paper introduces ILP-PLAN, a novel framework that tackles complex AI planning problems by reformulating them as Integer Linear Programs (ILPs). By leveraging the power of ILP solvers, ILP-PLAN can handle richer planning scenarios involving resources, action costs, and sophisticated optimization objectives, outperforming existing methods on challenging benchmarks.

What Problem Does This Paper Address?

Traditional AI planning systems, particularly those based on SAT solvers (like SATPLAN), have achieved remarkable success in solving state-space planning problems. However, they often struggle with real-world complexities such as:

  • Resource Constraints: Many planning problems involve managing limited resources (e.g., fuel, bandwidth, personnel). Representing these numeric constraints efficiently within a purely logical framework is challenging.
  • Complex Optimality Criteria: While SATPLAN can minimize the "parallel length" of a plan (the number of time steps when actions can occur concurrently), real-world scenarios often demand more nuanced optimization. This could include minimizing the cost of actions, minimizing resource consumption, or finding the shortest sequential plan (where actions are executed one after another).
  • Bridging AI and Operations Research: There's a desire to harness the advanced optimization capabilities of Operations Research (OR) tools for AI planning problems.

ILP-PLAN aims to bridge this gap by providing a unified framework that can express and solve these more complex planning problems.

Methods

The core innovation of ILP-PLAN lies in its reformulation of planning problems as Integer Linear Programs (ILPs). Here's a breakdown of the key techniques:

  • Integer Linear Programming (ILP): ILP is a mathematical optimization technique that deals with variables that can only take integer values. It allows for expressing both constraints and objective functions as linear inequalities. This is a generalization of SAT, as any logical clause can be translated into a linear inequality over binary variables.
  • ILP-PLAN Framework: This framework translates AI planning problems into ILPs. It supports:
  • STRIPS-style Operators: The logical structure of actions (preconditions and effects) is encoded using standard AI planning representations.
  • Resource Constraints: Numeric variables representing resources are introduced, and their usage by actions is modeled using linear inequalities.
  • Optimization Objectives: Complex criteria, such as minimizing total action cost or sequential plan length, are formulated as linear objective functions to be minimized.
  • Two Solver Approaches:
    • Branch-and-Bound Solvers: The paper demonstrates using commercial ILP solvers (like ILOG CPLEX) that employ branch-and-bound algorithms to find optimal solutions.
  • Integer Local Search (WSAT(OIP)): For problems that are primarily logical in nature, the paper leverages a novel integer local search algorithm called WSAT(OIP). This algorithm generalizes the Walksat algorithm for SAT to "over-constrained integer programs" (OIPs), where some constraints are "soft" and can be violated to a certain degree, forming the objective function. This approach is shown to be more efficient for certain types of problems.

Datasets

The paper evaluates ILP-PLAN on two main types of benchmarks:

  • Transportation Problem ("Airplane"): A modified version of a classic example used in prior planning research, extended to include resource optimization (minimizing fuel).
  • Logistics Domain Benchmark Problems: A set of well-known, challenging logistics planning problems that have been used to evaluate various AI planning systems. These problems involve transporting packages between locations using airplanes and trucks.

Key Insights and Ideas

  • Unified Representation: ILP provides a powerful and flexible language that naturally integrates logical constraints (from STRIPS operators) with numeric constraints (resources) and optimization objectives. This offers a more elegant and comprehensive way to model planning problems than purely logical or purely numeric approaches.
  • Bridging AI and OR: ILP-PLAN effectively demonstrates how sophisticated OR solvers can be applied to AI planning. This opens up new avenues for leveraging decades of research in optimization for AI tasks.
  • Local Search for Optimization: The application of WSAT(OIP) to planning problems shows that local search techniques, traditionally used for satisfiability, can be effectively adapted for optimization problems, often outperforming systematic solvers in terms of speed for certain problem structures.
  • State-Based vs. Operator-Based Encodings: The paper highlights that the choice of encoding (state-based vs. operator-based) significantly impacts the performance of local search algorithms. State-based encodings, which focus on fluent changes between states, seem to be more amenable to local search for planning.
  • Trade-offs in Optimality: The logistics domain experiments reveal that different optimality criteria (e.g., minimizing sequential length vs. minimizing flights/drives) can lead to different plans, and there can be trade-offs between them.

Key Results

  • Improved Solution Quality: For the logistics domain benchmark problems, ILP-PLAN found solutions with a lower sequential plan length and, more importantly, a better "flight-drive" metric (representing actual transportation actions) than previously published results.
  • Efficiency Gains: The WSAT(OIP) solver demonstrated competitive or superior performance compared to traditional ILP branch-and-bound solvers on certain problem instances, particularly for the logistics domain.
  • Handling Complex Objectives: ILP-PLAN successfully handled complex optimization objectives, such as minimizing fuel consumption in the airplane example and minimizing sequential plan length in the logistics domain.

Limitations and Future Work

  • Automated Translation: While the paper describes the encoding conventions, the current implementation relies on manual encoding in AMPL. The authors suggest that an automated system to translate resource-annotated STRIPS into ILP would be highly beneficial.
  • Encoding Complexity for Local Search: The paper notes that operator-based encodings, when combined with state-based encodings, can be problematic for local search. Understanding why this occurs and developing more robust heuristics is an open research question.
  • Systematic Solvers vs. Local Search: The paper acknowledges that while WSAT(OIP) is effective, traditional ILP branch-and-bound solvers are also applicable and might be preferred for certain problem structures or when guaranteed optimality is paramount.
  • Generalizing to More Complex ILPs: The paper focuses on linear inequalities. Future work could explore handling more complex ILP formulations, potentially leveraging recent advances in mixed logical/linear programming.

Summary updated

BibTeX
@inproceedings{1999state,
  title = {{State-Space Planning by Integer Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}

Loading related content...

Figure