On K* Search for Top-k Planning

Abstract

Finding multiple high-quality plans is essential in many planning applications, and top-k planning asks for finding k best plans, naturally extending cost-optimal classical planning. Several attempts have been made to formulate top-k classical planning as k-shortest paths finding problem and apply K* search, which alternates A* and Eppstein's algorithm. However, earlier work had shortcomings, among which were failure to handle inconsistent heuristics and degraded performance in Eppstein's algorithm. As a result, existing evaluation results severely underrate the performance of the K*-based approach to top-k planning. This paper presents a top-k planner based on a novel variant of the K* search. We address the following three aspects. First, we show an alternative implementation of Eppstein's algorithm for classical planning, which resolves a major bottleneck in earlier attempts. Second, we present a new strategy for alternating A* and Eppstein's algorithm that improves the performance of K* on classical planning benchmarks. Last, we introduce a simple mitigation of the limitation of K* to tasks with a single goal state, allowing us to preserve heuristic informativeness in the face of imposed task reformulation. Empirical evaluation results show that the proposed approach achieves state-of-the-art performance on the classical planning benchmark.