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

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

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

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

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

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

圖1 利用空間鏈式自重構機器人進行裝配、 合作操縱和自我修復的構想[3]Fig.1 Idea of using space chain self-reconfigurable robots for assembly, cooperative manipulation and self-repair[3]

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

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

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

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

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

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

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

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

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

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

圖4 構型的拓撲連接圖Fig.4 Topological connection diagram of configuration

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

2.2 構型的位置矩陣

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

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

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

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

2.3 構型的連接矩陣

(1)

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

vk=vi+N(k)

(2)

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

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

(3)

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

3 自重構過程中的運動空間與運動特性

在相對位置的約束下可以對模塊的運動進行離散化分析，研究模塊一步運動結束后到達的位置，以此建立自重構運動模型。

3.1 立方體模塊旋轉運動的PCM模型

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

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

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

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

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

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

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

圖5 PCM模型下的模塊旋轉運動Fig.5 Module rotation under PCM model

3.2 模塊在當前構型下的運動空間及其求解

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

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

(4)

式中:i為旋轉模塊；vi為其坐標向量。在旋轉過程中，模塊運動的路徑經過圖6中的位置1、2。

(5)

式中:v1、v2分別是位置1、2的坐標向量，表達式為

v1=2vi-vj

(6)

v2=2vi-vj+N(d)

(7)

式中：j為相鄰模塊；vj為其坐標向量。

同理可得模塊旋轉π到達的位置可以表示為

vπ=vj+N(d)

(8)

(9)

式中：v3、v4分別為位置3、4的坐標向量，表達式為

圖6 旋轉過程中掃過的位置Fig.6 Swept position during rotation

v3=vi+2N(d)

(10)

v4=vj+2N(d)

(11)

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

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

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

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

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

算法1 運動空間輸入:位置矩陣V,模型i坐標vi輸出:運動空間Ci1:if i為構型的割點then2: Ci=03:else4: Ci=0 %運動空間初始化為空集5: Vη^i←相鄰位置6: Vηi←f∩(Vη^i,V)7: for all j∈η do8: for all 可能旋轉的方向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

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

3.3 立方體模塊的旋轉運動特性分析

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

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

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

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

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

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

圖10 “L”型結構和直線型結構Fig.10 “L” structure and straight structure

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

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

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

4.1 解決自重構問題的分層模型

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

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

雖然傳統(tǒng)的動態(tài)規(guī)劃算法同樣可以降低前面構型變換步驟對后續(xù)變換的影響，但動態(tài)規(guī)劃的優(yōu)勢在于解決具有重疊子問題和最優(yōu)子結構性質的問題。在本文提出的問題模型下，尋找最優(yō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ī)劃是一個指派問題，它將目標位置分配給具體的模塊衛(wèi)星去填充。將分配好任務的一模塊按下層規(guī)劃得到的最短路徑移動到它被指派的目標位置的過程稱為構型更新。完成一次構型更新可以得到一個中間構型。通過合理中間構型就可以在有限步構型更新內完成自重構。每一次構型更新都會從目標構型中尚未有模塊到達位置中挑選一個目標位置，并從當前構型挑選一個模塊移動到該位置。

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

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

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

給出如下定義：

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

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

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

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

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

(12)

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

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

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

(13)

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

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

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

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

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

(14)

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

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

算法開始前對節(jié)點的頂點標記進行初始化：

(15)

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

(16)

更改交錯路中頂點的頂點標記：

(17)

通過修改頂點標記可以擴大相等子圖的范圍。在相等子圖中進行匹配的問題可以轉化為簡單匹配問題，用匈牙利算法解決[22]。直到相等子圖中包含構型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: 調整可行頂點標記7:end while8:return(eij)

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

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

在上述曼哈頓矩陣中框出匹配模塊之間的曼哈頓距離。可以計算出上層規(guī)劃的曼哈頓距離和為9，是所有匹配中的最小值。

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

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

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

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

5 算例與仿真

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

圖12和圖13分別為初始構型和目標構型的示意圖。圖14為分層規(guī)劃算法(算法2)得到的模塊運動方式(即自重構問題的解)，圖中白色立方塊表示運動模塊的初始位置，深灰色立方塊表示不移動模塊，黑色立方體表示運動模塊的目標位置，淺灰色立方塊表示模塊移動的路徑?？梢钥闯鼋涍^6個模塊共計19步運動，衛(wèi)星由初始構型最終變?yōu)槟繕藰嬓?，完成了在軌自重構?/p>

圖12 初始構型Fig.12 Initial configuration

圖13 目標構型Fig.13 Target configuration

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

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

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

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

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

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

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

(18)

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

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

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

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

圖16 重構算法的未完成度Fig.16 Unreconfigurated rate of algorithm

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

以直線構型作為中間構型[14]，結構跨度等于模塊數(shù)目。因此可以將直線y=n作為參考曲線。可以看出，按照分層規(guī)劃策略進行重構可以有效減小中間構型的結構跨度，從而起到避免大幅振動的效果。

6 結 論

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

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

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