基于层次任务网络的舰载机任务规划

卞大鹏，代丽红，李晶晶，祁超

1海军驻中国舰船研究设计中心军事代表室，湖北武汉430064

2中国舰船研究设计中心，湖北武汉430064

3华中科技大学自动化学院，湖北武汉430074

基于层次任务网络的舰载机任务规划

卞大鹏1，代丽红2，李晶晶2，祁超3

1海军驻中国舰船研究设计中心军事代表室，湖北武汉430064

2中国舰船研究设计中心，湖北武汉430064

3华中科技大学自动化学院，湖北武汉430074

航空母舰舰载机任务规划问题涉及复杂的资源约束、时态约束、操作规范及设备使用限制，且任务间相互耦合，是一类非确定性难（NP-hard）问题。其计算复杂度随问题规模呈指数增长，采用常规数学建模和求解方法很难解决。针对舰载机任务规划问题，考虑任务的层次性特征，以及时间和空间约束导致的资源冲突，设计资源状态更新机制，提出层次任务网络（Hierarchical Task Network，HTN）规划算法。算例分析结果表明，该规划方法可以充分考虑资源与时间约束，快速为多个带有截止期限的飞行任务提供可行的行动方案。

舰载机任务规划；层次任务网络；时态约束；资源冲突

网络出版地址：http://www.cnki.net/kcms/detail/42.1755.TJ.20160921.1345.030.html期刊网址：www.ship-research.com

引用格式：卞大鹏，代丽红，李晶晶，等.基于层次任务网络的舰载机任务规划［J］.中国舰船研究，2016，11（5）：35-41.

BIAN Dapeng，DAI Lihong，LI Jingjing，et al.Hierarchical task network-based carrier aircraft task planning［J］. Chinese Journal of Ship Research，2016，11（5）：35-41.

0　引言

舰载机是以航空母舰（以下简称“航母”）为基地的海上飞机，是航母主要的作战武器［1］。合理的舰载机任务规划，根据给定的飞行任务确定舰载机具体的准备、起飞及着舰时间和使用的资源，是保证航母作战效率和甲板运作安全的重要前提。由于舰载机的飞行任务具有层次性特征，需要将其分解成一系列可执行的、具有时间约束且不可分解的原子任务，不同的分解方法将产生不同的任务序列。另外，由于甲板、机舱、起飞和降落跑道的空间限制和功能区重叠，以及舰载机等关键设备的数量限制，舰载机任务规划需要考虑复杂的时间和资源约束。

2002年，美国曾在海军训练系统计划中提出自动任务规划的重要性［2］。然而，直到2011年，任务计划依然多由操作员人工实现，很少借助和使用决策支持工具［3］。实践中的任务规划也往往依赖人工对全局资源状态的观察凭借经验进行［4］。这种方式高度依赖规划人员的经验，由于涉及的任务和资源情况复杂，往往难以获得较优的方案，而且会由于对约束条件考虑不足而制定出有冲突的方案，导致危险操作。

目前，专门针对舰载机任务规划的研究还十分有限，研究主要集中在布列规划层面，而站在全局视角的任务规划则很少。麻省理工大学航空工程系设计了甲板运作行动方案规划系统DCAP（Deck operations course of action planner）［5-8］，其以DCAP为基础，对舰载机任务规划问题的研究采用了整数线性规划［5］、面向马氏决策过程的反向强化学习［6］和基于排队网络的方案制定［7］。

国内的研究主要采用多Agent建模仿真与混合优化算法相结合的方法［9］、多模式资源受限项目调度方法［10］和启发式方法［11］。这些研究大多需要构建数学模型，建模过程复杂，对约束的处理能力有限，且难以处理大规模问题，具有较强的局限性。究其原因，主要有以下几个方面：

1）要求能用数学模型对问题进行描述，但是实际的舰载机任务规划问题极其复杂，难以在考虑所有因素的前提下建立统一的数学模型。

2）对带有复杂约束的大规模问题的处理能力有限，难以处理任务之间复杂的时间、资源和空间约束，而且当问题规模较大时，消耗的计算时间过长，不符合实际需求。

3）主要处理静态确定性问题，难以处理实际环境中大量的动态因素和不确定性。

