Cost-optimal planning is a variant of a general planning problem, where all actions have non-negative costs, and the solution is a valid plan that minimizes the sum of the costs of all actions included in the plan. In this paper, we propose a new planning problem formulation, top-k planning, which is a generalization of cost-optimal planning with applications in plan recognition, diagnosis, explanation generation, and other domains. No existing planners can solve this problem out of the box. We have implemented and compared a total of four new planning algorithms for top-k planning. Two of the algorithms are based on the k shortest paths algorithm by Eppstein and a recently proposed variant of that algorithm for dynamic graphs called K , by Aljazzar and Leue. We also implemented a branch and bound algorithm, and an iterative replanning algorithm based on LAMA. Our experiments show that the top-k planning problem can be solved efficiently, in time comparable to cost-optimal planning. We also show that our implementation of top-k planning based on the K algorithm outperforms other algorithms.
By: Anton V. Riabov, Shirin Sohrabi, Octavian Udrea
Published in: RC25463 in 2014
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .