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

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