Multiple-Goal Heuristic Search

Abstract

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.