Bi-Criteria Diverse Plan Selection via Beam Search Approximation

Abstract

Recent work on diverse planning has focused on a two-step setting where the first step consists of generating a large number of plans, and the second step consists of selecting a subset of plans that maximizes diversity. For the second step, previous work has focused on solving a combinatorial optimization problem for diverse subset selection that can be approximated using greedy search. In this work, we propose a flexible, bi-criteria framework for diverse plan selection. Our framework consists of optimizing both quality and diversity, generalizing previous work and providing flexibility to prioritize one objective over the other. We consider two quality and two diversity measures and show that greedy search guarantees an approximation with a constant ratio for certain configurations based on established results in the literature. To allow users to trade off additional computation for better solutions, we introduce a beam search approximation that generalizes the greedy search, and we provide approximation guarantees on the obtained solutions. Finally, we conduct extensive experiments that show that: (1) our flexible bi-criteria framework allows us to obtain solutions of better quality while still maintaining a high degree of diversity; (2) our beam search approximation obtains significant improvement in performance over greedy search and, for a large number of instances, is able to generate solutions that are equal to or better than those obtained by an exact MIP solver with a significantly higher runtime limit.