基于ＭＡＳ技術(shù)的多星協(xié)同偵察任務(wù)規(guī)劃系統(tǒng)設(shè)計(jì)
2009-01-01 00:00:00程思微陳克偉張輝陳璟
計(jì)算機(jī)應(yīng)用研究 2009年3期
（國防科學(xué)技術(shù)大學(xué) 機(jī)電工程與自動化學(xué)院， 長沙 410073）
摘 要：基于MAS技術(shù)，提出用多agent系統(tǒng)來實(shí)現(xiàn)多星協(xié)同偵察任務(wù)規(guī)劃系統(tǒng)，建立系統(tǒng)的總體結(jié)構(gòu)，并對其中的關(guān)鍵技術(shù)進(jìn)行分析，給出了基于合同網(wǎng)的多星協(xié)作結(jié)構(gòu)，實(shí)現(xiàn)了偵察任務(wù)分解和任務(wù)分配；在單個(gè)agent中利用已有規(guī)劃器SAPA實(shí)現(xiàn)單星行動規(guī)劃。基于MAS建立的任務(wù)規(guī)劃系統(tǒng)具有較好的智能性和自主性。
關(guān)鍵詞：多智能體技術(shù)； 任務(wù)規(guī)劃； 多偵察衛(wèi)星； 合同網(wǎng)
中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A
文章編號：10013695(2009)03095603
Design of coordinated multisatellite reconnaissance mission planning system
based on multiagent technique
CHENG Siwei， CHEN Kewei， ZHANG Hui， CHEN Jing
(College of Electromechanical Engineering Automation， National University of Defense Technology， Changsha 410073， China)
Abstract:The paperimplemented a coordinated multisatellite reconnaissance mission planning system by using multiagent system. It established the architecture of the system and analyzed the keytechnologies: brought out a structure of multisatellite cooperation on account of contractnet coordinate protocol， and implemented the decomposition anddistribution of reconnaissance tasks， took advantage of SAPA planner to achieve satellite operation planning in single agent. So as to enhance the mission planning system’s intelligence and autonomy.
Key words：multiagent technology; mission planning; multiple reconnaissance satellites; contract net
0 引言
現(xiàn)代戰(zhàn)爭對空間信息支持的依賴越來越大。由于戰(zhàn)場環(huán)境的不確定性和動態(tài)的變化，通過一兩顆或某一類偵察衛(wèi)星來獲取整個(gè)戰(zhàn)場的有用信息已遠(yuǎn)遠(yuǎn)不能滿足實(shí)際需求。多星組網(wǎng)進(jìn)行偵察和監(jiān)視，已成為偵察衛(wèi)星發(fā)展的一種必然模式。隨著衛(wèi)星作戰(zhàn)應(yīng)用需求的日益迫切，我國也開始研究將各種型號的偵察衛(wèi)星組網(wǎng)，組成多星偵察系統(tǒng)，以更快、更準(zhǔn)、更全面地獲得空間信息優(yōu)勢。
多星偵察系統(tǒng)采用多星組合偵察的工作模式，涉及各種型號的偵察衛(wèi)星和多個(gè)地面站間的協(xié)同工作，任務(wù)需求種類繁多，工作模式更加復(fù)雜。為完成特定的航天任務(wù)，對空間和時(shí)間上存在多種復(fù)雜約束的、一定數(shù)量的異（同）種偵察衛(wèi)星及地面站，采用合適的描述體系和相應(yīng)的規(guī)劃方法，在一定的時(shí)間要求下，實(shí)現(xiàn)對多星偵察系統(tǒng)的高效組織和優(yōu)化配置，以保證資源能最大化滿足任務(wù)的需求。
隨著人工智能和計(jì)算機(jī)技術(shù)的發(fā)展，在傳統(tǒng)的計(jì)劃協(xié)同系統(tǒng)基礎(chǔ)上應(yīng)用多agent系統(tǒng)技術(shù)，已逐漸成為實(shí)現(xiàn)自動化、智能化，以及盡量減少人的干預(yù)作為未來地面系統(tǒng)和空間系統(tǒng)開發(fā)研究的重要手段[1~3]。
本文將多agent系統(tǒng)理論引入到多星協(xié)同偵察任務(wù)規(guī)劃系統(tǒng)研究中，建立基于多agent的層次體系結(jié)構(gòu)，利用agent技術(shù)實(shí)現(xiàn)復(fù)雜協(xié)同任務(wù)的分解和分配。將多星的協(xié)同任務(wù)規(guī)劃轉(zhuǎn)換為單星任務(wù)規(guī)劃問題，在降低問題求解難度的同時(shí)，實(shí)現(xiàn)了較為靈活的系統(tǒng)結(jié)構(gòu)，方便利用重規(guī)劃技術(shù)實(shí)現(xiàn)動態(tài)的任務(wù)重規(guī)劃。
基于多agent結(jié)構(gòu)具有以下優(yōu)點(diǎn)：在執(zhí)行任務(wù)過程中，根據(jù)航天任務(wù)的變化、任務(wù)環(huán)境的變化以及航天資源的變化情況，從可用的航天資源中選擇、確定出最能適應(yīng)動態(tài)變化和任務(wù)需求的最佳航天資源動態(tài)聯(lián)盟及其相互協(xié)同關(guān)系，以實(shí)現(xiàn)航天資源的動態(tài)利用與高效管理。在一定的約束條件下，根據(jù)所涉及航天資源個(gè)體的能力，對航天資源進(jìn)行優(yōu)化配置，以保證航天資源配置方案能最大化滿足任務(wù)的需求。
此外，本文提出的基于多agent系統(tǒng)結(jié)構(gòu)，不僅適用于偵察衛(wèi)星資源的規(guī)劃，對于解決其他類型的航天資源的任務(wù)規(guī)劃問題也具有一定的借鑒作用。
1 基于MAS系統(tǒng)的特點(diǎn)
多星協(xié)同偵察任務(wù)規(guī)劃系統(tǒng)采用基于MAS的技術(shù)構(gòu)建。具有以下特點(diǎn):
a)降低多星協(xié)同偵察任務(wù)規(guī)劃問題的求解難度。當(dāng)前的規(guī)劃器如SAPA[4，5]、LPG[6]等，在求解規(guī)模較小的問題時(shí)體現(xiàn)出較好的性能。但對于涉及多衛(wèi)星多地面站的協(xié)同偵察任務(wù)規(guī)劃問題，則不能得到滿意的規(guī)劃結(jié)果。解決這個(gè)問題的方法包括：采用分布式的求解方式代替原有的集中式求解方式，對復(fù)雜問題進(jìn)行分解，從而降低問題求解難度；研究更為高效的規(guī)劃器。
b）具有在線重規(guī)劃能力。航天資源具備適應(yīng)不斷變化的戰(zhàn)場環(huán)境的能力，因此時(shí)間因素是一個(gè)重要的指標(biāo)。一般來說，大多數(shù)規(guī)劃方法都采用分段優(yōu)化，每個(gè)優(yōu)化時(shí)間段持續(xù)相當(dāng)長一段時(shí)間，所以可以將規(guī)劃看做是離線處理的。基于MAS構(gòu)建系統(tǒng)能夠?qū)崿F(xiàn)近實(shí)時(shí)的在線規(guī)劃，通過智能體之間的協(xié)商將任務(wù)分配到各agent；agent在完成任務(wù)之后，向上層返回任務(wù)執(zhí)行結(jié)果，如果任務(wù)執(zhí)行不成功，則開始新一輪的多agent協(xié)商，由MAS對該任務(wù)進(jìn)行重新的任務(wù)分配。如此往復(fù)處理，實(shí)現(xiàn)在線重規(guī)劃。
c）對動態(tài)的戰(zhàn)場環(huán)境具有更好的動態(tài)響應(yīng)能力。提高系統(tǒng)的響應(yīng)速度，使航天系統(tǒng)能更好地在瞬息萬變的戰(zhàn)場條件下完成任務(wù)。基于MAS構(gòu)建系統(tǒng)能夠適應(yīng)系統(tǒng)的交互協(xié)作、異步執(zhí)行和不完整信息推理等功能，因此在多星協(xié)同偵察任務(wù)規(guī)劃系統(tǒng)中采用MAS技術(shù)可以大大提高其協(xié)作求解能力，使其具有更好的靈活性、更高的效率和更強(qiáng)的魯棒性，適應(yīng)環(huán)境的實(shí)時(shí)動態(tài)變化要求。
2 基于MAS的系統(tǒng)體系結(jié)構(gòu)
在不確定性戰(zhàn)場環(huán)境下，多星協(xié)同偵察任務(wù)規(guī)劃系統(tǒng)的體系結(jié)構(gòu)在很大程度上決定了系統(tǒng)的作戰(zhàn)效率和靈活性。對體系結(jié)構(gòu)的設(shè)計(jì)和選擇應(yīng)能滿足以下幾方面的要求：良好的伸縮性、高魯棒性、高可靠性、快速反應(yīng)能力、動態(tài)重構(gòu)能力和良好的容錯(cuò)能力。
目前，MAS系統(tǒng)的體系結(jié)構(gòu)通常有集中式、有中心節(jié)點(diǎn)的分布式、無中心節(jié)點(diǎn)的分布式三種形式[3]。本文提出的MAS系統(tǒng)采用有中心節(jié)點(diǎn)的多星偵察分布式體系結(jié)構(gòu)，以平衡集中式和分布式兩種結(jié)構(gòu)的優(yōu)點(diǎn)和不足，適應(yīng)多星偵察系統(tǒng)復(fù)雜、開放的特性。系統(tǒng)由一個(gè)管理服務(wù)agent和多個(gè)衛(wèi)星規(guī)劃agent構(gòu)成。其中，集中式的管理服務(wù)agent一方面實(shí)現(xiàn)基于規(guī)則的任務(wù)分解；另一方面通過與衛(wèi)星規(guī)劃agent之間的協(xié)商完成任務(wù)的分配。
衛(wèi)星規(guī)劃agent分布在各顆衛(wèi)星上，負(fù)責(zé)對管理服務(wù)agent發(fā)布的任務(wù)進(jìn)行投標(biāo)，中標(biāo)的任務(wù)即為衛(wèi)星需要執(zhí)行的任務(wù)，由衛(wèi)星規(guī)劃agent上集成的規(guī)劃器對中標(biāo)任務(wù)進(jìn)行規(guī)劃，并將執(zhí)行結(jié)果返回管理服務(wù)agent。此外，由于規(guī)劃器采用的是標(biāo)準(zhǔn)的規(guī)劃建模語言PDDL[7]，衛(wèi)星規(guī)劃agent還負(fù)責(zé)將需要執(zhí)行的偵察任務(wù)轉(zhuǎn)換為規(guī)劃器可以識別的形式，作為規(guī)劃器的輸入。即對獲得的偵察任務(wù)要素表示為PDDL的問題文件和領(lǐng)域文件的形式。
系統(tǒng)體系結(jié)構(gòu)如圖1所示。系統(tǒng)的輸入包括航天任務(wù)需求和可用的航天資源集合。航天任務(wù)需求主要來源于各個(gè)用戶的偵察需求，其中有些任務(wù)可能需要多星多地面站之間的協(xié)同工作才能實(shí)現(xiàn)。航天任務(wù)需求需要采用規(guī)范化的任務(wù)描述方法對任務(wù)進(jìn)行建模才能作為系統(tǒng)的輸入。而可用的航天資源集合主要包括各種型號的偵察衛(wèi)星及其有效載荷以及衛(wèi)星系統(tǒng)的狀態(tài)信息等，在系統(tǒng)中一個(gè)可用的航天資源數(shù)據(jù)庫維護(hù)這些信息。在規(guī)劃開始和進(jìn)行過程中提供任務(wù)規(guī)劃必需的衛(wèi)星狀態(tài)信息。系統(tǒng)輸出的是多星協(xié)同偵察任務(wù)規(guī)劃方案。
3 任務(wù)的分解和分配
3.1 任務(wù)分解
任務(wù)分解一方面可在規(guī)劃開始之前的預(yù)處理階段由人工進(jìn)行判別；另一方面也可借助智能體的相關(guān)技術(shù)，定義任務(wù)分解方法庫，通過定義一定的規(guī)則和分解策略，實(shí)現(xiàn)任務(wù)的分解。
任務(wù)分解模塊主要是依據(jù)基于規(guī)則的策略對復(fù)雜的協(xié)同任務(wù)進(jìn)行分解，將偵察任務(wù)分解為一系列能夠由偵察衛(wèi)星執(zhí)行的任務(wù)。對于復(fù)雜的多星偵察系統(tǒng)的任務(wù)規(guī)劃，其任務(wù)分解是逐級進(jìn)行的，分解粒度為單星可執(zhí)行的任務(wù)。任務(wù)分解的原則是：任務(wù)規(guī)劃的任務(wù)目標(biāo)明確，并且最小化任務(wù)相關(guān)性以減少通信量、潛在的沖突和解決沖突所需要的時(shí)間，以便提高問題求解的效率。根據(jù)多星偵察系統(tǒng)任務(wù)規(guī)劃問題的分布性、層次性和相關(guān)性的特點(diǎn)，理論上可以從單顆偵察衛(wèi)星的能力和特性、偵察任務(wù)類型和時(shí)間等方面對問題進(jìn)行分解。
1）基于偵察任務(wù)類型的任務(wù)分解 偵察任務(wù)包括不同的類型，如目標(biāo)確認(rèn)、攻擊、毀傷評估等。不同的偵察任務(wù)對于衛(wèi)星成像分辨率和圖像類型等重要屬性參數(shù)的要求也不同，從而對應(yīng)著不同類型的偵察衛(wèi)星及星載遙感器。
2）基于單顆偵察衛(wèi)星能力和特性的任務(wù)分解 各種偵察衛(wèi)星往往具有不同的用途，同一用途的偵察衛(wèi)星也可能包括不同的型號。對于可能需要多顆不同類型或型號的偵察衛(wèi)星協(xié)同偵察的任務(wù)，可以考慮依據(jù)單顆衛(wèi)星的偵察能力和特性進(jìn)行分解。
3）基于時(shí)間的任務(wù)分解 同一類型的任務(wù)也分布在不同的地理位置并具有不同的時(shí)間要求，還有一些任務(wù)是具有時(shí)間周期性的偵察任務(wù)，可依據(jù)時(shí)間的先后順序?qū)θ蝿?wù)進(jìn)行分解。
多星協(xié)同偵察任務(wù)規(guī)劃系統(tǒng)的任務(wù)分解是一個(gè)比較復(fù)雜的問題，必須綜合應(yīng)用上述三種分解方法。依據(jù)上述三種方法生成基于規(guī)則的任務(wù)分解方法庫，并具有記錄歷史知識的功能。因此對于一個(gè)協(xié)同任務(wù)，可以通過查找任務(wù)分解方法庫中定義的合適的分解規(guī)則進(jìn)行綜合分解，一直進(jìn)行到每個(gè)子任務(wù)均可以由單顆偵察衛(wèi)星執(zhí)行為止，從而得到一個(gè)任務(wù)分解樹。如圖2所示，任務(wù)樹的根節(jié)點(diǎn)T為總?cè)蝿?wù)，T={T11，T12，T21，T22，T31}。其中：T中的任務(wù)均為可以直接由單顆偵察衛(wèi)星執(zhí)行的任務(wù)。同層節(jié)點(diǎn)間是與/或關(guān)系，弧線表示其子節(jié)點(diǎn)為“與”子節(jié)點(diǎn)，其他為“或”子節(jié)點(diǎn)，利用此方法可以把復(fù)雜的任務(wù)分解為一組較簡單的任務(wù)。
3.2 改進(jìn)合同網(wǎng)的任務(wù)分配
一般的合同網(wǎng)協(xié)議應(yīng)用于多星協(xié)同任務(wù)分配時(shí)，存在以下幾個(gè)方面的不足：a）任務(wù)通知對象沒有針對性，管理服務(wù)agent需要將招標(biāo)信息以廣播方式發(fā)送給系統(tǒng)中的所有衛(wèi)星規(guī)劃agent，造成系統(tǒng)通信頻繁，管理服務(wù)agent須對大量投標(biāo)申請作出評價(jià)，造成負(fù)載過重；b）合同的確認(rèn)和反復(fù)較費(fèi)時(shí)；c）投標(biāo)者知識更新不便；d）后繼學(xué)習(xí)困難。
針對以上不足，結(jié)合多星協(xié)同偵察任務(wù)規(guī)劃系統(tǒng)的特性，對合同網(wǎng)作如下改進(jìn)：
a）確定投標(biāo)者范圍。建立agent聯(lián)盟。管理服務(wù)agent在本地具有維護(hù)衛(wèi)星規(guī)劃agent能力和屬性信息的知識庫。可以在公布招投標(biāo)信息之前挑選出能夠處理該任務(wù)的若干候選agent，然后將投標(biāo)信息發(fā)送給這部分衛(wèi)星規(guī)劃agent。
b）投標(biāo)限定條件。假定衛(wèi)星規(guī)劃agent投標(biāo)時(shí)提供的各種信息都是真實(shí)有效的，以提高合同成功率，避免二次選擇。
c）Agent能力信息的更新。記錄合作信息到歷史知識庫，同時(shí)修改投標(biāo)者對這方面問題的解決能力等數(shù)據(jù)，以備后用。
基于合同網(wǎng)的任務(wù)分配流程如圖3所示。管理服務(wù)agent進(jìn)行任務(wù)分解后，向合同網(wǎng)中相關(guān)衛(wèi)星規(guī)劃agent廣播有關(guān)任務(wù)的投標(biāo)信息；接到招標(biāo)書的衛(wèi)星規(guī)劃agent檢查自己對解決該任務(wù)的能力，然后發(fā)出投標(biāo)申請成為投標(biāo)者；最后由管理服務(wù)agent對收到的投標(biāo)申請進(jìn)行評估并從中選擇最合適的投標(biāo)者作為中標(biāo)者，將任務(wù)分配給它。衛(wèi)星規(guī)劃agent接收招標(biāo)信息，對適合自己的偵察任務(wù)返回投標(biāo)書，并與管理服務(wù)agent簽訂合同，兩者構(gòu)成合同關(guān)系，完成任務(wù)分配。
4 基于SAPA規(guī)劃器的衛(wèi)星規(guī)劃agent
衛(wèi)星規(guī)劃agent主要包括以下功能：
a）通過與管理服務(wù)agent間的招投標(biāo)獲得需要執(zhí)行的偵察任務(wù)。
b）在任務(wù)執(zhí)行結(jié)束后向管理服務(wù)agent返回任務(wù)執(zhí)行結(jié)果。如果執(zhí)行成功，則返回衛(wèi)星執(zhí)行該任務(wù)的行動序列。如果不能完成任務(wù)，則返回任務(wù)失敗的原因，由管理服務(wù)agent發(fā)起新一輪的任務(wù)分配，對任務(wù)重新分配。
c）星上自主規(guī)劃。給出任務(wù)對應(yīng)的偵察衛(wèi)星的行動序列。其過程如圖4所示。
SAPA規(guī)劃器是由Minh Binh Do等人開發(fā)的應(yīng)用于衛(wèi)星任務(wù)規(guī)劃領(lǐng)域的高效規(guī)劃器，能夠高效地處理復(fù)雜的時(shí)間和資源約束。其規(guī)劃引擎采用目前規(guī)劃領(lǐng)域定義域模型的標(biāo)準(zhǔn)語言PDDL定義。PDDL是由國際規(guī)劃大賽（IPC）[7]開發(fā)的，包括STRIPS、ADL 以及其他規(guī)劃子語言，是一種命題式描述機(jī)制的域描述語言。該語言是通過定義對象、謂詞、初始狀態(tài)、目標(biāo)說明、動作五種成分來建立規(guī)劃模型的。PDDL具有通用性、不依賴問題領(lǐng)域等優(yōu)點(diǎn)。
SAPA規(guī)劃器采用Java語言實(shí)現(xiàn)，具有平臺無關(guān)性、方便集成到衛(wèi)星規(guī)劃agent等優(yōu)點(diǎn)。此外，由于代碼開源，用戶可以在標(biāo)準(zhǔn)的PDDL語言的實(shí)現(xiàn)框架下，方便地將自定義的規(guī)劃域模型和相關(guān)的規(guī)劃算法進(jìn)行修改，以適應(yīng)特點(diǎn)問題研究的需要。
如圖4所示，衛(wèi)星規(guī)劃agent將需要執(zhí)行的偵察任務(wù)集合作為輸入，利用問題產(chǎn)生器將分配的任務(wù)翻譯為規(guī)劃器可以識別的形式，即PDDL語言定義的領(lǐng)域文件和問題文件形式，作為SAPA規(guī)劃器的輸入。其中，領(lǐng)域文件定義謂詞和動作；問題文件定義對象、初始狀態(tài)和目標(biāo)說明。
5 結(jié)束語
在許多領(lǐng)域，多agent 系統(tǒng)已經(jīng)被廣泛研究用來提供分布式系統(tǒng)的智能行為。本文采用多agent 系統(tǒng)的分布式問題求解思想，建立了多星協(xié)同偵察任務(wù)規(guī)劃系統(tǒng)的MAS 結(jié)構(gòu)，深入研究了任務(wù)分解、任務(wù)分配和單星自主規(guī)劃等關(guān)鍵技術(shù)。這種基于多agent協(xié)商方式的分布式任務(wù)規(guī)劃方法能降低問題的求解難度，還能對動態(tài)觀測作出快速反應(yīng)，具有在線重規(guī)劃能力，從而提高了整個(gè)系統(tǒng)的自主決策能力。
此外，本文提出的基于多agent系統(tǒng)結(jié)構(gòu)，不僅適用于偵察衛(wèi)星資源的規(guī)劃，對于解決其他類型的航天資源的任務(wù)規(guī)劃問題也具有一定的借鑒作用。
參考文獻(xiàn)：
［1］張正強(qiáng)，譚躍進(jìn)，王軍民. 基于MAS的分布式衛(wèi)星系統(tǒng)任務(wù)規(guī)劃研究[J].系統(tǒng)仿真學(xué)報(bào)，2007，19(12):28682871.
[2]王紅飛，李緒志，陳立軍. 基于multiagent 的衛(wèi)星計(jì)劃調(diào)度系統(tǒng)智能機(jī)制[J].計(jì)算機(jī)工程， 2006，32(22):194196.
[3]RUSSELL S，NORVIG P. Artificial intelligence: a modern approach[M].Upper Saddle River: Prentice Hall，2004.
[4]DO M B， KAMBHAMPATI S. SAPA: a scalable multiobjective heuristic metric temporal planner[J]. Journal of Artificial Intelligence Research， 2003，20:155194.
[5]DO M B， KAMBHAMPATI S. Planning graphbased heuristics for costsensitive temporal planning[C]//Proc of the 6th International Conference on Artificial Intelligence Planning and Scheduling. 2002:312.
[6]GUETTIER C， PONCET J C. Multilevels planning for spacecraft autonomy[C]//Proc of the 6th International Symposium on Artificial Intelligence， Robotics and Automation in Space. 2001.
[7]EDELKAMP S， HOFFMANN J. PDDL 2.2: the language for the classical part of the 4th international planning competition， Tech. Rep.195[R]. Freiburg: Univ Inst Fur Informatik， 2004.
