随着社会进步和科技发展,机器人被广泛应用于手术、军事、水果采摘、快递配送、抢险救灾以及餐饮服务等许多领域,这都涉及路径优化问题。全局路径优化问题是指在静态已知的环境中,机器人根据给定的路径优化算法,按照目标函数(如距离最短、时间最快和能耗最低等),搜索一条从起始点到目标点无碰撞且最优的路径[1]。目前,存在很多与求解全局路径优化问题有关的算法,如A*算法[2]、遗传算法[3]、粒子群算法[4]和蚁群算法等。在二维静态栅格环境地图中,本文重点采用本文所提的蚁群算法来研究全局路径优化问题。
每种算法都有优缺点,蚁群算法也不例外。蚁群算法有较多的优势,如较强的鲁棒性、优良的并行搜索能力和容易与其他算法融合的能力等[5-6],因此,本文选择蚁群算法规划全局路径。针对传统蚁群算法存在容易陷入局部最优解、收敛速度慢和拐点多等问题,不同学者从不同方面进行针对性改进。张苏英等[7]从路径搜索方向进行改进,添加反向路径搜索,即双向路径搜索的蚁群算法,但不是双向交替搜索,即没有使用相遇策略,而是起始点处的蚂蚁正向路径搜索结束后,目标点处的蚂蚁才开始反向路径搜索。陈英俏[8]采用基于障碍物有效顶点的并行双向蚁群算法,即首先对障碍物环境进行预处理,筛选出障碍物的有效顶点。以环境中的有效顶点为路径搜索点,以双向搜索中出现各自的信息素为相遇条件,能够快速找到一条最优路径。张玮等[9]采用烟花算法和蚁群算法相结合的方法来改进蚁群算法,将改进的烟花算法得到的最短路径转换为蚁群算法的初始信息素,蚁群算法初始信息素被差异化处理,使蚂蚁更倾向于浓度高的栅格转移,从而提高算法的收敛速度。Luo等[10]从状态转移概率方面进行改进,引入伪随机概率转移策略,即设定阈值,在该阈值范围内,蚂蚁将以大概率选择较优的栅格,提高了算法的全局搜索能力和收敛速度。王红君等[11]从拐点方面进行改进,从规划完成后的路径节点中紧接着起点的第二个节点开始,依次连接起点,直到连线与障碍物发生碰撞,前一节点为必要节点,删除中间冗余点,直到将终点加入路径中,该方法能够减少路径上的拐点数目。徐玉琼等[12]从步长方面进行改进,通过筛选可以到达的跳点,实现变步长路径搜索,不再局限于传统算法步长为1的路径搜索方式,得到的路径拐点少且最短。敖邦乾等[13]对得到的路径进行平滑处理,即采用冗余点删除策略去除路径中间冗余节点和三阶贝塞尔曲线对路径拐点进行平滑处理,最终得到的路径平滑且最短。孙凌宇等[14]采用一种跳点搜索算法与蚁群算法结合的算法求解传统蚁群算法路径规划问题,该算法能够以多邻域、多搜索方向的路径搜索方式得到最短路径。刘师良等[15]将改进的人工势场法引入蚁群算法的启发函数和状态转移函数中,具有较好的全局搜索能力和对U型障碍物的避障能力。唐宏伟等[16]采用多邻域蚁群算法实现多步长路径搜索,将步长和夹角信息引入启发函数中,加快算法的收敛速度。徐万福等[17]将人工势场法的势场分布函数引入蚁群算法的初始信息素中,实现初始信息素的不均匀分配,降低了初期路径搜索的盲目性。周晓晖等[18]采用A*算法实现蚁群算法初始信息素的不平等分布,降低了初期路径搜索的盲目性。王健雄等[19]采用路径二次规划策略平滑最优路径,即将原本的大地图分为若干小地图,再调用改进的蚁群算法进行路径搜索,能够优化路径。牛秦玉等[20]采用贪心算法平滑路径,删除了冗余点,减少了转角个数,缩短了路径长度,得到的路径更短更平滑。文献[21-22]采用贝塞尔曲线平滑由各自改进蚁群算法得到的最优路径,最终路径更短且平滑。文献[23-24]采用B样条曲线平滑由各自改进蚁群算法得到的最优路径,最终路径更短且平滑。
基于以上讨论,本文主要研究传统蚁群算法的全局搜索能力问题、路径的平滑度问题和路径最优解问题,即移动方向和视野范围受限、路径搜索的盲目性较大、规划的路径非最短、路径转弯次数多、转角大和路径不平滑问题。针对上述存在的问题,本文所做的贡献如下:首先,针对蚁群算法的全局搜索能力问题,提出了扩展邻域和方向(24邻域16方向)的路径搜索策略来扩大路径搜索视野范围。紧接着,为进一步提高蚁群算法的全局搜索能力,提出了基于扩展邻域和方向以相同路径节点为相遇条件的双向交替搜索的蚁群算法。然后,针对蚁群算法最优解问题,采用改进的启发函数和随机状态转移概率公式,降低路径搜索的盲目性,为搜索到最优路径奠定基础。其次,为进一步解决最优解问题,提出路径交叉策略,可以提高路径的多样性并解决局部最优问题。最后,针对蚁群算法的路径平滑度问题,提出路径节点转移平滑策略,减少路径拐点数目、降低转角度数、提高路径的平滑度且缩短了路径长度,最终得到的路径是最短的。
1 问题描述
以栅格地图为移动机器人的运行环境,栅格序号编码顺序为从左向右、从下到上。对障碍物进行膨化处理,只要不规则障碍物触及栅格,就将其膨化为一个栅格,再将该障碍物栅格进一步膨化,此时机器人可视为质点。
传统蚁群算法的状态转移概率公式和信息素更新公式如公式(1)~(4)所示。
$\tau_{i j}(t+1)=(1-\rho) \tau_{i j}(t)+\Delta \tau_{i j}^{\text {valid }}(t),$
$\Delta \tau_{i j}^{\mathrm{valid}}(t)=\sum_{m=1}^{n} \Delta \tau_{i j}^{m}(t)$
$\Delta \tau_{i j}^{\prime \prime}(t)=\left\{\begin{array}{l}\frac{Q}{L^{\text {valid }}}, \text { ant }_{m} \in \text { vaild } \operatorname{path}(i, j), \\0, \quad \text { 其他。 }\end{array}\right.$
式中:j∈allowedm为可选的邻居集合;τij表示当前节点和邻居节点之间的信息素浓度;ηij表示当前节点和邻居节点之间的启发式函数信息,即当前点与下一节点之间的欧氏距离的倒数;α为信息素因子;β是启发式因子;ρ表示挥发系数;Q表示信息素强度;Δ (t)意味着从起点到达终点的蚂蚁所产生的信息素浓度;Lvalid表示蚂蚁从起点到达终点所行走的路径长度。
2 改进的蚁群算法
2.1 改进路径搜索方式
2.1.1 蚂蚁搜索方向
通常,传统的或经典的蚁群算法有两种可选的路径搜索邻域和方向,即4邻域4方向或8邻域8方向。图1a表示4邻域4方向,蚂蚁只能沿水平方向或竖直方向移动,转角度数只有90°可以选择,转角较大,得到的路径不平滑,也不是最优路径。图1b表示8邻域8方向,蚂蚁在4邻域4方向的基础上,可以沿45°倾斜角方向移动,有两种转角度数可供选择。与4邻域4方向相比,8邻域8方向的转角较小,得到的路径相对平滑,路径也相对较短。图1c表示本文的16个移动方向,即24邻域16方向,蚂蚁在8邻域8方向的基础上,可以以22.5°倾斜角方向移动,有三种转角度数可供选择。与4邻域4方向和8邻域8方向相比,24邻域16方向的转角最小,得到的路径相对最平滑,路径也相对最短。增加邻域和方向有助于找到更优的路径。
2.1.2 蚂蚁搜索视野
2.1.3 蚂蚁移动方式
2.1.4 本文的蚂蚁视野优势
2.2 改进启发式函数
为降低路径搜索的盲目性,引入常数h和与迭代次数(iter)n有关的变量来增强在路径规划前期启发式函数的引导作用。随着算法不断迭代,启发式函数的路径引导性不断减弱。另外,启发式函数还包括起始点、当前节点、可选节点和终点的信息。改进后的启发式函数如式(5)~(7)所示。
当蚂蚁正向搜索路径时,
$\eta_{i j}^{+}=\frac{h}{1-h} \times \frac{d_{S j}}{\left(d_{i j}+d_{j E}\right)^{2}} \times \lambda ;$
当蚂蚁反向搜索路径时,
$\eta_{i j}^{-}=\frac{h}{1-h} \times \frac{d_{j E}}{\left(d_{i j}+d_{S j}\right)^{2}} \times \lambda,$
$\lambda=\left\{\begin{array}{l}\frac{n_{\max }-n}{n_{\max }}, n \neq n_{\max } \\\frac{1}{n_{\max }}, n=n_{\max \circ}\end{array}\right.$
式中:dSj表示起始点与可选节点之间的欧氏距离;dij为当前路径节点与可选节点之间的欧氏距离;djE表示可选节点与目标点之间的欧式距离;λ表示一个随迭代数变化的因子。
2.3 改进状态转移概率公式
为进一步降低路径搜索的盲目性,在传统的状态转移概率公式基础上,添加确定性和任一性的概率,形成三层伪随机状态转移概率J。并在三层伪随机状态转移概率公式中添加转角θ信息,使蚂蚁更喜欢选择转角较小的移动方向。改进后的状态转移概率公式如式(8)~(10)所示。
$J=\left\{\begin{array}{l}\max \left\{\omega \times \tau_{i j}^{\alpha} \times \eta_{i j}^{\beta}\right\}, 0<q \leqslant q_{0}, \\p_{i j}^{k}, q_{0}<q \leqslant q_{1}, \\\operatorname{rand}_{j}, q_{1}<q \leqslant 1,\end{array}\right.$
$p_{i j}^{k}=\left\{\begin{array}{l}\frac{\omega \times \tau_{i j}^{\alpha} \times \eta_{i j}^{\beta}}{\sum \omega \times \tau_{i j}^{\alpha} \times \eta_{i j}^{\beta}}, j \in \text { allowed }_{k}, \\0, \text { 否则, }\end{array}\right.$
$\omega=\left\{\begin{array}{l}1, \theta=0, \\0.9, \theta \in\left(0,90^{\circ}\right), \\0.8, \theta=90^{\circ}, \\0.7, \theta \in\left(90^{\circ}, 180^{\circ}\right)\end{array}\right.$
式中:randj表示在可选节点集合中,任选一个节点作为下一节点;q表示在(0,1]中产生的随机数;q0和q1分别表示(0,1)之间的常数。
2.4 双向交替搜索策略
为进一步提高算法的全局搜索能力,提出基于24邻域和16方向的双向交替搜索的蚁群算法。相比于单向的路径搜索方式,该算法能够增加路径的多样性。设置蚂蚁种群的总数目,将这些蚂蚁平均分为两组,分别放置在起始点和目标点处。首先,派出起始点处的一只蚂蚁在24邻域16方向内以一定的概率向目标点进行一步路径搜索,判断与反向的蚂蚁是否相遇。如果相遇,则结束,否则,派出目标点处的一只蚂蚁在24邻域16方向内以一定的概率向目标点(正向路径搜索的起始点)进行一步路径搜索,判断与正向的蚂蚁是否相遇。如果相遇,则结束,否则,继续上述正向的路径搜索。直到正向蚂蚁和反向的蚂蚁搜索到同一个栅格时,即该栅格为相遇点,结束算法。值得注意的是,相遇点可能为起始点或目标点,视为特殊的相遇点,即正向或反向的蚂蚁单独完成了路径规划任务。从相遇点分别向起始点和目标点回溯形成一条完整的路径,并记录该路径的相关信息(如长度、转折点数目和转角总度数等)。基于24邻域和16方向的双向交替搜索的蚁群算法仿真图如图6所示。
双向搜索过程:正向蚂蚁F放在起点S(0.5,0.5),将其加入正向路径表rF={S},反向蚂蚁R放在终点E(9.5,9.5),将其加入反向路径表rR={E},同时将起点和终点加入禁忌表。禁忌表中存储着障碍物和已经选择过的节点信息,该表的作用是防止蚂蚁重复选择已经走过的路。正向蚂蚁F根据观察到的24邻域的环境信息情况,基于改进的启发式信息、改进的状态转移概率公式和蚂蚁的移动规则将栅格13(2.5,1.5)作为下一步的路径关键点,把该栅格添加到正向的路径表rF={S,13}中,同时将该栅格加入禁忌表中,经过判断正向路径表和反向路径表中无共同的栅格信息,即没有相遇,则蚂蚁进行反向的路径搜索。反向路径搜索方式与正向的路径搜索方式类似,蚂蚁移动到栅格88(7.5,8.5),把该栅格添加到反向的路径表rR={E,88}中,同时将该栅格加入禁忌表中,经过判断正向路径表和反向路径表中无共同的栅格信息,则蚂蚁进行正向的路径搜索。按照上述正向和反向交替搜索的方式进行搜索路径,直到两个方向的路径表中存在同一个栅格的信息结束算法。我们给出相遇前一步的路径搜索情况,即正向路径表为rF={S,13,35,45,55},反向路径表为rR={E,88,86,75},此时反向路径搜索的蚂蚁在视野内搜索到正向路径表中唯一可选的路径节点55(视为相遇),直接连接这两个栅格,形成一条完整的路径。如果反向路径搜索的蚂蚁在视野内搜索到正向路径表中多个可选的节点,选择两点连接后使整条路径最短的栅格,最终rF+rR=rL={S,13,35,45,55}+{E,88,86,75,55}={S,13,35,45,55,75,86,88,E}。
2.5 路径交叉策略
为进一步求解最优解问题,提出路径交叉策略,可以进一步增加路径的多样性。所谓的路径交叉策略的定义如下:规划得到的两条完整路径有重合线段或重合点部分,经过对可交叉操作的线段部分进行互换,保留更短的线段部分,可以得到新的路径,即产生了新的解,能够得到更优的解。使用交叉策略的条件为:起始点和目标点都不是交叉点;因两条路径重合产生的多个交叉点,随机选择公共部分的二者其一;两条完整的路径存在一个或多个交叉点时,逐一进行交叉操作,从每一部分的交叉变换中选择更短的路径。每完成一次迭代的交叉操作后,记录最优路径。多个交叉点的交叉操作过程如图7所示。
2.6 路径节点转移平滑策略
通常,采用传统的或经典的蚁群算法规划出的路径存在较多的转角且转弯度数较大,移动机器人无法很好地运行。即使安全到达目标点,也将消耗大量的能量。为进一步提高路径平滑度,在由上述改进的蚁群算法规划出的路径基础上,提出路径节点转移平滑策略。该策略能够进一步使路径转折点更少,路径平滑度更高。
路径节点是指路径所经过的栅格中心点,即图8中用符号“*”表示的栅格中心点,本文主要转移拐弯处的路径节点。所谓的路径节点转移平滑策略可以描述为:转弯处的路径节点基于一定的转移规则,根据该节点所在栅格的4个顶点到起始点或目标点的距离最近原则,转移到使转移后路径最短的顶点处。传统蚁群算法只能把栅格中心点作为路径节点,导致转角角度较大,路径平滑度有待提高。通过该策略优化路径可以减少拐点个数,有效减少路径长度。
路径节点转移平滑策略实现步骤可以描述如下:
1)采用上述改进的蚁群算法规划出一条最优路径(平滑前路径),该平滑策略针对该路径进行平滑操作。
2)该策略从起始点开始到目标点结束,需要转移的路径节点主要针对路径拐点处的路径节点(不包括起始点和目标点),根据实际情况的需要,转移到顶点的点还可以转移到栅格中心点。
3)当平滑前最优路径上有竖直线段时,比如线段CD,分别计算点D所在栅格的4个角顶点 (upper left、upper right、lower left、lower right, 分别缩写为UL、UR、LL、LR) 和起始点S的距离,点D移动到距离最短的角顶点处。分别计算点C所在栅格的4个角顶点 (UL、UR、LL、LR)和目标点E的距离,点C移动到距离最短的角顶点处。因点C和目标点是同一个点,需要转移的路径节点不包括目标点,故点C位置不变。
4)当平滑前最优路径上有水平线段时,例如线段AB,分别计算点A所在栅格的4个角顶点 (UL、UR、LL、LR) 和起始点S的距离,点A移动到距离最短的角顶点。分别计算点B所在栅格的4个角顶点(UL、UR、LL、LR)和目标点E的距离,点B移动到距离最短的角顶点。
5)当平滑前最优路径上有特殊方向的线段(即斜向)时,例如图8中的点M,该路径节点两端的线段不属于上述线段方向类型,因点M位于线段SM上端,可按照步骤3)的转移方法进行转移。
6)执行完步骤3)~5),从起始点开始依次连接上述步骤筛选出的转移路径节点,连接到终点结束。平滑后的路径转弯次数更少且路径长度更短。
图9为上述整体改进的蚁群算法流程图。
其中:K0表示正向路径搜索的蚂蚁;K1表示反向路径搜索的蚂蚁;t表示算法运行时间;Tmax表示设置的最大的算法运行时间。
3 仿真实验与分析
为说明本文所提的蚁群算法是可行的和有效的,我们采用MATLAB 2016a进行仿真实验。本文仿真实验不再采用以前的比较方法[25],即设置相同数量的蚂蚁和相同的最大迭代次数,而是每种算法设置相同的运行时间,比较哪种算法在所用的迭代次数少的情况下找到最短路径。本文所提的比较方法能够减少相应的工作量,即不再比较每种算法的运行时间。本文引入的比较方法刚好与传统比较方法相反。本文设置的最大算法运行时间是根据前人大量研究数据和实际仿真过程中形成的经验法,即从蚂蚁数量、迭代数、算法的复杂程度、环境的尺度和复杂程度以及计算机性能方面考虑,算法收敛时间会在某个区间,在这个区间选择一个较为合适的值作为算法的结束条件。最终,算法会在设定的时间内找到最优解。本文将进行两方面仿真实验:一方面,设置3种不同尺度和复杂度的栅格地图环境,将本文算法与4邻域4方向和8邻域8方向的传统蚁群算法进行仿真对比与分析,证明本文所提的24邻域16方向的蚁群算法的可行性和有效性;另一方面,在尺度为50×50的复杂环境的栅格地图中,将本文所提蚁群算法与传统蚁群算法和文献[24,26-27]改进的蚁群算法进行仿真对比与分析,证明本文所提的蚁群算法具有一定的优势。
目前,并没有优化参数的统一的标准,本文采用控制变量的方法逐一优化每个参数,即在其他参数不变的情况下,以设置一系列梯度的方式只改变一种参数,从一系列梯度中选取最优参数,固定这一参数,继续采用上述步骤,直到所有的参数都达到最优组合。本文仿真参数的最优组合为:蚂蚁数量设置为60,最大迭代次数为200,α=1,β=8,Q=50,q0=0.2,q1=0.7,以下结果都是算法运行30次得到的。
3.1 3种不同环境下的仿真
图10 不同环境下3种算法最优路径图注:网络版为彩图。 Fig.10 Optimal path of three algorithms in different environments |
表1 3种环境下的仿真结果Tab.1 Simulation results in three environments |
| 算 法 | 15×15(运行时间10 s) | 30×30(运行时间30 s) | 50×50(运行时间40 s) | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 最短路径 | 拐点均值 | 迭代均值 | 二次规划最短路径 | 最短路径 | 拐点均值 | 迭代均值 | 二次规划最短路径 | 最短路径 | 拐点均值 | 迭代均值 | 二次规划最短路径 | |||||||||||
| 传统算法4邻域 | 28.00 | 7.0 | 47.7 | 58.00 | 17.1 | 31.6 | 114.00 | 76.7 | 93.7 | |||||||||||||
| 传统算法8邻域 | 23.90 | 14.7 | 84.3 | 48.53 | 23.0 | 142.8 | 88.12 | 53.9 | 135.5 | |||||||||||||
| 本文算法24邻域 | 20.44 | 6.9 | 7.1 | 20.16 | 44.04 | 15.8 | 48.9 | 42.92 | 70.21 | 16.3 | 36.4 | 69.73 | ||||||||||
3.2 50×50复杂地图环境下的仿真
表2 4种算法的仿真结果Tab.2 Simulation results of four algorithms |
| 算 法 | 平滑前 | 二次路径优化 | 平滑前拐点 | 迭代次数均值 | 运行时间均值/s | 二次路径优化后拐点 | 转角总度数/(°) | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 最小 | 最大 | 均值 | 标差 | 最少 | 最多 | 均值 | 标差 | ||||||
| 传统算法 | 91.296 5 | 109.593 1 | 98.069 7 | 4.31 | 34 | 61 | 45.7 | 6.25 | 139.8 | 40 | 2 790 | ||
| 文献[24]算法 | 72.811 2 | 72.811 2 | 72.811 2 | 0 | 72.228 8 | 9 | 14 | 10.9 | 1.79 | 33.4 | 40 | 630 | |
| 文献[26]算法 | 72.811 2 | 80.811 2 | 75.845 5 | 2.05 | 72.333 8 | 12 | 31 | 20.1 | 4.41 | 109.2 | 40 | 540 | |
| 文献[27]算法 | 72.811 2 | 75.740 1 | 73.951 8 | 0.93 | 10 | 28 | 19 | 4.96 | 16.5 | 40 | 630 | ||
| 本文算法 | 70.851 6 | 71.793 7 | 71.320 8 | 0.24 | 70.154 8 | 10 | 21 | 16 | 2.97 | 42.4 | 40 | 6.0 | 77 |
从图11中以及表2结果可知,在路径长度、转弯数目、转弯总度数和相同时间内找到最短路径的速度等指标方面,本文所提的蚁群算法和文献[24,26-27]改进的蚁群算法都优于传统蚁群算法。与文献[26]改进的蚁群算法相比,文献[27]改进的蚁群算法的启发式函数引导性更好,规划的路径较好(平滑前),转折点较少,收敛速度快,但文献[26]算法采用贝塞尔曲线进行二次路径优化,平滑后的路径长度72.333 8优于文献[27]算法最短路径长度72.811 2。与文献[26]算法相比,最新对比文献[24]采用B样条曲线优化后,路径长度更短,且每次都能找到最优解。与文献[24]算法比,本文算法虽然在收敛速度和稳定性(用30次路径规划长度的标准差来衡量)略逊于对比算法,但在路径长度、拐角数和路径转角总角度方面具有较大优势。本文算法在启发式函数中添加了起始点、当前节点、下一节点和终点等信息,路径搜索的引导性更强。加之三层伪随机状态转移概率公式,蚂蚁再根据双向24邻域搜索,引入路径交叉策略避免算法陷入局部最优,得到平滑前的路径长度70.851 6优于对比算法平滑前以及平滑后的路径长度。在路径长度与转弯点的均值和标准差方面,本文算法具有优势,表明算法每次运行都能很好地找到最短路径且稳定在最优解附近。优化24邻域搜索得到路径后,转折点数量在对比算法中最少,优化后的拐点均值为6.0,路径转角总度数最小,相应地,路径平滑性最好,最终的路径长度为70.154 8。由以上论述,验证了本文算法的优越性。
4 结论
在二维静态栅格环境地图中,传统蚁群算法进行移动机器人路径规划时,只能以4邻域4方向或8邻域8方向方式移动、很难找到最优路径和路径不平滑(拐点多和转角大)等问题,提出基于24邻域16方向的双向交替搜索的蚁群算法。24邻域16方向扩大搜索视野范围,能够更好地发现目标。双向交替搜索的路径搜索方式,能提高全局搜索能力且增加路径的多样性。改进的启发式函数和概率公式,增强路径搜索的引导性;引入路径交叉策略,避免陷入局部最优解;采用路径节点转移策略平滑路径,得到的路径拐点少且路径最短。基于以上改进,在不同尺度和复杂度栅格地图中,进行了仿真对比实验。结果表明,本文所提的蚁群算法是可行的和有效的。
本文重点研究了改进的蚁群算法求解全局(静态)路径规划问题。在现实生活环境中,机器人在前进过程中面临的不只是静态的障碍物,还存在各种各样的动态障碍物。在具有动态障碍物的环境中,依靠全局路径规划算法无法很好地避开未知的动态障碍物。因此,我们未来的工作重点是采用本文改进的蚁群算法结合局部路径规划算法(如动态窗口法和人工势场法)来研究机器人动态路径规划问题。