基于層次任務(wù)網(wǎng)絡(luò)的艦載機(jī)任務(wù)規(guī)劃

卞大鵬，代麗紅，李晶晶，祁超

1海軍駐中國(guó)艦船研究設(shè)計(jì)中心軍事代表室，湖北武漢430064

2中國(guó)艦船研究設(shè)計(jì)中心，湖北武漢430064

3華中科技大學(xué)自動(dòng)化學(xué)院，湖北武漢430074

基于層次任務(wù)網(wǎng)絡(luò)的艦載機(jī)任務(wù)規(guī)劃

卞大鵬1，代麗紅2，李晶晶2，祁超3

1海軍駐中國(guó)艦船研究設(shè)計(jì)中心軍事代表室，湖北武漢430064

2中國(guó)艦船研究設(shè)計(jì)中心，湖北武漢430064

3華中科技大學(xué)自動(dòng)化學(xué)院，湖北武漢430074

航空母艦艦載機(jī)任務(wù)規(guī)劃問(wèn)題涉及復(fù)雜的資源約束、時(shí)態(tài)約束、操作規(guī)范及設(shè)備使用限制，且任務(wù)間相互耦合，是一類(lèi)非確定性難（NP-hard）問(wèn)題。其計(jì)算復(fù)雜度隨問(wèn)題規(guī)模呈指數(shù)增長(zhǎng)，采用常規(guī)數(shù)學(xué)建模和求解方法很難解決。針對(duì)艦載機(jī)任務(wù)規(guī)劃問(wèn)題，考慮任務(wù)的層次性特征，以及時(shí)間和空間約束導(dǎo)致的資源沖突，設(shè)計(jì)資源狀態(tài)更新機(jī)制，提出層次任務(wù)網(wǎng)絡(luò)（Hierarchical Task Network，HTN）規(guī)劃算法。算例分析結(jié)果表明，該規(guī)劃方法可以充分考慮資源與時(shí)間約束，快速為多個(gè)帶有截止期限的飛行任務(wù)提供可行的行動(dòng)方案。

艦載機(jī)任務(wù)規(guī)劃；層次任務(wù)網(wǎng)絡(luò)；時(shí)態(tài)約束；資源沖突

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/42.1755.TJ.20160921.1345.030.html期刊網(wǎng)址：www.ship-research.com

引用格式：卞大鵬，代麗紅，李晶晶，等.基于層次任務(wù)網(wǎng)絡(luò)的艦載機(jī)任務(wù)規(guī)劃［J］.中國(guó)艦船研究，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　引言

艦載機(jī)是以航空母艦（以下簡(jiǎn)稱(chēng)“航母”）為基地的海上飛機(jī)，是航母主要的作戰(zhàn)武器［1］。合理的艦載機(jī)任務(wù)規(guī)劃，根據(jù)給定的飛行任務(wù)確定艦載機(jī)具體的準(zhǔn)備、起飛及著艦時(shí)間和使用的資源，是保證航母作戰(zhàn)效率和甲板運(yùn)作安全的重要前提。由于艦載機(jī)的飛行任務(wù)具有層次性特征，需要將其分解成一系列可執(zhí)行的、具有時(shí)間約束且不可分解的原子任務(wù)，不同的分解方法將產(chǎn)生不同的任務(wù)序列。另外，由于甲板、機(jī)艙、起飛和降落跑道的空間限制和功能區(qū)重疊，以及艦載機(jī)等關(guān)鍵設(shè)備的數(shù)量限制，艦載機(jī)任務(wù)規(guī)劃需要考慮復(fù)雜的時(shí)間和資源約束。

2002年，美國(guó)曾在海軍訓(xùn)練系統(tǒng)計(jì)劃中提出自動(dòng)任務(wù)規(guī)劃的重要性［2］。然而，直到2011年，任務(wù)計(jì)劃依然多由操作員人工實(shí)現(xiàn)，很少借助和使用決策支持工具［3］。實(shí)踐中的任務(wù)規(guī)劃也往往依賴(lài)人工對(duì)全局資源狀態(tài)的觀察憑借經(jīng)驗(yàn)進(jìn)行［4］。這種方式高度依賴(lài)規(guī)劃人員的經(jīng)驗(yàn)，由于涉及的任務(wù)和資源情況復(fù)雜，往往難以獲得較優(yōu)的方案，而且會(huì)由于對(duì)約束條件考慮不足而制定出有沖突的方案，導(dǎo)致危險(xiǎn)操作。

