|M.Sc Student||Davidov Dmitry|
|Subject||Multiple-Goal Heuristic Search Algorithms|
|Department||Department of Computer Science||Supervisor||Professor Shaul Markovitch|
The work described in this thesis presents a new framework for heuristic search where the task is to collect as many goals as possible within the allocated resources.
We show the inadequacy of traditional distance-estimation heuristics for tasks of this type and describe a new set of heuristics that are better suited for multiple-goal search.
In particular, we introduce the marginal-utility heuristic, which considers the expected costs as well as the expected benefits associated with each search direction. Designing an effective marginal-utility heuristic is a rather difficult task. We therefore developed two methods for online learning of marginal-utility heuristics. One is based on local similarity of the partial marginal utility of sibling nodes. It estimates the marginal utility of a node based on the average partial marginal utility of its siblings. The other method generalizes marginal-utility over the state feature space. It uses an induction algorithm to infer a classifier for identifying nodes with high marginal utility.
We apply our adaptive and non-adaptive multiple-goal search algorithms to several problems, including focused crawling, and show their efficiency. The framework described in this thesis opens a new research direction. The field is wide open for the development of new algorithms and for the application of multiple-goal search algorithms to other tasks.