多Agent航天自主運行系統的模型描述

顏 軍 李 勇

1.北京控制工程研究所，北京 100190 2.中國空間技術研究院，北京 100094

多航天器密切配合的航天系統，如分布式衛星、分離模塊衛星系統[1]，要及時協調多個航天器的工作，并處理各種不確定的問題，需要分布協同的自主運行系統。

自主運行系統要根據任務要求對系統的任務進行規劃，產生一系列的活動安排，從而完成任務目標。因此要對活動的條件及相互間的關系、活動對系統自身及環境的影響進行描述，所以模型描述是自主運行系統的基礎。

本文提出面向航天應用的多Agent自主運行系統模型描述方法，通過活動和方案兩級結構的模型，將多Agent之間的協調配合與Agent內部的規劃結合起來，方便實現局部的方案優化。設計類似C++語法的描述語言，實現了對模型的描述，并已應用于多Agent自主運行仿真系統。

1 規劃問題的描述方法介紹

規劃問題的模型描述，就是對規劃對象及其變化規律進行描述，使問題得到標準化的抽象，以便使用通用的規劃方法來求解。由計算機來實現規劃問題的求解，需要使用描述語言將規劃知識轉化為知識文件。計算機組織和處理這些知識和數據，需要相應的數據結構，這幾部分的關系見圖1。

圖1 規劃問題構成

求解規劃問題，一類方法是以集合或謂詞來描述狀態，根據初始狀態和目標狀態，找出一個動作序列來使對象狀態逐次從初始狀態變化到目標狀態。這是“基于狀態”的方法，如STRIPS[2]和PDDL[3]。這類方法的優點是方便描述前提條件間的“與”、“或”、“選擇”等關系。此類方法在機器人規劃領域使用較多，在航天領域多系統并行且包含時間、資源等多種約束關系，較少使用此類方法。另一類方法是以狀態變量(state variable)在不同時間區間上的取值來描述對象的狀態，狀態變量的取值是一些離散狀態值，比如“On”、“Off”、“Idle”等。狀態、資源都以時間線(timeline)的形式描述，體現它們隨時間的變化。動作對狀態、資源的依賴和影響，動作之間的約束關系通過模型加以描述。這種方法由于動作間的約束關系而稱為“基于約束”的規劃方法。這種描述模型的例子是ASPEN系統[4]中的AML描述語言[5]，其動作(活動)與狀態及資源間的約束關系模型見圖2。

圖2 考慮時間和資源、動作間有約束的規劃問題

RA系統使用的規劃方法也是基于約束的[6]，其特點是不再區分動作和狀態，而用狀態變量上的權標(token)來描述。一個時間區間(interval)上的狀態變量的取值，稱為一個token，token之間及token與資源變量之間存在約束關系。RA使用參數來描述Token，比如使用MoveTo(x,y)來表示向坐標(x,y)移動。參數的使用提高了描述的效率，同時也可以通過參數的運算、傳遞和約束來描述更為復雜的問題。

2 規劃問題模型描述的內容及要求

動作、狀態、時間、資源和參數是規劃問題的要素，其關系見圖3。動作是規劃問題的核心要素，狀態描述了對象，動作和狀態相互作用描述了對象的演變，動作受時間和資源的約束，動作之間有時間關系的約束，參數描述了動作的細節，參數之間也存在約束關系。

圖3 規劃問題要素及其關系

綜合考察各種規劃方法及描述方法，并根據航天領域的需要，歸納了規劃描述方法的內容要點和層次如圖4所示。在這些要點中，分解是一種約束關系，將一些動作組合起來，通過逐級細化來完成規劃。同一任務可以有幾種不同的分解，可根據實時情況選擇其中一種來進行規劃。過程性運算是指數學運算、函數運算等，可以用于參數間的運算。選擇性約束是約束條件間的“與”、“或”、“選擇”等邏輯關系。優先級是給動作賦予固定的或臨時的優先級，以便在發生規劃沖突時保留優先級高的任務。性能指標用來進行規劃的優化，如果任務的實現有不同的途徑，可以通過性能指標來衡量不同途徑的優劣。依據這些要點，可以考察和對比不同的描述模型，并根據需要來選擇和設計。

圖4 規劃描述方法的內容層次

描述語言使用規范的語法，提供人機接口，將規劃知識提供給計算機。描述語言大體分兩類：一類是以動作(action)為核心，主要對應 “基于動作-狀態”的方法；一類是以屬性(attribute)或時間線來組織描述語言，主要對應“基于約束”的方法。就描述語言的語法特征而言，一類是接近人工智能領域的描述語言，如PDDL[7]；一類如AML[4]，是接近C++這樣的通用編程語言。

