Least commitment in Graphplan

Planners of the Graphplan family (Graphplan, IPP, STAN,...) are currently c onsidered to be the most efficient ones on numerous planning domains. Their partially ordered plans can be represented as sequences of sets of actions . The sets of actions generated by Graphplan satisfy a strong independence property which allows one to manipulate each set as a whole. We present a d etailed formal analysis that demonstrates that the independence criterion c an be partially relaxed in order to produce valid plans in the sense of Gra phplan. Indeed, two actions at a same level of the planning graph do not ne ed to be marked as mutually exclusive if there exists a possible ordering b etween them that respects a criterion of "authorization", less constrained than the criterion of independence. The ordering between the actions can be set up after the plan has been generated, and the extraction of the soluti on plan needs an extra checking process that guarantees that an ordering ca n be found for actions considered simultaneously, at each level of the plan ning-graph. This study lead us to implement a modified Graphplan, LCGP (for "Least Committed GraphPlan"), which is still sound and complete and genera lly produces plans that have fewer levels than those of Graphplan (the same number in the worst cases). We present an experimental study which demonst rates: that, in classical planning domains, LCGP solves more problems than planners from the family of Graphplan (Graphplan, IPP, STAN,...). In most c ases, LCGP also outperforms the other planners. (C) 2001 Elsevier Science B .V. All rights reserved.