Marco Baioletti, Stefano Marcugini, and Alfredo Milani
The most efficient planning algorithms recently developed are mainly ased on Graphplan system or on satfi is ability approach. In this paper e present a new approach to plan generation based on planning graph analysis, which can be considered as a bridge between the two planning approaches. The method exploits the propagation of planning axioms and vonstraints 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. he experimental results obtained with DP-Plan, a planner implementing he 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 strong connection with the planning problem allowing the development of search strategies which incorporate domain dependent heuristics. Moreover, the typical SAT techniques, such as stochastic and incomplete strategies, can easily be transferred and integrated in this framework.