移动机器人3维路径规划方法综述

摘要
图/表
参考文献
相关文章 (15)

全文: PDF (861 KB) HTML ( ) 输出: BibTeX \| EndNote (RIS)
引用本文:
陈洋, 赵新刚, 韩建达. 移动机器人3维路径规划方法综述[J]. 机器人, 2010, 32(4): 568-576.. CHEN Yang, ZHAO Xingang, HAN Jianda. Review of 3D Path Planning Methods for Mobile Robot. ROBOT, 2010, 32(4): 568-576..

摘要按照建模原理的不同，将目前各种3维路径规划方法分为4类，阐述了各种方法的工作原理，指出了各种方法在不同应用领域的优势和劣势．分别从实时性、动态环境适应性、规划路径的光滑性、全局规划能力以及加入动力学约束的难易程度等方面进行了比较．分析结果指出，基于虚拟势场与导航函数的方法实时性最好，可在局部规划器中优先选用．基于数学优化的方法能够综合考虑各种动力学约束；而基于生物智能的方法虽然便于表达各种棘手的约束，但规划周期太长，只适用于长周期调用．

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	陈洋
	赵新刚
	韩建达

关键词 ： 3维空间, 避障, 环境建模, 动力学约束, 搜索算法, 实时

Abstract：A variety of three-dimensional path planning methods are divided into four categories according to their mod-eling principles.The working principles of those methods are introduced,and the advantages and disadvantages are pointed out in various applications.All of them are compared from the viewpoints whether they can be used in real-time and dy-namic environment,whether they can achieve smooth path and global planning,and whether they can add different dynamic constraints conveniently.Conclusions are drawn from the comparison that the method based on virtual potential field and navigation function is superior to others for its real-time performance and will be a priority in local planners.The method based on mathematic optimization is capable of dealing with a variety of dynamic constraints.In contrast to mathematic op-timization,the bio-inspired one is limited in solutions of long calling cycle for its large planning period although it is efficient to describe intractable constraints.

Key words： three dimensional space obstacle avoidance environment modeling dynamic constraint searching algorithm real-time

收稿日期: 2009-08-21 录用日期: 2010-02-07

TP24

基金资助:国家自然科学基金资助项目（60775056，60705028）

通讯作者: 陈洋 E-mail: chenyang@sia.cn

作者简介: 陈洋（1980- ），男，硕士，讲师．研究领域:机器人路径规划，自主学习．
赵新刚（1978- ），男，博士，助理研究员．研究领域:辅助机器人，最优控制理论．
韩建达（1968- ），男，博士，研究员，博士生导师．研究领域:无人机控制，复杂环境建模，机器人智能发育．

链接本文:

https://robot.sia.cn/CN/ 或 https://robot.sia.cn/CN/Y2010/V32/I4/568

[1] Ladd A M,Kavraki L E.Measure theoretic analysis of probabilistic path planning[J].IEEE Transactions on Robotics and Automation,2004,20(2):229-242.

