Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal

Understand

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 \hstar\ is unnecessarily difficult.