于曉強，鄭紅星

（哈爾濱工業(yè)大學，哈爾濱 150001）

1 引 言

在軌裝配技術(shù)屬于模塊化航天器技術(shù)的重要組成部分［1］，是可以將受限制的大型空間結(jié)構(gòu)等大質(zhì)量、大體積的地面裝備拆解后分批次地發(fā)射到空間中再進行裝配的關(guān)鍵技術(shù)之一［2］。隨著未來空間科學任務(wù)的日益復(fù)雜以及人工智能產(chǎn)業(yè)的蓬勃發(fā)展，對智能化、自主化空間在軌裝配任務(wù)規(guī)劃技術(shù)的需求也逐步提高［3-5］。目前的在軌裝配任務(wù)不再局限于單個航天器獨自安裝，而需要多個航天器協(xié)同完成多類在軌裝配任務(wù)，從而實現(xiàn)空間資源的高效利用［6］。面對不同種類的在軌裝配任務(wù)（如零件運輸任務(wù)、安裝任務(wù)、維修任務(wù)等），不同任務(wù)之間會有一定的時間窗限制，如何統(tǒng)籌分配所有不同種類航天器資源，在最大化滿足裝配需求和資源充分利用的條件下，制定出最佳的航天器裝配任務(wù)執(zhí)行方案，是在軌裝配領(lǐng)域中出現(xiàn)的亟待解決的新問題。

本文所研究的問題可描述為：針對大量在軌裝配任務(wù)需求，在滿足裝配任務(wù)的類別約束及時間窗約束下，解決將各項任務(wù)分配給多個多種類航天器的在軌裝配任務(wù)分配問題，即確定使用哪些航天器在哪段時間內(nèi)按照什么順序來執(zhí)行哪些特定任務(wù)，以滿足不同任務(wù)對不同種類機器人及各自完成時間的裝配需求，最終實現(xiàn)在軌裝配任務(wù)圓滿完成、且綜合效益最大的目標。任務(wù)描述如圖1所示。

常見的任務(wù)分配算法主要包括基于合同網(wǎng)的市場拍賣方法、分布式馬爾可夫決策方法和模型預(yù)測控制方法［7-10］。其中，基于合同網(wǎng)的拍賣算法面向動態(tài)任務(wù)的自主分配，并在過程中考慮智能體之間的信息交互和協(xié)商，是一種相對容易實現(xiàn)的分布式算法［11-13］。基于一致性的捆綁拍賣算法（Consensus-Based Bundle Algorithm，CBBA）是一種利用拍賣算法的多任務(wù)分配算法，允許智能體對每個任務(wù)進行競價，然后開發(fā)一個共識算法來解決智能體之間的分配沖突［14-15］。本文提出了一種改進的CBBA算法，用于將具有協(xié)同任務(wù)約束的裝配任務(wù)分配給具有不同能力的異構(gòu)在軌裝配航天器團隊。

本文提出的改進算法包括以下兩個方面：

（1）為體現(xiàn)在軌裝配中運輸、安裝等任務(wù)的時間先后特性，為每個任務(wù)設(shè)置完成時間窗及完成任務(wù)所需時間。通過設(shè)計新的競價函數(shù)，考慮運輸及裝配航天器運動速度及任務(wù)時間窗約束，保證所有任務(wù)在規(guī)定時間段內(nèi)完成，并使整個航天器團隊所花費的時間或路程代價最小。

圖1 在軌裝配任務(wù)分配問題描述Fig.1 Description of on-orbit assembly task assignment problem

（2）考慮某些復(fù)雜運輸/安裝任務(wù)需要多個運輸/安裝航天器協(xié)同完成，這是原算法無法處理的情況。本文提出了一種新的一致性算法，更改了本地拍賣信息的儲存方式，并提出了一種新的分配沖突解決規(guī)則，使算法可以處理多智能體任務(wù)分配問題。

最后，對本文提出的算法進行了仿真實驗，證明了該算法能夠在不增加額外計算時間情況下收斂到一個無沖突、可行的任務(wù)分配解決方案，可解決復(fù)雜多約束的在軌裝配任務(wù)分配問題。

2 算法模型

2.1 CBBA算法原理

CBBA算法是一種分布式拍賣算法，為多智能體多任務(wù)分配問題提供了可靠的解決方案。CBBA算法在兩個不同的階段之間迭代進行，分別是拍賣包構(gòu)建階段和共識階段，拍賣包構(gòu)建階段每個智能體按一定的順序生成一個本地的任務(wù)包，共識階段通過相鄰智能體之間的通信及一致性算法解決分配沖突。

第一階段：拍賣包構(gòu)建階段。每個智能體在本地構(gòu)建一個任務(wù)包，其中包含它計劃在分配過程中完成的所有任務(wù)，然后智能體不斷地向包中添加任務(wù)并進行合理排序，直到達到它所能完成的任務(wù)數(shù)量上限。每個智能體i任務(wù)包中含有兩個任務(wù)相關(guān)向量：bi和pi。其中bi按添加進包的先后進行排序，而pi按智能體計劃完成任務(wù)的先后進行排序。表示智能體i按p中的任務(wù)序列執(zhí)行任i務(wù)得到的總獎勵，當包內(nèi)插入了新的任務(wù)j時，表示將任務(wù)j插入到任務(wù)路徑pi的第n個位置后得到的總獎勵。cij［bi］表示由于添加任務(wù)j到任務(wù)包而導(dǎo)致的得分增長量。

每個智能體在當前路徑pi中的所有可能位置插入新任務(wù)j，從而確定使cij［bi］最大的位置n。然后依次添加所有智能體可完成的任務(wù)至任務(wù)包內(nèi)，從而確定出最大化任務(wù)獎勵的完成路徑pi。

每個智能體在構(gòu)建完成自己的任務(wù)包后，需要構(gòu)建包含競標信息的量：中標價格列表yi、中標智能體列表zi、更新時間si。yi表示每個任務(wù)的當前出價中出價最高的價格，zi表示出價最高的智能體，zij=k表示智能體i認為任務(wù)j被分配給智能體k。智能體不僅需要知道它選擇的任務(wù)是否高于最高出價，還要知道每個任務(wù)的分配對象。因此，需要更復(fù)雜的沖突解決規(guī)則來解決多智能體間的分配沖突，實現(xiàn)更好的分配。

第二階段：共識階段。CBBA算法的共識階段是避免太多智能體分配到相同的任務(wù)。當智能體i收到來自另一個智能體k的消息時，yi、zi和si用于產(chǎn)生無沖突的任務(wù)分配細節(jié)。智能體i可以對任務(wù)j采取三種可能的行動：（1）更新：當yij＜ykj時，；（2）保留：當yij＞ykj時，；（3）重置：當路徑pi中已經(jīng)有其它變動，yij=0，zijij=?。

如果以上規(guī)則更改了智能體的出價列表，每個智能體將檢查更新或重置的任務(wù)是否在其任務(wù)包中，如果是，則在任務(wù)包內(nèi)刪除該任務(wù)。因為刪除該任務(wù)會改變所有后續(xù)任務(wù)的得分，所以也需要刪除在bin之后添加到捆綁包中的所有任務(wù)，對應(yīng)的中標價格列表yi以及中標智能體列表zi都會被重置，即：如此依次解決每個任務(wù)的分配沖突，然后算法返回到第一階段并重新添加新任務(wù)。算法會一直迭代這兩個階段，直到它們收斂到一個無沖突的解決方案。

2.2 考慮時間約束的競價函數(shù)

考慮在軌裝配過程中運輸、安裝等各子任務(wù)的時間先后，需要為每個子任務(wù)設(shè)置任務(wù)時間窗約束。本文設(shè)計了一種考慮任務(wù)復(fù)雜時間約束的競價函數(shù)，考慮每個任務(wù)的時間約束，保證所有任務(wù)在其規(guī)定時間段內(nèi)完成，并使整個航天器團隊所花費的時間及路程代價最小。本文首先定義了時間分數(shù)項sj(t)以及時間窗uj(t)如下：

