基于改进SARSA算法的航空器滑行路径规划

张云景，王 昊，王 帅，孟 斌

(1.郑州航空工业管理学院民航学院，河南 郑州 450046;2.河海大学，江苏 南京 211100）

0 引 言

航空器滑行路径规划是建设智慧机场的重要一环，也是保证航空器在机场安全高效运行的核心，但我国在智慧机场建设方面仍处于起步阶段，国内大多数机场仍在使用传统的人工机坪管制方法。传统的人工调度成本高昂，效率低下，而利用计算机辅助的场面滑行路径规划可以更加清晰地建立和实施场面滑行计划，对建设智慧机场和绿色机场具有重要意义。

场面航空器滑行路径规划问题是一个研究热点，早有学者对此进行了相关研究。路径规划可分为静态路径规划和动态路径规划，传统算法可以满足静态路径规划要求，而动态路径规划则需对算法进行改进。李志龙［1］考虑将航空器冲突热点加入路径规划的约束条件，提出了一种基于冲突热点等级划分的动态路径规划算法。当场面冲突等级值相加高于最低阈值时，使用改进的Q-learning 路径规划算法进行路径规划，否则采用改进的A*路径规划算法。当航空器在滑行中感知到冲突时，则使用Q-learning算法进行路径调整。王玉婷［2］改进了传统的Dijkstra算法，引入了静态路径库的预先选定，并将其作为动态规划路由路径的一种可行方案，从而获得最优路由路径。冯广洪［3］建立了航空器地面滑行路径多目标优化模型，以机场航空器地面滑行总时间最少和航空器滑行油耗最小为最优目标，并采用多目标A*算法对模型进行求解验证。刘成［4］在基于Petri 网模型的基础上，将遗传算法与Petri 融合，有效地对进离港滑行路径进行合理规划。邱梦琦［5］在航班滑行路径规划中，进一步利用Petri 网模型，并结合启发式算法和模拟退火算法，进行滑行路径的优化。Kawabe Tomoya［6］提出了结合强化学习算法和A*算法的灵活路径规划方法，该方法使用Q-learning 算法来避免冲突，使用有限状态空间的离线学习来缩短总的学习时间。每个智能体都使用A*算法独立寻找最短路径，并利用Q学习来避免碰撞。

强化学习无须完善的先验知识，航空器面对陌生的机场场面环境能够通过与环境的动态交互自主获得最佳决策行为。因此，基于强化学习的场面航空器滑行系统，能减少飞机的运行成本，提高机场的资源利用率以及确保外界环境的安全，同时，还有助于减少对环境的污染。本文针对新郑机场进离港航空器路径规划进行研究，构建基于改进SARSA算法的路径规划方法。仿真结果表明改进的SARSA 算法收敛速度更快，能够为航空器滑行规划出安全路径。

1 模型构建

1.1 问题描述

静态规划问题被表述为整数规划问题。在解决航空器静态路径规划时，首先要给定参数，它是由初始节点组成的一组任务集合Rr和目标节点集合Mr组成。对于任务r，需要考虑场面系统布局G=（V，E），以及航空器集和H。其中二进制变量为，它表示当航空器k在时间t从栅格i移动到栅格j时取1，否则取0。

该静态问题的目标是最小化滑行时间σk,r，其定义为航空器k执行滑行任务r从初始栅格Rr到目标栅格Mr的时间，如果航空器k从开始Rr到达目标栅格Mr则取1，否则为0。该规划目的在于为航空器找到一条无冲突的路线。以下为最小化目标函数。

其中，k代表航空器索引，r代表航空器滑行任务，可由下面的公式表示，N是所有可以从栅格i移动的所有栅格的集合。

式（2）表明航空器任务r的滑行时间等于后面变量的时间总和，该变量在任务未完成时为1，否则为0。式（3）确保一旦航空器k从初始点启动变量取1。式（4）要求航空器k未到达目标栅格Mr则满足δk,r,t≤δk,r,t+1。由式（5）可知，当航空器k到达目的地时δk,r,t取0。

每架航空器的滑行满足下列限制：

约束式（6）和式（7）由环境限制，表明航空器能从i栅格滑行到任意可以到达的栅格且在一定的时间内航空器只能出现在一个栅格。式（8）和式（9）分别表示避免航空器之间的碰撞和禁止同时在一个滑行道滑行。

1.2 机场环境建模

机场环境建模是航空器滑行路径规划的核心。建模时，将机场环境信息抽象化为模型化信息，从而将场面环境划分为可滑行区域和不可滑行区域［7]，栅格化地图是研究路径规划的常用方法之一。栅格化可以确保连续的路径离散化为对栅格的选择，且离散化后的信息方便储存和维护。本文采用栅格法对机场环境建模，具体情况如下。

