Adaptive Continuous Collision Detection for Linear Segments in High Dimensional Configuration Space

In order to efficiently build the collision-free roadmap, an adaptive continuous collision detection algorithm is proposed to construct the collision-free linear segments in configuration space. Before performing continuous collision detection for the linear segments, the proposed method compares the minimal Euclidean distance of two static objects in a fixed configuration and the maximal displacement distance of specific objects in different configurations, to determine whether or not to bisect the linear segments for fine detection. So, the times of redundant detections are reduced effectively, and the mapping efficiency is improved. The proposed method is demonstrated by planning the collision-free path between the given starting and terminal configurations for a high dimensional robot simulation system. As a result, the computational efficiency of the proposed adaptive collision detection method is 25.1%~84.1% higher than the methods of fixed detection resolution.