Home | Publications | CS Home

Multiple-goal Heuristic Search

---

Dmitry Davidov and Shaul Markovitch. Multiple-goal Heuristic Search. Journal of Artificial Intelligence Research, 26:417-451 2006.

---

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.

---

Keywords: Heuristic Search, Speedup Learning, Focused Crawling, Anytime Algorithms

---

Secondary Keywords:

---

Online version:

---

Bibtex entry:

 @article{Davidov:2006:MGH,
  Author = {Dmitry Davidov and Shaul Markovitch},
  Title = {Multiple-goal Heuristic Search},
  Year = {2006},
  Journal = {Journal of Artificial Intelligence Research},
  Volume = {26},
  Number = {},
  Month = {},
  Pages = {417--451},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Davidov-Markovitch-JAIR2006.pdf},
  Keywords = {Heuristic Search, Speedup Learning, Focused Crawling, Anytime Algorithms},
  Secondary-keywords = {},
  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.
  }

  }