改进蚁群优化算法求解移动机器人路径规划问题
- 格式：pdf
- 大小：471.23 KB
- 文档页数：5
第 35 卷 第 5 期 2011 年 10 月
南京理工大学学报
Journal of Nanjing University of Science and Technology
Vol． 35 No． 5 Oct． 2011
改进蚁群优化算法求解移动机器人路径规划问题
1， 2 1 2， 3 赵娟平 ， 高宪文 ， 符秀辉
图3 栅格环境对应的图结构 图2 栅格的直接编码
2
改进蚁群算法的设计
1
基于栅格法的环境建模
蚁群算法虽然具有并行、 正反馈、 强鲁棒、 全 局最优等优点， 但同时也不可避免地具有搜索收 敛速度慢， 易陷入局部最优的缺点。 本文主要针 对蚁群算法这两方面的不足进行改进 。 2． 1 蚂蚁双向并行搜索策略 传统蚁群算法中， 蚂蚁从起点出发到达终点 时才会有新路径生成； 这并没有充分发挥蚂蚁的 使得较优解的生成速度偏慢， 影响了算法 协作性， 的效率和收敛速度。 为了提高算法的效率， 充分 1］提出了双向并 发挥蚁群的相互协作性， 文献［ 行搜索策略， 即： 所有蚂蚁分成相同数量的 2 组， 分别从起点和终点相向并行搜索路径 。采用这种 搜索算法， 不仅可提高初始可行解的构造效率 ， 也 保证了搜索的多样性， 使搜索不易陷于停滞， 因 此， 本文借鉴并采用这种策略。 2． 2 新的蚂蚁相遇判别策略 蚂蚁双向并行搜索寻优过程中， 会出现寻优 方向不同的 2 只蚂蚁相遇的情况， 这 2 只蚂蚁分 结合它们的信息， 连接相 别携带各自的搜寻信息， 遇蚂蚁所走的路径即为一条可行路径 。那么采用 何种方式来确定蚂蚁何时相遇便成为焦点问题 。 大多数文献都是通过对两栅格间的距离值 d（ g i ， g j ） 来判断蚂蚁是否相遇， 即： 算法执行过程 k j 的位置分 中的某时刻， 来自不同方向的蚂蚁 k i 、
算法执行过程中， 具有不同 flag k 值的 2 只蚂 k 、 k ， 蚁 1 2 相遇时 通过连接这 2 只蚂蚁禁忌表中 的记录便可得到一条新路径。蚂蚁相遇的路径可 以描述为： L new = L（ ant_tabu k1 ） ∩L（ ant_tabu k2 ） （ 1）
L （ ant 式中： L new 是通过区域内相遇得到的新路径， _tabu k1 ） 和 L （ ant _ tabu k2 ） 是 k1 、 k2 相遇时根据其 禁忌表得到的一段路径。 45 号栅格内既有信息素 τ 0 （ i， 图 4 中， j） （ 0 ） ， 1 （ i， 又有信息素τ 由此可判断出 2 只蚂蚁在 j） （ 0 ） ，
栅格法由 Howden 于 1968 年提出， 是目前应 用最广泛、 也较为成功的环境建模方法。 该方法 简单有效， 对障碍物的适应能力强， 便于计算机存 计算和使用， 已成功应用于多种成熟算法和技 储、 术。因此， 本文仍采用栅格法划分移动机器人工 ［9 ］ 作环境空间 。 首先按栅格法划分机器人工作空间； 为进一步 简化问题， 同时确保运动的安全性， 根据机器人物 理实体的体积半径， 对障碍物进行适当膨胀， 最终 ， 可将机器人实体转化为质点来简化处理 如图 1 所 示。再利用直角坐标法进行栅格标识， 如图 2 所 示； 同时环境的表达借助图论思想， 如图 3 所示。 此时所谓的路径规划就是在如图 3 所示的栅 格环境中规划出一条从起始点到目标点的一序列 自由栅格节点。
图4 蚂蚁相遇判别图
g1 是来自于起点 Start 的某只蚂蚁 k1 图 4 中， g2 是来 在算法执行过程中某时刻 t 所处的位置， 自于终点 Goal 的某只蚂蚁 k2 在算法执行过程中 某时刻 t 所处的位置； 实线是蚂蚁 k1 所走过的路 虚线是蚂蚁 k2 所走过的路径。 径， k1 、 k2 2 只蚂蚁在不同时刻先后 由图 4 可知， 而在同一时刻 t 它们之间的距离 经过 g2 点， | d （ g1 ， g2 ） | ＞槡 2 。若按文献［ 1］的相遇判别策略 2 只蚂蚁没有相遇， 判别， 它们之间无可行路径。 而事实上， 它们之间存在可行路径。 可见， 文献 ［ 1］ 所提出的相遇判别策略丢失了部分 可 行 路 径， 人为地缩小了寻优范围， 甚至可能导致算法无 法获得最优解。 因此， 本文提出新的判别策略判 断蚂蚁是否相遇。 0 （ i， 定义 1 记τ j） （ 0 ） 为起点 Start 的信息素 ， 1 （ i， τ j） （ 0 ） 为终点 Goal 的信息素 。 定义 2 算法执行过程中某时刻， 对某一栅 格来说， 若该点既有来自于起点蚂蚁释放的信息素 0 （ i， τ j） （ 0 ） ，又有来 自 于 终 点 蚂 蚁 释 放 的 信 息 素 1 （ i， k2 相遇。 则称 k1 、 τ j） （ 0 ） ，
（ 1． 东北大学 信息科学与技术学院， 辽宁 沈阳 110819 ； 2． 沈阳化工大学 信息工程学院， 辽宁 沈阳 110142 ； 3． 中科院 沈阳自动化所， 辽宁 沈阳 110015 ）
摘 要： 针对蚂蚁双向并行搜索策略会丢失蚂蚁间的部分可行路径甚至最优路径的问题， 该文采 用栅格法建立移动机器人环境模型， 提出了根据信息素判断蚂蚁是否相遇的新的蚂蚁相遇判别 。 ， 法 为避免算法陷入局部最优 提出了综合考虑多种因素的新的路径选择策略和全局信息素更新 策略。二维环境下的仿真研究表明， 只要路径客观存在， 算法就能快速地规划出相应的安全路径。 关键词： 蚁群优化； 路径规划； 移动机器人； 栅格法； 双向并行搜索 中图分类号： TP242 文章编号： 1005－9830 （ 2011 ） 05－0637－05
α
k2 ， 且 ant_ta此处相遇。找到经过该点的蚂蚁 k1 、 12 ， 23 ， 33 ， 44 ， 45 ， 35 ， 26 ， 17 ｝ ， bu k1 的记录为｛ Start， ant_ tabu k2 的记录为 ｛ Goal， 90 ， 80 ， 70 ， 59 ， 58 ， 57 ， 46 ， 45 ｝ ， 连接 ant _ tabu k1 和 ant _ tabu k2 的记录可得 12 ， 23 ， 33 ， 44 ， 45 ， 46 ， 57 ， 58 ， 59 ， 新路径为： ｛ Start， 70 ， 80 ， 90 ， Goal｝ 。 2． 3 新的路径选择策略 蚁群算法中转移概率仅仅取决于历史信息 路径的选择缺乏未来信 τij 和当前信息 η ij ； 因此， 使得算法易陷入局部最优。因此， 本文 息的指导， 提出了节点活跃度的概念。 定义 3 节点 j 的活跃度： 表示在一次迭代 ， 中 种群在节点 j 建立的节点连接的分支程度， 记 liveness 。 为 j liveness j = node_branch j / n （ 2） 式中： node_branch j 表示节点 j 具有的分支数目。 由节点活跃度的定义可知： 节点的分支数越 多， 节点的活跃度越高； 选择该节点后， 候选节点 就越多， 种群的多样性将得以保持， 故而算法不易 陷入局部最优。因此， 为预防局部最优的出现， 应 尽量选择节点活跃程度高的节点 。 具有城市活跃度的转移概率公式为 ：
Email： zjp020417@ 作者简介： 赵娟平（ 1972－ ） ， 女， 博士生， 讲师， 主要研究方向： 机器人控制、 智能控制及其应用， 163． com。
638
南京理工大学学报
第 35 卷第 5 期
统， 具有较强的鲁棒性、 优良的分布式计算、 易于 ［6 ， 7 ］ 。 其生物机理是蚁群 与其他算法结合等优点 在蚁巢与食物源间寻觅一条最短的可行路径 ， 这 恰好与机器人路径规划的物理过程不谋而合 ； 二 为基于蚁群算法的 者在内部机理上的天然联系， ［8 ］ 路径规划研究提供了有力依据 。 在采用栅格法建立了移动机器人环境模型 1］提出的蚂蚁双向并行搜索 后， 本文借鉴文献［ 策略， 该方法可充分利用蚂蚁的协作和优化能力 ， 1］方法会丢失蚂 加速了寻优速度； 但由于文献［ 蚁间的部分可行路径， 甚至导致算法无法找到最 优解， 本文提出了新的蚂蚁相遇判别法。 为防止 算法陷入局部最优、 加快算法收敛速度， 给出了综 合考虑过去、 现在及未来信息的新的路径选择策 以及根据全局信息、 局部信息和节点活跃度等 略， 因素仅更新部分较优蚂蚁信息素的新的全局信息 素更新法。在二维环境下进行了仿真研究， 仿真 结果表明： 即使在复杂环境下， 该算法仍能快速地 规划出安全的可行路径。
图1
障碍物的膨化处理
gj ， g j ） | ≤槡 2， g j 之间有 别为 g i 、 若有 | d （ g i ， 且 gi 、
总第 180 期
赵娟平
高宪文
符秀辉
改进蚁群优化算法求解移动机器人路径规划问题
639
k j 相遇。但采用这种方式定 逻辑连接边， 则称 k i 、 ， 、 如图 4 所示。 义时 容易忽略 丢失一些可行路径，
Improved Ant Colony Optimization Algorithm for Solving Path Planning Problem of Mobile Robot
2 3 ZHAO Juanping1 ， ， GAO Xianwen1 ， FU Xiuhui2 ，
（ 1． School of Information Science and Technology， Northeastern University， Shenyang 110819 ， China； 2． School of Information Engineering， Shenyang University of Chemical Technology， Shenyang110142 ， China； 3． Shenyang Institute of Automation， Chinese Academy of Sciences， Shenyang 110015 ， China） Abstract： In view of that the ant colony optimization algorithm with a twoway parallel searching tacthe environment models of a tic has the defects of losing some feasible paths and even optimal paths， mobile robot are established by grids method and a new ants meeting judgment is used to solve the path planning problem of a mobile robot． The new judgment can judge if ants meet according to the kind of pheromones． A new path selecting method and a new global pheromone updating technique are proposed to avoid running into local optima． Simulation results of twodimension environment indicate that improved algorithm can plan a safe optimal path quickly for the existing paths． Key words： ant colony optimization； path planning； mobile robots； grids methods； twoway parallel searching 移动机器人路径规划是机器人学的重要分 支， 是研究机器人控制系统的基础问题 ， 长久以来 广受关注
南京理工大学学报
Journal of Nanjing University of Science and Technology
Vol． 35 No． 5 Oct． 2011
改进蚁群优化算法求解移动机器人路径规划问题
1， 2 1 2， 3 赵娟平 ， 高宪文 ， 符秀辉
图3 栅格环境对应的图结构 图2 栅格的直接编码
2
改进蚁群算法的设计
1
基于栅格法的环境建模
蚁群算法虽然具有并行、 正反馈、 强鲁棒、 全 局最优等优点， 但同时也不可避免地具有搜索收 敛速度慢， 易陷入局部最优的缺点。 本文主要针 对蚁群算法这两方面的不足进行改进 。 2． 1 蚂蚁双向并行搜索策略 传统蚁群算法中， 蚂蚁从起点出发到达终点 时才会有新路径生成； 这并没有充分发挥蚂蚁的 使得较优解的生成速度偏慢， 影响了算法 协作性， 的效率和收敛速度。 为了提高算法的效率， 充分 1］提出了双向并 发挥蚁群的相互协作性， 文献［ 行搜索策略， 即： 所有蚂蚁分成相同数量的 2 组， 分别从起点和终点相向并行搜索路径 。采用这种 搜索算法， 不仅可提高初始可行解的构造效率 ， 也 保证了搜索的多样性， 使搜索不易陷于停滞， 因 此， 本文借鉴并采用这种策略。 2． 2 新的蚂蚁相遇判别策略 蚂蚁双向并行搜索寻优过程中， 会出现寻优 方向不同的 2 只蚂蚁相遇的情况， 这 2 只蚂蚁分 结合它们的信息， 连接相 别携带各自的搜寻信息， 遇蚂蚁所走的路径即为一条可行路径 。那么采用 何种方式来确定蚂蚁何时相遇便成为焦点问题 。 大多数文献都是通过对两栅格间的距离值 d（ g i ， g j ） 来判断蚂蚁是否相遇， 即： 算法执行过程 k j 的位置分 中的某时刻， 来自不同方向的蚂蚁 k i 、
算法执行过程中， 具有不同 flag k 值的 2 只蚂 k 、 k ， 蚁 1 2 相遇时 通过连接这 2 只蚂蚁禁忌表中 的记录便可得到一条新路径。蚂蚁相遇的路径可 以描述为： L new = L（ ant_tabu k1 ） ∩L（ ant_tabu k2 ） （ 1）
L （ ant 式中： L new 是通过区域内相遇得到的新路径， _tabu k1 ） 和 L （ ant _ tabu k2 ） 是 k1 、 k2 相遇时根据其 禁忌表得到的一段路径。 45 号栅格内既有信息素 τ 0 （ i， 图 4 中， j） （ 0 ） ， 1 （ i， 又有信息素τ 由此可判断出 2 只蚂蚁在 j） （ 0 ） ，
栅格法由 Howden 于 1968 年提出， 是目前应 用最广泛、 也较为成功的环境建模方法。 该方法 简单有效， 对障碍物的适应能力强， 便于计算机存 计算和使用， 已成功应用于多种成熟算法和技 储、 术。因此， 本文仍采用栅格法划分移动机器人工 ［9 ］ 作环境空间 。 首先按栅格法划分机器人工作空间； 为进一步 简化问题， 同时确保运动的安全性， 根据机器人物 理实体的体积半径， 对障碍物进行适当膨胀， 最终 ， 可将机器人实体转化为质点来简化处理 如图 1 所 示。再利用直角坐标法进行栅格标识， 如图 2 所 示； 同时环境的表达借助图论思想， 如图 3 所示。 此时所谓的路径规划就是在如图 3 所示的栅 格环境中规划出一条从起始点到目标点的一序列 自由栅格节点。
图4 蚂蚁相遇判别图
g1 是来自于起点 Start 的某只蚂蚁 k1 图 4 中， g2 是来 在算法执行过程中某时刻 t 所处的位置， 自于终点 Goal 的某只蚂蚁 k2 在算法执行过程中 某时刻 t 所处的位置； 实线是蚂蚁 k1 所走过的路 虚线是蚂蚁 k2 所走过的路径。 径， k1 、 k2 2 只蚂蚁在不同时刻先后 由图 4 可知， 而在同一时刻 t 它们之间的距离 经过 g2 点， | d （ g1 ， g2 ） | ＞槡 2 。若按文献［ 1］的相遇判别策略 2 只蚂蚁没有相遇， 判别， 它们之间无可行路径。 而事实上， 它们之间存在可行路径。 可见， 文献 ［ 1］ 所提出的相遇判别策略丢失了部分 可 行 路 径， 人为地缩小了寻优范围， 甚至可能导致算法无 法获得最优解。 因此， 本文提出新的判别策略判 断蚂蚁是否相遇。 0 （ i， 定义 1 记τ j） （ 0 ） 为起点 Start 的信息素 ， 1 （ i， τ j） （ 0 ） 为终点 Goal 的信息素 。 定义 2 算法执行过程中某时刻， 对某一栅 格来说， 若该点既有来自于起点蚂蚁释放的信息素 0 （ i， τ j） （ 0 ） ，又有来 自 于 终 点 蚂 蚁 释 放 的 信 息 素 1 （ i， k2 相遇。 则称 k1 、 τ j） （ 0 ） ，
（ 1． 东北大学 信息科学与技术学院， 辽宁 沈阳 110819 ； 2． 沈阳化工大学 信息工程学院， 辽宁 沈阳 110142 ； 3． 中科院 沈阳自动化所， 辽宁 沈阳 110015 ）
摘 要： 针对蚂蚁双向并行搜索策略会丢失蚂蚁间的部分可行路径甚至最优路径的问题， 该文采 用栅格法建立移动机器人环境模型， 提出了根据信息素判断蚂蚁是否相遇的新的蚂蚁相遇判别 。 ， 法 为避免算法陷入局部最优 提出了综合考虑多种因素的新的路径选择策略和全局信息素更新 策略。二维环境下的仿真研究表明， 只要路径客观存在， 算法就能快速地规划出相应的安全路径。 关键词： 蚁群优化； 路径规划； 移动机器人； 栅格法； 双向并行搜索 中图分类号： TP242 文章编号： 1005－9830 （ 2011 ） 05－0637－05
α
k2 ， 且 ant_ta此处相遇。找到经过该点的蚂蚁 k1 、 12 ， 23 ， 33 ， 44 ， 45 ， 35 ， 26 ， 17 ｝ ， bu k1 的记录为｛ Start， ant_ tabu k2 的记录为 ｛ Goal， 90 ， 80 ， 70 ， 59 ， 58 ， 57 ， 46 ， 45 ｝ ， 连接 ant _ tabu k1 和 ant _ tabu k2 的记录可得 12 ， 23 ， 33 ， 44 ， 45 ， 46 ， 57 ， 58 ， 59 ， 新路径为： ｛ Start， 70 ， 80 ， 90 ， Goal｝ 。 2． 3 新的路径选择策略 蚁群算法中转移概率仅仅取决于历史信息 路径的选择缺乏未来信 τij 和当前信息 η ij ； 因此， 使得算法易陷入局部最优。因此， 本文 息的指导， 提出了节点活跃度的概念。 定义 3 节点 j 的活跃度： 表示在一次迭代 ， 中 种群在节点 j 建立的节点连接的分支程度， 记 liveness 。 为 j liveness j = node_branch j / n （ 2） 式中： node_branch j 表示节点 j 具有的分支数目。 由节点活跃度的定义可知： 节点的分支数越 多， 节点的活跃度越高； 选择该节点后， 候选节点 就越多， 种群的多样性将得以保持， 故而算法不易 陷入局部最优。因此， 为预防局部最优的出现， 应 尽量选择节点活跃程度高的节点 。 具有城市活跃度的转移概率公式为 ：
Email： zjp020417@ 作者简介： 赵娟平（ 1972－ ） ， 女， 博士生， 讲师， 主要研究方向： 机器人控制、 智能控制及其应用， 163． com。
638
南京理工大学学报
第 35 卷第 5 期
统， 具有较强的鲁棒性、 优良的分布式计算、 易于 ［6 ， 7 ］ 。 其生物机理是蚁群 与其他算法结合等优点 在蚁巢与食物源间寻觅一条最短的可行路径 ， 这 恰好与机器人路径规划的物理过程不谋而合 ； 二 为基于蚁群算法的 者在内部机理上的天然联系， ［8 ］ 路径规划研究提供了有力依据 。 在采用栅格法建立了移动机器人环境模型 1］提出的蚂蚁双向并行搜索 后， 本文借鉴文献［ 策略， 该方法可充分利用蚂蚁的协作和优化能力 ， 1］方法会丢失蚂 加速了寻优速度； 但由于文献［ 蚁间的部分可行路径， 甚至导致算法无法找到最 优解， 本文提出了新的蚂蚁相遇判别法。 为防止 算法陷入局部最优、 加快算法收敛速度， 给出了综 合考虑过去、 现在及未来信息的新的路径选择策 以及根据全局信息、 局部信息和节点活跃度等 略， 因素仅更新部分较优蚂蚁信息素的新的全局信息 素更新法。在二维环境下进行了仿真研究， 仿真 结果表明： 即使在复杂环境下， 该算法仍能快速地 规划出安全的可行路径。
图1
障碍物的膨化处理
gj ， g j ） | ≤槡 2， g j 之间有 别为 g i 、 若有 | d （ g i ， 且 gi 、
总第 180 期
赵娟平
高宪文
符秀辉
改进蚁群优化算法求解移动机器人路径规划问题
639
k j 相遇。但采用这种方式定 逻辑连接边， 则称 k i 、 ， 、 如图 4 所示。 义时 容易忽略 丢失一些可行路径，
Improved Ant Colony Optimization Algorithm for Solving Path Planning Problem of Mobile Robot
2 3 ZHAO Juanping1 ， ， GAO Xianwen1 ， FU Xiuhui2 ，
（ 1． School of Information Science and Technology， Northeastern University， Shenyang 110819 ， China； 2． School of Information Engineering， Shenyang University of Chemical Technology， Shenyang110142 ， China； 3． Shenyang Institute of Automation， Chinese Academy of Sciences， Shenyang 110015 ， China） Abstract： In view of that the ant colony optimization algorithm with a twoway parallel searching tacthe environment models of a tic has the defects of losing some feasible paths and even optimal paths， mobile robot are established by grids method and a new ants meeting judgment is used to solve the path planning problem of a mobile robot． The new judgment can judge if ants meet according to the kind of pheromones． A new path selecting method and a new global pheromone updating technique are proposed to avoid running into local optima． Simulation results of twodimension environment indicate that improved algorithm can plan a safe optimal path quickly for the existing paths． Key words： ant colony optimization； path planning； mobile robots； grids methods； twoway parallel searching 移动机器人路径规划是机器人学的重要分 支， 是研究机器人控制系统的基础问题 ， 长久以来 广受关注