4）难以有效表达操作规程和经验知识，更难以利用经验知识提高任务规划的效率。

与大部分经典规划相比，层次任务网络（HTN）规划技术在推理能力和表达能力方面都有良好的表现。HTN规划的思想最早由Sacerdoti［12］于1975年提出，并结合了Tate［13］有关规划空间方面的研究。HTN技术是一种基于知识的分布式规划技术，它的出现与发展填补了人工智能规划技术和项目管理以及调度的运筹研究技术的缺口。从上世纪80年代开始，HTN技术被广泛应用于人工智能规划系统的开发中。1998年，Erol等［14］提出了一种全序规划控制策略，使HTN规划在众多应用领域中实现了更好的效果。Yang［15］和Kambhampati等［16］首次对HTN规划的理论模型进行了研究。Erol等［17］提出了一种完备的模型，为复杂性分析奠定了基础。

研究证明，HTN规划器可以表示并求解多种非经典规划问题，能有效模拟决策者的认知过程，能在任务分解的过程中对领域知识进行很好的描述和利用，在求解大规模问题时搜索效率高，适用于复杂性问题，满足时效性要求［18］，主要表现在：

1）HTN规划具有强大的表达能力，能够对复杂的舰载机任务规划问题进行有效的知识建模和表示，具体包括飞行任务、约束条件、航母状态、操作规程和经验知识等。

2）HTN规划求解过程具有目标导向的特征，其将问题求解过程分解为确定目标的完成途径和选择实现目标的最佳方法2个相对独立的子过程，与指挥人员的思考过程相似，生成的行动方案合理、直观，易于被指挥人员接受和信任。

3）HTN规划过程生成的分层任务网络表达了目标与子目标之间的分解关系，提供了任务规划过程中涉及的决策点及其上下文信息，反映了具有层次性的方案制定过程，便于将甲板运作的方案与航母其他区域作业环节（例如，底层仓库、物资保障等）的行动方案相互衔接、整合，实现整体上的协同运作。

4）HTN规划中使用了方法集合，可以利用方法模型描述任务分解的过程性知识，表达不同条件下完成给定任务目标的多种可行途径，很好地表示和利用已有的经验及知识，提高规划的速度。

正因如此，HTN规划在类似领域实践中成为应用最为广泛的智能规划方法［19］，其应用领域包括应急［20］、制造业［21］和企业管理［22］等。

为此，本文将以美国“尼米兹”号航母甲板布局为背景，采用HTN规划技术描述带有资源和时间约束的航母舰载机任务规划问题，进行知识建模与问题求解，并通过算例证明HTN规划技术对航母舰载机任务规划问题的有效性和可用性，以此来探索航母舰载机调度方案的自动规划方法。

1　问题描述

美国“尼米兹”号航母的甲板布局如图1所示［23］。其中，有4条弹射起飞跑道catapult 1～catapult 4，绿线中间为着舰带。

图1　“尼米兹”号航母甲板布局图Fig.1Deck of Nimitz class aircraft carrier

这4条起飞跑道可以同时使用，但由于甲板面积有限，以下硬约束必需满足：着舰带与弹射起飞跑道catapult 3和catapult 4重叠，因此，起飞和降落动作不能在该区域同时进行；甲板上可停放的舰载机数量最大为N。

设舰载机的飞行任务有给定的截止期限（deadline），本文所考虑的舰载机任务规划问题是为多个有截止期限的舰载机飞行任务规划出可行的准备、起飞与降落方案，并作如下假设：

1）任务必须在截止期限（指舰载机在空中开始执行任务的最晚时刻）之前尽可能早地执行。

2）同一种类型舰载机只能执行特定类型的飞行任务，本文考虑编队护航和侦察巡逻这2种任务类型，分别由舰载机SMAC和FMAC执行。

3）舰载机在某一时刻被指定执行某个飞行任务时，需不间断地进行准备动作并起飞，其中SMAC执行任务时的动作次序为：加燃料、移动至弹射器、弹射、执行任务、着舰；FMAC执行任务时的动作次序为：加武器、加燃料、移动至弹射器、弹射、执行任务、着舰。如果该时刻舰载机不在甲板上，在动作次序之前增加“移至甲板”；如果着舰时甲板舰载机数量达到上限，在动作次序之后增加“移至舰载机库。

