PDF | PostScript | doi:10.1613/jair.1940
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.
