O'Reilly logo

GPU Computing Gems Jade Edition by Wen-mei W. Hwu

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 22

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required