CN112824998A - 马尔可夫决策过程的多无人机协同航路规划方法和装置 - Google Patents

Abstract

本发明公开了马尔可夫决策过程的多无人机协同航路规划方法和装置，方法包括：根据马尔可夫决策过程中的状态空间、动作空间、状态转移函数与预先构造的报酬函数，构建多无人机协同航路规划任务下的马尔可夫过程模型；基于预先构造的评价函数执行基于马尔可夫过程模型的搜索策略迭代，搜索出使评价函数值最大的动作序列，从而规划出最优多无人机协同航路。本发明还将无人机行驶时雷达威胁引入报酬函数，合理设计多无人机作战环境与状态空间数目；不仅能为多无人机快速规划出合理有效的飞行路径，同时也大大降低了多无人机航路的雷达威胁代价，提高了无人机在复杂环境下执行任务的安全性。

Description

马尔可夫决策过程的多无人机协同航路规划方法和装置

技术领域

本发明涉及无人机航路规划技术领域，具体涉及马尔可夫决策过程的多无人机协同航路规划方法和装置。

背景技术

随着航空技术的发展，利用多无人机在复杂多变的环境下进行协同作战已得到广泛应用。开展无人机航路规划方法的研究，在减轻人工规划航路的负担和不便的同时，能够充分利用已知的地形、威胁等信息完成满足自身约束和任务要求的全局航路，为实现无人机低空突防、隐蔽飞行提供了技术保证。因此无人机航路规划方法是无人机系统的关键组成部分；是实现无人机自主飞行的重要前提；是保证无人机顺利完成任务、精确击中敌方目标的重要基础；是实现无人机自动控制的有力保障。开展航路规划的研究也能提高目前任务规划的整体水平，对于任务规划的进一步研究也具有重要的现实意义。开展航路规划与任务规划的研究将进一步提高了无人机的生存概率，为确定航路的作战使用价值提供有力的依据，对于我国无人机的发展具有较强的工程应用价值和现实意义。如何快速地规划出满足约束条件的飞行航迹，也是实现无人机自主规划的关键。

目前，国内外对于航路规划的研究工作主要集中在航路规划算法方面，航路规划算法对无人机的自主飞行、精确跟踪或打击起着决定性作用，关系着航路规划的效率甚至是无人机的生存概率。航迹规划中，无人机所执行的任务不同，所采取的航路规划算法亦不同。执行简单的侦查任务时，只需根据已经获得的信息规划出一条全局航路，无人机在起飞前只需加载该全局航路即可。而实施对敌打击时往往伴随着敌方动态威胁的出现，这时需要在全局参考航线的基础上适当做动态调整，以便躲避动态威胁。

目前，国内外常用的多无人机协同航路规划方法有蚁群算法、遗传算法、A^*算法等。蚁群算法具有较强的鲁棒性与良好的信息反馈能力等优点，但算法的收敛速度低且易陷入局部最优。遗传算法因其不依赖于模型特点使得算法鲁棒性强，但是对于复杂的战场环境，算法的收敛速度缓慢，导致路径搜索时间较长。A^*算法具有算法简单，易于工程师先等优点，但其算法计算量较大，规划时间较长。

发明内容

为解决现有技术中以上多无人机协同航路规划方法至少一个方面的不足。

一方面，本发明提供一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，包括如下步骤：

根据多无人机协同航路规划任务确定飞行场景中多无人机的起始点、任务目标点以及雷达威胁区域；

根据多无人机的起始点、任务目标点以及雷达威胁区域确定多无人机运动过程中所有的状态空间、动作空间以及状态转移函数；

根据马尔可夫决策过程中的状态空间、动作空间、状态转移函数与预先构造的报酬函数，构建多无人机协同航路规划任务下的马尔可夫决策过程模型；

基于预先构造的评价函数执行基于马尔可夫决策过程模型的搜索策略迭代，搜索出使评价函数值最大的动作序列，从而规划出最优多无人机协同航路。

无人机在起飞前只需加载规划出的最优多无人机协同航路即可执行协同飞行任务。

前述的一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，优选地，对无人机飞行环境进行建模，初始化任务环境，采用栅格法对无人机飞行环境进行二维空间建模，为简化模型，忽略地形障碍、恶劣天气等影响，只考虑敌方雷达威胁，飞行场景中包含多无人机的起始点，任务目标点，以及雷达威胁区域。

前述的一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，优选地，还包括搜索策略迭代过程中基于预先构造的多无人机综合航行代价函数计算多无人机综合航行代价函数值，以多无人机综合航行代价函数值最小的路径作为最优无人机协同航路；

