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

舰载机的调度能力是舰载机出动与回收能力的重要基础，但调度方案受到有限舰面空间的严重制约，但调度方案受到有限舰面空间的严重制约，必须进行合理调度路径规划，以减少舰载机群调度时间，提高机群调度效率[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<N)。为满足甲板上舰载机群路径规划需要，必须尽可能减少单机最大的调度时间。将其作为优化机群调度的目标函数，我们定义不同飞机在其初始位置开始移动的时间为FTi(0)，1≤i≤N，经过移动的完整路径后设飞机到达目的位置的时间为FTi(r)，1≤i≤N，FTi(r)包含飞机Agent移动、等待以及起飞在内所有时间。因此，飞机调度过程中权重α1，α2设置以及飞机冲突解决策略会对FTi(r)产生影响。此外，整个规划应实现目标函数F的最优值为：

多机多点的调度环境下，调度过程需满足一些约束条件，包括飞机调运最大速度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.1.2 空间Agent的基本属性描述

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

1)空间Agent的位置

式(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的邻居集合为：

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

2.2 飞机Agent

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

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

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

式(6)中：

为第i个飞机Agent在第k+1栅格上的状态；

表示该飞机在第k个栅格上的状态；wk为该飞机的控制函数，为

第j个飞机在第l个栅格上的状态；pstart，pend表示该飞机在初始和目标位置时的状态。

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

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

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

1)同一空间Agent碰撞，即两个飞机Agent在同一时间内移动到同一个空间Agent，即

2)飞机Agent移动到固定障碍物处，即

3)两个飞机Agent正面相撞，其下一个路径点是彼此当前所在的空间Agent位置，即

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

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

3.1 代价函数

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

式(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)中：[xk,yk]T、[xk+1,yk+1]T分别为当前空间Agent位置坐标和下一路径点(邻居集要素)的位置坐标。满足式(9)不等式的空间Agent构成备选空间Agent集Selected(Ai)=

解集包含所有的飞机Agent可以到达的下一个空间Agent。

2)在Selected(Ai)中，明确各个空间Agent的状态属性

剔除

的备选空间Agent。根据当前飞机Agent所在的位置进行以下判定：

θ(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(φ,θ)是φ,θ的函数，可表示为：

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

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

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

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

如一个空间Agent的状态值

将其作为备选空间集要素。对于动态碍物的避障策略可以采用等待或绕行策略，定义

为空间Agent的临时占用状态，并在一段时间t后变为可用状态。若某飞机Agent所在空间Agent为

则

经过式(11)计算后选择的空间Agent为

时，应首先选择等待策略，并针对以下两种情况进行处理：

1)若

所在的飞机Agent经过算式(11)得出的空间Agent不是

即两个飞机Agent产生了冲突,则

所在的飞机Agent在

所在的飞机Agent移动并释放

后移动至

2)若

所在的飞机Agent经过算式(11)得出的空间Agent是

则

所在的飞机应先执行绕行策略，待其释放

后，

所在的飞机移动至

在这种情况下，

的飞机Agent最先执行空间Agent选择算法，因此优先级高，需要别的飞机Agent为其释放空间资源。

3.2 算法的执行过程

基于两类Agent的飞机路径规划规则，给出机群基于A*算法的启发式路径规划算法的执行过程如图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时刻。

以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)-

全部机群路径规划结果如表2所示。

在本次仿真中，从第一架飞机开始到最后一架飞机完成起飞所花费的总时间为658 s，这一结果说明本文所构建的模型是合理可行的。

5 结论

1)在机群路径规划的研究中，要考虑舰载机的空间特征对机群调度的影响。

2)利用正六边形对机群调运的空间环境进行栅格建模，并确定空间环境Agent和飞机Agent。

3)考虑机群调度中的碰撞问题，引入等待策略和绕行策略对机群路径规划的影响，并利用改进A*算法对飞机Agent 的调度路径进行规划，实现了机群调度的全局最优。

