Exploiting procedural domain control knowledge in state-of-the-art planners

Abstract

Domain control knowledge (DCK) has proven effective in improving the efficiency of plan generation by reducing the search space for a plan. Procedural DCK is a compelling type of DCK that supports a natural specification of the skele-ton of a plan. Unfortunately, most state-of-the-art planners do not have the machinery necessary to exploit procedural DCK. To resolve this deficiency, we propose to compile procedural DCK directly into PDDL2.1, thus enabling any PDDL2.1-compatible planner to exploit it. The contribution of this pa-per is threefold. First, we propose a PDDL-based seman-tics for an Algol-like, procedural language that can be used to specify DCK in planning. Second, we provide a polyno-mial algorithm that translates an ADL planning instance and a DCK program, into an equivalent, program-free PDDL2.1 instance whose plans are only those that adhere to the pro-gram. Third, we argue that the resulting planning instance is well-suited to being solved by domain-independent heuris-tic planners. To this end, we propose three approaches to computing domain-independent heuristics for our translated instances, sometimes leveraging properties of our translation to guide search. In our experiments on familiar PDDL plan-ning benchmarks we show that the proposed compilation of procedural DCK can significantly speed up the performance of a heuristic search planner. Our translators are implemented and available on the web.