基于拓展CBBA算法的在軌裝配航天器任務(wù)分配技術(shù)研究

于曉強(qiáng)，鄭紅星

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

1 引 言

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

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

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

本文提出的改進(jìn)算法包括以下兩個(gè)方面：

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

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

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

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

2 算法模型

2.1 CBBA算法原理

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

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

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

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

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

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

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

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

時(shí)間分?jǐn)?shù)項(xiàng)sj(t)：表示航天器在時(shí)間t到達(dá)任務(wù)時(shí)從任務(wù)j獲得的獎(jiǎng)勵(lì)，是基于任務(wù)的獎(jiǎng)勵(lì)值Rj和任務(wù)時(shí)間懲罰及距離懲罰的函數(shù)。

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

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

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

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

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

2.3 擴(kuò)展一致性算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 各實(shí)驗(yàn)的實(shí)驗(yàn)性能對比Fig.3 Experimental performance between the Single-Agent, Multi-Agent and Mix experiments

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

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

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

4 結(jié) 論

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

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