Unifying and Certifying Top-Quality Planning
This work addresses the need for standardized certification in planning tools, which is incremental as it builds on existing transformations and definitions.
The paper tackles the problem of unifying diverse definitions of top-quality planning by proposing a single definition based on dominance relations, enabling certification of solution quality using existing methods and introducing a novel transformation for loopless planning.
The growing utilization of planning tools in practical scenarios has sparked an interest in generating multiple high-quality plans. Consequently, a range of computational problems under the general umbrella of top-quality planning were introduced over a short time period, each with its own definition. In this work, we show that the existing definitions can be unified into one, based on a dominance relation. The different computational problems, therefore, simply correspond to different dominance relations. Given the unified definition, we can now certify the top-quality of the solutions, leveraging existing certification of unsolvability and optimality. We show that task transformations found in the existing literature can be employed for the efficient certification of various top-quality planning problems and propose a novel transformation to efficiently certify loopless top-quality planning.