栅格法简单有效,对障碍物的适应能力强,可大大减小建模的复杂性,便于计算机存储和处理,并可防止丢失部分可行路径,已被广泛用于环境建模方法。故采用序号法和二维直角坐标相结合的方式建立栅格模型(见图1)。如图2所示,其中黑色栅格抽象为障碍栅格,白色栅格抽象为自由栅格。block[ x][ y]表示节点 i处( x_i, y_i)的信息,设起始节点为 s,终止节点为 g。在栅格图中,栅格序号值 c与位置坐标( x, y)的对应关系为:

式中:mod为取余运算;int为取整运算; m为每一行的栅格数。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 栅格法建立环境模型Fig.1 Environment model by grid method

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 斜行与弧形前行示意图模型Fig.2 Diagonal forward and arc forward

受灾现场的目标点未知,机器人找到目标点后,以起始点与目标的连线为对角线建立栅格图,确定搜索范围。

单个机器人的搜索范围有限,只能识别自身周围的8个栅格,而栅格的大小略大于搜索机器人的体积。机器人不能等效为质点,因障碍物的阻挡,因此不能斜行前进,只能有4个行走方向。机器人可以选择弧形前行的方式,缩短绕行距离,扩大行走范围。

在基本蚁群算法中,蚂蚁很容易陷入如U型障碍物发生死锁,导致算法停滞,文献[7]提出了蚂蚁回退策略,增强了算法的鲁棒性。但当U型障碍物很多时,蚂蚁需要反复回退、反复判断是否在U型路径中,增加了计算量。本文采用设置禁忌栅格的方式进行优化,当蚂蚁进入U型路径时,将入口节点压栈处理,并不再采用转移概率公式运动到下一点,而是按惯性直接前行,这样可简化路径选择的运算量。若存在出口,该蚂蚁通过后则继续前行;若无出口,则蚂蚁回退到入口,并将该U型栅格标定为禁忌栅格,提醒其他蚂蚁不再行走。

在传统的蚁群算法中信息素挥发因子 ρ为常量,可能导致算法陷入局部最优解,文献[8]给出一种自适应改进方法:

式中: ρ_min为 ρ的最小值; γ为预设的衰减常数,一般取为0.95。

式(8)是基于时间的函数,本文在此基础上,进一步提出基于空间的改进策略。由于最短路径多集中出现于在起始点与终点的连线附近区域,因此将对角线附近区域定义为重要区域;而起点与终点附近区域尤为重要,定义为核心区域,需加大搜索力度;而与核心区域相对的两个对角区域,出现最短路径的概率最小,定义为非核心区域,如图3所示。第一只蚂蚁搜索到目标点后,建立搜索范围,将整个区域划分为核心区域、非核心区域和重要区域,并通过调节 ρ值实现:

式中:( x_i, y_i)为节点 i的坐标;( x_s, y_s)为起点坐标;( x_g, y_g)为终点坐标;mid为中间分割线; δ为某一常数;使 ρ( l)与 ρ( t)处于同一量级。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 核心区域与非核心区域示意图Fig.3 Core area and non-core area

因此,信息素更新的公式改为:

引入 ρ( l)后,在非核心区域内 ρ( l)值较大,可加速信息素的挥发,减小蚂蚁进入该区域搜索的概率;在重要区域内,信息素含量较高,而在核心区域内 ρ( l)值最小,信息素含量最高,蚂蚁更倾向于在该区域内搜索,这样既防止蚂蚁陷入局部最优,又减少了搜索的盲目性,加快了收敛速度。

在实际应用中,机器人搜索到达目标点后,应返回到起始点。为更大限度地发挥蚂蚁个体的搜索能力,文献[9]提出一种带折返的迭代方式,但这种方式会造成正向信息素对反向信息素的干扰,本文提出新的改进策略,蚂蚁个体由起点到达终点,则进行信息素更新;随即返回起点,再次更新信息素完成单个蚂蚁一次迭代。这样可以减少蚂蚁迭代时的等待,加大了蚂蚁的重复利用率,提高了搜索效率。

在正向前行和反向折返过程中,分别采用不同的转移策略。

(1)正向搜索策略

对式(2)的启发信息 η_ij 和信息素因子 α做出改进,以距离信息作为主要导向:

