模塊化可重構(gòu)衛(wèi)星在軌自重構(gòu)的分層規(guī)劃

王博，葉東,*，孫兆偉，唐生勇，陳欣

1.哈爾濱工業(yè)大學(xué) 衛(wèi)星技術(shù)研究所，哈爾濱 150001 2. 上海宇航系統(tǒng)工程研究所，上海 201109 3. 北京航天長征飛行器研究所，北京 100076

隨著微小衛(wèi)星及其技術(shù)的蓬勃發(fā)展，結(jié)構(gòu)固定的衛(wèi)星已經(jīng)難以滿足各國對其提出的多任務(wù)執(zhí)行能力、較強(qiáng)的環(huán)境適應(yīng)性及抗風(fēng)險等要求，因此人們將目光轉(zhuǎn)向具有在軌變結(jié)構(gòu)[1]能力的模塊化可重構(gòu)衛(wèi)星。

在傳統(tǒng)的設(shè)計模式下，衛(wèi)星的研制周期很長。在軌衛(wèi)星一旦失效，就需要很長的時間進(jìn)行重新部署。并且由于現(xiàn)有衛(wèi)星采用定制研制模式，導(dǎo)致衛(wèi)星的設(shè)計成本和測試成本無法有效降低。

模塊化可重構(gòu)衛(wèi)星可根據(jù)不同任務(wù)需求，將原有構(gòu)型的多個功能衛(wèi)星模塊重組成適應(yīng)新任務(wù)的最佳構(gòu)型；在局部衛(wèi)星模塊出現(xiàn)故障的情況下，可通過在軌自重構(gòu)完成備用模塊與故障模塊之間的替換，具有自修復(fù)功能[2]；還可根據(jù)發(fā)射條件將模塊化可重構(gòu)衛(wèi)星調(diào)整到最佳的發(fā)射構(gòu)型，進(jìn)入軌道后通過在軌重組恢復(fù)到運行及工作形態(tài)。圖1 為利用空間鏈?zhǔn)阶灾貥?gòu)機(jī)器人進(jìn)行裝配、合作操縱和自我修復(fù)的構(gòu)想圖[3]。

自重構(gòu)機(jī)器人的概念首次由日本學(xué)者福田敏夫提出，并且設(shè)計了全部由通用連接模塊構(gòu)成的機(jī)器人CEBOT[4-5]。但是該機(jī)器人模塊數(shù)目少，執(zhí)行任務(wù)的能力有限。日本產(chǎn)業(yè)技術(shù)研究所、南加州大學(xué)、康奈爾大學(xué)等機(jī)構(gòu)分別研發(fā)了M-TRAN[6-7]、SuperBot[8]、Molecubes[9]，這些自重構(gòu)機(jī)器人都采用鏈?zhǔn)浇Y(jié)構(gòu)，相比網(wǎng)格型結(jié)構(gòu)可以實現(xiàn)的構(gòu)型較少。Telecube[10-11]是美國Xerox Palo Alto研究中心研制的一款以平動為運動方式的網(wǎng)格型結(jié)構(gòu)自重構(gòu)機(jī)器人。文獻(xiàn)[12]基于模塊平動的特點提出將底部空心的結(jié)構(gòu)下沉填滿下層空缺的“梳齒-梳柄”化過程。將這一過程形成的“梳齒-梳柄”結(jié)構(gòu)作為中間構(gòu)型，并通過逆“梳齒-梳柄”化過程完成自重構(gòu)。與滑動相比，模塊旋轉(zhuǎn)需要額外的間隙。因而，基于滑動模型的算法不能應(yīng)用于旋轉(zhuǎn)立方體模型。麻省理工學(xué)院設(shè)計了以轉(zhuǎn)動為運動方式的模塊化自重構(gòu)機(jī)器人3D M-Block[13-14]。與文獻(xiàn)[12]類似，文獻(xiàn)[15]基于轉(zhuǎn)動運動的特點提出了將直線結(jié)構(gòu)作為中間構(gòu)型，通過直線化和逆直線化實現(xiàn)自重構(gòu)的規(guī)劃算法。

圖1 利用空間鏈?zhǔn)阶灾貥?gòu)機(jī)器人進(jìn)行裝配、 合作操縱和自我修復(fù)的構(gòu)想[3]Fig.1 Idea of using space chain self-reconfigurable robots for assembly, cooperative manipulation and self-repair[3]

但是由于直線構(gòu)型結(jié)構(gòu)跨度大，整體表現(xiàn)出頻率低、模態(tài)密集的動力學(xué)特征[16]。衛(wèi)星所處的空間環(huán)境復(fù)雜、阻尼小，直線構(gòu)型在模塊旋轉(zhuǎn)過程中容易產(chǎn)生大幅振動，并且這種振動不易衰減。因此這一算法不適合應(yīng)用于航天領(lǐng)域。本文提出一種新的以轉(zhuǎn)動運動網(wǎng)格型自重構(gòu)機(jī)器人為基礎(chǔ)的可重構(gòu)衛(wèi)星的在軌自重構(gòu)規(guī)劃算法。文章內(nèi)容安排如下：首先，詳細(xì)陳述了模塊化可重構(gòu)衛(wèi)星的在軌自重構(gòu)過程。其次，建立了矩陣形式的自重構(gòu)模型，并給出了構(gòu)型、位置矩陣、連接矩陣等概念。再次，給出了模塊運動空間的求解算法，并分析了模塊三維運動特性?；诜謱右?guī)劃模型設(shè)計了重構(gòu)規(guī)劃問題的規(guī)劃算法，并且給出了基于二分圖理論和Kuhn-Munkres算法的上層規(guī)劃以及基于廣度優(yōu)先搜索的下層規(guī)劃。最后，將提出的規(guī)劃算法應(yīng)用于10模塊衛(wèi)星在軌自重構(gòu)問題，并針對自重構(gòu)過程中中間構(gòu)型構(gòu)型的結(jié)構(gòu)跨度進(jìn)行了仿真研究。

1 模塊化可重構(gòu)衛(wèi)星的在軌自重構(gòu)過程

模塊化可重構(gòu)衛(wèi)星是一種新概念衛(wèi)星，由許多功能獨立、外形相同的標(biāo)準(zhǔn)模塊組成。依靠模塊上的傳感器感知周圍環(huán)境信息，在沒有外力干預(yù)的情況下利用模塊間的可連接性和互換性通過模塊間的相互運動、連接/分離(衛(wèi)星在模塊運動的過程中保持整體的連通性)改變構(gòu)型，擴(kuò)展功能和運動形式。

模塊化可重構(gòu)衛(wèi)星可以進(jìn)行組合發(fā)射，如圖2 所示。設(shè)計合理的模塊化可重構(gòu)衛(wèi)星初始構(gòu)型，將多個衛(wèi)星組合成適應(yīng)發(fā)射平臺的標(biāo)準(zhǔn)發(fā)射構(gòu)型。入軌后，發(fā)射構(gòu)型分離解體。每一個衛(wèi)星進(jìn)行自重構(gòu)，由初始構(gòu)型變?yōu)閳?zhí)行設(shè)計任務(wù)的目標(biāo)構(gòu)型。接到任務(wù)變更指令時，根據(jù)任務(wù)設(shè)計新的目標(biāo)構(gòu)型。進(jìn)行重構(gòu)規(guī)劃，得到自重構(gòu)策略。按照該策略完成自重構(gòu)，執(zhí)行新的任務(wù)。

圖2 模塊化可重構(gòu)衛(wèi)星的組合發(fā)射和在軌自重構(gòu)Fig.2 Combined launch and on-orbit self-reconfiguration of modular reconfigurable satellites

通過自重構(gòu)可以解決公用平臺針對不同任務(wù)和有效載荷的適應(yīng)性問題。同時可以實現(xiàn)在軌自修復(fù)，在軌釋放、捕獲目標(biāo)等功能；模塊化可重構(gòu)衛(wèi)星可以提前發(fā)射入軌待命，接到指令后進(jìn)行變形以完成相應(yīng)任務(wù)，實現(xiàn)對緊急情況的快速響應(yīng)；當(dāng)衛(wèi)星的某一執(zhí)行機(jī)構(gòu)失效時，模塊化可重構(gòu)衛(wèi)星可以通過自重構(gòu)適當(dāng)調(diào)整相應(yīng)的安裝矩陣，保證衛(wèi)星可以繼續(xù)正常工作。原理框圖如圖3所示。

2 模塊化可重構(gòu)衛(wèi)星的相對位置建模

2.1 模塊化可重構(gòu)衛(wèi)星的構(gòu)型

