人工势场与蚁群算法结合下的移动机器人路径规划研究及其仿真

周祖坤

(昆明冶金高等专科学校，云南 昆明　650033)

0　前　言

移动机器人的路径规划属于机器人研究领域中的重要技术，其是基于障碍物环境，之后根据某个性能指标找寻能够从起始状态最优或者近似最优的，没有碰撞的路径。目前传统移动机器人路径规划的方法主要包括人工势场法及栅格法，栅格法能够在全局路径规划过程中使用，在环境空间扩大的时候，需要的存储内存比较大，并且计算的效率比较低，没有良好的决策实时性[1]。人工势场法属于机器人局部路径规划过程中比较成熟的方法，能够使用到实时控制中，但是此种方法容易出现死锁或者陷入局部最优的问题中[2]。在环境系统越来越复杂，并且不断增加任务难度的过程中，以数学模型为基础的传统路径规划方法无法得到良好的效果，所以就出现了部分仿生智能优化算法，比如人工鱼群、免疫、粒子群、遗传算法等，但是此种算法的搜索空间比较大，并且无法确定参数，算法较为复杂，降低了搜索效率，并且还有可能无法实现可行路径的搜索。所以，在复杂环境中，就要寻找高效移动机器人路径规划方法。蚁群算法属于随机搜索的最优方法，其属于全局优化算法，具有较广的应用领域，其能够实现全局最优路径的寻找[3]。基于此，本文就全面研究基于势场蚁群算法的多机器人编队。

1　人工势场概述

1.1　人工势场原理

简单来说，人工势场就是实现移动机器人运行环境抽象势场的虚拟。此势场主要包括两个分场：第1部分属于目标位置引力场，第2部分为在已知环境中形成的障碍斥力场。人工势场的引力场及斥力场都是矢量，斥力场的矢量方向和障碍物背对，引力场的矢量方向和目标位置相对[4]，人工势场见图1。

图1　人工势场

人工势场可以通过多种势场函数进行表示，不同函数意义也各有不同，对于移动机器人的编队，一般使用梯度势场法实现。也就是将机器人在环境中的势力场作为基础，使其在移动机器人虚拟力中作用，目标位置对于移动机器人出现引力Fatt，障碍物对于移动机器人在运动过程中产生斥力Frep，两者合力就是移动机器人对目标点进行运动的加速度[5]，图2为人工势力场的受力。

图2　人工势力场的受力

1.2　人工势场中的问题

人工势场能够有效实现移动机器人的路径规划，其理论研究较为成熟，并且被广泛应用到工业中。人工势场法能够将移动机器人运动空间拓扑结构充分的反映出来，并且及时获得已知环境障碍物的形状位置及分布情况，将此信息在移动机器人运行环境中的势场值中使用，机器人合力大小在势场变化过程中而变化。其和其他的路径规划算法相比计算量比较小，并且具有较快的反应速度及较强的实时性。但是，传统人工势场法在使用过程中还是具有一定的局限性，比如目标不可达及局部稳定[6]。

在机器人运行过程中空间受到的势场属于斥力场及引力场相互叠加斥力及引力大小通过机器人和目标位置距离相关。在障碍物与目标位置越来越接近的时候，基于引力朝着目标位置进行运动，在距离越来越短的时候，斥力就会提高，那么如果机器人斥力较大，就不能够朝着目标位置进行移动，所以无法达到目标[7]。图3为目标不可达的示意图。

图3　目标不可达

人工势场法的局部稳定是在实现路径规划时候，因为障碍物位置的不同，移动机器人在运行路径过程中目标位置障碍物斥力和引力相互抵消为0，那么移动机器人就没有牵引作用，从而出现局部稳定。图4为拒不稳定的示意图。

图4　拒不稳定

2　势场蚁群算法

2.1　环境的建模

机器人在工作过程中的环境属于二维空间，其中的障碍物静止。根据栅格化实现工作环境的划分，栅格划分的尺寸和机器人大小具有密切的联系，无障碍物栅格属于可行栅格，如果存在障碍物栅格属于不可行栅格[8]，图5为迷失的蚁群和交叉的路径。

图5　迷失的蚁群和交叉的路径

2.2　目标函数

基于栅格描述的背景下，假如机器人的起始位置属于P(1,1)，目标位置属于P(M,N)，机器人从t步进行运动，通过T步运动到目的位置，本文机器人的路径规划目标函数是通过起始点到目标点没有障碍路径的总长度L是最短的[9]，也就是：

图6　蚁群算法中信息素的扩散方向

