A depth-first approach to target-value search

Details

Event International Symposium on Combinatorial Search (SoCS)

Authors

Tim Schmidt
Kuhn, Lukas
Zhou, Rong
Technical Publications
July 8th 2009
In this paper, we consider how to improve the scalability and efficiency of target-value-path search on directed acyclic graphs. To this end, we introduce a depth-first heuristic search algorithm and a dynamic-programming method to compute the heuristic's pattern database in linear (in the number of edges) time. We show the benefits of the new approach over previous work on this problem (c.f. Kuhn et al. "Heuristic search for the target-value problem."

Citation

Schmidt, T.; Zhou, R.; de Kleer, J.; Price, R.; Kuhn, L. A depth-first approach to target-value search. International Symposium on Combinatorial Search (SoCS 2009); 2009 July 8-10; Lake Arrowhead, CA.

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