用于規劃的數據結構主要有模型數據、狀態數據和計劃數據，這些數據可以獨立于描述語言和規劃算法，見圖5。只要將不同語言描述的模型，通過模型處理過程轉化為通用的數據結構即可為規劃算法使用。

圖5 規劃的模型描述與規劃運算的關系

針對多航天器系統的應用要求，自主運行系統基于多Agent，這就要求規劃模型描述要具備分布系統的特點，能夠描述多Agent系統中分布存在的規劃知識及其相互間的關系，使系統可以完成各Agent的自主規劃和多Agent之間的協同規劃。STRIPS和PDDL的后續版本提出了針對多Agent的模型描述，但不適于航天領域時間和資源約束的特點。AML將活動與狀態變量分開描述，約束關系體現在活動之間、活動與狀態變量及資源之間，關系比較清晰，也比較容易描述活動的分解。AML直接地描述了狀態變量的狀態值之間的轉換關系，但是狀態值沒有參數，也就沒有參數間的約束關系。RA的DDL描述，token之間的參數約束關系表達能力強，但由于直接使用了狀態變量上token之間的約束關系，雖然有統一了狀態與動作的優點，但是狀態轉換關系不明晰，且需要集中描述狀態變量的信息，限制了其應用于多Agent系統。AML有活動的分解，有性能指標用于優化，并以調用C語言函數的方式提供了有限的過程運算，DDL沒有這方面的功能。

3 多Agent自主運行系統的模型描述

多Agent自主運行系統(multi-agent autonomous running system, MARS)是基于Agent組織的，其中包括負責規劃的Agent(稱為“規劃Agent”)、負責執行的Agent(稱為“執行Agent”)等多種類型的Agent。自主運行系統以多個協同工作的規劃Agent為骨干，Agent由稱為Agent容器程序的軟件組織在一起，Agent容器程序負責多個Agent的管理和通信。

規劃Agent負責對特定的系統組成部分進行規劃，具有獨立的規劃能力，通過多個規劃Agent的相互配合實現系統的自主運行。規劃Agent用若干“屬性”(Attribute)來描述系統的組成部分，屬性又分為“配置屬性”和“資源屬性”，每個屬性通過時間線來記錄在不同時間的取值。配置屬性與執行Agent相聯系，配置屬性在一段時間區間的取值稱為“方案” (Scheme)，類似RA中狀態變量上的token，描述了系統特定部分的狀態或動作。方案包含參數，它對應了執行Agent中的控制或執行方案，規劃運算得到的計劃，就是由配置屬性上的方案組成。方案由規劃Agent輸出給執行Agent，執行Agent負責方案的執行。執行Agent在執行方案時具有局部的閉環處理措施，可以在一定范圍內根據實時的情況進行調整，因而具有自主性和魯棒性。資源屬性的取值一般是連續或離散的數值，用來約束對有限資源的占用。

“活動”是規劃Agent使用的主要的數據結構，描述了系統需要完成的一項工作。活動覆蓋的范圍比較寬，從系統接受的目標任務，到系統逐級分解給各Agent的子任務都以活動來描述。規劃Agent之間的交互以活動協商來實現，規劃Agent內部的分解及約束關系通過活動間的約束來描述。活動最終分解為配置屬性上的方案，并要占用資源屬性上一定數量的資源。規劃運算就是根據活動的約束關系，對配置屬性上的方案進行安排，并滿足資源約束的求解過程。

系統中使用的變量包括參數和一般變量，參數是描述活動和方案的，參數之間有運算、傳遞關系和約束關系。一般變量包括常規的數據類型，也可以包括一些自定義的結構數據類型。系統模型描述的層次和聯系見圖6。

規劃Agent之間通過活動的協商來實現協同配合，而配置屬性和資源屬性的規劃在各自的規劃Agent中完成，以實現規劃的分布性和局部的自主性。規劃Agent不必關注其他規劃Agent的屬性細節，只是根據其他規劃Agent的對活動協商的回復來調整和確定計劃。通過活動和方案兩級數據結構來實現規劃和執行的模型描述，規劃Agent之間使用活動來交互，規劃Agent內部解決約束并將活動落實為方案，規劃Agent與執行Agent之間通過方案實現規劃輸出。

在同一時間同一配置屬性上有且只有一種方案。為簡化方案間的約束關系，只定義同一配置屬性上的方案間的約束關系，不同配置屬性上的方案之間的關系通過其上級活動間的約束來體現。針對航天系統的實際情況，配置方案采用類似狀態轉移系統的描述，即同一配置屬性上的方案間有一定的銜接轉換關系，通過約束關系描述來體現，比如方案A可以銜接在方案B或方案C之后，而其后可以銜接方案D或方案E。相互銜接的方案之間，可以定義參數約束關系。