3　基于势场蚁群算法的算法

3.1　蚁群算法的搜索

假如蚁群中的蚂蚁数量为m，第k只蚂蚁在走了t步时的位置为P(t)=r，到下个位置P(t+1)=s概率为：

在第k只蚂蚁下一步的位置使用集合表示，路径搜索过程中的蚂蚁能够出现环路，在集合为空的时候，机器人就要后退。蚂蚁k在路径搜索时候走过的边使用以下几步规则实现信息素的更新：

t(t+1)=(1-q)t(t)+q△t(t)

利用相邻的启发规则路径长度，其属于信息素蒸发过程，主要目的就是降低已经走过边的其他蚂蚁还要走，提高蚂蚁对于其他能够实现路径搜索的挖掘。在蚂蚁走完所有路径之后，就要寻找蚂蚁的最短路径，并且使用全局更新规则实现信息素的更新[10]，图7为简化之后的信息素扩散模型。

图7　简化之后的信息素扩散模型

3.2　算法的步骤

以上属于算法具体的设计，以下就是本文所提出基于势场蚁群算法的步骤：

1)实现参数的初始化。在此步骤中，主要包括栅格单独长度的创建，人工势场基本的参数，比如障碍物的斥力半径，斥力系数和引力系数，还有蚁群搜索过程中的迭代次数、蚂蚁数量等一系列的参数；

2)使用栅格化实现机器人运动过程中环境的离散化，实现各个栅格位置坐标的确定，并且实现机器人的起始栅格、目标栅格和障碍物栅格的有效确定[11]；

3)对环境自由位置势场合力方向及大小的计算，包括合力和可行方向夹角；

4)在起始的栅格中放入m只蚂蚁，蚂蚁k从以上分析中的式子启发信息中选择允许运行的边进入到另外栅格中，之后在此栅格位置中实现蚂蚁k创建路径表的存储，在所有蚂蚁到达另外位置之后，实现走过边信息素的优化，如果蚂蚁路径表栅格位置不属于目标位置，那么就要继续进行搜索[12]；

5)所有蚂蚁都在目标位置之后，对蚂蚁搜索路径长度进行计算，寻找目前搜索最短可行的路径，并且根据相应的公式实现信息素全局的搜索，对蚂蚁路径存储表进行清空；

6)对算法是否能够停止进行判断，如果可以，那么就要停止计算，并且将最短的可行路径进行输出。如果不可以，那么就要继续进行第四步[13]。

4　仿真对比

本文使用仿真平台实现仿真，在仿真过程中，蚂蚁的数量会影响到搜索路径能力和收敛的速度，蚂蚁数量越大，表示随机搜索的机率就越高，所以就会降低收敛的速度。如果蚂蚁数量较小，就会导致早熟的现象出现，停止搜索。图8为优化之后的蚂蚁算法流程。

在栅格环境中，左上角栅格就是蚁群起始的栅格，黑色的栅格属于障碍，白色的栅格属于自由栅格。对蚁群算法初始的参数进行设置，其中的启发信息因子、信息素浓度因子和信息素浓度挥发因子对搜索过程速度及随机性有一定的决定性作用[14]。

实现两种栅格环境的设置，对于传统蚁群算法及本文所提出的基于势场蚁群算法实现实验。在简单环境中简单分布障碍物，但是要避开L型的障碍，搜索路径通过折线进行表示[15]。图9为简单环境中算法改进之前的路径规划结果，图10为简单环境中改进算法的路径规划结果。

图8　优化之后的蚂蚁算法流程

a 简单环境中最短路径　　　　　　　　　　　　　　　　b 简单环境中最短路径收敛曲线

a 简单环境中最短路径　　　　　　　　　　　　　　　　　b 简单环境中最短路径收敛曲线

通过上图就可以看出来，本文所提出的算法能够搜索路径和传统蚁群算法的搜索路径较为平滑，并且路径比较短。通过多次连续实验表示，本文所研究的基于势场蚁群算法实现路径规划，具有较高的收敛速度[16]。

5　结　语

在移动机器人技术研究过程中，对于路径规划问题的研究较为重要。首先，路径规划能够对机器人的导航效果造成影响，其主要为移动机器人导航过程中的重要环节。另外，路径规划和多门学科技术具有密切的联系，寻找最优的运动路径，其能够在运动过程中寻找高效、安全及没有障碍的运动。通过本文研究表示，基于势场的蚁群算法机器人具有可行性，并且能够提高收敛速度，比传统算法要有效。