為了描述后續(xù)研究內(nèi)容，提出構(gòu)型的概念：具有一定連接關(guān)系的模塊集合、位置集合或模塊位置混合集合在三維空間中的結(jié)構(gòu)形式稱為構(gòu)型。模塊化可重構(gòu)衛(wèi)星的一個構(gòu)型C由n個模塊構(gòu)成。兩個面接觸的模塊通過施加在接觸面上的相互作用力連接在一起，彼此稱為對方的相鄰模塊。模塊化可重構(gòu)衛(wèi)星所有模塊的連接關(guān)系可以用圖g(ν,ε):頂點集合ν={i:i為C中的模塊},邊ε={(i,j):模塊i,j互為相鄰模塊}來表示，稱為構(gòu)型C的拓?fù)溥B接圖，如圖4所示。

圖3 模塊化可重構(gòu)衛(wèi)星在軌自重構(gòu)原理框圖Fig.3 Block diagram of modular reconfigurable satellite on-orbit self-reconfiguration

圖4 構(gòu)型的拓?fù)溥B接圖Fig.4 Topological connection diagram of configuration

基于構(gòu)型的概念定義衛(wèi)星自重構(gòu)：給定模塊數(shù)均為n的初始構(gòu)型C0和目標(biāo)構(gòu)型Cgoal，在保證構(gòu)型連通性并且模塊之間不發(fā)生碰撞的前提下，通過模塊的運動使構(gòu)型C0經(jīng)歷一個構(gòu)型序列(C0,C1,…,CT)最終變?yōu)镃goal。重構(gòu)規(guī)劃問題就是求解構(gòu)型序列(C0,C1,…,CT)。

2.2 構(gòu)型的位置矩陣

位置矩陣是構(gòu)型對應(yīng)集合中各元素之間相對位置的描述。定義一個三維坐標(biāo)系，模塊i可由它的坐標(biāo)(xi,yi,zi)表示。xi,yi,zi∈Z，模塊的邊長作為一個單位長度。按照ν中的順序?qū)⒛K的坐標(biāo)向量排成一列，使第i行對應(yīng)模塊i，這就定義了模塊化可重構(gòu)衛(wèi)星的位置矩陣V。如果將位置也用坐標(biāo)表示，就可以得到構(gòu)型的位置矩陣。

當(dāng)模塊i的坐標(biāo)(xi,yi,zi)包括在構(gòu)型C的位置矩陣中時，稱i∈C。定義構(gòu)型位置矩陣的集合運算如下。

定義1(交運算)f∩稱為位置矩陣的交：Va和Vb是構(gòu)型Ca、Cb的位置矩陣，f∩(Va,Vb)=Va∩b。Ca∩b是構(gòu)型Ca與Cb的公共模塊組成的構(gòu)型，使得?i∈Ca∩b滿足i∈Ca且i∈Cb。若構(gòu)型Ca與Cb沒有公共模塊，稱他們的交集為空，表示為f∩(Va,Vb)=0。

定義2(并運算)f∪稱為位置矩陣的并：Va和Vb是構(gòu)型Ca、Cb的位置矩陣，f∪(Va,Vb)=Va∪b。Ca∪b是構(gòu)型Ca與Cb的公共模塊組成的構(gòu)型，使得?i∈Ca∩b滿足i∈Ca或i∈Cb。

2.3 構(gòu)型的連接矩陣

(1)

利用N可以計算出模塊i相鄰位置k的坐標(biāo)：

vk=vi+N(k)

(2)

式中：N(k)表示矩陣N的第k行。

定義連接向量e表示模塊i的連接情況，e為一個六維向量，它的第k個元素ek表示標(biāo)號為k的相鄰位置是否有模塊與i連接。ek∈{0,1}，滿足：

(3)

按照ν中的順序?qū)⒛K的連接向量排成一列，使第i行對應(yīng)模塊i，這就定義了模塊化可重構(gòu)衛(wèi)星的連接矩陣E。已知構(gòu)型的位置矩陣可以推算出構(gòu)型的連接矩陣。

3 自重構(gòu)過程中的運動空間與運動特性

在相對位置的約束下可以對模塊的運動進(jìn)行離散化分析，研究模塊一步運動結(jié)束后到達(dá)的位置，以此建立自重構(gòu)運動模型。

3.1 立方體模塊旋轉(zhuǎn)運動的PCM模型

模塊在旋轉(zhuǎn)的過程中，除了初始位置和運動結(jié)束后的位置，還需要掃過一片額外的區(qū)域。這片區(qū)域的存在意味著利用模塊平移進(jìn)行自重構(gòu)和利用模塊旋轉(zhuǎn)進(jìn)行自重構(gòu)這兩種方式在研究上存在根本性的區(qū)別。因而，人們在研究這片區(qū)域?qū)\動影響的過程中建立了專門描述利用模塊旋轉(zhuǎn)實現(xiàn)變構(gòu)的自重構(gòu)機(jī)械系統(tǒng)單個模塊運動的旋轉(zhuǎn)立方模型(Pivoting Cube Model，PCM)，如圖5所示。

