On the Use of Integer Programming Models in AI Planning

1 Introduction

Although some of the application areas addressed in the fields of Artificial Intelligence (AI) and Operations Re­ search (OR) are very similar (e.g., planning, scheduling), the techniques that are used to solve these problems are oftentimes substantially different. Therefore, it seems only natural that recent research in the interface between AI and OR has focused on comparing the relative mer­ its of the techniques and tools that are used in these areas. In this paper, we further explore the interface between AI and OR by applying Integer Programming Amnon Lotem Dana N au Department of Computer Science and Institute for Systems Research University of Maryland College Park, MD 20742 USA {lotem, nau}@cs.umd.edu

(IP), which has a rich history in OR, to a classical AI problem, AI planning.

The possibility of using OR techniques in AI plan­ ning has not received much attention so far. Bylander [1997] uses Linear Programming as a heuristic for non­ linear planning; Bockmayr and Dimopoulos [1998] de­ scribe domain-dependent IP models for specific problem domains; and Kautz and Walser [1999], who use IP for­ mulations for planning problems with resources, action costs, and complex objective functions. However, theirs is the only work we know of besides ours.

One potential advantage of using Integer Program­ ming for AI planning is that IP formulations quite natu­ rally allow the incorporation of numeric constraints and objectives into planning domains( for example, see Kautz and Walser [1999]). The use of numerical constraints and objectives is not addressed adequately in most existing AI planning systems, but it is critical in real-world plan­ ning [Nau et al., 1998] .

One difficulty indeveloping Integer Programming for­ mulations for AI planning is that the performance of the resulting IP will depend critically on how AI planning problems are formulated as Integer Programs. The pur­ pose of this paper is therefore to develop good domain­ independent IP formulations for AI planning. In par­ ticular, we discuss various IP formulations for the class of action-based planning problems using STRIPS-style operators. Our main objective is to show that a care­ fully chosen IP formulation significantly improves the "strength" of the LP relaxation, so that it can provide useful guidance in solving the problem.

Our IP formulations are principally derived from work by Kautz and Selman [1996], which showed that planning problems can be efficiently solved by general proposi­ tional satifiablity algorithms. As such, the use of Integer Programming also addresses one of the challenges posed in the paper "Ten Challenges in Propositional Reason­ ing and Search," by Selman et al. [1 997]. Specifically, the challenge that we address concerns the development of IP models and methods for propositional reasoning. Selman et al. mention that the basic technique used to solve integer programs-that is, the Linear Program­ ming (LP) relaxation of the problem- does not appear to be useful for satisfiability problems, since it usually sets all variables (modulo unit propagation) to the value ~ and therefore does not guide the selection of variables in solving the problem.

Our results are as follows:

• In our experiments, IP formulations derived directly from SAT encodings proposed by Kautz and Selman [1996] performed rather poorly-but an alternative IP formulation that we call the "state-change for­ mulation" was competitive with BlackBox using the systematic Satz solver [Kautz and Selman, 1998], in terms of the number of nodes expanded in the search space. Since the branching rule that is used in systematic satisfiability algorithms is an impor­ tant factor in reducing the size of the search tree, this indicates that the LP relaxation does guide the selection of variables in solving the problem.
• Like Graphplan-based planners such as Blackbox, state-change formulation is guaranteed to find plans that have optimal values for the number of time steps in the plan. However, this formulation also takes into account the number of actions required by the plans (i.e., the plan length); and the number of actions obtained using the state-change IP for­ mulation was usually much less than the number of actions in the plans obtained by BlackBox.

The organization of this paper is as follows. In Section 2, we discuss the various IP formulations of the planning problem. Next, Section 3 provides experimental results for these formulations, and a comparison with the sys­ tematic satisfiability solver. We conclude in Section 4 with a brief discussion of issues that arise in using IP techniques, and of plans for future work.

2 Integer Programming Formulations

