Potential Search: A Bounded-Cost Search Algorithm

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.