在PCM模型中，模塊旋轉(zhuǎn)盡可能大的角度。這就意味著在它有一面與其他模塊接觸前運動不會停止。由于旋轉(zhuǎn)的模塊為立方體型，旋轉(zhuǎn)掃過的最大區(qū)域取決于模塊在旋轉(zhuǎn)面內(nèi)投影的對角線掃過的面積。PCM模型給出了模塊旋轉(zhuǎn)需要滿足的5條假設(shè)：

1) 旋轉(zhuǎn)模塊圍繞與另一個模塊共享的邊緣(轉(zhuǎn)軸邊緣)旋轉(zhuǎn)。

2) 正在旋轉(zhuǎn)的模塊掃過的區(qū)域不能和其他模塊區(qū)域相交。

3) 旋轉(zhuǎn)掃過的區(qū)域在同一平面內(nèi)，該平面與轉(zhuǎn)軸垂直。

4) 在不旋轉(zhuǎn)期間，模塊位于立方晶格上。

5) 連接的模塊必須共享一個面。因此正在進(jìn)行旋轉(zhuǎn)的模塊是無連接的。

圖5 PCM模型下的模塊旋轉(zhuǎn)運動Fig.5 Module rotation under PCM model

3.2 模塊在當(dāng)前構(gòu)型下的運動空間及其求解

不考慮連接情況，模塊共有6個可能的運動方向。為了研究的方便，將模塊剛開始運動的速度方向定義成模塊旋轉(zhuǎn)運動的方向。

對于立方模塊，運動方向總是與模塊本體系坐標(biāo)軸平行。因此運動方向可以用相應(yīng)坐標(biāo)軸方向的標(biāo)號表示，在本文中用d表示。

(4)

式中:i為旋轉(zhuǎn)模塊；vi為其坐標(biāo)向量。在旋轉(zhuǎn)過程中，模塊運動的路徑經(jīng)過圖6中的位置1、2。

(5)

式中:v1、v2分別是位置1、2的坐標(biāo)向量，表達(dá)式為

v1=2vi-vj

(6)

v2=2vi-vj+N(d)

(7)

式中：j為相鄰模塊；vj為其坐標(biāo)向量。

同理可得模塊旋轉(zhuǎn)π到達(dá)的位置可以表示為

vπ=vj+N(d)

(8)

(9)

式中：v3、v4分別為位置3、4的坐標(biāo)向量，表達(dá)式為

圖6 旋轉(zhuǎn)過程中掃過的位置Fig.6 Swept position during rotation

v3=vi+2N(d)

(10)

v4=vj+2N(d)

(11)

定理在保證連通性的前提下，模塊i繞相鄰模塊j沿方向d旋轉(zhuǎn)：

枚舉出模塊在平面內(nèi)所有可能的連接情況，利用定理1進(jìn)行分析可以得到運動空間，如圖7所示。

模塊i繞其相鄰模塊j的旋轉(zhuǎn)可以在兩個平面內(nèi)進(jìn)行，這兩個平面均與i、j連接面垂直。i繞j的空間運動可以分解成兩個平面運動進(jìn)行研究，運動空間為各平面內(nèi)運動空間的交集。在每個平面內(nèi)運動有順時針和逆時針兩個運動方向。

對每個相鄰模塊討論這兩個平面內(nèi)的4個運動方向可以遍歷模塊i所有可能的運動形式。除此之外，模塊的運動不能破壞構(gòu)型整體的連通性。借用圖論中割點的定義[17]，模塊可以運動的前提是該模塊不是構(gòu)型的割點。根據(jù)以上兩條結(jié)論可以得到求解模塊運動空間的算法1。

圖7 模塊在平面內(nèi)運動的所有可能情況Fig.7 All possible cases of module motion in the plane

算法1 運動空間輸入:位置矩陣V,模型i坐標(biāo)vi輸出:運動空間Ci1:if i為構(gòu)型的割點then2: Ci=03:else4: Ci=0 %運動空間初始化為空集5: Vη^i←相鄰位置6: Vηi←f∩(Vη^i,V)7: for all j∈η do8: for all 可能旋轉(zhuǎn)的方向d do9: 計算Vπ2和Vπ10: if f∩(Vπ2,V)=0 then11: if f∩(Vπ,V)=0 then12: 將vπ2加入Ci13: else if f∩(Vπ2,V)≠0 then14: 將vπ加入Ci15: end if16: end if 17: end for18: end for 19:end if20:return Ci

