多机器人路径规划研究方法(一)
张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝
摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。
关键词：多机器人；路径规划；强化学习；评判准则
e,itexpoundedthebottleneckofthepathplanningresearchfor，
；
近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI 研究大致可以分为DPS（distributedproblemsolving）和MAS （）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术
界研究的热点,而路径规划研究又是其核心部分。
机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。
1多机器人路径规划方法
单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。
目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学
习等；其他方法主要有动态规划、最优控制算法、模糊控制等。它们中的大部分都是从单个机器人路径规划方法扩展而来的。
1）传统方法多机器人路径规划传统方法的特点主要体现在基于图论的基础上。方法一般都是先将环境构建成一个图，然后再从图中寻找最优的路径。其优点是比较简单，比较容易实现；缺点是得到的路径有可能不是最优路径，而是次优路径。薄喜柱等人4]提出的一种新路径规划方法的基本思想就是基于栅格类的环境表示和障碍地图的。而人工势场方法的基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力，目标点产生引力，引力和斥力周围由一定的算法产生相应的势，机器人在势场中受到抽象力作用,抽象力使得机器人绕过障碍物。其优点是适合未知环境下的规划，不会出现维数爆炸问题；但是人工势场法也容易陷入局部最小，并且存在丢失解的部分有用信息的可能。顾国昌等人5]提出了引用总体势减小的动态调度技术的多机器人路径规划，较好地解决了这个问题。
2）智能优化方法多机器人路径规划的智能优化方（算）法是随着近年来智能计算发展而产生的一些新方法。其相对于传统方法更加智能化，且日益成为国内外研究的重点。
遗传算法是近年来计算智能研究的热点，作为一种基于群体进化的概率优化方法，适用于处理传统搜索算法难以解决的复杂和非线性问题，如多机器的路径规划问题。在路径规划中，其基本思想是先用链接图
法把环境地图构建成一个路径节点链接网，将路径个体表达为路径中一系列中途节点，并转换为二进制串；然后进行遗传操作（如选择、交叉、复制、变异），经过N次进化，输出当前的最优个体即机器人的最优路径。遗传算法的缺点是运算速度不快，进化众多的规划要占据很大的存储空间和运算时间；优点是有效避免了局部极小值问题，且计算量较小。
孙树栋等人6，7]在这方面较早地展开了研究，提出的基于集中协调思想的一种混合遗传算法来规划多机器人路径方法较好地解决了避障问题。但不足的是该方法必须建立环境地图，在环境未知情况下的规划没有得到很好的解决；且规划只能保证找到一个比较满意的解，在求解全局最优解时仍有局限。
文献8]中提出的一种基于定长十进编码方法有效降低了遗传算法的编码难度，克服了已有的变长编码机制及定长二进制编码机制需特殊遗传操作算子和特殊解码的缺陷,使得算法更加简单有效。
智能计算的另一种常见的方法——蚁群算法属于随机搜索的仿生算法。其基本思想是模拟蚂蚁群体的觅食运动过程来实现寻优，通过蚂蚁群体中各个体之间的相互作用，分布、并行地解决组合优化问题。该算法同样比较适合解决多机器人的路径规划问题。
朱庆保9]提出了在全局未知环境下多机器人运动蚂蚁导航算法。该方法将全局目标点映射到机器人视野域边界附近作为局部导航子目标，再由两组蚂蚁相互协作完成机器人视野域内局部最优路径的搜索，然
后在此基础上进行与其他机器人的碰撞预测与避碰规划。因此，机器人的前进路径不断被动态修改，从而在每条局部优化路径引导下，使机器人沿一条全局优化的路径到达目标点。但其不足是在动态不确定的环境中路径规划时间开销剧增，而且机器人缺乏必要的学习，以至于整个机器人系统路径难以是最优路径。
强化学习10，11](又称再激励学习)是一种重要的机器学习方法。它是一种智能体从环境状态到行为映射的学习，使得行为从环境中获得积累奖赏值最大。其原理如图1所示。
强化学习算法一般包含了两个步骤：a）从当前学习循环的值函数确定新的行为策略；b）在新的行为策略指导下，通过所获得的瞬时奖惩值对该策略进行评估。学习循环过程如下所示，直到值函数和策略收敛
目前比较常见的强化学习方法有：MonteCarlo方法、动态规划方法、TD（时间差分）方法。其中TD算法包含Sarsa算法、Q学习算法以及Dyna-Q算法等。其Q值函数迭代公式分别为
TD（0）策略：V(si)←V(si)+αγi+1+γV(si+1)-V(si)]
Sarsa算法：Q(st,at)←Q(st,at)+αγt+1+γQ(st+1,at.+1)-＇学习算法：Qπ(s,a)=∑Pαss＇Rass＇+γVπ(s＇
近年来，基于强化学习的路径规划日益成为国内外学者研究的热点。M.J.Mataric12]首次把强化学习引入到多机器人环境中。而基于强化学习的多机器人路径规划的优点主要体现在：无须建立精确的环境模型，
简化了智能体的编程；无须构建环境地图；强化学习可以把路径规划、避碰、避障、协作等问题统一解决。
张芳等人13]提出了基于再激励协调避障路径规划方法，把再励函数设计为基于行为分解的无模型非均匀结构，新的再励函数结构使得学习速度得以提高且有较好的鲁棒性。同时，证明了在路径规划中，机器人的趋向目标和避障行为密切相关，对反映各基本行为的再励函数取加权和来表示总的再励函数要优于取直接和的表示方式，也反映了再励函数设计得合理与否及其确切程度将影响再励学习的收敛速度。王醒策等人14]在动态编队的强化学习算法方面展开了研究。宋一然15]则提出了分段再励函数的强化学习方法进行路径规划。其缺点是学习次数较多、效率不高，当机器人数目增加时，它有可能面临维数灾难的困难。所以，基于强化学习的路径规划在多机器人环境下的学习将变得比较困难，需要对传统的强化学习加以优化，如基于人工神经网络的强化学习16]等。
3)其他方法除了以上国内外几种比较常见且研究较多的方法外，还有唐振民等人17]提出的基于动态规划思想的多机器人路径规划，把运筹学中的动态规划思想与Dijkstra算法引入到多机器人的路径规划中，用动态规划的基本思想来解决图论中的费用流问题和路径规划中的层级动态联盟问题。其选择距离邻近法作为联盟参考依据。一个机器人的邻居是指在地理位置上分布在这个机器人周围的其他机器人；与该机器人最近邻的机器人为第一层邻居,第一层邻居的邻居为该机器人的第二
层邻居,依此类推。那么层级越高（即越近)的邻居,它满足协作要求的可能性越大。动态规划算法实质上是一种以空间换时间的技术，它在实现的过程中，必须存储产生过程中的各种状态，其空间复杂度要大于
其他算法，故动态规划方法比较适合多机器人的全局路径规划。
孙茂相等人18]提出了最优控制与智能决策相结合的多移动机器人路径规划方法。其首先构造一个以各机器人最优运动状态数据库为核心的实时专家系统,在离线状态下完成;然后各机器人在此专家系统的支持下,以最优规划策略为基础,采用速度迁移算法,自主决定其控制。该方法拥有较好的稳定性与复杂度。焦立男等人19]提出的基于局部传感和通信的多机器人运动规划框架较好地解决了多机器人路径规划在局部在线规划的系统框架问题。沈捷等人20]提出了保持队形的多移动机器人路径规划。以基于行为的导航算法为基础,把机器人队列的运动过程划分为正常运动、避障和恢复队形三个阶段。在避障阶段,引入虚拟机器人使队形保持部分完整;当队形被严重打乱时,规划机器人的局部目标位姿使队列快速恢复队形。其算法重点为避障机器人进入避障状态,暂时脱离队列,并以虚拟机器人代替避障机器人。
2多机器人避碰和避障
避障和避碰是多机器人路径规划研究中需要考虑的重点问题之一。避障和避碰主要讨论的内容有防止碰撞；冲突消解、避免拥塞；如何避免死锁。在路径规划中常见的多机器人避障方法21]有主从控制法、动态优先法（建立在机器人之间的通信协商上）、交通规则法、速率调整
法，以及障碍物膨胀法、基于人工势场的方法等。
目前国内外对于多机器人避障展开的研究还不是很多，比较典型的有徐潼等人22]以Th.Fraichard的思想为基础，扩充并完善了路径/速度分解方案来协调多机器人,设立集中管理进行整体规划，为每个机器人规划路径；并根据优先级规则对运动特征进行分布式规划以避免机器人间的冲突。周明等人23]提出分布式智能避撞规划系统，将原来比较复杂的大系统转换为相对简单的子系统问题,由各智能机器人依据任务要求和环境变化,独立调整自身运动状态,完成任务的分布式智能决策体系结构。任炎等人24]提出了基于过程奖赏和优先扫除的强化学习多机器人系统的冲突消解方法。该算法能够显著减少冲突,避免死锁,提高了系统整体性能。欧锦军等人提出了通过调整机器人的运动速度实现多机器人避碰，将避碰问题转换为高维线性空间的优化问题,并进一步将其转换为线性方程的求解。该方法的缺点是系统的复杂度较高、计算量太大。
人工势场方法的特点是计算简洁、实时性强、便于数学描述，且适合于多自由度机器人环境，但容易产生抖动和陷入局部极小。为了克服其缺点，景兴建等人26]提出了人工协调场的方法，在传统排斥力场中增加一个协调力,并将吸引力、排斥力和协调力与局部环境下机器人的运动状态和运动要求结合起来，有效地保证机器人的安全性，提高机器人在复杂动态环境下行为决策的准确性和鲁棒性。
3多机器人协作和协调机制
多机器人间的运动协调27~31]是多机器人路径规划的关键，也是多机器人与单机器人路径规划相区别的根本所在。多机器人系统在复杂动态实时环境下，由于受到时间、资源及任务要求的约束，需要在有限时间、资源的情况下进行资源分配、任务调配、冲突解决等协调合作问题，而机器人间的协调与协作，能够大大地提高整个系统的效率和鲁棒性，成为系统完成控制或解决任务的关键。
目前已有的协调方式分为集中式、分布式和混合式三种。在集中式协调中，集中规划器详细地规划出每个机器人的动作，通常的做法是将多个机器人看做一个多自由度的机器人进行规划；而分布式协调规划中，机器人之间进行合作，将一个任务分成多个子任务，根据各自的特点完成不同的子任务，从而共同完成总任务；混合式协调是集中式和分布式混合在一起的形式。
复杂环境下多移动机器人协同路径规划 多移动机器人协同路径规划是机器人导航研究领域中极具挑战性的问题。复杂环境下多移动机器人协同路径规划,需要为各机器人寻求一条从起始点到目标点的最优路径,同时保证机器人间以及机器人与动、静态障碍物之间无碰撞。因此,如何实现机器人间的避碰和机器人与动态障碍物的避障是该问题的研究难点。当前大部分研究仍聚集于静态环境下单机器人路径规划,复杂环境下多移动机器人协同路径规划问题仍是亟待解决的难题。本文主要工作如下:1)针对单机器人全局路径规划问题,采用约束满足法构建优化数学模型,并结合问题属性提出一种改进蚁群算法。利用当前节点的局部路径方向与起始点至终点的欧式路径方向夹角设计新启发式函数,引导机器人沿最短路径行走;根据可选节点数量设计避障规则,提高避障能力;依据路径长度对信息素进行比较更新,提高算法收敛速度。实验表明,改进算法性能优于原始蚁群算法。2)针对静态环境下多移动机器人协同路径问题,构建以路径长度短和暂停时间少为目标的多目标数学模型。考虑到机器人之间存在碰撞冲突,研究启发式规则对冲突进行消除。以单机器人全局路径规划为基础,研制出一种基于全局路径规划和融入启发式规则的局部路径调整的两阶段规划算法求解该问题,仿真实验表明了该算法的有效性。3)针对动态环境下多移动机器人协同路径规划问题,基于静态环境下多移动机器人路径规划的研究成果,根据动态障碍物的运动性质研究避障方法,消除机器人与动态障碍物的碰撞冲突。设计了相应的仿真实验,结果表明了该方法的有效性。4)考虑
到企业的实际需要,设计了多移动机器人协同路径规划系统。该系统具有较好的集成性和开放性,提供了用户登录、用户管理、单机器人调度方案和多机器人调度方案等交互界面,满足用户在不同运行环境下的需要。
东南大学 硕士学位论文 移动机器人完全遍历路径规划算法研究 姓名：胡正聪 申请学位级别：硕士 专业：机械电子工程 指导教师：张赤斌 20080403
第一章绪论 第一章绪论 １．１移动机器人的发展史 社会的主体是人类，历史的推动者是人类，伟大的人类运用自己的智慧不断创造伟大的发明，不断推动社会的发展。邓小平同志说过：“科技是第一生产力。”生产力是社会发展的动力，所以人类推动社会发展就是要致力于发展生产力，致力于发展科技。人类不断发展生产力来提高自身认识自然、改造自然、得到自己所需物质的能力，这种能力的进化由最初的运用双手、简单工具、发展到运用畜力、发展到运用简单机器、发展到运用自动化设备、还会发展到我们无法想象的未来。 机器人就是生产力发展的产物。机器人的概念最早是在１９２０年的科幻小说中提出的，而早期的机器人如１９３９年美国纽约世界博览会上展出的西屋电气公司制造的家用机器人Ｅｌｅｋｔｒｏ和１９５６年美国人乔治?德沃尔制造出的世界上第一台可编程的机器人都是一些实用价值不高的机器人，它们是现代机器人的雏形。上世纪６０年代，由于传感器和计算机技术的发展及应用，兴起了全世界第二代机器人的研究热潮，并向人工智能进发。１９６８年，美国斯坦福研究所公布了他们研发成功的机器人Ｓｈａｋｅｙ。它带有视觉传感器，能根据人的指令发现并抓取积木。Ｓｈａｋｅｙ可以算是世界第一台智能机器人，它拉开了第三代机器人研发的序幕。到了上世纪８０年代，发达国家都组建各种机器人研究机构，尤其是以美国为代表的国家将机器人的研究列入了军事发展计划，带动各国把机器人的研究推上了高潮，日本和欧洲各国都成立了各自的机器人研究中心和规划了自己的研究计划。进入９０年代后，机器人的应用领域除了工业和军事外，还涉及到了服务和娱乐领域，以日本本田公司的ＡＳＩＭＯ人型机器人和索尼公司的ＡＩＢＯ娱乐机器人为代表的机器人展示了机器人领域各方面的先进研究成果。在欧洲，２００２年丹麦ｉＲｏｂｏｔ公司推出了吸尘器机器人Ｒｏｏｍｂａ，它能避开障碍，自动设计行进路线，还能在电量不足时，自动驶向充电座。Ｒｏｏｍｂａ是目前世界上销量最大、最商业化的家用机器人。２００６年６月，微软公司推出ＭｉｃｒｏｓｏＲＲｏｂｏｔｉｃｓＳｔｕｄｉｏ，机器人模块化、平台统一化的趋势越来截明显，比尔?盖茨预言：“家用机器人很快将席卷伞球。” 图１．１丹麦ｉＲｏｂｏｔ公司推出的吸尘机器人Ｒｏｏｍｂａ［
第5期(总第156期) 2009年10月机械工程与自动化 M ECHAN I CAL EN G I N EER I N G & AU TOM A T I ON N o 15 O ct 1 文章编号:167226413(2009)0520194203 机器人路径规划方法的研究 李爱萍,李元宗 (太原理工大学机械工程学院,山西 太原 030024) 摘要:路径规划技术是机器人学研究领域中的一个重要部分。目前的研究主要分为全局规划方法和局部规划方法两大类。通过对机器人路径规划方法研究现状的分析,指出了各种方法的优点及不足,并对其发展方向进行了展望。 关键词:机器人;全局规划;局部规划中图分类号:T P 242 文献标识码:A 收稿日期:2009201207;修回日期:2009204218 作者简介:李爱萍(19792),女,山西晋中人,在读硕士研究生。 0 引言 路径规划技术是机器人学研究领域中的一个重要 部分。机器人的最优路径规划就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短等),在其工作空间中找到一条从起始状态到目标状态的最优路径。根据对环境信息的掌握程度不同,路径规划可分为:①全局路径规划:环境信息完全已知,根据环境地图按照一定的算法搜寻一条最优或者近似最优的无碰撞路径,规划路径的精确程度取决于获取环境信息的准确程度;②局部路径规划:环境信息完全未知或部分未知,根据传感器的信息来不断地更新其内部的环境信息,从而确定出机器人在地图中的当前位置及周围局部范围内的障碍物分布情况,并在此基础上,规划出一条从当前点到某一子目标点的最优路径。 1 全局规划方法111 栅格法 栅格法是目前研究最广泛的路径规划方法之一。该方法将机器人的工作空间分解为多个简单的区域(栅格),由这些栅格构成一个显式的连通图,或在搜索过程中形成隐式的连通图,然后在图上搜索一条从起始栅格到目标栅格的路径。一般路径只需用栅格的序号表示。但栅格的划分直接影响其规划结果,如果栅格划分过大,环境信息储藏量小,分辨率下降,规划能力就差;栅格划分过小,规划时间长,而且对信息存储能力的要求会急剧增加。112 可视图法 可视图法中的路径图由捕捉到的存在于机器人一 维网络曲线(称为路径图)自由空间中的节点组成。路径的初始状态和目标状态同路径图中的点相对应,这样路径规划问题就演变为在这些点间搜索路径的问题。要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,即直线是“可视的”。然后采用某种方法搜索从起始点到目标点的最优路径,搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。该法能够求得最短路径,但需假设忽略机器人的尺寸大小,使得机器人通过障碍物顶点时离障碍物太近甚至接触,并且搜索时间长。113 拓扑法 拓扑法将规划空间分割成具有拓扑特征的子空间,根据彼此的连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。拓扑法的基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。其优点在于利用拓扑特征大大缩小了搜索空间,其算法的复杂性仅依赖于障碍物数目,在理论上是完备的;而且拓扑法通常不需要机器人的准确位置,对于位置误差也就有了更好的鲁棒性。缺点是建立拓扑网络的过程相当复杂,特别是在增加障碍物时如何有效地修正已经存在的拓扑网是有待解决的问题。 114 自由空间法 自由空间法采用预先定义的广义锥形或凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,通过搜索连通图来进行路径规划。自由空间的构
一种移动机器人的路径规划算法 作者：霍迎辉，张连明 (广东工业大学自动化研究所广州510090 文章来源：自动化技术与应用点击数：1419 更新时间：2005-1-24 摘要：本文提出一种移动机器人路径规划最短切线路径算法。依据此算法，机器人能顺利地避开障碍物到达目标位置，其原理简单，计算快捷，容易实现。仿真结果验证了它的有效性和实用性。 关键词：移动机器人；路径规划；机器人避障 1引言 移动机器人路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从给定起点到终点的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物［1］。 障碍环境中机器人的无碰撞路径规划［2］是智能机器人研究的重要课题之一，由于在障碍空间中机器人运动规划的高度复杂性使得这一问题至今未能很好地解决。路径规划问题根据机器人的工作环境模型可以分为两种，一种是基于模型的路径规划，作业环境的全部信息都是预知的；另一种是基于传感器的路径规划，作业环境的信息是全部未知或部分未知的。 对机器人路径规划的研究，世界各国的专家学者们提出了许多不同的路径规划方法，主要可分为全局路径和局部路径规划方法。全局路径规划方法有位形空间法、广义锥方法、顶点图像法、栅格划归法；局部路径规划方法主要有人工势场法。这些方法都各有优缺点［3］，也没有一种方法能够适用于任何场合。 本文提出一种最短切线路径的规划方法，其涉及的理论并不高深，计算简单，容易实现，可供侧重于应用的读者参考。下面将详细介绍该算法的基本原理，最后给出仿真实现的结果。 2最短切线路径算法 2.1算法基本原理 (1)首先判断机器人和给定的目标位置之间是否存在障碍物。如图1所示，以B代表目标位置，其坐标 为(x Ｂ，y Ｂ ），以R、A分别代表机器人及障碍物，坐标为(x Ｒ ，y Ｒ )、(x Ａ ，y Ａ )。Ｒr和Ra表示机器人和障 碍物的碰撞半径，也就是说在其半径以外无碰撞的危险。这里对碰撞半径的选择作出一点说明，碰撞半径越小，发生碰撞的危险度越大，但切线路径越短；碰撞半径越大，发生碰撞的危险度越小，但同时切线路径越长。要根据实际情况和控制要求来确定碰撞半径。若机器人与目标位置之间不存在障碍物，机器人可走直线直接到达目标位置，此时的直线方程可由两点式确定：
1绪论 1.1机器人简介 1.1.1什么是机器人 机器人一词不仅会在科幻小说、动画片等上看到和听到，有时也会在电视上看到在工厂进行作业的机器人，在实际中也有机会看到机器人的展示。今天，说不定机器人就在我们的身过，但这里我们要讨论的是什么是机器人学研究的机器人。 机器人（robot）一词来源下1920年捷克作家卡雷尔. 查培克（Kapel Capek）所编写的戏剧中的人造劳动者，在那里机器人被描写成像奴隶那样进行劳动的机器。 后来作为一种虚构的机械出现在许多作品中，代替人们去完成某些工作。20世纪60年代出现了作为可实用机械的机器人。为了反这种机器人同虚构的机器人及玩具机器人加以区别，称其为工业机器人。 工业机器人的兴起促进了大学及研究所开展机器人的研究。随着计算机的普及，又积极地开展了带有智能的机器人的研究。到70年代，机器人作为工程对象已经被确认，机器人一词也受到公认。目前，机器人学的研究对象已不仅仅是工业机器人了。 即便是实际存在的机器人，也很难把它定义为机器人，而且其定义也随着时代在变化。这里简单地反具有下述性质的机械看作是机器人： 1.代替人进行工作：机器人能像人那样使用工具和机械，因此，数控机床和 汽车不是机器人。 2.有通有性：既可简单地变换所进行的作为，又能按照工作状况的变化相应 地进行工作。一般的玩具机器人不能说有通用性。 3.直接对个界作工作：不仅是像计算机那样进行计算，而且能依据计算结果 对外界结果对外界产生作用。 机器人学把这样定义的机器人作为研究对象。
1.1.2机器人的分类 机器人的分类方法很多，这里我们依据三个有代表性的分类方法列举机器人的种类。 首先，由天机器人要代替人进行作业，因此可根据代替人的哪一个器官来分类： 操作机器人（手）：利用相当于手臂的机械手、相当于手指的手爪来使物体协作。 移动机器人（腿）：虽然已开发出了2足步行和4足步行机器人，但实用的却是用车轮进行移动的机器人。（本文以轮式移动机器人作为研究对象）视觉机器人（眼）：通过外观检查来除掉残次品，观看人的面孔认出是谁。虽然还有使用触觉的机器人，但由于它不是为了操作，所以不能说是触觉机器人。 也还有不仅代替单一器官的机器人，例如进行移动操作，或进行视觉和操作的机器人。 其次，按机器人的应用来分类： 工业机器人：可分为搬送、焊接、装配、喷漆、检查等机器人，主要用于工厂内。 极限作业器人：主要用在人们难以进入的核电站、海底、宇宙空间等进行作为的机器人。也包括建筑、农业机器人等。 娱乐机器人：有弹奏乐器的机器人、舞蹈机器人、宠物机器人等，具有某种程度的通用性。也有适应环境面改变行动的宠物机器人。 最后则是按照基于什么样的信息进行动作来分类： 表1基于动作信息的机器人分类
遗传算法与机器人路径规划 摘要：机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。 关键词：路径规划；移动机器人；避障；遗传算法 Genetic Algorithm and Robot Path Planning Abstract: Robot path planning research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers（e.g time optimal），and find a best movement path in work space. Robot path planning can be modeled that in the course of robots able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual. Key words: Path planning,mobile robot, avoid the obstacles, genetic algorithm 1路径规划 1.1机器人路径规划分类 （1）根据机器人对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划基本上可分为以下几类： 1，已知环境下的对静态障碍物的路径规划； 2，未知环境下的对静态障碍物的路径规划； 3，已知环境下对动态障碍物的路径规划； 4，未知环境下的对动态障碍物的路径规划。 （2）也可根据对环境信息掌握的程度不同将移动机器人路径规划分为两种类型： 1，基于环境先验完全信息的全局路径规划； 2，基于传感器信息的局部路径规划。 （第二种中的环境是未知或部分未知的，即障碍物的尺寸、形状和位置等信息必须通过传感器获取。） 1.2路径规划步骤 无论机器人路径规划属于哪种类别，采用何种规划算法，基本上都要遵循以下步骤： 1, 建立环境模型，即将现实世界的问题进行抽象后建立相关的模型； 2, 路径搜索方法，即寻找合乎条件的路径的算法。 1.3路径规划方法
第25卷第7期V ol.25No.7 控制与决策 Control and Decision 2010年7月 Jul.2010移动机器人路径规划技术综述 文章编号:1001-0920(2010)07-0961-07 朱大奇,颜明重 (上海海事大学水下机器人与智能系统实验室，上海201306) 摘要:智能移动机器人路径规划问题一直是机器人研究的核心内容之一.将移动机器人路径规划方法概括为:基于模版匹配路径规划技术、基于人工势场路径规划技术、基于地图构建路径规划技术和基于人工智能的路径规划技术.分别对这几种方法进行总结与评价,最后展望了移动机器人路径规划的未来研究方向. 关键词:移动机器人；路径规划；人工势场；模板匹配；地图构建；神经网络；智能计算 中图分类号:TP18；TP273文献标识码:A Survey on technology of mobile robot path planning ZHU Da-qi,YAN Ming-zhong (Laboratory of Underwater Vehicles and Intelligent Systems，Shanghai Maritime University，Shanghai201306, China．Correspondent：ZHU Da-qi，E-mail：zdq367@https://www.doczj.com/doc/ec1946383.html,) Abstract:The technology of intelligent mobile robot path planning is one of the most important robot research areas.In this paper the methods of path planning are classi?ed into four classes:Template based,arti?cial potential?eld based,map building based and arti?cial intelligent based approaches.First,the basic theories of the path planning methods are introduced brie?y.Then,the advantages and limitations of the methods are pointed out.Finally,the technology development trends of intelligent mobile robot path planning are given. Key words:Mobile robot；Path planning；Arti?cial potential?eld；Template approach；Map building；Neural network; Intelligent computation 1引言 所谓移动机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务.移动机器人路径规划主要解决3个问题:1)使机器人能从初始点运动到目标点;2)用一定的算法使机器人能绕开障碍物,并且经过某些必须经过的点完成相应的作业任务;3)在完成以上任务的前提下,尽量优化机器人运行轨迹.机器人路径规划技术是智能移动机器人研究的核心内容之一,它起始于20世纪70年代,迄今为止,己有大量的研究成果报道.部分学者从机器人对环境感知的角度,将移动机器人路径规划方法分为3种类型[1]:基于环境模型的规划方法、基于事例学习的规划方法和基于行为的路径规划方法;从机器人路径规划的目标范围看,又可分为全局路径规划和局部路径规划;从规划环境是否随时间变化方面看,还可分为静态路径规划和动态路径规划. 本文从移动机器人路径规划的具体算法与策略上,将移动机器人路径规划技术概括为以下4类:模版匹配路径规划技术、人工势场路径规划技术、地图构建路径规划技术和人工智能路径规划技术.分别对这几种方法进行总结与评价,展望了移动机器人路径规划的未来发展方向. 2模版匹配路径规划技术 模版匹配方法是将机器人当前状态与过去经历相比较,找到最接近的状态,修改这一状态下的路径,便可得到一条新的路径[2,3].即首先利用路径规划所用到的或已产生的信息建立一个模版库,库中的任一模版包含每一次规划的环境信息和路径信息,这些模版可通过特定的索引取得;随后将当前规划任务和环境信息与模版库中的模版进行匹配,以寻找出一 收稿日期:2009-08-30；修回日期:2009-11-18. 基金项目:国家自然科学基金项目(50775136)；高校博士点基金项目(20093121110001)；上海市教委科研创新项目(10ZZ97). 作者简介:朱大奇(1964?),男,安徽安庆人,教授,博士生导师,从事水下机器人可靠性与路径规划等研究；颜明重(1977?),男,福建泉州人,博士生,从事水下机器人路径规划的研究.
多机器人路径规划研究方法 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝 摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multi robot.Then discussed the criterion of path planning research for multi robot based large of literature.Meanwhile,it expounded the bottleneck of the path planning research for multi robot，forecasted the future development of multi robot path planning. Key words:multi robot；path planning;reinforcement learning;evaluating criteria 近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI研究大致可以分为DPS（distributed problem solving）和MAS（multi agent system）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点,而路径规划研究又是其核心部分。 机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果[1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、Dempster Shafer 证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划
移动机器人路径规划技术的现状与发展 现阶段，移动机器人技术是科学领域研究的一个重点内容，而在该技术的研究中，移动机器人的路径规划技术是非常重要的。其中，路径规划可以被划分成两种，其一是基于模型环境进行的已知的全局路径进行规划，其二是基于传感器环境对未知局部路径进行规划。文章对移动机器人的路径规划方法进行了详细的分析，并分别列举了全局路径规划以及局部路径规划的具体规划方法，并对该技术未来的发展进行展望。 标签：移动机器人；路径规划；神经网络；栅格法 1 移动机器人路径规划技术的分类 按照机器人对周围环境信息的识别与对信息的掌握程度以及对不同种类障碍物的识别进行分类，可将机器人路径规划分成四类：第一类，在已知的比较熟悉的环境中，根据静态障碍物的位置对移动机器人的路径进行规划；第二类，在未知的比较陌生的环境中根据静态障碍物的位置对移动机器人的路径进行规划；第三类，在已知的比较熟悉的环境中，根据动态障碍物的运行状态对移动机器人的路径进行规划；第四类，在未知的比较陌生的环境中，根据动态障碍物的运行状态对移动机器人的路径进行规划。根据机器人对周围环境的掌握能力不同，可以对路径规划技术进行划分，第一类是在对周围环境信息已经验证的基础上对移动机器人的的路径进行规划，所规划的路径为全局路径；第二类是基于傳感器信息的基础上对机器人的路径进行规划，规划的路径为局部路径[1]。移动机器人的路径规划方法一般可以划分成两大类型，即传统方法与智能方法。 2 全局路径规划方法 2.1 拓扑法 该路径规划的方法主要就是把所规划的空间进行分割，并形成具有拓扑特点的子空间，同时构建拓扑网络，并在其中探索出起点至终点的详细拓扑路径，然后根据拓扑路径的路径规划得到最终需要的几何路径。拓扑路径的规划方法是以降维法为主要依据，也就是，将高维的比较复杂的空间几何路径求法转化为低维的比较简单的拓扑空间的辨别连通方法。这种方法的最明显优势就是对拓扑特点进行充分利用，进而有效地减小实际搜索的空间范围[2]。而其算法的复杂程度则只是同障碍物数目有较大关系，所以，最主要的问题就是在障碍物数量增加的情况下，采取合理措施对已有拓扑网络进行修正，并实现图形速度提升的目的。 2.2 可视图法 这种路径规划的方法就是将机器人看做是一个点，然后进行合理组合，并将机器人与目标点、多边形障碍物的各顶点相连。在连接点的过程中，需要保证直线可视，也就是目标点与多边形障碍物的各顶点以及各个障碍物顶点间的连线不
龙源期刊网 https://www.doczj.com/doc/ec1946383.html, 基于Player/Gazebo的移动机器人路径规划仿真实现 作者：郝萍萍姚立峰 来源：《教育界》2010年第10期 [摘要]利用Player/Gazebo可以在3D环境中对单个或多个移动机器人的定位、路径规划、建图等导航算法进行高效的仿真。本文在简介Player/Gazebo仿真环境的基础上，对移动机器人路径规划进行了讨论，利用Player/Gazebo的服务器/客户端模式，实现了对移动机器人路径规划的仿真，提高了机器人路径规划研究的效率。 [关键词]Player/Gazebo移动机器人仿真 1.引言 移动机器人技术是当今信息技术中最热门的领域，涉及感知、建模、导航、控制等各个方面。其中，路径规划是移动机器人自主导航的基本要求之一，它使机器人在已知或未知环境中由一个初始配置自主移动到一个终点配置。随着计算机技术的发展，移动机器人仿真成为现今机器人导航技术研究的重要手段。研究人员可以在虚拟环境中对机器人进行建模和控制，模拟仿真各种现实环境和突发状况，避免在复杂环境下现场试验的困难并降低实际运行的成本。Player/Stage/Gazebo是应用最广泛的机器人控制仿真平台之一，利用Gazebo的三维仿真环境，人们可以清楚地看到机器人在环境中的运行状况，极大的方便了机器人导航算法的研究。本文在介绍Player/Stage/Gazebo仿真平台的基础上，以移动机器人路径规划为例，详细论述了如何建立移动机器人的运行环境和三维模型，并对机器人的路径规划控制进行了仿真。结果表明该仿真环境可以真实有效的模拟移动机器人的运动和动力学特性、各种传感器以及机器人运动规划控制，必将进一步促进移动机器人的自主导航研究。 2.Player/Stage/Gazebo简介 Player/Stage/Gazebo是目前全世界应用最广泛的机器人仿真开发平台之一。 Player/Stage/Gazebo仿真平台包括机器人设备接口Player、2D多机器人仿真环境Stage以及3D 多机器人仿真环境Gazebo三部分。其中，Player采用基于TCP的客户端，服务器模式，为各
多机器人路径规划研究方法（一） 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 e,itexpoundedthebottleneckofthepathplanningresearchfor ， ； 近年来，分布式人工智能（DAI）成为人工智能研究的一个重要分支。DAI 研究大致可以分为DPS （distributedproblemsolving ）和MAS （）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点,而路径规划研究又是其核心部分。
机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果 1~3］，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi 图法、自由空间法、栅格法、拓扑法、链接图法、证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。 1 多机器人路径规划方法单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。 目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi 图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学 习等；其他方法主要有动态规划、最优控制算法、模糊控制等。它们中的大部分都是从单个机器人路径规划方法扩展而来的。 1）传统方法多机器人路径规划传统方法的特点主要体现在基于图论的基础
机器人路径规划 冯赟:机器人路径规划方法研究 1绪论 1.1机器人简介 1.1.1什么是机器人 机器人一词不仅会在科幻小说、动画片等上看到和听到，有时也会在电视上看到在工厂进行作业的机器人，在实际中也有机会看到机器人的展示。今天，说不定机器人就在我们的身过，但这里我们要讨论的是什么是机器人学研究的机器人。 robot)一词来源下1920年捷克作家卡雷尔 . 查培克(Kapel Capek)机器人( 所编写的戏剧中的人造劳动者，在那里机器人被描写成像奴隶那样进行劳动的机器。 后来作为一种虚构的机械出现在许多作品中，代替人们去完成某些工作。20世纪60年代出现了作为可实用机械的机器人。为了反这种机器人同虚构的机器人及玩具机器人加以区别，称其为工业机器人。 工业机器人的兴起促进了大学及研究所开展机器人的研究。随着计算机的普及，又积极地开展了带有智能的机器人的研究。到70年代，机器人作为工程对象已经被确认，机器人一词也受到公认。目前，机器人学的研究对象已不仅仅是工业机器人了。 即便是实际存在的机器人，也很难把它定义为机器人，而且其定义也随着时代在变化。这里简单地反具有下述性质的机械看作是机器人: 1. 代替人进行工作:机器人能像人那样使用工具和机械，因此，数控机床和 汽车不是机器人。 2. 有通有性:既可简单地变换所进行的作为，又能按照工作状况的变化相应
地进行工作。一般的玩具机器人不能说有通用性。 3. 直接对个界作工作:不仅是像计算机那样进行计算，而且能依据计算结果 对外界结果对外界产生作用。 机器人学把这样定义的机器人作为研究对象。 - 1 - 郑州大学电气工程学院毕业设计(论文) 1.1.2机器人的分类 机器人的分类方法很多，这里我们依据三个有代表性的分类方法列举机器人的 种类。 首先，由天机器人要代替人进行作业，因此可根据代替人的哪一个器官来分类: 操作机器人(手):利用相当于手臂的机械手、相当于手指的手爪来使物体协 作。 移动机器人(腿):虽然已开发出了2足步行和4足步行机器人，但实用的却是 用车轮进行移动的机器人。(本文以轮式移动机器人作为研究对象) 视觉机器人(眼):通过外观检查来除掉残次品，观看人的面孔认出是谁。虽然 还有使用触觉的机器人，但由于它不是为了操作，所以不能说是触觉机器人。 也还有不仅代替单一器官的机器人，例如进行移动操作，或进行视觉和操作的 机器人。 其次，按机器人的应用来分类: 工业机器人:可分为搬送、焊接、装配、喷漆、检查等机器人，主要用于工厂 内。 极限作业器人:主要用在人们难以进入的核电站、海底、宇宙空间等进行作为 的机器人。也包括建筑、农业机器人等。
多机器人路径规划研究方法(一) 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝 摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 e,itexpoundedthebottleneckofthepathplanningresearchfor， ； 近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI 研究大致可以分为DPS（distributedproblemsolving）和MAS （）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术
界研究的热点,而路径规划研究又是其核心部分。 机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。 1多机器人路径规划方法 单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。 目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学
1.自主机器人近距离操作运动规划体系 在研究自主运动规划问题之前，首先需建立相对较为完整的自主运动规划体系，再由该体系作为指导，对自主运动规划的各项具体问题进行深入研究。本节将根据自主机器人的思维方式、运动形式、任务行为等特点，建立与之相适应的自主运动规划体系。并按照机器人的数量与规模，将自主运动规划分为单个机器人的运动规划与多机器人协同运动规划两类规划体系。 1.1单个自主机器人的规划体系 运动规划系统是自主控制系统中主控单元的核心部分，因此有必要先研究自主控制系统和其主控单元的体系结构问题。 自主控制技术研究至今，先后出现了多种体系结构形式，目前被广泛应用于实践的是分布式体系结构，其各个功能模块作为相对独立的单元参与整个体系。随着人工智能技术的不断发展，基于多Agent的分布式体系结构逐渐成为了主流，各功能模块作为独立的智能体参与整个自主控制过程，该体系结构应用的基本形式如图1所示。一方面，主控单元与测控介入处理、姿态控制系统、轨道控制系统、热控系统、能源系统、数传、有效载荷控制等功能子系统相互独立为智能体，由总线相连；另一方面，主控单元为整个系统提供整体规划，以及协调、管理各子系统Agent的行为。测控介入处理Agent保证地面系统对整个系统任意层面的控制介入能力，可接受上行的使命级任务、具体的飞行规划和底层的控制指令；各子系统Agent存储本分系统的各种知识和控制算法，自主完成主控单元发送的任务规划，并将执行和本身的健康等信息传回主控单元，作为主控单元Agent运行管理和调整计划的依据。 图1 基于多Agent的分布式自主控制系统体系结构基本形式示意图 主控单元Agent采用主流的分层递阶式结构，这种结构层次鲜明，并且十分利于实现，其基本结构如图2所示。主控单元由任务生成与调度、运动行为规划和控制指令生成三层基本结构组成，由任务生成与调度层获得基本的飞行任务，经过运动行为规划层获得具体的行为规划，再由控制指令生成层得到最终的模块控制指令，发送给其它功能Agent。各功能Agent发送状态信息给主控单元的状态检测系统，状态检测系统将任务执行情况和子系统状态反馈回任务生成与调度层，以便根据具体情况对任务进行规划调整。当遇到突发情况时，还可启用重规划模块，它可根据当时情况迅速做出反应快速生成行为规划，用以指导控制指令生成层得到紧急情况的控制指令。此外，地面控制系统在三个层次上都分别具有介入能
Business ! ·233· 机器人路径规划算法探讨 陈书光 作者简介：陈书光，（1980－），男，籍贯：河南省唐河县，汉族，学历：研究生，职称：讲师，研究方向：数据库技术、软件设计、 算法分析。 摘要：机器人路径规划问题被定义为一个障碍的工作环境中找到一个适当的从起点到终点的运动路径，机器人在运动过程中能安全无碰撞，绕过所有的障碍。屏障环境的机器人无碰撞路径规划是一个重要的研究课题，智能机器人，由于障碍物空间机器人运动规划的高度复杂性，使得这个问题一直没有得到很好的解决。路径规划问题的基础上，机器人的工作环境模型可以分为2类，一个是基于模型的路径规划，经营环境的整体的信息是可预测的；另一种是基于传感器的路径规划，环境信息完全未知或部分未知。 关键词：机器人路径规划算法一、本文就常见的几种常见的路径规划算法及应用进行简单的探讨如下： （一）遗传算法概念 遗传算法是根据达尔文的进化论，模拟自然选择的一种智能算法 ，“适者生存”是它的核心机制。遗传算法是从代表问题可能潜在解集的一个种群开始的。基于随机早期人口，根据的原则，优胜劣汰，适者生存，世代演化产生更好的人口大概。在每一代，根据问题域的个体适应度大小来选择个人，然后选定的个人在自然遗传学，遗传算子组合交叉和变异，产生代表性的解集的人口。通过这些步骤，后生代种群比前代对于环境具有更好的适应性。人口最优个体解码后可作为近似最优解。 （二）遗传算法的特点 作为一种智能算法，遗传算法具有如下特点：①遗传算法在寻优过程中，只把适应度函数的值作为寻优判据。②遗传算法是由一个问题集合（种群）开始的，而不是从一个个体开始的。故而遗传算法的搜索面积很大，适合全局寻优。③遗传算法根据概率性的变换规则进行个体的优胜劣汰并推动种群的进化。④遗传算法具有隐含的并行性。⑤遗传算法具有自组织、自适应以及内在的学习性，同时遗传算法具有很强的容错能力。⑥遗传算法的基本思想简单。对于复杂的和非线性的问题具有良好的适应性。 （三）遗传算法的应用 遗传算法提供了一个整体框架地址复杂系统问题，它不依赖于俞特定领域的问题，问题的类型、已是强的鲁棒性，所以广泛应用余许多科学：功能优化遗传算法的经典应用，是遗传算法的性能评价的常见的例子，许多人建设的各种复杂的表格功能测试：连续函数和离散函数，凸、凹函数、低维功能和高尺寸功能、单式功能和更多峰值函数。一些非线性、多模型、多目标函数优化问题和其他优化方法很难解决，GA 你可以更好的结果。增加问题的规模，搜索空间的组合优化问题，将会迅速增加，有时的当前枚举方法和计算很难找到最佳的解决方案。实践证明，遗传算法、组合优化问题的粒子非常有效。 二、蚁群算法及其应用（一）蚁群算法概念 蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo 于1992年在他的博士论文中提出，灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法。 （二）蚁群算法的特点 ①蚁群算法是一种自组织算法。在早期的算法，单一的人工蚂蚁障碍找到求解算法，久而久之，通过信息作用的激素，人工蚂蚁进化将找到一些解决办法更接近最优的解决方案，它是无序到有序的过程。 ②蚁群算法的并行算法是一种基本的。每个蚁群搜索进程 独立的对方，只能通过信息素通讯。因此，蚁群算法可以看作是一种分布式的多智能体系统，它在问题空间搜索算法开始是一个独立的解决方案，不仅提高了可靠性，这使得该算法具有强的全局搜索能力。 ③蚁群算法是一种积极的反馈的算法。从蚂蚁觅食中不难看到蚂蚁已设法找到最短路径的信息的过程取决于直接上的最短路径的积累，以及信息素的积累是一个积极的反馈过程。这种正反馈的过程进行初步的差距有不断扩大，并导致系统的最优解的方向发展。 ④蚁群算法具有较强的鲁棒性。比较与其他算法、蚁群算法、初始对齐要求不高，外务大臣蚁群算法用于路由和搜索过程的初步结果不需要手动调整。第二，设立简单、便于应用的蚁群算法求解组合优化问题的蚁群算法参数的殖民地，数目。 （三）蚁群算法应用 蚁群算法应用包括：二次分配问题、车间任务调度问题、车辆路线问题、机构同构判定问题、学习模糊规则问题、旅行社新旅游线路与旅行产品的制作等领域。 三、神经网络算法（一）神经网络的概念 人工神经网络也被称为神经网络连接模式，它是一种动物模型，神经网络的行为特征，分布式并行处理算法的数学模型。网络依赖于复杂的系统，通过调整内部之间的联系，大量节点，以实现节能的目的，信息处理。 特征的神经网络模型的人工神经网络的主要网络连接拓扑，神经元的特点，学习规则。目前，近40种神经网络模型，其中有一个BP 网络，传感器网络，自组织映射，神经，波尔兹曼机，自适应共振理论。系统的稳定性与联想记忆功能密切相关。 神经网络的应用 人工神经网络的非线性自适应信息处理能力，克服了传统人工智能方法的直觉，作为模型，语音识别，非结构化信息处理方面的缺陷，使神经网络专家系统，模式识别，智能控制，组合优化，预测等领域得到成功应用。人工神经网络和其他传统方法相结合，将促进人工智能和信息处理技术的发展。近年来，人工神经网络模拟人类认知方式更深入的发展，模糊系统，遗传算法，进化机制相结合，形成智能计算，人工智能，已成为一个重要的方向，在实际的应用开发。信息几何学应用于人工神经网络的研究，人工神经网络理论开辟了一条新的途径。 机器人路径规划算法有很多，可以说有优点和缺点，目前还没有一个算法可以应用于任何场合。因此，各种新的算法被提出，一方面丰富了解决问题的手段，不同的情况下都能找到一个合适的算法；另一方面也不断吸收新的理论，促进学科发展。一个很好的算法，理论深度不高，但其使用；相反，原理简单，计算效率的算法是更容易被接受，关键是看最后达到的效果。（作者单位：柳州城市职业学院）