DPPlan: an Algorithm for Fast Solutions Extraction from a Planning Graph

The most efficient planning algorithms recently developed are mainly based on Graphplan system or on satisfiability approach. In this paper we present a new approach to plan generation based on planning graph analysis, wich can be considered as a bridge between the two planning approaches. The method exploits the propagation of planning axioms and constraints in order to make deductions on the planning graph and therefore to prune the search space. The consequences of decisions made during search have backward and forward impact on the planning graph. In contrast with Graphplan based backward algorithms our approach allows to search the planning graph without committing to any specific direction. The experimental results obtained with DPPlan, a planner implementing the presented propagation approach by systematic search, are encouraging even if compared with approaches based on SAT. DPPlan has not the huge memory requirements as SAT solvers and keeps a stong connecton with the planning problem allowing the development of search strategies which incorporate domain dependant heuristics. Moreover, the typical SAT techniques, such as stochastic and incomplete strategies, can easily be transfered and integrated in this framework.