輸入任意構(gòu)型C的位置矩陣V和構(gòu)型中任意模塊i的坐標(biāo)vi，算法1可以求解i在C中的運動空間。首先判斷i是否是C的割點。如果是，i的運動空間為空集。模塊根據(jù)自身連接向量搜索到相鄰模塊。遍歷繞該相鄰模塊旋轉(zhuǎn)的4個 移動方向，計算旋轉(zhuǎn)經(jīng)過的位置。根據(jù)定理3確定在各方向旋轉(zhuǎn)的角度，將旋轉(zhuǎn)到達(dá)的位置添加到i的運動空間中。對每一個相鄰模塊都按上述方法操作就能得到模塊的運動空間。

3.3 立方體模塊的旋轉(zhuǎn)運動特性分析

當(dāng)模塊i有5個相鄰模塊時，i不能運動。當(dāng)i有4個相鄰模塊時，如果這4個模塊在同一平面那么i同樣無法運動；當(dāng)這4個相鄰模塊不在同一平面時，為保證構(gòu)型連通性，模塊可以移動的必要條件是這4個相鄰模塊自身至少有2個相鄰模塊。如圖8中所示，由于橢圓形中的3個模塊除了運動模塊沒有其他相鄰模塊，導(dǎo)致這種翻出運動無法進(jìn)行。

模塊i有3個相鄰模塊時，i的運動可分為兩類情況：① 3個相鄰模塊中存在2個模塊在同一軸線方向；② 3個相鄰模塊中任意2個模塊不在同一軸線方向，如圖9所示。第1種情況i只能繞與其他2個模塊不在一條直線上的相鄰模塊運動，需要克服較大的阻力，稱為“翻出”運動。

模塊i有2個相鄰模塊時，圍繞i可以構(gòu)成直線型結(jié)構(gòu)和“L”型結(jié)構(gòu)，如圖10所示。在直線型結(jié)構(gòu)中i不能運動。模塊i有1個相鄰模塊時，i在4個方向均能旋轉(zhuǎn)，旋轉(zhuǎn)角度取決于相鄰模塊的連接情況。

通過算法1可以列出模塊所有可能的運動情況，稱為模塊的運動空間構(gòu)型庫。限于篇幅，以下僅列舉部分，如圖11所示。

圖8 4相鄰模塊運動的連通性Fig.8 Connectivity of four adjacent module motion

圖9 3相鄰模塊的兩類情況Fig.9 Two types of three adjacent modules

圖10 “L”型結(jié)構(gòu)和直線型結(jié)構(gòu)Fig.10 “L” structure and straight structure

圖11 模塊部分連接情況的運動空間Fig.11 Motion space of several situations of module connection

4 基于分層規(guī)劃的重構(gòu)算法

自重構(gòu)問題可以分解為挑選模塊和移動模塊兩個子任務(wù)的組合，因而適合采用分層規(guī)劃策略解決。根據(jù)Kuhn-Munkres算法明確在軌自重構(gòu)結(jié)束后模塊的最終位置，利用廣度優(yōu)先搜索求解模塊的最短移動路徑，就可以完成重構(gòu)規(guī)劃。

4.1 解決自重構(gòu)問題的分層模型

在自重構(gòu)過程中，每一步移動都會對之后的重構(gòu)過程產(chǎn)生影響，這種影響往往是難以預(yù)測的。有些影響不會在下一步直接體現(xiàn)出來，而是在若干步后才開始體現(xiàn)。自重構(gòu)問題的這一特點決定了重構(gòu)規(guī)劃是復(fù)雜且不確定的。

涉及大量模塊在三維空間內(nèi)運動，直接尋找由初始構(gòu)型到目標(biāo)構(gòu)型的運動路徑十分困難，本文提出將初始構(gòu)型到目標(biāo)構(gòu)型的運動拆分為初始構(gòu)型到中間構(gòu)型、中間構(gòu)型到中間構(gòu)型、中間構(gòu)型到目標(biāo)構(gòu)型的運動。分解的目的在于將一條復(fù)雜構(gòu)型到復(fù)雜構(gòu)型的完整運動路徑拆分成多段簡單構(gòu)型到簡單構(gòu)型的運動路徑，降低運動規(guī)劃的難度，增加了運動規(guī)劃的可操作性。針對上述路徑拆分的思想，本文提出分層運動規(guī)劃方法:上層運動規(guī)劃解決經(jīng)歷哪些中間構(gòu)型的問題，屬于構(gòu)型間的規(guī)劃;下層運動規(guī)劃解決簡單構(gòu)型到簡單構(gòu)型之間，單個模塊由初始位置到目標(biāo)位置的運動路徑問題，屬于單個模塊的最優(yōu)路徑問題。

