基于粒子群算法的无人机灭火路径规划仿真

李锐君,董素鸽

(1.郑州西亚斯学院电信与智能制造学院,河南 郑州 451150 2. 信息工程大学信息与系统工程学院,河南 郑州 450000)

1 引言

随着科技的发展无人机已经逐步从单纯的飞行设备转变为多功能的智能系统,被大量应用在民用以及军事等领域内[1]。在民用领域内,无人机被大量运用在关键区域火灾灭火、建筑施工路线勘察及农情监测等方面,而在军事领域内,无人机可被作为军事武器应用于战场上[2]。其中灭火无人机的应用与相关问题的研究已成为当下诸多学者的重点研究方向。无人机灭火方式可解决传统人工灭火人员伤亡问题,大幅度降低火灾环境中灭火人员的危险等级[3,4]。而对于无人机灭火方式而言,保障无人机在实际灭火环境中无碰撞、高效率完成灭火行为的关键即为最优灭火路径的规划问题,需通过研究恰当的无人机灭火路径仿真规划方法,获得长度最短、耗时最低、水平转角最平缓且可完全避开障碍与危险区域的路径,为无人机灭火方式提供保障[5]。

粒子群算法属于一类迭代优化算法,它通过模拟鸟群觅食过程,将每只鸟看成一个粒子,即优化中的可能解之一,鸟群看成粒子群,通过运用相关适应度函数实现粒子群的迭代进化,寻得最优解[6,7]。该算法的优点是早期搜寻效率高,缺点是搜寻时易错失最优解,且易步入局部最优[8]。细菌觅食算法属于一类群智能优化算法,是通过对肠道中大肠杆菌觅食过程实施模拟获得的,其关键组成部分为趋向算子、复制算子及迁徙算子[9],该算法具有可并行搜索、群智能性、寻优范围广等优点,可避免所优化算法陷入局部最优,提升寻得最优解的能力[10]。

综合以上分析,本文研究一种基于粒子群算法的无人机灭火路径规划仿真方法,实现无人机灭火路径的仿真规划,获得最优最短路径,为无人机高效灭火提供科学依据。

2 无人机灭火路径规划仿真方法研究

为了实现无人机灭火路径规划仿真,需先以现实无人机灭火环境为依据构建无人机灭火路径规划仿真环境模型;再结合无人机灭火路径长度代价、无人机航迹高程代价、无人机航迹水平转角代价及灭火环境中障碍危险代价建立适应度函数;通过细菌觅食算法对基础粒子群算法实施改进,获得改进粒子群算法(PSO-BFA),定位检测出灭火环境中的火点位置,并以此类火点位置作为规划过程中的终极目标点,通过改进粒子群算法运用所构建的仿真环境模型与适应度函数实现种群迭代进化寻优,获得最优无人机灭火路径,完成无人机灭火路径规划仿真。

2.1 无人机灭火路径规划仿真环境建模

依据现实灭火环境构建无人机灭火路径规划仿真环境模型,主要包含水平区域模型、障碍区域模型、危险区域模型,具体如下:

1)水平区域模型构建:依据灭火环境地形的起伏状态选用函数模拟法构建水平区域模型,所构建的水平区域模型可表示成

z1(x,y)=dsin(x)+sin(y+c)+ucos(y)+

(1)

式中,水平区域高程通过z1表示;水平区域的点坐标通过(x,y)表示;数字地图内该区域的地表特征通过b、c、d、u、v系数表示。

2)障碍区域模型构建:障碍区域模型重点针对灭火环境中的山体与树木等障碍建模,所遵循的依据为已监测所得的实际数据信息[11]。所构建的障碍区域模型表示为

(2)

式中,树木与山体的总数目通过m表示;第i棵树木或第i座山体的控制坡度、高度分别通过li与hi表示;该树木或山体的中心水平面投影点坐标通过ei与fi表示;该区域高程通过z2表示。

3)危险区域模型构建:该区域模型重点针对灭火环境中的雷达危险体区域实施仿真建模,选取半球体近似模拟该区域,则所构建的危险区域模型可表示成

(3)

式中,危险区域的高程通过z3表示;第j个危险体的中心水平面投影点坐标通过ej与fj表示;半球体的探测半径通过r表示。

通过融合以上所构建的水平区域模型、障碍区域模型及危险区域模型,获得无人机灭火路径规划的整体仿真环境模型,可表示成

z(x,y)=max[z1(x,y),z2(x,y),z3(x,y)]

(4)

2.2 无人机灭火路径规划适应度函数创建

适应度函数是粒子群算法规划无人机灭火路径过程中种群迭代进化的根据,对粒子群算法的执行质量与效率有着直接的影响作用[12],另外,通过适应度函数能够对粒子群算法规划后所获得的无人机灭火路径的优劣实施评价。因此,适应度函数的创建是粒子群算法规划无人机灭火路径的基础与关键。在此结合了无人机航迹高程代价、无人机航迹水平转角代价、障碍危险代价与路径长度代价共同创建适应度函数。

设一共存在A条路径,各条路径均具备m个点,无人机航行环境内所具备的障碍与危险区域总计k个。各代价如下:

1)路径长度代价:作为评价无人机灭火路径好坏的关键指标之一的路径长度,其值越低代表无人机由此路径航行的耗能与用时越少。路径长度代价可表示成

(5)

式中,路径内第i个节点坐标通过(xi,yi,zi)表示;第n条路径内全部邻近节点之间的间距之和通过Dn表示,其中,n=1,2,…,N。

(6)

(7)

式中,第g个危险或障碍区域半径通过rg表示。

3)无人机航迹高程代价:无人机航迹高程即无人机平稳航行时的高度,由于无人机平稳航行高度能够有效降低无人机操控系统的负担,以此节约航行燃料,减少耗能,故该指标也是评价无人机灭火路径好坏的重要指标。无人机航迹高程代价可表示为

(8)

式中,路径节点i的高度通过hi表示;路径节点i下一个邻近节点的高度通过hi+1表示。

4)无人机航迹水平转角代价:除此之外,无人机航迹水平转角也是评价路径好坏的指标之一。无人机航迹水平转角代价可表示为

(9)

式中,无人机航行中的现实水平转角通过β表示;预先设定的无人机最高水平转角通过βmax表示。通过三角函数与向量可得出无人机的现实水平转角β,将第n条路径第j个路段的水平投影表示为

pn,j=(xn,j-xn,j-1,xn,m+j-xn,m+j+1)

(10)

则其当前转角运算式为

(11)

式中,矢量pn,j的长度通过‖pn,j‖表示。

将以上所得的路径长度代价、障碍危险代价、无人机航迹高程代价及无人机航迹水平转角代价相结合后,能够得到路径的适应度函数,可表示成

f=Dn×w1+δn×w2+Hn×w3+θn×w4

(12)

式中,w1～w4为对各代价间关系实施灵活配置的权重系数,四个权重系数的总和为1。

2.3 基于细菌觅食改进粒子群算法的无人机灭火路径规划

在构建的无人机灭火路径规划仿真环境模型基础上,通过细菌觅食改进粒子群算法(PSO-BFA),获得改进粒子群算法,对灭火环境中的火点位置实施定位检测,以所检测到的火点位置作为终极目标点,通过改进粒子群算法运用所创建的适应度函数当作种群迭代进化的根据实现迭代寻优,获得最优无人机灭火路径。

2.3.1 基于细菌觅食算法的改进粒子群算法

基础粒子群算法是通过模拟鸟觅食过程而得的,将粒子种群内各个粒子看成一只鸟,也就是一个可行路径,各个粒子采取追踪全局与个体两种极值的方式,实现迭代更新,直至搜寻到最优解,即最优路径为止[13]。粒子种群内各个粒子速度与位置的更新方程式为