结合机场图，采用20*20 的栅格对机场环境进行仿真，采用二维直角坐标或一维坐标均可确定航空器的空间位置，并对每个栅格从下往上、从左至右分别标号得到400个栅格，每个栅格的标号可作为其位置坐标。图1 为二维环境矩阵，图2 为机场道面栅格化处理图。

图1 二维环境矩阵

图2 机场道面栅格化处理图

综合以上，栅格地图用于路径规划有以下好处：

（1）可以将任意形状轮廓的地图，用足够精细的栅格进行绘制。

（2）每一个栅格，可以通过不同颜色表征不同含义，如黑色代表障碍物、白色代表滑行道。

（3）基于栅格的机场地图进行路径规划，有横、纵、斜三个规划方向，对于场面滑行的低速航空器（一般为5 海里/小时—20 海里/小时海里/小时）完全可以按照规划路径滑行。

2 SARSA学习算法的改进

2.1 SARSA学习算法

强化学习是从环境状态到动作映射的机器学习方法［8］，目的是基于与环境的交互来自主地学习如何做出正确的决策，以最大化预期的累积回报。在强化学习算法中，SARSA 算法是一种经典的在线学习算法，该算法的主要思想是在每个状态下，根据当前动作和即将采取的动作来更新，SARSA 算法的迭代更新公式为：

其中，Q(s,a)为状态—动作函数，表示在s状态下采取动作a的价值；s为状态；a为选择的动作；α为学习率，表示每轮更新的步长；r为奖励信号，表示智能体在采取动作后经环境反馈获得的奖励；γ为折扣因子，表示未来奖励的重要性，使得智能体更倾向于选择长期的奖励；Q(s',a')为状态—动作函数的下一个状态和动作，即在下一个状态下选择下一个动作的预期价值［9］。

按照上述迭代更新公式，智能体会不断与环境交互，更新Q表中的值，最终智能体可按照Q表根据ε-greedy 策略来进行动作决策。该策略设定动态因子ε，ε∈(0，1)代表了航空器拥有ε的概率值，将会在滑行状态中选择当前Q表中奖励较大的动作，1-ε 的概率值会选择Q表中除最大分值外的其他动作［10］。

因此当ε 较大时，智能体倾向于考虑当前状态下的奖赏值，算法收敛得较慢，训练效率较低，随着训练的进行，可按照预定的步长或时序进行调整。对于其他参数的取值，要根据实际情况经过探索最终确定。表1 为3 个状态、2 个动作的Agent 生成的Q表示例。

表1 Q表

为使SARSA 算法顺利更新，需要设置合适的奖赏集合r，常用末状态奖励函数下，当智能体在达到目标时所获得的奖励值为1，其他状态的奖励值为0［11］。在机场滑行道上，航空器从起始栅格开始滑行时存在某一栅格突然出现障碍物的情况，假设航空器需要经过30 个栅格到达目标栅格，每走一步均可做8种选择,因此30 步可做出的选择总数为830，如果采用末状态奖励函数设置奖赏，则意味着在每次学习迭代时都需要重新计算奖励值，会使得SARSA 算法在处理长时间任务时复杂度提高，从而导致算法收敛困难。

2.2 改进的SARSA算法分析

本节讨论将模拟退火算法的策略思想应用于SARSA 算法的策略选择中。模拟退火算法是一种全局优化算法，其基本思想是将问题看作随机热力学系统，在系统达到平衡的过程中，利用温度控制的随机扰动方法，慢慢降低温度，以一定概率接受劣解，从而逐步趋近于全局最优解。算法的具体步骤如下：

（1）设定初始状态和初始温度。

（2）在每个温度下，随机产生一个新的状态，并计算新状态的代价函数。

（3）判断是否接受新状态：若新状态代价函数比当前状态更优，则接受新状态。若新状态代价函数较劣，则以一定的概率接受新状态，概率由Metropolis准则来决定，即p=e(-ΔE/T)，其中ΔE为新旧状态的代价函数差值，T为当前温度。

（4）降温，调整温度参数，进入下一轮循环。

（5）当温度达到最低温度时停止算法［12］。

由以上步骤可知，模拟退火算法并非全盘否定较劣的策略，因此可以避免陷入局部搜索，进而得到全局最优解。

本文所提出的基于模拟退火策略的SARSA 算法，将上述思想融入SARSA 算法中。模拟退火策略步骤如下：