本文中的研究仍需要进一步深化，例如可以对舰面环境进行更精确的建模，从而实现路径规划的更优性研究。

[1] 张智,林圣琳.运动学约束的不规则目标遗传避碰规划算法[J].航空学报,2015,36(4):1348-1358.

[2] 冯强,曾声奎,康锐.不确定条件下舰载机动态调度仿真与优化方法[J].系统仿真学报,2009,30(11):2119-2125.

[3] WU Y,QU X.Obstacle Avoidance and Path Planning for Carrier Aircraft Launching[J].Chinese Journal of Aeronautics(S1000-9361),2015,28(3):695-703.

[4] 潘莹，陈家琪.基于Multi—Agent仿真的动态车辆路径算法研究[J].信息技术,2015,32(5):121-124.

[5] AN J X,WANG W X,LIU Z,ZHANG J Q.A Route Planning Method Based on the Airspace Divided by Grid Method[J].Advanced Materials Research(S1662-8985),2014,1073-1076:2381-2384.

[6] ZHANG Z，ZHAO Z.A Multiple Mobile Robots Path planning Algorithm Based on A-star and Dijkstra Algorithm[J].International Journal of Smart Home(S1975-4094),2014,8(3):75-86.

[7] 曹畔畔,罗长远.多态加权k/N系统可用度动态评估模型[J].系统工程,2015,33(3):143-148.

[8] 李楠,赵擎.基于A*算法的机场滑行路径优化研究[J].计算机仿真,2012,29(7):88-92.

[9] KOPRIVA S,SISLAK D.Iterative Accelerated A* Path Planning[J].49th IEEE Conference on Decision and Control December,2010.

[10] 王宇,陈海涛,李煜,等.基于Grid-GSA算法的植保无人机路径规划方法[J].农业机械学报,2017,48(7):29-37.

[11] ZHANG Z，ZHAO Z.A Multiple Mobile Robots Path planning Algorithm Based on A-star and Dijkstra Algorithm[J].International Journal of Smart Home,2014,8(3):75-86.

[12] 陈海,何开锋,钱炜祺.多无人机协同覆盖路径规划[J].航空学报,2016,37(3):928-935.

[13] 葛媛媛,张宏基,唐虹.粒子群优化算法融合行为动力学的路径规划方法研究[J].机械科学与技术,2018,37(2):244-249.

[14] TUNCER A.Dynamic path planning of mobile robots with improved genetic algorithm[J].Computers and Electrical Engineering,2012,38:1564-1572.

[15] RATH M K,RYANA J C,CUMMINGS M L.Design an interactive local and global decision support system for aircraft carrier deck scheduling[C]//Proceedings AIAA Infotech,2011:1516.

[16] 刘铭,徐杨.基于Multi-Agent系统的多飞行器协同路径规划方法的研究[J].计算机科学,2012,39(1):219-222.

[17] 王国庆.舰载机甲板调度路径优化方法研究[D].哈尔滨:哈尔滨工程大学,2012.

[18] KIM D.An Approach to Multi-agent Interactive Control in an Intelligent Space[J].International Journal of Control,Automation,and Systems(S1598-6446),2015,13(3):697-708.

[19] FENG Q,LI S,SUN B.A Multi-Agent Based Intelligent Configuration Method for Aircraft Fleet Maintenance personnel[J].Chinese Journal of Aeronautics(S1000-9361),2014,27(2):280-290.

[20] 尤杰,韩松臣.基于多Agent的机场场面最优滑行路径算法[J].交通运输工程学报,2009,9(1):109-112.

[21] 朱庆保,张玉兰.基于栅格法的机器人路径规划蚁群算法[J].机器人,2005,27(2):132-136.

[22] 王沛栋,冯祖洪.基于栅格模型机器人路径规划的改进蚁群算法[J].计算机应用与软件,2009,26(10):107-110.

[23] 林辉.地理信息系统中栅格单元大小与形状[J].中南林业科技大学学报,2000,20(1):93-93.