基于空间Agent的舰载机群调度路径规划

2020-04-22张鹏翼黄百乔崔博文

兵器装备工程学报 2020年3期

张鹏翼,黄百乔,崔博文

(1.中国船舶工业系统工程研究院，北京 100036；2.北京航空航天大学可靠性与系统工程学院，北京 100191)

舰载机的调度能力是舰载机出动与回收能力的重要基础，但调度方案受到有限舰面空间的严重制约，但调度方案受到有限舰面空间的严重制约，必须进行合理调度路径规划，以减少舰载机群调度时间，提高机群调度效率[1-6]。

目前应用较为广泛的算法包括A*搜索算法[7-9]、引力搜索算法[10]、Dijkstra算法[11]、模拟退火算法[12]、遗传算法[13]、粒子群优化算法[14-15]、Multi-agent协同路径规划[16]，以及随机生成树等方法[17]。

一些研究将舰载机视为质点，未考虑调度路径的干涉问题，这导致路径可执行性下降。常见的解决方案是按圆形、多边形等几何形状对实体和障碍物进行抽象，通过检测距离实现碰撞检测[18]。

Multi-Agent在群体路径规划方面已有很好的应用，且Agent技术可支持对Agent外形尺寸的描述。为此，本文拟基于Multi-agent技术，考虑空间约束以及避障等需求，通过改进的A*算法研究舰载机群多机协同路径的联合规划问题[4，19-20]。

1 机群路径规划过程

舰载机群的调度过程是舰载机在各个机务站位从规定位置或给定位置到达指定机务站位的过程。以起飞调度过程为例，其基本情况如图1所示。

本文考虑一个包含N架次舰载机的机群编队，可用起飞站位的数量为M(M

(1)

多机多点的调度环境下，调度过程需满足一些约束条件，包括飞机调运最大速度v、飞机起飞位上的最长占用时间为TD、飞机调度中飞机的偏转角的最大值Ψ。

同时，在机群调度的过程中，应避免干涉，包括两类：即飞机与固定障碍物的静态干涉、两架飞机同时移动时发生的动态干涉。为此给出飞机的最小安全距离d。

2 基于Multi-Agent的舰载机调度问题建模

2.1 空间环境Agent

2.1.1空间栅格模型

栅格法[21-22]是路径规划中常用的环境建模方法，本文借助栅格法对航母舰面环境进行建模。由于正六边形栅格具有步间转角适当、障碍物覆盖能力强等优点[23]，本文采用正六边形栅格对空间环境进行分割，空间栅格模型如图2所示。栅格数量为m×n个，每个栅格的编号分别用二维坐标(i,j)来表示，其中i表示行坐标、j表示列坐标。每个栅格可按两种状态进行初始化，0表示该栅格被占用、1表示该栅格未被占用。划分的栅格覆盖所有有效的舰面空间范围。

在此基础上，给出一种考虑安全碰撞距离的栅格尺寸的界定方式。调度过程中，飞机作为不规则形状，可以简化为一个包络圆形，设半径为R。已知飞机的安全碰撞距离为d，飞机的中心位置为Oi，则飞机与障碍物的距离应满足d(O1O2)>2R+d。栅格划分规则为：(1)以O1，O2为圆心，以(R+d/2)为半径对两圆进行扩展，形成两个相切圆；(2)分别作两个圆的外接六边形，单个栅格形状为相切圆的外接六边形。则可以计算出边长为：

(2)

2.1.2空间Agent的基本属性描述

将每个离散的栅格抽象为空间Agent，并对空间Agent的基本属性进行如下描述。

1)空间Agent的位置

L={I/I=[x,y]T, 0≤x≤X, 0≤y≤Y}

(3)

式(3)中：X,Y分别表示整个空间行坐标与列坐标的最大值。空间Agent依据位置设定优先级，假设跑道位置上的优先级低。

2)空间Agent的状态集

设置C={-1,0,1}三种状态，-1表示固定占用空间，该空间的状态为一直不可用；0表示临时占用，并假设该空间在有限的时间t后可变为可用状态；1表示该空间可用。

3)空间Agent的邻居

每个栅格都至少与一个其他栅格相连接，定义空间Agent邻居，Lk(xk,yk)表示某一空间Agent的位置，Lk+1(xk+i,yk+i)表示该空间Agent的邻居坐标，则该空间Agent的邻居集合为：

(4)

在整个机群的路径规划中，飞机所经过的空间Agent连接关系构成了飞机Agent移动的路径。

2.2 飞机Agent

定义飞机Agent集Ω，且每个飞机Agent在任意空间中的状态为：

p=〈A,θ,v〉

(5)

式(5)中：A表示飞机的位置，A应满足与某个空间Agent的位置重合；θ表示为当前位置距离目标位置偏角；v为考虑方向的飞机移动速度，其方向为η。

定义飞机Agent在某一k栅格时的状态为pk={Ak,θk,vk}∈P，其中P为np维度的状态空间；飞机Agent选择空间Agent的控制函数为wk=g(v,ψ,d,ω)，wk体现了根据飞机Agent转移时的速度、偏转角、安全距离及目的角度等参数作为飞机Agent决策指标。飞机动态路径规划问题可以描述为以下状态方程，即：

(6)

