Domain-Dependent Constraint Planning in the Graphplan Framework

摘要

Graphplan has enjoyed considerable success as a planning algorithm for classical STRIPS domains in the past few years, and many efficient planning systems are based on it. The paper contributes a new graphplan algorithm called Domain-Dependent Constraint Graphplan (DCGraphplan), which combines the Graphplan algorithm with domain-dependent knowledge to solve the more complex planning problems. DCGraphplan introduces additional mutex relations from constraint operators in the planning graph. The constraint-operators "deduce" additional domain knowledge defined by constraint stratifications. In addition, DCGraphplan exploits certain heuristics when extracting a plan from the planning graph. The approach is experimentally verified on a blocks-world example where it leads to significant speed-ups.