Early Commitment through Flaw Selection.

We have shown (Younes & Simmons, 2002) that giving priority to static open conditions can be beneficial when planning with lifted actions. Introducing a new flaw type, ``t'', representing static open conditions, we can specify this flaw selection strategy as follows:

Static-First    {t}LIFO  /  {n, s}LIFO  /  {o}LIFO

A static open condition is a literal that involves a predicate occurring in the initial conditions of a planning problem, but not in the effects of any operator in the planning domain. This means that a static open condition always has to be linked to the initial conditions, and the initial conditions consist solely of ground literals. Resolving a static open condition $\;\stackrel{{q}}{{\longrightarrow}}\;$a_i will therefore cause all free variables of q to be bound to specific objects. Resolving static open conditions before other flaws represents a bias towards early commitment of parameter bindings. This resembles the search strategy inherent in planners using ground actions, but without necessarily committing to bindings for all parameters of an action at once. The gain is a reduced branching factor compared to a planner using ground actions, and this reduction can compensate for the increased complexity that comes with having to keep track of variable bindings.

Our earlier results (Younes & Simmons, 2002) indicated that despite a reduction in the number of generated plans when planning with lifted actions, using ground actions was still faster in most domains. In the gripper domain, for example, while using lifted actions resulted in less than half the number of generated plans compared to when using ground actions, planning with ground actions was still more than twice as fast. We have greatly improved the implementation of the planner and the handling of variable bindings since then. When using the latest version of VHPOP in the gripper domain, the planner is roughly as fast when planning with lifted actions giving priority to static preconditions as when planning with ground actions.