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

Font Size: 
Under-Approximation Refinement for Classical Planning
Manuel Heusner, Martin Wehrle, Florian Pommerening, Malte Helmert

Last modified: 2014-05-11


A general and important problem of search-based planning techniques is the state explosion problem, which is usually tackled with approaches to reduce the branching factor of the planning task. Such approaches often implicitly exploit the observation that the number of available operators is higher than the number of operators that are actually needed to find a plan. In this paper, we propose a simple, but general under-approximation refinement framework for satisficing planning that explicitly exploits this observation. Our approach iteratively searches for plans with operator subsets, which are refined if necessary by adding operators that appear to be needed. Our evaluation shows that even a straight-forward instantiation of this framework yields a competitive planner that often finds plans with small operator sets.

Full Text: PDF