Journal Home Online First Current Issue Archive For Authors Journal Information 中文版

Strategic Study of CAE >> 2006, Volume 8, Issue 1

Research on Mobile Robots Motion Planning: A Survey

Dept. of Computer Science , Nanjing University of Science and Technology , Nanjing 210094 , China

Received: 2004-09-21 Revised: 2004-12-23 Available online: 2006-01-20

Next Previous

Abstract

Mobile robots motion planning is one of the key technologies in the robot navigation. During the past 40 years of mobile robot development, lots of planning algorithms were proposed. Because of the tremendous difference among environment models and planning methods, it is difficult to compare them experimentally. This survey reviewed the classical planning algorithms in the history of robot development and presented a set of criteria of planners and the formal description of the problem of planning. The paper described each algorithm's principle or main technology in detail and classified the algorithms based on environment model and search strategy. They are classified into four categories, that is, planners based on geometry construction of free spaces, forward graph search algorithms, random sampling-based motion planning algorithms and intelligent planners. Last, The paper compared and summarized their performance and gave an outlook to the future research of the mobile robots motion planning.

References

[ 1 ] Leonard J, Durrant-Whyte H F. Mobile robot localization by tracking geometric beacons [J].IEEE transaction on robotics and automation, 1991, 7(3)376-38 link1

[ 2 ] Nilsson N J. Shakey the robot [R]. Technical Report TR223, SRI International. 1984

[ 3 ] Lozano- Perez T, Wesley An algorithm for planning collision-free paths polyhedral obstacles[J]nicatIo M,1979,22(10):560~570 link1

[ 4 ] Laumond J P, Sekhavat S, Lamiraux F. Guidelines in Nonholonomic Motion Planning for Mobile Robots[M]. Lectures Notes in Control and Information Sciences 229, Springer, 1998

[ 5 ] Niku s b.机器人学导论:分析、系统及应用[M].孙富春,朱纪洪,刘国栋译。北京:电子工业出版社,2004

[ 6 ] Oommen B, Iyengar S, Rao N, Kashyap R.Robot graphs, Part I:The disjoint convex obstacle case[J]. IEEE Journal of Robotics and Automation, 1987, 3(6):672~681 link1

[ 7 ] Liu Y H, Arimoto S. Computation of the tangent graph of polygonal obstacles by moving-line processing[J]. IEEE Transaction on Robotics and Automation1994,10(6):823~830 link1

[ 8 ] Canny J F. A Voronoi method for the piano-movers problem [A]. IEEE International Conference on Robotics and Automation Vol 2 [C].1985.530-535

[ 9 ] Parsons D, Canny J F. A motion planner for multiple mobile robots [A]. IEEE International Conference on Robotics and Automation, Vol 1 [C].1990.8-13

[10] Chen D Z, Szczerba R J, Uhran J J jr. A framed-quad tree approach for determining Euclidean shortest paths in a 2D environment [J]. IEEE Transactions on Robotics and Automation, 1997, 13(5):668-681 link1

[11] Bonet B, Geffner H, Planning as heuristic search [J]Artificial Intelligence, 2001, 129(1-2):5-33 link1

[12] McKeever S D. Path Planning for an Autonomous Vehicle [M]. Master Thesis, MIT, 2000

[13] Orlin J. Network Flows [M]. Prentice Hall, Upper Saddle River, New Jersey, 1993

[14] Papadatos A. Research on Motion Planning of Autonomous Mobile Robot [M].Master Thesis Naval Postgraduate School, 1996

[15] Stentz A. The focussed D´ algorithm for real-time replanning [A]. Proceedings of the International Joint Conference on Artificial Intelligence [C]. August 1995 link1

[16] Khatib O. Real-time obstacle avoidance for manipulators and mobile robots [A]. Proc IEEE Int Conf Robotics and Automation [C].1985 link1

[17] Lavalle S M. Planning Algorithms [M]. University of Illinois, 2004

[18] Halperin D, Kavraki L, Latombe J C. Robot Algorithms, Algorithms and Theory of Computation Handbook [M]. Atallah M J(ed)。 CRC Press,Boca Raton, FL, Chapter 21, 1999

[19] Jean F. Complexity of Nonholonomic Motion Planning[J]. International Journal of Control, 2001, 74(8) link1

[20] Barraquand J, Latombe J C. A monte-carlo algorithm for path planning with many degrees of freedom [A].IEEE Int Conf Robot Autom [C].1990. 1712-1717 link1

[21] Kavraki L, Latombe J. Randomized preprocessing of figuration space for fast path planning [A].IEEE int conf on Robotics and Automation [C]. San Diego1994.2138~2139

