טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDavidov Dmitry
SubjectMultiple-Goal Heuristic Search Algorithms
DepartmentDepartment of Computer Science
Supervisor Professor Shaul Markovitch


Abstract

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.