每個規劃Agent是相同的軟件組件，通過使用不同的知識描述文件使規劃Agent具有不同的知識、角色和功能。每個規劃Agent的知識描述文件中對與其發生作用的其他Agent進行角色說明，指明規劃Agent之間的關系以及角色與實體的對應關系、信息傳遞需求及途徑等。使用角色定義可以動態地組織和維護系統，同一個角色在不同的時間點可以指向不同的物理系統，可以通過更新這種角色的對應關系，實現多Agent組織的演變。

規劃Agent的知識描述文件中對其可以承擔的活動進行描述。活動有若干自身專用參數，同時還有時間區間、優先級等通用參數。活動的描述中包含該活動與其他活動的約束關系，比如前后 (Meets，Met by)、包含(Contains，Contained by)等時間約束關系[8]，分解關系等。在活動涉及與其他規劃Agent的協商時，要指明相關的Agent角色。例如，有效載荷Agent拍照的活動，要求姿態Agent保持目標指向，這里保持目標指向活動包含拍照活動是約束關系，姿態Agent是相關的Agent角色。上層的活動可以分解為底層的活動，底層活動的描述涉及配置屬性上的方案和占用的資源。

為了對方案進行局部優化，定義了方案的能量級參數或者說在選用方案時的偏好值，比如方案A能量級為2，方案B的能量級為3，表明方案B的能量消耗更大一些，那么在同樣滿足系統需求的前提下，優先選擇方案A。當沒有明確的需求時，配置屬性就執行缺省方案，缺省方案能量級最低，定義為1。

在活動和方案的描述中，有一些參數的運算，如時間長度和資源需求量的計算，是和具體的活動或方案的參數相關的。所以活動和方案的說明中包含一些過程性運算，復雜的運算還可以使用專門的運算Agent，通過Agent之間的函數調用來實現。

規劃活動中的選擇性約束，通過約束項的分組來實現，同組中的約束項是可選關系，包括“3選2”這樣的多選，不同組之間是“與”的關系。當一種活動不可行時，可以根據分組約束采用其他可選的活動來實現。

多Agent自主運行系統的描述方法中的活動與AML中的活動的區別是，這里的活動不僅在Agent內部進行分解，更重要的是承擔Agent之間的協調和約束的功能。配置方案的設計參考并擴展了RA系統的token的概念，并且為適應航天應用使用了類似狀態變換關系的方案間銜接約束。由于結合了RA與ASPEN的模型描述方法并改進了規劃分解、過程性運算和優化指標，增加了選擇性約束和多Agent組織關系描述，所以自主運行系統描述方法可以滿足多Agent結構下協同規劃及工作的需求。

4 知識描述語言的設計

這里定義的描述語言稱為Agent知識描述語言(Agent Knowledge Description Language, AKDL)，是通用的描述語言，主要應用于描述規劃Agent的知識，其他類型的Agent也可以用它來描述配置。每個規劃Agent有一個文本形式的知識文件，由知識處理模塊處理成為規劃Agent的知識存儲在知識庫中。

AKDL使用接近C++語言的語法及基本符號，使用簡單數據類型、類和預定義函數來描述規劃模型。使用與C++語言相同的表達式，方便定義一些過程性的運算和函數調用。簡單數據類型，包括浮點數float、整型數int及其數組等，用來定義參數和變量。

預先定義的類，主要有以下幾種：CThisAg是Agent說明，CCoopAg是相關Agent角色定義，CConfig是配置屬性類、CResource是資源屬性類、CActivity是活動類、CScheme是方案類。類的描述比較復雜，可以用(param1,param2,…)來定義參數，對于活動和方案則在{…}中包含參數設置、約束關系描述等豐富的內容。如CScheme cfAttd::scLock(float fAngle[3])定義了一個配置屬性cfAttd上的方案scLock，其參數是一個包含3個浮點數的數組。

使用預定義函數(或者稱為關鍵字函數)來實現一些特定的功能，類似于其他知識描述語言的關鍵字(保留字)。對約束關系，協商行為，以及Agent組織、角色、交互的描述等都采用了預定義函數的方式。活動、方案的實例也使用帶參數的函數的方式，此外活動、方案或函數的實例也可以作為預定義函數中的參數。在語句fpFnEx(agFunc,fnFunc02 (&iDura, fAngleFr,fAngleTo))中，fpFnEx是預定義函數，表示調用運算Agent的函數，參數agFunc是運算Agent的名稱，fnFunc02(&iDura,fAngleFr, fAngleTo)是含參數的函數調用實例，在這里整體作為一個參數項。

規劃Agent的知識文件，主要由3部分構成，分別是 Agent說明、活動說明、方案說明，其具體內容見表1。

舉一個應用的例子，系統是由4顆衛星組成的編隊，每顆衛星和地面站在軟件上對應一個Agent容器程序，每個容器程序包含若干Agent。衛星1的容器程序中包含AgSatsPlan，AgSat1Plan，AgSat1Attd，AgSat1Orbt，AgSat1Imag，分別是編隊規劃、衛星1的規劃，衛星1的姿態分系統、軌道分系統、拍照分系統的規劃Agent，部分知識文件內容見表1中的舉例。

