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

1、蚁群算法及其在移动机器人路径规划中的应用剖析Company Logou1.1.蚁群算法的概念蚁群算法的概念u蚁群算法是一种受到生物界中真实蚁群集觅食行蚁群算法是一种受到生物界中真实蚁群集觅食行为的启发式算法为的启发式算法, ,它模拟和借鉴了现实世界中蚂蚁它模拟和借鉴了现实世界中蚂蚁种群的行为特征。用来解决各种分布环境下的组种群的行为特征。用来解决各种分布环境下的组合优化问题合优化问题. .该算法在求解旅行商该算法在求解旅行商( () )和作业和作业调度等多目标优化问题取得了不错的成果调度等多目标优化问题取得了不错的成果, ,且大量且大量研究结果表明相对于其它人工智能算法研究结果表明相对于其它人

2、工智能算法, ,蚁群算法蚁群算法所取得的结果是最优的所取得的结果是最优的Company Logou2.2.蚁群算法的基本原理蚁群算法的基本原理图1.1初始状态蚂蚁随机挑选路径寻找食物图1.2经过一段时间后蚂蚁成功避开障碍物找到一条合适路径Company Logou 3.3.蚁群算法的数学模型蚁群算法的数学模型u设设 m m 表示蚂蚁总数量，用表示节点表示蚂蚁总数量，用表示节点 i i 和节点和节点 j j 之间的距离，表示在之间的距离，表示在 t t 时刻连线上的信息素浓度时刻连线上的信息素浓度。在初始时刻，。在初始时刻，m m只蚂蚁会被随机地放置，各路径只蚂蚁会被随机地放置，各路径上的初始信

3、息素浓度是相同的。在上的初始信息素浓度是相同的。在 t t 时刻，蚂蚁时刻，蚂蚁 k k 从节点从节点i i转移到节点转移到节点 j j 的状态转移概率为的状态转移概率为 otherpallowedttttkijkallowedkijijijijkij?,0j,)()()()(pkCompany Logou 其中，其中， 表示蚂蚁表示蚂蚁 k k 下一步可以下一步可以选择的所有节点，选择的所有节点，C C 为全部节点集合；为全部节点集合； 为信息启为信息启发式因子，在算法中代表轨迹相对重要程度，反发式因子，在算法中代表轨迹相对重要程度，反映路径上的信息量对蚂蚁选择路径所起的影响程映路径上的信息

4、量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间的协作性就越强；可称为度，该值越大，蚂蚁间的协作性就越强；可称为期望启发式因子，在算法中代表能见度的相对重期望启发式因子，在算法中代表能见度的相对重要性。是启发函数，在算法中表示由节点要性。是启发函数，在算法中表示由节点i i 转移转移到节点到节点 j j 的期望程度，通常可取的期望程度，通常可取 。在算法。在算法运行时每只蚂蚁将根据运行时每只蚂蚁将根据(2-1)(2-1)式进行搜索前进。式进行搜索前进。otherpallowedttttkijkallowedkijijijijkij?,0j,)()()()(pkkktabucallowed ij

5、ijijd/1Company Logou4.4.三种不同的基本蚁群算法模型三种不同的基本蚁群算法模型u“蚁周系统蚁周系统”(Ant-Cycle)”(Ant-Cycle)模型模型 otherLQkkij?,0,第k只蚂蚁走过 ij Company Logou“蚁量系统蚁量系统”(Ant-Quantity)”(Ant-Quantity)模型模型 otherdQijkij?,0,第k只蚂蚁在t和t+1之间走过Company Logou“蚁密系统蚁密系统”(Ant-Density)”(Ant-Density)模型模型otherQkij?,0,第k只蚂蚁在t和t+1之间走过Company Logo开始设

6、置参数，初始化蚁群蚂蚁构造路径应用局部更新规则一次循环结束？应用全局更新找出最短路径满足终止条件？结束否是否是5.5.蚁群系统流程图蚁群系统流程图Company Logou6.6.机器人路径规划机器人路径规划u移动机器人导航的任务主要由定位、避障和路径移动机器人导航的任务主要由定位、避障和路径规划组成规划组成, ,其中路径规划是机器人控制最为关键的技其中路径规划是机器人控制最为关键的技术。移动机器人路径规划是指在有障碍物的工作环术。移动机器人路径规划是指在有障碍物的工作环境中按照一定的评价标准境中按照一定的评价标准( (如工作代价最小、行走路如工作代价最小、行走路线最短、行走时间最短等线最短、

7、行走时间最短等),),寻找一条从起始状态寻找一条从起始状态( (包包括位置和姿态括位置和姿态) )到达目标状态到达目标状态( (包括位置和姿态包括位置和姿态) )的无的无碰路径。碰路径。Company Logou7.7.机器人工作环境建模机器人工作环境建模u我们通常利用栅格法建立环境模型，模拟机器人我们通常利用栅格法建立环境模型，模拟机器人工作的实际工作空间。采用栅格表示机器人工作的工作的实际工作空间。采用栅格表示机器人工作的环境地图环境地图, ,在处理障碍物边界时在处理障碍物边界时, ,可避免复杂的计算可避免复杂的计算。在栅格法的应用中。在栅格法的应用中, ,栅格粒度的划分非常关键栅格粒度的

8、划分非常关键: :栅栅格粒度越小格粒度越小, ,障碍物的表示会越精确障碍物的表示会越精确, ,但同时会占用但同时会占用大量的存储空间大量的存储空间, ,算法的搜索范围会按指数增加算法的搜索范围会按指数增加; ;栅栅格粒度太大格粒度太大, ,规划出的路径会很不精确。如图规划出的路径会很不精确。如图3.23.2，为截取的部分栅格环境，灰色栅格为障碍格，其它为截取的部分栅格环境，灰色栅格为障碍格，其它栅格为自由格栅格为自由格Company LogoCompany Logou（1 1）近期对蚁群算法在移动机器人路径规划中的）近期对蚁群算法在移动机器人路径规划中的应用研究还处于初期探索阶段应用研究还处于初期探索阶段, , 研究重点主要集中研究重点主要集中在算法模型的建立与实例仿真方面在算法模型的建立与实例仿真方面, ,而对于算法的理而对于算法的理论分析、与其他算法结合等方面的研究较少论分析、与其他算法结合等方面的研究较少; ;u （2 2）近期对蚁群算法在移动机器人路径规划）近期对蚁群算法在移动机器人路径规划的研究主要集中于静态环境下的路径规划