林火搜救多无人机协同任务分配方法
2024-05-07姜雪松张宇晨郭轶男李晋泽
刘 森 姜雪松 张宇晨 郭轶男 李晋泽
(东北林业大学,黑龙江 哈尔滨 150040)
随着科技的不断进步与创新,越来越多的国内外专家与学者开始致力于探索无人机在搜救行动中的潜在应用。
肖玉杰等[1]提出了一种分层框架,其用途是分配任务、规划路径和进行碰撞检测,其中,使用协商算法进行任务分配。袁德平等[2]运用群智能算法和进化算法解决了搜救任务分配问题。朱红果等[3]提出一种基于市场机制的复杂任务分配算法,充分考虑了任务的优先级,并验证了分层动态树方法在大规模UAV监测中的有效性。国博等[4]创建了基于混合整数线性规划的任务分配模型,并改进了粒子群算法,以解决多UAV任务分配问题。有伟等[5]综合考虑多种约束条件,建立多目标整数规划的任务协同分配模型,设计了免疫粒子群算法,以解决多UAV任务分配问题。Deng,Qi bo等[6]使用多类型基因改进遗传算法处理异构UAV动态任务分配问题,同时考虑了资源约束。基于无人机在搜救行动受到的环境影响,如风速、风向、大气能见度、云层高度以及光照角度等关键要素,本文构建了一个无人机-环境约束模型,旨在精确评估并优化无人机在复杂环境下的搜救效率。针对多机协同搜救任务分配问题,提出状态压缩动态规划算法,通过仿真确定最终任务分配方案。
1 无人机-环境约束模型
1.1 风力风速约束模型
无人机的最大抗风能力Cw通常取决于多个因素,包括无人机的质量、体积以及发动机的最大输出功率等核心参数。在气象学领域,根据其对各种物体的影响程度将风速划分为不同的等级。目前,搜救无人机能够在最大风力达到6级的情况下保持稳定运行和操作。为保障搜救无人机的安全,保证搜救效率,本文设定了无人机可承受的最大风速为10.8m/s。一旦风速超过阈值,无人机将无法通过该区域。当风速超过可承受最大风速时,可通过降低无人机的飞行高度来减缓风速,直至其降至无人机可承受的最大风速范围内。采用该模型的目的是找到一种策略,以应对不同风速条件下的搜救任务,如公式(1)所示。
式中:vΔH为由当前高度降低高度ΔH后的风速大小;vs为海拔高度Hs处的平均水平风速大小构建无人机最大抗风能力与飞行速度之间的约束模型,以保障搜救行动的安全,如公式(2)所示。
式中:v为搜救无人机搜索时的飞行速度;vw为当前风速;cw为无人机可承受最大风速。
1.2 能见度约束模型
根据森林地区能见度的特性分析,该地区的局部能见度与平原地区存在显著差异,变化较大。在能见度较低的情况下,为了确保机载摄像机能够清晰拍摄到目标区域的地面情况,搜救无人机需要降低飞行高度,因此,本文构建了能见度与拍摄距离之间的约束关系模型,如公式(3)~公式(5)所示。
式中:Vis为目标区域的当前能见度;Hcloud为云层距离地面的相对高度;Hmin为搜救无人机在该地区最低安全飞行高度,具体高度值须根据实际情况进行确定;Hmax为搜救无人机的最高飞行高度。
1.3 光照角度对无人机搜救约束
通常可以用太阳的高度角和太阳方位角来描述光照角度。这2个参数对拍摄图像的清晰度和质量有重要影响,如图1所示。
图1 太阳光照角度
光照角度和方位角关系式如公式(6)所示。
式中:α、β分别为太阳的高度角和方位角;φ、δ分别为赤纬角和太阳时角。
1.4 搜救无人机视程约束
当搜救无人机执行搜索与救援任务时,其核心功能依赖于图像采集技术。在实践中,常见的图像采集方法涵盖了摄像机、扫描仪、红外线热成像仪以及激光雷达等多种设备。然而,鉴于森林环境的独特复杂性,这些设备在应用中常会受到环境因素的干扰,影响其精确度。同时,考虑经济成本,搜救无人机难以配备高精尖或高成本的图像采集设备。搜救无人机携带的摄像机系统包括摄像头和云台2个主要部分,以满足在搜救任务中获取图像数据的需求。搜救无人机机载摄像机对目标区域地面的拍摄方式如图2所示。
图2 搜救无人机动态视程示意图
无人机尺寸和搜救无人机拍摄视程的比例关系如公式(7)~公式(9)所示。
式中:p为待搜救区域面积和无人机搜救视程之间的比例关系;l为待搜救区域长度;w为待搜救区域宽度;α、β分别为太阳的高度角和方位角。
1.5 无人机动态搜救油耗约束
搜救无人机的油耗受多种因素影响,包括发动机型号、飞行速度、载荷以及飞行高度。在发动机型号一致的情况下,飞行速度、载荷和飞行高度与油耗之间存在正相关关系。随着飞行速度的增加、载荷的加重以及飞行高度的提升,无人机的油耗也会相应上升。基于这些因素,可以构建一个关于搜救无人机油耗的模型表达式,如公式(10)~公式(15)所示。
式中:Fueli为搜救无人机在高度Hi处搜救时的油耗;v为搜救无人机的飞行速度;G为无人机所携带的负载;为搜救无人机在高度H处巡航时的油耗;C为巡航阶段;fuelH为搜救无人机在巡航阶段的速度、高度和载荷均不变阶段无人机的油耗为固定值;为搜救无人机爬升高度的油耗;U为爬升阶段;λ1每百米油耗增长系数,即每爬升100m消耗燃料增加量的燃料消耗;为搜救无人机下降高度ΔH的油耗;D为下降阶段;λ2为每百米油耗降低系数,表示在下降阶段每下降100m所减少的燃料消耗;ΔH为无人机在不同飞行阶段的高度变化;C为搜救无人机在特定高度H处的巡航阶段的耗油量,即巡航期间的燃料消耗;为搜救无人机在飞行高度H处、飞行总时间的耗油量;m为在高度处H的航段数;capfuel为最大载油量。
2 无人机协同搜救任务分配模型原理
2.1 火势蔓延模型
模型假设如下。
A1:森林火灾火势初始蔓延速度与气温和风力呈线性相关。
A2:研究区域为丘陵地区,地势坡度<60°。
A3:林场类型包括草甸、次生林和针叶林。
A4:能够及时获取森林火灾区域的气象数据,如公式(16)和公式(17)所示。
式中:Vd为火势蔓延速度;Vw为风速;V0为火势初始蔓延速度;Ks为可燃物类型修正系数;Kw为风力修正系数;Kφ为地形坡度修正系数;T为温度;w为风力;a=0.053,b=0.048,c=0.275。
初始蔓延速度可通过地表可燃物取样火烧方法测算获得,根据回归取样数据可得到V0与空气温度、风速或风力等关系式;可燃物类型修正系数为草甸Ks,g=1.0;次生林Ks,sf=0.7;针叶林Ks,cf=0.4;草甸、零坡度地势、风力等级为1~12级时的Vw。
2.2 基于状态压缩动态规划算法建模
使用状态压缩的动态规划,mask:由01组成的二进制数,第i位表示第i个着火点,第i位为1说明第i个着火点已灭火,第i位为0说明第i个着火点未灭火。dp[j][mask]:说明在只有1个无人机且状态为mask时,最后1个灭火点为j,需要的最短时间prev_j:j的前一个灭火点,prev_mask:j的前一个灭火点对应的mask,time_to_extinguish:从prev_j到j点并灭火需要的总时间。先求出使用1个无人机时状态为mask的最短时间dp2[0][mask] = min(dp[j][mask]) j 在mask内再通过动态规划求出dp2[i][mask]i >1,dp2[i][mask1]= min(dp2[i][mask1],max(dp2[0][mask2],dp2[i - 1][mask1 -mask2])),dp2[0][mask2] 表示状态mask2用第i + 1个无人机去灭火dp2[i - 1][mask1 - mask2] 表示剩余的灭火点用前i个无人机去灭火,最终求出多无人机的飞行路径paths和总灭火时间。
模型假设如下。1)着火点的火势由中心匀速环状向外蔓延,蔓延半径和时间成正比。2)各无人机的救援速度相同。3)无人机同型号且飞行速度相同。4)出救点的资源储备满足火点的总需求。
目标函数min_Tp。
式中:Tp为搜救时间;Vij为第i个着火点到第j个着火点距离(第0个点为救援点);ri为第i个着火点初始火势大小;vdi为第i个着火点火势蔓延速度;vf为无人机飞行速度;Vu为无人机搜救速度。
3 案例分析
3.1 案例
为验证多无人机协同任务分配模型的有效性,本文以2010年大兴安岭呼中林业局呼中林区发生火灾为背景,根据调查有7个着火点,火灾于7月3日11时被扑灭。各火点之间的距离如图3所示、气象以及地理数据见表1~表3。本文采用贪心算法和状态压缩DP算法进行求解。所有搜救无人机均从同一起点飞入各自负责的子区域。已知该型号的搜救无人机性能如下:升限高度为6700m,最大载油量为5000mL,油耗系数λ1=λ2= 0.05;该型号搜救无人机的搜救能力如下:横向视场角α= 60°,纵向视场角β= 60°,对发生火灾区域进行标记,分别为 A、B、C、D、E、F和G 共7个地区。
表1 着火点气象数据
表2 着火点的地理数据
表3 各着火点的火势蔓延速度
图3 着火点之间距离
出救点目前有3架无人机向7个着火点进行搜救。
3.2 仿真结果
基于改进动态规划算法和贪心算法仿真结果,假设有3架无人机,飞行速度分别为80km/h、85km/h、90km/h、95km/h以及100km/h,对比如图4和图5所示。
图4 算法对比结果一
图5 算法对比结果二
对比训练结果可知,固定无人机数量和无人机飞行速度,无人机救援速度在15km/h~20km/h,贪心算法的救援时间比动态规划算法的救援时间更短,而无人机救援速度在10km/h~15km/h,动态规划算法的救援时间比贪心算法的救援时间更短。然而实际救援速度大部分在10km/h~15km/h,因此改进的动态规划算法更有优势。
4 结语
本文研究了多UAV对于动态任务分配的问题,在综合考虑UAV能耗、视程等自身性能约束,执行任务环境约束等条件的情况下建立以UAV搜救时间最短为目标的任务分配模型。1)根据搜救任务的动态变化趋势选取符合搜救环境的UAV,满足搜救任务的稳定性。2)状态压缩DP以更快的速度进行状态转移和计算,因为状态的表示更紧凑。这可以降低计算复杂度,使任务分配问题的求解时间更短,特别是对于大型复杂任务分配问题来说。