We present parallel algorithms to accelerate collision queries for sample-based motion planning. Our approach is designed for current many-core GPUs and exploits data-parallelism and multi-threaded capabilities. In order to take advantage of the high number of cores, we present a clustering scheme and collision-packet traversal to perform efficient collision queries on multiple configurations simultaneously. Furthermore, we present a hierarchical traversal scheme that performs workload balancing for high parallel efficiency. We have implemented our algorithms on commodity NVIDIA GPUs using CUDA and can perform 500, 000 collision queries per second with our benchmarks, which is 10 times faster than prior GPU-based techniques. Moreover, we can compute collision-free paths for rigid and articulated models in less than 100 ms for many benchmarks, almost 50–100 times faster than current CPU-based PRM planners.
AilaTLaineS (2009) Understanding the efficiency of ray traversal on GPUs. In Proceedings of High Performance Graphics, 145–149.
2.
AkincMBekrisKEChenBYLaddAMPlakuEKavrakiLE (2005) Probabilistic roadmaps of trees for parallel computation of multiple query roadmaps. In Robotics Research, vol. 15 of Springer Tracts in Advanced Robotics. Springer, 80–89.
3.
AmatoNDaleL (1999) Probabilistic roadmap methods are embarrassingly parallel. In International Conference on Robotics and Automation, 688–694.
4.
BanerjeeAGhoshJ (2006) Scalable clustering algorithms with balancing constraints. Data Mining and Knowledge Discovery13(3): 365–395.
5.
BarraquandJLatombeJ-C (1991) Robot motion planning: A distributed representation approach. International Journal of Robotics Research10: 6.
6.
CheSBoyerMMengJTarjanDSheafferJWSkadronK (2008) A performance study of general-purpose applications on graphics processors using CUDA. Journal of Parallel and Distributed Computing68(10): 1370–1380.
7.
FoskeyMGarberMLinMManochaD (2001) A Voronoi-based hybrid planner. In Proceedings of IEEE International Conference on Intelligent Robots and Systems, 55–60.
8.
GuntherJPopovSSeidelH-PSlusallekP (2007) Realtime ray tracing on GPU with BVH-based packet traversal. In Proceedings of IEEE Symposium on Interactive Ray Tracing, 113–118.
9.
HarrisM (2009) Optimizing Parallel Reduction in CUDA. NVIDIA Developer Technology.
10.
HoffKCulverTKeyserJLinMManochaD (2000) Interactive motion planning using hardware accelerated computation of generalized Voronoi diagrams. In Proceedings of IEEE International Conference on Robotics and Automation, 2931–2937.
11.
JáJáJ (1992) An Introduction to Parallel Algorithms. Addison Wesley Longman Publishing Co., Inc.
12.
KavrakiLSvestkaPLatombeJCOvermarsM (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation12(4): 566–580.
13.
KimDHeoJ-PHuhJKimJYoonS-E (2009) HPCCD: Hybrid parallel continuous collision detection using CPUs and GPUs. Computer Graphics Forum28(7): 1791–1800.
14.
KuffnerJLaValleS (2000) RRT-connect: An efficient approach to single-query path planning. In Proceedings of IEEE International Conference on Robotics and Automation, 995–1001.
15.
LarsenEGottschalkSLinMManochaD (2000) Distance queries with rectangular swept sphere volumes. In Proceedings of IEEE International Conference on Robotics and Automation, 3719–3726.
16.
LauterbachCGarlandMSenguptaSLuebkeDManochaD (2009) Fast BVH construction on GPUs. Computer Graphics Forum28(2): 375–384.
17.
LauterbachCMoQManochaD (2010) gProximity: Hierarchical GPU-based operations for collision and distance queries. Computer Graphics Forum29(2): 419–428.
18.
LaValleSM (2006) Planning Algorithms. Cambridge University Press.
19.
LinMManochaD (2004) Collision and proximity queries. In Handbook of Discrete and Computational Geometry. CRC Press, Inc., 787–808.
20.
LindholmENickollsJObermanSMontrymJ (2008) NVIDIA Tesla: A unified graphics and computing architecture. IEEE Micro28(2): 39–55.
21.
Lozano-PerezTO’DonnellP (1991) Parallel robot motion planning. In Proceedings of IEEE International Conference on Robotics and Automation, 1000–1007.
22.
OwensJDLuebkeDGovindarajuNHarrisMKrügerJLefohnAEPurcellT (2007) A survey of general-purpose computation on graphics hardware. Computer Graphics Forum26(1): 80–113.
23.
PanJManochaD (2011) GPU-based parallel collision detection for real-time motion planning. In Algorithmic Foundations of Robotics IX, vol. 68 of Springer Tracts in Advanced Robotics. Springer, 211–228.
24.
PanJLauterbachCManochaD (2010a) Efficient nearest-neighbor computation for GPU-based motion planning. In Proceedings of IEEE International Conference on Intelligent Robots and Systems, 2243–2248.
25.
PanJLauterbachCManochaD (2010b) g-Planner: Real-time motion planning and global navigation using GPUs. In Proceedings of AAAI Conference on Artificial Intelligence, 1245–1251.
26.
PisulaCHoffKLinMCManochaD (2000) Randomized path planning for a rigid body based on hardware accelerated Voronoi sampling. In Proceedings of International Workshop on Algorithmic Foundation of Robotics, 279–292.
27.
PlakuEBekrisKEKavrakiLE (2007) Oops for motion planning: An online open-source programming system. In Proceedings of IEEE International Conference on Robotics and Automation, 3711–3716.
28.
SudAAndersenECurtisSLinMManochaD (2007) Real-time path planning for virtual agents in dynamic environments. In Proceedings of IEEE Virtual Reality, 91–98.
29.
TalamadupulaKBentonJSchermerhornP (2009) Integrating a closed world planner with an open world. In Proceedings of ICAPS Workshop on Bridging the Gap Between Task and Motion Planning.
TzengSWeiL-Y (2008) Parallel white noise generation on a GPU via cryptographic hash. In Proceedings of the Symposium on Interactive 3D Graphics and Games, 79–87.
32.
ZhangLManochaD (2008) A retraction-based RRT planner. In Proceedings of IEEE International Conference on Robotics and Automation, 3743–3750.