预先设置多无人机综合航行代价函数，用以评价所规划航路的性能指标，具体步骤为：

对于单无人机来说，航路代价主要包括燃油代价、威胁代价等。而对于多无人机协同航路规划，航路代价不仅考虑单机的航行代价，还应满足多机协同航行代价。采用如下代价方程来描述多无人机的综合航行代价计算公式如下：

J_i＝W₁J_l，i+W₂J_r，i+W₃J_t (1)

式中：W₁、W₂和W₃分别为燃油代价、威胁代价以及协同代价的权重，J_l，i代表第i个航路段下航路段长度为l时的燃油代价，与无人机飞行航程有关；J_r，i代表第i个航路段下雷达威胁为r时的威胁代价；J_t为协同代价，它随着无人机飞行时间的变化而改变。根据多无人机综合航行代价函数计算公式(1)，可计算出规划后航路的综合航行代价，并选择综合航行较小的航路作为算法所规划出的最终航路，确保无人机在复杂环境下执行任务的安全性。前述的一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，优选地，其所述马尔可夫决策过程模型用马尔可夫决策过程模型(MDP)用以下四元组M＝<S，A，P，R>来表示：

S表示系统状态的有限集合，包含无人机飞行环境的有限状态点。根据步骤 S11在二维坐标系下建立无人机的环境模型，环境模型中不同坐标点代表着无人机的不同状态，而每个状态都与状态空间集合S中的一个元素相对应。

A表示无人机可用的有限动作集合。在无人机的实际飞行过程中无人机的飞行是连续的状态，但在多无人机的航路规划中，设定了各无人机的起始点和目标点之后，在路径规划过程中将无人机看作为一个质点。由于采用栅格法建立了无人机的飞行环境状态，因此在这里定义无人机有8个可执行动作， a＝1，2，3，…，8。整个360°被这些动作等分，相邻两个动作之间的角度为45°。

P为状态转移函数，表示当主体处在状态s_t时，执行动作a_t∈A，而转移到状态s_t+1的概率。状态转移概率会随着目标状态、威胁状况等发生改变。在给定无人机当前状态和执行动作的情况下，状态转移概率的分布将在很大程度上决定无人机在下一时刻的动作选择。状态转移概率可表示为：

P(s′|s，a)＝P(s_t+1＝s′|s_t＝s，a_t＝a) (2)

∑_s′∈SP(s′|s，a)＝1 (3)

其中

表示无人机的状态实例，

表示无人机动作实例，s_t表示在t时刻下无人机所处的状态，a_t表示t时刻无人机所选择的动作。

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

在目标点位置点已知时，为控制无人机朝着目标点方向移动，无人机可执行的动作有限，同时认定无人机将以较大概率朝目标点方向所在的栅格给出动作，无人机也会以一定概率进入相邻的栅格，但概率较小。当无人机处于目标点某个位置空间内时，无人机将有5个可执行动作，且每个动作概率不同，则对于8个位置空间，动作输出状态共有5×8＝40。本领域技术人员可跟根据实际任务规划无人机可执行动作的状态转移概率。

R为报酬函数，表示在给定无人机当前状态和动作的情况下所能获得的立即报酬。马尔可夫模型系统中，报酬函数是在UAV做出动作策略并与环境进行交互后由环境反馈的惩罚或奖励信号。在模型中表征着无人机在某种状态下所采取动作的好坏程度，同时也是引导无人机进行飞行决策和安全避障的重要依据。针对航路规划过程无人机的安全性和趋向目标点的问题预先对报酬函数进行设计，引入了无模型均匀结构的报酬函数模型R_movegoal和R_{avoidobstacle}。

R_movegoal为无人机正常行驶时报酬函数模型，R_{avoidobstacle}为无人机遇到威胁时报酬函数模型；

无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle} (7)。

多无人机协同航路规划中，无人机在飞行过程中会时刻受到来自雷达的威胁，基于基本马尔可夫模型算法虽能为无人机规划出有效路径，但其仍有很大概率会被雷达探测到。因此，为进一步降低无人机被雷达探测的概率，在报酬函数中提出并引入了非均匀结构的雷达威胁模型R_threat。

其中，R_threat为无人机行驶时雷达威胁报酬函数模型，对于无人机飞行时受到的雷达威胁给以负的奖赏。L为无人机做出动作决策后该航路段的长度，N为雷达威胁个数，d_k/4，i，k＝1，2，3为航路段的k/4点处与第i个雷达威胁之间的距离，无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle}+R_threat (9)。

