K∗ Search over Orbit Space for Top-k Planning

K∗ Search over Orbit Space for Top-k Planning

Michael Katz, Junkyu Lee

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 5368-5376. https://doi.org/10.24963/ijcai.2023/596

Top-k planning, the task of finding k top-cost plans, is a key formalism for many planning applications and K* search is a well-established approach to top-k planning. The algorithm iteratively runs A* search and Eppstein’s algorithm until a sufficient number of plans is found. The performance of K* algorithm is therefore inherently limited by the performance of A*, and in order to improve K* performance, that of A* must be improved. In cost-optimal planning, orbit space search improves A* performance by exploiting symmetry pruning, essentially performing A* in the orbit space instead of state space. In this work, we take a similar approach to top-k planning. We show theoretical equivalence between the goal paths in the state space and in the orbit space, allowing to perform K* search in the orbit space instead, reconstructing plans from the found paths in the orbit space. We prove that our algorithm is sound and complete for top-k planning and empirically show it to achieve state-of-the-art performance, overtaking all existing to date top-k planners. The code is available at https://github.com/IBM/kstar.
Keywords:
Planning and Scheduling: PS: Search in planning and scheduling
Planning and Scheduling: PS: Planning algorithms
Planning and Scheduling: PS: Theoretical foundations of planning