Proceedings:
Vol. 21 (2011): Twenty-First International Conference on Automated Planning and Scheduling
Volume
Issue:
Vol. 21 (2011): Twenty-First International Conference on Automated Planning and Scheduling
Track:
Full Technical Papers
Downloads:
Abstract:
In this paper we address the following search task: find a goal with cost smaller than or equal to a given fixed constant. This task is relevant in scenarios where a fixed budget is available to execute a plan and we would like to find such a plan with minimum search effort. We introduce an algorithm called Potential search (PTS) which is specifically designed to solve this problem. PTS is a best-first search that expands nodes according to the probability that they will be part of a plan whose cost is less than or equal to the given budget. We show that it is possible to implement PTS even without explicitly calculating these probabilities, when a heuristic function and knowledge about the error of this heuristic function are given. In addition, we also show that PTS can be modified to an anytime search algorithm. Experimental results show that PTS outperforms other relevant algorithms in most cases, and is more robust.
DOI:
10.1609/icaps.v21i1.13455
ICAPS
Vol. 21 (2011): Twenty-First International Conference on Automated Planning and Scheduling