基于改进蚁群优化算法的养殖场机器人路径规划*

赵广元，赵 英

(1.西安邮电大学自动化学院,陕西 西安 710121;2.西安邮电大学西安市先进控制与智能处理重点实验室，陕西 西安 710121)

1 引言

随着科技的发展，养殖场逐渐向规模化、智能化发展。养殖场中智能巡视机器人正在逐渐替代人工，能够有效节约人力和物力资源，而且还能有效避免工作人员被病菌感染，更加方便养殖场的管理。智能巡视机器人在规模化养殖场巡视过程中存在电量不足的情况，需要寻找一条从起始点到充电点的最短无碰撞路径。路径的规划与选择是目前解决此问题的关键，较好的路径能够提高巡视效率，节约资源[1]。

现有的路径规划研究算法主要分为经典算法和启发式算法。近年来，学者们提出许多人工智能算法，代表性的启发算法有粒子群算法[2]、蚁群优化ACO(Ant Colony Optimization)算法[3]、遗传算法[4]、神经网络算法[5]和模拟退火算法[6]等。

蚁群优化ACO算法是一种启发式算法，由意大利学者Dorigo等[7]于1990年首次提出。传统的蚁群优化算法在路径优化方面存在一些缺陷，如路径传播方向不确定，收敛速度慢，容易出现停滞等。为避免上述缺陷，许多学者对传统的蚁群优化算法进行了改进。Yue等[8]通过改变蚁群优化算法初始信息素浓度和信息素更新规则解决了TSP(Traveling Salesman Problem)问题。Shen[9]将遗传算法加入到蚁群优化算法的每次迭代中,用于焊接机器人的路径规划研究。

法，为了找到在障碍物环境中的最佳无碰撞路径，本文提出一种改进的蚁群优化IACO(Improved ACO)算利用全局环境信息构建目标吸引函数，确定下一节点的转移概率，使得蚂蚁更加趋向于向最佳路径方向移动。通过加入额外的信息素更新项来提高算法的收敛速度，以及改进了信息素挥发系数以提高算法后期寻优能力。4个实验仿真表明，改进的蚁群优化算法可以在简单或者复杂的障碍物环境中找到无碰撞最佳路径。

2 用栅格法建立环境模型

移动机器人实际工作空间是三维的现实空间，环境地图建模的过程就是实现现实空间到抽象空间的映射过程，环境模型的构造采用了一种常用的网格映射方法。使用该方法，将机器人的工作环境映射到一个二维网格中，如图1所示。

Figure 1 Two-dimensional working environment model of robot图1 机器人二维工作环境模型

在栅格环境中，自由区域(由白色栅格表示)和障碍物区域(由黑色栅格表示)分别由二进制数字“0”和“1”代替。蚂蚁只能通过自由区域，不能进入障碍物区域。地图中栅格编号r与坐标(x,y)之间的转换关系如式(1)所示：

(1)

其中，mod(·)为求余运算,fix(·)为取整运算。

3 传统蚁群优化算法

蚁群优化算法是受蚂蚁觅食过程中互相交流的行为启发提出的。蚂蚁在一起寻找食物的主要过程描述如下：蚂蚁在觅食时，在行走的过程中释放出信息素标识自己的行走路径,信息素浓度与蚂蚁走过的路径长度成反比关系。随后，许多蚂蚁开始根据信息素和环境信息找到从洞穴到食物的途径。蚂蚁在选择路径时总是倾向于朝信息素浓度高的地方移动，越来越多的信息素被释放在较短的路径上，后续蚂蚁选择该路径的概率也会越大，其他路径上的信息素随着时间推移不断挥发，最后会将蚁群聚集到最短路径上。

(2)

(3)

在搜索的初期，蚁群进行无方向的搜索。当所有蚂蚁完成一次搜寻后，对路径上的信息素进行更新，更新公式如式(4)所示：

(4)

(5)

