多移动机器人路径规划技术的研究现状与展望

1、 收稿日期:2007-08-15作者简介:李艳宏(1978-,女,兰州理工大学在读研究生,主要研究方向为机械制造及自动化。多移动机器人路径规划技术的研究现状与展望邬再新,李艳宏,刘涛(兰州理工大学 机电工程学院,甘肃 兰州 730050摘要:移动机器人技术研究中的一个重要领域是路径规划技术。所谓移动机器人路径规划是指各机器人在同一工作空间中规划一条避障导航的运动路径,保证每一时刻机器人与机器人之间无碰撞、机器人与环境障碍物之间无碰撞。从单机器人到多机器人的路径规划已有很多算法,首先从多机器人协作性质、环境信息和机器人结构三方面分别介绍多机器人路径规划方法,主要有全局路径规划方法、局部路径规划方

2、法、集中式路径规划方法、分布式路径规划方法、混合式路径规划方法,再指出各种方法的优点和不足,最后对多移动机器人路径规划技术的发展趋势进行展望:传统的规划方法和新的智能方法的结合;多传感器融合;性能指标的提高。关键词:多移动机器人;路径规划;神经网络控制;模糊控制;遗传算法;全局路径规划;局部路径规划 中图分类号:TP24 文献标识码:A 文章编号:1006-0316(200801-01-04Research progress and future development on path planning for multi-robotWU Zai-xin ,LI Yan-hong ,LIU T

3、ao(Lanzhou university of Technology Electric and Mechanical engineer ,Lanzhou 730050,ChinaAbstract :Mobile robot path planning technology is one of the important domains in mobile robot technologies research. Mobile path planning is that robots reach goal point from the beginning point in unknown en

4、vironment during the path planning, nocollidance among robots and stumbling blocks. The path-planning from single robot to multi-robot has many algorithms, this article introduces the path planning from coordination, environment information and robot architecture: such as global path planning, local

5、 path planning, concentrated path planning, decentralized path planning and blended path planning. In addition ,the advantages and disadvantages of these algorithms are pointed out. At last, the trend of multiple mobile robots path planning is described: traditional and intelligent path planning int

6、egrated; multi-sensor amalgamated; capability index improved. Key words :multiple mobile robot ;path planning ;neural network control ;fuzzy control ;genetic algorithms ;global path planning ;local path planning智能移动机器人是一类通过传感器感知环境和自身状态,实现在有障碍物的环境中面向目标的自主运动,从而完成一定作业功能的机器人系统1,2。近年来,随着机器人生产线的出现及柔性制造系统的

7、应用,研究人员对由多个机器人组成的系统越来越感兴趣,分布式多机器人系统已经成为一个活跃的、具有挑战性的研究领域。在多移动机器人系统的研究和开发过程中,路径规划是必须解决的重要问题。所谓多机器人协调避障路径规划,主要是指在同一工作空间中,各自治机器人如何利用环境的信息,规划一条避障导航的运动路径,保证每一时刻机器人与机器人之间无碰撞、机器人与环境障碍物之间无碰撞3。1 移动机器人路径规划方法的分类及现状移动机器人路径规划主要要解决三个问题:使机器人能从初始点运动到目标点;用一定的算法使机器人能够绕开障碍物,并且经过某些必须经过的点;在完成以上任务的前提下,尽量优化机器人的运行轨迹。1.1 按协调

8、性质划分的路径规划方法多机器人协作路径规划的算法很多,按机器人协作的性质大致可分为:基于显式协作的多机器人路径规划和基于隐式协作的多机器人路径规划。基于显式协作的多机器人路径规划:主要是指当机器人遇到动态障碍物,首先要辨别它是一般障碍物还是别的机器人,如果动态障碍物是机器人,它们通过通讯协商确定各自的运动策略。显式协作主要侧重于通讯及协商机制的研究。基于隐式协作的多机器人路径规划:主要是从单机器人路径规划发展起来的,为了避免与静态、动态障碍物碰撞,机器人只要遇到障碍物就执行预先定义好的应激性避障策略,而不考虑动态障碍物是不是机器人。目前比较有影响的多机器人隐式协作的路径规划方法有:人工势场法、

9、模糊控制方法等,它们都是单机器人规划方法的扩展。1.2 按环境信息划分的路径规划方法根据环境信息的完整程度,路径规划方法分为:全局路径规划、局部路径规划以及环境不完全确定型路径规划4,5。全局路径规划:指在全局环境信息已知的情况下,给机器人规划出一条从起点至终点的运动路径。该法通常可以寻找最优解,但需要预先知道准确的全局环境信息,计算量大,实时性差,不能较好地适应动态非确定环境。基于环境建模的全局路径规划的方法主要有:可视图法、切线图法、Voronoi 图法、拓扑法、惩罚函数法、栅格法等。局部路径规划:前提是动态时变环境条件下,侧重考虑机器人在未知环境中通过传感器探知局部环境,自主地进行导航。

10、由于仅依靠局部信息,有时会产生局部极值点或振荡无法保证机器人顺利到达目标点。局部路径规划的方法主要有人工势场法、模糊逻辑算法、遗传算法、人工神经网络法、模拟退火算法、蚁群优化算法、粒子群算法和启发式搜索法等6。环境不完全确定型路径规划:指在全局环境已知、但其它机器人信息未知条件下,将全局规划路径与实时规划路径相结合的规划方法。此方法试图结合全局和局部方法的优点,前面提到的人工势场法和模糊方法均可归入局部路径规划和环境不完全确定型路径规划。1.3 按机器人控制结构划分的方法根据多机器人规划的体系结构可将多机器人路径规划方法分为:集中式、分布式、混合式。集中式体系结构7:指多机器人上层具有统一的规

11、划单元,规划单元在对环境和任务充分理解的基础上,对每台机器人要走的路线进行评估和规划,以保证系统总的执行代价最小。集中式结构的优点在于理论背景清晰,实现起来较为直观,系统的协调性较好,但也存在许多缺点:容错性差、柔性差、实用性差、适应性差,另外还存在集中规划单元和机器人之间的通讯瓶颈问题,以及当任务复杂时集中规划的复杂度和计算量增长迅速等问题。分布式体系结构:指整个系统没有集中协调器,每个机器人作为一个Agent810,具有独立的观察、通讯、判断、决定等高度自主自治能力,遇到冲突时,可通过通讯或局部感知同其它机器人协商解决。各机器人独立运作,通过各自的动作互相影响,彼此制约,从而实现协同作业,

12、完成相对复杂的任务。与集中式控制相比,分布式控制具有所需全局知识更少、系统柔性增加、完成任务更高效、容错能力更强等优点,所以日益成为多机器人研究的发展趋势。其缺点是全局规划性差,大量的信息交互受到通讯瓶颈的限制。混合式结构:又叫分布决策-中央协调结构,每一台机器人都具有对当前规划评价的能力和更改运动规划的权利1114。系统进行初始规划,根据规划机器人开始运动。但在运动过程中,每台机器人根据环境信息和自身状态,从自身局部利益出发对当前的行动路线进行评估,如果发现了更有利于自身的运动规划,则把新的规划意见提交给中央协调器。中央协调器对每台机器人的“提议”进行总体评估和决定,如果某提议对系统整体没有

13、损害,或者能获得更好的系统效益,那么该提议就被采纳;否则该提议被否决,系统仍按照原有规划行动15。这种模式能够发挥每台机器人的能力,弥补中央规划时的缺陷是系统更加适应不确定性环境。然而,它还需要一个中央协调器,不具备完全的自治能力。2 移动机器人路径规划新的发展趋势随着移动机器人应用范围的扩大,对于规划技术的要求也越来越高,单个规划方法有时不能很好地解决某些规划问题,所以新的发展趋向于将多种方法相结合,对此可从以下几方面进行探讨。2.1 传统规划方法与新的智能方法之间的结合近年来,一些新的智能技术逐渐被引入到路径规划中来,也促使了各种方法的融合发展,例如人工势场与神经网络、模糊控制的结合等,其

14、中Kyun Y16的混合控制结构先用神经网络对环境进行分类以避免陷入局部最小,并建立基于反应式行为的控制器,再根据势场法选择一个特定的反应式行为来引导移动机器人前进,该结构有较好的鲁棒稳定性,对动态环境具有一定的适应性。Mbede J B17设计了一种融合了模糊逻辑和人工势场函数的模糊控制器,解决了已知环境中存在未知动态障碍的规划问题,较大提高了运动规划的效率,适合于实时应用。2.2 多传感器信息融合用于路径规划移动机器人在动态环境中进行路径规划所需的信息都是从传感器得来18。单传感器难以保证输入信息的准确与可靠。多传感器所获得的信息具有冗余性、互补性、实时性和低代价性,且可快速并行分析现场环

15、境19。目前方法有采用概率方法表示信息的加权平均法、贝叶斯估计法、多贝叶斯法、卡尔曼滤波法、统计决策理论法、仿效生物神经网络的信息处理方法、人工神经网络法等20。2.3 路径规划的性能指标要不断提高路径规划的性能指标包括:实时性、安全性和可达性等。在动态环境中,由于环境信息时刻变化,如果移动机器人实时性差,滞后于动态环境,就可能会导致避障失败21。安全性和可达性也很重要。一个性能指标不好的方法,即使它能使移动机器人走出完美的轨迹,也将被淘汰。如何使性能指标更好是各种算法研究的一个重要方面。3 结论总结目前的研究可以看出:对于各种规划方法的改进有这样一个趋势把某几种方法相互结合,因此怎样把各种方

16、法的优点融合到一起以达到更好的效果是一个有待探讨的问题;目前大多数规划方法都只针对固定目标点而没有考虑移动目标点的情况,此时的规划由于要考虑机器人及目标的位置信息和速度信息而更加复杂,这方面研究也是今后发展的重点。综上所述,多移动机器人的路径规划技术研究已经取得了丰硕成果。但各种方法各有优缺点,没有一种方法能适用于任何场合。随着科技不断发展,多机器人应用领域还将不断扩大,移动机器人路径规划这一课题领域还将不断深入。在研究这一领域时,要结合以前的研究成果,把握发展趋势,以实用性作为最终目的,不断推动其向前发展。参考文献:1欧青立,何克忠. 室外智能移动机器人的发展及其相关技术研究J.机器人,20

17、00,22(6:519-526.2蔡自兴,贺汉根,陈虹. 未知环境中移动机器人导航控制研究的若干问题J. 控制与决策,2002,17(4:385-390.3李磊,叶涛,谭民,等. 移动机器人技术研究现状与未来J. 机器人,2002,24(5:475-480.4Y. UNY CAO. Cooperative Mobile Robotics: Antecedents and DirectionsJ. Autonomous Robotics,1997,(4:7-27.5孟庆浩,彭商贤,刘大维. 基于Q-M 图启发式搜索的移动机器人全局路径规划J. 机器人,1998,20(4.6蔡自兴. 人工智能原理

18、及其应用M. 北京:清华大学出版社,2003.7Suh I H,Yeo H J,et al. Design of a Supervisory Control System for Multiple Robotics SystemsJ. IEEE IROS96,1996:332-339.8Kamada T,Oikawa K,Amadeus. A Mobile, Autonomous Decentralized Utility System for Indoor TransportationJ. Proc. IEEE Int. Conf. Robot. Automat.,1998(5:2229-2

19、236.9Tao W M,How K Y. A Decentralized Approach for Cooperative Sweeping by Multiple Mobile RobotsJ. IROS'98 Proc. IEEE Int. Conf. Intell. Robot. Syst.,1998:380-385.10Azarm K G Schmidt. A Decentralized Approach for the Conflict-free Motion of Multiple Mobile RobotsJ. IEEE IROS96,1996:1667-1675.11

20、陈卫东,董胜龙,等. 基于开放式多智能体结构的分布式自主机器人系统J. 机器人,2001,23(1:45-50.12Parker L E,ALLIANCE. An Architecture for Fault Tolerant Multi(下转第16页才对,但压力在模拟过程中有类似滑移速度的剧烈变化,仅仅弹性形变无法解释这一情况。这种情况我们可以看成,当牵引力作用在滑块上时,由于滑块与基底之间的粘着形变导致接触处分子之间的相互作用发生变化,使得压力在短时间迅速降低至静止状况压力值的附近。3 结论本文利用分子动力学方法,用一个简单的模型,通过对滑移速度、摩擦力以及压力的研究,来探讨粘滑现象产生的

21、起因。结果表明:粘滑现象是一个基底和滑块的分子之间集体作用的结果,特别是相接触处分子之间的作用,当滑块静止在基底上时,随着牵引力的增大,压力由于基底与滑块的相互粘着作用而迅速减小,而当牵引力大于最大静摩擦力时,粘着被破坏,滑块与基底分离,同时压力也随之恢复到正常状况。因此,我们认为:原子尺度下相接触物体之间的粘着分离是导致粘滑现象的主要原因。参考文献:1Mate,C.M.,McClelland,G.M,Erlandsson,R. Atomic-scale friction of atungsten tip on a graphite surfaceJ.Phys. Rev. Lett. 1987

22、,59:194 -245.3Riedo,E,Gnecco,E,Bennewitz,et al. Interaction Potential and Hopping Dynamics Governing Sliding FrictionJ. Phys. Rev. Lett.91, 084502(2003.5Reimann,P,and Evstigneev M. Nonmonotonic Velocity Dependence of Atomic FrictionJ. Phys. Rev. Lett. 93,230802(2004.8Sills,Sand. and Overney,R.M. Cre

23、eping Friction Dynamics and Molecular Dissipation Mechanisms in Glassy PolymersJ. Phys. Rev. Lett. 91,095501(2003.11Persson,B.N. J. Friction dynamics for curved solid surfaces with long-range elasticityJ. J. Chem. Phys.113(13,5477.(2000. 12Luengo,Gustavo,Israelachvili,Jacob,Granick Steve. Generalize

24、d effects in confined fluids: new friction map for boundary lubrationJ. wear 200 (1996 328.13Aranson,I.S.,Tsimring,L.S. and Vinokur,V. M. Stick-slip friction and nucleation dynamics of ultrathin liquid filmsJ. Phys. Rev. B. 65. 125402 (2002.14Budakian,Raffi. and Putterman,Seth. J. Time scales for co

25、ld welding and the origins of stick-slip frictionJ. Phys. Rev. B. 65. 235429(2002.15Schirmeisen,A.,Jansen,L,and Fuchs.H. Tip-jump statistics of stick-slip frictionJ. Phys. Rev. B,71.245403(2005.robot CooperationJ. IEEE Transactions on Robotics and Automation, 1998,14(2:220-240.13Ueyama T,Fukuda T,Sa

26、kai A et al. Hierarchical Control Architecture with Learning and Adaptation Ability for Cellular Robotic SystemJ. Distributed Autonomous Robotic Systems,1994:16-28. 14Laengle T,Lueth T C,Rembold U,A Distributed Control Architecture for Autonomous Robot Systems,Modelling and Planning for Sensor Based Intelligent Robo