時間分數(shù)項sj(t)：表示航天器在時間t到達任務(wù)時從任務(wù)j獲得的獎勵，是基于任務(wù)的獎勵值Rj和任務(wù)時間懲罰及距離懲罰的函數(shù)。

其中，（t-tjstart）是任務(wù)開始時間和航天器到達任務(wù)時間之間的差異，而λj是懲罰航天器遲到的折扣參數(shù)，Pdistance是懲罰航天器按路徑p從上一任務(wù)到任務(wù)j所花費的路程項。

時間窗uj(t)：任務(wù)的有效時間窗口表示允許航天器執(zhí)行任務(wù)的時間。對于任務(wù)j，此窗口定義為：

定義航天器對任務(wù)j的競價函數(shù)cj(tij)為：

tij是其到達任務(wù)j位置的時間，是航天器在到達任務(wù)j之前所采取的路徑p的函數(shù)。給定一個路徑pi，和一組對于路徑中所有任務(wù)k（k ∈pi）對應(yīng)的最佳時間，對于每個任務(wù)j? p，執(zhí)行任i務(wù)j的最佳時間定義為：

其中⊕表示將任務(wù)j插入路徑pi而不改變pi中已有任務(wù)的順序。上式約束為，將新任務(wù)j插入路徑pi不能影響路徑中已有任務(wù)的當前到達時間。通過將j插入最佳位置來更新路徑。然后將任務(wù)j的最佳時間和得分保存為：和。

2.3 擴展一致性算法

考慮大型空間結(jié)構(gòu)中某些復(fù)雜運輸/安裝任務(wù)需要多個運輸/安裝航天器協(xié)同完成，這是原算法無法處理的情況。本文據(jù)此提出了一種新的一致性算法，更改了本地拍賣信息的儲存方式，并針對多智能體任務(wù)分配沖突提出了一種新的分配沖突解決規(guī)則。在算法的拍賣包構(gòu)造階段，每個航天器的任務(wù)包bi和路徑pi的構(gòu)造方法與原來的CBBA算法相同。在算法的分配沖突解決階段，航天器接收來自附近航天器的所有任務(wù)分配信息的數(shù)據(jù)，然后使用一致性算法協(xié)調(diào)所有任務(wù)的分配沖突，下面對兩部分內(nèi)容分別進行詳細描述。

2.3.1 航天器的信息矩陣構(gòu)造

首先需要確定一致性算法所需的數(shù)據(jù)。當開始使用CBBA算法時，任務(wù)及航天器信息存儲在航天器本地。每個航天器存儲兩個長度為Nm的向量（其中，Nm是總?cè)蝿?wù)數(shù)），中標列表yi和中標航天器列表zi。每個航天器可以使用zi確定每個任務(wù)的出價最高者，并使用yi確定最高出價。當使用原始CBBA共識算法處理多航天器任務(wù)的數(shù)據(jù)時，不同的任務(wù)可以分配不同數(shù)量的航天器，對于需要多個分配的任務(wù)，向量不能存儲每個分配的數(shù)據(jù)。因此，為了解決需要多航天器的任務(wù)分配問題，需要改變存儲這些值的方式，必須將這兩個向量轉(zhuǎn)換成一個矩陣，以確定多個獲勝者及其出價。

將這兩個向量組合成一個包含所有拍賣獲勝信息的信息矩陣B。矩陣使用行來顯示任務(wù)，使用列來顯示航天器，Bij對應(yīng)于航天器i對任務(wù)j的出價，如果航天器尚未出價，則為0。此外，矩陣B的大小為Nn*Nm，其中Nn是在軌航天器數(shù)，每行中的非零值的數(shù)目不應(yīng)超過任務(wù)所需的航天器數(shù)Lj。除此之外，還使用來區(qū)分每個航天器的本地數(shù)據(jù)，＞0表示航天器i認為任務(wù)j分配給航天器m，算法1給出了如何將zi、yi轉(zhuǎn)換成矩陣集。

