Technical Report No. 88, August 1997 - Abstract

Koehler, J.; Nebel, B.; Hoffmann, J.; Dimopoulos, Y.:
Extending Planning Graphs to an ADL Subset

We describe an extension of Graphplan to a subset of ADL that allows conditional and universally quantified effects in operators. The data structure of planning graphs is extended to cope with the more expressive operators in such a way that most of the interesting properties of the original Graphplan formalism are preserved. A sound and complete planning algorithm extracts plans from planning graphs and terminates on unsolvable problems. A new efficient technique for subset memoization is presented to speed up the planner and we prove that Graphplan's termination test remains complete under subset memoization.