Some Orders Are Important: Partially Preserving Orders in Top-Quality Planning
This work addresses the need for flexibility in plan selection for real-life planning applications, though it is incremental as it builds on existing top-quality planning methods.
The paper tackles the problem of generating multiple top-cost plans in planning applications by introducing a method to specify which action orders are important, interpolating between fully ordered and unordered planning. Experimental evaluations show benefits from adapting partial order reduction search pruning techniques to this new setting.
The ability to generate multiple plans is central to using planning in real-life applications. Top-quality planners generate sets of such top-cost plans, allowing flexibility in determining equivalent ones. In terms of the order between actions in a plan, the literature only considers two extremes -- either all orders are important, making each plan unique, or all orders are unimportant, treating two plans differing only in the order of actions as equivalent. To allow flexibility in selecting important orders, we propose specifying a subset of actions the orders between which are important, interpolating between the top-quality and unordered top-quality planning problems. We explore the ways of adapting partial order reduction search pruning techniques to address this new computational problem and present experimental evaluations demonstrating the benefits of exploiting such techniques in this setting.