Learning heuristics for A*
Path finding in graphs is one of the most studied classes of problems in computer science. In this context, search algorithms are often extended with heuristics for a more efficient search of target nodes. In this work we combine recent advancements in Neural Algorithmic Reasoning to learn efficient heuristic functions for path finding problems on graphs. At training time, we exploit multi-task learning to learn jointly the Dijkstra's algorithm and a consistent heuristic function for the A* search algorithm. At inference time, we plug our learnt heuristics into the A* algorithm. Results show that running A* over the learnt heuristics value can greatly speed up target node searching compared to Dijkstra, while still finding minimal-cost paths.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Task LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Inductive Learning of Declarative Domain-Specific Heuristics for ASP
Domain-specific heuristics are a crucial technique for the efficient solving of problems that are large or computationally hard. Answer Set Programming (ASP) systems support declarative specifications of domain-specific …
Inductive LearningInductive logic programmingLearning Robust Search Strategies Using a Bandit-Based Approach
Effective solving of constraint problems often requires choosing good or specific search heuristics. However, choosing or designing a good search heuristic is non-trivial and is often a manual process. In this paper, rat…
Correlation Heuristics for Constraint Programming
Effective general-purpose search strategies are an important component in Constraint Programming. We introduce a new idea, namely, using correlations between variables to guide search. Variable correlations are measured …
Beyond the Hype: Benchmarking LLM-Evolved Heuristics for Bin Packing
Coupling Large Language Models (LLMs) with Evolutionary Algorithms has recently shown significant promise as a technique to design new heuristics that outperform existing methods, particularly in the field of combinatori…
BenchmarkingEvolutionary AlgorithmsLearning 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…