Abstract

The Optiplan planning system is the first integer programming-based planner that successfully participated in the international planning competition. This engineering note describes the architecture of Optiplan and provides the integer programming formulation that enabled it to perform reasonably well in the competition. We also touch upon some recent developments that make integer programming encodings significantly more competitive.

Introduction

Optiplan is a planning system that uses integer linear programming (IP) to solve STRIPS planning problems. It is the first such system to take part in the international planning competition (IPC) and was judged the second best performer in four competition domains of the optimal track for propositional domains. Optiplan’s underlying integer programming formulation extends the state change model by Vossen and his colleagues (1999). Its architecture is very similar to that of Blackbox (Kautz & Selman, 1999) and GP-CSP (Do & Kambhampati, 2001), but instead of unifying satisfiability (SAT) or constraint satisfaction (CSP) with graph based planning, Optiplan uses integer programming. Like Blackbox and GP-CSP, Optiplan works in two phases. In the first phase a planning graph is built and transformed into an IP formulation, then in the second phase the IP formulation is solved using the commercial solver ILOG CPLEX (ILOG Inc., 2002).

A practical difference between the original state change model and Optiplan is that the former takes as input all ground actions and fluents over all initialized plan steps, while the latter takes as input just those actions and fluents that are instantiated by Graphplan (Blum & Furst, 1995). It is well known that the use of planning graphs has a significant effect on the size of the final encoding no matter what combinatorial transformation method (IP, SAT, or CSP) is used. For instance, Kautz and Selman (1999) as well as Kambhampati (1997) pointed out that Blackbox’s success over Satplan (Kautz & Selman, 1992) was mainly explained by Graphplan’s ability to produce better, more refined, propositional structures than Satplan. In addition, Optiplan allows propositions to be deleted without being required as preconditions. Such state changes are not modeled in the original state change model, and therefore Optiplan can be considered to be a more general encoding.