在表1的Agent說明中，為AgSat1Plan中定義了4個相關Agent角色，定義了電源和存儲器2個資源屬性。在活動說明中，拍照活動acGetImg涉及3個Agent的配合，并占用電源和存儲器的資源。在acGetImg中包含參數fAngle，iSet1，iSet2的傳遞、變量fUsedMem的聲明及過程性運算。

預定義函數fpParm用于為活動或方案的參數賦值；fpResc指明資源消耗；fpBehv用于指明活動之間或活動與方案之間的約束關系，可以定義選擇性的約束關系；fpSelf用于指明方案間的銜接約束。

在方案說明中，為每種方案定義能量級參數及配置屬性的缺省方案，如fpParm(Cost,2)定義能量級別為2，而fpDeft(cfAttd, scLock(0.0,0.0,0.0))定義了配置屬性cfAttd的缺省方案是scLock(0.0,0.0,0.0)。

表1 規劃Agent知識文件的構成

根據實際需要，AKDL對參數及其關系的描述使用了一些特殊方法。活動或方案中的常用參數，將作為固有參數，比如iDura表示方案的時長，在運算中直接使用。方案中不能單獨確定，需要與相鄰的方案共同確定的參數用“?”來代表，比如fpSelf(MetBy, scChange(?, ?, ?, fAngle))表示轉向的起始角度要由前一個方案來決定。參數設置中不加約束的項用“*”表示，如在fpParm(PmTm,1000, 1000,*)中表示方案的時間長度沒有上限。

通過應用的例子可以看出AKDL可以對各種規劃知識，包括描述性的參數設置及交互、約束關系、過程性的運算及函數調用進行方便靈活的描述。

5 結束語

以文中的描述方法為基礎，已經構建了多Agent的自主運行仿真系統AgSimu，實現了知識文件的處理，對多個Agent的角色、相互關系、規劃知識進行了描述，對多個航天器協同配合場景進行了仿真。體現了該模型描述方法的通用性與靈活性，可以方便地使用通用Agent組件快速建立起多Agent組織，展開仿真工作。

多Agent自主運行系統的模型描述，是多Agent自主運行系統的基礎。文中的描述方法采用配置屬性上的方案來描述系統的設置狀態，在參數傳遞、過程性運算、方案間銜接約束關系、方案的能量參數定義等方面功能豐富而靈活。使用活動-方案兩級的模型描述，多Agent之間通過活動進行交互和協商，在Agent內部通過安排方案和資源來落實活動，劃分了Agent之間和Agent內部的規劃職責，提高了規劃Agent的自主性，減少了Agent之間的交互代價。

描述語言采用類似C++語法，可以通過擴展預定義類和函數來擴展語言的功能，兼具描述性和過程性的語言描述能力，便于定義過程性的運算。描述語言增加了針對多Agent系統組織關系及交互信息的描述以適合多Agent系統的組織和配置。

[1] Lobosco D M, Cameron G E, Golding R A, et al.Pleiades Fractionated Space System Architecture and the Future of National Security Space[C].AIAA Space Conference & Exposition, San Diego, California, 2008.

[2] Nilsson N J, Fikes R E.STRIPS：A New Approach to the Application of Theorem Proving to Problem Solving [J].Artificial Intelligence, 1971,2(3): 189-208.

[3] Maria F, Derek L.PDDL2.1:An Extension to PDDL for Expressing Temporal Planning Domains[J].Journal of Artificial Intelligence Research,2003,(20):61-124.

[4] Fukunaga A, Rabideau G, Chien S, Yan D.ASPEN：A Framework for Automated Planning and Scheduling of Spacecraft Control and Operations [C].International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS), Tokyo, Japan, 1997.

[5] Smith B, Sherwood R, Govindjee A, et al.Representing Spacecraft Mission Planning Knowledge in ASPEN[C].Artificial Intelligence Planning Systems Workshop on Knowledge Acquisition, Pittsburgh, PA, 1998.

[6] Muscettola N, Nayak P P, Pell B, Williams B C.Remote Agent: to Boldly Go Where No AI System Has Gone Before [J].Artificial Intelligence, 1998,(103):5-47.

[7] Ghallab M, Howe A, Knoblock C, et al.PDDL -The Planning Domain Definition Language Version 1.2[C].Artificial Intelligence Planning and Scheduling Conference(AIPS’98), Pittsburgh，Pennsylvania, 1998.

[8] Allen J F, Koomen J A.Planning Using a Temporal World Model[C].The 8thInternational Joint Conference on Artificial Intelligence，Karlsruhe, Germany,1983.