Michel Cayrol, Pierre Régnier, and Vincent Vidal
Planners from the family of Graphplan (Graphplan, IPP, STAN...) are presently considered as the most efficient ones on numerous planning domains. Their partially ordered plans can be represented as sequences of sets of simultaneous actions. Using this representation and the criterion of independence, Graphplan constrains the choice of actions in such sets. We demonstrate that this criterion can be partially relaxed in order to produce valid plans in the sense of Graphplan. Our planner LCGP needs fewer levels than Graphplan to generate these plans (the same number in the worst cases). Then we present an experimental study which demonstrates that, in classical planning domains, LCGP "practically" solves more problems than planners from the family of Graphplan (Graphplan, IPP, STAN...). In most cases, these tests demonstrate the best performances of LCGP. Then, we present a domain-independent heuristic for variable and domain ordering. LCGP is thus improved using this heuristic, and compared with HSP-R, a very efficient non-optimal sequential planner, based on an heuristic backward state space search.