A lookahead strategy for solving large planning problems

1 Computing and using lookahead states

In classical forward state-space search algorithms, a node in the search graph represents a planning state and an arc start­ ing from that node represents the application of one action to this state, that leads to a new state. In order to ensure com­ pleteness, all actions that can be applied to one state must be considered. The order in which these states will then be con­ sidered for development depends on the overall search strat­ egy: depth-first, breadth-first, best-first. ..

The determination of an heuristic value for each state as performed in the FF planner [Hoffmann and Nebel, 200 I] offers a way to compute such lookahead plans. FF creates a planning graph [Blum and Furst, 1997] for each encoun­ tered stateS, using the relaxed problem obtained by ignoring deletes of actions and using S as initial state. A relaxed plan is then extracted in polynomial time and space from this plan­ ning graph. The length in number of actions of the relaxed plan corresponds to the heuristic evaluation of the state for which it is calculated. Generally, the relaxed plan for a state S is not valid for S, as deletes of actions are ignored during its computation. In numerous benchmark domains, we can observe that relaxed plans have a very good quality because they contain a lot of actions that belong to solution plans. We propose a way of computing lookahead plans from these re­ laxed plans, by trying as most actions as possible from them and keeping the ones that can be collected into a valid plan.

Let us now imagine that for each evaluated state S, we knew a valid plan P that could be applied to S and would lead to a state closer to the goal than the direct descendants of S. It could then be interesting to apply P to S, and use the resulting state S' as a new node in the search. This state could be simply considered as a new descendant of S .

We have then two kinds of arcs in the search graph: the ones that come from the direct application of an action to a state, and the ones that come from the application of a valid plan to a stateS and lead to a stateS' reachable from S. We will call such states lookahead states, as they are computed by the application of a plan to a node S but are considered in the search tree as direct descendants of S. Nodes created for lookahead states will be called lookahead nodes. Plans label­ ing arcs that lead to lookahead nodes will be called lookahead plans. Once a goal state is found, the solution plan is then the concatenation of single actions for arcs leading to classi­ cal nodes and lookahead plans for arcs leading to lookahead nodes.

*This work has been supported in part by the IUT de Lens, the CNRS and the Region Nord/Pas-de-Calais under the TACT Pro­ gramme.

The lookahead algorithm and the modifications to the search algorithm are the following (all details can be found in [Vidal, 2002]). Each time a state S is evaluated, it is en­ tered into the open list. The relaxed plan extracted by the evaluation function is used to compute a lookahead plan P which leads to a stateS' reachable from S. If Pis more than one action long, S' is evaluated and added to the open list. Let P be a relaxed plan for a state S. A lookahead plan P' is computed as follows: all actions of P are observed in tum. When an action a is applicable to S, it is added to the end of P' and S is updated (by the application of a). When all ac­ tions of P have been tried, this process is iterated without the actions that have been applied, until no action can be used.

Completeness and correctness of search algorithms are pre­ served by this process, because no information is lost: all ac­ tions that can be applied to a state are still considered, and be­ cause the nodes that are added by lookahead plans are reach­ able from the states they are connected to. The only modifi­ cation is the addition of new nodes, corresponding to states that can be reached from the initial state.

2 Using helpful actions: the "optimistic" best-first search algorithm

In classical search algorithms, all actions that can be applied to a node are considered the same way: the states that they lead to are evaluated by an heuristic function and are then ordered, but there is no notion of preference over the actions themselves. Such a notion of preference during search has been introduced in the FF planner, with the concept of help­ ful actions. Once a relaxed plan is extracted for a stateS, the actions of the relaxed plan that are executable in S are con­ sidered as helpful, while the other actions are forgotten by the local search algorithm ofFF. This strategy appeared to be too restrictive, so the set of helpful actions is augmented in FF by all actions executable in S that produce fluents that were con­ sidered as subgoals at the first level of the planning graph, during the extraction of the relaxed plan. The main draw­ back of this strategy, as used in FF, is that it does not preserve completeness: the actions executable in a state S that are not considered as helpful are simply lost. FF switches to a com­ plete best-first algorithm when no solution is found.

We present a way to use such a notion of helpful actions in complete search algorithms, that we call optimistic search algorithms because they give a maximum trust to the infor­ mations returned by the computation of the heuristic. The principles are the following:

• Several classes of actions are created. In our implemen­ tation, we only use two of them: helpful actions (there­ stricted ones), and rescue actions that are all the actions that are not helpful.
• When a newly created state S is evaluated, the heuris­ tic function returns the numerical estimation of the state and also the actions executable inS partitioned into their different classes. For each class, one node is created for the state S, that contains the actions of that class.
• Nodes containing helpful actions are always preferred for development over nodes containing rescue actions, whatever their numerical heuristic values are.

No information is lost by this process. The way nodes are developed is simply modified: a stateS is developed first with helpful actions, some other nodes are developed, and then S can potentially be developed with rescue actions. As the union of helpful actions and rescue actions is equal to the set of all the actions that can be applied to S, completeness and correctness are preserved.

3 Experimental evaluation

We compare four planners: FF v2.3, and three different set­ tings of our planning system called YAHSP (which stands for Yet Another Heuristic Search Planner') implemented in Ob­ jective Cam!: BFS (Best First Search: classical WA* search, with W = 3. The heuristic is based on the computation of a relaxed plan as in FF), OBFS (Optimistic Best First Search: identical to BFS, with preference of helpful actions over res­ cue actions), and LOBFS (Lookahead Optimistic Best First Search: identical to OBFS, with lookahead states).

We report here complete results for Logistics domain (see Figure 1) and show in Table 1 some data about the largest problems solved by FF, OBFS and LOBFS, in order to realize the progress accomplished in the size of the problems that can be solved by a STRIPS planner, for five different domains.

Acknowledgments

Thanks a lot to Pierre Regnier for his help ...