GPU Acceleration Techniques Integrated Into OneSAF

Route Planning

The problem of route planning over a complex terrain has been studied for many years. The topic has received considerable attention largely due to the high computational complexity associated with it. Good solutions to route planning have applications in many areas, including autonomous navigation or planning among collaborating agents. We present a method for accelerating route planning for computer generated forces (CGF) that utilizes graphics processing units (GPUs). GPUs have become an integral part of many commodity PC systems and gaming consoles. Additionally, GPU performance has been increasing at a faster rate than that of their CPU counterparts. For nongraphics- intensive applications such as route planning, the GPU represents a computational resource in addition to the CPU.

Our algorithm tackles the feature intersection problem, a bottleneck in route planning systems. The algorithm exploits the parallel computing capability of GPUs along with their ability to perform visibility culling. We then combine the GPU accelerated computations with exact intersection tests on the CPU. This approach supports dynamic terrains as well as planning multiple routes in parallel. The method is able to perform feature intersection tests in a few microseconds on a commodity PC.

Overview of GPU-Accelerated Route Planning

Ability to test multiple route segments in parallel

Queries all potential segments faster than individually testing on the CPU

More efficient search of the large planning space

System integrated with OneSAF

Demonstrated 30-50x speedup in feature analysis computation

Demonstrated 10x speed up of route planning in OneSAF on a single CPU-GPU machine

Figure 1: Our GPU-based culling algorithm proceeds in three phases. First, non-intersecting segments are pruned. Second, non-intersecting features are pruned. Third, potentially intersecting features are paired with segments.

Figure 2: The terrain features of the environment are rendered once into the depth buffer. We then cull the segment sets against the features set to reduce the segments. Next we cull the feature set against the segment set to reduce the features. Finally we cull the reduced features set against individual segments.

Figure 3: The route generated avoids the obstacles.

©2003 Department of Computer Science, UNC Chapel Hill