卞大鵬,代麗紅,李晶晶,祁超
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.
艦載機是以航空母艦(以下簡稱“航母”)為基地的海上飛機,是航母主要的作戰武器[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所示[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]。
本節將首先描述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。
本節利用假定數據,通過算例分析驗證基于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
本文針對航母艦載機任務的規劃問題,提出了基于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