The most effective current approach for solving general integer programs involves the use of branch and bound employing a linear programming (LP) relaxation. Thus, the key to the effectiveness of using integer programming to solve planning problems will lie in the effectiveness of the LP relaxation in improving the underlying tree search. The LP relaxation is typically solved at every node in the search tree. Search can be terminated at a node 1) if LP relaxation value indicates that further search could only uncover solutions with objective func­ tion values inferior to the best known, 2) if the LP is infeasible, which in turn implies the integer program is infeasible and 3) if the LP yields an integer solution. Since for planning problems, the objective function is only of secondary consideration, 1) will have little value. On the other hand 2) and 3) can be quite useful in im­ proving search performance for planning problems. In particular, if the initial LP solves integer then no search is necessary. Another role the LP relaxation plays is that it provides information useful in deciding which variables to branch on.

A key issue in the performance of integer programming algorithms is the "strength" of the formulation. In gen­ eral, there cari be many equivalent integer programming formulations for a given problem. One formulation is stronger than another if the feasible region of the LP re­ laxation more closely approximates the integer program (see [Wolsey, 1998] for more details on this concept). Stronger formulations are more likely to yield integer so­ lutions and produce objective function values closer to the values of the integer program.

In the remainder of this section we discuss two IP for­ mulations for STRIPS-style planning problems. In order to express these formulations, we first introduce the fol­ lowing sets:

• :F, the set of ftuents, that is, the set of all instanti­ ated predicates;
• A, the set of actions, that is, the set of all instanti­ ated operators;
• I ~ :F. I represents the set of fluents that hold initially;
• g ~ :F. g represents the set of fluents that have to to hold in the goal state.

We assume that the number of time steps in the plan, t, is given. FUrthermore, we introduce the sets

• pre 1 ~ A for all f E :F. pre 1 represents the set of actions which have fluent f as a precondition;
• add 1 ~ A for all f E :F. add 1 represents the set of actions which have fluent f as an add effect;
• del 1 ~ A for all f E :F. del 1 represents the set of actions that delete fluent f.

2.1 SATPLAN-based IP Formulations

Initially, our IP formulations were motivated by the well known SATPLAN encodings, as discussed in [Kautz and Selman, 1996]. In SATPLAN, the problem of determin­ ing whether a plan exists, given a fixed number of time steps, is expressed as a satisfiability problem.

It is well known that satisfiability problems can be expressed as integer linear programs. (see for instance [Blair et al., 1986] or [Hooker, 1988]) . Usually, this is done by converting the clauses in the CNF representation of the satisfiability problem to 0-1linear inequalities. For instance, the clause

is equivalent to the 0- 1 inequality

Our first formulation consisted of this conversion for the SATPLAN encodings that are based on GraphPlan [Blum and FUrst, 1996], i.e., we allow for parallel actions and the propagation of fluents using the "n(}-op" opera­ tor. The resulting formulation is summarized as follows:

Variables For all f E :F, i E 1, ... , t + 1, we have fluent variables, which are defined as

For all a E A, i E 1, .. . , t, we have action variables, which are defined as

We remark that the action variables include the "no­ op" maintain operators from GraphPlan for each time step and fact, which simply has that fact both as a precondition and as an add effect. "no-op" actions are necessary to propagate the fluent values.

Constraints The constraints are separated into differ­ ent classes, which can be outlined as follows:

• Initial/ Goal State Constraints These con­ straints set the requirements on the initial and final period, i.e.

• Precondition Constraints Actions should imply their preconditions, which is expressed as follows.

• Backward Chaining Constraints Backward chaining is expressed as

• Exclusiveness Constraints Actions conflict if one deletes a precondition or add effect of the other. The exclusiveness of conflicting actions is expressed as

for all i E 1, ... , t, and all a, a' for which there exist f E :F such that a E pre f and a' E pre 1 U add1.

Objective Function The objective function was set to minimize the number of actions in the plan. It should be noted that in theory we could have chosen any objective function, since the constraints guar­ antee a feasible solution. In practice however, the choice of an objective function can significantly im­ pact performance.