4）考虑到舰载机携带燃料的有限性，飞机的空中飞行时间等于所执行任务类型所需要的时间，即执行完任务后必须立即着舰。

5）整个规划时间区间为［0，end］。

2　基于HTN的舰载机任务规划算法

本节将首先描述HTN问题及规划领域，着重阐述任务分解方法（method）与操作（operator）之间的层次关系，从而体现一个飞行任务的分解过程。另外，分别介绍规划过程中的2个要点，包括时间和资源约束的处理以及甲板舰载机数量的更新。

2.1HTN规划问题和领域

对于当前待分解的任务M，为了在截止期限前尽可能早地执行任务，在某时刻t-s如果有舰载机可用，则立即开始执行任务M需要的准备动作。由于舰载机在空中飞行的时间固定，一旦弹射成功，其着舰时间便会成为硬约束。如果着舰时刻着舰跑道被其他任务占用，则需在满足任务截止期限的范围内调整舰载机准备动作的开始时刻，从而改变着舰时间。由于在任务分解过程中是先产生舰载机开始占用时间和弹射时间，后产生着舰时间这一硬约束，因此不能以着舰时间为基准确定舰载机和弹射器的使用时间。

为了处理上述矛盾，本文设计了基于“飞机选择、时间校验、行动确定”的HTN任务网络构建思路，图2为设计HTN规划领域的方法和操作的层级关系图。

图2　HTN规划方法总体思路Fig.2Main method of HTN

受篇幅所限，本文未呈现该方法的所有分支。具体方法如下：

1）飞机选择。根据任务截止期限和当前规划状态下可利用的资源情况，确定执行该任务的舰载机并进行标记，确定任务最早开始准备时间、弹射器、弹射时间，以及最早的着舰时间。

2）时间校验。检验当前规划状态下能否满足方法（1）产生的硬约束着舰时间。如果满足，则直接进入行动确定阶段，不满足则根据着舰跑道使用情况调整着舰时间，同时调整舰载机开始准备时间和弹射时间，并检验此时是否满足任务截止期限的约束，如果满足，便可进入任务确定阶段，否则规划失败。

3）行动确定。该方法分解得到完成任务的具体操作，并基于时间和资源约束处理机制对资源状态进行更新。

2.2时间和资源约束处理

大部分HTN规划器处理时态的能力相对较弱［16］，针对SHOP2规划器，Nau等［24］提出了一种多时间轴预处理（MTP）的时态处理机制。MTP的基本思想是：为每一个动态属性p赋予一个时间轴，使用read-time（p）和write-time（p）记录最后一次对该属性进行读写操作的时刻；为每一个操作增加2个属性，即？start-time和？duration，用于更新操作中所改变动态属性p的read-time（p）和write-time（p）。这样，所有动态属性的时间轴就随着操作的执行不断向前移动。然而，这种只记录属性时间轴最后时刻的时态处理机制并不适用于上述提出的舰载机任务的规划过程。因为舰载机的任务规划过程是对每个任务逐个进行分解，假设当前分解任务为M1，确定使用舰载机a1，其着舰时间为t1-land，然后对任务M2进行分解，使用舰载机a2，如果a2在空中执行任务的时间小于a1的时间，则其着舰时间t2-land有可能小于t1-land。在这种情况下，如果使用MTP，分解M1时着舰带的时间轴已经推进到t1-land，导致分解M2时在t1-land之后搜索可能无法找到可行解，即使找到也是较劣解。

针对这一问题，本文设计了相应的时间和资源约束处理机制：

1）初始为每一个资源在规划时段［0，end］内增加一个时间轴状态（idle 0 end），表示在0时刻和end时刻该资源是空闲的。

2）任务分解过程中，时段o［t3，t4］内可以占用该资源的前提条件是，该资源存在一个时间轴状态（idle t1t2），且时段i［t1，t2］包含时段o［t3，t4］。如果该资源与其他资源功能区重合，则区域内其他资源也必须存在时间轴状态（idle t5t6），使时段i'［t5，t6］也包含时段o。