(13)

式中,惯性权重通过ω表示;第i代粒子的速度与位置分别通过Vi与Xi表示;其下一代粒子的速度与位置则分别通过Vi+1与Xi+1表示;s1与s2均为随机数;全局极值与个体极值分别通过X与X1表示;q1与q2均为学习因子。

基础粒子群算法具有早期搜寻效率高的优点,但因粒子速度太快导致此算法在搜寻过程中易错失最优解,同时,此算法中全部粒子的搜寻方向相同,导致种群过于单一,令此算法最终易陷入局部最优且难以由局部最优解中跳出来[14]。为解决基础粒子群算法的以上问题,在此将细菌觅食算法融入到基础粒子群算法内,获得改进粒子群算法(PSO-BFA),通过该算法实现对无人机灭火路径的。

细菌觅食算法主要包括趋向算子、复制算子及迁徙算子三个操作步骤[15],其表达公式为

(14)

式中,0～1之间随机矩阵通过Rand表示;第i个细菌的第m个位置通过Xi,m表示;其第m次趋向方向通过Wi,m表示,其中,m=1,2,…,M1×M2×M3,复制、迁徙及趋向的最高循环次数依次通过M1、M2、M3表示;单位方向的向量通过Wd表示;随机向量通过Δi,m表示;细菌走动时的步长通过Lm表示。此算法中的各个细菌可看作是路径规划中的各条路径。通过细菌觅食算法的趋向算子可将基础粒子群算法的局部搜寻性能有效提升,并解决基础粒子群算法因粒子速度过快导致搜寻时错失最优解的问题;而细菌觅食算法的迁徙算子能够扩大寻优范围,防止粒子群算法步入局部最优。

2.3.2 灭火环境中火点定位检测

运用实时采集的火灾现场图片将火灾环境中火点相对无人机的位置运算得出,运算时所用到的火点定位图如图1所示。

图1 火点定位图

图中的红色标记为火点,设火点的中心点O位于地面,C点为由O点经过并与x轴平行的OC线同y轴的交点。无人机深度相机中深度信息已知FO、FC的长度,其中FC与OC垂直,依据勾股定理能够得出OC的长度为

(15)

已知无人机的高度h,则O点至I点的间距为:

(16)

结合式(15)与式(16),能够将J点至O点的间距获得,可表示为:

(17)

综合可得出火灾环境中火点的位置坐标为(JO,CO,0),设无人机的位置坐标为(x,y,z),那么火点相对无人机的相对位置坐标则为(JO+x,CO+y,0+z)。

2.3.3 基于改进粒子群算法的无人机灭火路径规划过程

运用改进粒子群算法在所构建的无人机灭火路径规划仿真环境中,依据所创建的适应度函数实施迭代寻优,得到最优无人机灭火路径,实现无人灭火路径规划仿真。基于改进粒子群算法的无人机灭火路径规划过程为:

1)对所构建的无人机灭火路径规划仿真环境实施初始化,将无人机灭火路径规划空间的边界确准,以R=(xmax-xmin,ymax-ymin,zmax-zmin)表示,并提取出原始起点,以B(x0,y0,z0)表示,以定位检测所得火点位置(JO+x,CO+y,0+z)作为终极目标点。

2)以数条路径构成大小为Psize的粒子种群,每条路径为一个粒子,其大小为psize,设置粒子的最高速度与最高迭代次数分别为Vmax与Gmax,其中最高速度等于0.1R,粒子的初始化速度可表示成

(18)

(19)

式中,s表示随机数,其取值区间为(0,1);第i个粒

5)对算子是否陷入局部最优实施判别,若陷入局部最优,将迁徙算子融入对部分适应度不好的粒子实施迁徙操作;若未陷入局部最优,即可继续接下来的过程。

