A depth-first approach to target-value search

Details

Event International Symposium on Combinatorial Search (SoCS)

Authors

Tim Schmidt

Kuhn, Lukas

Price, Robert

View Profile

de Kleer, Johan

View Profile

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