Reinforcement Learning with A* and a Deep Heuristic

2018/11/19 by Ariel Keselman, Keselman, Ariel, Sergey Ten +6 · 13 citations
Computer Science · Engineering · Mathematics · #Aleph #Algorithm #Artificial intelligence #Artificial neural network #Autonomous Vehicle Technology and Safety #Computer science #Deep learning #Deep neural networks #FOS: Computer and information sciences #Function (biology) #Heuristic #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine learning #Mathematics #Path (computing) #Reinforcement Learning in Robotics #Reinforcement learning #Robotic Path Planning Algorithms #Star (game theory) #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1811.07745

published in arXiv (Cornell University) (Cornell University) · 6 pages 2 figures

arxiv created 2018/11/19 · openalex publication_date 2018/11/19 · arxiv updated 2018/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A* is a popular path-finding algorithm, but it can only be applied to those domains where a good heuristic function is known. Inspired by recent methods combining Deep Neural Networks (DNNs) and trees, this study demonstrates how to train a heuristic represented by a DNN and combine it with A*. This new algorithm which we call aleph-star can be used efficiently in domains where the input to the heuristic could be processed by a neural network. We compare aleph-star to N-Step Deep Q-Learning (DQN Mnih et al. 2013) in a driving simulation with pixel-based input, and demonstrate significantly better performance in this scenario.

Citations

• Playing Atari with Deep Reinforcement Learning
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Observe and Look Further: Achieving Consistent Performance on Atari
• Exploration by Random Network Distillation

Related

• Pathfinding in Random Partially Observable Environments with Vision-Informed Deep Reinforcement Learning
• End-to-End Deep Reinforcement Learning for Lane Keeping Assist
• Towards Learning Foundation Models for Heuristic Functions to Solve Pathfinding Problems
• Learning to Drive using Inverse Reinforcement Learning and Deep Q-Networks
• DAQN: Deep Auto-encoder and Q-Network