Learning to Combine Admissible Heuristics Under Bounded Time

Carmel Domshlak, Erez Karpas and Shaul Markovitch. Learning to Combine Admissible Heuristics Under Bounded Time. In Proceedings of the ICAPS 2009 Workshop on Planning and Learning, Thessaloniki, Greece, 2009.

Abstract

Usually, combining admissible heuristics for optimal search (e.g. by using their maximum) requires computing numerous heuristic estimates at each state. In many cases, the cost of computing these heuristic estimates outweighs the benefit in the reduced number of expanded states. If only state expan- sions are considered, this is a good option. However, if time is of the essence, we can do better than that. We propose a novel method that reduces the cost of combining admissible heuristics for optimal planning, while maintaining its bene- fits. We first describe a simplified model for deciding which heuristic is best to compute at each state. We then formulate an active learning approach to decide which heuristic to com- pute at each state, online, during search. The resulting tech- nique, which we call selective max is evaluated empirically, and is shown to outperform each of the individual heuristics that were used, as well as their regular maximum, in terms of number of solved instances and average solution time.

Keywords: Planning, Speedup Learning, Anytime Algorithms

Secondary Keywords:

Online version:

Bibtex entry:

 @inproceedings{Domshlak:2009:LCA,
  Author = {Carmel Domshlak and Erez Karpas and Shaul Markovitch},
  Title = {Learning to Combine Admissible Heuristics Under Bounded Time},
  Year = {2009},
  Booktitle = {Proceedings of the ICAPS 2009 Workshop on Planning and Learning},
  Address = {Thessaloniki, Greece},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Karpas-Domshlak-Markovitch-ICAPS2009ws.pdf},
  Keywords = {Planning, Speedup Learning, Anytime Algorithms},
  Abstract = {
    Usually, combining admissible heuristics for optimal search (e.g.
    by using their maximum) requires computing numerous heuristic
    estimates at each state. In many cases, the cost of computing
    these heuristic estimates outweighs the benefit in the reduced
    number of expanded states. If only state expan- sions are
    considered, this is a good option. However, if time is of the
    essence, we can do better than that. We propose a novel method
    that reduces the cost of combining admissible heuristics for
    optimal planning, while maintaining its bene- fits. We first
    describe a simplified model for deciding which heuristic is best
    to compute at each state. We then formulate an active learning
    approach to decide which heuristic to com- pute at each state,
    online, during search. The resulting tech- nique, which we call
    selective max is evaluated empirically, and is shown to outperform
    each of the individual heuristics that were used, as well as their
    regular maximum, in terms of number of solved instances and
    average solution time.
  }

  }