Abstract：To overcome the problem of local extrema existing in iterative closest point(ICP) algorithm when severe occlusions occur,the closest point(CP) rule is modified and dual closest point(DCP) rule is proposed.DCP rule contains twice CP correspondences so that computation complexity is doubled.To decrease the computation complexity,iterative dual closest point based on clustering(IDCP BoC) is proposed.Scan range points are divided into clusters and then a procedure of data reduction is conducted.The reduced data set is used for iterative computation before the error of two consecutive iterations’ residual errors is less than a preset threshold to speed up the algorithm,and the data set without reduction is used after that to guarantee the accuracy.Experimental results show that IDCP BoC can avoid the problem of local extrema effectively and its real-time performance is also acceptable.
 Cox I J.Blanche-An experiment in guidance and navigation of an autonomous robot vehicle[J].IEEE Transactions on Robotics and Automation,1991,7(2):193-204.
 Gutmann J S,Weigel T,Nebel B.A fast,accurate and robust method for self-localization in polygonal environments using laser range finders[J].Advanced Robotics,2001,14(8):651-667.
 Weiss G,Wetzler C,yon Puttkamer E.Keeping track of position and orientation of moving indoor systems by correlation of range-finder scans[C]//IEEE/RSJ/GI International Conference on Intelligent Robots and Systems.Piscataway,NJ,USA:IEEE,1994:595-601.
 Besl P J,McKay N D.A method for registration of 3-13 shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239-256.
 Lu F,Milios E E.Robot pose estimation in unknown environments by matching 2D range scans[J].Journal of Intelligent and Robotic Systems,1997,18(3):249-275.
 杨明,王宏,张钹.基于激光雷达的移动机器人位姿估计方法综述[J].机器人,2002,24(2):177-183.Yang Ming,Wang Hong,Zhang Bo.Overview of laser radar based pose estimation for mobile robots[J].Robot,2002,24(2):177-183.
 Gutmann J S,Schlegel C.AMOS:Comparison of scan matching approaches for self-localization in indoor environments[C]//First Euromicro Workshop on Advanced Mobile Robots.1996:61-67.
 Langis C,Greenspan M,Godin G.The parallel iterative closest point algorithm[C]//Third International Conference on 3-D Digital Imaging and Modeling.Los Aiamitos,CA,USA:IEEE Computer Society,2001:195-202.
 杨明,董斌,王宏,等.基于激光雷达的移动机器人实时位姿估计方法研究[J].自动化学报,2004,30(5):679-687.Yang Ming,Dong Bin,Wang Hong,et al.Research on laser radar based real-time pose estimation for mobile robots[J].Acta Automatic Sinica,2004,30(5):679-687.
 Nuchter A,Lingemann K,Hertzberg J,et al.Cached k-d tree search for ICP algorithms[C]//Sixth International Conference on 3-D Digital Imaging and Modeling.Piscataway,NJ,USA:IEEE,2007:419-426.
 Barnea S,Filin S.Keypoint based autonomous registration of terrestrial laser point-clouds[J].ISPRS Journal of Photogrammetry and Remote Sensing,2008,63(1):19-35.
 Xu Y H,Zhang C W,Bao W,et al.A robust pose estimation algorithm for mobile robot based on clusters[C]//International Conference on Intelligent Robotics and Applications.Berlin,Germany:Springer-Verlag,2008:1003-1010.
 Zhang L,Ghosh B K.Line segment based map building and localization using 2D laser rangeflnder[C]//IEEE International Conference on Robotics and Automation.Piscataway,NJ,USA:IEEE,2000:2538-2543.
 Gutmann J S,Konolige IL Incremental mapping of large cycfic environments[C]//IEEE International Symposium on Computational Intelligence in Robotics and Automation.Piscataway,NJ,USA:IEEE,1999:318-325.