3）某操作导致时段o［t3，t4］内该资源被占用，则删除时间轴状态（idle t1t2），增加时间轴状态（idle t1t3）和（idle t4t2）。如果该资源与其他资源功能区重合，则区域内其他资源删除时间轴状态（idle t5t6），增加时间轴状态（idle t5t3）和（idle t4t6）。如果与多个资源功能区重合，则所有其他资源执行相同的状态增删机制。

上述时间和资源约束处理机制通过方法（schedule-catapult？catapult？t-launch），操作（！！schedule-aircraft？t-s？t-e）和（！！schedule-land land0？t-landing）得以实现，处理的资源包括弹射起飞跑道、着舰带及舰载机。

2.3甲板舰载机数量更新

由于本文考虑了甲板舰载机停放数量的限制，因此在规划过程中就必须记录每个时段内甲板上舰载机的停放数量，并根据导致甲板舰载机数量改变的操作进行实时更新。相应的甲板舰载机数量更新机制具体如下：

1）假设初始时刻甲板舰载机数量为x，则初始为甲板舰载机数量设置一个状态（on-deck-number x 0 end），表示在初始时刻认为甲板上舰载机数量在规划时段［0，end］内为x。

2）假设t时刻执行了改变甲板舰载机数量的操作，改变量为n，且甲板状态（on-deck-number x t1t2）所标记的时段［t1，t2］包含了时刻t，则删除甲板状态（on-deck-number x t1t2），增加甲板状态（on-deck-numberxt1t）和（on-deck-numberx+ntt2）。

3）操作实际改变了时段［t1，t2］之后的所有时段的甲板舰载机数量，而舰载机数量更新操作（！！forward-update-deckairnumber？t1？t2？x？n）每次只能对一个时段的舰载机数量作修改，因此以？t2作为传递参数使用递归算法依次改变后续时段的甲板舰载机数量。甲板舰载机数量更新递归算法如下：

会改变甲板舰载机数量的任务分解方法有：（move-to-bottom？p？t-move-to-bottom），（move-to-deck？aircraft？t-move-to-deck），（launch？aircraft？catapult？t-launch）和（landing？aircraft？t-landing），为便于阐述，分别记为方法1～方法4。方法1和方法2用于将舰载机移入或移出底层舰载机库，使用情形如下：有舰载机着舰时，如果甲板舰载机数量达到容量上限，则执行方法1；如果需要调用的舰载机在底层舰载机库中，则执行方法2；如果甲板舰载机数量达到容量上限，且所需要的舰载机在底层舰载机库中，则先执行方法1，然后再执行方法2。

3　算例分析

本节利用假定数据，通过算例分析验证基于HTN的舰载机任务规划方法的有效性，并检验问题规模对规划运行时间的影响。

3.1规划方法的有效性

为了验证基于HTN的舰载机任务规划方法的有效性，设计了12个飞行任务的规划问题（mission？type？deadline），分别为（mission 1 A），（mission 2 B），（mission 1 C），（mission 1 D），（mission 2 E），（mission 2 F），（mission 2 G），（mission 2 H），（mission 1 I），（mission 2 J），（mission 1 K）和（mission 1 L），其中常数A～L为12个任务的deadline。舰载机数量为6个，分别为SUAV 1（on-deck），SUAV 2（on-deck），SUAV 3（belowdeck），FUAV 1（on-deck），FUAV 2（below-deck）及FUAV 3（below-deck），甲板容量为3个，运行得到的行动方案如图3所示。

图3表示了规划得到的12个任务在执行过程中的时间安排和对资源的占用，其中舰载机所在行标注了每个任务的截止期限，弹射器所在行标注了任务的实际开始执行时间。由此可见，HTN规划得到了可行方案，即12个目标任务均在截止期限之前得到执行。调度人员根据需要执行舰载机从仓库移至甲板和从甲板移至仓库的动作，方案对资源的占用也满足功能重叠区域的时间约束（灰色部分所示）。HTN规划用接近自然语言的建模实现了对约束和方案规划方法的表达，并顺利规划出可行方案，验证了提出的基于HTN的舰载机任务规划方法的有效性。

图3　规划获得的行动方案时序图Fig.3Result of the planning

3.2问题规模对规划运行时间的影响