目前，專(zhuān)門(mén)針對(duì)艦載機(jī)任務(wù)規(guī)劃的研究還十分有限，研究主要集中在布列規(guī)劃層面，而站在全局視角的任務(wù)規(guī)劃則很少。麻省理工大學(xué)航空工程系設(shè)計(jì)了甲板運(yùn)作行動(dòng)方案規(guī)劃系統(tǒng)DCAP（Deck operations course of action planner）［5-8］，其以DCAP為基礎(chǔ)，對(duì)艦載機(jī)任務(wù)規(guī)劃問(wèn)題的研究采用了整數(shù)線性規(guī)劃［5］、面向馬氏決策過(guò)程的反向強(qiáng)化學(xué)習(xí)［6］和基于排隊(duì)網(wǎng)絡(luò)的方案制定［7］。

國(guó)內(nèi)的研究主要采用多Agent建模仿真與混合優(yōu)化算法相結(jié)合的方法［9］、多模式資源受限項(xiàng)目調(diào)度方法［10］和啟發(fā)式方法［11］。這些研究大多需要構(gòu)建數(shù)學(xué)模型，建模過(guò)程復(fù)雜，對(duì)約束的處理能力有限，且難以處理大規(guī)模問(wèn)題，具有較強(qiáng)的局限性。究其原因，主要有以下幾個(gè)方面：

1）要求能用數(shù)學(xué)模型對(duì)問(wèn)題進(jìn)行描述，但是實(shí)際的艦載機(jī)任務(wù)規(guī)劃問(wèn)題極其復(fù)雜，難以在考慮所有因素的前提下建立統(tǒng)一的數(shù)學(xué)模型。

2）對(duì)帶有復(fù)雜約束的大規(guī)模問(wèn)題的處理能力有限，難以處理任務(wù)之間復(fù)雜的時(shí)間、資源和空間約束，而且當(dāng)問(wèn)題規(guī)模較大時(shí)，消耗的計(jì)算時(shí)間過(guò)長(zhǎng)，不符合實(shí)際需求。

3）主要處理靜態(tài)確定性問(wèn)題，難以處理實(shí)際環(huán)境中大量的動(dòng)態(tài)因素和不確定性。

4）難以有效表達(dá)操作規(guī)程和經(jīng)驗(yàn)知識(shí)，更難以利用經(jīng)驗(yàn)知識(shí)提高任務(wù)規(guī)劃的效率。

與大部分經(jīng)典規(guī)劃相比，層次任務(wù)網(wǎng)絡(luò)（HTN）規(guī)劃技術(shù)在推理能力和表達(dá)能力方面都有良好的表現(xiàn)。HTN規(guī)劃的思想最早由Sacerdoti［12］于1975年提出，并結(jié)合了Tate［13］有關(guān)規(guī)劃空間方面的研究。HTN技術(shù)是一種基于知識(shí)的分布式規(guī)劃技術(shù)，它的出現(xiàn)與發(fā)展填補(bǔ)了人工智能規(guī)劃技術(shù)和項(xiàng)目管理以及調(diào)度的運(yùn)籌研究技術(shù)的缺口。從上世紀(jì)80年代開(kāi)始，HTN技術(shù)被廣泛應(yīng)用于人工智能規(guī)劃系統(tǒng)的開(kāi)發(fā)中。1998年，Erol等［14］提出了一種全序規(guī)劃控制策略，使HTN規(guī)劃在眾多應(yīng)用領(lǐng)域中實(shí)現(xiàn)了更好的效果。Yang［15］和Kambhampati等［16］首次對(duì)HTN規(guī)劃的理論模型進(jìn)行了研究。Erol等［17］提出了一種完備的模型，為復(fù)雜性分析奠定了基礎(chǔ)。

研究證明，HTN規(guī)劃器可以表示并求解多種非經(jīng)典規(guī)劃問(wèn)題，能有效模擬決策者的認(rèn)知過(guò)程，能在任務(wù)分解的過(guò)程中對(duì)領(lǐng)域知識(shí)進(jìn)行很好的描述和利用，在求解大規(guī)模問(wèn)題時(shí)搜索效率高，適用于復(fù)雜性問(wèn)題，滿(mǎn)足時(shí)效性要求［18］，主要表現(xiàn)在：