其中，Q为蚂蚁信息素强度，Lk为第k只蚂蚁在本次迭代中所走过的路径总长度。

4 改进蚁群优化IACO算法

4.1 改进状态转移概率

状态转移概率决定了蚂蚁下一步的移动方向，由启发函数和信息素浓度确定。传统蚁群优化算法的启发函数为当前节点到下一节点之间欧氏距离的倒数，在算法搜索前期，由于方向差异很小，缺乏原始的方向性启发式信息，导致算法的收敛速度慢[10]。为了提高经典蚁群优化算法的搜索性能，提高算法收敛速度，本文利用工作环境的全局信息建立目标吸引函数，确定向下一节点目标的转移概率，减少在算法前期搜索的盲目性，指导蚁群向最佳路径的方向移动。目标吸引函数如式(6)所示：

(6)

(7)

改进后的状态转移概率方程，通过引入目标吸引函数使蚁群优化算法更快地找到最优路径。

4.2 改进信息素更新机制

在传统的蚁群优化算法中，信息素更新规则如式(4)所示，采用该信息素更新规则，虽然算法能够收敛，但无法保证算法的收敛速度[11]。为了加快算法收敛速度，提高算法搜索能力，本文通过式(8)和式(9)将额外信息素更新项添加到原始信息素更新规则中：

(8)

(9)

其中，Qextra(t)为信息素增强系数，Lavg为蚁群搜索到的平均路径长度，LBetter为短于平均路径长度的路径，LWorse为长于平均路径长度的路径，Lelse为无法到达的路径,ij表示节点i和节点j之间的路径。

使用额外的信息素更新项，提高了算法搜索效率，加快了收敛速度。同时，避免了信息素在较好的路径中无限积累而容易陷入局部极小的情况。设置信息素增强系数Qextra如式(10)所示：

(10)

其中，A和B为设置参数，N为最大迭代次数,n为当前迭代次数。Qextra的值与迭代次数成反比关系，有效避免了算法搜索后期的信息素在最好路径上的无限累积而导致算法陷入局部最优的情况。

蚁群寻找路径时主要通过信息素进行交流，信息素挥发系数ρ在蚁群优化算法中至关重要[12]。在传统蚁群优化算法中，ρ是定值，一般根据先验知识选取，主观性太强。当处于复杂环境时，ρ值较大会增加信息素的正反馈并减小搜索空间，ρ值过小会降低算法的收敛速度[13]。随着时间和迭代次数的增加，传统蚁群优化算法容易陷入局部最优解。为了提高算法收敛速度同时确保寻找到全局最优解，设置t时刻的自适应信息素挥发系数ρ(t)如式(11)所示：

(11)

其中，ρmin为信息素挥发系数ρ的最小值，μ为常数。

4.3 限定信息素阈值

在蚁群优化算法搜索后期，由于蚁群优化算法的正反馈机制，路径之间信息素差异太大，算法容易过早收敛[14]。为了提高算法的全局搜索能力，算法在每次迭代后，将路径上的信息素限制在一个固定的范围内，如式(12)所示：

(12)

其中，τmin为信息素最小值，τmax为信息素最大值。

4.4 IACO算法具体步骤

IACO算法基本步骤如下所示：

步骤1采用栅格法创建环境模型，初始化蚁群优化算法相关参数以及机器人起始点和目标点坐标。

步骤2将蚂蚁放在起始点，按照式(7)，利用轮盘赌的方法选择下一步移动到的节点j，其转移概率为pij，其中的目标吸引函数由式(6)确定，并将节点j加入禁忌表。

步骤3所有蚂蚁都搜索到路径之后，找出其中的最短路径。在已有信息素基础上增加这一代蚂蚁生成的信息素，根据式(8)和式(12)完成全局的信息素更新。

步骤4如果算法达到最大迭代次数，则输出最短路径，否则重复步骤2和步骤3。

5 仿真结果与分析

