Abstract：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.
 LaValle S, Kuffner J. Randomized kinodynamic planning[J]. International Journal of Robotics Research, 2001, 20(5):378-400.
 Jaillet L, Cortes J, Simeon T. Sampling-based path planning on configuration-space costmaps[J]. IEEE Transactions on Robotics, 2010, 26(4):635-646.
 Xie B Y, Zhuo J, Liu Y. Motion planning of reaching point movements for 7R robotic manipulators in obstacle environment based on rapidly-exploring random tree algorithm[J]. Journal of Mechanical Engineering, 2012, 48(3):63-69.
 Latombe J C. Robot motion planning[M]//The Springer International Series in Engineering and Computer Science, vol.124. Berlin, Germany:Springer-Verlag, 2012.
 Saha M, Roughgarden T, Latombe J C, et al. Planning tours of robotic arms among partitioned goals[J]. International Journal of Robotics Research, 2006, 25(3):207-223.
 Isto P, Saha M. A slicing connection strategy for constructing PRMs in high-dimensional cspaces[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA:IEEE, 2006:1249-1254.
 Kannan A, Gupta P, Tiwari R, et al. Robot motion planning using adaptive hybrid sampling in probabilistic roadmaps[J]. Electronics, 2016, 5(2):16-17.
 Schwarzer F, Saha M, Latombe J C. Exact collision checking of robot paths[J]. Springer Tracts in Advanced Robotics, 2004, 7(5):25-41.
 潘佳,Dinesh M.运动规划的高效配置空间构建与优化[J].Engineering,2015,1(1):46-57.Pan J, Dinesh M. Efficient configuration space construction and optimization for motion planning[J]. Engineering, 2015, 1(1):46-57.
 Schwarzer F, Saha M, Latombe J C. Adaptive dynamic collision checking for single and multiple articulated robots in complex environments[J]. IEEE Transactions on Robotics, 2005, 21(3):338-353.
 Larsen E, Gottschalk S, Lin M C, et al. Fast distance queries with rectangular swept sphere volumes[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA:IEEE, 2000:3719-3726.
 Wang H Y, Liu S G. A collision detection algorithm using AABB and octree space division[J]. Advanced Materials Research, 2014, 989(26):2389-2392.
 Canny J. Collision detection for moving polyhedral[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, 8(2):200-209.
 Schweikard A. Polynomial time collision detection for manipulator paths specified by joint motions[J]. IEEE Transactions on Robotics and Automation, 1992, 7(6):865-870.
 Spensieri D, Carlson J S, Ekstedt F, et al. An iterative approach for collision free routing and scheduling in multirobot stations[J]. IEEE Transactions on Automation Science & Engineering, 2015, 13(2):1-13.
 王伟,马峻,刘伟,等.基于OBB包围盒的碰撞检测研究与应用[J].计算机仿真,2009,26(9):180-183.Wang W, Ma J, Liu W, et al. Research and application of collision detection based oriented bounding box[J]. Computer Simulation, 2009, 26(9):180-183.
 Baginski B. Efficient dynamic collision detection using expanded geometry models[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway, USA:IEEE, 1997:1714-1720.
 UNC GAMMA Group. Proximity query packages[EB/OL].[2016-11-13]. http://gamma.cs.unc.edu.
 Welzl E. Smallest enclosing disks (balls and ellipsoids)[M]//New Results and New Trends in Computer Science. Berlin, Germany:Springer-Verlag, 1991:359-370.