{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:28:03Z","timestamp":1756992483392},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SOCS"],"abstract":"<jats:p>Finding multiple high-quality plans is essential in many planning applications, and top-k planning asks for finding the k best plans, naturally extending cost-optimal classical planning. Several attempts have been made to formulate top-k classical planning as a k-shortest paths finding problem and apply K* search, which alternates between A* and Eppstein's algorithm. However, earlier work had shortcomings, among which were failing to handle inconsistent heuristics and degraded performance in Eppstein's algorithm implementations. As a result, existing evaluation results severely underrate the performance of the K* based approach to top-k planning. In this paper, we present a new top-k planner based on a novel variant of 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 the 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 face of imposed task reformulation. Empirical evaluation results show that the proposed approach achieves the state-of-the-art performance on the classical planning benchmarks. The code is available at https:\/\/github.com\/IBM\/kstar.<\/jats:p>","DOI":"10.1609\/socs.v16i1.27281","type":"journal-article","created":{"date-parts":[[2023,7,2]],"date-time":"2023-07-02T07:25:57Z","timestamp":1688282757000},"page":"38-46","source":"Crossref","is-referenced-by-count":1,"title":["On K* Search for Top-K Planning"],"prefix":"10.1609","volume":"16","author":[{"given":"Junkyu","family":"Lee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shirin","family":"Sohrabi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9382","published-online":{"date-parts":[[2023,7,2]]},"container-title":["Proceedings of the International Symposium on Combinatorial Search"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/download\/27281\/27054","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/download\/27281\/27054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,2]],"date-time":"2023-07-02T07:25:57Z","timestamp":1688282757000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/view\/27281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,2]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,7,2]]}},"URL":"https:\/\/doi.org\/10.1609\/socs.v16i1.27281","relation":{},"ISSN":["2832-9163","2832-9171"],"issn-type":[{"value":"2832-9163","type":"electronic"},{"value":"2832-9171","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7,2]]}}}