式中: d_jg为 j点到目标点 g的距离。

采用当前节点到目标点的距离作为启发信息,可大大加强蚂蚁搜索的目的性,加快算法的收敛速度。为防止搜索空间过小,需加大正向信息素因子 α_f( α_f >1),增大信息素对下一节点选择的比重。

若 d_jg≤ d_ig,定义节点 j为近距节点;若 d_jg>d_ig,定义节点 j为远距节点。

蚂蚁转移一般采用的是轮盘赌选择法,按距离因素搜索时,按上述表述,远距节点无需搜索,仅需计算几个近距节点,因此allowed _k可更改为所有近距节点,采用这种策略可进一步减小计算量,加快算法的收敛速度。

(2)反向折返搜索策略

为减小正向搜索产生的信息素对折返过程造成的影响,增强搜索的随机性,需减小反向信息素因子 α_b( α_b <1),减小信息素对下一节点选择的比重,式(2)中的 η_ij 更改为:

采用 η₂作为启发信息可增强蚂蚁搜索的随机性,适当扩大搜索空间。

采用折返搜索策略可实现正向蚂蚁与折返蚂蚁之间的优势互补,弥补各自搜索时的不足,提高了蚂蚁的利用率和搜索效率,兼顾了算法的收敛速度和多样性。

由于在实际应用中,机器人寻找的为最优路径而非最短路径,因此引入计算量和转折量作为新的评定指标,构造综合评定目标函数。机器人在应用中常采用嵌入式系统,在选择节点时可能会因计算量大而导致机器人短暂停滞,因此应尽量减少大量的计算,引入计算量评定目标函数:

图4为节点计算量示意图。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 节点计算量示意图Fig.4 Schematic diagram of calculation of node

当节点 i的可行节点 j为障碍栅格或远距节点时,节点 j无需带入转移概率公式计算,当节点 j为近距节点时才需要计算,因此每个节点计算量不同:

机器人在急速转弯时,会造成一定的能量损耗,因此应尽量避免机器人的大量转弯,使机器人按原定方向前行,即保持一定的“惯性”,增强路径的平滑性,引入转折量评定目标函数:

不同的转角对前行的影响也不同,因此加入转角的惩罚措施:因为蚂蚁是在栅格图中移动,转角只能为45°、90°、135°,3种转角采用不同的权重系数,加大对大转角的惩罚力度。图5为转角惩罚示意图。

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 转角惩罚示意图Fig.5 Schematic diagram of turning angle punishment

t_i( l) =λ₁ t_{45 °}+λ₂ t_{90 °}+λ₃ t_{135 °}(16)

式中: λ₁、 λ₂、 λ₃为权重系数,暂定 λ₂ =2 λ₁, λ₃ =3 λ₁; t_{45 °}=π/4, t_{90 °}=π/2, t_{135 °}=(3 π) /4。

因此综合评定函数为:

式中: ω₁、 ω₂、 ω₃代表不同的权值大小。

信息素更新策略变为 Δ ( t) =Q/F_k,这样在更新信息素时算法会在考虑距离时兼顾计算量和转折量,选出最优路径。

Step1 改进蚁群算法初始化。循环次数 N_c=0,时间 t=0,出动蚂蚁波数 N_cmax,将 m只蚂蚁放在栅格图中Start位置。按式(9)确定 ρ( l),分配起始空间各区域信息素浓度 τ_ij( t)。

Step2 发动 m只蚂蚁根据正向搜索策略进行最佳路径搜索。当有蚂蚁找到目标点时,填充禁忌表,运用式(13)(15)确定并记录下计算量 Cal( l)、转折量 Turn( l),及此路线的综合评定函数 F_k,对未找到终点的蚂蚁,使其死亡,不进行信息素的更新。对找到终点的蚂蚁,按式(7)得出信息素增量,根据式(8)确定当前信息素衰减因子,根据式(10)更新整个障碍空间内信息素。

Step3 更新信息素后,蚂蚁立即调转方向,根据反向搜索策略搜索起始点。在找到起始点后,再次按照所走路线计算并记录 Cal( l)、 Turn( l)、 F_k值,确定信息素增量,信息素衰减因子,并更新整个障碍空间内的信息素。