1）HTN規(guī)劃具有強(qiáng)大的表達(dá)能力，能夠?qū)?fù)雜的艦載機(jī)任務(wù)規(guī)劃問(wèn)題進(jìn)行有效的知識(shí)建模和表示，具體包括飛行任務(wù)、約束條件、航母狀態(tài)、操作規(guī)程和經(jīng)驗(yàn)知識(shí)等。

2）HTN規(guī)劃求解過(guò)程具有目標(biāo)導(dǎo)向的特征，其將問(wèn)題求解過(guò)程分解為確定目標(biāo)的完成途徑和選擇實(shí)現(xiàn)目標(biāo)的最佳方法2個(gè)相對(duì)獨(dú)立的子過(guò)程，與指揮人員的思考過(guò)程相似，生成的行動(dòng)方案合理、直觀，易于被指揮人員接受和信任。

3）HTN規(guī)劃過(guò)程生成的分層任務(wù)網(wǎng)絡(luò)表達(dá)了目標(biāo)與子目標(biāo)之間的分解關(guān)系，提供了任務(wù)規(guī)劃過(guò)程中涉及的決策點(diǎn)及其上下文信息，反映了具有層次性的方案制定過(guò)程，便于將甲板運(yùn)作的方案與航母其他區(qū)域作業(yè)環(huán)節(jié)（例如，底層倉(cāng)庫(kù)、物資保障等）的行動(dòng)方案相互銜接、整合，實(shí)現(xiàn)整體上的協(xié)同運(yùn)作。

4）HTN規(guī)劃中使用了方法集合，可以利用方法模型描述任務(wù)分解的過(guò)程性知識(shí)，表達(dá)不同條件下完成給定任務(wù)目標(biāo)的多種可行途徑，很好地表示和利用已有的經(jīng)驗(yàn)及知識(shí)，提高規(guī)劃的速度。

