Learning Heuristic Functions Through Approximate Linear Programming

Marek Petrik and Shlomo Zilberstein. Learning Heuristic Functions Through Approximate Linear Programming. Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 248-255, Sydney, Australia, 2008.

Abstract

Planning problems are often formulated as heuristic search. The choice of the heuristic function plays a significant role in the performance of planning systems, but a good heuristic is not always available. We propose a new approach to learning heuristic functions from previously solved problem instances in a given domain. Our approach is based on approximate linear programming, commonly used in reinforcement learning. We show that our approach can be used effectively to learn admissible heuristic estimates and provide an analysis of the accuracy of the heuristic. When applied to common heuristic search problems, this approach reliably produces good heuristic functions.

Bibtex entry:

@inproceedings{PZicaps08,
  author	= {Marek Petrik and Shlomo Zilberstein},
  title		= {Learning Heuristic Functions Through Approximate Linear
                   Programming},
  booktitle     = {Proceedings of the International Conference on Automated
                   Planning and Scheduling},
  year		= {2008},
  pages		= {248-255},
  address       = {Sydney, Australia},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/PZicaps08.html}
}

shlomo@cs.umass.edu