本节运用提出的舰载机任务规划方法分别求解了任务数量为3，6，12和18的4组规划问题。试验过程中取舰载机数量总数为12，甲板容量上限为6。规划时间随问题规模的变化趋势如图4所示。

可以看出，目前的规划运行时间为毫秒级。随着任务数量的增多，规划时间相应增加，但并非呈指数型增长。因此，在解决舰载机任务规划问题的过程中，HTN规划的速度应当远优于人工规划的速度。

图4　问题规模对规划时间的影响Fig.4Effect of problem size on planning time

4　结语

本文针对航母舰载机任务的规划问题，提出了基于HTN的舰载机任务规划方法，简要阐述了规划问题、领域及其关键环节，通过算例分析对方法的有效性进行了验证。本文的工作可以视为将HTN规划用于解决航母舰载机任务规划问题的初步探索，在今后的工作中，还需进一步考虑更为复杂的实际情况，对规划方法进行有针对性的扩展，提高HTN规划在舰载机规划领域的实用性。

［1］张立，王平，侯玉.航母舰载机对空防御作战出航保障指挥决策建模［J］.火力与指挥控制，2009，34（7）：89-91. ZHANG Li，WANG Ping，HOU Yu.Modeling of the command and decision system of launching preparations of aircraft on a carrier［J］.Fire Control and Command Control，2009，34（7）：89-91.

［2］NDRI.Navy training system plan for the aviation data management and control system：N78-NTSP-A-50-0009/A［R］.［S.l.］：NDRI，2002.

［3］RYAN J C，CUMMINGS M L，ROY N，et al.Designing an interactive local and global decision support system for aircraft carrier deck scheduling［C］//Aerospace Conferences.St.Louis，Missouri：American Institute of Aeronautics and Astronautics，2011.

［4］司维超，韩维，史玮韦.基于PSO算法的舰载机舰面布放调度方法研究［J］.航空学报，2012，33（11）：2048-2056. SI Weichao，HAN Wei，SHI Weiwei.Research on deck-disposed scheduling method of carrier planes based on PSO algorithm［J］.Acta Aeronautica et Astronautica Sinica，2012，33（11）：2048-2056.

［5］RYAN J C.Investigating possible effects of UAVs on aircraft carrier deck operations［R］.Cambridge，MA：Humans and Automation Laboratory，2011.

［6］MICHINI B，HOW J.A human-interactive course of action planner for aircraft carrier deck operations［C］// Aerospace Conferences.St.Louis，Missouri：American Institute of Aeronautics and Astronautics，2011.

［7］RYAN J C.Assessing the performance of human-automation collaborative planning system［D］.Massachusetts Avenue，Cambridge，MA：Massachusetts Institute of Technology，2011.

［8］CLARE A S，RYAN J C，JACKSON K F，et al.Innovative systems for human supervisory control of unmanned vehicles［J］.Proceedings of the Human Factors and Ergonomics Society Annual Meeting，2012， 56（1）：531-535.

［9］冯强，曾声奎，康锐.不确定条件下舰载机动态调度仿真与优化方法［J］.系统仿真学报，2011，23（7）：1497-1501，1506. FENG Qiang，ZENG Shengkui，KANG Rui.Dynamic scheduling simulation and optimization of carrier aircraft under uncertainty［J］.Journal of System Simulation，2011，23（7）：1497-1501，1506.

［10］刘钦辉，邱长华，王能建.考虑空间约束的舰载机作业调度模型研究［J］.哈尔滨工程大学学报，2012，33（11）：1435-1439，1452. LIU Qinhui，QIU Changhua，WANG Nengjian.Study on ship-based aircraft operation scheduling model considering spatial restriction［J］.Journal of Harbin Engineering University，2012，33（11）：1435-1439，1452.

［11］司维超，韩维，宋岩，等.基于多种群协作混沌智能算法的舰载机出动调度［J］.计算机应用研究，2013，30（2）：454-457. SI Weichao，HAN Wei，SONG Yan，et al.Takeoff scheduling of carrier plane based on multi-colonies cooperation and CLS intelligence algorithm［J］.ApplicationResearchofComputers，2013，30（2）：454-457.

［12］SACERDOTI E D.The nonlinear nature of plans［C］// Proceedings of the 14th International Joint Conference on Artificial Intelligence.San Francisco，CA，USA：Morgan Kaufmann Publishers Inc.，1975，1：206-214.

