基于動態(tài)智能體交互圖的深空探測器任務(wù)規(guī)劃方法

趙宇庭，徐 瑞，李朝玉，朱圣英

（1. 北京理工大學(xué) 宇航學(xué)院, 北京 100081；2. 深空自主導(dǎo)航與控制工信部重點實驗室, 北京 100081）

引 言

隨著空間中航天器數(shù)量增長和航天任務(wù)的日益復(fù)雜，地面站的管控壓力不斷增大，從而產(chǎn)生了對航天器規(guī)劃技術(shù)的需求。地面自動規(guī)劃能快速生成規(guī)劃方案，提高航天器的管控效率；在軌自主規(guī)劃能賦予航天器自我管理能力，減輕地面管控壓力。

國內(nèi)外機(jī)構(gòu)和學(xué)者已經(jīng)對航天器規(guī)劃技術(shù)展開研究。美國國家航空航天局（National Aeronautics and Space Administration）開發(fā)了可擴(kuò)展標(biāo)準(zhǔn)化遠(yuǎn)程操作規(guī)劃框架（Extensible Universal Remote Operations Planning Architecture，EUROPA）[1-2]，該框架內(nèi)的時間網(wǎng)絡(luò)模塊負(fù)責(zé)傳播時間約束并保持規(guī)劃解的時間一致性，資源管理模塊負(fù)責(zé)處理存儲能源等數(shù)值資源約束。EUROPA在多個航天器上得到了應(yīng)用，包括哈勃望遠(yuǎn)鏡的觀測調(diào)度[3]，“深空一號”（Deep Space 1）[4]和“地球觀測一號”（Earth Observing-1）的自主控制[5]。

自主規(guī)劃和調(diào)度環(huán)境（Automated Scheduling and Planning Environment,，ASPEN）[6]是美國噴氣推進(jìn)實驗室（JPL）的人工智能小組開發(fā)的一個可重構(gòu)規(guī)劃調(diào)度框架，采用基于沖突修復(fù)的規(guī)劃方法。連續(xù)活動調(diào)度規(guī)劃執(zhí)行和重規(guī)劃系統(tǒng)（Continuous Activity Scheduling Planning Execution and Replanning，CASPER）[7]是ASPEN的軟實時星上規(guī)劃版本，能夠在環(huán)境變化或目標(biāo)變化后快速進(jìn)行重新規(guī)劃。

以上3個規(guī)劃系統(tǒng)都采用狀態(tài)時間線知識表示方法，適合描述探測器的時間資源約束知識，可通過在搜索算法中加入啟發(fā)式提高規(guī)劃效率。金顥等[8]提出了基于狀態(tài)轉(zhuǎn)移圖的啟發(fā)式加速規(guī)劃搜索。王曉暉等[9]設(shè)計時間線啟發(fā)式因子引導(dǎo)規(guī)劃擴(kuò)展過程，提高任務(wù)規(guī)劃效率。

除了設(shè)計啟發(fā)式，利用深空探測器子系統(tǒng)分布并行的特性，將子系統(tǒng)抽象為智能體，采用多智能體任務(wù)規(guī)劃方法，也能夠提高規(guī)劃效率。在領(lǐng)域無關(guān)規(guī)劃（domain-independent planning）的研究中，多智能體規(guī)劃是一個重要分支。Brafman和Domshlak[10]量化表示了MA-STRIPS（Multi-Agent Stanford Research Institute Problem Solver）問題中智能體之間的耦合程度，證明多智能體規(guī)劃問題的復(fù)雜度主要與智能體間耦合程度相關(guān)。MADLA（Multi-Agent Distributed and Local Asynchronous）[11]規(guī)劃器針對MA-STRIPS問題提出了分布式狀態(tài)空間前向鏈?zhǔn)蕉鄦l(fā)式搜索方法。FMAP（Forward Multi-Agent Planning）[12]為了表示狀態(tài)變量采用PDDL3.1描述領(lǐng)域知識，并提出一種啟發(fā)式前向鏈?zhǔn)狡蛞?guī)劃方法。這些規(guī)劃器雖然致力于解決多智能體規(guī)劃問題，但缺乏對時間、資源等數(shù)值約束的表達(dá)和處理能力[13]。徐瑞等[14]提出了一個用于航天器的多智能體規(guī)劃器，能夠處理時間資源約束，采用有中心的多智能體分布式規(guī)劃，設(shè)置管理智能體作為其它智能體通信和協(xié)作的中心。

深空探測器與地球距離遙遠(yuǎn)，傳統(tǒng)的規(guī)劃后再上傳指令的控制方式會造成較長的時間延遲，因此需要研究自主規(guī)劃技術(shù)以提高探測器的決策效率和任務(wù)收益。深空探測器任務(wù)規(guī)劃存在領(lǐng)域知識復(fù)雜、時間資源約束復(fù)雜、子系統(tǒng)多、任務(wù)目標(biāo)多等難點。

本文的研究目的是探索應(yīng)用于復(fù)雜多系統(tǒng)探測器的高效規(guī)劃方法，主要思想是結(jié)合多智能體規(guī)劃高效率的優(yōu)勢和經(jīng)典航天器規(guī)劃器的數(shù)值處理能力，提出基于動態(tài)智能體交互圖的深空探測器任務(wù)規(guī)劃架構(gòu)與方法。

本文建立基于狀態(tài)時間線的多智能體規(guī)劃問題模型，并為實現(xiàn)探測器各系統(tǒng)活動及數(shù)值約束知識的表示而設(shè)計了相應(yīng)的多智能體規(guī)劃建模語言。提出基于分布式求精搜索的多智能體規(guī)劃空間規(guī)劃方法，不設(shè)置管理智能體作為協(xié)調(diào)中心，而是設(shè)計動態(tài)智能體交互圖引導(dǎo)多智能體協(xié)同規(guī)劃，并采用基于圖論的方法處理探測器的時間和資源約束。最后，通過仿真實驗驗證了方法的有效性。

1 探測器多智能體規(guī)劃問題建模

由于狀態(tài)時間線模型具有復(fù)雜時間資源約束的描述能力，較為適合深空探測器規(guī)劃問題建模，本文在時間線模型基礎(chǔ)上建立多智能體規(guī)劃問題模型。

定義1. 狀態(tài)變量是表示智能體狀態(tài)的變量，可定義為

定義2.狀態(tài)是狀態(tài)變量的取值，可定義為

定義3.狀態(tài)時間線是狀態(tài)變量不同取值在時間上的連續(xù)分布，表示智能體的狀態(tài)在規(guī)劃周期內(nèi)隨時間變化的情況，可定義為

定義4.智能體是一個規(guī)劃單元，依據(jù)問題需求和領(lǐng)域知識進(jìn)行規(guī)劃，可定義為

定義5.多智能體規(guī)劃問題：為包含n個多智能體的集合，S為所有智能體的狀態(tài)變量集合，I為各狀態(tài)變量初始值集合，G為各狀態(tài)變量目標(biāo)值集合，多智能體規(guī)劃問題可表示對于每一個智能體， 規(guī)劃問題為

對于深空探測器任務(wù)規(guī)劃，探測器的子系統(tǒng)和載荷可抽象為智能體，探測器各系統(tǒng)的活動間的約束關(guān)系通過狀態(tài)的約束集合表示。

在具體的規(guī)劃實現(xiàn)中，需要設(shè)計建模語言，用建模語言描述領(lǐng)域知識和規(guī)劃問題作為規(guī)劃器的輸入。NDDL（New Domain Description Language）是EUROPA采用的建模語言，具備對邏輯約束、時間約束和資源約束的表達(dá)能力，適合狀態(tài)時間線模型的知識表示。本研究對NDDL進(jìn)行多智能體化的擴(kuò)展，設(shè)計多智能體數(shù)值領(lǐng)域建模語言（Multi-Agent Numeric Domain Modelling Language，MANDML）。

MANDML繼承了NDDL的功能，并加入多智能體系統(tǒng)所需的元素。

首先，加入智能體的概念，將探測器的子系統(tǒng)抽象為智能體。在規(guī)劃器輸入中添加智能體定義文件，其中包含所有智能體的名稱和編號，作為規(guī)劃過程中智能體相互通信的標(biāo)識。假設(shè)探測器有載荷系統(tǒng)（LoadSys）和姿態(tài)系統(tǒng)（AttitudeSys）兩個系統(tǒng)需要規(guī)劃，那么可以定義兩個智能體。智能體定義文件的內(nèi)容如下所示：

然后，設(shè)計適用于多智能體規(guī)劃的文件輸入模式。規(guī)劃智能體輸入相同的智能體定義文件和模型文件，從而使每個規(guī)劃智能體對探測器的各系統(tǒng)組成和狀態(tài)間的約束關(guān)系有一致的認(rèn)識。各規(guī)劃智能體的問題文件是獨立的，只包含當(dāng)前智能體的初始狀態(tài)和目標(biāo)狀態(tài)。比如，對于Agent 1，輸入的只有載荷分系統(tǒng)的初始和目標(biāo)狀態(tài)。以包含兩個規(guī)劃智能體的多智能體規(guī)劃系統(tǒng)為例，兩個規(guī)劃智能體的所有的輸入如圖1所示。

圖1 規(guī)劃智能體輸入文件示意Fig. 1 Inputs of planning agents

2 多智能體規(guī)劃空間規(guī)劃方法

提出一種多智能體規(guī)劃空間規(guī)劃方法。不設(shè)置管理智能體協(xié)調(diào)各智能體規(guī)劃，而是設(shè)計動態(tài)智能體交互圖作為多智能體交互的規(guī)則，引導(dǎo)規(guī)劃搜索的路徑在多智能體間擴(kuò)展。構(gòu)建多智能體時間約束網(wǎng)絡(luò)模型，采用圖的最短路徑算法實現(xiàn)時間約束傳播與解耦。構(gòu)建資源約束網(wǎng)絡(luò)模型，采用基于圖最大流的算法處理資源約束。

2.1 動態(tài)智能體交互圖

智能體基于狀態(tài)間的約束關(guān)系在規(guī)劃中展開協(xié)作。在當(dāng)前部分規(guī)劃中成功加入一個狀態(tài)后，此狀態(tài)的約束集合中的其它狀態(tài)也要隨之加入到部分規(guī)劃當(dāng)中。例如，相機(jī)拍照之前需要姿態(tài)校準(zhǔn)，那么相機(jī)智能體的拍照狀態(tài)加入規(guī)劃后，姿態(tài)智能體的校準(zhǔn)狀態(tài)也要加入規(guī)劃，以滿足拍照狀態(tài)與校準(zhǔn)狀態(tài)的約束關(guān)系。

定義6.如果狀態(tài)a出現(xiàn)在狀態(tài)s的約束集合中，即，那么a為s的從屬狀態(tài)，s為a的主導(dǎo)狀態(tài)。

定義7.如果一個狀態(tài)a是狀態(tài)s的從屬狀態(tài)，狀態(tài)s屬于智能體A，但狀態(tài)a不屬于智能體A，即那么a為一個公共狀態(tài)，否則為私有狀態(tài)。

在某些多智能體規(guī)劃方法中，公共信息要對所有智能體公開，而在本研究設(shè)計的基于動態(tài)智能體交互圖的多智能體協(xié)同規(guī)劃方法中，公共狀態(tài)只需要向特定智能體公開，能夠提高智能體的私有性并降低通信代價。例如，拍照狀態(tài)的從屬狀態(tài)中包含姿態(tài)校準(zhǔn)狀態(tài)，而姿態(tài)校準(zhǔn)狀態(tài)顯然屬于姿態(tài)智能體而不屬于相機(jī)智能體，則姿態(tài)校準(zhǔn)狀態(tài)是相機(jī)智能體中的公共狀態(tài)。公共狀態(tài)在規(guī)劃中依據(jù)約束信息動態(tài)出現(xiàn)，當(dāng)前姿態(tài)校準(zhǔn)狀態(tài)為公共狀態(tài)不代表所有姿態(tài)校準(zhǔn)狀態(tài)都是公共狀態(tài)。

顯然，相機(jī)智能體不應(yīng)該在局部規(guī)劃中加入姿態(tài)校準(zhǔn)這個狀態(tài)，因為它屬于姿態(tài)智能體。在生成公共狀態(tài)的智能體中，它被視作一個不需要加入規(guī)劃的“虛狀態(tài)”，只有當(dāng)虛狀態(tài)被發(fā)送到正確的智能體，才成為需要加入規(guī)劃的“實狀態(tài)”。

本文提出動態(tài)智能體交互圖作為智能體間信息交互的依據(jù)。

探測器的完整動態(tài)智能體交互圖按子系統(tǒng)分解為多個子圖，如圖2所示。子圖中的點按是否已經(jīng)加入規(guī)劃時間線分為已激活和未激活兩部分，圖中的點表示狀態(tài)，有向邊表示狀態(tài)之間的關(guān)系。子圖內(nèi)部有向邊從狀態(tài)指向其從屬狀態(tài)，表示狀態(tài)擴(kuò)展過程及狀態(tài)間從屬關(guān)系。子圖間的邊從虛狀態(tài)指向相應(yīng)的實狀態(tài)，表示智能體間狀態(tài)發(fā)送過程。智能體交互圖隨規(guī)劃進(jìn)行動態(tài)變化，已激活狀態(tài)擴(kuò)展生成未激活狀態(tài)，未激活狀態(tài)中的公共狀態(tài)被發(fā)送到其它智能體，未激活狀態(tài)激活后轉(zhuǎn)移到已激活區(qū)。圖中實箭頭表示狀態(tài)擴(kuò)展過程，虛箭頭表示狀態(tài)在圖的不同區(qū)域中轉(zhuǎn)移的過程。

圖2 動態(tài)智能體交互圖Fig. 2 Illustration of dynamic agent interaction graph

圖2中，智能體A中包含多個節(jié)點，每個節(jié)點代表一個狀態(tài)，其中一個狀態(tài)在規(guī)劃中擴(kuò)展后得到公共未激活狀態(tài)1，狀態(tài)1在A中是一個虛狀態(tài)，狀態(tài)1的信息被發(fā)送到智能體B中，智能體B根據(jù)虛狀態(tài)1的信息生成一個實狀態(tài)1。實狀態(tài)1在智能體B中被激活后按照規(guī)則繼續(xù)擴(kuò)展它的從屬狀態(tài)。完成發(fā)送過程后，智能體A不再保留狀態(tài)1。同理，B也會生成公共虛狀態(tài)，虛狀態(tài)2由B中的規(guī)則引發(fā)，但應(yīng)該屬于智能體C，因此C會接收虛狀態(tài)2的信息然后生成一個相應(yīng)的實狀態(tài)2，并激活此狀態(tài)繼續(xù)規(guī)劃。

2.2 多智能體數(shù)值約束處理

探測器任務(wù)規(guī)劃考慮的數(shù)值約束主要包括時間約束和資源約束。

本研究采用多智能體時間約束網(wǎng)絡(luò)建模智能體內(nèi)部及智能體間的時間約束。時間約束網(wǎng)絡(luò)中的節(jié)點代表狀態(tài)的開始時刻或結(jié)束時刻，網(wǎng)絡(luò)中的邊表示時間點之間的約束關(guān)系。時間點a和時間點b之間的時間約束關(guān)系用邊ab和邊ba表示，邊上的權(quán)值分別為Eab和Eba，b-a≤Eab，b-a≥-Eba（Eab≥0，Eba≤0），Eab表示b點在a點后最長時長，-Eba表示b點在a點后最短時長。

智能體的狀態(tài)之間的時間約束構(gòu)成了當(dāng)前智能體的簡單時間網(wǎng)絡(luò)[15]（STN，Simple Temporal Network）。多智能體時間約束網(wǎng)絡(luò)中包含每個智能體的局部STN和多個智能體STN之間的邊。STN之間的邊表示屬于不同智能體的狀態(tài)間的時間約束。

本研究通過基于圖的最短路徑算法的約束解耦方法實現(xiàn)智能體之間的時間約束處理。

當(dāng)一個公共狀態(tài)從虛狀態(tài)轉(zhuǎn)換為實狀態(tài)時，將其與主導(dǎo)狀態(tài)之間的時間約束加入到主導(dǎo)狀態(tài)所屬智能體的STN當(dāng)中，采用Floyd-Warshall算法（一種最短路徑算法）對此網(wǎng)絡(luò)進(jìn)行推理，得到網(wǎng)絡(luò)中所有邊的最小值。公共狀態(tài)的開始結(jié)束時刻都是網(wǎng)絡(luò)中的節(jié)點，這兩個節(jié)點與時間零點間的邊表示此狀態(tài)的開始結(jié)束時刻的取值范圍，即兩個節(jié)點之間的邊表示公共狀態(tài)持續(xù)時長的取值范圍，即。至此，公共狀態(tài)將其與主導(dǎo)狀態(tài)間的約束，轉(zhuǎn)換為其自身的時間約束信息，實現(xiàn)了公共狀態(tài)與其主導(dǎo)狀態(tài)的時間約束解耦。

如圖3所示，狀態(tài)3是狀態(tài)2的從屬狀態(tài)，因此兩個狀態(tài)之間存在時間約束。當(dāng)虛狀態(tài)3發(fā)送到智能體2中成為實狀態(tài)3時，它與狀態(tài)2之間的時間約束會被切斷，但是它與時間零點之間的約束和自身的持續(xù)時間約束會保留，從而實現(xiàn)了兩個STN之間的解耦。

圖3 多智能體時間約束網(wǎng)絡(luò)解耦示意Fig. 3 Illustration of multi-agent temporal network decoupling

對于資源約束，提取所有影響資源量的狀態(tài)，構(gòu)建資源約束網(wǎng)絡(luò)。狀態(tài)的開始結(jié)束時刻為網(wǎng)絡(luò)中的節(jié)點，資源量增加的點定義為生產(chǎn)點，資源量減少的點定義為消耗點，并增加一個源點和一個匯點。網(wǎng)絡(luò)中的邊分為3種：內(nèi)部邊從執(zhí)行時間晚的點指向執(zhí)行時間早的點；生產(chǎn)邊從源點指向生產(chǎn)點；消耗邊從消耗點指向匯點。在資源約束網(wǎng)絡(luò)中采用圖的最大流算法判斷資源量是否滿足約束[16]。本研究目前只考慮單個智能體的私有資源，多智能體共享資源通過規(guī)劃前定義每個智能體的用量上限轉(zhuǎn)換為私有資源處理。

2.3 基于分布式求精搜索的規(guī)劃空間規(guī)劃

求精搜索是一種基于缺陷處理的規(guī)劃方法，由于搜索空間中的節(jié)點是部分規(guī)劃，因此是一種規(guī)劃空間規(guī)劃方法。在每一步規(guī)劃中，算法從當(dāng)前部分規(guī)劃中選擇并消解一個缺陷，從而產(chǎn)生一個新的部分規(guī)劃。求精搜索考慮3種缺陷[17]：

1）未綁定變量：如果一個部分規(guī)劃中的變量的值域不是唯一的，那么此變量就是一個未綁定變量。未綁定變量的消解方式是在值域中為此變量指定一個值。

2）開放條件：一個未激活（inactive）狀態(tài)就是一個開放條件。消解此缺陷的方式是融合（merge）、激活（activate）或拒絕（reject）未激活的狀態(tài)。

3）威脅：一個狀態(tài)加入部分規(guī)劃后，可能會間接影響其他狀態(tài)。比如，時間線上的狀態(tài)不允許重疊，但新加入的狀態(tài)可能會與時間線上已有狀態(tài)重疊引發(fā)威脅缺陷。如果多個狀態(tài)共享一個資源，也可能引起資源約束不一致的威脅。解決威脅的方式是在狀態(tài)之間加入順序約束。

圖4所示為在多智能體規(guī)劃過程中，每個智能體內(nèi)部的規(guī)劃流程。此流程與單智能體規(guī)劃的主要區(qū)別在于公共狀態(tài)缺陷處理和終止條件判斷。

圖4 多智能體求精規(guī)劃中每個智能體的規(guī)劃流程Fig. 4 Flowchart of multi-agent refinement planning

本研究的方法將共享資源轉(zhuǎn)換為智能體私有資源處理，因此在3種缺陷中，只有開放條件缺陷會涉及多個智能體。開放條件缺陷就是一個未激活的狀態(tài)，未激活狀態(tài)可能是一個私有狀態(tài)，也可能是公共狀態(tài)。一個狀態(tài)激活后，其從屬狀態(tài)就成為新的未激活狀態(tài)。多智能體求精搜索需要解決的主要問題就是如何處理未激活的公共狀態(tài)。

本研究不設(shè)置多智能體協(xié)調(diào)中心，而是基于動態(tài)智能體交互圖定義的狀態(tài)擴(kuò)展和轉(zhuǎn)移規(guī)則處理未激活公共狀態(tài)。將未激活的公共狀態(tài)發(fā)送到相應(yīng)子系統(tǒng)的智能體中，成為該智能體的未激活狀態(tài)，實現(xiàn)跨智能體的缺陷轉(zhuǎn)移。第2.2節(jié)的時間約束傳播及解耦方法給出了公共狀態(tài)傳遞過程中時間約束的處理方式。在多智能體求精搜索算法中，為了實現(xiàn)公共狀態(tài)從智能體B到A的傳遞，需要以下具體步驟：

1）第i步規(guī)劃中，智能體B記錄新生成的開放條件缺陷，加入集合Opi；在第i步規(guī)劃后，從Opi中篩選出所有公共狀態(tài)。

2）獲取每個公共狀態(tài)T的謂詞名稱，包括智能體名稱（即子系統(tǒng)名稱，如“AttitudeSys”），狀態(tài)類型（如“AttitudeSys.Pointing”），狀態(tài)名稱（如“pointing”）和時間信息。時間信息包括該狀態(tài)的開始時刻s、結(jié)束時刻e和持續(xù)時長d三種時間變量的可行區(qū)間，即s∈[smin, smax]，e∈[emin, emax]，d∈[dmin, dmax]。

3）智能體B將公共狀態(tài)的謂詞名稱和時間信息發(fā)送到智能體A中，并從B的候選缺陷中剔除公共狀態(tài)。

4）智能體A生成與公共狀態(tài)智能體名稱、狀態(tài)類型相同的新狀態(tài)Tnew。為了避免與已有狀態(tài)重名，在公共狀態(tài)的名稱上添加元素，構(gòu)造新的狀態(tài)名稱，比如在pointing的基礎(chǔ)上增加單詞“add”和表示規(guī)劃輪數(shù)的數(shù)字n。

5）智能體A按照接收到的公共狀態(tài)的時間信息，為新生成的狀態(tài)Tnew添加時間約束，將開始結(jié)束時刻和狀態(tài)持續(xù)時長限制在規(guī)定的值域內(nèi)。在時間約束網(wǎng)絡(luò)中加入Tnew，進(jìn)行約束傳播。

6）智能體A將接收到的狀態(tài)加入開放條件候選缺陷集合中。

這樣一來，未激活的公共狀態(tài)從B轉(zhuǎn)移到A中，由A負(fù)責(zé)修復(fù)。

多智能體規(guī)劃的結(jié)束條件與單智能體規(guī)劃不同。單智能體規(guī)劃只需要考慮本地的缺陷是否都得到修復(fù)，規(guī)劃步數(shù)和時長是否達(dá)到上限。而多智能體規(guī)劃中的每個智能體在規(guī)劃步數(shù)和時長達(dá)到用戶設(shè)置的上限之前，不僅需要以自身是否有待處理的缺陷，也需要考慮其他智能體是否有待處理缺陷。因為對于一個暫時沒有待處理缺陷的智能體，其它智能體可能會在后續(xù)規(guī)劃中向它發(fā)送公共缺陷。只有確認(rèn)所有智能體都不需要繼續(xù)處理缺陷，才能停止規(guī)劃。

3 仿真實驗及結(jié)果分析

為了驗證方法的有效性，本研究在火星環(huán)繞器領(lǐng)域構(gòu)建測試用例，考慮載荷相機(jī)、姿態(tài)系統(tǒng)、對地通信等9個子系統(tǒng)（見表1），規(guī)劃程序使用C++語言實現(xiàn)。

表1 火星環(huán)繞器各子系統(tǒng)功能Table 1 Functions of subsystems in Mars Orbiter

多智能體規(guī)劃方法將環(huán)繞器的各子系統(tǒng)抽象為智能體，共有9個智能體，各智能體的狀態(tài)之間相互耦合，共有37個狀態(tài)（見表2）和49個約束，約束中定義的公共狀態(tài)有11個。其中載荷相機(jī)中包含載荷電池，用于驗證資源約束處理能力。

表2 火星環(huán)繞器各子系統(tǒng)狀態(tài)列表Table 2 States of subsystems in Mars Orbiter

各智能體間有如下約束關(guān)系。載荷相機(jī)拍照需要姿態(tài)系統(tǒng)指向目標(biāo)；對地通信需要姿態(tài)系統(tǒng)指向地球；對火通信需要姿態(tài)指向巡視器，對火通信后需要對地通信；太陽帆板充電需要姿態(tài)系統(tǒng)指向太陽，太陽帆板鎖定前需要綜電系統(tǒng)調(diào)整測控為模式1；GNC模式調(diào)整系統(tǒng)有兩種模式，模式1前需要太陽帆板鎖定，模式1中需要姿態(tài)轉(zhuǎn)動，模式2前需要太陽帆板對日；軌道控制系統(tǒng)調(diào)整軌道的同時需要推進(jìn)系統(tǒng)工作；綜合電子系統(tǒng)有兩種測控模式，進(jìn)入模式2前需要GNC模式調(diào)整系統(tǒng)進(jìn)入模式2。

設(shè)計5個測試問題，測試問題中每個子系統(tǒng)的規(guī)劃目標(biāo)數(shù)量由1到5遞增，總目標(biāo)數(shù)由9到45遞增。分別采用提出的多智能體規(guī)劃方法和EUROPA的進(jìn)行規(guī)劃，對比規(guī)劃用時和規(guī)劃步數(shù)。每個問題進(jìn)行10次測試，統(tǒng)計規(guī)劃用時的平均值。

對多智能體規(guī)劃空間規(guī)劃方法（MAPP）進(jìn)行串行（MAPP-串行）和并行（MAPP-并行）兩種模式的測試。多智能體串行模式指在每一輪規(guī)劃中，多個智能體依次規(guī)劃一步，同一時刻只有一個智能體處于規(guī)劃狀態(tài)，一輪規(guī)劃后智能體間交互信息，再進(jìn)行下一輪規(guī)劃。并行模式指在一輪規(guī)劃中多個智能體同時規(guī)劃一步，交互信息后再進(jìn)行下一輪規(guī)劃。兩種模式的算法本質(zhì)相同，每一步規(guī)劃中各智能體在邏輯上都是并行的，不受其它智能體影響。串行模式主要用于說明本文提出的方法即使不利用并行計算也能夠提高規(guī)劃效率。

圖5 規(guī)劃用時結(jié)果曲線Fig. 5 Computational results of runtime curves

圖6展示了采用本文提出的多智能體規(guī)劃方法得到的規(guī)劃結(jié)果序列，序列中的空白部分表示沒有新動作指令，探測器子系統(tǒng)保持上一個動作結(jié)束后的狀態(tài)。輸入問題中，探測器每個子系統(tǒng)有一個規(guī)劃目標(biāo)狀態(tài)。規(guī)劃結(jié)果顯示姿態(tài)、載荷、對地通信、推進(jìn)、太陽帆板、GNC模式調(diào)整及綜電系統(tǒng)的規(guī)劃結(jié)果中實現(xiàn)了不止一個狀態(tài)，說明算法成功實現(xiàn)了智能體間的協(xié)同規(guī)劃，除了自身問題文件中的目標(biāo)狀態(tài)，智能體還能配合其他智能體處理公共狀態(tài)。不同系統(tǒng)的狀態(tài)間的時間關(guān)系也滿足前文所述的智能體間約束。圖中僅標(biāo)出了智能體本身的目標(biāo)狀態(tài)和公共狀態(tài)。

圖6 各系統(tǒng)規(guī)劃結(jié)果甘特圖Fig. 6 Gantt chart of subsystems

3種規(guī)劃方法的規(guī)劃用時都隨著問題的目標(biāo)數(shù)增加而增長，MAPP-并行用時最少，EUROPA用時最多。多智能體規(guī)劃空間規(guī)劃的串行模式比EUROPA的規(guī)劃用時少，說明通過將子系統(tǒng)抽象為智能體，分割搜索空間，能夠提高規(guī)劃效率。

多智能體規(guī)劃空間規(guī)劃中，每個智能體只需要選擇并修復(fù)局部缺陷，而不必比較所有子系統(tǒng)中的待處理缺陷，降低了缺陷處理的復(fù)雜程度，提高了規(guī)劃效率。

多智能體規(guī)劃提高了時間約束處理的效率。假設(shè)智能體i的時間約束網(wǎng)絡(luò)中的節(jié)點數(shù)為ki，n個智能體的時間約束網(wǎng)絡(luò)中的節(jié)點數(shù)之和為。采用Floyd-Warshall算法對時間約束網(wǎng)絡(luò)進(jìn)行推理，此算法的時間復(fù)雜對為O(k3)，k為網(wǎng)絡(luò)中的節(jié)點數(shù)。對于多智能體時間約束網(wǎng)絡(luò)，每個智能體的時間約束推理的時間復(fù)雜度為O(ki3)，多個智能體串行推理的時間復(fù)雜度為在集中式規(guī)劃中，所有智能體的節(jié)點在同一張時間約束網(wǎng)中，約束推理的時間復(fù)雜度為顯然將時間約束網(wǎng)絡(luò)分解后的推理效率更高。

并行模式的多智能體規(guī)劃空間規(guī)劃中，規(guī)劃步數(shù)為所有智能體的規(guī)劃步數(shù)中的最大值。與EUROPA和串行模式的多智能體規(guī)劃相比，并行模式的多智能體規(guī)劃增加了參與規(guī)劃的計算資源，規(guī)劃步數(shù)更少，規(guī)劃用時更短，極大提高規(guī)劃效率。規(guī)劃步數(shù)對比參見圖7。

圖7 規(guī)劃步數(shù)結(jié)果對比Fig. 7 Comparison of planning steps

對于子系統(tǒng)眾多、領(lǐng)域知識復(fù)雜、任務(wù)目標(biāo)多的深空探測器任務(wù)規(guī)劃問題，適于采用多智能體規(guī)劃空間規(guī)劃。計算資源有限時可采用串行模式，多個智能體輪流規(guī)劃，與將多子系統(tǒng)視為一個整體的單智能體規(guī)劃空間規(guī)劃相比，可實現(xiàn)更高的規(guī)劃效率；計算資源充足則可采用并行模式，如多進(jìn)程并行或多計算機(jī)并行計算，進(jìn)一步縮短規(guī)劃時間。

4 結(jié) 論

本研究實現(xiàn)了基于求精搜索的深空探測器多智能體規(guī)劃空間規(guī)劃的理論設(shè)計和仿真驗證。結(jié)合數(shù)值約束處理技術(shù)和多智能體規(guī)劃方法，即滿足了深空探測器的時間資源約束處理需求，又實現(xiàn)了高效的多智能體協(xié)同規(guī)劃。實驗證明所設(shè)計的規(guī)劃方法能夠為深空探測器任務(wù)規(guī)劃生成合理規(guī)劃，并顯著提高了規(guī)劃效率，為未來深空探測任務(wù)規(guī)劃提供了一種新的可行方案。