正因如此，HTN規(guī)劃在類(lèi)似領(lǐng)域?qū)嵺`中成為應(yīng)用最為廣泛的智能規(guī)劃方法［19］，其應(yīng)用領(lǐng)域包括應(yīng)急［20］、制造業(yè)［21］和企業(yè)管理［22］等。

為此，本文將以美國(guó)“尼米茲”號(hào)航母甲板布局為背景，采用HTN規(guī)劃技術(shù)描述帶有資源和時(shí)間約束的航母艦載機(jī)任務(wù)規(guī)劃問(wèn)題，進(jìn)行知識(shí)建模與問(wèn)題求解，并通過(guò)算例證明HTN規(guī)劃技術(shù)對(duì)航母艦載機(jī)任務(wù)規(guī)劃問(wèn)題的有效性和可用性，以此來(lái)探索航母艦載機(jī)調(diào)度方案的自動(dòng)規(guī)劃方法。

1　問(wèn)題描述

美國(guó)“尼米茲”號(hào)航母的甲板布局如圖1所示［23］。其中，有4條彈射起飛跑道catapult 1～catapult 4，綠線中間為著艦帶。

圖1　“尼米茲”號(hào)航母甲板布局圖Fig.1Deck of Nimitz class aircraft carrier

這4條起飛跑道可以同時(shí)使用，但由于甲板面積有限，以下硬約束必需滿(mǎn)足：著艦帶與彈射起飛跑道catapult 3和catapult 4重疊，因此，起飛和降落動(dòng)作不能在該區(qū)域同時(shí)進(jìn)行；甲板上可停放的艦載機(jī)數(shù)量最大為N。

設(shè)艦載機(jī)的飛行任務(wù)有給定的截止期限（deadline），本文所考慮的艦載機(jī)任務(wù)規(guī)劃問(wèn)題是為多個(gè)有截止期限的艦載機(jī)飛行任務(wù)規(guī)劃出可行的準(zhǔn)備、起飛與降落方案，并作如下假設(shè)：

1）任務(wù)必須在截止期限（指艦載機(jī)在空中開(kāi)始執(zhí)行任務(wù)的最晚時(shí)刻）之前盡可能早地執(zhí)行。

2）同一種類(lèi)型艦載機(jī)只能執(zhí)行特定類(lèi)型的飛行任務(wù)，本文考慮編隊(duì)護(hù)航和偵察巡邏這2種任務(wù)類(lèi)型，分別由艦載機(jī)SMAC和FMAC執(zhí)行。

3）艦載機(jī)在某一時(shí)刻被指定執(zhí)行某個(gè)飛行任務(wù)時(shí)，需不間斷地進(jìn)行準(zhǔn)備動(dòng)作并起飛，其中SMAC執(zhí)行任務(wù)時(shí)的動(dòng)作次序?yàn)椋杭尤剂?、移?dòng)至彈射器、彈射、執(zhí)行任務(wù)、著艦；FMAC執(zhí)行任務(wù)時(shí)的動(dòng)作次序?yàn)椋杭游淦?、加燃料、移?dòng)至彈射器、彈射、執(zhí)行任務(wù)、著艦。如果該時(shí)刻艦載機(jī)不在甲板上，在動(dòng)作次序之前增加“移至甲板”；如果著艦時(shí)甲板艦載機(jī)數(shù)量達(dá)到上限，在動(dòng)作次序之后增加“移至艦載機(jī)庫(kù)。

4）考慮到艦載機(jī)攜帶燃料的有限性，飛機(jī)的空中飛行時(shí)間等于所執(zhí)行任務(wù)類(lèi)型所需要的時(shí)間，即執(zhí)行完任務(wù)后必須立即著艦。

5）整個(gè)規(guī)劃時(shí)間區(qū)間為［0，end］。

2　基于HTN的艦載機(jī)任務(wù)規(guī)劃算法

本節(jié)將首先描述HTN問(wèn)題及規(guī)劃領(lǐng)域，著重闡述任務(wù)分解方法（method）與操作（operator）之間的層次關(guān)系，從而體現(xiàn)一個(gè)飛行任務(wù)的分解過(guò)程。另外，分別介紹規(guī)劃過(guò)程中的2個(gè)要點(diǎn)，包括時(shí)間和資源約束的處理以及甲板艦載機(jī)數(shù)量的更新。

2.1HTN規(guī)劃問(wèn)題和領(lǐng)域

對(duì)于當(dāng)前待分解的任務(wù)M，為了在截止期限前盡可能早地執(zhí)行任務(wù)，在某時(shí)刻t-s如果有艦載機(jī)可用，則立即開(kāi)始執(zhí)行任務(wù)M需要的準(zhǔn)備動(dòng)作。由于艦載機(jī)在空中飛行的時(shí)間固定，一旦彈射成功，其著艦時(shí)間便會(huì)成為硬約束。如果著艦時(shí)刻著艦跑道被其他任務(wù)占用，則需在滿(mǎn)足任務(wù)截止期限的范圍內(nèi)調(diào)整艦載機(jī)準(zhǔn)備動(dòng)作的開(kāi)始時(shí)刻，從而改變著艦時(shí)間。由于在任務(wù)分解過(guò)程中是先產(chǎn)生艦載機(jī)開(kāi)始占用時(shí)間和彈射時(shí)間，后產(chǎn)生著艦時(shí)間這一硬約束，因此不能以著艦時(shí)間為基準(zhǔn)確定艦載機(jī)和彈射器的使用時(shí)間。

為了處理上述矛盾，本文設(shè)計(jì)了基于“飛機(jī)選擇、時(shí)間校驗(yàn)、行動(dòng)確定”的HTN任務(wù)網(wǎng)絡(luò)構(gòu)建思路，圖2為設(shè)計(jì)HTN規(guī)劃領(lǐng)域的方法和操作的層級(jí)關(guān)系圖。

圖2　HTN規(guī)劃方法總體思路Fig.2Main method of HTN

受篇幅所限，本文未呈現(xiàn)該方法的所有分支。具體方法如下：

1）飛機(jī)選擇。根據(jù)任務(wù)截止期限和當(dāng)前規(guī)劃狀態(tài)下可利用的資源情況，確定執(zhí)行該任務(wù)的艦載機(jī)并進(jìn)行標(biāo)記，確定任務(wù)最早開(kāi)始準(zhǔn)備時(shí)間、彈射器、彈射時(shí)間，以及最早的著艦時(shí)間。

2）時(shí)間校驗(yàn)。檢驗(yàn)當(dāng)前規(guī)劃狀態(tài)下能否滿(mǎn)足方法（1）產(chǎn)生的硬約束著艦時(shí)間。如果滿(mǎn)足，則直接進(jìn)入行動(dòng)確定階段，不滿(mǎn)足則根據(jù)著艦跑道使用情況調(diào)整著艦時(shí)間，同時(shí)調(diào)整艦載機(jī)開(kāi)始準(zhǔn)備時(shí)間和彈射時(shí)間，并檢驗(yàn)此時(shí)是否滿(mǎn)足任務(wù)截止期限的約束，如果滿(mǎn)足，便可進(jìn)入任務(wù)確定階段，否則規(guī)劃失敗。

3）行動(dòng)確定。該方法分解得到完成任務(wù)的具體操作，并基于時(shí)間和資源約束處理機(jī)制對(duì)資源狀態(tài)進(jìn)行更新。

2.2時(shí)間和資源約束處理

大部分HTN規(guī)劃器處理時(shí)態(tài)的能力相對(duì)較弱［16］，針對(duì)SHOP2規(guī)劃器，Nau等［24］提出了一種多時(shí)間軸預(yù)處理（MTP）的時(shí)態(tài)處理機(jī)制。MTP的基本思想是：為每一個(gè)動(dòng)態(tài)屬性p賦予一個(gè)時(shí)間軸，使用read-time（p）和write-time（p）記錄最后一次對(duì)該屬性進(jìn)行讀寫(xiě)操作的時(shí)刻；為每一個(gè)操作增加2個(gè)屬性，即？start-time和？duration，用于更新操作中所改變動(dòng)態(tài)屬性p的read-time（p）和write-time（p）。這樣，所有動(dòng)態(tài)屬性的時(shí)間軸就隨著操作的執(zhí)行不斷向前移動(dòng)。然而，這種只記錄屬性時(shí)間軸最后時(shí)刻的時(shí)態(tài)處理機(jī)制并不適用于上述提出的艦載機(jī)任務(wù)的規(guī)劃過(guò)程。因?yàn)榕炤d機(jī)的任務(wù)規(guī)劃過(guò)程是對(duì)每個(gè)任務(wù)逐個(gè)進(jìn)行分解，假設(shè)當(dāng)前分解任務(wù)為M1，確定使用艦載機(jī)a1，其著艦時(shí)間為t1-land，然后對(duì)任務(wù)M2進(jìn)行分解，使用艦載機(jī)a2，如果a2在空中執(zhí)行任務(wù)的時(shí)間小于a1的時(shí)間，則其著艦時(shí)間t2-land有可能小于t1-land。在這種情況下，如果使用MTP，分解M1時(shí)著艦帶的時(shí)間軸已經(jīng)推進(jìn)到t1-land，導(dǎo)致分解M2時(shí)在t1-land之后搜索可能無(wú)法找到可行解，即使找到也是較劣解。

針對(duì)這一問(wèn)題，本文設(shè)計(jì)了相應(yīng)的時(shí)間和資源約束處理機(jī)制：

1）初始為每一個(gè)資源在規(guī)劃時(shí)段［0，end］內(nèi)增加一個(gè)時(shí)間軸狀態(tài)（idle 0 end），表示在0時(shí)刻和end時(shí)刻該資源是空閑的。

2）任務(wù)分解過(guò)程中，時(shí)段o［t3，t4］內(nèi)可以占用該資源的前提條件是，該資源存在一個(gè)時(shí)間軸狀態(tài)（idle t1t2），且時(shí)段i［t1，t2］包含時(shí)段o［t3，t4］。如果該資源與其他資源功能區(qū)重合，則區(qū)域內(nèi)其他資源也必須存在時(shí)間軸狀態(tài)（idle t5t6），使時(shí)段i'［t5，t6］也包含時(shí)段o。

3）某操作導(dǎo)致時(shí)段o［t3，t4］內(nèi)該資源被占用，則刪除時(shí)間軸狀態(tài)（idle t1t2），增加時(shí)間軸狀態(tài)（idle t1t3）和（idle t4t2）。如果該資源與其他資源功能區(qū)重合，則區(qū)域內(nèi)其他資源刪除時(shí)間軸狀態(tài)（idle t5t6），增加時(shí)間軸狀態(tài)（idle t5t3）和（idle t4t6）。如果與多個(gè)資源功能區(qū)重合，則所有其他資源執(zhí)行相同的狀態(tài)增刪機(jī)制。

上述時(shí)間和資源約束處理機(jī)制通過(guò)方法（schedule-catapult？catapult？t-launch），操作（??！schedule-aircraft？t-s？t-e）和（！！schedule-land land0？t-landing）得以實(shí)現(xiàn)，處理的資源包括彈射起飛跑道、著艦帶及艦載機(jī)。

2.3甲板艦載機(jī)數(shù)量更新

由于本文考慮了甲板艦載機(jī)停放數(shù)量的限制，因此在規(guī)劃過(guò)程中就必須記錄每個(gè)時(shí)段內(nèi)甲板上艦載機(jī)的停放數(shù)量，并根據(jù)導(dǎo)致甲板艦載機(jī)數(shù)量改變的操作進(jìn)行實(shí)時(shí)更新。相應(yīng)的甲板艦載機(jī)數(shù)量更新機(jī)制具體如下：

1）假設(shè)初始時(shí)刻甲板艦載機(jī)數(shù)量為x，則初始為甲板艦載機(jī)數(shù)量設(shè)置一個(gè)狀態(tài)（on-deck-number x 0 end），表示在初始時(shí)刻認(rèn)為甲板上艦載機(jī)數(shù)量在規(guī)劃時(shí)段［0，end］內(nèi)為x。

2）假設(shè)t時(shí)刻執(zhí)行了改變甲板艦載機(jī)數(shù)量的操作，改變量為n，且甲板狀態(tài)（on-deck-number x t1t2）所標(biāo)記的時(shí)段［t1，t2］包含了時(shí)刻t，則刪除甲板狀態(tài)（on-deck-number x t1t2），增加甲板狀態(tài)（on-deck-numberxt1t）和（on-deck-numberx+ntt2）。

3）操作實(shí)際改變了時(shí)段［t1，t2］之后的所有時(shí)段的甲板艦載機(jī)數(shù)量，而艦載機(jī)數(shù)量更新操作（?。orward-update-deckairnumber？t1？t2？x？n）每次只能對(duì)一個(gè)時(shí)段的艦載機(jī)數(shù)量作修改，因此以？t2作為傳遞參數(shù)使用遞歸算法依次改變后續(xù)時(shí)段的甲板艦載機(jī)數(shù)量。甲板艦載機(jī)數(shù)量更新遞歸算法如下：

會(huì)改變甲板艦載機(jī)數(shù)量的任務(wù)分解方法有：（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用于將艦載機(jī)移入或移出底層艦載機(jī)庫(kù)，使用情形如下：有艦載機(jī)著艦時(shí)，如果甲板艦載機(jī)數(shù)量達(dá)到容量上限，則執(zhí)行方法1；如果需要調(diào)用的艦載機(jī)在底層艦載機(jī)庫(kù)中，則執(zhí)行方法2；如果甲板艦載機(jī)數(shù)量達(dá)到容量上限，且所需要的艦載機(jī)在底層艦載機(jī)庫(kù)中，則先執(zhí)行方法1，然后再執(zhí)行方法2。

3　算例分析

本節(jié)利用假定數(shù)據(jù)，通過(guò)算例分析驗(yàn)證基于HTN的艦載機(jī)任務(wù)規(guī)劃方法的有效性，并檢驗(yàn)問(wèn)題規(guī)模對(duì)規(guī)劃運(yùn)行時(shí)間的影響。

3.1規(guī)劃方法的有效性

為了驗(yàn)證基于HTN的艦載機(jī)任務(wù)規(guī)劃方法的有效性，設(shè)計(jì)了12個(gè)飛行任務(wù)的規(guī)劃問(wèn)題（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），其中常數(shù)A～L為12個(gè)任務(wù)的deadline。艦載機(jī)數(shù)量為6個(gè)，分別為SUAV 1（on-deck），SUAV 2（on-deck），SUAV 3（belowdeck），F(xiàn)UAV 1（on-deck），F(xiàn)UAV 2（below-deck）及FUAV 3（below-deck），甲板容量為3個(gè)，運(yùn)行得到的行動(dòng)方案如圖3所示。

圖3表示了規(guī)劃得到的12個(gè)任務(wù)在執(zhí)行過(guò)程中的時(shí)間安排和對(duì)資源的占用，其中艦載機(jī)所在行標(biāo)注了每個(gè)任務(wù)的截止期限，彈射器所在行標(biāo)注了任務(wù)的實(shí)際開(kāi)始執(zhí)行時(shí)間。由此可見(jiàn)，HTN規(guī)劃得到了可行方案，即12個(gè)目標(biāo)任務(wù)均在截止期限之前得到執(zhí)行。調(diào)度人員根據(jù)需要執(zhí)行艦載機(jī)從倉(cāng)庫(kù)移至甲板和從甲板移至倉(cāng)庫(kù)的動(dòng)作，方案對(duì)資源的占用也滿(mǎn)足功能重疊區(qū)域的時(shí)間約束（灰色部分所示）。HTN規(guī)劃用接近自然語(yǔ)言的建模實(shí)現(xiàn)了對(duì)約束和方案規(guī)劃方法的表達(dá)，并順利規(guī)劃出可行方案，驗(yàn)證了提出的基于HTN的艦載機(jī)任務(wù)規(guī)劃方法的有效性。

圖3　規(guī)劃獲得的行動(dòng)方案時(shí)序圖Fig.3Result of the planning

3.2問(wèn)題規(guī)模對(duì)規(guī)劃運(yùn)行時(shí)間的影響

本節(jié)運(yùn)用提出的艦載機(jī)任務(wù)規(guī)劃方法分別求解了任務(wù)數(shù)量為3，6，12和18的4組規(guī)劃問(wèn)題。試驗(yàn)過(guò)程中取艦載機(jī)數(shù)量總數(shù)為12，甲板容量上限為6。規(guī)劃時(shí)間隨問(wèn)題規(guī)模的變化趨勢(shì)如圖4所示。

可以看出，目前的規(guī)劃運(yùn)行時(shí)間為毫秒級(jí)。隨著任務(wù)數(shù)量的增多，規(guī)劃時(shí)間相應(yīng)增加，但并非呈指數(shù)型增長(zhǎng)。因此，在解決艦載機(jī)任務(wù)規(guī)劃問(wèn)題的過(guò)程中，HTN規(guī)劃的速度應(yīng)當(dāng)遠(yuǎn)優(yōu)于人工規(guī)劃的速度。

圖4　問(wèn)題規(guī)模對(duì)規(guī)劃時(shí)間的影響Fig.4Effect of problem size on planning time

4　結(jié)語(yǔ)

本文針對(duì)航母艦載機(jī)任務(wù)的規(guī)劃問(wèn)題，提出了基于HTN的艦載機(jī)任務(wù)規(guī)劃方法，簡(jiǎn)要闡述了規(guī)劃問(wèn)題、領(lǐng)域及其關(guān)鍵環(huán)節(jié)，通過(guò)算例分析對(duì)方法的有效性進(jìn)行了驗(yàn)證。本文的工作可以視為將HTN規(guī)劃用于解決航母艦載機(jī)任務(wù)規(guī)劃問(wèn)題的初步探索，在今后的工作中，還需進(jìn)一步考慮更為復(fù)雜的實(shí)際情況，對(duì)規(guī)劃方法進(jìn)行有針對(duì)性的擴(kuò)展，提高HTN規(guī)劃在艦載機(jī)規(guī)劃領(lǐng)域的實(shí)用性。

［1］張立，王平，侯玉.航母艦載機(jī)對(duì)空防御作戰(zhàn)出航保障指揮決策建模［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ī)艦面布放調(diào)度方法研究［J］.航空學(xué)報(bào)，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］馮強(qiáng)，曾聲奎，康銳.不確定條件下艦載機(jī)動(dòng)態(tài)調(diào)度仿真與優(yōu)化方法［J］.系統(tǒng)仿真學(xué)報(bào)，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］劉欽輝，邱長(zhǎng)華，王能建.考慮空間約束的艦載機(jī)作業(yè)調(diào)度模型研究［J］.哈爾濱工程大學(xué)學(xué)報(bào)，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］司維超，韓維，宋巖，等.基于多種群協(xié)作混沌智能算法的艦載機(jī)出動(dòng)調(diào)度［J］.計(jì)算機(jī)應(yīng)用研究，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，F(xiàn)ERNá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，F(xiàn)DEZ-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網(wǎng)絡(luò)出版時(shí)間：2016-9-21 13:45

國(guó)家自然科學(xué)基金面上項(xiàng)目（71371079）

卞大鵬，男，1976年生，碩士，工程師。研究方向：艦船航空保障。E-mail：18607109657@163.com

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

E-mail：jjli1986@126.com