Parallel Hierarchical A* for Multi Agent-Based Simulation on the GPU

In this work, we describe a Parallel Hierarchical A* (PHA*) for path-finding in real-time using the Graphics Processor Units (GPUs). The technique aims to find potential paths for many hundreds of agents by building an abstraction graph of the input map in an off-line phase and then using this representation to speed up the path-finding during the on-line phase. The approach is appropriate in the case of scenarios based on grid maps and is independent on a specific obstacle configurations. In addition, we propose also a strategy to obtain smooth paths during the search. We show that this approach fits well with the programming model of the GPUs, enabling searching for many hundreds of agents in parallel in real-time applications such as simulations. The paper describes this implementation using the Compute Unified Device Architecture programming environment, and demonstrates its advantages in terms of performance and quality of the paths founded comparing PHA* with a GPUs implementation of Real-Time Adaptive A* and the classic A* algorithm.