[2] Hrabar S E.Vision-based 3D navigation for an autonomous helicopter[D].USA:University of Southern California,2006.
[3] LaValle S M.Planning algorithms[M].2nd ed.New York,USA:Cambridge University Press,2006.
[4] Fahimi F.Autonomous robots modeling,path planning,and control[M].Boston,USA:Springer Science+Business Media,LLC,2009.
[5] Kuwata Y,How J.Three dimensional receding horizon control for UAVs[C]//AIAA Guidance,Navigation,and Control Conference.Reston,VA,USA:AIAA,2004:2100-2113.
[6] Yang K,Sukkarieh S.3D smooth path planning for a UAV in cluttered natural environments[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ,USA:IEEE,2008:794-800.
[7] Kim J,Ostrowski J P.Motion planning of aerial robot using rapidly-exploring random trees with dynamic constraints[C]//IEEE International Conference on Robotics and Automation.Piscataway,NJ,USA:IEEE,2003:2200-2205.
[8] Redding J,Amin J N,Boskovic J D,et al.A real-time obstacle detection and reactive path planning system for autonomous small-scale helicopters[C]//AIAA Guidance,Navigation and Control Conference.Reston,VA,USA:AIAA,2007:989-1010.
[9] Williams M,Jones D I.A rapid method for planning paths in three dimensions for a small aerial robot[J].Robotica,2001,19(2):125-135.
[10] Cocaud C,Jnifene A,Kim B.Environment mapping using hybrid octree knowledge for UAV trajectory planning[J].Canadian Journal of Remote Sensing,2008,34(4):405-417.

[11] Jung D,Tsiotras P.Multiresolution on-line path planning for small unmanned aerial vehicles[C]//American Control Conference.Piscataway,NJ,USA:IEEE,2008:2744-2749.
[12] Hwang J Y,Kim J S,Lim S S,et al.A fast path planning by path graph optimization[J].IEEE Transactions on Systems,Man,and Cybernetics,Part A,2003,33(1):121-128.

[13] 肖秦琨,高晓光.基于空间改进犁Voronoi图的路释规划研究[J].自然科学进展,2006,16(2):232-237.Xiao Qinkun,Gao Xiaoguang.A study on path planning based on 3D improved Voronoi diagram[J].Progress in Natural Science,2006,16(2):232-237.
[14] Sakahara H,Masutani Y,Miyazaki F.Real-time motion planning in unknown environment:A Voronoi-based StRRT (SpatiotemporalRRT)[C]//The Society of Instrument and Control Engineers (SICE) Annual Conference.Hongo,Bunkyo-ku,Tokyo,Japan:SICE,2008:2326-2331.
[15] Wu X J,Tang J,Li Q,et al.Development of a configuration space motion planner for robot in dynamic environment[J].Robotics and Computer-Integrated Manufacturing,2009,25(1):13-31.

[16] Carsten J,Ferguson D,Stentz A.3D field D*:Improved path planning and replanning in three dimensions[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ,USA:IEEE,2006:3381-3386.
[17] Sathyaraj B M,Jain L C,Finn A,et al.Multiple UAVs path planning algorithms:A comparative study[J].Fuzzy Optimization and Decision Making,2008,7(3):257-267.

[18] Yang I H,Zhao Y J.Real-time trajectory planning for autonomous aerospace vehicles amidst static obstacles[C]//AIAA's 1st Technical Conference and Workshop on Unmanned Aerospace Vehicles.Reston,VA,USA:AIAA,2002.
[19] Dolgov D,Thrun S,Montemerlo M,et al.Practical search techniques in path planning for autonomous driving[C]//First International Symposium on Search Techniques in Artificial Intelligence and Robotics (STAIR-08).Menlo Park,CA,USA:2008:32-37.
[20] Likhachev M,Ferguson D,Gordon G,et al.Anytime dynamic A*:An anytime,replanning algorithm[C]//Procecdings of the International Conference on Automated Planning and Scheduling (ICAPS).Menlo Park,CA,USA:AAAI,2005:262-271.
[21] Yershova A,LaValle S M.Improving motion-planning algorithms by efficient nearest-neighbor searching[J].IEEE Transactions on Robotics,2007,23(1):151-157.

[22] Kitamura Y,Tanaka T,Kishino F,et al.3-D path planning in a dynamic environment using an octree and an artificial potential field[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ,USA:IEEE,1995:474-481.
[23] Kim J O,Khosla P K.Real-time obstacle avoidance using harmonic potential functions[J].IEEE Transactions on Robotics and Automation,1992,8(3):338-349.

[24] Fahimi F,Nataraj C,Ashrafiuon H.Real-time obstacle avoidance for multiple mobile robots[J].Robotica,2009,27(2):189-198.

[25] Zhang Y,Valavanis K P.A 3-D potential panel method for robot motion planning[J].Robotica,1997,15(4):421-434.

[26] Liu C,Wei Z,Liu C.A new algorithm for mobile robot obstacle avoidance based on hydrodynamics[C]//IEEE International Conference on Automation and Logistics.Piscataway,NJ,USA:IEEE,2007:2310-2313.
[27] Konolige K.A gradient method for realtime robot control[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ,USA:IEEE,2000:639-646.
[28] Oh T S,Shin Y S,Yun S Y,et al.A feature information based VPH for local path planning with obstacle avoidance of the mobile robot[C]//4th International Conference on Mechatronics and Information Technology.Proceedings of the SPIE,vol.6794.Bellingham,WA,USA:SPIE,2007:679425.
[29] Prazenica R J,Kurdila A J,Sharpley R C,et al.Multiresolution and adaptive path planning for maneuver of micro-airvehicles in urban environments[C]//AIAA Guidance,Navigation,and Control Conference.Reston,VA,USA:AIAA,2005:1761-1772.
[30] Weiss B,Naderhim M,del Re L.Global real-time path planning for UAVs in uncertain environment[C]//IEEE International Symposium on Intelligent Control.Piscataway,NJ,USA:IEEE,2006:2725-2730.
[31] Dogan A.Probabilistic approach in path planning for UAVs[C]//IEEE International Symposium on Intelligent Control.Piscataway,NJ,USA:IEEE,2003:608-613.
[32] Shih C L,Lee T T,Gruver W A.A unified approach for robot motion planning with moving polyhedral obstacles[J].IEEE Transactions on Systems,Man,and Cybernetics,1990,20(4):903-915.

[33] Keith G,Tait J,Richards A.Efficient path optimization with terrain avoidance[C]//AIAA Guidance,Navigation and Control Conference.Reston,VA,USA:AIAA,2007:2940-2949.
[34] Yilmaz N K,Evangelinos C,Lermusianx P F J,et al.Path planning of autonomous underwater vehicles for adaptive sampling using mixed integer linear programming[J].IEEE Journal of Oceanic Engineering,2008,33(4):522-537.

[35] Earl M G,D'Andrea R.Iterative MILP methods for vehiclecontrol problems[J].IEEE Transactions on Robotics,2005,21(6):1158-1167.

[36] Cecil T,Marthaler D E.A variational approach to path planning in three dimensions using level set methods[J].Journal of Computational Physics,2006,211(1):179-197.

[37] Cecil T,Marthaler D E.A variational approach to search and path planning using level set methods[R].USA:UCLA CAM,2004.
[38] Singh R,Bussa N.Path planning using Shi and Karl level sets[C]//Proceedings of the 1st International Conference on Robot Conunupication and Coordination.Piscataway,N J,USA:IEEE,2007:2829-2832.
[39] Masehian E,Habibi G.Motion planning and control of mobile robot using linear matrix inequalities (LMIs)[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ,USA:IEEE,2007:4277-4282.
[40] Masehian E,Amin-Naseri M R.A Voronoi diagram-visibility graph-potential field compound algorithm for robot path planping[J].Journal of Robotic Systems,2004,21 (6):275-300.
[41] Miura J.Support vector path planping[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ,USA:IEEE,2006:2894-2899.
[42] Shanmugavel M,Tsonrdos A,Zbikowski R,et al.3D path planning for multiple UAVs using pythagorean hodograph corves[C]//AIAA Guidance,Navigation and Control Conference.Reston,VA,USA:AIAA,2007:1576-1589.
[43] Twigg S,Calise A,Johnson E.On-line trajectory optimization including moving threats and targels[C]//AIAA Guidance,Navigation,and Control Conference.Reston,VA,USA:AIAA,2004:2019-2030.
[44] Geiger B R,Horn J F,DeLullo A M,et al.Optimal path planning of UAVs using direct collocation with nonlinear programming[C]//AIAA Guidance,Navigation,and Controls Conference.Reston,VA,USA:AIAA,2006:1257-1269.
[45] KanchanavaUy S,Ordonez R,Schumacher C J.Path planning in three dimensional environment using feedback linearization[C]//American Control Conference.Piscataway,NJ,USA:IEEE,2006:3545-3550.
[46] Chen M,Wu Q X,Jiang C S.A modified ant optimization algorithm for path planning of UCAV[J].Applied Soft Computing Journal,2008,8(4):1712-1718.

[47] Hao Y,Zu W,Zhao Y.Real-time obstacle avoidance method based on polar coordination particle swarm optimization in dynamic environment[C]//2nd IEEE Conference on Industrial Electronics and Applications.Piscataway,NJ,USA:IEEE,2007:1612-1617.
[48] Jung L F,Knutzon J S,Oliver J H,el al.Three-dimensional path planning of unmanned aerial vehicles using particle swarm optimization[C]//11th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference.Reston,VA,USA:AIAA,2006:992-1001.
[49] Mittal S,Deb K.Three-dimensional offline path planning for UAVs using mnltiobjective evolutionary algorithms[C]//IEEE Congress on Evolutionary Computation.Piscataway,NJ,USA:IEEE,2007:3195-3202.
[50] Zhang H,Liu M,Liu R,et al.Path planning of robot in three-dimensional grid environment based on genetic algorithms[C] /17th World Congress on Intelligent Control and Automation.Piscataway,NJ,USA:IEEE,2008:1010-1014.
[51] Zhao L,Murthy V R.Optimal flight path planner for an unmanned helicopter by evolutionary algorithms[C]//AIAA Guidance,Navigation and Control Conference.Reston,VA,USA:AIAA,2007:3716-3739.
[52] Allaire F C J,Tarbouchi M,Labonté G,et al.FPGA implementation of genetic algorithm for UAV real-time path planning[J].Journal of Intelligent and Robotic Systems,2009,54(1/213):495-510.
[53] Moreno J A,Castro M.Heuristic algorithm for robot path planping based on a growing elastic net[C]//Lecture Notes in Computer Science,vol.3808.Berlin,Germany:Springer-Verlag,2005:447-454.
[54] Fu X,Gao X,Chen D.A Bayesian optimization algorithm for UAV path planping[C]//2nd International Conference on Intelligent Information Processing.New York,USA:Springer,2005:227-232.
[55] Zapata R,Lepinay P.Flying among obstacles[C]//3rd European Workshop on Advanced Mobile Robots.Piscataway,NJ,USA:IEEE,1999:81-88.
[56] Mohandas S U,Mogre A M,McLaren R W,et al.A robot path planning algorithm using fuzzy goal programming[C]//Proceedings of the SPIE,vol.1293.Bellingham,WA,USA:SPIE,1990:1039-1049.
[57] Tian J,Gao M,Lu E.Dynamic collision avoidance path planping for mobile robot based on multi-sensor data fusion by support vector machine[C] /IEEE International Conference on Mechatronics and Automation.Piscataway,NJ,USA:IEEE,2007:2779-2783.
[58] Mettler B,Toupet O.Receding horizon trajectory planning with an environment-based cost-to-go function[C]//44th IEEE Conference on Decision and Control,and the European Control Conference.Piscataway,NJ,USA:IEEE,2005:4071-4076.
[59] Shi C,Bu Y,Lin J.Mobile robot path planning in threedimensional environment based on ACO-PSO hybrid algorithm[C]//IEEE/ASME International Conference on Advanced Intelligent Mechatronics.Piscataway,NJ,USA:IEEE,2008:252-256.
[60] Bruijnen D,van Helvoort J,van de Molengraft R.Realtime motion path generation using subtargels in a rapidly changing environment[J].Robotics and Autonomous Systems,2007,55(6):470-479.

[61] Sfeir J,Kanaan H Y,Saad M.A neural-network-based path generation technique for mobile robots[C]//IEEE International Conference on Mechatropics.Piscataway,NJ,USA:IEEE,2004:176-181.