雖然傳統(tǒng)的動態(tài)規(guī)劃算法同樣可以降低前面構(gòu)型變換步驟對后續(xù)變換的影響，但動態(tài)規(guī)劃的優(yōu)勢在于解決具有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。在本文提出的問題模型下，尋找最優(yōu)子結(jié)構(gòu)較為困難，因而這一方法并不適用。

算法2 分層規(guī)劃輸入:位置矩陣Va,Vb1:\Kuhn-Munkres算法2:for all eij∈G=(Ga,Cb;E) do3: 最短路徑←最短路徑(vi,vj,Vka)4: 按最短路徑將ai移動到bi5: Vk+1a←移動后的位置矩陣6:end for7:return (Vka)

可以看出，上層規(guī)劃是一個指派問題，它將目標(biāo)位置分配給具體的模塊衛(wèi)星去填充。將分配好任務(wù)的一模塊按下層規(guī)劃得到的最短路徑移動到它被指派的目標(biāo)位置的過程稱為構(gòu)型更新。完成一次構(gòu)型更新可以得到一個中間構(gòu)型。通過合理中間構(gòu)型就可以在有限步構(gòu)型更新內(nèi)完成自重構(gòu)。每一次構(gòu)型更新都會從目標(biāo)構(gòu)型中尚未有模塊到達(dá)位置中挑選一個目標(biāo)位置，并從當(dāng)前構(gòu)型挑選一個模塊移動到該位置。

分解前的原規(guī)劃問題不能在多項式時間內(nèi)驗證其最優(yōu)解，是一個典型的非確定性問題。經(jīng)過分解得到的指派問題和最短路徑問題都是可以在多項式時間內(nèi)解決的確定性問題，從而降低了問題的不確定性。

4.2 基于二分圖模型的最優(yōu)分配模型

對于兩個模塊數(shù)目均為n的構(gòu)型Ca和Cb,ai和bi分別為其中的節(jié)點。它們之間可以建立一種映射：f:Ca→Cb，將構(gòu)型中Ca的節(jié)點ai與構(gòu)型Cb中的節(jié)點bi對應(yīng)起來，稱之為構(gòu)型Ca和Cb之間的匹配。簡單匹配問題是將構(gòu)型Ca和Cb中的節(jié)點對應(yīng)，通過簡單匹配可以找到上層規(guī)劃的一種可能的解。但這個解并不一定是最優(yōu)的。要找到一種使構(gòu)型改變幅度最小的自重構(gòu)方法需要在上層規(guī)劃中進(jìn)行權(quán)重匹配。解決這一權(quán)重匹配問題需要建立基于二分圖理論的最優(yōu)分配模型。

給出如下定義：

定義1(曼哈頓矩陣)構(gòu)型Ca和Cb的曼哈頓矩陣D為一個n×n的矩陣，矩陣中的元素D(i,j)為ai與bi之間的曼哈頓距離。

定義2(匹配矩陣)匹配矩陣M為一個n階方陣，M(i,j)∈{0,1}。M(i,j)=1表示ai與bi匹配。當(dāng)匹配完成時，rank(M)=n。

定義3(分配度量)所有匹配在一起的節(jié)點ai與bj的權(quán)重之和作為構(gòu)型Ca和Cb的分配度量，用δ表示。δ=trace(M×D)。

定義4(權(quán)重矩陣)常用的最優(yōu)分配算法往往用于求解分配度量的最大值，而上層規(guī)劃要求曼哈頓距離之和最小，因此要做如下轉(zhuǎn)化：

W(i,j)=dmax-D(i,j)

(12)

在權(quán)重匹配中，分配度量最大的一種分配稱為最優(yōu)分配。其分配度量稱為最優(yōu)分配度量，用δC表示。最優(yōu)分配度量可以作為兩個構(gòu)型之間的一種度量函數(shù)，它滿足度量函數(shù)應(yīng)具備的3條性質(zhì)[18]。

