第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·