本发明将雷达威胁代价与马尔可夫模型相结合，合理设计马尔可夫决策模型、提出了一种基于改进马尔可夫决策模型的多无人机航路规划算法。在复杂多威胁环境下，为多无人机进行飞行航路规划，不仅能为多无人机快速规划出合理有效的飞行路径，同时也大大降低了多无人机航路的威胁代价和航路综合代价，提高了无人机在复杂环境下执行任务的安全性。

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

利用最优策略π^*表示对于所有状态s∈S均存在V^*(s)＝max_πV^π(s)，最优策略π^*对应的评价函数称为最优评价函数V^*(s)。最优策略的生成过程称为策略迭代。最优策略π^*可用动态规划寻找最大奖励V^*(s)。在无限阶段折扣模型中，评价函数V^π(s)可以描述为：

其中γ为折扣因子，γ^t为t时刻折扣因子，取0.9。R_t为在t时刻所对应的报酬函数值。s为t＝0时刻无人机所对应的状态，s′为下一时刻无人机所处状态。则以递归形式可将上式重写为：

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

Q^π(s，a)＝R(s，a)+γ∑_s′∈SP(s′|s，a)V^π(s′) (12)

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

此时，MDP的最优策略π^*(s)可以表示为：

π^*(s)＝arg max_a∈AQ^π(s，a)＝arg max_a∈A{R(s，a)+γ∑_s′∈SP(s′|s，a)V^π(s′)}(13)

相应地，最优评价函数V^*(s)可以表示为：

V^*(s)＝max_a∈A{R(s，a)+γ∑_s′∈SP(s′|s，a)V^π(s′)} (14)

另一方面，本发明提供一种基于改进马尔可夫决策过程的多无人机协同航路规划装置，其特征在于，包括无人机协同系统建模模块、马尔可夫过程模型构建模块和多无人机协同航路规划模块；所述无人机协同系统建模模块，用于根据多无人机协同航路规划任务确定飞行场景中多无人机的起始点、任务目标点以及雷达威胁区域；

所述马尔可夫过程模型构建模块，用于根据多无人机的起始点、任务目标点以及雷达威胁区域确定多无人机运动过程中所有的状态空间、动作空间以及状态转移函数；根据马尔可夫决策过程中的状态空间、动作空间、状态转移函数与预先构建的报酬函数，构建多无人机协同航路规划任务下的马尔可夫决策过程模型；

所述多无人机协同航路规划模块，用于基于预先构造的评价函数执行基于马尔可夫决策过程模型的搜索策略迭代，搜索出使评价函数值最大的动作序列，从而规划出最优多无人机协同航路。

进一步地，预先构造的的报酬函数R包括无人机正常行驶时R_movegoal和无人机遇到威胁时R_{avoidobstacle}，表示如下：

R_movegoal为无人机正常行驶时报酬函数模型，R_{avoidobstacle}为无人机遇到威胁时报酬函数模型；

无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle}。

再进一步地，所述报酬函数还包括无人机行驶时雷达威胁报酬函数R_threat，表示如下：

其中，R_threat为无人机行驶时雷达威胁报酬函数；L为无人机做出动作决策后该航路段的长度，N为雷达威胁个数，d_k/4，i，k＝1，2，3为航路段的k/4点处与第i 个雷达威胁之间的距离；

无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle}+R_threat。

本发明所达到的有益技术效果：

本发明针对多无人机在复杂环境下执行作战任务时易受环境威胁影响的问题，提出了一种基于改进马尔可夫决策过程模型的多无人机航路规划算法。本发明根据多无人机协同航路规划任务确定飞行场景中多无人机的起始点、任务目标点以及雷达威胁区域；根据多无人机的起始点、任务目标点以及雷达威胁区域确定多无人机运动过程中所有的状态空间、动作空间以及状态转移函数；构造报酬函数，根据马尔可夫决策过程中的状态空间、动作空间、状态转移函数与报酬函数，构建多无人机协同航路规划任务下的马尔可夫过程模型；构建评价函数并基于评价函数执行基于马尔科夫决策的搜索策略迭代，搜索出使评价函数值最大的动作序列，从而规划出最优多无人机协同航路。

本发明还将无人机行驶时雷达威胁引入报酬函数，该算法利用离散化的雷达威胁信息，合理设计多无人机作战环境与状态空间数目；将目标点方位空间离散化，进而合理分配状态转移概率；

本发明将雷达威胁与马尔可夫决策过程模型相结合，在无模型均匀结构的报酬函数基础上提出并引入了非均匀结构的雷达威胁模型，建立改进后的马尔可夫决策过程模型；

本发明通过设置多无人机综合航行代价函数，搜索出使评价函数值最大的动作序列之后计算多无人机综合航行代价函数值，以多无人机综合航行代价函数值最小的路径作为最优无人机协同航路，不仅能为多无人机快速规划出合理有效的飞行路径，同时也大大降低了多无人机航路的威胁代价和航路综合代价，提高了无人机在复杂环境下执行任务的安全性。

附图说明

图1是本发明具体实施例的航路规划方法的算法流程图；

图2是本发明具体实施例多无人机环境模型图；

图3是本发明具体实施例无人机基本动作图；

图4是本发明具体实施例位置状态示意图；

图5是本发明具体实施例简单环境下仿真结果图；

图6是本发明具体实施例简单环境下仿真结果图，其中(a)为复杂环境下单目标仿真结果图；(b)为复杂环境下多目标仿真结果图。

具体实施方式

下面结合附图对本发明作进一步描述。以下实施例仅用于更加清楚地说明本发明的技术方案，而不能以此来限制本发明的保护范围。

如图1所示，一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，包括如下步骤：

步骤S1，根据多无人机协同航路规划任务本质，对无人机的飞行环境进行构建，并建立航路评判体系，确定飞行场景中多无人机的起始点、任务目标点以及雷达威胁区域；包括以下步骤：

对无人机飞行环境进行建模，初始化任务环境，采用栅格法对无人机飞行环境进行二维空间建模，每个栅格大小为5km，为简化模型，忽略地形障碍、恶劣天气等影响，只考虑敌方雷达威胁，飞行场景中包含多无人机的起始点，任务目标点，以及雷达威胁区域，多无人机环境模型如图2所示；

步骤S2根据多无人机的起始点、任务目标点以及雷达威胁区域确定多无人机运动过程中所有的状态空间、动作空间以及状态转移函数；

根据马尔可夫决策过程中的状态空间、动作空间、状态转移函数与预先构造的报酬函数，构建多无人机协同航路规划任务下的马尔可夫决策过程模型；

并基于预先构造的评价函数执行基于马尔可夫决策过程模型的搜索策略迭代，搜索出使评价函数值最大的动作序列，从而规划出最优多无人机协同航路。

具体包括以下步骤；

步骤S21，将雷达威胁代价与马尔可夫决策过程模型相结合，分别针对马尔可夫决策过程中的状态空间、动作空间、状态转移函数与报酬函数进行模型构建。

马尔可夫决策过程模型(MDP)用以下四元组M＝〈S，A，P，R〉来表示：

S表示系统状态的有限集合，包含无人机飞行环境的有限状态点。根据步骤 S11在二维坐标系下建立无人机的环境模型，环境模型中不同坐标点代表着无人机的不同状态，而每个状态都与状态空间集合S中的一个元素相对应。

A表示无人机可用的有限动作集合。在无人机的实际飞行过程中无人机的飞行是连续的状态，但在多无人机的航路规划中，设定了各无人机的起始点和目标点之后，在路径规划过程中将无人机看作为一个质点。由于采用栅格法建立了无人机的飞行环境状态，因此在这里定义无人机有8个可执行动作， a＝1，2，3，…，8。整个360°被这些动作等分，相邻两个动作之间的角度为45°，无人机基本动作图如图3所示。

P为状态转移函数，表示当主体处在状态s_t时，执行动作a_t∈A，而转移到状态s_t+1的概率。状态转移概率会随着目标状态、威胁状况等发生改变。在给定无人机当前状态和执行动作的情况下，状态转移概率的分布将在很大程度上决定无人机在下一时刻的动作选择。状态转移概率可表示为：

P(s′|s，a)＝P(s_t+1＝s′|s_t＝s，a_t＝a) (2)

∑_S′∈SP(s′|s，a)＝1 (3)

其中

表示无人机的状态实例，

表示无人机动作实例，s_t表示在t时刻下无人机所处的状态，a_t表示t时刻无人机所选择的动作。

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

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

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

R为报酬函数，表示在给定无人机当前状态和动作的情况下所能获得的立即报酬。马尔可夫模型系统中，报酬函数是在UAV做出动作策略并与环境进行交互后由环境反馈的惩罚或奖励信号。在模型中表征着无人机在某种状态下所采取动作的好坏程度，同时也是引导无人机进行飞行决策和安全避障的重要依据。针对航路规划过程无人机的安全性和趋向目标点的问题对报酬函数进行设计，预先构造了无模型均匀结构的报酬函数模型R_movegoal和R_{avoidobstacle}。

R_movegoal为无人机正常行驶时报酬函数模型，R_{avoidobstacle}为无人机遇到威胁时报酬函数模型。

无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle} (7)。

多无人机协同航路规划中，无人机在飞行过程中会时刻受到来自雷达的威胁，基于基本马尔可夫模型算法虽能为无人机规划出有效路径，但其仍有很大概率会被雷达探测到。因此，为进一步降低无人机被雷达探测的概率，在报酬函数中提出并引入了非均匀结构的雷达威胁模型R_threat。

其中，R_threat为无人机行驶时雷达威胁报酬函数模型，对于无人机飞行时受到的雷达威胁给以负的奖赏。L为无人机做出动作决策后该航路段的长度，N 为雷达威胁个数，d_k/4，i，k＝1，2，3为航路段的k/4点处与第i个雷达威胁之间的距离。在给定无人机当前状态s和执行动作a后，可根据无人机与目标点、障碍物之间的距离变化情况通过公式(5)～(6)确定R_movegoal和R_{avoidobstacle}，可依据无人机与雷达之间的距离关系通过公式(8)得出R_threat。无人机在状态s 下，选取动作a的所获得的报酬为：

R(s，a)＝R_movegoal+R_{avoidobstacle}+R_threat (9)

步骤S22，针对建立的马尔可夫决策过程模型，基于预先构造的评价函数执行搜索策略，搜索出使评价函数最大的动作序列。

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

利用最优策略π^*表示对于所有状态s∈S均存在V^*(s)＝max_πV^π(s)，最优策略π^*对应的评价函数称为最优评价函数V^*(s)。

最优策略的生成过程称为策略迭代。最优策略π^*可用动态规划寻找最大奖励V^*(s)。在无限阶段折扣模型中，评价函数V^π(s)可以描述为：

其中γ为折扣因子，γ^t为t时刻折扣因子，γ和γ^t取0.9。R_t为在t时刻所对应的报酬值。s为t＝0时刻无人机所对应的状态，s′为下一时刻无人机所处状态。则以递归形式可将上式重写为：

V^π(s)＝R(s，π(s))+γ∑_s′∈SP(s′|s，a)V^π(s′) (11)

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

Q^π(s，a)＝R(s，a)+γ∑_s′∈SP(s′|s，a)V^π(s′) (12)

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

此时，MDP的最优策略π^*(s)可以表示为：

π^*(s)＝arg max_a∈AQ^π(s，a)＝arg max_a∈A{R(s，a)+γ∑_s′∈S P(s′|s，a)V^π(s′)}(13)

相应地，最优评价函数V^*(s)可以表示为：

V^*(s)＝max_a∈A{R(s，a)+γ∑_s′∈SP(s′|s，a)V^π(s′)} (14)

在以上实施例的基础上，进一步地设置多无人机综合航行代价函数，用以评价所规划航路的性能指标，搜索策略迭代过程中计算多无人机综合航行代价函数值，以多无人机综合航行代价函数值最小的路径作为最优无人机协同航路；

对于单无人机来说，航路代价主要包括燃油代价、威胁代价等。而对于多无人机协同航路规划，航路代价不仅考虑单机的航行代价，还应满足多机协同航行代价。采用如下代价方程来描述多无人机的综合航行代价计算公式如下：

J_i＝W₁J_l，i+W₂J_r，i+W₃J_t (1)

式中：W₁、W₂和W₃分别为燃油代价、威胁代价以及协同代价的权重，J_r，i代表燃油代价，与无人机飞行航程有关；J_r，i为威胁代价；J_t为协同代价，它随着无人机飞行时间的变化而改变。

仿真分析：

图5是本发明具体实施例简单环境下仿真结果图；如图5所示，为在简单环境下分别利用基本蚁群算法和的基本MDP(Markov Decision Processes，马尔科夫决策过程)模型规划算法的Matlab仿真结果图，初始化相关参数：起飞点设为(4，40)，(60，5)，(90，90)，目标点设为(50，50)，雷达威胁半径统一为2，单位均为千米，雷达威胁数目为64，表2为简单环境下基本蚁群算法和基本MDP模型规划算法实验数据；从图5中可以看出，这两种算法均能规划出一条可行路径，其中实线表示基本MDP模型规划算法所规划出的可行路径，虚线表示基本蚁群算法规划出的可行路径；从表2中可以看出，在相同的目标环境下，采用基本MDP模型规划算法相比基本蚁群算法均能为无人机规划出可行路径，但基本MDP模型规划算法的路径规划时间更少、规划出的航路具有较小的威胁代价和航路综合代价。

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

实验方法	规划时间/ms	威胁代价	综合代价
				基本蚁群算法	352	470	324
基本MDP模型算法	223	358	263

图6是本发明具体实施例简单环境下仿真结果图，其中(a)为复杂环境下单目标仿真结果图；(b)为复杂环境下多目标仿真结果图。如图6所示，为在复杂环境下针对单目标和多目标任务分别利用基本MDP模型和改进后MDP模型算法(这里改进后的MDP模型算法即本发明在报酬函数中提出并引入了非均匀结构的雷达威胁模型的具体实施例)的Matlab仿真结果图，初始化相关参数：单目标任务下起飞点设为(4,40)，(60,5)，(90,90)，目标点设为(50,50)，多目标任务下起飞点设为(10,10)，(60,5)，(85,5)，目标点设为(20,80)， (50,85)，(70,85)，目标点雷达威胁半径不定，雷达威胁数目为64，表3为复杂环境下基本MDP模型算法和改进MDP模型规划算法实验数据；从表3可以看出改进后的MDP模型算法在为多无人机规划出合理有效的飞行路径的同时，也使得航路威胁代价和综合代价大大减少，提高了无人机在复杂环境下执行任务的安全性。

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

实施例：一种基于改进马尔可夫决策过程的多无人机协同航路规划装置，包括无人机协同系统建模模块、马尔可夫过程模型构建模块和多无人机协同航路规划模块；所述无人机协同系统建模模块，用于根据多无人机协同航路规划任务确定飞行场景中多无人机的起始点、任务目标点以及雷达威胁区域；

所述马尔可夫过程模型构建模块，用于根据多无人机的起始点、任务目标点以及雷达威胁区域确定多无人机运动过程中所有的状态空间、动作空间以及状态转移函数；构造报酬函数，根据马尔可夫决策过程中的状态空间、动作空间、状态转移函数与报酬函数，构建多无人机协同航路规划任务下的马尔可夫过程模型；

所述多无人机协同航路规划模块，用于构建评价函数并基于评价函数执行基于马尔科夫决策的搜索策略迭代，搜索出使评价函数值最大的动作序列，从而规划出最优多无人机协同航路。

所述马尔可夫过程模型构建模块构建的马尔可夫决策过程模型用马尔可夫决策过程模型(MDP)用以下四元组M＝〈S，A，P，R〉来表示：

S表示系统状态的有限集合，包含无人机飞行环境的有限状态点。根据步骤 S11在二维坐标系下建立无人机的环境模型，环境模型中不同坐标点代表着无人机的不同状态，而每个状态都与状态空间集合S中的一个元素相对应。

A表示无人机可用的有限动作集合。在无人机的实际飞行过程中无人机的飞行是连续的状态，但在多无人机的航路规划中，设定了各无人机的起始点和目标点之后，在路径规划过程中将无人机看作为一个质点。由于采用栅格法建立了无人机的飞行环境状态，因此在这里定义无人机有8个可执行动作， a＝1，2，3，…，8。整个360°被这些动作等分，相邻两个动作之间的角度为45°。

P为状态转移函数，表示当主体处在状态s_t时，执行动作a_t∈A，而转移到状态s_t+1的概率。状态转移概率会随着目标状态、威胁状况等发生改变。在给定无人机当前状态和执行动作的情况下，状态转移概率的分布将在很大程度上决定无人机在下一时刻的动作选择。状态转移概率可表示为：

P(s′|s，a)＝P(s_t+1＝s′|s_t＝s，a_t＝a) (2)

∑_s′∈SP(s′|s，a)＝1 (3)

其中

表示无人机的状态实例，

表示无人机动作实例，s_t表示在t时刻下无人机所处的状态，a_t表示t时刻无人机所选择的动作。

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

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

马尔可夫过程模型构建模块包括报酬函数构建模块，R为报酬函数，表示在给定无人机当前状态和动作的情况下所能获得的立即报酬。马尔可夫模型系统中，报酬函数是在UAV做出动作策略并与环境进行交互后由环境反馈的惩罚或奖励信号。在模型中表征着无人机在某种状态下所采取动作的好坏程度，同时也是引导无人机进行飞行决策和安全避障的重要依据。针对航路规划过程无人机的安全性和趋向目标点的问题对报酬函数进行设计，报酬函数构建模块引入了无模型均匀结构的报酬函数模型R_movegoal和R_{avoidobstacle}。

R_movegoal为无人机正常行驶时报酬函数模型，R_{avoidobstacle}为无人机遇到威胁时报酬函数模型；

无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle} (7)。

多无人机协同航路规划中，无人机在飞行过程中会时刻受到来自雷达的威胁，基于基本马尔可夫模型算法虽能为无人机规划出有效路径，但其仍有很大概率会被雷达探测到。因此，为进一步降低无人机被雷达探测的概率，报酬函数构建模块在报酬函数中提出并引入了非均匀结构的雷达威胁模型R_threat。

其中，R_threat为无人机行驶时雷达威胁报酬函数模型，对于无人机飞行时受到的雷达威胁给以负的奖赏。L为无人机做出动作决策后该航路段的长度，N为雷达威胁个数，d_k/4，i，k＝1，2，3为航路段的k/4点处与第i个雷达威胁之间的距离，无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle}+R_threat (9)。

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

利用最优策略π^*表示对于所有状态s∈S均存在V^*(s)＝max_πV^π(s)，最优策略π^*对应的评价函数称为最优评价函数V^*(s)。最优策略的生成过程称为策略迭代。最优策略π^*可用动态规划寻找最大奖励V^*(s)。在无限阶段折扣模型中，评价函数V^π(s)可以描述为：

其中γ为折扣因子，γ^t为t时刻折扣因子，取0.9。R_t为在t时刻所对应的报酬函数值；s为t＝0时刻无人机所对应的状态，s′为下一时刻无人机所处状态。则以递归形式可将上式重写为：

V^π(s)＝R(s，π(s))+γ∑_s′∈SP(s′|s，a)V^π(s′) (11)

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

Q^π(s，a)＝R(s，a)+γ∑_s′∈SP(s′|s，a)V^π(s′) (12) 其中，R(s，a)为无人机在状态s下，选取动作a时所获得的报酬。

此时，MDP的最优策略π^*(s)可以表示为：

π^*(s)＝arg max_a∈AQ^π(s，a)＝arg max_a∈A{R(s，a)+γ∑_s′∈SP(s′|s，a)V^π(s′)}(13)

相应地，最优评价函数V^*(s)可以表示为：

V^*(s)＝max_a∈A{R(s，a)+γ∑_s′∈SP(s′|s，a)V^π(s′)}

(14)

本发明针对多无人机协同航路规划问题的特点，针对多无人机在复杂环境下执行作战任务时易受环境威胁影响的问题，提出了一种基于改进马尔可夫决策过程模型的多无人机航路规划算法。本发明根据多无人机协同航路规划任务确定飞行场景中多无人机的起始点、任务目标点以及雷达威胁区域；根据多无人机的起始点、任务目标点以及雷达威胁区域确定多无人机运动过程中所有的状态空间、动作空间以及状态转移函数；构造报酬函数，根据马尔可夫决策过程中的状态空间、动作空间、状态转移函数与报酬函数，构建多无人机协同航路规划任务下的马尔可夫过程模型；构建评价函数并基于评价函数执行基于马尔科夫决策的搜索策略迭代，搜索出使评价函数值最大的动作序列，从而规划出最优多无人机协同航路。

为进一步降低无人机被雷达探测的概率，在报酬函数中提出并引入了非均匀结构的雷达威胁模型，本发明将雷达威胁代价与马尔可夫模型相结合，合理设计马尔可夫决策模型、提出了一种基于改进马尔可夫决策模型的多无人机航路规划算法。在复杂多威胁环境下，为多无人机进行飞行航路规划，仿真结果表明，基于改进马尔可夫决策模型的多无人机航路规划不仅能为多无人机快速规划出合理有效的飞行路径，同时也大大降低了多无人机航路的雷达威胁代价和航路综合代价，提高了无人机在复杂环境下执行任务的安全性。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、 CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和 /或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/ 或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

以上结合附图对本发明的实施例进行了描述，但是本发明并不局限于上述的具体实施方式，上述的具体实施方式仅仅是示意性的，而不是限制性的，本领域的普通技术人员在本发明的启示下，在不脱离本发明宗旨和权利要求所保护的范围情况下，还可做出很多形式，这些均属于本发明的保护之内。

Claims (10)

1.一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，其特征在于，包括如下步骤：

根据多无人机协同航路规划任务确定飞行场景中多无人机的起始点、任务目标点以及雷达威胁区域；

根据多无人机的起始点、任务目标点以及雷达威胁区域确定多无人机运动过程中所有的状态空间、动作空间以及状态转移函数；

根据马尔可夫决策过程中的状态空间、动作空间、状态转移函数与预先构建的报酬函数，构建多无人机协同航路规划任务下的马尔可夫决策过程模型；

基于预先构建的评价函数执行基于马尔可夫决策过程模型的搜索策略迭代，搜索出使评价函数值最大的动作序列，从而规划出最优多无人机协同航路。

2.根据权利要求1所述的一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，其特征在于，所述方法还包搜索策略迭代过程中基于预先构建的多无人机综合航行代价函数计算多无人机综合航行代价函数值，以多无人机综合航行代价函数值最小的路径作为最优无人机协同航路；

所述多无人机综合航行代价函数计算公式如下：

J_i＝W₁J_l，i+W₂J_r，i+W₃J_t

式中：J_i为第i个航路段下的多无人机综合航行代价，W₁、W₂和W₃分别为燃油代价、威胁代价以及协同代价的权重，J_l，i代表第i个航路段下航路段长度为l时的燃油代价；J_r，i代表第i个航路段下雷达威胁为r时的威胁代价；J_t为协同代价。

3.根据权利要求1所述的一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，其特征在于，所述马尔可夫决策过程模型用以下四元组M＝<S，A，P，R>来表示：

S表示系统状态的有限集合，包含无人机飞行环境的有限状态点；

A表示无人机可用的有限动作集合；

P为状态转移概率函数，表示当主体处在状态s_t时，执行动作a_t∈A，而转移到状态s_t+1的概率；

R为报酬函数，表示在给定无人机当前状态和动作的情况下所能获得的立即报酬。

4.根据权利要求3所述的一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，其特征在于，状态转移概率函数表示为：

P(s′|s，a)＝P(s_t+1＝s′|s_t＝s，a_t＝a)

其中

表示无人机的状态实例，

表示无人机动作实例，s_t表示在t时刻下无人机所处的状态，a_t表示t时刻无人机所选择的动作。

5.根据权利要求1所述的一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，其特征在于，报酬函数R包括无人机正常行驶时报酬函数R_movegoal和无人机遇到威胁时报酬函数R_{avoidobstacle}，表示如下：

无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle}。

6.根据权利要求5所述的一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，其特征在于，所述报酬函数还包括无人机行驶时雷达威胁报酬函数R_threat，表示如下：

其中，L为无人机做出动作决策后该航路段的长度，N为雷达威胁个数，d_k/4，i，k＝1，2，3为航路段的k/4点处与第i个雷达威胁之间的距离；

无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle}+R_threat。

7.根据权利要求1所述的一种基于改进马尔可夫决策过程的多无人机协同航路规划方法，其特征在于，所述预先构建的评价函数V^π(s)表示为：

V^*(s)＝max_a∈A{R(s，a)+γ∑_s′∈SP(s′|s，a)V^π(s′)}

(11)

其中V^*(s)表示最优策略π^*对应的评价函数称为最优评价函数；A表示无人机可用的有限动作集合；R(s，a)为无人机在状态s下，选取动作a的所获得的报酬函数值；γ为折扣因子，V^π(s′)为策略π下状态s′的评价函数；

表示无人机的状态实例，

表示无人机动作实例，P(s′|s，a)为状态转移函数。

8.一种基于改进马尔可夫决策过程的多无人机协同航路规划装置，其特征在于，包括无人机协同系统建模模块、马尔可夫过程模型构建模块和多无人机协同航路规划模块；所述无人机协同系统建模模块，用于根据多无人机协同航路规划任务确定飞行场景中多无人机的起始点、任务目标点以及雷达威胁区域；

所述马尔可夫过程模型构建模块，用于根据多无人机的起始点、任务目标点以及雷达威胁区域确定多无人机运动过程中所有的状态空间、动作空间以及状态转移函数；根据马尔可夫决策过程中的状态空间、动作空间、状态转移函数与预先构造的报酬函数，构建多无人机协同航路规划任务下的马尔可夫决策过程模型；

所述多无人机协同航路规划模块，用于基于预先构建的评价函数执行马尔可夫决策过程模型的搜索策略迭代，搜索出使评价函数值最大的动作序列，从而规划出最优多无人机协同航路。

9.根据权利要求8所述的一种基于改进马尔可夫决策过程的多无人机协同航路规划装置，其特征在于，预先构造的报酬函数R包括无人机正常行驶时报酬函数R_movegoal和无人机遇到威胁时报酬函数R_{avoidobstacle}，表示如下：

无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle}。

10.根据权利要求9所述的一种基于改进马尔可夫决策过程的多无人机协同航路规划装置，其特征在于，所述报酬函数还包括无人机行驶时雷达威胁报酬函数R_threat，表示如下：

其中，L为无人机做出动作决策后该航路段的长度，N为雷达威胁个数，d_k/4，i，k＝1，2，3为航路段的k/4点处与第i个雷达威胁之间的距离；

无人机在状态s下，选取动作a的所获得的报酬函数R(s，a)表示如下：

R(s，a)＝R(s，a)＝R_movegoal+R_{avoidobstacle}+R_threat。

Images