Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal
Leah Chrestien, Stefan Edelkamp, Antonin Komenda, Tomáš Pevný
Abstract
In imitation learning for planning, parameters of heuristic functions are optimized against a set of solved problem instances. This work revisits the necessary and sufficient conditions of strictly optimally efficient heuristics for forward search algorithms, mainly A* and greedy best-first search, which expand only states on the returned optimal path. It then proposes a family of loss functions based on ranking tailored for a given variant of the forward search algorithm. Furthermore, from a learning theory point of view, it discusses why optimizing cost-to-goal h* is unnecessarily difficult. The experimental comparison on a diverse set of problems unequivocally supports the derived theory.
BibTeX
@inproceedings{
chrestien2023optimize,
title={Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal},
author={Leah Chrestien and Stefan Edelkamp and Antonin Komenda and Tom{\'a}{\v{s}} Pevn{\'y}},
booktitle={Thirty-seventh Conference on Neural Information Processing Systems},
year={2023},
url={https://openreview.net/forum?id=Mgy6sgslPY}
}