基于改进马尔可夫决策过程模型的多机协同航路规划研究

刘 蓉,张 衡,肖颖峰

(南京航空航天大学 1.无人机研究院;2.工信部中小型无人机重点实验室;3.自动化学院,江苏 南京 210016;4.中电熊猫汉达科技有限公司,江苏 南京 210016)

协同航路规划作为实现多无人机协同作战的关键环节,已成功聚焦国内外无人机领域专家的研究方向[1-3]。协同航路规划所生成航路能保证无人机之间相互配合,以最小的飞行代价完成任务[4]。目前,国内外对多机航路规划的研究,均侧重于对多无人机进行单独航路规划,很多没有考虑任务的时间协同要求[5-7]。常规的蚁群算法、遗传算法、A*算法具有较强的鲁棒性与良好的信息反馈能力等优点,但在复杂的战场环境下算法的收敛速度低导致路径搜索时间较长且易陷入局部最优[8-11]。随着人工智能技术的发展,基于Q学习方法的马尔科夫决策模型被应用于航迹规划,但其状态转移概率设计仅考虑了无目标点和目标点在正北方时的两种情况,无法充分体现状态转移概率在大范围状态空间下的分布[12]。

针对以上问题,本文提出一种基于改进马尔可夫决策模型的多无人机航路规划算法,利用离散化的雷达威胁信息,合理设计多无人机作战环境,离散化目标点方位空间,合理分配状态转移概率,在无模型均匀结构的报酬函数基础上引入了非均匀结构雷达威胁模型,建立改进马尔可夫决策过程(Markov decision processes,MDP)模型。最后在MATLAB环境中进行仿真实验,验证算法有效性。

1 多机协同航路规划

1.1 任务描述

多机协同航路规划是指多无人机的飞行航路满足客观约束条件同时能够让各无人机实现最优或次优的特定性能指标[13]。为降低威胁模型复杂度,本文仅考虑敌方雷达的影响[14]。如图1所示,由3架某型无人机在特定场景下执行任务,在该飞行场景下利用栅格法建立坐标系,A、B、C为3架无人机的起始点,D点为任务目标点,圆形区域为雷达威胁区域。多无人机协同航路规划的任务就是为整个无人机编队规划出安全可飞航路,并同时到达目标点[15]。

图1 多无人机协同航路规划示意图

1.2 多无人机综合航行代价

1.2.1 油耗代价

航路的油耗代价可表示为

JL,i=clLi

(1)

式中:cl为比例系数;Li表示第i架无人机的航路长度;JL,i为无人机的油耗代价。

1.2.2 威胁代价

第p个航路段所受到的威胁代价可表示为

(2)

无人机整体航路所受到的威胁代价为

(3)

式中:JT,p表示无人机在第p个航路段所受到的雷达威胁代价;lp表示第p个航路段长度;NT为雷达威胁个数;d1/4,p,q、d1/2,p,q、d3/4,p,q分别表示无人机在第p个航路段的1/4、1/2、3/4处与第q个雷达之间的距离;JT,i表示第i个无人机所受到的总体威胁代价。

1.2.3 多机协同航行代价

本文采用多机协同航行代价为时间协同代价。多无人机协同飞行在满足时间协同约束的条件下,才能同时到达规定目标点。时间协同代价可表示为

Jt,i=α(Li/vi-ta)

(4)

式中:Jt,i为时间协同代价;α>0为调节权重;Li为无人机航程;vi为无人机的航行速度;ta为时间协同变量。

1.2.4 综合航行代价

对于多无人机,航路代价不仅考虑单机的燃油代价、威胁代价等[16],还应满足多机协同航行代价。多无人机的综合航行代价描述为

Ji=W1Jl,i+W2Jr,i+W3Jt

(5)

式中:W1、W2和W3分别为燃油代价、威胁代价以及协同代价的权重,Jl,i代表燃油代价,与无人机飞行航程有关;Jr,i为威胁代价;Jt为协同代价,它随着无人机飞行时间的变化而改变。多无人机航路规划的目的就是使无人机综合代价最小化。

2 改进MDP的多机航路规划设计

2.1 马尔可夫决策基本模型

MDP模型用以下四元组M=〈S,A,P,R〉来表示[17]:S为系统状态的有限集合,包含无人机飞行环境的有限状态点;A为无人机可用的有限动作集合;P为状态转移函数,表示当主体处在状态st时,执行动作at∈A,而转移到状态st+1的概率。状态转移概率会随着目标状态、威胁状况等发生改变;R为报酬函数,表示在给定无人机当前状态和动作的情况下所能获得的立即报酬。

如图2所示,描述了在马尔可夫决策模型下,无人机与飞行环境间进行交互的过程:在无人机执行一个动作后,环境根据无人机所执行动作而提供一个立即收益,并根据该动作获知环境当前状态[18]。

图2 基本MDP模型

定义策略π作为马尔可夫决策过程的策略空间,即无人机与环境在交互过程中选取动作的方法。定义评价函数Vπ(s)作为评价策略的优劣。在航路规划的决策问题中,系统性能取决于长期的动作,无人机需经过多个时间步后完成任务或达到最后目标才能得到有意义的报酬。其中评价函数有以下3种[19]:

(1)有限范围报酬模型

(6)

(2)平均报酬模型

(7)

(3)无限范围折扣模型

(8)

式中:其中γ为折扣因子,Rt为在t时刻所对应的报酬值。

有限范围报酬模型是针对决策系统中决策序列长度已知的问题进行研究,而平均报酬模型和无限范围折扣模型则适用于对决策序列长度未知的系统进行求解。基于无限范围折扣报酬模型的评价函数相比平均报酬模型更注重近期报酬,更符合多无人机全局航路规划的特点,且基于平均报酬模型与无限范围折扣报酬模型相比前者研究尚未成熟。因此,本文在多无人机全局航路规划中将采用无限范围折扣报酬模型进行研究。

2.2 改进MDP模型的建立

2.2.1 状态空间的表示

本文定义无人机任务空间为100 km×100 km,采用栅格法进行离散建模。无人机飞行环境中,存在可飞区域与禁飞区域,因此,建立状态空间模型如图3所示,其中包含各无人机起点、目标点和若干以圆形等效的雷达威胁源,圆心所在位置为雷达出现的位置,圆的半径表示威胁源的有效作用范围。

图3 状态空间模型

2.2.2 动作空间的设计

在多无人机的航路规划中,设定了各飞机的起点和目标点之后,在航路规划时将飞机看作为一个质点。基于栅格法划分的环境空间,可将无人机的动作根据航向状态进行离散,定义无人机有8个可执行动作,a=1,2,3,…,8。整个360°被这些动作等分,相邻两个动作之间的角度为45°。如下图所示,为无人机的8个基本动作划分。

图4 无人机基本动作图

2.2.3 状态转移函数的设计

无人机所处时刻状态和对应的动作明确前提下,状态转移概率的分布将在很大程度上决定无人机在下一时刻的动作选择。状态转移概率可表示为

P(s′|s,a)=P(st+1=s′|st=s,at=a)

(9)

(10)

式中:∀s,s′∈S表示无人机的状态实例,∀a∈S表示无人机动作实例,st表示在t时刻下无人机所处的状态,at表示t时刻无人机所选择的动作。

无人机以安全到达目标点为任务目标,因此在无人机从初始点到目标点飞行时,其运动方向是以目标点的方位为导向的。将目标点与无人机的连线与目标点与X方向之间的夹角定义为θ,可以控制无人机根据目标点方位不断调整动作使无人机朝向目标点移动。根据θ可将目标点周围360°空间以45°为间隔划分,离散成8个位置状态。状态示意图如图5所示,目标点位置空间Tstate离散规则如下

(11)

在目标位置点已知时,为控制无人机朝着目标点移动,可执行的动作有限,同时认定无人机将以较大概率朝目标点方向所在栅格给出动作,也会以一定概率进入相邻的栅格,但概率较小。当无人机处于目标点某个位置空间内时,将有5个可执行动作,且每个动作概率不同,则对于8个位置空间,动作输出状态共有5×8=40。如表1所示,为部分位置空间下,无人机可执行动作的转移概率设计。

图5 位置状态示意图

表1 部分状态转移概率设计

2.2.4 报酬函数的改进设计

马尔可夫模型系统中,报酬函数是在无人机做出动作策略并与环境进行交互后由环境反馈的惩罚或奖励信号。在模型中表征着无人机在某种状态下所采取动作的好坏程度,同时也是引导无人机进行飞行决策和安全避障的重要依据。在设计报酬函数时,需要考虑以下因素[20]。

(1)靠近目标点。从起点出发至目标点,为了使每架无人机规划出的航路具有可行性,在环境模型下无人机所做出的动作行为应使其更加靠近目标点。对于无人机更加趋近目标点的动作行为,报酬函数会选择奖励,反之则会惩罚。

(2)安全性。在无人机的环境模型中,存在可飞安全区域与威胁源禁飞区域,无人机马尔可夫决策模型应在威胁源禁飞区域外规划出满足无人机可飞的航路,避开禁飞区。因此,在报酬函数中,对于接近禁飞区域的行为进行惩罚,反之则会奖励。

本文针对航路规划过程无人机的安全性和趋向目标点的问题对报酬函数进行设计,引入了无模型均匀结构的报酬函数模型Rmovegoal和Ravoidobstacle。

(12)

(13)

式中:Rmovegoal为无人机正常行驶时报酬函数模型,Ravoidobstacle为无人机遇到威胁时报酬函数模型。

无人机在飞行过程中会时刻受到雷达的威胁,所规划出的航路威胁代价过高时无人机会被雷达检测到。基于基本马尔可夫模型算法虽能为无人机规划出有效路径,但所设计的报酬模型中忽略了威胁代价对无人机安全造成的影响。因此,为进一步提高无人机自身安全性,在报酬函数中提出并引入了非均匀结构的雷达威胁模型Rthreat。