6)对整体规划过程是否已到达最高迭代次数,或者已达到终止条件实施判别,若未达到,即可向第(4)步返回,并令λ=λ+1;若已达到即可将所得最优规划结果输出,获得最优无人机灭火路径。

3 仿真结果分析

随机选取某片户外区域作为实验灭火区域,并在其中分别设置6处模拟障碍、2处模拟危险体、3个规划原始起点及3个模拟火点后,通过本文方法在等效地图内创建该实验区域的无人机灭火路径规划仿真环境模型,在等效数字地图下运用所创建的仿真环境模型完成实验灭火区域中无人机灭火路径规划仿真,检验本文方法的应用效果。其中,实验灭火区域仿真环境模型中所设置的各个模拟障碍与危险体的关键参数、各个规划原始起点的坐标、经本文方法定位所得各个模拟火点的坐标以及本文方法中改进粒子群算法的设置参数详见表1。

表1 实验灭火区域仿真环境模型及本文方法关键参数

以3个规划原始起点作为实验灭火区域中无人机灭火路径规划的3处原始起点,3个模拟火点作为该区域无人机灭火路径规划的3处终极目标点,通过本文方法在表1中参数的设置下,分别获得实验灭火区域仿真环境中3对起止点各自对应的无人机最优灭火路径(A、B、C),如图2所示。

图2 本文方法规划所得最优无人机灭火路径

由图2可得出,本文方法能够针对不同起点与目标点(火点)实现无人机灭火路径规划,所得规划路径能够有效避开全部模拟障碍与危险体,规划效果理想。

为了更清晰地呈现出本文方法规划所得最优无人机灭火路径的效果,现通过俯视图的方式呈现出本文方法所得各条规划路径,如图3所示。

通过图3能够看出,本文方法规划所得各条路径的长度均较短,且各条路径均能够与各个障碍物、危险体保持足够的安全间距,无人机依据所规划的各条路径航行时,航迹水平转角均较为平滑,由此可见,本文方法所得各条规划路径均较优,能够满足无人机灭火需求,规划结果十分可靠。

将以上仿真重复50次,统计各条路径规划过程中的收敛迭代次数平均值、平均收敛用时、路径长度平均值,以及无人机由各条规划所得路径航行用时平均值,依据所得统计结果分析本文方法的综合性能。统计结果如表2所示。

表2 本文方法仿真中关键性能指标统计结果

分析表2能够得知,本文方法在规划各条无人机灭火路径的仿真中,三条规划路径的总体平均收敛迭代次数为123次,总体平均收敛用时为4.49s,原因是本文方法在规划过程中将趋向与迁徙算子融入算法中,虽令运算中的迭代次数稍有增长,但整体收敛用时却较低,提升了整个规划过程的收敛速度;另外,本文方法规划所得各条无人机灭火路径长度较短,可降低无人机灭火航行用时。综合以上结果可知,本文方法的综合规划性能较好,能够快速获得最短最优灭火路径,为无人机实现快速无碰撞灭火提供保障。

4 结论

本文针对一种基于粒子群算法的无人机灭火路径规划仿真方法展开研究,创建无人机灭火路径规划仿真环境模型与适应度函数,将细菌觅食算法内的趋向算子与迁徙算子融入基础粒子群算法内,得到改进粒子群算法,通过定位检测出灭火环境中火点位置,运用改进粒子群算法结合所创建的仿真环境模型与适应度函数,以定位所得火点位置为灭火路径规划中的终极目标点,对由数条路径构成的粒子种群实施迭代更新寻优,得出最优无人机灭火路径,实验仿真结果表明,本文方法能够针对所仿真的灭火环境实现无人机灭火路径规划,且所规划的灭火路径能够避开全部模拟危险体与障碍物,路径的长度短且水平转角平滑度高,可有效降低无人机航行用时,整体规划过程中可快速收敛,规划结果理想可靠。