Massively Parallel A* Search on a GPU

Yichao Zhou, Jianyang Zeng
Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, P. R. China
Twenty-Ninth AAAI Conference on Artificial Intelligence(AAAI 2015), 2015


   title={Massively Parallel A* Search on a GPU},

   author={Zhou, Yichao and Zeng, Jianyang},



Download Download (PDF)   View View   Source Source   



A* search is a fundamental topic in artificial intelligence. Recently, the general purpose computation on graphics processing units (GPGPU) has been widely used to accelerate numerous computational tasks. In this paper, we propose the first parallel variant of the A* search algorithm such that the search process of an agent can be accelerated by a single GPU processor in a massively parallel fashion. Our experiments have demonstrated that the GPU-accelerated A* search is efficient in solving multiple real-world search tasks, including combinatorial optimization problems, pathfinding and game solving. Compared to the traditional sequential CPU-based A* implementation, our GPU-based A* algorithm can achieve a significant speedup by up to 45x on large-scale search problems.
Rating: 1.5/5. From 2 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: