第16卷第2期 智能系统学报 Vol.16 No.2 2021年3月 CAAI Transactions on Intelligent Systems Mar.2021 D0:10.11992tis.202004011 网络出版地址：https:/ns.cnki.net/kcms/detail/23.1538.TP.20200716.1146.004html 基于变步长蚁群算法的移动机器人路径规划 徐玉琼123，娄柯2中，李志锟2 (1.广州大学松田学院电气与汽车工程系，广东广州511370：2.高端装备先进感知与智能控制教育部重，点实 验室，安徽芜湖241000,3.安徽工程大学安徽省电气传动与控制重点实验室，安徽芜湖241000) 摘要：针对传统蚁群算法以及双层蚁群算法在路径规划中存在搜索效率低、收敛性较慢以及成本较高的问 题，本文提出了变步长蚁群算法。该算法扩大蚁群可移动位置的集合，通过对跳点的选择以达到变步长策略， 有效缩短移动机器人路径长度：初始化信息素采用不均匀分布，加强起点至终点直线所涉及到栅格的信息素浓 度平行地向外衰减：改进启发式信息矩阵，调整移动机器人当前位置到终点位置的启发函数计算方法。试验结 果表明：变步长蚁群算法在路径长度及收敛速度两方面均优于双层蚁群算法及传统蚁群算法，验证了变步长蚁 群算法的有效性和优越性，是解决移动机器人路径规划问题的有效算法。 关键词：传统蚁群算法；双层蚁群算法；路径规划；变步长；信息素；启发函数；收敛；移动机器人 中图分类号：TP242.6文献标志码：A文章编号：1673-4785(2021)02-0330-08 中文引用格式：徐玉琼，娄柯，李志锟.基于变步长蚊群算法的移动机器人路径规划川.智能系统学报，2021,16(2)： 330-337. 英文引用格式：XU Yuqiong,.LOU Ke,,LI Zhikun..Mobile robot path planning based on variable--step ant colony algorithm. CAAI transactions on intelligent systems,2021,16(2):330-337. Mobile robot path planning based on variable-step ant colony algorithm XU Yuqiong"23,LOU Ke23,LI Zhikun2 (1.Department of Electrical and Automotive Engineering,Songtian College,Guangzhou University,Guangzhou 511370,China;2.Key Laboratory of Advanced Perception and Intelligent Control ofHigh-End Equipment,Ministry of Education,Wuhu 241000,China,3.An- hui Provincial Key Laboratory of Electric Transmission and Control,Anhui Polytechnic University,Wuhu 241000,China) Abstract:To address the problems of the traditional and double-layer ant colony algorithms,such as their low search ef- ficiency,slow convergence,and high path-planning cost,in this paper we propose a variable-step ant colony algorithm. The proposed algorithm expands the set of mobile locations of the ant colony,and uses the variable-step strategy of se- lecting the hopping points,thus effectively shortening the path length of the mobile robot.The initialization pheromone adopts an uneven distribution,which increases the pheromone concentration of the grid in a straight line from the start to end points,with the pheromone decaying outward in parallel.The heuristic information matrix is improved and the method used to calculate the heuristic function of the mobile robot from the current to the end positions is adjusted.The experimental results show that the performance of the variable-step ant colony algorithm is superior to those of the double-layer and traditional ant colony algorithms with respect to path length and convergence speed,which proves its eff- ectiveness and superiority.Thus,the proposed algorithm is effective in solving the path-planning problem of mobile robots. Keywords:traditional ant colony algorithm;double-layer ant colony algorithm;path planning;variable-step;pher- omone;heuristic function;convergence;mobile robot 在移动机器人领域，路径规划技术一直都是 收稿日期：2020-04-10.网络出版日期：2020-07-16 重要研究内容，其任务是在地图环境中为移动机 基金项目：国家自然科学基金项目(61572032)：安徽省高校自 然科学研究重点项目(KJ2019A0151.KJ20I9A0150): 器人从起点至终点避开障碍物而规划出的最优路 2018年度皖江高端装备制造协同创新中心开放基 金项目(GCKJ2018009). 径。目前国内外学者针对路径规划技术做了诸多 通信作者：徐玉琼.E-mail:xuyuqiong0104@163.com 研究，并取得相应成果，常用的传统路径规划算
DOI: 10.11992/tis.202004011 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20200716.1146.004.html 基于变步长蚁群算法的移动机器人路径规划 徐玉琼1,2,3，娄柯2,3，李志锟2,3 （1. 广州大学松田学院 电气与汽车工程系，广东 广州 511370; 2. 高端装备先进感知与智能控制教育部重点实 验室，安徽 芜湖 241000; 3. 安徽工程大学 安徽省电气传动与控制重点实验室，安徽 芜湖 241000） 摘 要：针对传统蚁群算法以及双层蚁群算法在路径规划中存在搜索效率低、收敛性较慢以及成本较高的问 题，本文提出了变步长蚁群算法。该算法扩大蚁群可移动位置的集合，通过对跳点的选择以达到变步长策略， 有效缩短移动机器人路径长度；初始化信息素采用不均匀分布，加强起点至终点直线所涉及到栅格的信息素浓 度平行地向外衰减；改进启发式信息矩阵，调整移动机器人当前位置到终点位置的启发函数计算方法。试验结 果表明：变步长蚁群算法在路径长度及收敛速度两方面均优于双层蚁群算法及传统蚁群算法，验证了变步长蚁 群算法的有效性和优越性，是解决移动机器人路径规划问题的有效算法。 关键词：传统蚁群算法；双层蚁群算法；路径规划；变步长；信息素；启发函数；收敛；移动机器人 中图分类号：TP242.6 文献标志码：A 文章编号：1673−4785(2021)02−0330−08 中文引用格式：徐玉琼, 娄柯, 李志锟. 基于变步长蚁群算法的移动机器人路径规划 [J]. 智能系统学报, 2021, 16(2): 330–337. 英文引用格式：XU Yuqiong, LOU Ke, LI Zhikun. Mobile robot path planning based on variable-step ant colony algorithm[J]. CAAI transactions on intelligent systems, 2021, 16(2): 330–337. Mobile robot path planning based on variable-step ant colony algorithm XU Yuqiong1,2,3 ，LOU Ke2,3 ，LI Zhikun2,3 (1. Department of Electrical and Automotive Engineering, Songtian College, Guangzhou University, Guangzhou 511370, China; 2. Key Laboratory of Advanced Perception and Intelligent Control of High-End Equipment, Ministry of Education, Wuhu 241000, China; 3. Anhui Provincial Key Laboratory of Electric Transmission and Control, Anhui Polytechnic University, Wuhu 241000, China) Abstract: To address the problems of the traditional and double-layer ant colony algorithms, such as their low search efficiency, slow convergence, and high path–planning cost, in this paper we propose a variable-step ant colony algorithm. The proposed algorithm expands the set of mobile locations of the ant colony, and uses the variable-step strategy of selecting the hopping points, thus effectively shortening the path length of the mobile robot. The initialization pheromone adopts an uneven distribution, which increases the pheromone concentration of the grid in a straight line from the start to end points, with the pheromone decaying outward in parallel. The heuristic information matrix is improved and the method used to calculate the heuristic function of the mobile robot from the current to the end positions is adjusted. The experimental results show that the performance of the variable-step ant colony algorithm is superior to those of the double-layer and traditional ant colony algorithms with respect to path length and convergence speed, which proves its effectiveness and superiority. Thus, the proposed algorithm is effective in solving the path-planning problem of mobile robots. Keywords: traditional ant colony algorithm; double-layer ant colony algorithm; path planning; variable-step; pheromone; heuristic function; convergence; mobile robot 在移动机器人领域，路径规划技术一直都是 重要研究内容，其任务是在地图环境中为移动机 器人从起点至终点避开障碍物而规划出的最优路 径。目前国内外学者针对路径规划技术做了诸多 研究，并取得相应成果，常用的传统路径规划算 收稿日期：2020−04−10. 网络出版日期：2020−07−16. 基金项目：国家自然科学基金项目 (61572032)；安徽省高校自 然科学研究重点项目 (KJ2019A0151，KJ2019A0150)； 2018 年度皖江高端装备制造协同创新中心开放基 金项目 (GCKJ2018009). 通信作者：徐玉琼. E-mail: xuyuqiong0104@163.com. 第 16 卷第 2 期 智 能 系 统 学 报 Vol.16 No.2 2021 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2021
第2期 徐玉琼，等：基于变步长蚁群算法的移动机器人路径规划 ·331· 法有遗传算法、模拟退火算法、人工势场法、 径规划，因此，需要对移动机器人工作环境进行 A*算法川等。随着人工智能技术的高速发展，群 建模，常规环境建模方法如栅格图法6、可视 智能算法在路径规划技术中得到广泛应用和发 图空间法、自由空间法、几何信息法等。本文选 展，如人工鱼群算法、蜂群算法、蚁群算法、蛙 取栅格图法对移动机器人二维空间进行建模，将 跳算法等，人工鱼群算法是一种擅长随机搜索的 栅格分为黑色区域和白色区域，其中黑色区域为 算法，其算法原理简单，对初始值要求较低，但在 障碍物栅格，白色区域为自由栅格，机器人可以 算法后期存在收敛速率缓慢、计算结果不够精 在白色区域自由移动，如图1所示，假设每个栅 确。蜂群算法作为模仿蜜蜂行为提出的启发式算 格为边长为1m的正方形，不考虑机器人自身身 法，通过对单一的蜜蜂进行局部寻优，突出全局 高和体积的影响，机器人始终处于正方形的正中 最优值，容易陷入局部最优，其算法鲁棒性不 心位置。 强。传统的群智能算法已经无法满足移动机器人 0 在复杂环境下进行路径规划，因此，大量学者通 过对传统的群智能算法进行改进，如多策略人工 15 鱼群算法刀、双层蚁群算法圆、启发机制下的蚁群 算法网等。改进的群智能算法已经明显提高复杂 环境下移动机器人的路径规划能力。 蚁群算法作为启发式全局优化算法是由意大 利学者Dorigo在1992年提出，该算法得益于采用 正反馈机制，收敛性能大幅提升，通过分布式计 468101214161820单位：m 算方式进行搜索以及不同个体同时并行计算，提 图1栅格地图 高了该算法的运算效率以及计算能力，但仍存在 Fig.1 Raster map 收敛速度慢以及死锁问题。因此，文献[9]对蚁 1.2搜索方式 群算法进行改进，提出了基于启发式机制的蚁群 传统蚁群算法中蚁群为单步长19201移动方 算法，该算法通过当前节点到终点的距离动态的 式，每步移动距离为1或互个单元格，在不碰撞 调整启发函数，当算法处于局部最优时，引入惩 障碍物的情况下，可以向四周共8个方向移动，如 罚函数机制，降低最优路径的信息素，减少蚁群 图2所示。 算法的正反馈影响而跳出局部最优。文献[14]主 要针对于蚁群算法收敛速度慢进行改进，合理分 配信息素初始浓度，动态调整信息素挥发因子， 进行二次路径规划，有效缩短了移动机器人的路 径长度。文献[8]设计了双层蚁群算法，对移动 机器人二维栅格环境进行凸化处理，同时用外层 蚁群探索出一条路径作为一个小环境，内层蚁群 在该环境下重新探索，两条路径择优筛选，提高 蚁群算法路径搜索质量。 为了提高蚁群算法收敛速度以及缩短路径长 度，本文提出变步长蚁群算法，寻找移动机器人 图2移动方式 可以达到的跳点，得到不同长度的路径，根据路 Fig.2 Moving method 径长度的不同，不均匀分配初始信息素浓度，以 蚁群在寻路过程中，利用信息素相互通信， 降低边缘障碍物对移动机器人的影响，从而提高 在经过的路径上释放信息素，当某一条路径通 算法的计算能力。改进启发式信息矩阵，提高蚁 过的蚂蚁越来越多时，该路径的信息素浓度就 群避障能力，增强蚁群全局路径搜索能力，快速 越高，其他蚂蚁选择该路径的概率就越大，起到 找到最优路径。 正反馈作用，同时也容易陷入局部最优及存在 1蚁群算法原理 死锁现象。信息素会随着时间的增长而挥发， 动态的调整各路径的信息素浓度，蚂蚁在选择 1.1环境表示 路径时，会对信息素浓度、启发因子、路径方向 移动机器人需要在二维空间环境下进行路 等因素进行综合判断选择下一步移动位置，并
法有遗传算法、模拟退火算法、人工势场法、 A*算法[1] 等。随着人工智能技术的高速发展，群 智能算法在路径规划技术中得到广泛应用和发 展，如人工鱼群算法、蜂群算法、蚁群算法[2-4] 、蛙 跳算法等，人工鱼群算法是一种擅长随机搜索的 算法，其算法原理简单，对初始值要求较低，但在 算法后期存在收敛速率缓慢、计算结果不够精 确。蜂群算法作为模仿蜜蜂行为提出的启发式算 法，通过对单一的蜜蜂进行局部寻优，突出全局 最优值，容易陷入局部最优，其算法鲁棒性不 强。传统的群智能算法已经无法满足移动机器人 在复杂环境下进行路径规划，因此，大量学者通 过对传统的群智能算法进行改进，如多策略人工 鱼群算法[5-7] 、双层蚁群算法[8] 、启发机制下的蚁群 算法[9] 等。改进的群智能算法已经明显提高复杂 环境下移动机器人的路径规划[10-15] 能力。 蚁群算法作为启发式全局优化算法是由意大 利学者 Dorigo 在 1992 年提出，该算法得益于采用 正反馈机制，收敛性能大幅提升，通过分布式计 算方式进行搜索以及不同个体同时并行计算，提 高了该算法的运算效率以及计算能力，但仍存在 收敛速度慢以及死锁问题。因此，文献 [9] 对蚁 群算法进行改进，提出了基于启发式机制的蚁群 算法，该算法通过当前节点到终点的距离动态的 调整启发函数，当算法处于局部最优时，引入惩 罚函数机制，降低最优路径的信息素，减少蚁群 算法的正反馈影响而跳出局部最优。文献 [14] 主 要针对于蚁群算法收敛速度慢进行改进，合理分 配信息素初始浓度，动态调整信息素挥发因子， 进行二次路径规划，有效缩短了移动机器人的路 径长度。文献 [8] 设计了双层蚁群算法，对移动 机器人二维栅格环境进行凸化处理，同时用外层 蚁群探索出一条路径作为一个小环境，内层蚁群 在该环境下重新探索，两条路径择优筛选，提高 蚁群算法路径搜索质量。 为了提高蚁群算法收敛速度以及缩短路径长 度，本文提出变步长蚁群算法，寻找移动机器人 可以达到的跳点，得到不同长度的路径，根据路 径长度的不同，不均匀分配初始信息素浓度，以 降低边缘障碍物对移动机器人的影响，从而提高 算法的计算能力。改进启发式信息矩阵，提高蚁 群避障能力，增强蚁群全局路径搜索能力，快速 找到最优路径。 1 蚁群算法原理 1.1 环境表示 移动机器人需要在二维空间环境下进行路 径规划，因此，需要对移动机器人工作环境进行 建模，常规环境建模方法如栅格图法[16-18] 、可视 图空间法、自由空间法、几何信息法等。本文选 取栅格图法对移动机器人二维空间进行建模，将 栅格分为黑色区域和白色区域，其中黑色区域为 障碍物栅格，白色区域为自由栅格，机器人可以 在白色区域自由移动，如图 1 所示，假设每个栅 格为边长为 1 m 的正方形，不考虑机器人自身身 高和体积的影响，机器人始终处于正方形的正中 心位置。 0 20 15 10 5 2 4 6 8 10 12 14 16 18 20 单位: m 图 1 栅格地图 Fig. 1 Raster map 1.2 搜索方式 √ 2 传统蚁群算法中蚁群为单步长[19-20] 移动方 式，每步移动距离为 1 或 个单元格，在不碰撞 障碍物的情况下，可以向四周共 8 个方向移动，如 图 2 所示。 图 2 移动方式 Fig. 2 Moving method 蚁群在寻路过程中，利用信息素相互通信， 在经过的路径上释放信息素，当某一条路径通 过的蚂蚁越来越多时，该路径的信息素浓度就 越高，其他蚂蚁选择该路径的概率就越大，起到 正反馈作用，同时也容易陷入局部最优及存在 死锁现象。信息素会随着时间的增长而挥发， 动态的调整各路径的信息素浓度，蚂蚁在选择 路径时，会对信息素浓度、启发因子、路径方向 等因素进行综合判断选择下一步移动位置，并 第 2 期 徐玉琼，等：基于变步长蚁群算法的移动机器人路径规划 ·331·
·332· 智能系统学报 第16卷 利用轮盘算法计算当前节点到下一到达节点的 3.16m,节点2至节点3路径长度为2m,因此，方 概率： 案1路径总长度为5.16m,方案2为节点1变步 [t(t0]P.[(t)P 长跳跃至节点4再到节点5，最后由节点5单步移 j∈aw p0= [t.(t)]严·[s(t)9 (1) 动至终点3，方案2路径总长度为4.65m,方案 3为传统蚁群算法的单步长移动方式，从当前节 0. 其他 点1到节点6，再移动到节点7，再移动到节点8， 1 no=du (2) 最后再到终点3，该方案路径总长度为4.83m,方 式中：为路径（位，）上的信息素；为位置i到 案4为节点1跳跃至节点9，从节点9单步长移动 位置j的启发因子；a为蚂蚁k下一步可到达节 到节点8，最后移动到终点3，该方案路径总长度 点的集合；α表征信息素重要程度；B表征启发因 为5.16m,显然，方案2作为变步长移动方式优于 子重要程度；d是蚂蚁从位置i到位置j构建的 其他方案，变步长蚁群算法在寻路过程中，对每 路径长度。 种方案的路径长度进行评估，最终挑选出路径最 为了避免蚂蚁选择已经达到过的节点，采用 短的方案。 禁忌表记录蚂蚁k当前所达到过的位置，经过1 时刻，所有蚂蚁都已完成了一次路径规划，计算 所有蚂蚁完成的有效路径长度，筛选出最短路径 长度，同时更新各路径上的信息素，经过时间的 增长，信息素将挥发一部分： Ty =(1-p)Tij (3) 式中：P是信息素挥发系数，同时，蚂蚁也将在路 径中释放信息素： T=t+∑△ (4) k=1 式中：△是第k只蚂蚁在所经过的路径上释放的 图3步长选择 Fig.3 Step size selection 信息素，定义如下： 在图3中，节点1为起始点，节点3为终点， 1/d,边i,)在路径T上 △=0，其他 (5) 移动机器人进行路径规划时，将节点1作为父节 点，通过变步长选择策略，将下一步移动机器人 由式（⑤）可知，蚂蚁所构建的路径长度d,越 要到达的节点4作为子节点，再将节点4作为父 小，那么各路径将得到更多的信息素，在以后的 节点确定下一子节点，以此方法进行迭代，最终 迭代中该路径被其他蚂蚁选择的概率也将更大。 确定了本轮迭代后的最优路径{1,4,5,3}，结合变 2 变步长蚁群算法 步长蚁群算法的优点，移动机器人对于下一步所 选择的节点越接近于终点，则可以减少节点转折 传统蚁群算法步长选择为单步长，蚁群仅能 的次数，同时，转折点越接近于障碍物，则可以减 向相邻栅格位置移动，不能满足移动机器人实际 少无效路径，因此，为了缩短移动机器人路径长 需求，且搜索效率低及路径长度无法满足最优， 度，引入终点诱导因子中及障碍物诱导因子山，其 因此，本文提出变步长选择策略，在避开障碍物 选择概率为 的条件下，移动机器人可以从当前位置向全局地 [t)]P·[0]B 图的任何位置移动，大幅提高移动机器人搜索 k中μ· Jeat p(0= ∑PTnOF (6) 效率。 0. 其他 2.1步长选择策略 跳点的选择即步长的选择，所谓跳点就是移 ∑ty. sEd 动机器人在搜索过程中从当前节点可以到达下一 = (7) 步的节点。如图3所示。移动机器人从起点到终 点有4条路径可供选择，方案1为当前节点1跳 跃至节点2再到终点3，节点1到节点2步长为 (8)
利用轮盘算法计算当前节点到下一到达节点的 概率： p k i j(t) = [τi j(t)]α ·[ηi j(t)]β ∑ s∈ak [τis(t)]α ·[ηis(t)]β , j ∈ ak 0, 其他 (1) ηi j = 1 di j (2) τi j (i, j) ηi j i j ak k α di j 式中： 为路径 上的信息素； 为位置 到 位置 的启发因子； 为蚂蚁 下一步可到达节 点的集合； 表征信息素重要程度；β 表征启发因 子重要程度； 是蚂蚁从位置 i 到位置 j 构建的 路径长度。 k t 为了避免蚂蚁选择已经达到过的节点，采用 禁忌表记录蚂蚁 当前所达到过的位置，经过 时刻，所有蚂蚁都已完成了一次路径规划，计算 所有蚂蚁完成的有效路径长度，筛选出最短路径 长度，同时更新各路径上的信息素，经过时间的 增长，信息素将挥发一部分： τi j = (1−ρ)τi j (3) 式中： ρ 是信息素挥发系数，同时，蚂蚁也将在路 径中释放信息素： τi j = τi j + ∑m k=1 ∆τ k i j (4) ∆τ k i j 式中： 是第 k 只蚂蚁在所经过的路径上释放的 信息素，定义如下： ∆τ k i j = 1/di j, 边(i, j)在路径T k上 0, 其他 (5) 由式 (5) 可知，蚂蚁所构建的路径长度 di j 越 小，那么各路径将得到更多的信息素，在以后的 迭代中该路径被其他蚂蚁选择的概率也将更大。 2 变步长蚁群算法 传统蚁群算法步长选择为单步长，蚁群仅能 向相邻栅格位置移动，不能满足移动机器人实际 需求，且搜索效率低及路径长度无法满足最优， 因此，本文提出变步长选择策略，在避开障碍物 的条件下，移动机器人可以从当前位置向全局地 图的任何位置移动，大幅提高移动机器人搜索 效率。 2.1 步长选择策略 跳点的选择即步长的选择，所谓跳点就是移 动机器人在搜索过程中从当前节点可以到达下一 步的节点。如图 3 所示。移动机器人从起点到终 点有 4 条路径可供选择，方案 1 为当前节点 1 跳 跃至节点 2 再到终点 3，节点 1 到节点 2 步长为 3.16 m，节点 2 至节点 3 路径长度为 2 m，因此，方 案 1 路径总长度为 5.16 m，方案 2 为节点 1 变步 长跳跃至节点 4 再到节点 5，最后由节点 5 单步移 动至终点 3，方案 2 路径总长度为 4.65 m，方案 3 为传统蚁群算法的单步长移动方式，从当前节 点 1 到节点 6，再移动到节点 7，再移动到节点 8， 最后再到终点 3，该方案路径总长度为 4.83 m，方 案 4 为节点 1 跳跃至节点 9，从节点 9 单步长移动 到节点 8，最后移动到终点 3，该方案路径总长度 为 5.16 m，显然，方案 2 作为变步长移动方式优于 其他方案，变步长蚁群算法在寻路过程中，对每 种方案的路径长度进行评估，最终挑选出路径最 短的方案。 1 2 3 4 5 6 7 8 9 图 3 步长选择 Fig. 3 Step size selection ϕ µ 在图 3 中，节点 1 为起始点，节点 3 为终点， 移动机器人进行路径规划时，将节点 1 作为父节 点，通过变步长选择策略，将下一步移动机器人 要到达的节点 4 作为子节点，再将节点 4 作为父 节点确定下一子节点，以此方法进行迭代，最终 确定了本轮迭代后的最优路径{1,4,5,3}，结合变 步长蚁群算法的优点，移动机器人对于下一步所 选择的节点越接近于终点，则可以减少节点转折 的次数，同时，转折点越接近于障碍物，则可以减 少无效路径，因此，为了缩短移动机器人路径长 度，引入终点诱导因子 及障碍物诱导因子 ，其 选择概率为 p k i j(t) = k · ϕ · µ · [τi j(t)]α ·[ηi j(t)]β ∑ s∈ak [τis(t)]α [ηis(t)]β , j ∈ ak 0, 其他 (6) ϕ= ∑ s∈ak [γis(t)]ε σε (7) µ = ∑ s∈ak [γis(t)]ω λ ω (8) ·332· 智 能 系 统 学 报 第 16 卷
第2期 徐玉琼，等：基于变步长蚁群算法的移动机器人路径规划 ·333· 式中：k为常数，保证概率范围为(0,1)；ε为终点 免蚂蚁集中在某条路径上，将每条路径的信息素 诱导系数；ω为障碍物诱导系数；y:为移动机器 设置上下限为[tma,tm],当该条路径信息素浓度 人当前节点到下一步可到达所有节点的距离总 低于信息素下限时，将该条路径信息素设置为 和，σ为移动机器人下一步到达的节点与终点之 t,当该条路径信息素浓度高于信息素上限时， 间的距离，其值越小，则距离终点越近，被选择的 该条路径信息素设置为T,这样可以避免算法 概率也将越大，入为移动机器人下一步到达的节 陷人局部最优解，当蚁群经过一轮迭代后，挑选 点与其最近的障碍物之间的距离，优先考虑障碍 出最优路径，对其信息素进行更新，加强对最优 物相邻的节点，可以有效缩短无效路径，提高移 路径的利用，当所有蚂蚁完成一次迭代后，对路 动机器人避障能力。 径上的信息素进行全局更新： 2.2信息素分布策略 tt+l)=(1-pT0+△()，pe(0,1) (11) 在移动机器人路径规划之前，需要给栅格地 边亿，)包含在最优路径内 图环境的信息素进行初始化，初始化信息素采用 △= (12) 不均匀分布，障碍物栅格的信息素设置为0，加强 0,其他 起点至终点直线所涉及到栅格的信息素浓度，平 为了提高搜索效率，一只蚂蚁在一轮迭代中 行的向外衰减，将栅格地图建立直角坐标系，如 走过的完整路径将不被以后的蚂蚁所选择，对于 图4所示。 需要更新信息素的路径，可以是本轮迭代的最优 解，也可以是全局最优解。 2.3改进启发函数 结合变步长蚁群算法的优点，在直角坐标系 中，利用蚁群下一步到达的节点距离起点至终点 连线的长短，对启发函数进行改进，传统蚁群算 法的启发函数为蚁群下一步所选择的节点到终点 之间距离的倒数，如式(2)所示，该函数收敛性不 强，且容易使蚁群寻优路径冗长，改进后的启发 函数如下： 1V2 图4信息素分布策略 u=di+yCl (13) Fig.4 Pheromone distribution strategy 式中，(xy)为下一步所选择节点的坐标，当其距 连接移动机器人的起始点及终点，则该直线 离起点至终点对角线的长度越小，被选择概率则 方程为 越大，与传统蚁群算法的启发函数相比，改进后 y=-x+C,C∈N" (9) 的启发函数促使移动机器人将下一步选择的节点 在本文中，C取值为20或30，分别对应简单 趋近于移动机器人起点到终点连线处，使移动机 栅格环境和复杂栅格环境，令(O)=to为信息素 器人在路径寻优中能更快地找到最优解，提高了 浓度的初始值，根据初始信息素浓度的衰减方 算法的收敛速度，因此，改进后的启发函数作用 式，障碍物栅格的初始信息素τ。直接取0，非障碍 得到加强，有利于提高算法的收敛速度，提高算 物栅格初始信息素取值如下： 法的全局搜索能力。 T,y=-x+C C-1 3改进算法步骤 .T,y=-x+C±1 图5为变步长蚁群算法的流程图，算法的具 T0= C-2 .T,y=-x+C±2 (10) 体步骤如下： … 1)针对各项相关参数进行初始化：路径规划 1 的起始点及终点、信息素重要程度参数α、启发 ,，y=-x+1或y=-x+2C-1 因子重要程度参数B、迭代次数、蚂蚁数量、信息 式中：T为调整系数，T∈(1,20)，初试信息素的分 素挥发系数及增强系数等相关参数，建立地图二 布有利于蚁群提高搜索速度，快速收敛。 维栅格模型，邻接矩阵模型。 为了防止某条路径的信息素过高或过低，避 2)初始化信息素采用不均匀分布，加强起点
k ε ω γis σ λ 式中： 为常数，保证概率范围为 (0,1)； 为终点 诱导系数； 为障碍物诱导系数； 为移动机器 人当前节点到下一步可到达所有节点的距离总 和， 为移动机器人下一步到达的节点与终点之 间的距离，其值越小，则距离终点越近，被选择的 概率也将越大， 为移动机器人下一步到达的节 点与其最近的障碍物之间的距离，优先考虑障碍 物相邻的节点，可以有效缩短无效路径，提高移 动机器人避障能力。 2.2 信息素分布策略 在移动机器人路径规划之前，需要给栅格地 图环境的信息素进行初始化，初始化信息素采用 不均匀分布，障碍物栅格的信息素设置为 0，加强 起点至终点直线所涉及到栅格的信息素浓度，平 行的向外衰减，将栅格地图建立直角坐标系，如 图 4 所示。 x y 0 图 4 信息素分布策略 Fig. 4 Pheromone distribution strategy 连接移动机器人的起始点及终点，则该直线 方程为 y = −x+C, C ∈ N ∗ (9) τi j(0) = τ0 τ0 在本文中，C 取值为 20 或 30，分别对应简单 栅格环境和复杂栅格环境，令 为信息素 浓度的初始值，根据初始信息素浓度的衰减方 式，障碍物栅格的初始信息素 直接取 0，非障碍 物栅格初始信息素取值如下： τ0 = T, y = −x+C C −1 C ·T, y = −x+C ±1 C −2 C ·T, y = −x+C ±2 ··· 1 C ·T, y = −x+1或y = −x+2C −1 (10) 式中： T 为调整系数， T ∈ (1,20) ，初试信息素的分 布有利于蚁群提高搜索速度，快速收敛。 为了防止某条路径的信息素过高或过低，避 [τmin,τmax] τmin τmax 免蚂蚁集中在某条路径上，将每条路径的信息素 设置上下限为 ，当该条路径信息素浓度 低于信息素下限时，将该条路径信息素设置为 ，当该条路径信息素浓度高于信息素上限时， 该条路径信息素设置为 ，这样可以避免算法 陷入局部最优解，当蚁群经过一轮迭代后，挑选 出最优路径，对其信息素进行更新，加强对最优 路径的利用，当所有蚂蚁完成一次迭代后，对路 径上的信息素进行全局更新： τi j(t+1) = (1−ρ)· τi j(t)+ ∆τ best i j (t), ρ ∈ (0,1) (11) ∆τ best i j = 1 L best , 边(i, j)包含在最优路径内 0, 其他 (12) 为了提高搜索效率，一只蚂蚁在一轮迭代中 走过的完整路径将不被以后的蚂蚁所选择，对于 需要更新信息素的路径，可以是本轮迭代的最优 解，也可以是全局最优解。 2.3 改进启发函数 结合变步长蚁群算法的优点，在直角坐标系 中，利用蚁群下一步到达的节点距离起点至终点 连线的长短，对启发函数进行改进，传统蚁群算 法的启发函数为蚁群下一步所选择的节点到终点 之间距离的倒数，如式 (2) 所示，该函数收敛性不 强，且容易使蚁群寻优路径冗长，改进后的启发 函数如下： ηi j = 1 di j · √ 2 |xi +yj −C| (13) (xi 式中， , yj) 为下一步所选择节点的坐标，当其距 离起点至终点对角线的长度越小，被选择概率则 越大，与传统蚁群算法的启发函数相比，改进后 的启发函数促使移动机器人将下一步选择的节点 趋近于移动机器人起点到终点连线处，使移动机 器人在路径寻优中能更快地找到最优解，提高了 算法的收敛速度，因此，改进后的启发函数作用 得到加强，有利于提高算法的收敛速度，提高算 法的全局搜索能力。 3 改进算法步骤 图 5 为变步长蚁群算法的流程图，算法的具 体步骤如下： α β 1) 针对各项相关参数进行初始化：路径规划 的起始点及终点、信息素重要程度参数 、启发 因子重要程度参数 、迭代次数、蚂蚁数量、信息 素挥发系数及增强系数等相关参数，建立地图二 维栅格模型，邻接矩阵模型。 2) 初始化信息素采用不均匀分布，加强起点 第 2 期 徐玉琼，等：基于变步长蚁群算法的移动机器人路径规划 ·333·
·334· 智能系统学报 第16卷 至终点直线所涉及栅格的信息素浓度，平行的向 环境为20×20的栅格环境，对传统蚁群算法、本 外衰减：改进启发式信息矩阵，调整移动机器人 文算法进行仿真，与文献[8]进行对比，复杂环境 当前位置到终点位置的启发函数计算方法，建立 为30×30的栅格环境，对本文算法进行仿真，与 启发式信息矩阵。 文献[8]进行对比。 3)建立禁忌表以及对禁忌表初始化，将起点、 4.120×20栅格环境 障碍物节点、引起死锁的节点均加入禁忌表中。 在20×20的栅格环境下，对传统蚁群算法和 4)计算启发信息，根据信息素浓度以及概率 本文算法进行仿真，其中，路径规划仿真分别如 公式确定蚂蚁下一步可以到达的节点，记录路径 图6、7所示，实验数据如表1所示，传统蚁群算 并更新，更新禁忌表。 法路径规划长度为30.870m,文献[8]算法路径规 5)当所有蚂蚁完成一次迭代后，保存最优路 划长度为32.1421m,本文算法路径规划长度为 径，更新信息素及禁忌表，如果没有完成一次迭 28.042m,显然，本文算法在路径规划方面优于文 代，则继续开始下一只蚂蚁路径寻优。 献[8]算法及传统蚁群算法，本文算法较文献[8] 6)如果蚂蚁完成所有迭代次数，则输出最优 算法、传统蚁群算法的路径长度分别缩短了12.76% 路径及收敛迭代次数，如果没有完成所有迭代次 及9.16%。本文算法提出信息素不均匀分布策 数，则继续开始下一次迭代。 略，提高了最优路径上节点被选择的概率，通过 节点距离起点至终点对角线的距离，改进启发函 开始 数，提高了算法的全局搜索能力，有效缩短了全 局最优路径的长度。 各项参数初始化，建立地图模型及 邻接矩阵 20 18 16 信息素浓度不均匀分布，建立启发 14 式信息矩阵 12 10 建立禁忌表 确定蚂蚁下一步可前往的节点 0 2468101214161820单位：m 图6传统蚊群算法路径规划(20×20) 记录路径并更新，更新禁忌表 Fig.6 Path planning of traditional ant colony algorithm 20 一轮迭代是否结束 N 18 16 Y 12 保存最优路径，更新信息素，更新禁忌表 10 N 是否完成所有迭代 2 Y 0 2468101214161820单位：m 输出全局最优路径，收敛迭代次数 图7本文算法路径规划(20×20) Fig.7 Algorithm path planning in this paper 结束 表1各算法实验结果对比 Table 1 Comparison of experimental results of various al- 图5变步长蚁群算法流程 gorithms Fig.5 Flow chart of variable step size ant colony algorithm 算法 路径长度m 迭代次数 4算法仿真 传统蚁群算法 30.870 25 文献I8算法 32.1421 4 为了验证变步长蚁群算法的有效性，本文分 别在简易环境和复杂环境下进行仿真对比，简易 本文算法 28.042 2
至终点直线所涉及栅格的信息素浓度，平行的向 外衰减；改进启发式信息矩阵，调整移动机器人 当前位置到终点位置的启发函数计算方法，建立 启发式信息矩阵。 3) 建立禁忌表以及对禁忌表初始化，将起点、 障碍物节点、引起死锁的节点均加入禁忌表中。 4) 计算启发信息，根据信息素浓度以及概率 公式确定蚂蚁下一步可以到达的节点，记录路径 并更新，更新禁忌表。 5) 当所有蚂蚁完成一次迭代后，保存最优路 径，更新信息素及禁忌表，如果没有完成一次迭 代，则继续开始下一只蚂蚁路径寻优。 6) 如果蚂蚁完成所有迭代次数，则输出最优 路径及收敛迭代次数，如果没有完成所有迭代次 数，则继续开始下一次迭代。 开始 各项参数初始化，建立地图模型及 邻接矩阵 信息素浓度不均匀分布，建立启发 式信息矩阵 建立禁忌表 确定蚂蚁下一步可前往的节点 记录路径并更新，更新禁忌表 N N Y Y 一轮迭代是否结束 保存最优路径，更新信息素，更新禁忌表 是否完成所有迭代 输出全局最优路径，收敛迭代次数 结束 图 5 变步长蚁群算法流程 Fig. 5 Flow chart of variable step size ant colony algorithm 4 算法仿真 为了验证变步长蚁群算法的有效性，本文分 别在简易环境和复杂环境下进行仿真对比，简易 20×20 30×30 环境为 的栅格环境，对传统蚁群算法、本 文算法进行仿真，与文献 [8] 进行对比，复杂环境 为 的栅格环境，对本文算法进行仿真，与 文献 [8] 进行对比。 4.1 20×20 栅格环境 在 20×20 的栅格环境下，对传统蚁群算法和 本文算法进行仿真，其中，路径规划仿真分别如 图 6、7 所示，实验数据如表 1 所示，传统蚁群算 法路径规划长度为 30.870 m，文献 [8] 算法路径规 划长度为 32.142 1 m，本文算法路径规划长度为 28.042 m，显然，本文算法在路径规划方面优于文 献 [8] 算法及传统蚁群算法，本文算法较文献 [8] 算法、传统蚁群算法的路径长度分别缩短了 12.76% 及 9.16%。本文算法提出信息素不均匀分布策 略，提高了最优路径上节点被选择的概率，通过 节点距离起点至终点对角线的距离，改进启发函 数，提高了算法的全局搜索能力，有效缩短了全 局最优路径的长度。 20 18 16 14 12 10 8 6 4 2 0 2 4 6 8 10 12 14 16 18 20 单位: m 图 6 传统蚁群算法路径规划 (20×20) Fig. 6 Path planning of traditional ant colony algorithm 20 18 16 14 12 10 8 6 4 2 0 2 4 6 8 10 12 14 16 18 20 单位: m 图 7 本文算法路径规划 (20×20) Fig. 7 Algorithm path planning in this paper 表 1 各算法实验结果对比 Table 1 Comparison of experimental results of various algorithms 算法 路径长度/m 迭代次数 传统蚁群算法 30.870 25 文献[8]算法 32.1421 4 本文算法 28.042 2 ·334· 智 能 系 统 学 报 第 16 卷
第2期 徐玉琼，等：基于变步长蚁群算法的移动机器人路径规划 ·335· 收敛迭代仿真分别如图8、9所示，传统蚁群 4.230×30栅格环境 算法收敛迭代次数为25次，文献[8]算法收敛迭 在30×30栅格环境下，采用文献[8]中的同 代次数为4次，本文算法收敛迭代次数为2次， 一个栅格地图，对本文算法进行仿真实验，实验 显然，本文算法在收敛速度方面优于文献[8]算 数据如表2所示，本文算法的路径规划如图11所 法及传统蚁群算法，本文算法较文献[8]算法、 示，本文算法的最佳路径长度为41.961m,文献[8] 传统蚁群算法的收敛迭代次数分别减少了 的最佳路径长度为45.1127m,本文算法较文献[8] 50%及92%。图10为本文算法在该环境下各代 关于最佳路径长度缩短了6.99%，因此，在复杂栅 蚂蚁最优路径规划路线，各代路线集中于起点 格环境下，本文算法依然保持良好的路径规划能 至终点的连线处，表明信息素不均匀分布的有 力，通过变步长蚁群算法，有效地缩短了最优路 效作用，在20×20栅格环境中，本文算法无论是 径长度，收敛迭代效率如图12所示，本文算法的 在最优路径上还是在收敛速度上，都优于其他 收敛迭代次数为6次，文献[8]算法的收敛迭代次 两种算法。 数为8次，本文算法较文献[8]算法关于收敛迭代 70 次数减少了25%，栅格地图越复杂，本文算法的 优越性越明显，各代最优路径规划路线如图13 所示，各代路径规划的路线依然集中于起点至终 点的连线处，移动机器人将快速的寻找出最优 路径。 表2两种算法实验结果对比 10 Table 2 Comparison of experimental results of various al- 5 101520253035404550 gorithms 迭代次数 算法 路径长度m 迭代次数 转弯次数 图8传统蚊群算法收敛曲线 文献[8]算法 45.1127 8 24 Fig.8 Convergence curve of traditional ant colony al- gorithm 本文算法 41.961 6 7 30 25 25 20 20 10 10 5 5101520253035404550 10 20 30 迭代次数 15 单位：m 图9本文算法收敛曲线 图11本文算法路径规划(30×30) Fig.9 Convergence curve of the algorithm presented in Fig.11 Algorithm path planning in this paper(30x30) this paper 45 20 0 复 6 30 14 12 25 6 10 5 2 05101520253035404550 0 2468101214161820单位：m 选代次数 图10本文算法各代蚊群最优路径规划(20×20) 图12本文算法收敛曲线(30×30) Fig.10 Optimal path planning of each generation of ant Fig.12 Convergence curve of the algorithm presented in colony in this algorithm (20x20) this paper(30x30)
20×20 收敛迭代仿真分别如图 8、9 所示，传统蚁群 算法收敛迭代次数为 25 次，文献 [8] 算法收敛迭 代次数为 4 次，本文算法收敛迭代次数为 2 次 ， 显然，本文算法在收敛速度方面优于文献 [8] 算 法及传统蚁群算法，本文算法较文献 [8] 算法、 传统蚁群算法的收敛迭代次数分别减少 了 50% 及 92%。图 10 为本文算法在该环境下各代 蚂蚁最优路径规划路线，各代路线集中于起点 至终点的连线处，表明信息素不均匀分布的有 效作用，在 栅格环境中，本文算法无论是 在最优路径上还是在收敛速度上，都优于其他 两种算法。 70 60 50 40 30 最优解路径长度/m 20 10 0 5 10 15 20 25 迭代次数 30 35 40 45 50 图 8 传统蚁群算法收敛曲线 Fig. 8 Convergence curve of traditional ant colony algorithm 30 25 20 15 最优解路径长度/m 10 5 0 5 10 15 20 25 迭代次数 30 35 40 45 50 图 9 本文算法收敛曲线 Fig. 9 Convergence curve of the algorithm presented in this paper 20 18 16 14 12 10 8 6 4 2 0 2 4 6 8 10 12 14 16 18 20 单位: m 图 10 本文算法各代蚁群最优路径规划 (20×20) Fig. 10 Optimal path planning of each generation of ant colony in this algorithm (20×20) 4.2 30×30 栅格环境 在 30×30 栅格环境下，采用文献 [8] 中的同 一个栅格地图，对本文算法进行仿真实验，实验 数据如表 2 所示，本文算法的路径规划如图 11 所 示，本文算法的最佳路径长度为 41.961 m，文献 [8] 的最佳路径长度为 45.1127 m，本文算法较文献 [8] 关于最佳路径长度缩短了 6.99%，因此，在复杂栅 格环境下，本文算法依然保持良好的路径规划能 力，通过变步长蚁群算法，有效地缩短了最优路 径长度，收敛迭代效率如图 12 所示，本文算法的 收敛迭代次数为 6 次，文献 [8] 算法的收敛迭代次 数为 8 次，本文算法较文献 [8] 算法关于收敛迭代 次数减少了 25%，栅格地图越复杂，本文算法的 优越性越明显，各代最优路径规划路线如图 13 所示，各代路径规划的路线依然集中于起点至终 点的连线处，移动机器人将快速的寻找出最优 路径。 表 2 两种算法实验结果对比 Table 2 Comparison of experimental results of various algorithms 算法 路径长度/m 迭代次数 转弯次数 文献[8]算法 45.1127 8 24 本文算法 41.961 6 7 30 25 20 15 10 5 0 5 10 15 20 25 30 单位: m 图 11 本文算法路径规划 (30×30) Fig. 11 Algorithm path planning in this paper (30×30) 45 40 35 30 最优解路径长度/m 25 20 15 10 5 0 5 10 15 20 25 迭代次数 30 35 40 45 50 图 12 本文算法收敛曲线 (30×30) Fig. 12 Convergence curve of the algorithm presented in this paper (30×30) 第 2 期 徐玉琼，等：基于变步长蚁群算法的移动机器人路径规划 ·335·
·336· 智能系统学报 第16卷 30 表3各算法路径规划实验数据 25 Table 3 Experimental data of path planning for each al- gorithm 20 算法 路径长度/m 耗时s 0 传统蚁群算法 5.13 19.67 本文算法 3.26 13.56 101520 25 30单位：m 5结束语 图13本文算法各代蚊群最优路径规划(30×30) Fig.13 Optimal path planning of each generation of ant 传统蚁群算法在移动机器人路径规划中存在 colony in this algorithm (30x30) 搜索效率低、路径过长、收敛较慢等问题，本文在 4.3实验研究 传统蚁群算法的基础上引入了变步长策略对其进 本文采用自主搭建的移动机器人进行实验 行改进，扩充蚁群可以到达节点的集合，在不触 验证，如图14及图15所示，一个纸箱代表两个 碰障碍物的条件下，从蚁群当前位置的相邻位置 正方形障碍物栅格，空白场地为自由栅格，实验 扩大至全局地图的任意自由栅格位置，达到变步 场景为20×20的栅格环境，实验数据如表3所 长策略，改进信息素分布策略以及调整启发函数 示，本文算法路径规划最优长度为3.26m,移动 计算方法，大幅提高本文算法的收敛速度，快速 机器人从起点至终点耗时13.56s,传统蚁群算法 地寻找到最优路径。本文基于变步长蚁群算法在 路径规划最优长度为5.13m,耗时19.67s,验证 收敛速度和路径寻优方面有着较好的性能，不仅 了本文算法在移动机器人实际应用中能够较快 适用于简单栅格环境，也适用于复杂的栅格环 地找到最优路径，有效地提高了路径规划的工 境，使本文算法在实际应用场景中得到较好的应 作效率。 用，通过对整个地图状态空间的探索点进行采 样，能够增加搜索区域，适合解决移动机器人在 复杂环境下的路径规划。 参考文献： [1]CONFESSORE G.FABIANO M.LIOTTA G.A network flow based heuristic approach for optimising AGV move- ments[J].Journal of intelligent manufacturing,2013,24(2): 405-419. [2]张毅，权浩，文家富.基于独狼蚁群混合算法的移动机器 人路径规划[).华中科技大学学报（自然科学版），2020， 48(1:127-132, 图14移动机器人起点位置 ZHANG Yi,QUAN Hai,WEN Jiafu.Mobile robot path Fig.14 Starting position of mobile robot planning based on the wolf ant colony hybrid algorithm[J]. Journal of Huazhong University of Science and Techno- logy (Nature Science Edition),2020,48(1):127-132. [3]刘可，李可，宿磊，等.基于蚁群算法与参数迁移的机器 人三维路径规划方法[J刀.农业机械学报，2020,51(1)： 29-36. LIU Ke,LI Ke,SU Lei,et al.Robot 3D path planning method based on ant colony algorithm and parameter trans- fer[J].Transactions of the Chinese society for agricultural machinery,2020,51(1):29-36. [4]ZHOU Zhiping,NIE Yunfeng,GAO Min.Enhanced ant colony optimization algorithm for global path planning of mobile robots[C]//Proceedings of 2013 International Con- 图15移动机器人运行过程 ference on Computational and Information Sciences.Shiy- Fig.15 Mobile robot running process ang,China,.2013:698-701
30 25 20 15 10 5 0 5 10 15 20 25 30 单位: m 图 13 本文算法各代蚁群最优路径规划 (30×30) Fig. 13 Optimal path planning of each generation of ant colony in this algorithm (30×30) 4.3 实验研究 20×20 本文采用自主搭建的移动机器人进行实验 验证，如图 14 及图 15 所示，一个纸箱代表两个 正方形障碍物栅格，空白场地为自由栅格，实验 场景为 的栅格环境，实验数据如表 3 所 示，本文算法路径规划最优长度为 3.26 m，移动 机器人从起点至终点耗时 13.56 s，传统蚁群算法 路径规划最优长度为 5.13 m，耗时 19.67 s，验证 了本文算法在移动机器人实际应用中能够较快 地找到最优路径，有效地提高了路径规划的工 作效率。 图 14 移动机器人起点位置 Fig. 14 Starting position of mobile robot 图 15 移动机器人运行过程 Fig. 15 Mobile robot running process 表 3 各算法路径规划实验数据 Table 3 Experimental data of path planning for each algorithm 算法 路径长度/m 耗时/s 传统蚁群算法 5.13 19.67 本文算法 3.26 13.56 5 结束语 传统蚁群算法在移动机器人路径规划中存在 搜索效率低、路径过长、收敛较慢等问题，本文在 传统蚁群算法的基础上引入了变步长策略对其进 行改进，扩充蚁群可以到达节点的集合，在不触 碰障碍物的条件下，从蚁群当前位置的相邻位置 扩大至全局地图的任意自由栅格位置，达到变步 长策略，改进信息素分布策略以及调整启发函数 计算方法，大幅提高本文算法的收敛速度，快速 地寻找到最优路径。本文基于变步长蚁群算法在 收敛速度和路径寻优方面有着较好的性能，不仅 适用于简单栅格环境，也适用于复杂的栅格环 境，使本文算法在实际应用场景中得到较好的应 用，通过对整个地图状态空间的探索点进行采 样，能够增加搜索区域，适合解决移动机器人在 复杂环境下的路径规划。 参考文献： CONFESSORE G, FABIANO M, LIOTTA G. A network flow based heuristic approach for optimising AGV movements[J]. Journal of intelligent manufacturing, 2013, 24(2): 405–419. [1] 张毅, 权浩, 文家富. 基于独狼蚁群混合算法的移动机器 人路径规划 [J]. 华中科技大学学报(自然科学版), 2020, 48(1): 127–132. ZHANG Yi, QUAN Hai, WEN Jiafu. Mobile robot path planning based on the wolf ant colony hybrid algorithm[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition), 2020, 48(1): 127–132. [2] 刘可, 李可, 宿磊, 等. 基于蚁群算法与参数迁移的机器 人三维路径规划方法 [J]. 农业机械学报, 2020, 51(1): 29–36. LIU Ke, LI Ke, SU Lei, et al. Robot 3D path planning method based on ant colony algorithm and parameter transfer[J]. Transactions of the Chinese society for agricultural machinery, 2020, 51(1): 29–36. [3] ZHOU Zhiping, NIE Yunfeng, GAO Min. Enhanced ant colony optimization algorithm for global path planning of mobile robots[C]//Proceedings of 2013 International Conference on Computational and Information Sciences. Shiyang, China, 2013: 698−701. [4] ·336· 智 能 系 统 学 报 第 16 卷
第2期 徐玉琼，等：基于变步长蚁群算法的移动机器人路径规划 ·337· [5]HE Qiang,HU Xiangtao,REN Hong,et al.A novel artifi- improved ant colony algorithm[J].Journal of computer cial fish swarm algorithm for solving large-scale reliabil- and communications,2016,4(2):11-19. ity-redundancy application problem[].ISA transactions, [16]徐玉琼，娄柯，李婷婷，等.改进自适应蚁群算法的移动 2015,59:105-113. 机器人路径规划[】.电子测量与仪器学报，2019， [6]WU Tao,JING Xiaojun.Exploration of multiple access in- 33(10):89-95 terference suppression based on multi-user detection[J]. XU Yugiong.LOU Ke,LI Tingting,et al.Path planning Chinese journal of electronics,2019,28(4):835-840. of mobile robot based on improved adaptive ant colony [7]陈军章.改进人工鱼群算法的机器人路径规划及跟踪 algorithm[J].Journal of electronic measurement and in- [).机械设计与制造，201904)：251-255. strumentation,2019,33(10):89-95. CHEN Junzhang.Mobile Robot Path Planning and Track- [17]AJEIL F H,IBRAHEEM I K,AZAR A T,et al.Grid- ing Based on Improved Artificial Fish Swarm based mobile robot path planning using aging-based ant Algorithm[J].Machinery Design Manufacture, colony optimization algorithm in static and dynamic en- 2019(04):251-255. vironments[J1.Sensors,2020,20(7):1880. [8]许凯波，鲁海燕，黄洋，等.基于双层蚁群算法和动态环 [18]杨俊成，李淑霞，蔡增玉.路径规划算法的研究与发 境的机器人路径规划方法[J】.电子学报，2019,47(10)： 展).控制工程，2017,247)：1473-1480. 2166-2176 YANG Juncheng,LI Shuxia,CAI Zengyu.Research and XU Kaibo,LU Haiyan,HUANG Yang,et al.Robot path development of path planning algorithm[J].Control en- planning based on double-layer ant colony optimization al- gineering of China,2017,24(7):1473-1480. gorithm and dynamic environment[J].Acta electronica sin- [19]王培良，张婷，肖英杰.蚁群元胞优化算法在人群疏散 ica,2019,47(10):2166-2176 路径规划中的应用U.物理学报，2020,69(8)：234242 [9]朱艳，游晓明，刘升.基于启发式机制的改进蚁群算 WANG Peiliang,ZHANG Ting,XIAO Yingjie.Applica- 法.信息与控制，2019,48(3265-271 tion research of ant colony cellular optimization al- ZHU Yan,YOU Xiaoming,LIU Sheng.Improved ant gorithm in population evacuation path planning[J].Acta physica sinica,2020,69(8):234-242. colony algorithm based on heuristic mechanism[J.Inform- [20]万方，周风余，尹磊，等.基于电势场法的移动机器人全 ation and control,2019,48(3):265-271. [10]LIU Jianhua,YANG Jianguo,LIU Huaping,et al.An im- 局路径规划算法).机器人，2019,41(6：742-750. WAN Fang,ZHOU Fengyu,YIN Lei,et al.Global path proved ant colony algorithm for robot path planning[J. Soft computing,2017,21(19):5829-5839. planning algorithm of mobile robot based on electric po- [11]HWU T,WANG A Y,OROS N,et al.Adaptive robot tential field[J].Robot,2019,41(6):742-750. path planning using a spiking neuron algorithm with ax- 作者简介： onal delays[J].IEEE transactions on cognitive and devel- 徐玉琼，硕土研究生，主要研究方 opmental systems,2018,10(2):126-137. 向为移动机器人路径规划技术、图像 [12]封声飞，雷琦，吴文烈等.自适应蚁群算法的移动机器 处理。 人路径规划J].计算机工程与应用，2019,55(17)： 35-43. FENG Shengfei,LEI Qi,WU Wenlie,et al.Mobile robot path planning based on adaptive ant colony algorithm[J]. Computer Engineering and Applications,2019,55(17): 娄柯，副教授，博士，主要研究方 35-43 向为多智能体协同控制、嵌入式系统 [13]黄琰，李岩，俞建成，等.AUV智能化现状与发展趋 及应用。主持及参与国家、省部级科 势).机器人，2020,42(2：215-231. 学基金项目10余项。发表学术论文 HUANG Yan,LI Yan,YU Jiancheng,et al.State-of-the- 20余篇。 art and development trends of AUV intelligence[J].Ro- bot2020,42(2):215-231. [14]江明，王飞，葛愿，等.基于改进蚁群算法的移动机器人 李志锟，硕士研究生，主要研究方 路径规划研究).仪器仪表学报，2019,40(2)：113-121 向为移动机器人路径规划技术、移动 JIANG Ming,WANG Fei,GE Yuan,et al.Research on 机器人地图构建技术、智能算法。 path planning of mobile robot based on improved ant colony algorithm[J].Chinese journal of scientific instru- ment,2019,40(2):113-121 [15]CAO Jingang.Robot global path planning based on an
HE Qiang, HU Xiangtao, REN Hong, et al. A novel artificial fish swarm algorithm for solving large-scale reliability-redundancy application problem[J]. ISA transactions, 2015, 59: 105–113. [5] WU Tao, JING Xiaojun. Exploration of multiple access interference suppression based on multi-user detection[J]. Chinese journal of electronics, 2019, 28(4): 835–840. [6] 陈军章. 改进人工鱼群算法的机器人路径规划及跟踪 [J]. 机械设计与制造, 2019(04): 251–255. CHEN Junzhang. Mobile Robot Path Planning and Tracking Based on Improved Artificial Fish Swarm Algorithm[J]. Machinery Design & Manufacture, 2019(04): 251–255. [7] 许凯波, 鲁海燕, 黄洋, 等. 基于双层蚁群算法和动态环 境的机器人路径规划方法 [J]. 电子学报, 2019, 47(10): 2166–2176. XU Kaibo, LU Haiyan, HUANG Yang, et al. Robot path planning based on double-layer ant colony optimization algorithm and dynamic environment[J]. Acta electronica sinica, 2019, 47(10): 2166–2176. [8] 朱艳, 游晓明, 刘升. 基于启发式机制的改进蚁群算 法 [J]. 信息与控制, 2019, 48(3): 265–271. ZHU Yan, YOU Xiaoming, LIU Sheng. Improved ant colony algorithm based on heuristic mechanism[J]. Information and control, 2019, 48(3): 265–271. [9] LIU Jianhua, YANG Jianguo, LIU Huaping, et al. An improved ant colony algorithm for robot path planning[J]. Soft computing, 2017, 21(19): 5829–5839. [10] HWU T, WANG A Y, OROS N, et al. Adaptive robot path planning using a spiking neuron algorithm with axonal delays[J]. IEEE transactions on cognitive and developmental systems, 2018, 10(2): 126–137. [11] 封声飞, 雷琦, 吴文烈, 等. 自适应蚁群算法的移动机器 人路径规划 [J]. 计算机工程与应用, 2019, 55(17): 35–43. FENG Shengfei, LEI Qi, WU Wenlie, et al. Mobile robot path planning based on adaptive ant colony algorithm[J]. Computer Engineering and Applications, 2019, 55(17): 35–43. [12] 黄琰, 李岩, 俞建成, 等. AUV 智能化现状与发展趋 势 [J]. 机器人, 2020, 42(2): 215–231. HUANG Yan, LI Yan, YU Jiancheng, et al. State-of-theart and development trends of AUV intelligence[J]. Robot, 2020, 42(2): 215–231. [13] 江明, 王飞, 葛愿, 等. 基于改进蚁群算法的移动机器人 路径规划研究 [J]. 仪器仪表学报, 2019, 40(2): 113–121. JIANG Ming, WANG Fei, GE Yuan, et al. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Chinese journal of scientific instrument, 2019, 40(2): 113–121. [14] [15] CAO Jingang. Robot global path planning based on an improved ant colony algorithm[J]. Journal of computer and communications, 2016, 4(2): 11–19. 徐玉琼, 娄柯, 李婷婷, 等. 改进自适应蚁群算法的移动 机器人路径规划 [J]. 电子测量与仪器学报, 2019, 33(10): 89–95. XU Yuqiong, LOU Ke, LI Tingting, et al. Path planning of mobile robot based on improved adaptive ant colony algorithm[J]. Journal of electronic measurement and instrumentation, 2019, 33(10): 89–95. [16] AJEIL F H, IBRAHEEM I K, AZAR A T, et al. Gridbased mobile robot path planning using aging-based ant colony optimization algorithm in static and dynamic environments[J]. Sensors, 2020, 20(7): 1880. [17] 杨俊成, 李淑霞, 蔡增玉. 路径规划算法的研究与发 展 [J]. 控制工程, 2017, 24(7): 1473–1480. YANG Juncheng, LI Shuxia, CAI Zengyu. Research and development of path planning algorithm[J]. Control engineering of China, 2017, 24(7): 1473–1480. [18] 王培良, 张婷, 肖英杰. 蚁群元胞优化算法在人群疏散 路径规划中的应用 [J]. 物理学报, 2020, 69(8): 234–242. WANG Peiliang, ZHANG Ting, XIAO Yingjie. Application research of ant colony cellular optimization algorithm in population evacuation path planning[J]. Acta physica sinica, 2020, 69(8): 234–242. [19] 万方, 周风余, 尹磊, 等. 基于电势场法的移动机器人全 局路径规划算法 [J]. 机器人, 2019, 41(6): 742–750. WAN Fang, ZHOU Fengyu, YIN Lei, et al. Global path planning algorithm of mobile robot based on electric potential field[J]. Robot, 2019, 41(6): 742–750. [20] 作者简介： 徐玉琼，硕士研究生，主要研究方 向为移动机器人路径规划技术、图像 处理。 娄柯，副教授，博士，主要研究方 向为多智能体协同控制、嵌入式系统 及应用。主持及参与国家、省部级科 学基金项目 10 余项。发表学术论文 20 余篇。 李志锟，硕士研究生，主要研究方 向为移动机器人路径规划技术、移动 机器人地图构建技术、智能算法。 第 2 期 徐玉琼，等：基于变步长蚁群算法的移动机器人路径规划 ·337·