Least commitment in Graphplan Original Research Article

Planners of the Graphplan family (Graphplan, IPP, STAN,…) are currently considered 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 detailed formal analysis that demonstrates that the independence criterion can be partially relaxed in order to produce valid plans in the sense of Graphplan. Indeed, two actions at a same level of the planning-graph do not need to be marked as mutually exclusive if there exists a possible ordering between 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 solution plan needs an extra checking process that guarantees that an ordering can be found for actions considered simultaneously, at each level of the planning-graph. This study lead us to implement a modified Graphplan, LCGP (for “Least Committed GraphPlan”), which is still sound and complete and generally produces plans that have fewer levels than those of Graphplan (the same number in the worst cases). We present an experimental study which demonstrates that, in classical planning domains, LCGP solves more problems than planners from the family of Graphplan (Graphplan, IPP, STAN,…). In most cases, LCGP also outperforms the other planners.