［13］TATE A.Generating project networks［C］//Proceedings of the 5th International Joint Conference on Artificial Intelligence.San Francisco，CA，USA：Morgan Kaufmann Publishers Inc.，1977，2：888-893.

［14］EROL K，HENDLER J，NAU D S.HTN planning：complexity and expressivity［C］//Proceedings of the twelfth National Conference on Artificial Intelligence. Menlo Park，CA，USA：American Association for Artificial Intelligence，1994，2：1123-1128.

［15］YANG Q.Formalizing planning knowledge for hierarchicalplanning［J］.ComputationalIntelligence，1990，6（1）：12-24.

［16］KAMBHAMPATI S，HENDLER J A.A validationstructure-based theory of plan modification and reuse［J］.Artifical Intelligence，1992，55（2/3）：193-258.

［17］EROL K，HENDLER J，NAU D S.UMCP：a sound and complete procedure for hierarchical task-network planning［C］//Proceedings of the International Conference on AI Planning Systems.［S.l.］：AIPS，1994：249-254.

［18］GEORGIEVSKI I，AIELLO M.HTN planning：overview，comparison，and beyond［J］.Artificial Intelli-gence，2015，222：124-156.

［19］NAU D，AU T C，ILGHAMI O，et al.Applications of SHOP and SHOP2［J］.IEEE Intelligent Systems，2005，20（2）：34-41.

［20］QI C，WANG H W.HTN planning based emergency responseactionplandevelopment［C］//ISCRAM ASIA 2012 Conference on Information Systems for Crisis Response and Management.Beijing，China：IEEE，2012：430-436.

［21］SOLTANI S，ASADI M，HATALA M，et al.Automated planning for feature model configuration based on stakeholder'business concerns［C］//Proceedings of the 2011 26th IEEE/ACM International Conference on Automated Software Engineering.Lawrence，KS， USA：IEEE，2011：536-539.

［22］GONZÁLEZ-FERRER A，FERNÁNDEZ-OLIVARES J，CASTILLO L.From business process models to hierarchical task network planning domains［J］.The KnowledgeEngineeringReview，2012，28（2）：175-193.

［23］CASTILLOL，FDEZ-OLIVARESJ，GARCÍAPÉREZ O，et al.Efficiently handling temporal knowledge in an HTN planner［C］//Proceedings of the 16th International Conference on Automated Planning and Scheduling.Cumbria，K：AAAI Press，2006：63-72.

［24］NAU D，AU T C，ILGHAMI O，et al.SHOP2：an HTN planning system［J］.Journal of Artificial Intelligence Research，2003，20（1）：379-404.

Hierarchical task network-based carrier aircraft task planning

BIAN Dapeng1，DAI Lihong2，LI Jingjing2，QI Chao3
1 Naval Military Representative Office in China Ship Development and Design Center，Wuhan 430064，China
2 China Ship Development and Design Center，Wuhan 430064，China
3 School of Automation，Huazhong University of Science and Technology，Wuhan 430074，China

Carrier aircraft task planning problems involve complicated resource constraints，temporal constraints，operation rules and equipment limitations.Tasks seriously interact with each other.As such，it is a typical NP-hard problem which is difficult to deal with by following conventional mathematical modeling and problem-solving methods.Aiming at the aircraft task planning problem，this paper considers task hierarchy and resource conflicts caused by time and spatial constraints，develops a resource status updating mechanism and proposes a Hierarchical Task Network（HTN）planning algorithm.The results of the experimental study indicate that the proposed HTN algorithm is capable of rapidly generating an action plan for tasks with time windows constrained by resources and temporal relationships.

carrier aircraft task planning；Hierarchical Task Network（HTN）；temporal constraints；resource conflicts

U674.771

A

10.3969/j.issn.1673-3185.2016.05.006

2015-12-21网络出版时间：2016-9-21 13:45

国家自然科学基金面上项目（71371079）

卞大鹏，男，1976年生，硕士，工程师。研究方向：舰船航空保障。E-mail：18607109657@163.com

李晶晶（通信作者），男，1986年生，硕士，工程师。研究方向：舰船航空保障。

E-mail：jjli1986@126.com