期刊首页 优先出版 当期阅读 过刊浏览 作者中心 关于期刊 English

《中国工程科学》 >> 2006年 第8卷 第1期

移动机器人运动规划研究综述

南京理工大学计算机科学与技术系,南京 210094

收稿日期: 2004-09-21 修回日期: 2004-12-23 发布日期: 2006-01-20

下一篇 上一篇

摘要

机器人运动规划是移动机器人导航的核心技术之一。40多年来,运动规划技术发展迅速,涌现出了许多规划算法,但因为环境描述方式差异巨大,技术差别大,实验比较难度较大。在总结机器人发展史上具有典型意义的规划算法的基础上,提出了路径规划算法的评价标准和形式化描述方式,介绍了每种算法的原理或技术,从搜索策略和环境建模的角度将它们分为四大类,分别是基于自由空间几何构造的规划算法、前向图搜索算法、基于随机采样的运动规划算法以及智能化规划算法,并按照提出的标准比较它们的性能。

参考文献

[ 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 链接1

[ 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 链接1

[ 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 链接1

[ 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 链接1

[ 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 链接1

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

[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 链接1

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

[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) 链接1

[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 链接1

[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 链接1

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

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

[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 链接1

[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 链接1

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

[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 链接1

[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 链接1

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

[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 链接1

[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 链接1

[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 链接1

[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 链接1

[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 链接1

[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 链接1

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

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

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

[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 链接1

[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 链接1

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

[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 链接1

[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 链接1

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

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

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

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

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

[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 链接1

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

[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 链接1

[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 链接1

[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 链接1

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

[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 链接1

[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 链接1

相关研究