蚁群算法及其在移动机器人路径规划中的应用剖析

会计学1蚁群算法及其在移动机器人路径规划中的蚁群算法及其在移动机器人路径规划中的应用剖析应用剖析n n题目选择：受亚马逊物流机器人启发，选题目选择：受亚马逊物流机器人启发，选择了移动机器人的路径规划。因为正在看择了移动机器人的路径规划。因为正在看蚁群算法，所以选择了蚁群算法，所以选择了蚁群算法及其在移动机器人路径规划中的应用。第1页/共14页n n1.1.蚁群算法的概念蚁群算法的概念n n蚁群算法是一种受到生物界中真实蚁群集蚁群算法是一种受到生物界中真实蚁群集觅食行为的启发式算法觅食行为的启发式算法,它模拟和借鉴了现它模拟和借鉴了现实世界中蚂蚁种群的行为特征。用来解决实世界中蚂蚁种群的行为特征。用来解决各种分布环境下的组合优化问题各种分布环境下的组合优化问题.该算法在该算法在求解旅行商求解旅行商()和作业调度等多目标和作业调度等多目标优化问题取得了不错的成果优化问题取得了不错的成果,且大量研究结且大量研究结果表明相对于其它人工智能算法果表明相对于其它人工智能算法,蚁群算法蚁群算法所取得的结果是最优的所取得的结果是最优的第2页/共14页n n2.2.蚁群算法的基本原理蚁群算法的基本原理图1.1初始状态蚂蚁随机挑选路径寻找食物图1.2经过一段时间后蚂蚁成功避开障碍物找到一条合适路径第3页/共14页n n3.3.蚁群算法的数学模型蚁群算法的数学模型n n设设 m m 表示蚂蚁总数量，用表示节点表示蚂蚁总数量，用表示节点 i i 和和节点节点 j j 之间的距离，表示在之间的距离，表示在 t t 时刻连线时刻连线上的信息素浓度。在初始时刻，上的信息素浓度。在初始时刻，m m只蚂蚁会只蚂蚁会被随机地放置，各路径上的初始信息素浓被随机地放置，各路径上的初始信息素浓度是相同的。在度是相同的。在 t t 时刻，蚂蚁时刻，蚂蚁 k k 从节点从节点i i转移到节点转移到节点 j j 的状态转移概率为的状态转移概率为 第4页/共14页n n 其中，其中，表示蚂蚁表示蚂蚁 k k 下一下一步可以选择的所有节点，步可以选择的所有节点，C C 为全部节点集为全部节点集合；合；为信息启发式因子，在算法中代表轨为信息启发式因子，在算法中代表轨迹相对重要程度，反映路径上的信息量对迹相对重要程度，反映路径上的信息量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间的协作性就越强；可称为期望启发蚂蚁间的协作性就越强；可称为期望启发式因子，在算法中代表能见度的相对重要式因子，在算法中代表能见度的相对重要性。是启发函数，在算法中表示由节点性。是启发函数，在算法中表示由节点i i 转移到节点转移到节点 j j 的期望程度，通常可取的期望程度，通常可取 。在算法运行时每只蚂蚁将根据。在算法运行时每只蚂蚁将根据(2-1)(2-1)式进式进行搜索前进。行搜索前进。第5页/共14页n n4.4.三种不同的基本蚁群算法模型三种不同的基本蚁群算法模型n n“蚁周系统蚁周系统”(Ant-Cycle)”(Ant-Cycle)模型模型第k只蚂蚁走过 ij 第6页/共14页n n“蚁量系统蚁量系统”(Ant-Quantity)”(Ant-Quantity)模型模型第k只蚂蚁在t和t+1之间走过第7页/共14页n n“蚁密系统蚁密系统”(Ant-Density)”(Ant-Density)模型模型第k只蚂蚁在t和t+1之间走过第8页/共14页开始设置参数，初始化蚁群蚂蚁构造路径应用局部更新规则一次循环结束？应用全局更新找出最短路径满足终止条件？结束否是否是5.5.蚁群系统流程图蚁群系统流程图第9页/共14页n n6.6.机器人路径规划机器人路径规划n n移动机器人导航的任务主要由定位、避障和移动机器人导航的任务主要由定位、避障和路径规划组成路径规划组成,其中路径规划是机器人控制最其中路径规划是机器人控制最为关键的技术。移动机器人路径规划是指在为关键的技术。移动机器人路径规划是指在有障碍物的工作环境中按照一定的评价标准有障碍物的工作环境中按照一定的评价标准(如工作代价最小、行走路线最短、行走时间如工作代价最小、行走路线最短、行走时间最短等最短等),),寻找一条从起始状态寻找一条从起始状态(包括位置和姿包括位置和姿态态)到达目标状态到达目标状态(包括位置和姿态包括位置和姿态)的无碰路的无碰路径。径。第10页/共14页n n7.7.机器人工作环境建模机器人工作环境建模n n我们通常利用栅格法建立环境模型，模拟机我们通常利用栅格法建立环境模型，模拟机器人工作的实际工作空间。采用栅格表示机器人工作的实际工作空间。采用栅格表示机器人工作的环境地图器人工作的环境地图,在处理障碍物边界时在处理障碍物边界时,可避免复杂的计算。在栅格法的应用中可避免复杂的计算。在栅格法的应用中,栅格栅格粒度的划分非常关键粒度的划分非常关键:栅格粒度越小栅格粒度越小,障碍物障碍物的表示会越精确的表示会越精确,但同时会占用大量的存储空但同时会占用大量的存储空间间,算法的搜索范围会按指数增加算法的搜索范围会按指数增加;栅格粒度栅格粒度太大太大,规划出的路径会很不精确。如图规划出的路径会很不精确。如图3.23.2，为截取的部分栅格环境，灰色栅格为障碍格，为截取的部分栅格环境，灰色栅格为障碍格，其它栅格为自由格其它栅格为自由格第11页/共14页第12页/共14页n n（1 1）近期对蚁群算法在移动机器人路径规）近期对蚁群算法在移动机器人路径规划中的应用研究还处于初期探索阶段划中的应用研究还处于初期探索阶段,研究研究重点主要集中在算法模型的建立与实例仿真重点主要集中在算法模型的建立与实例仿真方面方面,而对于算法的理论分析、与其他算法结而对于算法的理论分析、与其他算法结合等方面的研究较少合等方面的研究较少;n n （2 2）近期对蚁群算法在移动机器人路径）近期对蚁群算法在移动机器人路径规划的研究主要集中于静态环境下的路径规规划的研究主要集中于静态环境下的路径规划研究划研究,而对动态环境下的路径规划研究相对而对动态环境下的路径规划研究相对较少。较少。第13页/共14页