(1）生成一个随机数λ；

(2）在温度T时刻，计算随机动作a的接受概率

(3)策略判断做出选择：若e(Q(s',a')-Q(s,a))/T＞λ，则随机选择一个动作，反之选择动作arg maxQ(s,a)；

(4）判断是否至冷却状态，若至冷却状态，则T=Tmin［13］。

基于模拟退火策略的SARSA 算法通过温度参数控制策略进行选择，增加了搜索空间，提高了局部搜索能力。温度参数随着迭代次数的增加而不断降低，最终可以得到全局最优解。此外，模拟退火策略采用的是基于误差平方和的奖励函数，具有较好的收敛性和泛化性能。在更新Q值时，根据当前状态、动作和下一个状态的奖励值来进行更新，以获得更好的学习效果。

基于模拟退火策略的SARSA 算法流程的步骤如下：

步骤一：初始化参数。包括初始温度、最终温度、温度下降率、可接受解的概率等参数。

步骤二：初始化状态和动作。根据实际问题的需要，给定初始状态和动作。

步骤三：迭代过程。进行多轮迭代，每一轮都根据当前状态与动作更新Q值，并基于模拟退火策略选择下一个状态和动作。

步骤四：更新Q值。根据当前状态、动作和下一个状态的奖励值来更新Q值，使其逐步趋向全局最优解。

步骤五：修改温度和可接受解的概率。随着迭代次数的增加，不断降低温度并逐渐收缩可接受解的概率，以逼近最优解。

步骤六：判断是否收敛。如果满足停止条件，算法结束；否则，回到第3步继续迭代。

综上，基于模拟退火的SARSA 算法可以在搜索解空间时跳出局部最小值，从而有更大机会找到全局最优解，并且在多轮迭代中状态随机生成，因此可以在一定程度上探索状态空间中的各种状态。考虑到该算法率分布更加稳定，因此它能够适应复杂变化的机场场面环境。

3 实验及结果分析

3.1 分析思路

为验证整个算法的可行性和规划效果，本研究使用了新郑机场滑行道实际道面网络，对该机场进离港航班分别使用SARSA 算法和改进的SARSA 算法进行路径规划，比较不同情况下两种算法的优劣。

3.2 算法设置

基于上文构建的模型环境进行仿真验证，根据先验知识，并结合机场栅格环境，将航空器当前所在栅格作为初始状态，航空器分为8个运动方向，如图3所示。

图3 智能体搜索方向示意图

为方便表示奖赏函数r，假设目标栅格位于航空器当前栅格正前方，将航空器选择方向从正前方按顺时针分别标号为{1，2，3，4，5，6，7，8}；将SARSA 算法参数进行设置，其中学习率α为0.8，折扣因子γ为0.95，动态因子ε 为0.9，则奖赏函数r可表示为：每进行一次环境交互做出动作奖励值为r=-1，到达目标栅格的奖励值r=100，仿真模拟退火参数设置为：初始温度T=300，降温速率v=0.95，常温Tmin= 10-8［14］。

3.3 实验结果与分析

由栅格仿真环境和设置的算法参数对改进的SARSA 算法和传统SARSA 算法进行对比，智能体的总收益为每一栅格收益之和。图4 是航空器仿真运行后的迭代结果图，本次实验选择迭代次数为400，也就是智能体在规划出400 条路径后将会结束搜索行为［15］。

图4 传统SARSA算法和改进SARSA算法迭代对比图

对比实验结果可知，迭代前期初始温度高搜索率大，因此路径长度变化较大，策略上随机选择动作，随着温度降低搜索加快，收敛速度明显加快，路径长度变化幅度减小；传统SARSA 算法由于其较小的动态因子ε，导致算法收敛较慢，且稳定性差，后逐渐趋于收敛。在收敛所需迭代次数方面，改进的SARSA 算法迭代次数为66，而传统SARSA 算法的迭代次数为93，表明模拟退火策略迭代次数更少，有更好的训练效果［16］。

图5 是相同起终点情况下对比SARSA 算法和改进SARSA 算法的滑行路径规划图，在该实验中，假设航空器在左转过程中遇到前方障碍物，设障碍物坐标为210，左边是使用传统SARSA 算法的规划结果，结果显示由于障碍物没有处于滑行路径所在栅格，在该转弯过程中，对航空器路径不产生影响；右边是使用改进SARSA 算法的路径规划结果，在同样位置设置障碍物后，由于算法的模拟退火行为策略，滑行路径发生改变，航空器在进行方向选择时，偏向于远离障碍物的方案，避免了潜在的冲突和碰撞，且收敛更快，规划路径的长度更短。

图5 传统SARSA算法和改进SARSA算法的路径规划对比图

4 结 论

基于模拟退火策略的SARSA 算法相对于传统SARSA 算法具有更加高效的搜索效率、收敛速度和稳定性，并基于栅格地图环境，得出模拟退火策略相较于ε-greedy 策略搜索效率更高，改进的SARSA 算法实时性好，能够为航空器快速规划出安全的路线。