1、I摘要智能移动机器人技术是机器人学中的一个重要分支，是一项有着广阔应用前景的高新技术，从工业制造领域到服务业，军事侦察、核工业、航空航天、服务业、医疗器械、基因工程等诸多领域，移动机器人技术都大有发展空间。机器人技术作为多学科融合的高科技技术，其运动环境的多变性和复杂性，决定了移动机器人路径规划问题是机器人领域一个研究重点，也是机器人实现智能化的关键技术。路径规划问题作为移动机器人研究中一个最基本最关键的课题，它解决移动机器人如何在环境中行走的问题。路径规划在机器人研究中不是独立的，同时还涉及到机器人领域的其它方面，如机器人的感知、通信及协调协作机制等，所以它是一个综合性的研究课题。本文针对移
2、动机器人路径规划问题展开研究，并通过仿真验证证明了所提出理论及方法的有效性。本文首先对国内外智能移动机器人的研究现状和发展趋势进行了分析，介绍了多机器人系统的体系结构及编队控制方法，并对己有的路径规划方法进行了分类总结，为进一步研究机器人路径规划问题作了准备。其次在对移动机器人控制系统进行介绍分析的基础上，阐述了经典人工势场法路径规划原理，分析了传统人工势场方法存在的缺陷，解决了其中的若干问题，优化了算法。关键词移动机器人；人工势场法；路径规划；编队控制IIABSTRACTTHETECHNOLOGYOFMOBILEROBOTISANIMPORTANTBRANCHOFROBOTICSITSANA
3、DVANCEDTECHNOLOGYWHICHHASEXPANSIVEAPPLICATIONFIELDSFROMINDUSRIALMANUFACTURETOMILITARYSPY,SERVICES,NUCLEARINDUSTRY,AVIATIONANDSPACEFLIGHT,SERVICEINDUSTRY,MEDICALINSTRUMENT,GENEENGINEERING,ETC,MOBILEROBOTHASGREATDEVELOPMENTSPACEINALLOFTHESEFIELDSROBOTICS,ASAMULTISUBJECTSYNCRETIZEDHIGHTECHSCIENCE,ISCER
4、TAINLYDIFFICULTTOREASEACHFORTHEDIVERSITYANDCOMPLEXITYOFTHEENVIRONMENT,PATHPLANNINGHASBEINGANIMPORTANTASPECTINTHEMOBILEROBOTICREASERCHFILEDANDALSOACRUCIALTECHNOLOGYTOINTELLIGENTIZETHEROBOTPATHPLANNINGPROBLEMISONEOFTHEMOSTBASICANDPIVOTALASPECTSINTHERESEARCHOFMOBILEROBOTITSTASKISTOSOLVETHEPROBLEMOFHOWT
5、OMOVEINTHEENVIRONMENTFORROBOTITSRELATIVEWITHMANYOTHERASPECTS,SUCHASTHESENSEPROBLEM,COMMMUNTAIONSYSTEMANDRULESOFCOLLABORATIONTHISTHESISDOESTHERESEARCHONTHEPATHPLANNINGPROBLEMFORMOBILEROBOTTHERESULTSOFSIMULATIONDEMONSTRATETHEVALIDITYOFPROPOSEDTHEORYANDMETHODSTHEMAINLYCOMMENTANDACHEIEVEMENTSOFTHETHESIS
6、AREASFOLLOWSFIRSTOFALL,THISTHESISANALYSESTHESTATUSANDDEVELOPMENTTRENDISELABORATEDANDSUMMARIZEDOFINTELLIGENTMOBILEROBOTATHOMEANDABROADITISINTRODUCEDTOTHENAVATIONTECHNOLOGYOFTHEMOBILEROBOTTHENECESSARYTECHNOLOGYOFMODELINGANDSENSINGOFMOBILEROBOTISSUMMARIZEDINADDITION,THEEXISTEDPATHPLANNINGMETHODSARESTOR
7、EDANDSUMMARIZEDALLTHESEMAKEAGOODPREPARATIONFORTHERESEARCHONTHEPATHPLANNINGPROBLEMOFMOBILEROBOTSECOND,ITANALYSESTHECLASSICALARTIFICIALPOTENTIALFIELDOFPATHPRINCIPLEONTHEBASISOFDESCRIBINGTHEMOBILEROBOTFORMATIONCONTROLTHISTHESISSOLVESANUMBEROFMETHODSFLAWEDOFTRADITIONALARITICIALPOTENTIALFIELDANDOPTIMIZES
8、THEALGORITHMKEYWORDSMOBILEROBOTARTIFICIALPOTENTIALFIELDPATHPANINGFORMATIONCONTROL沈阳理工大学学士学位论文11绪论11课题背景及意义随着机器人的工作环境从结构化的工厂车间扩展到了非结构化的一般性环境，机器人的控制方式也从预编程控制方式发展到了基于人工智能和自主控制方法。非结构化的应用场合拉动了机器人对智能和自主能力的需求。在一些应用场合，单一的机器人受个体能力和可靠性等诸多因素的制约，有时难于应对复杂的工作内容。此时通过多个机器人之间的协作来完成某些单个机器人难于完成的使命，作为对个体机器人能力的补充，多机器人协作
9、可以有效地提高个体机器人在能力、效率、可靠性等方面的不足。因此机器人的协调合作能力已经成为评价机器人智能和自主能力的一个重要方面。当前，在操作大型物体，军事侦察，自动搬运等领域多机器人协调控制技术已经得到了应用。机器人技术的发展目前大致正沿着两个重要的方向一是针对提高单个机器人性能的研究方向，另一个则是适应复杂任务要求的多机器人系统的研究方向。进行多机器人系统的研究是机器人技术发展的必然趋势，必将对机器人技术的发展起重要作用。今后随着科技的发展，多机器人系统的应用领域将逐渐向工业、军事领域发展，它的应用将越来越广。在工业中，多机器人系统的柔性可极大地加快企业的转产速度，实现柔性加工；在国防中，
10、它可以实现无人飞机和无人坦克代替军队进行作战，最大限度地减少人员伤亡。可以预见多机器人系统的应用将会对社会带来巨大变革，能极大地提高人们的生活质量以及工农业和国防现代化程度。中国工程院院长宋健指出“机器人学的进步和应用是20世纪自动控制最有说服力的成就，是当代最高意义上的自动化”。编队，是指多机器人在到达目的地的过程中，保持某种队形，同时又要适应环境约束例如存在障碍物或者空间的物理限制的控制技术。在编队控制中，一方面要绕开各种障碍物向目标移动；另一方面还要保持队形不变。因此，编队控制是一个典型且通用的多机器人协调问题，是多机器人协调控制的基本。12编队控制研究的发展方向编队控制具有广阔的应用范
11、围，特别是在军事应用及航空航天等领域，在沈阳理工大学学士学位论文2目前研究工作的基础上，今后编队控制研究的方向主要有以下几个方面机器人队形控制是依赖于单个机器人控制之上的，所以与单个机器人能力相关。如与传感信息处理、定位方法研究、导航方法、控制结构、通信等方面的研究密切相关。如何用简单有效的方法实现队形控制，以及用较少的代价实现大量机器人队形控制是一个研究方向。机器人之间高效的协调方法的研究以及加入机器人后的机器人队形控制也是值得关注的问题。自适应的队形控制研究即如何根据任务、环境和约束自适应地进行队形控制；如何将机器人自身处理问题的能力与群体处理问题的能力互为补充。机器人队形控制主要应用于搜
12、索、防卫、围捕等军事用途，以及合作搬运、航空航天中的虚拟探测等。13论文总体结构本论文主要由以下几个方面组成1多机器人编队控制方法2多机器人编队基本问题研究3多机器人编队行为4多机器人系统体系结构5改进的人工势场法原理以及局部稳定问题14论文主要研究内容本论文在对移动多机器人控制系统进行介绍分析的基础上，阐述了在静态环境中经典人工势场法路径规划的原理，并且分析了传统人工势场法存在的缺陷，解决了其中若干问题，优化了算法。针对人工势场法障碍物附近目标不可达问题，在分析了斥力函数的基础上，建立了新的斥力函数，从而使得机器人能够顺利地到达目标。并且针对人工势场法固有的局部稳定问题，通过设置中间目标点的
13、方法，使移动机器人在到达局部稳定点的时候，能够顺利地跳出稳定点，从而达到目标。沈阳理工大学学士学位论文32多机器人编队控制方法21多机器人编队的优点多机器人保持一定的队形前进，可以有许多好处（1）更加准确、有效的获取环境信息。由于机器人的硬件约束如传感器的精度和能力、噪声的干扰等，单个机器人很难准确地获取环境信息。当多个机器人保持一定的队形，其中每个机器人都负责相应的职责，那么在有效通讯的范围内，将不同机器人获得的信息融合起来，可以获得更多的环境信息。在多机器人协调探测环境过程中，通过贝叶斯理论的概率模型，可以逐渐增加单个机器人对环境认识的可信度，从而更加有效地识别环境形状。（2）提高工作的效
14、率。首先，单个机器人能力有限，完成任务需要花费很长的时间。从这个角度来看，多个机器人就已经提供了并行执行任务的能力，因而可以提高工作的效率。另外，在搬运物体的过程中，多个机器人编排固定的队形，才可以将物体推动到目标位置。而且单个机器人不一定有能力完成这些任务，此时多机器人的协作更加重要。（3）增加抵抗外界入侵的能力。在机器人军队中，机器人通过组成一种或多种编队形状，可以有效地抵抗外界的干扰。同样，通过保持队形，可以保护重要的对象，以达到相应的目标。（4）增加系统的鲁棒性。在编队中，机器人受到队形向量的约束，即使在行进过程中出现死锁或停滞现象，其他机器人都可以通过这些约束将该机器人从死锁的状态中
15、摆脱。（5）有助于机器人之间的合作。在队形保持中，机器人满足队形约束，如距离约束。在距离约束之下，机器人通过视觉等辅助传感器得知其他机器人的信息，以便给出相应的对策或决策。沈阳理工大学学士学位论文422多机器人编队的基本问题221任务描述R3LR2FR1FR4FO1GOALO2运动方向转向方向图21多机器人工作区间模型如图31所示，为了完成指定任务，多个同构机器人将在未知环境中完成编队控制，具体包括运动到指定位置形成某种队形、保持队形运动到某一位置、在保持队形过程同时完成避障等其他任务。222多机器人编队的基本队形在机器人编队过程中，需要解决很多问题。其中，首先要解决的问题是机器人队形的选择问
16、题。选择合理的队形，对机器人系统执行任务的性能有着很大的影响。例如在障碍密集的地区，柱形可以灵活的避开障碍物。通常，机器人编队的基本队形有线形、柱形、菱形和V形楔形这四种对称的形状，如图22所示A线形B柱形C菱形DV形图22多机器人基本队形在编队运行过程中，机器人队形并不是一成不变的，各种队形在不同的情况下队形保持的效果不同。沈阳理工大学学士学位论文523多机器人编队控制方法231产生式方法产生式方法的实现是通过给定多机器人一些IFTHEN规则，使得当队形不规整的时候，机器人可以很容易的调整自己的位置。它的优点就是反应速度快，因此主要应用于实时性要求比较高的情况。它的缺点就是人为指定的规则可能
17、会遗漏或者冲突，而且不能适用于相对复杂的情况。当环境变得复杂时，规则将非常难以制定，要么制定出来的规则集非常庞大，要么规则的适应性不高。因此，这种方法的适应性和鲁棒性都很差，无法体现多机器人的智能。虽然专家系统和模糊规则等方法对这种方法进行改进，但是这些方法都未能解决这种方法根本问题。232跟随领航者法跟随领航者法的基本思想是在多机器人组成的群体中，某个机器人被指定为领航者，其余作为它的跟随者，跟随者以一定的距离间隔跟踪领航机器人的位置和方向。对该方法进行拓展，即不仅可以指定一个领航者，也可以指定多个，但整体队形的领航者只有一个。根据领航者与跟随机器人之间的相对位置关系，就可以形成不同的网络拓
18、扑结构，也就是说，形成不同的队形。该方法中，协作是通过共享领航机器人的状态等知识实现的。233基于行为法基于行为是指机器人个体采用基于行为的体系结构。基于行为法的基本思想是首先为机器人定义一些期望的基本行为，一般情况下，机器人的行为包括避碰、避障、沿墙行走、驶向目标和保持队形等。当机器人的传感器接受到外界环境刺激时，根据传感器的输入信息做出反应，并输出反应向量作为该行为的期望反应例如，方向和运动速度。行为选择模块通过一定的机制来综合各行为的输出，并将处理结果作为机器人对环境刺激的反应而输出。该方法中，协作是通过共享机器人之间的相对位置、状态等知识实现的，因此通讯是必不可少的。关于行为选择机制的
19、研究，是基于行为主义的多智能体协调研究的热点和核心问题，已经在不同的领域提出了许多算法和理论。目前的行为选择机制主要有三种沈阳理工大学学士学位论文61BROOKS提出的行为抑制法。2ARKIN的加权平均法。3模糊逻辑法。234虚结构法MANTHONYLEWIS首先提出了虚结构法（VIRTUALSTRUCTURE），其基本思想是将机器人团体的队形看作是一个刚体的虚拟结构，每个机器人是虚拟结构上相对固定的一点。当刚体在空间中运动时，虽然刚体上的各点位置在变化，但是他们之间的相对位置保持不变。虚结构基本算法是采用双向控制，首先用虚拟结构尽量匹配个机器人的位置，然后根据局部或全局生成的轨迹，微调虚拟结
20、构的位置和方向，最后机器人确定各自的轨迹并调整速度以跟踪虚拟结构上的目标位置点，如此循环往复。235其他方法2351基于图论法基于图论的队形控制方法的基本思想是图上的节点表示机器人的动力学或运动学特性，节点之间的边表示机器人相互之间的约束；采用图论和控制理论知识对以图形表示的队形进行稳定性分析，进而得到控制策略。这方面研究一般是将图论、控制理论及动态系统理论结合起来研究队形控制方法和稳定性。2352模型预测法WILLIAM分析并设计了将模型预测控制用于多机器人队形控制的理论框架，同时研究了系统的稳定性、鲁棒性以及实时实现等问题。模型预测控制顾及了动态环境的变化和过程的不确定性，用反复进行的有限
21、优化代替了一次全局优化的结果，使预测控制在过程中实现了优化与反馈的理想结合以及对信息的充分利用，通过在线滚动优化并结合实时信息的反馈校正，使每一时刻的优化均建立在实际过程的基础上。预测模型、滚动优化以及反馈校正使得预测控制满足了许多实际需要，取得了很大成功。模型预测法具有较强的理论基础，在实时计算、可扩展以及分布实现等方面还有待进一步的研究。24典型的机器人运动规划方法按照环境的建模方式和路径搜索策略，运动规划算法可以大体上分为三类沈阳理工大学学士学位论文7前向图搜索法、智能化方法和采样法。241前向图搜索法前向图搜索法的基本思想是构造某种图来描述环境的自由空间，从图上找到满足某种规则的最优路
22、径。这种方法一般分为两步第一步构造一个描述自由空间的关系图，第二步按照一定搜索原则（距离最短、时间最少等）利用搜索算法寻找一条最优路径。构造关系图常用的方法有可视图法、VORONOI图法、栅格分解法和切线图法41，搜索算法常用的有贪心算法、DIJKSTRA算法、A算法、D算法和人工势场法。前向图搜索法需要在搜索路径之前对运行环境进行建模过程的方法很直观，理论上存在可行路径的情况下一定能够找到最优路径，但是在环境不断扩大、建模精度不断提高的情况下，计算量将呈指数级增长，运行速度明显放慢。而在可行的精度限制下，有丢失可行路径的可能。242智能化算法随着人工智能技术的发展，将智能化算法应用到运动规划
23、中来，提高运动规划的智能化水平已成为运动规划一个重要的发展趋势，常用到的智能化算法有遗传算法、模糊推理以及神经网络。这些智能化推理方法与前向图搜索算法类似，都需要全局已知环境或大范围已知环境的模型，随着环境复杂度的增加，同样存在内存占用过大、运算效率低的问题。243采样法基于采样的运动规划2仅仅通过对位形空间中的采样点进行碰撞检测来获取障碍物信息，并在此基础上进行运动规划。其中最常见的是随机性采样法，BARRAQUAND和ATOMBEL设计的一种随机路径规划器（RPP）3被认为是随机采样法在运动规划应用方面的开端。近几年概率路标法（PRM）和快速探索随机树（RRTS）得到了深入的研究和广泛应用
24、。沈阳理工大学学士学位论文825多机器人编队行为251奔向目标行为该行为使得机器人向最终目标点运动，对于FOLLOWER来说奔向目标行为是没有意义的，因为跟随者具有保持队形的任务，也就是说只有LEADER具有该行为，定义TGGYX,为队伍最终目标位置，TCCYX,为机器人当前位置，T为转置操作符。式（41）给出奔向目标行为的输出向量MTGV，图31描述了奔向目标的行为。CGCGCGCGMTGYYXXYYXXV22121MTGVTGGYX,TCCYX,V图23奔向目标行为252保持队形行为编队过程要求机器人在遇到障碍物时可以实时避开障碍物，当没有障碍物时就能恢复队形，机器人的队形保持行为同时也实
25、现了队形恢复的功能。大多数会采用动态死区法，首先根据队形计算机器人在期望队形中的位置，根据同期望位置的距离，将整个空间分成三个区域弹道区，控制区和死区，在弹道区机器人采用最大速度，在控制区机器人的速度与距离成正比，进入死区后速度稍大于平均速度，到达目的点时速度等于平均速度，以控制机器人的速度达到保持队形的目的。该方法中LEADER与FOLLOWER之间比较独立，且遇到复杂障碍物或障碍物密集时很难划分空间区域。253躲避静态障碍物行为躲避静态障碍物行为AVOID_STATIC_OBSV在机器人的运动规划有着非常重要的地位，首先静态障碍物数量众多，AVOID_STATIC_OBSV设计的是否合适很
26、大程度上决定着最终运动路沈阳理工大学学士学位论文9径的好坏；其次因为静态障碍物是静止的，在机器人的各种行为中，只有AVOID_STATIC_OBSV是可以精确确定的，在层间信息融合控制结构中的高级层行为中，要根据AVOID_STATIC_OBSV输出的方向和速度为参考量，进行各自行为的计算。在机器人运动规划中，躲避静态障碍物的基本方法有固定角转向法、切线避障法和人工势场法。254躲避机器人行为在多机器人系统中，机器人除了要面对静态环境外，还必须协调好与其他机器人的运动，因此我们在高级层行为中引入了躲避机器人行为，其功能是根据环境中机器人的信息和障碍物的信息，决定机器人如何运动。环境中多个机器人
27、组成队形在前进路径上遇到其他机器人的机会很少，而组成队形的多个机器人在LEADER的协调下能保持队形运动到目标位置，但是由于在一个系统中各种资源是有限的，许多情况下会出现资源冲突，像队形形成阶段分配队形点时机器人都希望分到距离最近的点，过狭窄通道时多个机器人在某个点相遇都希望先通过，变换队形避障中转换成蛇形队形时，各个FOLLOWER存在一个启动顺序的问题等等，我们设计躲避机器人行为以防止机器人之间相互碰撞，使编队控制过程更加理想。255多机器人编队行为融合机制奔向目标行为躲避障碍物行为保持队形行为躲避机器人行为执行器通信传感器环境友邻机器人机器人提供前进方向和运动速度提供前进方向和运动速度提
28、供通行区域和下一步的运动方向图24多机器人编队行为融合机制机器人的功能单元为行为，主体控制结构分为三层，分别是初级层行为，中沈阳理工大学学士学位论文10级层行为和高级层行为。初级层行为在不同的运动阶段有MOVE_TO_GOALV和KEEP_FORMATIONV中的某一种行为与之对应，他们的基本功能是一致的，但具体实现时有所不同，初级层行为的基本功能为控制机器人的整体运动趋势，为后面行为提供运动速度和运动方向，实现以较高的速度和准确度到达目标位置。中级层行为包括躲避障碍物行为，为后面行为提供可通行区域和下一步的前进方向，以便更有效地避开障碍物。高级层行为参考前面行为所提供的运动方向和运动速度，对
29、象为动态。各层行为间信息流单向传递，相互融合，使机器人能更有效地完成编队任务。26多机器人编队中参考点的选取在编队控制过程中，为了保证队形的完整，必须有一个队形的调节机制。即在编队过程中必须要有一个参考点，不同机器人位于参考点的不同位置，从而形成一定的队形。队形保持控制一般可以分两步完成首先是一个感性的处理，称为探测队形位置，根据当前环境信息确定机器人在队形中的正确位置；然后根据一定的控制策略生成控制命令，驱动机器人保持一定的队形驶向目标位置。参考点的选取方法通常有三种（1）以多机器人系统的中心点作为参考点（图26（A）；（2）以群体中的某一个机器人作为参考点（图26（B）；（3）以相邻机器人
30、为参考点（图26（C）。ARKIN曾对这几种方法进行了比较以机器人为参考点在运动过程中队形被打乱的时间较短，而以系统中心点为参考点队形被改变的幅度较小17。A领航参考B中心参考C邻居参考图25队形参考点图A领航参考。从队伍中，选取一个机器人作为领航机器人，其他机器人以该机器人为参考点，只需保持自己与该机器人的相对位姿和期望值相同，就可以沈阳理工大学学士学位论文11保证编队的队形。由于领航机器人没有参考点，所以不考虑队形约束，队形的保持由跟随者实现。B中心参考。根据每个机器人的位置，计算出当前的几何中心。每个机器人都保持同该几何中心的相对位姿，同样也可以保持队形。该方法要求所有机器人知道其他机器
31、人的位姿信息，该方法使用大量的通讯量。C邻居参考。当编队队形确定后，每个机器人可以保持同队形中相邻机器人的相对位姿来达到编队的目标。同前两个方法比较，除了不被选作参考点的机器人不需要广播信息之外，其他机器人都要向环境中发出自己的位姿信息，信息量自然较大。另外，为了识别邻居，对邻居的标识信息也需要通过通讯来告知其他机器人，因此该方法在通讯上消耗了大量的时间。通常，该方法是配合其他传感器进行的。针对不同的队形和选择不同的参考点，队形保持效果就可能不同。根据文献18当队形转弯时，采用单位中心为参考点，菱形队形打乱的时间最短，队形保持效果最好；采用领航机器人位置为参考点，楔形和横队形保持效果较好，柱形
32、编队效果最差。当队形穿越有障碍区域时，柱形编队性能最好。在大多数情况下，选择单位中心为参考点优于选择领航机器人位置为参考点。27多机器人编队中的通讯编队控制中的另一个基本问题是通讯问题。特别是以几何中心和邻居机器人为参考点的队形控制来说，通讯技术事关队形形成的成败。通讯技术虽然发展很快，但不是面向机器人的。从通讯的体系结构上来看有三种形式一是各机器人之间没有精确的相互作用；二是各机器人通过传感器的相互检测获取对方信息，产生局部的相互反应；三是各机器人之间存在精确通讯，用点对点、BLACKBOARD或BROADCAST方式传递信息。在编队控制中，集中控制是一种自上而下的层次控制结构，由一个机器人
33、或计算机集中控制整个系统，这种方式协调性较好，但实时性、动态性较差；分布式控制是一种在全局上各机器人具有一定的自主能力基础上的局部集中的结构方式，系统的灵活性和鲁棒性比集中控制更好。通讯是机器人之间进行交互和组织的基础。通过信息交流，机器人可以详细地了解其他机器人的意图、目标和动作以及当前环境更全面的信息，进而进行有沈阳理工大学学士学位论文12效地磋商，协作完成任务。WANGJING等提出一种媒体接入协议CSMA/CDWCARRIERSENSEMULTIPLEACCESSWITHCOLLISIONDETECTIONFORWIRELESS来支持分布式机器人系统的点到点通信和广播式通信19。与已有
34、的通信系统不同，此系统不需要一个中心服务器或基站的存在，通过共享无线通信通道的方式实现了机器人之间的数据通信，符合多机器人系统的基本特点和要求。虽然近年来无线通讯技术己经得到长足发展,但在目前的技术条件下,多机器人系统实现所有机器人之间的点对点实时通讯还有较大困难，这也是大多数多机器人系统仍然采用集中通讯方式的主要原因。在本文中，我们模拟了基于黑板10的通讯方式。在多机器人系统中，黑板提供了公共信息区，机器人从黑板上读取或往黑板上写入整体控制指令、本地环境信息及本身运行状态。在基于黑板的通讯方式中，很重要的一个方面就是要保证整个系统数据的一致性，防止读取“脏数据”写入数据的机器人没有完全写入而
35、被其它机器人读取的数据。28编队控制中的性能评估为了验证编队算法的好坏，需要对编队算法进行评估。对队形算法优劣的评估主要有三个指标L路径长度比率。该比率定义为队形的平均行走距离同初始位置到达目标位置直线距离的比值。该比值可以用来衡量算法的避障性能，比值越小说明避障性能越好。没有障碍物，理论上该比值为1，没有意义。2队形维持率。在整个编队行进过程中，机器人在期望位置的时间所占的比例。与之相对的概念就是个体偏移率，即机器人在编队过程中不在期望位置的时间比例。该数值可以用来评价算法在避障过程中，队形保持的性能。3运行时间。指机器人在到达目标到形成队形所消耗的时间。该数值可以用来评价算法在队伍避开障碍
36、物或打乱队形后，恢复队形的性能。29多机器人路径规划常用方法自由空间法的基本思想是采用预先定义的基本形状如广义锥形，凸多边形等构造自由空间，并将自由空间表示为连通图，然后通过对图的搜索来规划路径。沈阳理工大学学士学位论文13自由空间法的优点是比较灵活，机器人的起始点和目标点的改变不会造成连通图的重构，但算法的复杂程度与障碍物的多少成正比，且不是任何情况下都能获得最短路径。可视图法是将机器人视为一点，通过起始点和目标点及障碍物的顶点在内的一系列点来构造可视图。连接这些点，使某点与其周围的某可视点相连即使相连接的两点间不存在障碍物或边界。然后机器人对可视图进行搜索，并利用优化算法删除一些不必要的连
37、线以简化可视图，最终就可以找到一条无碰最优路径。该方法的优点是可以求得最短路径，缺点是缺乏灵活性，即一旦机器人的起点和目标点发生改变，就要重新构造可视图。栅格法将机器人的工作空间分成若干栅格，利用传感器测得的信息，确定障碍物位置并映射到相应栅格上。在由这些栅格构成的连通图上搜索一条从起始栅格到目标栅格的路径。在实现上，用一个二维数组表示机器人的工作区域，其中每个元素代表一个栅格。每个栅格具有一个可信度值，用于表示该区域内的障碍物分布状况。该方法比较容易实现，但当栅格数量很大时，规划时间较长。人工势场法把机器人在环境中的运动视为一种在抽象的人工受力场中的运动，即在环境中建立人工势场的负梯度方向指
38、向系统的运动控制方向。把机器人处理成在人工势场影响下的一个点，目标点对机器人产生“引力”，障碍物对机器人产生“斥力“，些力的叠加得到合力，施加于机器人，控制机器人的运动方向，实现平滑地引导机器人趋向目标，同时避免碰撞障碍物。该方法简单，但对存在局部最优解的问题，易陷入局部最小值。遗传算法是以自然遗传机制和自然选择等生物进化理论为基础，构造的一类随机化搜索算法。它模仿生物遗传及进化的步骤，引入选择、复制、交叉重组和变异等方法，并将适者生存的概念引入到算法中。由于宏观上具有一定的方向性，使得它比一般的随机搜索算法的效率要高。作为一种并行算法，其隐含的并行性适用于全局搜索，能搜索到全局最优点。遗传算
39、法克服了人工势场法的局部极小值问题，鲁棒性强，但进化众多的规划要占据较大的存储空间和运算时间。模糊逻辑法是驾驶员避碰动作并非对环境信息精确计算完成的，而是根据模糊的环境信息，通过查表得到规划出的信息，完成局部路径规划。模糊逻辑法模拟驾驶员的驾驶思想，将模糊控制本身所具有的鲁棒性与基于生理学上的“感知，动作“行为结合起来，适用于时变未知环境下的路径规划，实时性较好。神经网络方法是一种仿效生物神经系统的信息处理方法。它是一个高度并行沈阳理工大学学士学位论文14的分布式系统，处理速度高且不依赖于系统精确的数学模型，还具有自适应和自学习的能力。由于路径规划工作没有明显的规划和难以进行事件分类，可以让神
40、经网络通过大量的实例学习来掌握。机器人采用一定的学习算法学习避障行为，学习从地图上不同位置到目标的行走路线，一旦学习完成后，机器人就能够实现自主导航。通过对各种算法的分析和比较，本文选择重点研究利用遗传算法和人工势场法对机器人进行路径规划。作为现实环境中驻留的智能体，机器人与外界环境交互需要解决基本的三个问题我在哪里应该去哪里如何到达那里对于此类问题的研究称为导航技术，而最后一个问题涉及机器人的路径规划，它是导航研究的一个重要环节和课题。所谓路径规划，可以描述为在有障碍物的工作环境中，如何为机器人寻找一条从起点到目标点的最优或次优路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物，到达
41、目标点。路径的性能指标有距离、时间、能量、安全等。与单机器人相比，多机器人的路径规划不仅要求每一个机器人各自寻找一条上述的路径，还要求机器人沿该路径行走时避免与其它机器人发生碰撞，从而对机器人之间路径的规划和协凋提出了更高的要求。因此，多机器人路径规划具有如下特点复杂性动态时变环境下的规划非常复杂且计算量庞大；随机性复杂环境下的不确定因素使得环境充满随机性；多约束机器人存在形状、速度、加速度等约束；多目标多个机器人均需路径最短、安全无碰，在同一环境下会产生冲突。根据机器人对环境信息了解的程度不同，路径规划可分为两种类型1环境信息己知的离线全局路径规划；2环境信息全部未知或部分未知，通过传感器对
42、机器人的工作环境进行探测，以获取障碍物位置、形状和尺寸等信息的在线局部路径规划。目前，关于环境信息完全已知的全局路径规划方法比较多，由于是离线静态规划方法，通常可以得到最优路径。这类方法主要有可视图法、自由空间法以及栅格法等。但当机器人在环境信息完全未知或局部未知的环境下工作时，就无法使用这些离线方法了。因此，需要使用基于传感器信息的局部路径规划方法。这类方法通常有人工势场法、VFII、D宰法等。局部路径规划利用传感器提供的环境信息来进行规划，常用的传感器包括有声呐、超声波传感器、激光测距仪和视觉传感器等。路经规划是机器人完成任务的安全保障，也是机器人实现智能化的关键技术，是机器人智能化程度的
43、重要标志。在当前机器人硬件系统精度短期内无法提高的情况下，对于路径规划算法的研究显得尤为重要。沈阳理工大学学士学位论文153多机器人系统体系结构31多机器人群体体系结构群体体系结构一般分为集中式（CENTRALIZED）和分散式（DECENTRALIZED）两种，而分散式结构又可进一步分为分层式（HIERARCHICAL）和分布式（DISTRIBUTED）两种（具体形式见图31）。群体体系结构的选择受机器人本身、任务、工作环境的状况等诸多因素影响，因此应当综合分析这些因素，确定系统的规模及系统机器人间恰当的相互关系，从而选择合适的结构，充分发挥其优越性。多机器人协作的体系结构可以归结为两个问题
44、由谁来做出决策并协调大家；用什么方法来做决策，得到每个机器人每个运动周期的指令。主控信息主控信息信息A集中式结构B分层式结构C分布式结构图31多机器人群体体系结构图1集中式结构集中式结构如图31A所示，它有一个主控机器人，主控机器人运行各种规划算法，对其控制下的机器人进行任务分配、相互调度和动作选择。在这种体系结构中，受控机器人之间不存在通讯，本身只是一个执行体，没有自己选择动作和进行相互协调的能力。集中式结构的优点是理论背景清晰，实现起来较为直观。它的缺点在于容错性、适应性和灵活性差，对主控机器人的要求高，当某一个机器人出现问题，特别是主控机器人出现问题时，会导致整个系统的瘫痪。2分布式结构
45、分布式结构如图31C所示，这种结构不存在主控机器人，各机器人之间是平等的，均能通过通讯进行交流、自主地进行决策。相对于集中式结构，分布式结构具有故障冗余、并行运行和可伸缩性等诸多优点。但是这种系统的整体性以及协调性较差，容易杂乱无章，当各个机器人过分强调自己任务的重要性时，将会过多地占用系统资源，使得整个系统的效率低下。沈阳理工大学学士学位论文163分层式结构分层式结构如图31B所示，它是介于集中式结构和分布式结构之间的一种结构，是一种混合型结构。分层式结构有一个主控机器人，同时受控机器人之间也存在着通讯。主控机器人在掌握全局信息及同受控机器人交流的基础上对任务进行分配，同时协调任务执行过程中
46、出现的冲突等问题，但不具体地控制受控机器人的运动。各受控机器人掌握着局部环境信息及所需要的系统信息，执行任务时结合着主控机器人的命令及周围环境情况自主进行运动规划。32典型的机器人个体体系结构机器人个体控制体系结构是指机器人系统内部硬件和软件的组成结构、功能分配、管理方式，是确定一个机器人系统的智能结构和逻辑上的计算结构。多机器人控制系统MRCSMULTIROBOTCOOPERATIVESYSTEM由多个机器人组成，机器人控制系统是机器人的核心部分，同时也决定了MRCS中机器人的协作能力。机器人本身需要具有自主性，对环境的交互性、协作性、可通讯性，以及自适应性、实时性等特性。可以说系统性能直接
47、取决于个体机器人性能的好坏。个体机器人的控制结构不同，其采用的控制方法也各不相同。移动机器人从诞生到发展至今，出现的颇具特色的个体控制结构有慎思式结构、反应式、分层递阶式、以及混合式结构。321慎思式结构慎思式结构，又称为传统结构，是通过传感系统获得的描述环境的符号信息，建立环境模型，然后结合要实现的目标，进行规划任务，再由执行机构来控制电机转动，从而实现个体机器人对环境的响应。慎思式结构模型如图32所示。慎思式体系结构是一种纵向结构，它遵循一条从感知、建模、规划、任务执行到电机控制的串行控制路线，典型的结构是智能机器人SHAKEY。慎思式结构适合已知环境下的任务明确、目标给定的系统，其控制过
48、程都预先规定，是一个显式的符号模型，系统的智能在于规划者或程序员，而不是执行任务的系统。慎思式结构的缺点很明显1体积大。机器人存储符号信息量与它内部状态的大小相当，系统越复杂，体积越大。2建模困难。规划和世界模型的建立是一个非常困难的过程，而且计划的开环执行无法适应环境的不确定性和不可预知性。沈阳理工大学学士学位论文17建模规划动作感知反应环境图32慎思式结构图322反应式结构反应式结构是RCARIKIN提出的基于MOTORSCHEMA的一种“纯粹”的行为（BEHAVIORS）控制系统，它遵循“感知动作”的规则，在AI（AGENTINTELLIGENT）领域也被称为行为主义。基于行为的控制思想
49、不同于传统人工智能的功能分解方法，它采用动作分解或行为分解的方法。反应式结构模型如图33所示。行为1行为2行为N传感器执行器环境权重1权重2权重N归一化图33反应式结构反应式结构采用自下而上的构造系统方式。它不包含世界模型，也不使用复杂的符号推理，系统的功能由一些基本、简单的行为完成，在得到传感器的输入后，有能力不经过复杂的推理而立即对环境做出反应，是一种构造工作于开放式环境中机器人的有效工具。它建立了机器人传感器与执行器的直接联系，通过行为的响应实现控制，从而提高了系统的快速反应能力。各种行为在融合时通过权重的大小来体现机器人的不同侧重点（像以协作为主还是以竞争为主），权重有不同的调整规则。BROOKS提出的包容式结构SUBSUMPTIONARCHITECTURE）可以看作沈阳理工大学学士学位论文18反应式结构的一个特例，它的行为权重只有0和1，而且每次只有一种行为的权重为1，其余行为权重抑制为0。反应式结构的优点是采用模块化设计，对于不同的任务要求及环境需求易于重构，而且响应快速，适合于动态、开放的环境。其缺点是不能胜任传感器数据的复杂分析、推理，而且由于知识的不足，不能完成认知水平的任务。323分层递阶式体系结构分层递阶式体系结构，美国学者SARIDIS很早就提出了一个关于智能控制系统的三级分层递阶式体系结构33
