基于模拟退火蚁群算法的机器人路径规划

王正存 张晓玲 吴作君

摘 要：针对蚁群算法在机器人路径规划中易陷入局部最优问题，提出首先利用蚁群算法寻找移动路径，然后采用模拟退火算法进行迭代，并加入回火机制消除局部最优，有效提高蚁群算法的全局搜索能力。仿真研究表明，模拟退火蚁群算法在机器人路径搜索上可得到较短路径。

关键词：蚁群算法；模拟退火；路径规划

机器人路径规划问题中，路径规划算法是核心，蚁群算法具有较强的优化能力和鲁棒性，成为近年来的研究热点。[1] [2]但当寻优过程中问题规模变大时，存在收敛精度变低和易落入局部最优问题。本文采用改进的蚁群算法在搜索路径过程中，使用模拟退火算法迭代，寻找栅格地图中的可行性路径。

1 环境建模

首先建立机器人路径规划的工作地图，鉴于栅格法的方便实现、高精度优点，选用栅格法建立机器人运行的模拟环境。[3]环境建模后，需要对栅格地图进行路径规划寻找较短路径，其中路径的移动和计算过程如下描述。假设t时刻机器人在栅格地图上移动一步长度d：

d=2，xt+1=xt±1且yt+1=yt±11，xt+1=xt±1或yt+1=yt±1（1）

机器人从起点到终点所走路径总长度等于每次移动长度之和。

2 基于模拟退火蚁群算法的路径规划

本文将模拟退火与蚁群算法结合，旨在解决蚁

群算法在寻优过程中不能得到全局最优解的问题，其迭代步骤如下：

S1：建立栅格地图，将机器人看做一只蚂蚁。

S2：初始化参数，包括蚂蚁数量num、迭代次数m、模拟退火算法的冷却系数q，初始温度T0，最大回火次数Hmax等。

S3：初始化信息素和设置启发值，即预先初始化各边信息素强度以及各蚂蚁的禁忌表。

S4：利用蚂蚁搜索路径，每一步移动方向由不同路径上的信息浓度决定，并计算转移概率（公式参考文献[4]）。重复该过程直到到达目的地或者找不到目的地退出。

S5：根据目标函数，计算寻优得到的路径长度，将其与原有路径比较，若短于原路径，则接受该路径，否则更新信息素（公式参考文献[4]）。

S6：比较当前温度T与前一时刻温度下的解（指用蚁群算法优化得到的解），若较前一时刻温度下的解好，便保留新解，否则计算温度T下接受劣解的概率[5]：

P=edEkT（2）

同时产生一个随机数X ，其取值范围为[0，1]，若X

S7：更新模拟退火温度，判断回火次数是否未达到或当前温度是否低于最小回火温度，成立则回火。

S8：检验模拟退火迭代次数是否满足条件，不满足则进入下一次循环迭代，满足则退出。

S9：输出最短路径。

3 仿真实验

首先在二维平面生成大小为20*20的随机栅格地图，采用序号对栅格编号，蓝色方块为环境中的障碍物；然后将传统蚁群算法和模拟退火蚁群算法分别应用到机器人路径规划中，仿真结果见图1、图2。

仿真结果对比可见，传统蚁群算法得到的路径长度196，模拟退火蚁群算法搜索到的最佳路径长度179，明显优于传统算法。

4 结语

本文在传统蚁群算法基础上加入带回火的模拟退火算法，解决机器人路径规划时容易陷入局部最优、不能得到真正的最短路径问题。通过MATLAB仿真研究发现，该模拟退火蚁群算法在路径搜索上具有更强的寻优能力。

参考文献：

[1]邱莉莉.基于改进蚁群算法的机器人路径规划[D].东华大学，2015.

[2][JP2]屈鸿，黄利伟，柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报， 2015， 2： 260265.

[3]朱磊，樊继壮，赵杰，吴晓光，刘罡.基于栅格法的矿难搜索机器人全局路径规划与局部避障[J].中南大学学报（自然科学版），2011，42（11）：34213428.

[4]何小虎.基于改进蚁群算法在粮食物流配送路径优化的应用研究[J].电子设计工程，2016，24（09）：3941.

[5]徐鹏.基于模拟退火算法的机器人路径规划与研究[J].科技广场， 2011， 1： 4244.

基金项目：中国石油大学胜利学院大学生创新创业训练计划项目资助（2017026）

作者简介：王正存（1994），男，山东济宁人，本科，中国石油大学胜利学院机械与控制工程学院自动化专业学生，主要从事机器人路径规划研究；张晓玲（1982），女，山东潍坊人，硕士，中国石油大学胜利学院讲师，主要从事自动化专业教学、机器人路径规划研究、工业过程故障診断方法研究等。