1、 第五章 机器人路径规划机器人路径规划机器人路径规划 第五章 机器人路径规划第一节第一节 路径规划分类路径规划分类3 3一、路径规划概述一、路径规划概述 n什么是路径规划？什么是路径规划？著名学者蒋新松将路径规划定义为路径规划是移动 机器人的一个重要组成部分,它的任务就是在具有障碍物 的环境内按照一定的评价标准如工作代价最小、行走路 线最短、行走时间最短等,寻找一条从起始状态包括位置 和姿态到达目标状态包括位置和姿态的无碰路径。第五章 机器人路径规划4 4一、路径规划概述一、路径规划概述 n路径规划需要解决的问题：路径规划需要解决的问题：1.使机器人能从初始位置运动到目标位置。2.一定的算法使
2、机器人能绕开障碍物,并且经过某些必须经过的点完成相应的作业任务。3.在完成以上任务的前提下,尽量优化机器人运行轨迹。第五章 机器人路径规划5 5二、路径规划的分类二、路径规划的分类 n按对环境信息的把握程度分为全局或局部路径按对环境信息的把握程度分为全局或局部路径规划：规划：1.基于先验完全信息的是全局路径规划；全局路径规划属于静态规划(又称离线规划)。全局路径规划需要掌握所有的环境信息，根据环境地图的所有信息进行路径规划。2.基于传感器信息的是局部路径规划。局部路径规划属于动态规划(又称在线规划)。局部路径规划只需要由传感器实时采集环境信息，了解环境地图信息，然后确定出所在地图的位置及其局部
3、的障碍物分布情况，从而可以选出从当前结点到某一子目标结点的最优路径。第五章 机器人路径规划第五章 机器人路径规划第二节第二节 路径规划方法路径规划方法7 7一、路径规划方法一、路径规划方法 n1.1.传统方法：传统方法：可视图法、自由空间法、栅格法、人工势场法 第五章 机器人路径规划n2.2.智能方法：智能方法：蚁群算法、神经网络、遗传算法n3.3.其他方法：其他方法：A*算法、Dijkstra 算法8 8二、可视图法二、可视图法 第五章 机器人路径规划 对可视图进行搜索,并利用优化算法删除一些不必要的连线以简化可视图,缩短了搜索时间,最终就可以找到一条无碰最优路径。优点是可以求得最短路径,缺
4、点是此法缺乏灵活性,即一旦机器人的起点和目标点发生改变,就要重新构造可视图,比较麻烦。9 9三、自由空间法三、自由空间法 第五章 机器人路径规划 自由空间法的基本思想是采用预先定义的基本形状如广义锥形,凸多边形等构造自由空间,并将自由空间表示为连通图,然后通过对图的搜索来规划路径,其算法的复杂度往往与障碍物的个数成正比。由两个障碍和工作空间边界生成的广义锥n1.1.自由空间法基本思想：自由空间法基本思想：101111三、自由空间法三、自由空间法 第五章 机器人路径规划 自由空间法的优点是比较灵活,机器人的起始点和目标点的改变不会造成连通图的重新构造。自由空间法的缺点为不是任何时候都可以获得最短
5、路径。n2.2.自由空间法的优缺点：自由空间法的优缺点：由算法找到的路径1212四、栅格法四、栅格法 第五章 机器人路径规划 用编码的栅格来表示地图，把包含障碍物的栅格标记为障碍栅格，反之则为自由栅格，以此为基础作路径搜索。栅格法一般作为路径规划的环境建模技术来用，作为路径规划的方法它很难解决复杂环境信息的问题，一般需要与其他智能算法相结合。上图中灰色区域为障碍物 上图黄色路线为该算法得到的最优路径1313五、人工势场法五、人工势场法 第五章 机器人路径规划 人工势场法是一种虚拟力法。它模仿引力斥力下的物体运动，目标点和运动体间为引力，运动体和障碍物间为斥力，通过建立引力场斥力场函数进行路径寻
6、优。优点是规划出来的路径平滑安全、描述简单等，但是存在局部最优的问题，引力场的设计是算法能否成功应用的关键。n1.1.人工势场法基本思想：人工势场法基本思想：1414第五章 机器人路径规划五、人工势场法五、人工势场法 1515五、人工势场法五、人工势场法 第五章 机器人路径规划n2.2.人工势场法的两个问题：人工势场法的两个问题：（1)非点形障碍物 普通的障碍物的形状不是一个点，如何确定一个障碍物对机器人的排斥力呢？方案1：计算障碍物内所有点斥力的合力。方案2：用离障碍物最近的点进行计算。（2)死锁（dead lock）现象1616五、人工势场法五、人工势场法 第五章 机器人路径规划n2.2.
7、人工势场法的两个问题：人工势场法的两个问题：（3）避免死锁的改进算法：APF与随机采样相结合如RPP算法、APF与遗传算法（GA）相结合、APF与其他全局优化算法相结合：如：粒群算法，蚁群算法，模拟退火法，附加动量法等。1717 六、蚁群算法六、蚁群算法 第五章 机器人路径规划 蚁群算法通过模拟蚁群搜索食物的过程,达到求解比较困难的组合优化问题的目的。该方法是受到对真实蚁群行为研究的启发而提出的。仿生学家经过大量细致的观察研究发现,蚂蚁个体之间是通过一种称之为外激素的物质进行信息传递的。蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且蚂蚁在运动过程中能够感知这种物质的存在及其强度,并
8、以此指导自己的运动方向,蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象某一路经上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。算法通过迭代来模拟蚁群觅食的行为达到目的。具有良好的全局优化能力、本质上的并行性、易于用计算机实现等优点，但计算量大、易陷入局部最优解，不过可通过加入精英蚁等方法改进。n1.1.蚁群算法基本思想：蚁群算法基本思想：1818 六、蚁群算法六、蚁群算法 第五章 机器人路径规划 设A是巢穴,E是食物源,CM为一障碍物。由于障碍物的存在,蚂蚁要从A到E或E从到A,只能沿
9、路线BCD或BMD通过,各点之间的距离如图所示。设每个单位时间有50只蚂蚁由到达,蚂蚁过后留下的激素物质量信息素为1,为方便起见,假设信息素挥发时间为10。在初始时刻,由于路径BC、BM、CD、DM上均无信息素存在,位于B的蚂蚁可以随机选择路径。n2.2.蚁群算法运用分析：蚁群算法运用分析：1919 六、蚁群算法六、蚁群算法 第五章 机器人路径规划 从统计的角度可以认为开始时它们以相同的概率选择路径BCD、BMD,这样由于路径短,相同时间内最终造成通过BCD的蚂蚁比通过BMD的多,使得BCD上的信息素比BMD上的多,这样又吸引更多的蚂蚁沿路径走,直至最终所有蚂蚁选择路径BCD,从而找到由蚁巢到
10、食物源的最短路径。由此可见,蚂蚁个体之间的信息交换是一个正反馈过程。2020七、神经网络算法（七、神经网络算法（Neural NetworksNeural Networks）第五章 机器人路径规划 神经网络算法是人工智能领域中的一种非常优秀的算法，它主要模拟动物神经网络行为，进行分布式并行信息处理。但它在路径规划中的应用却并不成功，因为路径规划中复杂多变的环境很难用数学公式进行描述，如果用神经网络去预测学习样本分布空间以外的点，其效果必然是非常差。尽管神经网络具有优秀的学习能力，但是泛化能力差是其致命缺点。但因其学习能力强鲁棒性好，它与其他算法的结合应用已经成为路径规划领域研究的热点。2121
11、八、遗传算法（八、遗传算法（Genetic AlgorithmsGenetic Algorithms）第五章 机器人路径规划 遗传算法是当代人工智能科学的一个重要研究分支，是一种模拟达尔文遗传选择和自然淘汰的生物进化过程中的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是按照基因遗传学原理而实现的一种迭代过程的搜索算法。最大的优点是易于与其他算法相结合，并充分发挥自身迭代的优势，缺点是运算效率不高，不如蚁群算法有先天优势，但其改进算法也是目前研究的热点。第五章 机器人路径规划第三节第三节 路径规划应用路径规划应用2323 一、全球第一个能自动避开障碍一、全球第一个能自动避开障碍物的机器
12、人物的机器人ShakeyShakey 第五章 机器人路径规划 1969年美国斯坦福国际研究所(Stanford Research Institute,SRI)研制了移动式机器人Shakey,这是首台采用了人工智能学的移动机器人，Shakey具备一定人工智能，能够自主进行感知、环境建模、行为规划并执行任务(如寻找木箱并将其推到指定目的位置)。它装备了电视摄像机、三角法测距仪、碰撞传感器、驱动电机以及编码器，并通过无线通讯系统由二台计算机控制。图像识别采用麻省理工（MIT）的Image-Understanding算法（Roberts，1965）图像处理耗时巨大，shakey的移动速度很慢，每小时只
13、能移动几米。2424第五章 机器人路径规划 扫地机器人采用随机覆盖法，有人也称为随机碰撞式导航，但这并非是指机器人真正与环境中的物体产生碰撞，也非毫无章法的在地板上随机移动。随机覆盖法是指机器人根据一定的移动算法，如三角形、五边形轨迹尝试性的覆盖作业区，如果遇到障碍，则执行对应的转向函数。这种方法是一种以时间换空间的低成本策略，如不计时间可以达到 100%覆盖率。二、扫地机器人二、扫地机器人ROOMBAROOMBA2525第五章 机器人路径规划二、扫地机器人二、扫地机器人ROOMBAROOMBA 随机覆盖法不用定位、也没有环境地图，也无法对路径进行规划，所以其移动路径基本依赖于内置的算法，算法
14、的优劣也决定了其清扫质量与效率的高低。2626第五章 机器人路径规划二、扫地机器人二、扫地机器人ROOMBAROOMBA 随机覆盖法不用定位、也没有环境地图，也无法对路径进行规划，所以其移动路径基本依赖于内置的算法，算法的优劣也决定了其清扫质量与效率的高低。三、火星探测器三、火星探测器DD*算法：算法：D*是动态A*（D-Star,Dynamic A*）卡内基梅隆机器人中心的Stentz在1994和1995年两篇文章提出，主要用于机器人探路。是火星探测器采用的寻路算法，适合于动态路径规划。D*算法的思路可以推广到改造自由空间法使其具有动态规划功能 第五章 机器人路径规划第四节第四节 路径规划展望路径规划展望2828第五章 机器人路径规划一、先进路径规划算法的改进一、先进路径规划算法的改进二、路径规划算法的有效结合二、路径规划算法的有效结合(即混合算法即混合算法)四、多智能体并联路径规划算法设计四、多智能体并联路径规划算法设计三、环境建模技术和路径规划算法的结合三、环境建模技术和路径规划算法的结合路径规划发展趋势路径规划发展趋势归纳总结路径规划分类路径规划方法路径规划应用路径规划展望第五章 机器人路径规划E N DE N D30