In addition, we made the following two modifications in the formulation. First of all, we used the notion of clique inequalities to strengthen the formulation. The basic idea behind this is that the inequalities x1 + x2 ::; 1, x2 + x3 ::; 1 and x 1 + x3 ::; 1 can be replaced by a single inequality x1 + x2 + X3 ::; 1. This leads to a formulation which is not only more compact but also stronger, in the sense that the fractional solution x1 = x2 = x3 = ! is feasible in the first set of inequalities, but not in the second. It should be noted that the ability to detect clique inequalities is available in most of today's commercial solvers.

Secondly, we did not restrict all variables to be 0-1 in­ tegers. Specifically, the integrality of the fluent variables x J,i was relaxed, that is, the constraints x J,i E {0, 1} were replaced by 0 ::; x J,i ::; 1. This is possible because the integrality of these variables is implied by the in­ tegrality of the action variables . We remark that as a consequence, none of the fluent variables will be selected in the branch and bound tree.

2.2 An Alternative Formulation

We now describe an alternative formulation of the plan­ ning problem, which we shall refer to as the "state­ change formulation". The differences with respect to the formulation described in the previous section are twofold. First of all, the original fluent variables are "compiled away" and suitably defined "state change" variables are introduced instead. As we will see, this results in a stronger representation of the exclusion con­ straints. Secondly, we more explicitly restrict the pos­ sible propagation of fluents through "no-op" -actions, so as to reduce the number of equivalent feasible solutions.

Before giving this formulation, we again first define the variables. The action variables are the same as before, i.e.,

for all a E A, i E 1 ... t. Now however, the "no-op" actions are not included, but represented separately by . bl mainta in .- II J :F . 1 t van a es x J,i , 10r a E , t E , .. . , .

In order to express the possible state changes, we in­ troduce auxiliary variables x 1 pre-add, xp 1 re-del and xa 1 dd , ~ , ~ , ~ ' which are defined logically as

Informally, xj~;"add = 1 if and only if an action is exe­ cuted in period i that has f as a precondition but does not delete it. We note that the execution of such an ac­ tion at a given time step implicitly asserts that the value fluent f is propagated. Similarly, xj~~del = 1 if and only if an action is executed in period i that has f both as a precondition and a delete effect. xa 1 dd = 1 if and only if .. an action is executed in period i that has f as an add effect but not as a precondition.

The logical interpretation of these variables is represented in the IP formulation by the following constraints:

for all f E F, i E 1, ... , t . The equality in the defi­ nition of xr:'""del follows from the fact that all actions that have f both as a precondition and as an add effect are mutually exclusive. As a consequence these variables can in fact be substituted out, although for reasons of clarity we shall not do so here. The remaining exclusive­ ness constraints can easily be expressed in terms of the auxiliary variables, by stating that xj~:'""del is mutually exclusive with xadd xpre-add and xmaintain However J,t , J,· , !.· . , in order to strengthen the formulation we furthermore assert that xmlC\intain is mutually exclusive with xadd and J,· J,t xr:'""add. Informally, this means that a fluent can only be propagated at a time step if no action that adds it is executed. The resulting constraints are as follows.

for all f E F, i E 1, ... , t.

