Heuristic Search for Target Value Path Problem

Lukas Kuhn, Tim Schmidt, Bob Price, Johan de Kleer, Rong Zhou, Minh Do

In this paper, we define a class of combinatorial search problems in which the objective is to find a set of paths in a graph whose elements' value is as close as possible to some target value. Unlike the usual shortest path problem, the goal is not necessarily to find paths with minimum length. We show that in most cases it is possible to decompose the problem into components where heuristic search can be used. We demonstrate the benefits of this approach on a synthetic domain and illustrate an instantiation of the approach for a problem in model-based diagnosis.

Subjects: 15.7 Search; 1.5 Diagnosis

Submitted: May 5, 2008


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.