[22] La valle S M. Rapidly-exploring random trees:a new tool for path planning [R]. Technical Report TR98l1, Computer Science Dept, lowa State University Oct 1998

[23] Goldberg K. Completeness in robot motion planning[A]. The First Workshop on the Algorithmic Foundations of Robotics [C]. February 1994 link1

[24] Latombe J C. Robot Motion Planning [M].Boston MA:Kluwer. 1991

[25] 符小卫,高晓光。一种无人机路径规划算法研究[J].系统仿真学报,2004,16(1):20~21 link1

[26] Choset H, Burdick J. Sensor based planning I, The generalized Voronoi graph [A].IEEE International Conference on Robotics and Automation, Vol 2 [CI1995.1649~1655

[27] Kambhampati S K, Davis L S. Multiresolution path planning for mobile robots [J]. IEEE Journal of Robotics and Automation, 1986,(RA-2, 3):135~145 link1

[28] Yahja A, Singh S, Stentz A. Recent results in path sanning for mobile robots operating in vast outdoor environments [A]. Proc 1998 Symposium on Image, Speech, Signal Processing and Robotics [C].The Chinese University of Hong Kong, 1998 link1

[29] 吴峰光,奚宏生。一种新的基于切线的路径规划方法[J].机器人,2004,26(3):193-197 link1

[30] Huyn N, Dechter R, Pearl J. Probabilistic analysis of the complexity of A[J]. Artificial Intelligence1980,15(3):241~254

[31] Stentz A. The D´Algorithm for Real-Time Planning of Optimal Traverses [M]. CMU-RI-TR-94-37CMU.1994

[32] Kimmel R, Kiryati N, Bruckstein AM,Multivalued distance maps for motion planning on surfaces with moving obstacles [J] IEEE Transactions on Robotics& Automation,1998,14(3):427~435 link1

[33] Waydo S. Vehicle Motion Planning Using Stream Functions [R], CDS Technical Report 2003-001California Institute of Technology, 2003

[34] Hwang Y K, Ahuja N. A potential field approach to path planning [J]. IEEE Transaction Robotics Automation, February 1992,(1):23-32 link1

[35] 朱向阳,丁汉,熊有伦。凸多面体之间的伪最小平移距离(Ⅱ)机器人运动规划[J].中国科学,E缉,2001,31(3):238~244 link1

[36] Mantegh I, Jenkin M R M, Goldenberg A A Solving the find-path problem:a complete and less complex approach using the BIE methodology [A]. 1997IEEE International Symposium on Computational Intelligence in Robotics and Automation(CIRA´97)[C].1997. 115-121 link1

[37] Xu Bin, Chen D Z, Szczerba R J. A new algorithm and simulation for computing optimal paths in a dynamic and weighted 2-D environment [A].IEEE International Conference on Systems, Man and Cybernetics Vol 1 [C].2000.313-318 link1

[38] Canny J F. The Complexity of Robot Motion Planning[M]. MIT Press, Cambridge, MA,1988

[39] Reif J H. Complexity of the mover´s problem and generalizations [A]. Proc of IEEE Symp on Foundat Comp Sci[C].1979.421~427 link1

[40] Overmars M H. A random approach to motion planning [R]. Utrecht University, Technical Report RUU-CS92-32,1992

[41] Lindemann S R, Lavalle S M. Current issues in sampling-based motion planning [A]. Dario P, Chatila R editors. Proc Eighth Int´I Symp. on Robotics Research [C]. Springer-Verlag,Berlin,2004 link1

[42] Kavraki L, Svestka P, Latombe J, Overmars M Probabilistic roadmaps for path planning in high dimensional configuration spaces[J]. IEEE Transaction on Robotics and Automation, 1996, 12(4):566~580

[43] Wilmarth S, Amato N. Stiller P. MAPRM:A probabilistic roadmap planner with sampling on the medial axis of the free space [A]. IEEE Int Conf on Robotics and Automation [C].1999. 1024-1031 link1

[44] Amato N, Bayazit O, Dale L, Jones C, vallejo D OBPRM:An obstacle-based PRM for 3D workspaces garwal P K, Kavraki L E, Mason M T eds.Robotics:The Algorithmic Perspective [M],AK Peters, Natick. 1998. 155-168

[45] Bohlin R, Kavraki L E. Path planning using lazy PRM[AL. Proc IEEE Int Conf on Robotics and Automation[C].2000.521-528 link1

[46] Nissoux C, Simeon T, Laumond J P. visibility based probabilistic roadmaps [A]. IEEE Int Conf on Intelligent Robots and Systems [C].1999 link1

[47] Mazer E, Ahuactzin J M, Bessiere P. The ariadne´s clew algorithm [J]. Journal of Artificial Intelligence Research,1998,(9):295-316 link1

[48] Hsu D, Latombe J C, Motwani R. Path planning in expansive configuration spaces [J]. Int J Comput Geom&Appl,1999,(4):495-512 link1

[49] La valle S M, Kuffner J. Rapidly-exploring random trees:Progress and prospects [A]. Proc Int Workshop on Algorithmic Foundations of Robotics(WAFR)[C].2000 link1

[50] Kuffner JJ, Lavalle S M. RRT-connect:an efficient approach to single-query path planning [A].Proc IEEE Int´I Conf on Robotics and Automation [C]2000.995~1001 link1

[51] Peng Cheng. Reducing RRT Metric Sensitivity for Motion Planning With Differential Constraints [D]Master Thesis, lowa State University,2001 link1

[52] de Smith J. Distance and Path Interpretation and Application of Distance Measurement in Mapping and Modeling [D]. PhD Thesis, University College, University of London,2003

[53] Urmson C. Locally Randomized Kinodynamic Motion Planning for Robots in Extreme Terrain [D]. PHD Thesis Proposal, CMU, 2002 link1

[54] Bekris K E, Chen BY, Ladd AM, Plaku E, Kavraki L E. Multiple query probabilistic roadmap planning using single query planning primitives [A]. In 2003IEEE/RJS International Conference on Intelligent Robots and Systems(IROS)[C]. Las Vegas, NV.2003.656~661 link1

[55] 张颖,吴成东,原宝龙。机器人路径规划方法综述[J].控制工程,2003,10(增刊):152~155 link1

[56] Nearchou A C. Path planning of a mobile robot using genetic heuristics [J].ROBOTICA,1998,16:575~588 link1

[57] 孙树栋,林茂。基于遗传算法的多移动机器人协调路径规划[J].自动化学报,2000,26(5):673~676 link1

[58] 陈刚,沈林成、复杂环境下路径规划问题的遗传路径规划方法[J].机器人,2001,23(1):40~44 link1

[59] Zadeh L A. Fuzzy Sets [J]. Inf and Control, 1965, 8(3):338-353 link1

[60] Bagchi A, Hatwal H. Fuzzy logic based techniques for motion planning of a robot manipulator amongst unknown moving obstacles [J]. Robotica, 1992,10(6):563~573 link1

[61] Howard A, Seraji H. An intelligent terrain-based avigation system for planetary rovers[J].IEEE Robotics Automation Magazine, 2001, 8(4):9~17 link1

[62] Brooks R A. The role of learning in autonomous robots[A]. Proceedings of the Fourth Annual Workshop on Computational Learning Theory (COLT 91)[C]forgan Kaufmann Publishe1991.5-10 link1

[63] Sukthankar R, Pomerleau D, Thorpe C.Panacea:An Active Sensor Controller for the al vInn Autonomous Driving System [R].CMU-RI-TR-93-09,The Robotics Institute, Carnegie Mellon University, 1993

[64] Batavia P H, Pomerleau D A, Thorpe C E. applying Advanced Learning Algorithms to ALVINN [R]CMU-RI-TR-96-31, Robotics Institute, carnegie Mellon University, 1996

[65] Janglova D. Neural Networks in Mobile Robot Motion[J]. International Journal of Advanced Robot Systems,2004,1(1):15-22 link1

[66] Kassim AA, Kumar B V K v. A neural network architecture for path planning [J]. International Joint Conference on Neural Networks, 1992, 2(June):787~792

[67] 禹建丽, V Broumov,孙增圻,成久洋之。一种快速神经网络路径规划算法[J].机器人,2001,23(3):201~205 link1

[68] 刘成良,张凯,付庄,曹其新,殷跃红。神经网络在机器人路径规划中的应用研究[J].机器人2001,23(7):605~607 link1

[69] De Souza G N, Kak A C. Vision for mobile robot navigation:a survey [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(2):237~267 link1

[70] Urmson C, Anhalt J, Clark M, et al.High Speed ion of Unrehearsed Terrain-Red Team Technology for Grand Challenge [R]. CMU-RI-TR04-37, The Robotics Institute, Carnegie Mellon University, 2004

[71] Volpe R, Baumgatner E, Schenker P, Hayati S Technology development and testing for enhanced mars rover sample return operations [A]. Proc IEEE Aerospace Conference [C]. 2000 link1

Related Research