Real-Time Adaptive GPU Multiagent Path Planning
Ugo Erra and Giuseppe Caggianese
This chapter presents a GPU path planning algorithm that is derived from the sequential A* algorithm to allow massively parallel, real-time execution. The new algorithm employs a limited lookahead strategy similar to the wave fronts of a breath-first-search algorithm. Using a heuristic to estimate the most profitable direction for moving along a particular direction at each step, the algorithm strikes a balance between work set size and optimality. The implementation of the algorithm further employs a windowed strategy to reduce the amount of information that needs to be maintained for fast access. We show that the resulting algorithm indeed achieves high ...
Get GPU Computing Gems Jade Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