飞机Agent运动行为学状态图见图3。飞机调度至目标位置的行为可用飞机Agent距离目标位置的偏离函数fgoal表示，fgoal越大越不利于靠近目标位置，fgoal可表示为：

fgoal(Ai)=α1θ(Ai)+α2φ(Ai)

(7)

式(7)中：θ(Ai)表示飞机Agent在位置Ai时距离目标位置G的角度；φ(Ai)表示该飞机Agent在位置Ai时的运动方向与飞机目的位置方向的偏差，且φ(Ai)=η(Ai)-ω；α1，α2表示飞机Agent的两个偏移角度要素对其奔向目标的作用权重，且α1+α2=1。

图3 飞机Agent运动行为学状态图

飞机在路径规划中存在的3种干涉情况：

飞机Agent在对下一个空间Agent进行搜索时，可实现障碍探测距离不小于(2R+d)，这样可以保证飞机提前转变移动方向，避免与障碍物相撞。

3 基于改进A*算法的舰载机Agent协同路径搜索算法

3.1 代价函数

定义如下的机群单架飞机路径规划的代价函数f为：

f(Ai)=g(Ai)+fgoal(Ai)

(8)

式(8)中：g(Ai)是飞机Agent移动到Ai位置实际花费时间；fgoal(Ai)是飞机Agent距离目标位置偏离函数，可以将其作为飞机Agent搜索下一个空间Agent的启发式函数。

飞机Agent与空间Agent的交互规则如下：

规则1：空间Agent选择规则。

1)飞机Agent在接到任务后，需要从其当前所属空间Agent的邻居集合Neighbor(Ai)中选择下一个路径点，Ai表示飞机Agent当前位置；在控制函数wk=g(v,ψ,d,ω)的约束下，应满足:

(9)

θ(Ai)>90°时，表示飞机在目标位置的前方，因此应设定α1占较大比重，且移动后方向为φ(Ai+1)=min{θ(Ai)，φ(Ai)+Ψ}，从而保证飞机Agent从正向移动至目标位置，提高规划的成功率。

θ(Ai)≤90°，φ(Ai)≥90°时，表示飞机在向远离目标位置的方向移动，因此，应设定α2占大比重，且移动后的方向为φ(Ai+1)=min{θ(Ai)，φ(Ai)-Ψ}从而使得飞机能够改变移动方向，向目标位置移动。

θ(Ai)≤90°，φ(Ai)≤90°时，表明飞机Agent正在向目标位置移动，可设置α1，α2均衡比重，且移动后的方向为φ(Ai+1)=min{θ(Ai)，φ(Ai)-Ψ}，保障飞机平稳向目标移动。

在飞机Agent的单次规划距离2R+d内，飞机可以到达所有Selected(Ai)中的位置。假设飞机Agent从当前位置到Selected(Ai)中每个空间Agent所经历的时间T(φ,θ)是φ,θ的函数，可表示为：

(10)

由于它对飞机Agent移动时间产生影响，fgoal是影响飞机Agent选择空间Agent的另一要素，因此，定义：

ming(Ai+1)+fgoal(Ai+1)

(11)

式(11)是飞机Agent选择下一个空间Agent的依据，其中g(Ai+1)=g(Ai)+T(φ,θ)，fgoal(Ai+1)是飞机Agent在Selected(Ai)中每个空间Agent上距离目标位置G的偏差函数。

代价函数的值相等时，应遵循先入为主的优先原则以及空间Agent的优先级顺序。

规则2：空间Agent冲突解决规则。

3.2 算法的执行过程

基于两类Agent的飞机路径规划规则，给出机群基于A*算法的启发式路径规划算法的执行过程如图4所示。

图4 机群路径搜索算法执行过程

本方法将Agent之间的协商过程融入到路径A*算法的实现过程中，可有效地解决机群多机同时调度的碰撞问题。

4 仿真案例

假设航母舰面的飞行甲板为斜直两段式甲板，尺寸约为330 m×80 m，舰载机的尺寸为20 m×15 m(展翼状态)，如图1所示。以舰载机作战的典型任务模式连续出击为例。假设机群某波次任务需出动10架次飞机，这些飞机需要从初始停放位置调度到弹射起飞的准备位，并要求机群调度过程为并行作业。

每个飞机初始位置、飞机朝向、目标位置等相关参数如表1所示，表1中包含了每架飞机的调度开始时间和目标位置信息。设飞机调度过程最大转角度为60°，最高速度为1.5 m/s，最小安全距离为2 m，飞机起飞位上的准备时间为服从N-(1.8,0.52)的正态分布，定义起飞任务开始的时刻为0时刻。

表1 机群飞机相关参数

以A3和A4飞机调度过程对机群路径规划进行说明，其中的避碰实现过程如图5所示。在第191 s时，A3调用空间Agent选择模块，并根据算法选择了位置(745,171)的空间Agent，并发现该点已经被A4飞机临时占用，因此A3选择了等待策略，直到A4释放了该点之后，才完成了移动。飞机A3和飞机A4的路径节点分别为:

A3:(690,76)-(745,171)-(800,226)-(910,226)-

(1 020,226)-(1 130,226)-(1 240,226);

A4：(415,171)-(525,171)-(635,171)-

(855,171)-(965,171)-(1 075,171)-

(1 185,171)