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

2023/10/30 by Chrestien, Leah, Pevný, Tomás, Edelkamp, Stefan +1 · 2 citations
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2310.19463

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 \hstar is unnecessarily difficult. The experimental comparison on a diverse set of problems unequivocally supports the derived theory.

Cited by

• GammaZero: Learning To Guide POMDP Belief Space Search With Graph Representations
• Learning Admissible Heuristics for A*: Theory and Practice

Related

• Learning Search-Space Specific Heuristics Using Neural Networks
• Heuristic Search Planning with Deep Neural Networks using Imitation, Attention and Curriculum Learning
• Learning Heuristic Selection with Dynamic Algorithm Configuration
• Learning Classical Planning Strategies with Policy Gradient
• A Differentiable Loss Function for Learning Heuristics in A*