Real-time swept volume and distance computation for self collision detection

We present a real-time self collision detection algorithm applicable for industrial and humanoid robots. The algorithm is based on computing the swept volumes of all bodies and checking them pairwise for collisions. The algorithm operates on joint angle intervals. Such, it does not only test a single or N intermediate configurations but assures safety of a whole movement. Key idea of the new swept volume computation is representing volumes as convex hulls extended by a buffer radius, so called sphere swept convex hulls (SSCH). This leads to tight and compact bounding volumes. The operation set available to model the different joints is strictly conservative and allows for a trade-off between accuracy and computation time. During a configurable timespan the algorithm updates a table of pairwise distances and thus can guarantee hard real-time. It is applied on DLR's humanoid Justin in a sports robotic scenario, where also accuracy and computational performance is evaluated (0.4ms, INTEL T2500@2GHz).