Heuristic search for target-value path problem

Details

Event AAAI 2008 Search Workshop

Authors

Kuhn, Lukas
Zhou, Rong
Do, Minh B.
Technical Publications
July 13th 2008
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.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

FIND OUT MORE
Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for¬†Commercialization.

FIND OUT MORE
News

PARC scientists and staffers are active members and contributors to the science and technology communities.

FIND OUT MORE