Learning Heuristic Functions Through Approximate Linear Programming

Marek Petrik, Shlomo Zilberstein

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.

URL: http://cs.umass.edu/~petrik/pub/Petrik2008b.pdf

Subjects: 15.7 Search; 12.1 Reinforcement Learning

Submitted: Jun 25, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.