Title :
A path non-existence proof in motion planning using CUDA
Author :
Nowakiewicz, Michal
Author_Institution :
Fac. of Math. & Inf. Sci., Warsaw Univ. of Technol., Warsaw, Poland
Abstract :
We consider a problem of 6DOF rigid body motion planning between static and known obstacles in presence of tight passages. Popular planners, like Probabilistic Roadmap, are not capable of concluding that the solution does not exist. We present a simple and massively parallel method of proving, that a requested motion is not possible. It is based on a regular cell decomposition of the space of rotations and computation of approximated Minkowski sums for each cell. Our main contribution is the proposed method of efficient realization on modern graphics hardware of the following operations: computation of approximated Minkowski sums, identification of connected components in them, identification of adjacency between such components that correspond to different cells. We also present the experimental results for the performance of our implementation.
Keywords :
path planning; probability; 6DOF rigid body motion planning; CUDA; approximated Minkowski sums; cell decomposition; probabilistic roadmap; Arrays; Instruction sets; Joining processes; Level set; Microprocessors; Planning;
Conference_Titel :
Advanced Intelligent Mechatronics (AIM), 2010 IEEE/ASME International Conference on
Conference_Location :
Montreal, ON
Print_ISBN :
978-1-4244-8031-9
DOI :
10.1109/AIM.2010.5695782