Step4 当出动的所有蚂蚁都已返回起点后,填充禁忌表,完成一次循环,找出此次循环最短路径,循环次数 N_c=N_c+1。

Step5 若循环次数 N_cc_max,清空禁忌表,跳回到Step2;否则,比较每次循环每只蚂蚁的 Cal( l)、 Turn( l)值,输出最小值,画出最优路径。

为验证算法的性能,本文首先使用Matlab编写仿真程序。硬件环境如下:CPU为Core i3,2.13 GHz,2 G内存。

仿真中各参数设定如下:蚂蚁的个数为50只,信息素初始浓度 Δτ_ij( t) =8,正向信息素因子 α_f =1 .2,反向信息素因子 α_b =0 .8,新增信息素强度因子 Q=1,衰减常数 γ=0.95,最小信息素挥发因子 ρ_min =0 .1,权重系数 λ₁ =1,权值 ω₁: ω₂: ω₃ =5 ∶2 ∶1, q₀ =0 .35。实验在20×20的栅格图中进行。

由表1的数据可以看出,虽然本文算法与基本蚁群算法、文献[7]算法找到的最短路径相同,但由于综合评价函数的引入,使得计算量、转折量都优于其他算法,因此,得到的最优路径效果更好。

表1

Table 1

表1(Table 1)

表1 本文算法与其他蚁群算法仿真比较 Table 1 Simulation comparison between proposed and other ant colony optimization algorithms 性能指标 蚁群算法 文献[7]算法 本文算法 综合评价最优路径 181.1 181.0 179.4 最短长度 29.80 29.80 29.80 最优转折量 19.63 19.59 18.13 最优计算量 50 50 49 最佳迭代次数 53 12 5 平均迭代次数 60 16 8 运行时间/s 19.1098 6.2410 1.4801

表1 本文算法与其他蚁群算法仿真比较 Table 1 Simulation comparison between proposed and other ant colony optimization algorithms

本文算法寻找到的最优路径如图6所示。最短路径、转折量、计算量及综合评价的收敛速度如图7~图10所示。

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 本文算法寻到的最优路径Fig.6 Optimal path by proposed ant colony optimization algorithm

图7

Fig.7

	Figure Option ViewDownloadNew Window
	图7 最短路径收敛速度Fig.7 Convergent speed of shortest path

图8

Fig.8

	Figure Option ViewDownloadNew Window
	图8 转折量收敛速度Fig.8 Convergent speed of turning quantity

图9

Fig.9

	Figure Option ViewDownloadNew Window
	图9 计算量收敛速度Fig.9 Convergent speed of calculated quantity

图10

Fig.10

	Figure Option ViewDownloadNew Window
	图10 综合评价收敛速度Fig.10 Convergent speed of comprehensive evaluation

从仿真对比结果中可以看出:与基本蚁群算法相比,本文算法的收敛速度明显加快,全局寻优能力有很大的提高。从各个评价量的收敛曲线对比中可以看出,本文算法寻得的最优路径的计算量和转折量都有一定程度的减少。

图11

Fig.11

	Figure Option ViewDownloadNew Window
	图11 最优路径Fig.11 Optimal path compared with ant colony optimization

图12

Fig.12

	Figure Option ViewDownloadNew Window
	图12 硬件平台示意图Fig.12 Schematic diagram of hardware platform

在随机生成的30×30的栅格中运行规划出最优路径如图11所示。大量仿真实验证明,本文算法针对复杂地图具有较强的适应能力,即使在复杂的障碍环境中,该算法仍可以规划出最优路径。

在实际应用中,为节约成本,机器人的数量不能太多,此处采用3只机器人在16×16的栅格环境中进行搜索,每个栅格长度为18 cm,如图12所示,两种算法对比结果如表2所示。

从表2的数据中可以看出,由于机器人数量太少,基本蚁群算法几乎无法找出最短路径,极易陷入局部最优解。而本文算法仍能以非常高的效率搜索出最优路径,因此具有很强的实用价值。

表2

Table 2

表2(Table 2)

表2 实际运行结果对比 Table 2 Experimental result comparison 性能指标 蚁群算法 本文算法 平均最优路径长度 497.952 432.486 最佳迭代次数 56 2 平均迭代次数 75 4 运行时间/s 70 56

表2 实际运行结果对比 Table 2 Experimental result comparison