將權(quán)重矩陣中的元素作為節(jié)點ai和bi之間的邊eij的權(quán)重，可以得到賦權(quán)二分圖：G=(Ca,Cb;E)。每一種匹配方式都有其對應(yīng)的賦權(quán)二分圖。尋找最優(yōu)分配的任務(wù)轉(zhuǎn)化為了尋找賦權(quán)二分圖G=(Ca,Cb;E)使權(quán)重和最小的圖論問題。

在二分圖理論中，若Ca的每個頂點都與Cb的每個頂點相連，則稱為完全二分圖。用匹配矩陣表示二分圖：

(13)

4.3 上層規(guī)劃的Kuhn-Munkres算法

利用Kuhn-Munkres(K-M)算法可以得到二分圖的最優(yōu)分配[19-20]。首先介紹算法過程中幾個概念的定義。

定義5(頂點標(biāo)記)給二分圖中每個節(jié)點都賦予一個實數(shù)值，稱這個值為節(jié)點的頂點標(biāo)記，用l表示。

若一個匹配是最佳匹配，那么所有匹配在一起的節(jié)點ai和bi的頂點標(biāo)記應(yīng)該滿足:

l(ai)+l(bj)=W(i,j)

(14)

式(14)稱為最佳匹配問題的邊界條件。

定義7(交錯路)[21]設(shè)M是G的匹配，G的M交錯路是指其邊在EM的M中交錯出現(xiàn)的路。

算法開始前對節(jié)點的頂點標(biāo)記進(jìn)行初始化：

(15)

初始化后，按照邊界條件至少有一對節(jié)點可以形成匹配，即相等子圖中至少包含一條邊。按照如下方法修改頂點標(biāo)記l

(16)

更改交錯路中頂點的頂點標(biāo)記：

(17)

通過修改頂點標(biāo)記可以擴(kuò)大相等子圖的范圍。在相等子圖中進(jìn)行匹配的問題可以轉(zhuǎn)化為簡單匹配問題，用匈牙利算法解決[22]。直到相等子圖中包含構(gòu)型Ca和Cb中的所有節(jié)點，在相等子圖中求簡單匹配就可以得到二分圖的最佳匹配。算法3如下。

算法3 Kuhn-Munkres算法輸入:位置矩陣Va,Vb1:D←曼哈頓矩陣2:l(xi)←minb∈B d(ai,b);l(yj)←03:while?aj?^Ca do4: 生成相等子圖^G5: 用匈牙利算法在^G中尋找最大匹配6: 調(diào)整可行頂點標(biāo)記7:end while8:return(eij)

用圖2中的自重構(gòu)過程驗證此上層規(guī)劃算法，初始構(gòu)型和目標(biāo)構(gòu)型之間的曼哈頓矩陣為

利用Kuhn-Munkres算法求解出上層規(guī)劃的匹配矩陣為

在上述曼哈頓矩陣中框出匹配模塊之間的曼哈頓距離?？梢杂嬎愠錾蠈右?guī)劃的曼哈頓距離和為9，是所有匹配中的最小值。

4.4 基于最短路徑的下層規(guī)劃

利用上層規(guī)劃已經(jīng)求解出了每個模塊自重構(gòu)后應(yīng)該到達(dá)的位置，根據(jù)模塊當(dāng)前位置和目標(biāo)位置可以通過下層規(guī)劃設(shè)計出每個模塊運動的最短路徑。

要解決最短路徑問題，必須要先建立相應(yīng)的帶權(quán)有向圖。在下層規(guī)劃中，對于一個模塊在其運動空間中的模塊權(quán)重為1，其他模塊權(quán)重為∞。本文采用廣度優(yōu)先搜索，可以在建圖的同時找到最短路徑。

一個模塊在當(dāng)前構(gòu)型下可以到的所有位置可以構(gòu)成一個搜索樹。p表示樹中節(jié)點的層號，其在路徑規(guī)劃中的意義是模塊運動的步數(shù)，w表示第p層中的節(jié)點序號。在搜索的過程中，標(biāo)記節(jié)點的父節(jié)點。從根節(jié)點出發(fā)，直到搜索到目標(biāo)位置停止搜索。從目標(biāo)位置依次回溯父節(jié)點可以得到模塊從當(dāng)前位置移動到目標(biāo)位置的一條路徑。由于是逐層進(jìn)行搜索，搜索到的目標(biāo)位置必是層號最小的一個。這就意味著得到的路徑運動步數(shù)最少，是最短路徑。

5 算例與仿真

用一個10模塊的模塊化可重構(gòu)衛(wèi)星在軌自重構(gòu)來驗證本文所設(shè)計的重構(gòu)規(guī)劃策略的有效性，衛(wèi)星初始構(gòu)型和目標(biāo)構(gòu)型的位置矩陣為