本仿真实验在Matlab R2016a平台上进行，初始化时，设置改进蚁群优化算法的参数：蚂蚁种群大小m=30，最大迭代次数N=100，其他参数α=1,β=5,ρ=0.1,Q=5,A=10,B=10。为了验证改进蚁群优化算法的性能，在规模和障碍物覆盖率不同的栅格环境中，将改进蚁群优化IACO算法与传统的蚁群优化ACO算法规划的路径进行比较。

5.1 20×20环境中2种算法比较

在20×20的栅格环境中，分别设置简单的栅格环境(障碍物覆盖率为10%，如图2a和图2b所示)和以养鸡场环境为模型的复杂环境(障碍物覆盖率为39%，如图3a和图3b所示)。图2a和图3a分别为ACO算法在简单和复杂环境中的行走路径。图2b和图3b分别为IACO算法在简单和复杂环境中的行走路径，不同环境中2种算法的路径迭代曲线分别如图2c和图3c所示。

为了避免算法结果产生的偶然性，在相同参数设置和同样的工作环境中，将2种算法独立运行10次，得到平均路径长度和平均迭代次数，如表1所示。

Figure 2 Path comparison results by two algorithms in a 20×20 simple environment 图2 20×20简单环境中的2种算法规划路径对比结果

Figure 3 Path comparison results by two algorithms in a 20×20 complex environment 图3 20×20复杂环境中2种算法规划路径对比结果

Table 1 Performance comparison between ACO algorithm and IACO algorithm in 20×20 environment表1 20×20环境中ACO算法与IACO算法性能比较

5.2 30×30环境中2种算法比较

为了进一步验证算法的优越性，将机器人工作环境扩大为30×30的栅格环境，分别设置简单(障碍物覆盖率为10%)和复杂(障碍物覆盖率为30%)的栅格环境,如图4与图5所示。图4a和图5a分别为ACO算法在简单和复杂环境中的行走路径。图4b和图5b分别为IACO算法在简单和复杂环境中的行走路径，不同环境中2种算法的路径迭代曲线分别如图4c和图5c所示。在30×30的栅格环境中，在相同的参数下将2种算法独立运行10次得到平均路径长度和迭代次数,如表2所示。

Figure 4 Path comparison results by two algorithms in a 30×30 simple environment 图4 30×30简单环境中2种算法规划路径对比结果

Figure 5 Path comparison results by two algorithms in a 30×30 complex environment 图5 30×30复杂环境中2种算法规划路径对比结果

Table 2 Performance comparison between ACO algorithm and IACO algorithm in 30×30 environment表2 30×30环境中ACO算法与IACO算法性能比较

从图2～图4可以看出，在简单和复杂的环境中，IACO算法在路径设计和规划方面都要优于ACO算法。通过2种算法的路径迭代曲线以及表1和表2中平均路径长度和迭代次数可以看出，在20×20的栅格环境中，本文IACO算法在简单和复杂环境中比ACO算法的平均路径长度缩短了2.829和5.009，平均收敛次数提升了62.190%和65.605%，在30×30的栅格环境中，相比ACO算法,本文IACO算法在简单和复杂环境中平均路径长度缩短了6.450和9.389，平均收敛次数提升了59.764%和60.202%。分析实验结果可知，ACO算法搜索效率低下，且易错过最优路径，本文IACO算法的最优路径长度更短，相比ACO算法拥有更加高效的寻径能力和质量。

6 结束语

本文通过对规模化养殖场巡视机器人路径规划问题的分析和建模，提出一种改进的蚁群优化IACO算法,用于巡视机器人路径规划。为了缩短算法的迭代时间，采用目标吸引函数代替传统启发函数，加入额外的信息素更新项加快算法的收敛速度；其次设置了自适应挥发系数，以有效克服算法后期易陷入局部最优的缺陷。通过仿真实验表明，本文的IACO算法用于移动机器人路径规划，在简单(较少障碍物)和复杂(较多障碍物)环境中都可以找到最佳避障路径。