Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal
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.
Code (1)
Similar Papers 제목 키워드 기반
Direction Informed Trees (DIT*): Optimal Path Planning via Direction Filter and Direction Cost Heuristic
Optimal path planning requires finding a series of feasible states from the starting point to the goal to optimize objectives. Popular path planning algorithms, such as Effort Informed Trees (EIT*), employ effort heurist…
Learning Domain-Independent Planning Heuristics with Hypergraph Networks
We present the first approach capable of learning domain-independent planning heuristics entirely from scratch. The heuristics we learn map the hypergraph representation of the delete-relaxation of the planning problem a…
Learning to Rank for Synthesizing Planning Heuristics
We investigate learning heuristics for domain-specific planning. Prior work framed learning a heuristic as an ordinary regression problem. However, in a greedy best-first search, the ordering of states induced by a heuri…
Learning-To-RankregressionMatheuristics to optimize refueling and maintenance planning of nuclear power plants
Planning the maintenance of nuclear power plants is a complex optimization problem, involving a joint optimization of maintenance dates, fuel constraints and power production decisions. This paper investigates Mixed Inte…
Machine Learning Based Path Planning for Improved Rover Navigation (Pre-Print Version)
Enhanced AutoNav (ENav), the baseline surface navigation software for NASA's Perseverance rover, sorts a list of candidate paths for the rover to traverse, then uses the Approximate Clearance Evaluation (ACE) algorithm t…
BIG-bench Machine Learning