Multiple-Goal Heuristic Search
  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.
