Encoding Planning Constraints into Partial Order Planning Domains
Marco Baioletti, Alfredo Milani, Stefano Marcugini · 1998
This paper presents a technique for encoding the representation of a constrained planning problem through the generation of an equivalent unconstrained planning problem. In many real situations the initial state/goals characterization of a planning problem is not satisfactory, this motivates the notion of a constrained planning problem, i.e. a planning problem for which the user specifies additional constraints on the problem solution in order to: give a limit to the length of the solution plan, use or avoid specific action instances, use particular strategies in adding steps or precedence constraints to the plan, reach some intermediate states. A common way to implement constrained planning is modifying the existing planner in order to take into account of the user additional constraints. In this paper we present a planner independent approach, which operates on the problem and constraints representation instead of modifying the planning algorithm. A planning constraint description language (PCDL) is therefore introduced. It is shown that a significant subset of PCDL can be encoded by modifying (domain preprocessing phase) the planning domain and goals. The original problem can then be solved by submitting the modified problem to the planner. The solutions to the modified problem defined by the new domain correspond (solution postprocessing phase) to the solutions of the original constrained problem. A significant result is that domain preprocessing phase has a linear time/space cost in the domain and additional constraints dimensions, and the solution postprocessing phase has also linear cost on the solution length. A theoretical consequence of the equivalence result is that representation of constraints and strategies does not ...