C.A. Micchelli, W.L. Miranker
Journal of the ACM
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.
C.A. Micchelli, W.L. Miranker
Journal of the ACM
Saurabh Paul, Christos Boutsidis, et al.
JMLR
Joxan Jaffar
Journal of the ACM
Cristina Cornelio, Judy Goldsmith, et al.
JAIR