基于势场改进蚁群算法的足球机器人路径规划研究

2018-06-25曲宝福王利利任超群

现代商贸工业 2018年21期

曲宝福王利利任超群

(1.内蒙古工业大学，内蒙古呼和浩特 010051；2.固阳县职业教育中心，内蒙古包头 014200)

0 引言

足球机器人在机器人发展领域发挥着重要的作用，具有广泛的应用前景。而机器人足球比赛作为检验机器人技术的一种有效手段，成为当前学术界的研究热点。

决定足球机器人胜负的关键因素就是合理的路径规划。路径规划简单的理解就是让机器人遵循某种性能指标(如距离，时间等)，从初始位置到达目标位置作出最优的行走路径。目前，路径规划的求解方法主要有人工势场法和基于人工智能的启发式方法，如蚁群算法、遗传算法和粒子群等。蚁群算法是一种受到生物界蚁群觅食行为的启发式搜索算法，本文为校及科研项目，项目实施过程中对各种算法进行实验比对，最终提出一种势场改进蚁群算法的足球机器人路径规划算法，并测试其有效性和优越性。

1 建立足球机器人路径规划模型

足球机器人比赛规则：要求由多个机器人组成足球队，在一个实时、噪声和对抗性的环境下进行，以机器人射门得分最高为胜。足球机器人的路径规划模型如图1所示，当前位置为足球机器人的起始点，当足球机器人遇到障碍物时，在避免碰撞的前提下，找到一条从起始点到达目标点长度最短的路径。

图1 足球机器人的路径规划模型

2 人工势场法的缺点

传统的人工势场法具有其不足和局限性:局部最小值问题；在障碍物前振荡前进；不能从两个距离较近的障碍物之间穿过等。其中，局部最小值问题是由于机器人在环境空间中在某个位置产生的斥力(或斥力的合力)和引力正好在同一条直线上大小相等，方向相反。则机器人认为已经到达目标处故在该点停留或者振荡徘徊。另外不能从两个较近的障碍物之间穿过也是上述原因，如图2所示。振荡前进则是如下图3所示。

图2 局部最小值的例子

图3 振荡前进示意图

3 人工势场的改进蚁群算法

结合人工势场法在未知环境下局部搜索的优势和蚁群算法在全局路径规划中的特点，用联合启发因子来进一步提高机器人在路径规划中的效率。

蚁群中一共有m只蚂蚁，当其中的蚂蚁k在第n位置P(n)=r转移到下一步位置P(n+1)=s的概率依据是由下面的式子决定的：

(1)

(2)

第k只蚂蚁在搜索路径的过程中，对走过边的局部信息素更新遵照下式：

τrs(n+1)=(1-ψ)τrs(n)+ψτ0

(3)

当0<ψ1为一个常数；τ0=m/Cnn为初始信息素的值；Cnn为相邻的启发规则产生的路径的长度。这个蒸发过程是为了避免对其它的蚂蚁的过于强的吸引力，以避免迭代过早的收敛，让蚂蚁对其他路径搜索的可能。当m只蚂蚁都已经走完，完成一次迭代后，对所有蚂蚁的路径进行比较从中找出最短路径，并对这条路径进行一次全局信息素更新，如下式：

τrs(n+1)=(1-ρ)τrs(n)+ρΔτrs(n)

(4)

当0<ρ1为控制信息素衰减速度的常数；其中Δτrs=1/Lgb，Lgb为本次迭代所找到的全局最优路径。

上述将人工势场法和蚁群算法的改进分别作了详述。下面将两种算法融合到一起，让它们共同构成完整的规划过程，可得该势场改进蚁群算法的启发信息ηrs为：

(5)

从式中得出，当势场的合力，也就是机器人处于势场的局部稳定点处，这时若只在人工势场中，将陷在局部最优中。但在本算法中，由于蚁群算法的加入，在这时启发信息会为ηrs(n)=ηd(n)=1/d2(P,G)，也就是说当某一位置合力Ftot=0时，ηd的启发信息会引导机器人跳出局部最优这个陷阱，继续进行全局最优路径的搜索。

4 仿真与实验分析

4.1 人工势场蚁群算法

人工势场蚁群算法仿真图及迭代次数与路径长度如图4、图5所示，在迭代30次后，算法就趋于稳定，最优路径长度在33.9258，这条路径也在最优路径上。但从图上也看出收敛曲线波动比较大，说明该方法在收敛上存在可以改进之处。

图4 势场蚁群算法

图5 迭代次数与路径长度关系

4.2 人工势场改进蚁群算法

如图6、图7所示在迭代15次后，算法就趋于稳定，最优路径长度是33.9053，在收敛效率上进一步提高，而且收敛曲线也较之前的方法平顺了很多，改进收敛效果明显。

图6 势场改进蚁群算法

图7 迭代次数与路径长度关系

综上所述，我们可以得出应用结合人工势场法的改进蚁群算法在收敛效率上有了明显的提高，搜索最优路径时间更快更加趋于合理。该算法克服了人工势场法遇到的局部最优和目标不可达等问题，而且提高了算法的收敛性。

5 算法验证

在实验平台AS-ROII上进行真实环境验证。将C++的算法代码用Visual studio2008生成可执行文件，利用无线局域网导入AS-ROII本体。利用此算法，机器人在实际运行中的路径比较平滑，但机器人行进过程中，当挪动障碍物形成动态规划时，机器人在靠近障碍物时会出现震荡前进，但最后依然可以到达目的地。这也为以后的进一步研究提出了改进方向。