AAAI Publications, Twenty-Second International Conference on Automated Planning and Scheduling

Font Size: 
Pruning Methods for Optimal Delete-Free Planning
Avitan Gefen, Ronen Brafman

Last modified: 2012-05-14


Delete-free planning underlies many popular relaxation (h+) based heuristics used in state-of-the-art planners; it provides a simpler setting for exploring new pruning methods and other ideas; and a number of interesting recent planning domains are naturally delete-free. In this paper we explore new pruning methods for planning in delete-free planning domains. First, we observe that optimal delete-free plans can be composed from contiguous sub-plans that focus on one fact landmark at a time. Thus, instead of attempting to achieve the goal, the planner can focus on more easily achievable landmarks at each stage. Then, we suggest a number of complementary pruning techniques that are made more powerful with this observation. To carry out these pruning techniques efficiently, we make heavy use of an And/Or graph depicting the planning problem. We empirically evaluate these ideas using the FD framework, and show that they lead to clear improvements.


optimal planning;delete-free;delete-relaxation;landmarks;pruning;A* search;And/Or graphs;directed hyper-graphs

Full Text: PDF