在初始时刻,由于路径BC、BM、CD、DM上均无信息素存在,位于 B的蚂蚁可以随机选择路径。
16
六、蚁群算法
第五章 机器人路径规划
从统计的角度可以认为开始时它们以相同的概率选择 路径BCD、BMD,这样由于路径短,相同时间内最终造成通过 BCD的蚂蚁比通过BMD的多,使得BCD上的信息素比BMD上的多, 这样又吸引更多的蚂蚁沿路径走,直至最终所有蚂蚁选择路 径BCD,从而找到由蚁巢到食物源的最短路径。由此可见,蚂 蚁个体之间的信息交换是一个正反馈过程。
11
五、人工势场法
第五章 机器人路径规划
12
第五章 机器人路径规划
五、人工势场法 2.人工势场法的两个问题：
（1)非点形障碍物 普通的障碍物的形状不是一个点，如何确定一个障碍物对机器 人的排斥力呢？ 方案1：计算障碍物内所有点斥力的合力。 方案2：用离障碍物最近的点进行计算。 （2)死锁（dead lock）现象
17
第五章 机器人路径规划
七、神经网络算法（Neural Networks）
神经网络算法是人工智能领域中的一种非常优秀的算 法，它主要模拟动物神经网络行为，进行分布式并行信息 处理。但它在路径规划中的应用却并不成功，因为路径规 划中复杂多变的环境很难用数学公式进行描述，如果用神 经网络去预测学习样本分布空间以外的点，其效果必然是 非常差。尽管神经网络具有优秀的学习能力，但是泛化能 力差是其致命缺点。但因其学习能力强鲁棒性好，它与其 他算法的结合应用已经成为路径规划领域研究的热点。
4
第五章 机器人路径规划
第二节 路径规划方法
一、路径规划方法
第五章 机器人路径规划
1.传统方法：
可视图法、自由空间法、栅格法、人工势场法
2.智能方法：
蚁群算法、神经网络、遗传算法
3.其他方法：
A*算法、Dijkstra 算法
6
二、可视图法
第五章 机器人路径规划
对可视图进行搜索,并利 用优化算法删除一些不必要 的连线以简化可视图,缩短了 搜索时间,最终就可以找到一 条无碰最优路径。优点是可 以求得最短路径,缺点是此法 缺乏灵活性,即一旦机器人的 起点和目标点发生改变,就要 重新构造可视图,比较麻烦。
六、蚁群算法 2.蚁群算法运用分析：
第五章 机器人路径规划
设A是巢穴,E是食物源,CM为 一障碍物。由于障碍物的存在, 蚂蚁要从A到E或E从到A,只能沿 路线BCD或BMD通过,各点之间的 距离如图所示。设每个单位时 间有50只蚂蚁由到达,蚂蚁过后 留下的激素物质量信息素为1, 为方便起见,假设信息素挥发时 间为10。
上图中灰色区域为障碍物
上图黄色路线为该算法得到的最优路1径0
第五章 机器人路径规划
五、人工势场法 1.人工势场法基本思想：
人工势场法是一种虚拟力法。它模仿引力斥力下的物体运动， 目标点和运动体间为引力，运动体和障碍物间为斥力，通过建立 引力场斥力场函数进行路径寻优。优点是规划出来的路径平滑安 全、描述简单等，但是存在局部最优的问题，引力场的设计是算 法能否成功应用的关键。
第五章 机器人路径规划
著名学者蒋新松将路径规划定义为路径规划是移动 机器人的一个重要组成部分,它的任务就是在具有障碍物 的环境内按照一定的评价标准如工作代价最小、行走路 线最短、行走时间最短等,寻找一条从起始状态包括位置 和姿态到达目标状态包括位置和姿态的无碰路径。
2
一、路径规划概述 路径规划需要解决的问题：
第五章 机器人路径规划
1.使机器人能从初始位置运动到目标位置。 2.一定的算法使机器人能绕开障碍物,并且经过某些 必须经过的点完成相应的作业任务。 3.在完成以上任务的前提下,尽量优化机器人运行轨迹。
3
二、路径规划的分类
第五章 机器人路径规划
按对环境信息的把握程度分为全局或局部路径 规划：
2.自由空间法的优缺点：
自由空间法的优点是比较 灵活,机器人的起始点和目标 点的改变不会造成连通图的重 新构造。
自由空间法的缺点为不是任 何时候都可以获得最短路径。
第五章 机器人路径规划
由算法找到的路径
9
四、栅格法
第五章 机器人路径规划
用编码的栅格来表示地图，把包含障碍物的栅格标记为障碍栅 格，反之则为自由栅格，以此为基础作路径搜索。栅格法一般作为 路径规划的环境建模技术来用，作为路径规划的方法它很难解决复 杂环境信息的问题，一般需要与其他智能算法相结合。
1.基于先验完全信息的是全局路径规划；全局路径规划 属于静态规划( 又称离线规划)。全局路径规划需要掌握所 有的环境信息，根据环境地图的所有信息进行路径规划。
2.基于传感器信息的是局部路径规划。局部路径规划属 于动态规划( 又称在线规划)。局部路径规划只需要由传感 器实时采集环境信息，了解环境地图信息，然后确定出所在 地图的位置及其局部的障碍物分布情况，从而可以选出从当 前结点到某一子目标结点的最优路径。
7
三、自由空间法
第五章 机器人路径规划
1.自由空间法基本思想：
自由空间法的基本思 想是采用预先定义的基本 形状如广义锥形,凸多边形 等构造自由空间,并将自由 空间表示为连通图,然后通 过对图的搜索来规划路径, 其算法的复杂度往往与障 碍物的个数成正比。
由两个障碍和工作空间边界生成的广义锥
8
三、自由空间法
13
五、人工势场法
2.人工势场法的两个问题：
（3）避免死锁的改
进算法： APF与随机采样相结
合如RPP算法、APF与遗 传算法（GA）相结合、 APF与其他全局优化算法 相结合：如：粒群算法， 蚁群算法，模拟退火法， 附加动量法等。
第五章 机器人路径规划
14
六、蚁群算法
第五章 机器人路径规划
1.蚁群算法基本思想：
蚁群算法通过模拟蚁群搜索食物的过程,达到求解比较困难的 组合优化问题的目的。该方法是受到对真实蚁群行为研究的启发而 提出的。仿生学家经过大量细致的观察研究发现,蚂蚁个体之间是 通过一种称之为外激素的物质进行信息传递的。蚂蚁在运动过程中, 能够在它所经过的路径上留下该种物质,而且蚂蚁在运动过程中能 够感知这种物质的存在及其强度,并以此指导自己的运动方向,蚂蚁 倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的蚁 群的集体行为便表现出一种信息正反馈现象某一路经上走过的蚂蚁 越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过 这种信息的交流达到搜索食物的目的。 算法通过迭代来模拟蚁群觅食的行为达到目的。具有良好的全局优 化能力、本质上的并行性、易于用计算机实现等优点，但计算量大、 易陷入局部最优解，不过可通过加入精英蚁等方法改进。 15