算法1：構(gòu)造航天器i的信息矩陣B

2.3.2 分配沖突解決規(guī)則

原CBBA算法使用一個查找表來確定是根據(jù)發(fā)送者的信息更新還是重置接收者的信息。對于需要多航天器解決的任務(wù)，接收者不必重置或更新與自己不同的數(shù)據(jù)，而更可能合并數(shù)據(jù)，從而使兩個航天器的數(shù)據(jù)都是正確的和保存的。新的分配沖突解決算法分為兩個階段，以便更好地結(jié)合航天器的數(shù)據(jù)，應(yīng)對任務(wù)的多樣性。

第一個階段是將航天器的時間信息與它接收的所有數(shù)據(jù)進行比較，并接受更新的數(shù)據(jù)。通過比較航天器的時間戳信息，可以知道哪個航天器的數(shù)據(jù)比較新。在算法2中的4-8行，skm＞sim表示k有更多的最新通信數(shù)據(jù)，這些數(shù)據(jù)可能是更高的出價或更多的最新分配信息，應(yīng)該保存。

在第二階段，如果所有發(fā)送方和接收方當前都是最新的信息，根據(jù)發(fā)送方的數(shù)據(jù)更新接收方的數(shù)據(jù)。首先檢查發(fā)送方k認為的分配給每個任務(wù)j的航天器m（算法2中第10-11行）。如果航天器i認為該任務(wù)沒有分配給航天器m（=0），并且分配給任務(wù)j的航天器數(shù)量還沒有達到該任務(wù)的需求數(shù)量，那么可以通過直接更新分配矩陣，將任務(wù)j同時分配給航天器i。

另外，當任務(wù)j的分配完成或有更好的出價時，應(yīng)該按算法2中第12-14行更新任務(wù)j的分配矩陣。當接收者認為任務(wù)j的分配已滿時，我們首先在分配給任務(wù)j的航天器中找到出價最低的航天器。如果發(fā)送者k認為出價高于此值，應(yīng)該用發(fā)送者的數(shù)據(jù)替換最低出價，用更新新的分配矩陣（其中n是最低的投標航天器）。這里也可能有一個問題，當最小出價等于發(fā)送者的數(shù)據(jù)時，就可能出現(xiàn)死鎖。因此，制定一個簡單的規(guī)則，當航天器的出價相等時，ID較高的航天器具有優(yōu)先級（算法2中的第15-19行）。

算法2：航天器i的分配沖突解決

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

本文中用于測試上述算法的仿真場景包括兩種異構(gòu)航天器（運輸航天器和裝配航天器），它們負責完成兩類任務(wù)（運輸和安裝），每個任務(wù)所需的航天器數(shù)量可以單獨定義。每個任務(wù)都有5min的時間窗口，一個隨機的開始時間，以及5min或15min的任務(wù)執(zhí)行時間。每個航天器都有自己的速度和特定的燃料消耗。

本文進行了以下仿真實驗：每次實驗包含20個任務(wù)，其中一半是運輸任務(wù)，一半是裝配任務(wù)。第一個實驗驗證了本文設(shè)計的競價函數(shù)的有效性，其中每個任務(wù)只需要1個航天器完成；第二個實驗驗證拓展一致性算法，每個任務(wù)需要2個航天器完成；第三個實驗設(shè)置為混合實驗，運輸任務(wù)需要2個運輸航天器，裝配任務(wù)需要1個裝配航天器。每個實驗的目標是最大化完成任務(wù)的所有航天器的獎勵總和。多航天器任務(wù)將獎勵完成任務(wù)的每個航天器，顯示此類任務(wù)的難度和重要性，逐漸增加異構(gòu)航天器的數(shù)量來測試算法性能。每個實驗運行100次并記錄平均數(shù)據(jù)。