圖12和圖13分別為初始構(gòu)型和目標(biāo)構(gòu)型的示意圖。圖14為分層規(guī)劃算法(算法2)得到的模塊運動方式(即自重構(gòu)問題的解)，圖中白色立方塊表示運動模塊的初始位置，深灰色立方塊表示不移動模塊，黑色立方體表示運動模塊的目標(biāo)位置，淺灰色立方塊表示模塊移動的路徑。可以看出經(jīng)過6個模塊共計19步運動，衛(wèi)星由初始構(gòu)型最終變?yōu)槟繕?biāo)構(gòu)型，完成了在軌自重構(gòu)。

圖12 初始構(gòu)型Fig.12 Initial configuration

圖13 目標(biāo)構(gòu)型Fig.13 Target configuration

圖14 移動第1～6個模塊Fig.14 Move the first to sixth module

為了減少文章篇幅和避免重復(fù)，只給出第1個 模塊移動路徑的位置矩陣：

同時給出第1個模塊的另外2條移動路徑的位置矩陣：

可以看出下層規(guī)劃中本文采用的廣度優(yōu)先搜索可以得到模塊移動的最短路徑。

按模塊數(shù)目從6～50隨機(jī)生成在軌自重構(gòu)任務(wù)，按本文提出的算法對這些任務(wù)進(jìn)行規(guī)劃。得到執(zhí)行重構(gòu)策略的模塊移動總步數(shù)，如圖15所示。

為方便觀察總步數(shù)隨模塊數(shù)目增加的變化趨勢，以每增長5個模塊為一組取步數(shù)的平均值，可以看出隨模塊數(shù)目增加該算法求解出的重構(gòu)方案所需的移動總步數(shù)近似線性增長。

圖16為按照本文提出的算法對上述在軌自重構(gòu)任務(wù)進(jìn)行規(guī)劃的重構(gòu)未完成度α,α的計算方式為

(18)

同樣為方便觀察α隨模塊數(shù)目增加的變化趨

圖15 自重構(gòu)所需的總步數(shù)Fig.15 Total step to self-reconfogurate

勢，以每增長5個模塊為一組取步數(shù)的平均值?？梢钥闯霰疚奶岢龅乃惴ǜm用于模塊數(shù)目較多的在軌自重構(gòu)任務(wù)。

利用本文設(shè)計的分層規(guī)劃策略對500個隨機(jī)在軌自重構(gòu)問題進(jìn)行求解，這些自重構(gòu)問題中模塊的數(shù)目在6～105之間。圖17為按Kuhn-Munkres算法設(shè)計的中間構(gòu)型的結(jié)構(gòu)跨度。在圖中，單位長度為模塊的邊長。

圖16 重構(gòu)算法的未完成度Fig.16 Unreconfigurated rate of algorithm

圖17 在軌自重構(gòu)過程中中間構(gòu)型的結(jié)構(gòu)跨度Fig.17 Structural span of intermediate configuration during rail self-reconfiguration process

以直線構(gòu)型作為中間構(gòu)型[14]，結(jié)構(gòu)跨度等于模塊數(shù)目。因此可以將直線y=n作為參考曲線?？梢钥闯觯凑辗謱右?guī)劃策略進(jìn)行重構(gòu)可以有效減小中間構(gòu)型的結(jié)構(gòu)跨度，從而起到避免大幅振動的效果。

6 結(jié) 論

本文基于自重構(gòu)過程的離散運動模型，面向模塊化可重構(gòu)衛(wèi)星，提出了一種在軌自重構(gòu)分層規(guī)劃算法。

1) 創(chuàng)新性地提出用分層規(guī)劃策略解決重構(gòu)規(guī)劃問題?；诙謭D模型，利用Kuhn-Munkres算法求解上層規(guī)劃，實現(xiàn)了中間構(gòu)型的動態(tài)設(shè)計。下層規(guī)劃中利用廣度優(yōu)先搜索可以得到模塊移動的最短路徑。

2) 仿真實驗表明，本文設(shè)計的算法可以完成初始構(gòu)型和目標(biāo)構(gòu)型中模塊間的最優(yōu)匹配以及實現(xiàn)重構(gòu)規(guī)劃問題的求解。并且驗證了相比現(xiàn)有算法可以減小中間構(gòu)型的結(jié)構(gòu)跨度，更適合應(yīng)用于航天領(lǐng)域。