(14)

式中:Rthreat为无人机行驶时雷达威胁报酬函数模型,对于无人机飞行时受到的雷达威胁给以负的奖赏。L为无人机做出动作决策后该航路段的长度,N为雷达威胁个数,dk/4,i,k=1,2,3为航路段的k/4点处与第i个雷达威胁之间的距离。

2.3 搜索策略

基于马尔可夫决策模型的多无人机航路规划旨在通过无人机动作与飞行环境之间进行交互并最终产生决策,规划出无人机的有效航路。无人机主体根据当前环境状态s,选择并执行动作a,使无人机状态由s转移到s′,同时获得报酬R,循环往复,直到最终达到目标状态。因此,寻找最优策略π*,即根据无人机的当前状态,执行搜索策略,搜索使期望报酬即评价函数Vπ(s)最大的动作序列。

最优策略π*表示所有状态s∈S均存在V*(s)=maxπVπ(s),最优策略π*对应评价函数为最优评价函数V*(s)。最优策略π*可用动态规划来寻找最大奖励V*(s)。评价函数Vπ(s)可以描述为

(15)

式中:γ为折扣因子Rt为在t时刻所对应的报酬值。s为t=0时刻无人机所对应的状态,s′为下一时刻无人机所处状态。则以递归形式可将上式重写为

(16)

式(16)给定了一种计算策略所对应评价函数的方法,定义状态-动作值函数Qπ(s,a)作为对评价函数求解过程中中间变量。在给定无人机初始状态s和当前动作a的条件下,无人机下一时刻将以概率P(s′|s,a)转向下一状态s′,并在未来遵循此规则,状态-动作值函数Qπ(s,a)可表示为

(17)

式中:R(s,a)为无人机在状态s下,选取动作a的所获得的报酬。

此时,MDP最优策略π*(s)可以表示为

(18)

相应地,最优评价函数V*(s)表示为

V*(s)=maxa∈A[R(s,a)+

(19)

3 仿真验证与分析

为验证基于马尔可夫决策模型的规划算法性能,利用MATLAB仿真软件,在二维坐标系下进行仿真实验。目标环境为100 km×100 km,利用栅格法将目标区域划分为100×100个单元。环境中分布3架具有相同RCS固定翼无人机及一定数量威胁源,无人机自身约束条件如表2所示。分别在简单和复杂环境下进行仿真实验。依据某预研项目的作战任务需求,简单环境下,雷达威胁个数为64,威胁半径均为2 km;复杂环境下,雷达威胁个数为64,雷达分布情况及半径参数如表3所示。

表2 无人机自身特性约束

表3 复杂环境下雷达威胁分布及半径参数

在简单环境下针对多无人机单目标任务分别采用基本蚁群算法和基本MDP模型算法进行航路规划仿真试验。其仿真结果如图6和表4所示。在复杂环境下针对多无人机单目标与多目标任务分别采用基本MDP模型算法和改进MDP模型算法进行航路规划仿真试验,其仿真结果如图7、图8和表5所示。图中,UAV为无人机各自的起飞点;图6、图7和图8中横轴和纵轴分别为无人机飞行横向和纵向范围。

图6 简单环境下仿真结果图

表4 基本蚁群算法和基本MDP模型规划算法实验数据

表5 基本MDP模型算法和改进MDP模型规划算法实验数据

图7 单目标仿真结果图

图8 多目标仿真结果图

由图6和表2可知,在简单环境下,采用基本MDP模型规划算法后,航路规划时间减少37%,航路威胁代价降低23%,航路综合代价降低19%。由图7、图8以及表3可知,复杂环境下多无人机执行单目标任务时,采用改进MDP模型规划算法后,航路规划时间减少46%,航路威胁代价和航路综合代价降低25%以上。当多无人机执行多目标任务时,采用改进MDP模型规划算法后,航路规划时间减少6%,航路威胁代价和航路综合代价降低25%以上。目前仿真验证中无人机数量最大做到100架无人机的航路规划,无人机数量增加后,算法仍能同时为多架无人机快速规划出合理有效的飞行路径,但算法的计算量变大,航路规划的时间增加了3倍。

在相同的条件下,改进后的MDP模型算法在为多无人机快速规划出合理有效的飞行路径的同时,也使航路威胁代价和综合代价大大减少,保障了在复杂战场态势下无人机高效执行任务的安全性。

4 结论

针对多无人机在复杂环境下执行作战任务时易受环境威胁影响的问题,提出一种基于改进马尔可夫决策模型的多无人机航路规划算法。将威胁代价与马尔可夫模型相结合,在无模型均匀结构的报酬函数基础上引入了非均匀结构的雷达威胁模型,建立改进马尔可夫决策模型执行策略搜索,为多无人机进行飞行航路规划。仿真结果表明,基于改进马尔可夫决策模型的多无人机航路规划不仅能为多无人机快速规划出合理有效的飞行路径,也将多无人机航路的威胁代价和航路综合代价有效降低了25%,保障了在复杂战场态势下无人机高效执行任务的安全性。