圖2顯示了實驗1的具體分配細節(jié)，圖2（a）顯示了每個航天器隨時間的分配路徑（為了更直觀顯示分配情況，只顯示了x方向隨時間的位置變化），圖2（b）顯示了每個航天器的具體分配時間表。從圖中可以看出，含新競價函數(shù)的分配算法可以成功處理具有復(fù)雜時間約束的在軌裝配任務(wù)分配問題。

圖3（a）顯示了隨著航天器數(shù)量的增加，三個實驗的總分變化情況?？梢园l(fā)現(xiàn)，在實驗開始時，由于異構(gòu)航天器數(shù)量不足，多智能體任務(wù)的得分低于單一智能體任務(wù)的得分，但隨著航天器數(shù)量的增加，多智能體任務(wù)的得分明顯高于單航天器任務(wù)。圖3（b）顯示計算時間只會隨著航天器數(shù)量的增加而增加，并且不會由于實驗任務(wù)的類型變化而發(fā)生明顯變化，它表明新的一致性算法不會導(dǎo)致計算量的增加。

圖2 實驗一任務(wù)分配細節(jié)（共10個航天器，5個運輸航天器，5個安裝航天器）Fig.2 The first experimentation task assignment details（10 spacecrafts, 5 transport spacecrafts, 5 installation spacecrafts）

圖3 各實驗的實驗性能對比Fig.3 Experimental performance between the Single-Agent, Multi-Agent and Mix experiments

圖4 實驗二任務(wù)分配細節(jié)（共10個航天器，5個運輸航天器，5個安裝航天器）Fig.4 The second experimentation task assignment details (10 spacecrafts, 5 transport spacecrafts, 5 installation spacecrafts)

值得注意的是，多航天器任務(wù)的通信步驟少于單航天器任務(wù)，這可以通過圖4中航天器的分配細節(jié)解釋。圖4顯示了共10個航天器執(zhí)行多航天器任務(wù)的分配細節(jié)。

與單個航天器任務(wù)實驗中每個任務(wù)需要選擇最佳航天器相比，在執(zhí)行多航天器任務(wù)過程中，當多個航天器組成團隊完成第一個任務(wù)時，他們通常會一起執(zhí)行下一個最近的任務(wù)，從而減少通信和距離成本。當然，航天器也會通過一致性算法形成一個更佳選擇的新團隊完成任務(wù)。但總的來說，這種現(xiàn)象減少了航天器之間的分配沖突，減少了通信步驟的數(shù)量。

4 結(jié) 論

本文提出了一種改進的CBBA算法，它為大型空間結(jié)構(gòu)的在軌裝配任務(wù)分配問題提供了一種分布式解決方法。算法的改進包括設(shè)計新的競價函數(shù)使CBBA算法能夠處理具有復(fù)雜時間約束的在軌裝配任務(wù)，以及針對某些需要多航天器協(xié)同完成的特定復(fù)雜任務(wù)提出了擴展一致性算法，針對多智能體任務(wù)的分配沖突，將原CBBA算法中的中標名單和中標代理名單組合成一個包含所有中標信息的矩陣，并設(shè)計了新的沖突解決規(guī)則，解決了多代理任務(wù)引起的分配沖突。

本文通過仿真實驗驗證了該算法的有效性。實驗表明，本文設(shè)計的含新競價函數(shù)的分配算法可以成功處理具有復(fù)雜時間約束的在軌裝配任務(wù)分配問題。同時，提出的擴展一致性算法成功解決了復(fù)雜多智能體任務(wù)的分配問題，且在不增加算法的運行時間情況下顯著提高了分配任務(wù)總得分。綜上所述，本文提出的分布式任務(wù)分配算法可以得出多航天器任務(wù)分配問題的無沖突解決方案，可以保證復(fù)雜在軌裝配任務(wù)的成功分配。