The backward chaining requirements can also be ex­ pressed in terms of the auxiliary variables. Since, all auxiliary variable that assert the precondition of a fact f at a certain time step (i.e., x 1 pr~add, xm 1 IC\intain, and ,~ ,1 xr:'""del) are mutually exciusive, we have the following constraint

for all f E F, i E 1, ... , t.

Finally, we can express the initial/ goal state con­ straints as

for all f E Q, and

The objective function is again set to minimize the number of actions. Also, the integrality requirement of the auxiliary variables variables was again relaxed, as it is implied by the integrality of the action variables.

3 Experimental Results

We tested the IP formulations on a variety of planning problems from the Blackbox software distribution, and compared the results with those obtained by Blackbox using the systematic Satz solver. The integer programs were solved using Cplex 6.0, a widely used LP /IP solver. In solving the integer programs, we used all of Cplex's default settings, except the following: the initial LP op­ timum was obtained by solving the dual problem, and the variable selection strategy used was "pseudo-reduced cost". In addition, the solver was terminated as soon as a feasible integer solution was found . All problems were run on a Sun Ultra workstation.

The results are shown in Table 1. "Nodes" represents the number of nodes visited in the branch and bound procedure, and "iterations" the number of simplex iter­ ations performed. All times are in seconds. It should be noted that, both for the IP formulations and BlackBox, the results shown are for the problem of finding a fea­ sible solution given the number of time steps (i.e., t is known in advance and given).

As shown in Table 1, the state-change formulation led to a significant improvement in performance. Whereas the SATPLAN-based IP formulation solved only the smallest problems, the state-change formulations solved all, and required both fewer nodes and less computa­ tion time. While the systematic BlackBox solver usu­ ally required less time than the state-change formula­ tion, both BlackBox and the state-change formulation explored similar numbers of nodes. Moreover, the Black­ Box/Satz did not find a feasible solution to the "bw­ large.b" blocks-world problem, while the state-change formulation did find a solution, using only 28 nodes.

It should be noted that the introduction of auxiliary variables can possibly introduce a large number of vari­ ables and constraints. However,we found that the size of the formulation was significantly reduced by standard IP preprocessing (similar to the use of Graphplan as a preprocessing tool in BlackBox). For example, while the initial formulation of the problem "rocket.a" had 27744 variables and 40018 constraints, preprocessing reduced this to 1573 variables and 3007 constraints. Similar re­ ductions in size were also obtained for the other prob­ lems.

A further indication of the strength of respective for­ mulations can be found by examining the value of the LP relaxations. Since the objective function that is used is to minimize the number of actions in the plan, the value of the LP relaxation may also viewed as a lower bound on the number of actions required in the plan. The re­ sults for the SATPLAN-based and the state-change for­ mulation are shown in Table 2. In almost all cases, the state-change formulation has a much higher lower bound, which indicates that its formulation is indeed much stronger.

In the SATPLAN and Graphplan framework, the par­ allel length (i.e., the number of time steps) of plans is minimized. The IP formulation follows this framework,

- denotes that no plan was found after 10 hours of computation time.

* denotes that the node limit of 2500 was reached without finding a feasible integer solution.

so it also is guaranteed to minimize the number of time steps. In addition, the IP formulation also explicitly uses minimization of the number of actions in the objective function. Since we set the solver to terminate as soon as the first feasible integer solution was found, the IP solutions were not guaranteed to minimize the possible number of actions. Still, we found that in most cases, the IP formulation found plans with a significantly smaller total number of actions than those obtained by Black­ Box. This is shown in Table 3.

4 Conclusions

Although Selman et al. [1997] reported difficulty in mak­ ing effective use of IP techniques for propositional rea­ soning in general, our results suggest that IP techniques may potentially work well for AI planning problems, for the following reasons.

• First, the IP formulation has the potential to do

efficient planning. In our results, the number of nodes expanded in the search space was typically small, and comparable to a systematic satisfiablity solver. This indicates that the LP relaxation gave significant guidance in the selection of variables in solving planning problems.

• Second, IP models may provide a natural means of incorporating numeric constraints and objec­ tives into the planning formulation. This capability would be important in many application domains, but it is not available in most existing approaches to AI planning. It should be noted, however, that the way in which numeric constraints will be repre­ sented may have a significant influence on the per­ formance, much in the same way as we saw with the various IP formulations . Therefore, the devel­ opment of strong IP representations that capture common numeric constraints that arise in the plan­ ning domain is an issue for further research.

We would like to emphasize that so far our main concern has been the development of different IP formulations, rather than improving the efficiency of the LP relaxation itself. While we believe that the state-change formula­ tion is reasonably strong, solving the LP relation at each node is still sometimes computationally expensive. One of the main reasons for this, we believe, is the degener­ acy of the LP relaxation (a condition that can cause the LP solver to execute many non-productive iterations). Therefore, we are currently also investigating techniques to resolve this degeneracy, as well as further strength­ ening of the IP formulation. In particular, we want to investigate the use of constraint and column generation techniques.