On the compilation of plan constraints and preferences

Abstract

State trajectory and preference constraints are the two language features introduced in PDDL3 (Gerevini & Long 2005) for describing benchmarks of the 5th inter-national planning competition. In this work we make existing solver technology applicable to planning with PDDL3 domains by compiling the new constructs back to PDDL2 (Fox & Long 2003). State trajectory constraints are translated into LTL for-mulae and further to Büchi automata, one for each constraint. These automata are compiled to grounded PDDL and the results are merged with the grounded representation of the original problem. Preference con-straints are compiled away using numerical state vari-ables. We provide encouraging experimental results in heuristic search planning. State Trajectory Constraints State trajectory constraints provide an important step of the agreed fragment of PDDL towards the descrip-tion of temporal control knowledge (Bacchus & Kabanza 2000) and temporally extended goals (DeGiacomo & Vardi 1999). In the proposed translation, we compile state trajectory constraints to LTL formulae and Büchi automata (Clarke, Grumberg, & Peled 2000). All plans are finite, so that we can cast the Büchi automaton as an NFA, which accepts a word if it ter-minates in a final state. The labels of the NFA are con-ditions over the propositions and variables in a given state. For example, the constraint a fragile block can never have something above it in the Blocksworld do-main is expressed as (always (forall (?b- block) (implies (fragile?b) (clear?b)) The instantiated LTL formula for two blocks a and b is [] ((fragile_a-> clear_a) && (fragile_b-> clear_b))