Multiple-Goal Heuristic Search

Main Article Content

D. Davidov
S. Markovitch


This paper presents a new framework for anytime heuristic search

where the task is to achieve as many goals as possible within the

allocated resources. We show the inadequacy of traditional

distance-estimation heuristics for tasks of this type and present

alternative heuristics that are more appropriate for multiple-goal

search. In particular, we introduce the marginal-utility

heuristic, which estimates the cost and the benefit of exploring a

subtree below a search node. We developed two methods for online

learning of the marginal-utility heuristic. One is based on local

similarity of the partial marginal utility of sibling nodes, and

the other generalizes marginal-utility over the state feature

space. We apply our adaptive and non-adaptive multiple-goal search

algorithms to several problems, including focused crawling, and

show their superiority over existing methods.

Article Details