Bounding Quality in Diverse Planning

Diverse planning is an important problem in automated planning with various real world applications. Recently, diverse planning has seen renewed interest, with work that defines a taxonomy of computational problems with respect to both plan quality and solution diversity. However, despite the recent advances in diverse planning the variety of approaches and the number of available tools for these problems are still quite limited, even nonexistent for several computational problems. In this work, we aim to extend the portfolio of approaches and tools for various computational problems in diverse planning. To that end, we introduce a novel approach to finding solutions for three computational problems within diverse planning and present planners for these three problems. For one of these problems, our approach is the first one that is able to provide solutions to the problem. For another, we show that top-k and top quality planners can provide, albeit naive, solutions to the problem and we extend these planners to improve the diversity of the obtained solution. Finally, for the third problem, we show that some existing diverse planners already provide solutions to the problem. Further, we suggest another approach and empirically show that our suggested approach compares favorably with these existing planners.