基于狭窄通道识别的机器人路径规划研究
|
摘要
机器人路径规划是移动机器人研究领域中的一个重要课题，经过几十年的研究，涌现出一批高效的算法：如路标法、基于栅格划分的A*算法、可视图法、势场法等。但当配置空间维数随机器人自由度增加而增加时，上述算法的性能急剧下降，甚至导致维数灾难。基于随机采样的路径规划在上世纪九十年代应运而生，致力于解决多自由度机器人的路径规划难题。其通过对配置空间的随机快速采样获得配置空间的连通性。近年来，随机性方法广泛应用于工作环境中存在障碍物的路径规划：如随机路标法，快速搜索随机树法等，对高维数配置空间中的路径规划非常有效。然而当机器人工作空间中存在较多障碍物或者未知位置的狭窄通道时，这些方法的运算时间就特别长，甚至很难找到合适的路径。针对这一问题，本文在对工作环境中狭窄通道进行识别的基础上，进行了相关路径规划方面的研究，主要包含以下几个方面的内容：
（1）提出了星形试验法，提高了算法对狭窄通道的识别能力，避免路标分布于障碍物的凹陷死角内。在此基础上，对均衡采样、高斯采样、桥试验法以及本文所提出的星形试验法等四种随机路标采集方法的狭窄通道识别性能进行分析，并以仿真验证了星形试验法的有效性。
（2）提出基于星形试验法的三树RRT算法，用于求解具有狭窄通道的多自由度机器人路径规划问题。通过星形试验法发现的标记配置点启发式地引导树扩展算法在狭窄通道中进行更多的采样，从而使RRT树既能够覆盖开阔的自由配置空间，又能够获得良好的连通性。算法具有简单、通用的特点，并通过大量仿真验证了该算法的性能比双树结构的RRT-CONNECT算法更高。
（3）针对狭窄通道中路标采集难的问题，提出了基于狭窄通道识别的混合路标规划法。新提出的路径规划器的关键策略在于星形试验法，它能提高狭窄通道中的路标密度以改善路标连接树的扩展速度。星形试验法可以看作是一种过滤狭窄通道的工具，在全局范围内筛选出狭窄通道区域，在标识出的区域内使用均衡采样器作局部的路标采集，提高局部区域的路标密度。在全局和局部交替采集路标，最终使路标的分布理想化，减少了路标规划所必需的路标总数，进而加快了连接树的扩展速度。
（4）提出了基于地图学习的多任务规划算法，利用高斯采样器生成三分之一的样本用以检测障碍物，用星型试验法生成三分之一的样本用以检测配置空间中的狭窄通道，同时在全空间均匀采样三分之一的样本点。通过混合采用三种采样方式，学习环境地图。在此基础之上，提出了一种改进的扩展随机树算法，使得算法即能够探索开阔的自由空间，也能有效地识别配置空间中的狭窄通道，同时使得机器人能够在这个框架下完成多任务。最后在2维及3维笛卡尔空间中的多自由度刚体机器人上进行仿真，验证了该算法的有效性。
Robot path planning is an important research topic in mobile robot. After decades ofeffort by researchers, effective algorithms emerges, e.g. roadmap, A*based on grid,visibility-based path planning method etc. But the performance of these algorithms greatlydrops as the dimension in configuration space increases with the addition of robot DoFs, andeven leads to curse of dimensionality. Random sampling method was proposed twenty yearsago to plan path for robot with multiple DoFs. It acquires the connection of configurationspace through randomly rapid sampling. In recent years, random method has widely beenused in path planning for the working space with obstacles, e.g. random roadmap andrapid-exploring tree. They are especially effective for cases with plenty of DoFs in theconfiguration space of moving object. However, when the working space has obstacles orexists with narrow passages, the above algorithms will cost long computation time and someeven inability to find suitable answers. In view of the above-stated limitations, this thesisfocuses on path planning base on recognition of narrow passages in the working space. Themain contents are listed as follows.
This thesis proposes Randomized Star Builder to improve the recognition of narrowpassages and to avoid sampling milestones locating in the corners of obstacles. The validity ofthis method is tested in simulations and we also compare the narrow passage recognitionperformance among the Uniform sampler, Gaussian sampler, Randomized Bridge Builder andthe proposed Randomized Star Builder.
This thesis presents a triple-RRTs algorithm based on Randomized Star Builder to planpath for robots with multiple DoFs in a space with narrow passages. It uses the configurationpoint sampled by Randomized Star Builder to heuristically lead tree expansion to facilitatemore in the narrow passages. As a result, the RRT covers a wide free configuration space and offers good connections among trees. Simulation results show that this algorithm is simple,general, and possesses better performance compared with the RRT-CONNECT.
In order to facilitate roadmap sampling in narrow passages, a hybrid roadmap plannerbase on the narrow passage identification is designed. This new planner, which relies onRandomized Star Builder, increases the roadmap density in narrow passages resulting inimprovement of the exploring speed of the roadmap connection tree. Randomized StarBuilder can be considered as a tool to filter narrow passages. It picks out narrow passages inglobal area, uses Uniform sampler to locally sample milestones in the identification area toincrease local roadmap density and samples milestones globally and locally in an alternatemanner. As a result, it gets an ideal roadmap distribution, reduces the total number ofmilestones and accelerates exploring speed of connection trees.
We also propose a multiple-method planning algorithm which is based on map learning.It uses Gaussian sampler to recognize obstacles with a third of the milestones, employsRandomized Star Builder to identify narrow passages in configuration space with anotherone-third of the milestones and acquires the remaining milestones in the full space usingUniform sampler. With this hybrid sampling method learned the environment, an improvedexpansive random tree algorithm is developed to explore wide free space. This hybridsampling method also effectively identifies narrow passages in the configuration space andachieves multiple robot tasks in this frame. Simulations of rigid robot with multiple DoFs in2-D and3-D validate the effectiveness of the proposed method.
（1）提出了星形试验法，提高了算法对狭窄通道的识别能力，避免路标分布于障碍物的凹陷死角内。在此基础上，对均衡采样、高斯采样、桥试验法以及本文所提出的星形试验法等四种随机路标采集方法的狭窄通道识别性能进行分析，并以仿真验证了星形试验法的有效性。
（2）提出基于星形试验法的三树RRT算法，用于求解具有狭窄通道的多自由度机器人路径规划问题。通过星形试验法发现的标记配置点启发式地引导树扩展算法在狭窄通道中进行更多的采样，从而使RRT树既能够覆盖开阔的自由配置空间，又能够获得良好的连通性。算法具有简单、通用的特点，并通过大量仿真验证了该算法的性能比双树结构的RRT-CONNECT算法更高。
（3）针对狭窄通道中路标采集难的问题，提出了基于狭窄通道识别的混合路标规划法。新提出的路径规划器的关键策略在于星形试验法，它能提高狭窄通道中的路标密度以改善路标连接树的扩展速度。星形试验法可以看作是一种过滤狭窄通道的工具，在全局范围内筛选出狭窄通道区域，在标识出的区域内使用均衡采样器作局部的路标采集，提高局部区域的路标密度。在全局和局部交替采集路标，最终使路标的分布理想化，减少了路标规划所必需的路标总数，进而加快了连接树的扩展速度。
（4）提出了基于地图学习的多任务规划算法，利用高斯采样器生成三分之一的样本用以检测障碍物，用星型试验法生成三分之一的样本用以检测配置空间中的狭窄通道，同时在全空间均匀采样三分之一的样本点。通过混合采用三种采样方式，学习环境地图。在此基础之上，提出了一种改进的扩展随机树算法，使得算法即能够探索开阔的自由空间，也能有效地识别配置空间中的狭窄通道，同时使得机器人能够在这个框架下完成多任务。最后在2维及3维笛卡尔空间中的多自由度刚体机器人上进行仿真，验证了该算法的有效性。
Robot path planning is an important research topic in mobile robot. After decades ofeffort by researchers, effective algorithms emerges, e.g. roadmap, A*based on grid,visibility-based path planning method etc. But the performance of these algorithms greatlydrops as the dimension in configuration space increases with the addition of robot DoFs, andeven leads to curse of dimensionality. Random sampling method was proposed twenty yearsago to plan path for robot with multiple DoFs. It acquires the connection of configurationspace through randomly rapid sampling. In recent years, random method has widely beenused in path planning for the working space with obstacles, e.g. random roadmap andrapid-exploring tree. They are especially effective for cases with plenty of DoFs in theconfiguration space of moving object. However, when the working space has obstacles orexists with narrow passages, the above algorithms will cost long computation time and someeven inability to find suitable answers. In view of the above-stated limitations, this thesisfocuses on path planning base on recognition of narrow passages in the working space. Themain contents are listed as follows.
This thesis proposes Randomized Star Builder to improve the recognition of narrowpassages and to avoid sampling milestones locating in the corners of obstacles. The validity ofthis method is tested in simulations and we also compare the narrow passage recognitionperformance among the Uniform sampler, Gaussian sampler, Randomized Bridge Builder andthe proposed Randomized Star Builder.
This thesis presents a triple-RRTs algorithm based on Randomized Star Builder to planpath for robots with multiple DoFs in a space with narrow passages. It uses the configurationpoint sampled by Randomized Star Builder to heuristically lead tree expansion to facilitatemore in the narrow passages. As a result, the RRT covers a wide free configuration space and offers good connections among trees. Simulation results show that this algorithm is simple,general, and possesses better performance compared with the RRT-CONNECT.
In order to facilitate roadmap sampling in narrow passages, a hybrid roadmap plannerbase on the narrow passage identification is designed. This new planner, which relies onRandomized Star Builder, increases the roadmap density in narrow passages resulting inimprovement of the exploring speed of the roadmap connection tree. Randomized StarBuilder can be considered as a tool to filter narrow passages. It picks out narrow passages inglobal area, uses Uniform sampler to locally sample milestones in the identification area toincrease local roadmap density and samples milestones globally and locally in an alternatemanner. As a result, it gets an ideal roadmap distribution, reduces the total number ofmilestones and accelerates exploring speed of connection trees.
We also propose a multiple-method planning algorithm which is based on map learning.It uses Gaussian sampler to recognize obstacles with a third of the milestones, employsRandomized Star Builder to identify narrow passages in configuration space with anotherone-third of the milestones and acquires the remaining milestones in the full space usingUniform sampler. With this hybrid sampling method learned the environment, an improvedexpansive random tree algorithm is developed to explore wide free space. This hybridsampling method also effectively identifies narrow passages in the configuration space andachieves multiple robot tasks in this frame. Simulations of rigid robot with multiple DoFs in2-D and3-D validate the effectiveness of the proposed method.
引文
[1]朱世强,王宣银.机器人技术及其应用.北京：浙江大学出版社,2002.
[2]柳洪义,宋伟刚.机器人技术基础.北京：冶金工业出版社,2002.
[3]蔡自兴.机器人学.北京：清华大学出版社,2000.
[4]韩建海.工业机器人.武汉：华中科技大学出版社,2009.
[5]孙树栋.工业机器人技术基础.西安：西北工业大学出版社,2006.
[6]Nilsson N. A mobile automation:An application of artificial intelligence techniques. Proceedings of the International Joint Conference on Artificial Intelligence, Washington, D. C.1969:509-520.
[7]Giralt G., Chatila R. and Vaisset M. An integrated navigation and motion control system for autonomous multisensory mobile robots.1st International Symposium on Robotics Research,1984:191-214.
[8]Moravec H. P. The stanford cart and the CMU rover. Proceedings of the IEEE,1983,71(7):872-884.
[9]Mosher R. S. Test and evaluation of a versatile walking truck. Proceedings of the Cornell Aeronautic Lab/ISTVS Off-road Mobility Research Symposium, Washington, D. C.1968:359-379.
[10]http://support.sony-europe.com/aibo/.
[11]赵冬斌,易建强.全方位移动机器人导论.北京：科学出版社,2010.
[12]李磊,叶涛,谭民,陈细军.移动机器人技术研究现状与未来.机器人,2002,24(5)：475-480.
[13]张毅,罗元,郑太雄.移动机器人技术及应用.北京：电子工业出版社,2007.
[14]Lozano-Pere Welsloy. An algorithm for collision-free path among polyhedral obstacles. Commun. Ass. Comput.,1979,22:56-570.
[15]Chien R. T., Zhang Ling and Zhang Bo. Planning collision-free path for robotic arm among obstacles. IEEE Trans. PAMI-6,1984,91-96.
[16]Zhang Bo. and Zhang Ling. Planning collision-free paths for three-dimension objects with rotation. Report on ACADEMIA SINICA(China) and CNRS(FRANCE) Roboties Workshop. Oct,1985.
[17]LaValle S. M. Planning Algorithms. New York:Cambridge University Press.2006.
[18]庄慧忠.动态不确定环境下移动机器人的在线实时路径规划.杭州：浙江大学博士学位论文,2005.
[19]奚茂龙.群体智能算法及其在移动机器人路径规划与跟踪控制中的研究.无锡：江南大学博士学位论文,2005.
[20]李劲松,宋立博,葛志飞,徐兆红,颜国正.基于分层搜索的移动机器人路径优化.控制工程,2010,17(2)：190-196.
[21]Khatib O. Real-time obstacle avoidance for manipulators and mobile robots. Robotics Research,1986,5(1):90-98.
[22]Keron Y. and Boresstein J. Potential field methods and their inherent limitations for mobile robot navigation. Proeedings of IEEE Inernational Conference on Robotics and Automation, California, April,1991:1398-1404.
[23]Hwang Y. K. and Ahuja N. Potential field approach to Path Planning. IEEE Tranactions on Robotics and Automation,1992,8(1):23-32.
[24]Ulrich I. and Borenstein J. VFH+:Reliable obstacle avoidance for fast mobile robots. IEEE International Conference on Robotics and Automation, Leuven, Belgium,1998:1572-1577.
[25]Ulrich I. and Borenstein J. VFH*:local obstacle avoidance with look-ahead verfication. In proceedings of the IEEE international conference on robotics and automation, San Francisco, CA,2000:2505-2511.
[26]王芳,万磊,徐玉如,张玉奎.基于改进人工势场的水下机器人路径规划.华中科技大学学报(自然科学版),2011,39(Sup.Ⅱ)：184-187.
[27]董立志,孙茂相.基于实时障碍物预测的机器人运动规划.机器人,2000,22(1)：12-16.
[28]朱向阳,丁汉.凸多面体之间的伪最小平移距离(Ⅱ)机器人运动规划.中国科学,2001,E辑：31(3)：238-244.
[29]Maaref H. and Barret C. Sensor-based fuzzy navigation of an autonomous mobile robot in anindoor environment. Control Engineering Practice,2000,8(7):757-768.
[30] Masoud S. A. and Masoud A. A. Motion planning in the presence of directional and regionalavoidance constraints using nonlinear, anisotropic, harmonic potential fields: a physiecalmetaphor. IEEE Transactions on System, Man, and Cyberneties. Part A,2002,32(6):705-723.
[31] Daily R. and Bevly D. M. Harmonic potential field path planning for high speed vehicles. InProeeedings of the2008American Control Conference,2008:4609-4614.
[32] Karnik M., Dasgupta B. and Eswaran V. A comparative study of Dirichlet and Neumannconditions for path planning through harmonic functions. Future Generation Computer Systems,2004,20(3):441-452.
[33] Hong R. and DeSouza G. N. A real-time path planner for a smart wheelchair using harmonicpotentials and a rubber band model. Proceedings of the2006IEEE/RSJ International Conferenceon Intelligent Robots and Systems,2010:3282-3287.
[34] Masoud A. A. A discrete harmonic potential field for optimum point-to-point routing on aweighted graph. Proceedings of the2006IEEE/RSJ International Conference on IntelligentRobots and Systems,2006:1779-1784.
[35] Masoud A. A. Managing the dynamics of a harmonic potential field-guided robot in a clutteredenvironment. IEEE Transactions on Industrial Electronics,2009,56(2):488-496.
[36] Metea M. B. Planning for intelligence autonomous land vehicles using hierarchical terrainrepresentation. Proceedings of IEEE International Conference on Robotics and Automation,1987:1947-1952.
[37] Weber H. A motion Planning and execution system for mobile robots driven by stepping motors.Robotics and Autonomous Systems,2000,33(4):207-221.
[38] Kambhampati S. K. and Davis L. S. Multi-resolution path planning for mobile robots. IEEEJoumal of Robotics and Automation,1986,(RA-2,3):135-145.
[39] Parsons D. and Canny J. F., A motion planner for multiple mobile robots. IEEE InternationalConference on Robotics and Automation,1990:8-13.
[40] Latombe J. C. Robot motion planning.1991.
[41] Chen D. Z., Szczerba R. J. and Uhran J. J. A framed-quadtree approach for determiningEuclidean shortest paths in a2-D environment. IEEE Transactions on Robotics and Automation, 1997,13(5):668-681.
[42]罗其俊,李志恒,李元朋,高庆吉.基于门墙栅格地图模型的有约束路径规划研究.计算机与现代化,2010,5：180-183.
[43]Wu L. Applying dynamic hybrid grids method to simulate AUV docking with a tube. Proceedings of2010IEEE International Conference on Information and Automation,2010:1363-1366.
[44]李天成,孙树栋,高扬.基于扇形栅格地图的移动机器人全局路径规划.机器人,2010,32(4)：547-552.
[45]Huyn N., Dechter R. and Pearl J., Probabilistic analysis of the complexity of A*. Artificial Intelligence,1980,15(3):241-254.
[46]Alexopoulos C. and Griffin P. M. Path planning for a mobile robot. IEEE Transactions on Systems, Man, and Cybernatics,1992,22(2):318-322.
[47]Guo J., Liu L., Liu Q. and Qu Y. An improvement of D*algorithm for mobile robot path planning in partial unknown environment. Proceedings of2009Intelligent Computation Technology and Automation,2009,3:394-397.
[48]Yahja A. and Singh S. Stentz. An efficient on-line path planner for outdoor mobile robots. Robotics and Autonomous Systems,2000,32(2-3):129-143.
[49]王仲民.移动机器人路径规划及轨迹跟踪问题研究.河北：河北工业大学博士学位论文,2006.
[50]杨晶东.移动机器人自主导航关键技术研究.哈尔滨：哈尔滨工业大学博士学位论文,2008.
[51]成伟明,唐振民,赵春霞,陈得宝,.基于神经网络和PSO的机器人路径规划研究.系统仿真学报.2008,20(3)：608-611.
[52]梁瑾,宋科璞.神经网络在移动机器人路径规划中的应用.系统仿真学报.2010,22(Sup.1)：269-272.
[53]王仲民,戚厚军,阎兵.一种新型混合优化算法在机器人路径规划中的应用.机械设计.2003,20(6)：43-44.
[54]Fierro R. and Lewis F. L. Control of a nonholonomic mobile robot using neural networks. IEEE Transaction on Neural Networks,1998,9(4):589-600.
[55]张宏烈.移动机器人全局路径规划的研究.哈尔滨工程大学硕士学位论文.2002.
[56]Latombe J. C. Robot Motion Planning. Kluwer Academic Puplishers,1991.
[57]Li H., Yang S. X. and Seto M. L. Neural-network-based path planning for a multirobot system with moving obstacles. IEEE Transactions on Systems, Man and Cybernetics, Part C,2009,39(4):410-419.
[58]Yamamoto M., Ushimi N., and Mohri A. Sensor-based navigation for mobile robots using target direction sensor. Journal of the Robotics Society of Japan,1998,16(8):1083-1090.
[59]Quoy M., Moga S. and Gaussier P. Dynamical neural networks for planning and low-level robot control. IEEE Transactions on Systems, Man and Cybernetics, Part A,2003,33(4):523-532.
[60]Qu H., Yang S. X., Willms A. R. and Zhang Yi. Real-time robot path planning based on a modified pulse-coupled neural network model. IEEE Transactions on Neural Networks,2009,20(11):1724-1739.
[61]田景文,高美娟.基于改进的模拟退火人工神经网络的薄互储层参数预测.信息与控制,2002,31(2)：180-184.
[62]Araujo R. Prune-able fuzzy aRT neural architecture for robot map learning and navigation in dynamic environments. IEEE Transactions on Neural Networks,2006,17(5):1235-1249.
[63]缪国春,贺知明.改进模拟退火算法在码组优化中的应用.工业控制计算,2004,17(2)：35-36.
[64]王仲民.岳宏.一种移动机器人全局路径规划新型算法.机器人,2003,25(2)：152-155.
[65]宋勇,李贻斌,刘冰.基于进化神经网络的移动机器人路径规划方法.中国科技论文在线,2010,5(1)：1-5.
[66]庄晓东,孟庆春,殷波,王汝霖,熊建设,王旭柱.动态环境中基于模糊概念的机器人路径搜索方法.机器人,2001,23(5)：397-399.
[67]Hwang C. L. and Chang L. J. Internet-based smart-space navigation of a car-like wheeled robot using fuzzy-neural adaptive control. IEEE Transactions on Fuzzy Systems.2008,16(5):1271-1284.
[68]成伟明.移动机器人自主导航中的路径规划与跟踪控制技术研究.南京：南京理工大学博士学位论文,2007.
[69]陈少斌.自主移动机器人路径规划及轨迹跟踪的研究.杭州：浙江大学博士学位论文,2008.
[70]康亮.自主移动机器人运动规划的若干算法研究.南京：南京理工大学博士学位论文,2009.
[71]Mitchell M. An introduction to genetic algorithms. Boston:The MIT Press,1996.
[72]Davidor Y. A genetic alogrithm applied to robot trajectory generation. HandBook of Genetic Alogrithms Ed L Davis, New York,1991:144-165.
[73]Chen M. W. and Zalzala A. M. S. Safty consideration in the optimisation of path for mobile robot using genetic alogrithms. Conference Publiccation No.414IEE,1995.
[74]王雪松,高阳,程玉虎,马小平.知识引导遗传算法实现机器人路径规划.控制与决策,2009,24(7)：1043-1049.
[75]Tsai C., Huang H. and Chan C. Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation. IEEE Transactions on Industrial Electronics,2011,58(10):4813-4821.
[76]Gyorfi J. S., Gamota D. R., Mok S. M., Szczech J. B., Toloo M. and Zhang, J. Evolutionary path planning with subpath constraints. IEEE Transactions on Electronics Packaging Manufacturing,2010,33(2):143-151.
[77]Alvarez A., Caiti A. and Onken R. Evolutionary path planning for autonomous underwater vehicles in a variable ocean. IEEE Journal of Oceanic Engineering,2004:418-429.
[78]李枚毅,蔡自兴.改进的进化编程及其在机器人路径规划中的应用.机器人,2000,22(6)：490-494.
[79]Deng X. Y., Yi J. Q. and Zhao D. B. An optimal two-stage path planner. International Journal of Information Technology,2005,11(11):21-30.
[80]刘国栋,谢宏斌,李春光.动态环境中基于遗传算法的移动机器人路径规划的方法.机器人,2003,25(4)：327-330.
[81]Yang W., Sillitoe I. P. W. and Mulvaney D. J. Mobile robot path planning in dynamic enviroment. IEEE International Conference on Robotics and Automation,2007:71-76.
[82]孙树栋,林茂.基于遗传算法的多移动机器人协调路径规划.自动化学报,2000,26(5)：672-676.
[83]柳长安,鄢小虎,刘春阳,吴华.基于改进蚁群算法的移动机器人动态路径规划方法.电子学报.2011,39(5)：1220-1224.
[84]朱庆保.动态复杂环境下的机器人路径规划蚂蚁预测算法.计算机学报.2005,28(11)：1898-1906.
[85]孙波,陈卫东,席裕庚.基于粒子群优化算法的移动机器人全局路径规划.控制与决策.2005,20(9)：1052-1060.
[86]陈宜航,牛玉刚.一种基于粒子群算法的轮式机器人路径规划.计算机仿真.2010,27(4)：167-171.
[87]Tewolde G. S. and Sheng W. Robot path integration in manufacturing processes:genetic algorithm versus ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part A,2007,278-287.
[88]Dorigo M., Maniezzo V. and Colorni A. The ant system:optimization by a colony of cooperating agents. IEEE Trans on Systems, Man, and Cybernetics, part B,1996,26(2):29-41.
[89]Dorigo M. and Gambardella L. M. Ant colony system:a cooperative learning approach to the travelling sales-man problem. IEEE Transactons on Evolutionary Computation,1997,1(1):53-66.
[90]马良.来自昆虫世界的寻优策略—蚂蚁算法.自然杂志,1999,21(3)：161-163.
[91]马良.全局优化的一种新方法.系统工程与电子技术,2000,22(9)：61-62.
[92]Kennedy J. and Eberhart R. C. Particle swarm optimization. Proceedings of IEEE International Conference on Neutral Networks,1995:1942-1948.
[93]Angeline P. J. Evolutionary optimization versus particle swarm optimization:philosophy and performance difference. Annual Conference Center on Evolutionary Programming,1998:601-610.
[94]Eberhart R. C. and Shi Y. Particle swarm optinization:developments,applications and resources. Proceedings of the Congress on Evolutionary Computation,2001:81-86.
[95]Clerc M. and Kennedy J. The particle swarm-explosion, stability and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computer,2002,6(1):58-73.
[96]Kavraki L. and Latombe J. Randomized preproeessing of configuration space for fast path planning. IEEE International Conference on Robotics and Automation,1994:2138-2139.
[97]Hsu D., Latombe J. and Kurniawati H. On the probabilistic foundations of probabilistic roadmap planning.12th International Sympium On Robotics Research,2005:627-643.
[98]Hsu D., Latombe J. and Motwani R. Path planning in expansive configuration spaces.International Journal of Computational Geometry and Applications,1999,9(4):495-512.
[97] Bhattacharya P. and Gavrilova M. L. Roadmap-based path planning–using the voronoi diagramfor a clearance-based shortest path, IEEE robotics And Automation Magazine,2008,15(2):58-66.
[98] Simonin E. and Diard J. BBPRM: A behavior-based probabilistic roadmap method. Proceedingsof IEEE International Conference on Systems, Man, and Cybernatics,2008:1719-1724.
[99] Chakravorty S. and Kumar S. Generalized sampling-based motion planners. IEEE Transactionson Systems, Man, and Cybernatics, Part B,2011,41(3):855-866.
[100] Saha M. and Latombe J. Finding narrow passages with probabilistic roadmaps: the small stepretraction method. IEEE Conference on Intelligent Robots and Systems,2005:301-319.
[101] S. M. Lavalle. Motion planning. IEEE Robotics and Automation Magazine,2011,18(1):79-89.
[102] Wilmarth S., Amato N. and Stiller P. MAPRM: A probabilistic roadmap Plarmer with samplingon the medial axis of the free space. IEEE Intemational Conference on Robotics and Automation,1999:1024-1031.
[103] Amato N., Bayazit O., Dale L., Jones C. and Vallejo D. OBPRM: an obstacle-based PRM for3D workspaces. Robotics: The algorithmic perspective,1998:155-168.
[104] Raveh B., Enosh A. and Halperin D. A little more, a lot better: improving path quality by apath-merging algorithm. IEEE Transactions on Robotics,2011,27(2):365-371.
[105] J. B. Su and W. L. Xie, Motion planning and coordination for robot systems based onrepresentation space. IEEE Transactions on Systems, Man, and Cybernatics, Part B,201141(1):248-259.
[106] Boor V., Overmars M. H. and Stappen A. F. The Gaussian sampling strategy for probabilisticroadmap planners. Proceedings of IEEE International Conference on Robotics and Automation,1999:1018–1023.
[107] Lin Y. T. The Gaussian PRM sampling for dynamic configuration spaces. Proceedings of9thInternational Conference on Control, Automation, Robotics, and Vision,2006:1-5.
[108] Hsu D., Jiang T., Reif J. and Sun Z. The bridge test for sampling narrow passages withprobabilistic roadmap planners. Proceedings of IEEE International Conference on Robotics andAutomation,2003,4420-4426.
[109] Sun Z., Hsu D., Jiang T., Kurniawati H. and Reif J. H. Narrow passage sampling forprobabilistic roadmap planning. IEEE Transactions on Robotics,2005,21(6):1105-1115.
[110] Quinlan S. Efficient distance computation between Non-convex objects. Proceedings of IEEEInternational Conference on Robotics and Automation,1994,3324-3330.
[111] Gottschalk S., Lin M. and Manocha D. OBBTree: A hierarchical structure for rapid interferencedetection. Proceedings of23rdAnnual Conference on Computer, Graphics, InteractiveTechnology,1996,171-180.
[112] Cortes J., Lin M., Manocha D. and Ponamgi M. I-Collide: an interactive and exact collisiondetection system for large scale environments. Proceedings of Conference ACM Sympium onInteractive3D Graphics,1995,189-196.
[113] S. M. LaValle. Rapidly-exploring random trees: A new tool for path planning. ComputerScience Departent., Iowa State University,1998.
[114] Kuwata Y., Karaman S., Teo J., Frazzoli E., How J. P. and Fiore G. Real-time motion planningwith applications to autonomous urban driving. IEEE Transactions on Control SystemsTechnology,2009,17(5):1105-1118.
[115] Smith J. Distance and path: the development, interpretation and application of distancemeasurement in mapping and modeling. PhD Thesis, University of London,2003.
[116] Jaillet L., Cortes J. and Simeon T. Sampling-based path planning on configuration-spacecostmaps. IEEE Transactions on Robotics,2010,26(4):635-646.
[117] Jaillet L., Yershova A., Lavalle S. M. and Simeon T. Adaptive tuning of the sampling domain fordynamic-domain RRTs. Proceedings IEEE International Conference on Intelligent Robots andSystems,2005:2851-2856.
[118] Yershova A., Jaillet L., Simeon T. and LaValle S. M. Dynamic-domain RRTs: efficientexploration by controlling the sampling domain. Proceedings of the IEEE InternationalConference on Robotics and Automation,2005:3856-3861.
[119] Lindemann S. R. and LaValle S. M. Steps toward de-randomizing RRTs. IEEE4thInternationalWorkshop on Robot Motion and Control.2004:271-277.
[120] Cheng P., Frazzoli E. and LaValle S. M. Improving the performance of sampling-based plannersby using a symmetry-exploiting gap reduction algorithm. proceedings IEEE International Conference on Robotics and Automation.2004:4362-4368.
[121]康亮,赵春霞,郭剑辉.未知环境下改进的基于RRT算法的移动机器人路径规划.模式识别与人工智能,2009,22(3)：337-343.
[122]LaValle S. M. and Kuffner J., Rapidly-exploring random trees:Progress and Prospects. Proceedings of Intnational Workshop on Algorithmic Foundations of Robotics,2000:293-308.
[123]Kuffner J. and LaValle S. M. RRT-connect:an efficient approach to single-query path planning. Proceedings of IEEE International Conference on Robotics and Automation,2000:995-100.
[124]Han L. and Amato N. M. A kinematics-based probabilistic roadmap method for closed chain systems. Algorithmic and Computational Robotics:New Directions,2001:233-246.
[125]Svestka P. and Overmars M. H. Coordinated motion planning for multiple car-like robots using probabilistic roadmaps. IEEE Transactions on Robotics and Automation,1995,1631-1636.
[126]Wang W. and Li Y. A multi-RRTs framework for robot path planning in high-dimensional configuration space with narrow passages. Proceedings of IEEE International Conference on Mechatronics and Automation,2009,4952-4957.
[127]钟建冬,苏剑波.基于概率路标的机器人狭窄通道路径规划.控制与决策,2010,25(12)：1831-1836.
[128]Latombe J. C. Motion planning:a journey of robots, molecules, digital actors, and other artifacts. International Journal of Robotics Research,1999,18:1119-1128.
[129]Chakravorty S. and S. Kumar. Generalized sampling-based motion planners. IEEE Transactions on Systems, Man, and Cybernetics, Part B,2011,41(3):855-866.
[130]Raveh B., Enosh A. and Halperin D. A little more, a lot better:improving path quality by a path-merging algorithm. IEEE Transactions on Robotics,2011,27(2):365-371.
[131]Jaillet L., Corte J. and Simeon T. Sampling-based path planning on configuration-space costmaps. IEEE Transactions on Robotics,2010,26(4):635-646.
[2]柳洪义,宋伟刚.机器人技术基础.北京：冶金工业出版社,2002.
[3]蔡自兴.机器人学.北京：清华大学出版社,2000.
[4]韩建海.工业机器人.武汉：华中科技大学出版社,2009.
[5]孙树栋.工业机器人技术基础.西安：西北工业大学出版社,2006.
[6]Nilsson N. A mobile automation:An application of artificial intelligence techniques. Proceedings of the International Joint Conference on Artificial Intelligence, Washington, D. C.1969:509-520.
[7]Giralt G., Chatila R. and Vaisset M. An integrated navigation and motion control system for autonomous multisensory mobile robots.1st International Symposium on Robotics Research,1984:191-214.
[8]Moravec H. P. The stanford cart and the CMU rover. Proceedings of the IEEE,1983,71(7):872-884.
[9]Mosher R. S. Test and evaluation of a versatile walking truck. Proceedings of the Cornell Aeronautic Lab/ISTVS Off-road Mobility Research Symposium, Washington, D. C.1968:359-379.
[10]http://support.sony-europe.com/aibo/.
[11]赵冬斌,易建强.全方位移动机器人导论.北京：科学出版社,2010.
[12]李磊,叶涛,谭民,陈细军.移动机器人技术研究现状与未来.机器人,2002,24(5)：475-480.
[13]张毅,罗元,郑太雄.移动机器人技术及应用.北京：电子工业出版社,2007.
[14]Lozano-Pere Welsloy. An algorithm for collision-free path among polyhedral obstacles. Commun. Ass. Comput.,1979,22:56-570.
[15]Chien R. T., Zhang Ling and Zhang Bo. Planning collision-free path for robotic arm among obstacles. IEEE Trans. PAMI-6,1984,91-96.
[16]Zhang Bo. and Zhang Ling. Planning collision-free paths for three-dimension objects with rotation. Report on ACADEMIA SINICA(China) and CNRS(FRANCE) Roboties Workshop. Oct,1985.
[17]LaValle S. M. Planning Algorithms. New York:Cambridge University Press.2006.
[18]庄慧忠.动态不确定环境下移动机器人的在线实时路径规划.杭州：浙江大学博士学位论文,2005.
[19]奚茂龙.群体智能算法及其在移动机器人路径规划与跟踪控制中的研究.无锡：江南大学博士学位论文,2005.
[20]李劲松,宋立博,葛志飞,徐兆红,颜国正.基于分层搜索的移动机器人路径优化.控制工程,2010,17(2)：190-196.
[21]Khatib O. Real-time obstacle avoidance for manipulators and mobile robots. Robotics Research,1986,5(1):90-98.
[22]Keron Y. and Boresstein J. Potential field methods and their inherent limitations for mobile robot navigation. Proeedings of IEEE Inernational Conference on Robotics and Automation, California, April,1991:1398-1404.
[23]Hwang Y. K. and Ahuja N. Potential field approach to Path Planning. IEEE Tranactions on Robotics and Automation,1992,8(1):23-32.
[24]Ulrich I. and Borenstein J. VFH+:Reliable obstacle avoidance for fast mobile robots. IEEE International Conference on Robotics and Automation, Leuven, Belgium,1998:1572-1577.
[25]Ulrich I. and Borenstein J. VFH*:local obstacle avoidance with look-ahead verfication. In proceedings of the IEEE international conference on robotics and automation, San Francisco, CA,2000:2505-2511.
[26]王芳,万磊,徐玉如,张玉奎.基于改进人工势场的水下机器人路径规划.华中科技大学学报(自然科学版),2011,39(Sup.Ⅱ)：184-187.
[27]董立志,孙茂相.基于实时障碍物预测的机器人运动规划.机器人,2000,22(1)：12-16.
[28]朱向阳,丁汉.凸多面体之间的伪最小平移距离(Ⅱ)机器人运动规划.中国科学,2001,E辑：31(3)：238-244.
[29]Maaref H. and Barret C. Sensor-based fuzzy navigation of an autonomous mobile robot in anindoor environment. Control Engineering Practice,2000,8(7):757-768.
[30] Masoud S. A. and Masoud A. A. Motion planning in the presence of directional and regionalavoidance constraints using nonlinear, anisotropic, harmonic potential fields: a physiecalmetaphor. IEEE Transactions on System, Man, and Cyberneties. Part A,2002,32(6):705-723.
[31] Daily R. and Bevly D. M. Harmonic potential field path planning for high speed vehicles. InProeeedings of the2008American Control Conference,2008:4609-4614.
[32] Karnik M., Dasgupta B. and Eswaran V. A comparative study of Dirichlet and Neumannconditions for path planning through harmonic functions. Future Generation Computer Systems,2004,20(3):441-452.
[33] Hong R. and DeSouza G. N. A real-time path planner for a smart wheelchair using harmonicpotentials and a rubber band model. Proceedings of the2006IEEE/RSJ International Conferenceon Intelligent Robots and Systems,2010:3282-3287.
[34] Masoud A. A. A discrete harmonic potential field for optimum point-to-point routing on aweighted graph. Proceedings of the2006IEEE/RSJ International Conference on IntelligentRobots and Systems,2006:1779-1784.
[35] Masoud A. A. Managing the dynamics of a harmonic potential field-guided robot in a clutteredenvironment. IEEE Transactions on Industrial Electronics,2009,56(2):488-496.
[36] Metea M. B. Planning for intelligence autonomous land vehicles using hierarchical terrainrepresentation. Proceedings of IEEE International Conference on Robotics and Automation,1987:1947-1952.
[37] Weber H. A motion Planning and execution system for mobile robots driven by stepping motors.Robotics and Autonomous Systems,2000,33(4):207-221.
[38] Kambhampati S. K. and Davis L. S. Multi-resolution path planning for mobile robots. IEEEJoumal of Robotics and Automation,1986,(RA-2,3):135-145.
[39] Parsons D. and Canny J. F., A motion planner for multiple mobile robots. IEEE InternationalConference on Robotics and Automation,1990:8-13.
[40] Latombe J. C. Robot motion planning.1991.
[41] Chen D. Z., Szczerba R. J. and Uhran J. J. A framed-quadtree approach for determiningEuclidean shortest paths in a2-D environment. IEEE Transactions on Robotics and Automation, 1997,13(5):668-681.
[42]罗其俊,李志恒,李元朋,高庆吉.基于门墙栅格地图模型的有约束路径规划研究.计算机与现代化,2010,5：180-183.
[43]Wu L. Applying dynamic hybrid grids method to simulate AUV docking with a tube. Proceedings of2010IEEE International Conference on Information and Automation,2010:1363-1366.
[44]李天成,孙树栋,高扬.基于扇形栅格地图的移动机器人全局路径规划.机器人,2010,32(4)：547-552.
[45]Huyn N., Dechter R. and Pearl J., Probabilistic analysis of the complexity of A*. Artificial Intelligence,1980,15(3):241-254.
[46]Alexopoulos C. and Griffin P. M. Path planning for a mobile robot. IEEE Transactions on Systems, Man, and Cybernatics,1992,22(2):318-322.
[47]Guo J., Liu L., Liu Q. and Qu Y. An improvement of D*algorithm for mobile robot path planning in partial unknown environment. Proceedings of2009Intelligent Computation Technology and Automation,2009,3:394-397.
[48]Yahja A. and Singh S. Stentz. An efficient on-line path planner for outdoor mobile robots. Robotics and Autonomous Systems,2000,32(2-3):129-143.
[49]王仲民.移动机器人路径规划及轨迹跟踪问题研究.河北：河北工业大学博士学位论文,2006.
[50]杨晶东.移动机器人自主导航关键技术研究.哈尔滨：哈尔滨工业大学博士学位论文,2008.
[51]成伟明,唐振民,赵春霞,陈得宝,.基于神经网络和PSO的机器人路径规划研究.系统仿真学报.2008,20(3)：608-611.
[52]梁瑾,宋科璞.神经网络在移动机器人路径规划中的应用.系统仿真学报.2010,22(Sup.1)：269-272.
[53]王仲民,戚厚军,阎兵.一种新型混合优化算法在机器人路径规划中的应用.机械设计.2003,20(6)：43-44.
[54]Fierro R. and Lewis F. L. Control of a nonholonomic mobile robot using neural networks. IEEE Transaction on Neural Networks,1998,9(4):589-600.
[55]张宏烈.移动机器人全局路径规划的研究.哈尔滨工程大学硕士学位论文.2002.
[56]Latombe J. C. Robot Motion Planning. Kluwer Academic Puplishers,1991.
[57]Li H., Yang S. X. and Seto M. L. Neural-network-based path planning for a multirobot system with moving obstacles. IEEE Transactions on Systems, Man and Cybernetics, Part C,2009,39(4):410-419.
[58]Yamamoto M., Ushimi N., and Mohri A. Sensor-based navigation for mobile robots using target direction sensor. Journal of the Robotics Society of Japan,1998,16(8):1083-1090.
[59]Quoy M., Moga S. and Gaussier P. Dynamical neural networks for planning and low-level robot control. IEEE Transactions on Systems, Man and Cybernetics, Part A,2003,33(4):523-532.
[60]Qu H., Yang S. X., Willms A. R. and Zhang Yi. Real-time robot path planning based on a modified pulse-coupled neural network model. IEEE Transactions on Neural Networks,2009,20(11):1724-1739.
[61]田景文,高美娟.基于改进的模拟退火人工神经网络的薄互储层参数预测.信息与控制,2002,31(2)：180-184.
[62]Araujo R. Prune-able fuzzy aRT neural architecture for robot map learning and navigation in dynamic environments. IEEE Transactions on Neural Networks,2006,17(5):1235-1249.
[63]缪国春,贺知明.改进模拟退火算法在码组优化中的应用.工业控制计算,2004,17(2)：35-36.
[64]王仲民.岳宏.一种移动机器人全局路径规划新型算法.机器人,2003,25(2)：152-155.
[65]宋勇,李贻斌,刘冰.基于进化神经网络的移动机器人路径规划方法.中国科技论文在线,2010,5(1)：1-5.
[66]庄晓东,孟庆春,殷波,王汝霖,熊建设,王旭柱.动态环境中基于模糊概念的机器人路径搜索方法.机器人,2001,23(5)：397-399.
[67]Hwang C. L. and Chang L. J. Internet-based smart-space navigation of a car-like wheeled robot using fuzzy-neural adaptive control. IEEE Transactions on Fuzzy Systems.2008,16(5):1271-1284.
[68]成伟明.移动机器人自主导航中的路径规划与跟踪控制技术研究.南京：南京理工大学博士学位论文,2007.
[69]陈少斌.自主移动机器人路径规划及轨迹跟踪的研究.杭州：浙江大学博士学位论文,2008.
[70]康亮.自主移动机器人运动规划的若干算法研究.南京：南京理工大学博士学位论文,2009.
[71]Mitchell M. An introduction to genetic algorithms. Boston:The MIT Press,1996.
[72]Davidor Y. A genetic alogrithm applied to robot trajectory generation. HandBook of Genetic Alogrithms Ed L Davis, New York,1991:144-165.
[73]Chen M. W. and Zalzala A. M. S. Safty consideration in the optimisation of path for mobile robot using genetic alogrithms. Conference Publiccation No.414IEE,1995.
[74]王雪松,高阳,程玉虎,马小平.知识引导遗传算法实现机器人路径规划.控制与决策,2009,24(7)：1043-1049.
[75]Tsai C., Huang H. and Chan C. Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation. IEEE Transactions on Industrial Electronics,2011,58(10):4813-4821.
[76]Gyorfi J. S., Gamota D. R., Mok S. M., Szczech J. B., Toloo M. and Zhang, J. Evolutionary path planning with subpath constraints. IEEE Transactions on Electronics Packaging Manufacturing,2010,33(2):143-151.
[77]Alvarez A., Caiti A. and Onken R. Evolutionary path planning for autonomous underwater vehicles in a variable ocean. IEEE Journal of Oceanic Engineering,2004:418-429.
[78]李枚毅,蔡自兴.改进的进化编程及其在机器人路径规划中的应用.机器人,2000,22(6)：490-494.
[79]Deng X. Y., Yi J. Q. and Zhao D. B. An optimal two-stage path planner. International Journal of Information Technology,2005,11(11):21-30.
[80]刘国栋,谢宏斌,李春光.动态环境中基于遗传算法的移动机器人路径规划的方法.机器人,2003,25(4)：327-330.
[81]Yang W., Sillitoe I. P. W. and Mulvaney D. J. Mobile robot path planning in dynamic enviroment. IEEE International Conference on Robotics and Automation,2007:71-76.
[82]孙树栋,林茂.基于遗传算法的多移动机器人协调路径规划.自动化学报,2000,26(5)：672-676.
[83]柳长安,鄢小虎,刘春阳,吴华.基于改进蚁群算法的移动机器人动态路径规划方法.电子学报.2011,39(5)：1220-1224.
[84]朱庆保.动态复杂环境下的机器人路径规划蚂蚁预测算法.计算机学报.2005,28(11)：1898-1906.
[85]孙波,陈卫东,席裕庚.基于粒子群优化算法的移动机器人全局路径规划.控制与决策.2005,20(9)：1052-1060.
[86]陈宜航,牛玉刚.一种基于粒子群算法的轮式机器人路径规划.计算机仿真.2010,27(4)：167-171.
[87]Tewolde G. S. and Sheng W. Robot path integration in manufacturing processes:genetic algorithm versus ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part A,2007,278-287.
[88]Dorigo M., Maniezzo V. and Colorni A. The ant system:optimization by a colony of cooperating agents. IEEE Trans on Systems, Man, and Cybernetics, part B,1996,26(2):29-41.
[89]Dorigo M. and Gambardella L. M. Ant colony system:a cooperative learning approach to the travelling sales-man problem. IEEE Transactons on Evolutionary Computation,1997,1(1):53-66.
[90]马良.来自昆虫世界的寻优策略—蚂蚁算法.自然杂志,1999,21(3)：161-163.
[91]马良.全局优化的一种新方法.系统工程与电子技术,2000,22(9)：61-62.
[92]Kennedy J. and Eberhart R. C. Particle swarm optimization. Proceedings of IEEE International Conference on Neutral Networks,1995:1942-1948.
[93]Angeline P. J. Evolutionary optimization versus particle swarm optimization:philosophy and performance difference. Annual Conference Center on Evolutionary Programming,1998:601-610.
[94]Eberhart R. C. and Shi Y. Particle swarm optinization:developments,applications and resources. Proceedings of the Congress on Evolutionary Computation,2001:81-86.
[95]Clerc M. and Kennedy J. The particle swarm-explosion, stability and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computer,2002,6(1):58-73.
[96]Kavraki L. and Latombe J. Randomized preproeessing of configuration space for fast path planning. IEEE International Conference on Robotics and Automation,1994:2138-2139.
[97]Hsu D., Latombe J. and Kurniawati H. On the probabilistic foundations of probabilistic roadmap planning.12th International Sympium On Robotics Research,2005:627-643.
[98]Hsu D., Latombe J. and Motwani R. Path planning in expansive configuration spaces.International Journal of Computational Geometry and Applications,1999,9(4):495-512.
[97] Bhattacharya P. and Gavrilova M. L. Roadmap-based path planning–using the voronoi diagramfor a clearance-based shortest path, IEEE robotics And Automation Magazine,2008,15(2):58-66.
[98] Simonin E. and Diard J. BBPRM: A behavior-based probabilistic roadmap method. Proceedingsof IEEE International Conference on Systems, Man, and Cybernatics,2008:1719-1724.
[99] Chakravorty S. and Kumar S. Generalized sampling-based motion planners. IEEE Transactionson Systems, Man, and Cybernatics, Part B,2011,41(3):855-866.
[100] Saha M. and Latombe J. Finding narrow passages with probabilistic roadmaps: the small stepretraction method. IEEE Conference on Intelligent Robots and Systems,2005:301-319.
[101] S. M. Lavalle. Motion planning. IEEE Robotics and Automation Magazine,2011,18(1):79-89.
[102] Wilmarth S., Amato N. and Stiller P. MAPRM: A probabilistic roadmap Plarmer with samplingon the medial axis of the free space. IEEE Intemational Conference on Robotics and Automation,1999:1024-1031.
[103] Amato N., Bayazit O., Dale L., Jones C. and Vallejo D. OBPRM: an obstacle-based PRM for3D workspaces. Robotics: The algorithmic perspective,1998:155-168.
[104] Raveh B., Enosh A. and Halperin D. A little more, a lot better: improving path quality by apath-merging algorithm. IEEE Transactions on Robotics,2011,27(2):365-371.
[105] J. B. Su and W. L. Xie, Motion planning and coordination for robot systems based onrepresentation space. IEEE Transactions on Systems, Man, and Cybernatics, Part B,201141(1):248-259.
[106] Boor V., Overmars M. H. and Stappen A. F. The Gaussian sampling strategy for probabilisticroadmap planners. Proceedings of IEEE International Conference on Robotics and Automation,1999:1018–1023.
[107] Lin Y. T. The Gaussian PRM sampling for dynamic configuration spaces. Proceedings of9thInternational Conference on Control, Automation, Robotics, and Vision,2006:1-5.
[108] Hsu D., Jiang T., Reif J. and Sun Z. The bridge test for sampling narrow passages withprobabilistic roadmap planners. Proceedings of IEEE International Conference on Robotics andAutomation,2003,4420-4426.
[109] Sun Z., Hsu D., Jiang T., Kurniawati H. and Reif J. H. Narrow passage sampling forprobabilistic roadmap planning. IEEE Transactions on Robotics,2005,21(6):1105-1115.
[110] Quinlan S. Efficient distance computation between Non-convex objects. Proceedings of IEEEInternational Conference on Robotics and Automation,1994,3324-3330.
[111] Gottschalk S., Lin M. and Manocha D. OBBTree: A hierarchical structure for rapid interferencedetection. Proceedings of23rdAnnual Conference on Computer, Graphics, InteractiveTechnology,1996,171-180.
[112] Cortes J., Lin M., Manocha D. and Ponamgi M. I-Collide: an interactive and exact collisiondetection system for large scale environments. Proceedings of Conference ACM Sympium onInteractive3D Graphics,1995,189-196.
[113] S. M. LaValle. Rapidly-exploring random trees: A new tool for path planning. ComputerScience Departent., Iowa State University,1998.
[114] Kuwata Y., Karaman S., Teo J., Frazzoli E., How J. P. and Fiore G. Real-time motion planningwith applications to autonomous urban driving. IEEE Transactions on Control SystemsTechnology,2009,17(5):1105-1118.
[115] Smith J. Distance and path: the development, interpretation and application of distancemeasurement in mapping and modeling. PhD Thesis, University of London,2003.
[116] Jaillet L., Cortes J. and Simeon T. Sampling-based path planning on configuration-spacecostmaps. IEEE Transactions on Robotics,2010,26(4):635-646.
[117] Jaillet L., Yershova A., Lavalle S. M. and Simeon T. Adaptive tuning of the sampling domain fordynamic-domain RRTs. Proceedings IEEE International Conference on Intelligent Robots andSystems,2005:2851-2856.
[118] Yershova A., Jaillet L., Simeon T. and LaValle S. M. Dynamic-domain RRTs: efficientexploration by controlling the sampling domain. Proceedings of the IEEE InternationalConference on Robotics and Automation,2005:3856-3861.
[119] Lindemann S. R. and LaValle S. M. Steps toward de-randomizing RRTs. IEEE4thInternationalWorkshop on Robot Motion and Control.2004:271-277.
[120] Cheng P., Frazzoli E. and LaValle S. M. Improving the performance of sampling-based plannersby using a symmetry-exploiting gap reduction algorithm. proceedings IEEE International Conference on Robotics and Automation.2004:4362-4368.
[121]康亮,赵春霞,郭剑辉.未知环境下改进的基于RRT算法的移动机器人路径规划.模式识别与人工智能,2009,22(3)：337-343.
[122]LaValle S. M. and Kuffner J., Rapidly-exploring random trees:Progress and Prospects. Proceedings of Intnational Workshop on Algorithmic Foundations of Robotics,2000:293-308.
[123]Kuffner J. and LaValle S. M. RRT-connect:an efficient approach to single-query path planning. Proceedings of IEEE International Conference on Robotics and Automation,2000:995-100.
[124]Han L. and Amato N. M. A kinematics-based probabilistic roadmap method for closed chain systems. Algorithmic and Computational Robotics:New Directions,2001:233-246.
[125]Svestka P. and Overmars M. H. Coordinated motion planning for multiple car-like robots using probabilistic roadmaps. IEEE Transactions on Robotics and Automation,1995,1631-1636.
[126]Wang W. and Li Y. A multi-RRTs framework for robot path planning in high-dimensional configuration space with narrow passages. Proceedings of IEEE International Conference on Mechatronics and Automation,2009,4952-4957.
[127]钟建冬,苏剑波.基于概率路标的机器人狭窄通道路径规划.控制与决策,2010,25(12)：1831-1836.
[128]Latombe J. C. Motion planning:a journey of robots, molecules, digital actors, and other artifacts. International Journal of Robotics Research,1999,18:1119-1128.
[129]Chakravorty S. and S. Kumar. Generalized sampling-based motion planners. IEEE Transactions on Systems, Man, and Cybernetics, Part B,2011,41(3):855-866.
[130]Raveh B., Enosh A. and Halperin D. A little more, a lot better:improving path quality by a path-merging algorithm. IEEE Transactions on Robotics,2011,27(2):365-371.
[131]Jaillet L., Corte J. and Simeon T. Sampling-based path planning on configuration-space costmaps. IEEE Transactions on Robotics,2010,26(4):635-646.