Heuristic search for target-value path problem

In this paper, we introduce a new class of search problems in which the objective is to find a path whose total cost is as close as possible to a target cost, called the ideal cost. As a result, we refer to these problems as ideal-cost path problems, which do not fit well with any of the existing optimization criteria used with A*. We show that, with appropriate extensions, A* can handle this new type of cost function. It is worth noting that the classic shortest (or least-cost) path problems can be formalized as ideal-cost path problems for which the cost ideal is zero. Thus, this new class contains the traditional shortest-path problems as special cases.

Citation

Kuhn, L.; Price, R.; Zhou, R.; Do, M. B. Heuristic search for target-value path problem. First International Symposium on Search Techniques in Artificial Intelligence and Robotics; 2008 July 13-14; Chicago, IL.