Review of 3D Path Planning Methods for Mobile Robot
CHEN Yang1,2,3, ZHAO Xingang1, HAN Jianda1
1. State Key Laboratory of Robotics, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China; 2. College of Information Science and Engineering, Wuhan University of Science and Technology, Wuhan 430081, China; 3. Graduate School of the Chinese Academy of Sciences, Beijing 100049, China
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.
 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.
 Hrabar S E.Vision-based 3D navigation for an autonomous helicopter[D].USA:University of Southern California,2006.
 LaValle S M.Planning algorithms[M].2nd ed.New York,USA:Cambridge University Press,2006.
 Fahimi F.Autonomous robots modeling,path planning,and control[M].Boston,USA:Springer Science+Business Media,LLC,2009.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 肖秦琨,高晓光.基于空间改进犁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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 Yershova A,LaValle S M.Improving motion-planning algorithms by efficient nearest-neighbor searching[J].IEEE Transactions on Robotics,2007,23(1):151-157.
 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.
 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.
 Fahimi F,Nataraj C,Ashrafiuon H.Real-time obstacle avoidance for multiple mobile robots[J].Robotica,2009,27(2):189-198.
 Zhang Y,Valavanis K P.A 3-D potential panel method for robot motion planning[J].Robotica,1997,15(4):421-434.
 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.
 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.
 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.
 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.
 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.
 Dogan A.Probabilistic approach in path planning for UAVs[C]//IEEE International Symposium on Intelligent Control.Piscataway,NJ,USA:IEEE,2003:608-613.
 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.
 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.
 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.
 Earl M G,D'Andrea R.Iterative MILP methods for vehiclecontrol problems[J].IEEE Transactions on Robotics,2005,21(6):1158-1167.
 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.
 Cecil T,Marthaler D E.A variational approach to search and path planning using level set methods[R].USA:UCLA CAM,2004.
 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.
 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.
 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.
 Miura J.Support vector path planping[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ,USA:IEEE,2006:2894-2899.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 Zapata R,Lepinay P.Flying among obstacles[C]//3rd European Workshop on Advanced Mobile Robots.Piscataway,NJ,USA:IEEE,1999:81-88.
 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.
 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.
 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.
 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.
 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.
 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.