岳程斐，張 梟，王宏旭，李宗凌，曹喜濱

(1. 哈爾濱工業(yè)大學(xué)(深圳) 空間科學(xué)與應(yīng)用技術(shù)研究院，深圳 518055；2. 哈爾濱工業(yè)大學(xué)衛(wèi)星技術(shù)研究所，哈爾濱 150001； 3. 北京空間飛行器總體設(shè)計部,北京 100094)

0 引 言

在軌操控機器人及在軌操控技術(shù)在未來大型航天裝備建造、維護、升級過程中將扮演重要的角色。在任務(wù)過程中，機器人需要在復(fù)雜環(huán)境下自由移動，包括狹小空間的自由穿行，同時還需要保證移動和操控過程中與被操控對象的接觸。因此，復(fù)雜環(huán)境下的三維全局路徑規(guī)劃成為實現(xiàn)移動和操控的前提和基礎(chǔ)。

機器人路徑規(guī)劃一般包括空間環(huán)境建模和運動軌跡的生成、迭代與優(yōu)化兩部分。空間環(huán)境建模方法主要有兩類：1)點云模型，即利用空間中離散的點云來描述空間環(huán)境的表面信息或者空間物體的坐標(biāo)信息；2)地形幾何模型，即利用正方形、矩形等規(guī)則形狀或三角形、多邊形等不規(guī)則形狀作為模型單元構(gòu)建空間環(huán)境模型。點云模型有較成熟的數(shù)據(jù)獲取技術(shù)，但一般用于物體表面信息的獲取，其不能直觀的表征物體的體積；以柵格地圖為代表的地形幾何模型又以二維模型為主，在地面路線規(guī)劃上有著廣泛的應(yīng)用。針對三維建模問題，文獻(xiàn)[4-5]將點云數(shù)據(jù)轉(zhuǎn)換成八叉樹結(jié)構(gòu)的三維柵格地圖，用來描述空間被占據(jù)的情況。文獻(xiàn)[6-7]則將多個二維柵格模型分層疊加，形成了三維高程模型。文獻(xiàn)[8]在文獻(xiàn)[6-7]基礎(chǔ)上添加了懸浮障礙，以獲取環(huán)境信息更為復(fù)雜的三維地圖。但是，目前基于空間分層思想的建模方法無法解決復(fù)雜桁架結(jié)構(gòu)或孔洞結(jié)構(gòu)的環(huán)境建模和繞回路徑規(guī)劃問題。

在運動軌跡的生成、迭代與優(yōu)化方面，國內(nèi)外許多學(xué)者對此進行了大量的研究。目前，粒子群算法、人工勢場法、A算法和蟻群算法等是較為常用的三維空間路徑規(guī)劃算法。文獻(xiàn)[9]采用粒子群算法針對自由漂浮空間機器人的關(guān)節(jié)角軌跡多項式插值系數(shù)進行優(yōu)化，以實現(xiàn)機械臂關(guān)節(jié)角耗散能最小；文獻(xiàn)[10]針對空間機械臂在軌跡規(guī)劃過程中可能陷入局部最優(yōu)的問題對粒子群算法進行了優(yōu)化，同時將減小基座擾動和機械臂的運動時間作為優(yōu)化指標(biāo)的一部分，得到了滿足減小基座姿態(tài)擾動及機械臂運動時間需求的空間機械臂軌跡。但是，以上兩篇文獻(xiàn)在規(guī)劃的過程中都沒有考慮空間環(huán)境障礙對機器人產(chǎn)生的約束。文獻(xiàn)[11]針對采用人工勢場法進行路徑規(guī)劃過程中的障礙可能會使路線陷入局部極值的問題，引入了一種細(xì)菌進化算法，得到了一種可以跳出局部極值的融合算法。但是，規(guī)劃過程中未考慮環(huán)境特性，全局搜索步長相同，規(guī)劃搜索效率仍有提升空間。文獻(xiàn)[12]在二維柵格地圖下基于地圖的平面結(jié)構(gòu)特征針對A算法中參數(shù)和跳點規(guī)則進行了改進，提高了算法的效率并縮短了路徑的長度。但是，轉(zhuǎn)化到三維空間下之后會存在數(shù)據(jù)量級指數(shù)級增加的問題。文獻(xiàn)[13-15]分別在不同的模型與工況下針對蟻群算法中的代價函數(shù)、信息素函數(shù)、概率選擇函數(shù)等進行了改進，以達(dá)到適應(yīng)不同任務(wù)的目的；文獻(xiàn)[16-18]將不同的路徑規(guī)劃算法進行了仿真和對比，分析了各個算法在性能上的差異，三維空間中的路徑規(guī)劃問題得到了部分解決，但現(xiàn)有研究均未考慮到環(huán)境的空間結(jié)構(gòu)特征并針對空間環(huán)境特性對算法進行改進，規(guī)劃效率較低。

基于以上調(diào)研，本文開展了在軌操控機器人包含空間站桁架中穿行應(yīng)用需求的三維全局路徑規(guī)劃問題研究。首先，采用三維單元柵格模型對桁架式空間站在軌操控空間環(huán)境以及機器人進行建模；其次，考慮穿行過程中的包絡(luò)約束和操控過程中的附著要求，對三維柵格模型進行預(yù)處理，封閉不滿足約束的空間，以減少路徑搜索域提升路徑搜索速度；再次，利用環(huán)境模型幾何特征對搜索路徑進行延拓，以調(diào)節(jié)搜索步長并利用拓鄰域搜索的一群算法得到滿足任務(wù)約束的最優(yōu)或近似最優(yōu)路徑。最后通過仿真驗證本文所提出算法的有效性。

1 空間環(huán)境和在軌操控機器人建模

1.1 環(huán)境模型

本文以國際空間站(International space station，ISS)為研究對象，對其結(jié)構(gòu)特征進行提取并簡化，并構(gòu)建三維柵格地圖環(huán)境模型。

在三維建模過程中，以空間站的對稱軸作為柵格空間的方向坐標(biāo)軸，綜合考慮環(huán)境的復(fù)雜程度、在軌操控機器人的尺寸、任務(wù)需求等選取柵格單元的實際像素大小。本文選取了具有桁架結(jié)構(gòu)特征的30×30×30柵格地圖作為仿真的環(huán)境模型。對應(yīng)的柵格地圖如圖1所示。

圖1 ISS三維柵格模型Fig.1 Three-dimensional raster model of the ISS

本文在算法驗證和圖形預(yù)處理過程中，將以圖1中放大部分為例，具體的三視圖如圖2所示。

圖2 三維柵格模型三視圖(局部)Fig.2 Three-view of three-dimensional raster model (part)

1.2 機器人模型

本文以某型空間操控機器人為研究對象，建立其剛球模型，即收縮狀態(tài)下的最小外接球，以描述其在空間站桁架中穿行時的包絡(luò)約束；選取空間操控機器人的自由操作空間描述操控任務(wù)的附著約束。

本文假定空間操控機器人剛球模型半徑為，其自由操作空間的半徑為。則在軌跡規(guī)劃過程中同時滿足包絡(luò)約束和附著要求的幾何約束可表示為：

=≤≤=

(1)

其中:為空間操控機器人剛球模型中心與障礙物的距離，和分別為滿足要求情況下的最大值和最小值。

2 預(yù)處理

由于為空間操控機器人剛球模型中心與障礙物體的距離，可得：

=-

(2)

式中：為障礙的位置;為剛球模型中心的位置。由式(1)(2)可以得到剛球模型中心位置的約束范圍：

-≤≤-

(3)

式(3)表明，機器人在運動過程中的剛球模型中心位置處于一個由障礙與自由操作空間半徑和剛球模型半徑共同決定的活動范圍內(nèi)。根據(jù)式(1)，將不滿足該條件的空間進行封閉，由此得到約束下的機器人路徑搜索可行域。

在三維路徑規(guī)劃過程中，機器人可搜索方向多，地圖信息維度高，為避免搜索過程中數(shù)據(jù)爆炸，在運算前需要對這些包含地圖屬性信息的相關(guān)數(shù)據(jù)按照八叉樹的規(guī)則進行儲存和處理，具體如圖3所示：

圖3 數(shù)據(jù)預(yù)處理Fig.3 Data preprocessing

該方法的具體處理規(guī)則如下：

1)將三維地圖均勻切割分成八個部分，每次分割記為一次操作，一次操作在數(shù)據(jù)儲存結(jié)構(gòu)中占據(jù)一層；

2)選定分割后的子區(qū)域按照相同方法進行切割，直到最小分割單元滿足路徑規(guī)劃最小像素單元精度要求；數(shù)據(jù)儲存則按照切割次數(shù)分層，并依據(jù)其在每次分割中占據(jù)的位置進行編碼、儲存和調(diào)用。

3 蟻群算法

蟻群算法(Ant colony optimization, ACO)是仿效自然界中蟻群由巢穴出發(fā)的覓食行為，根據(jù)其在行走過程中分泌的信息素信息，獲得最優(yōu)路徑的優(yōu)化方法。ACO算法的原理主要是依據(jù)兩個核心規(guī)則：可移動單元概率轉(zhuǎn)移規(guī)則和信息素更新規(guī)則。

3.1 可移動單元概率轉(zhuǎn)移規(guī)則

第代的第只螞蟻從當(dāng)前單元移動到下一個單元，首先需要確定下一步所有的可移動單元，并計算它們的轉(zhuǎn)移概率，依據(jù)每個單元的概率從所有的可移動單元中隨機選擇一個作為下一個路徑點?？梢苿訂卧D(zhuǎn)移概率如式(4)所示：

(4)

(5)

4 信息素更新規(guī)則

在第只螞蟻從單元移動到單元之后，將對信息素濃度()進行更新，其目的是使螞蟻已走過的信息素濃度減少，使后代螞蟻有著選擇其他路徑的傾向，避免路徑的解陷入局部最優(yōu)。更新信息素濃度的公式如式(6)(7)所示：

(6)

(7)

一般的，為了加快收斂速度，需要在轉(zhuǎn)移概率之前對轉(zhuǎn)移規(guī)則做預(yù)處理，如式(8)所示：

(8)

式中：參數(shù)(0<<1)為一個給定閾值，用以表征螞蟻的探索能力，(0<<1)為一個隨機生成的數(shù)。

為了表征算法的收斂速度，本文引入了收斂常數(shù)：

(9)

即第代螞蟻搜索到的最優(yōu)路徑長度相較于初始路徑長度減少量-與算法穩(wěn)定后路徑長度相較于初始路徑長度減少量-的比值，該值的取值范圍為0≤≤1。相同代數(shù)條件下，越大，收斂速度越快；相同數(shù)值情況下，值越小，算法收斂越快。

5 ACOBNCS算法

在三維空間的ACO算法中，螞蟻的每一步可移動節(jié)點在無障礙情況下為26個，相較于二維空間無障礙情況的8個可移動節(jié)點要多，螞蟻在選擇路徑的過程中，選擇到最優(yōu)路徑的概率也相應(yīng)的比二維空間要低，導(dǎo)致ACO算法規(guī)劃的路徑收斂性和平滑度較差。同時，三維空間下的信息素的數(shù)據(jù)規(guī)模也隨著維度的增加而指數(shù)級增加，這個現(xiàn)象在大地圖模型下變得更加明顯，成為導(dǎo)致運算速度變慢的主要原因之一。針對上述問題，提出了一種基于空間約束的桁架式結(jié)構(gòu)特殊節(jié)點搜索策略，在算法運行時，可以跳過某些桁架中大部分不需要計算的節(jié)點，僅計算桁架兩端特殊的節(jié)點。

5.1 可移動單元集合搜索策略

假設(shè)螞蟻的當(dāng)前節(jié)點為，下一步可移動單元集合為，對于任意的∈，都滿足以下的搜索規(guī)則：

1)與相鄰或位于同一直線上。

2)不為障礙且與之間也不存在障礙。

3)如果與不相鄰，那么在與相連所在的直線上，且必與障礙相鄰。

常規(guī)ACO算法在搜索時只考慮相鄰的單元，并沒有考慮到地圖的特性，本文改進的第2)條規(guī)則與第3)條規(guī)則可以使當(dāng)前節(jié)點所在軸線與障礙相鄰的末端直接加入到可移動單元的集合當(dāng)中去，直接跳過了該軸線上的搜索，即跳點。

ACOBNCS算法的搜索規(guī)則示意圖如圖4所示。圖中倒立π字形斜紋單元為障礙單元，五角星單元為當(dāng)前節(jié)點，豎條紋單元為ACO算法中下一步可以選擇的所有單元的集合，即ACO算法搜索可行域，橫條紋單元為ACOBNCS算法中在ACO搜索可行域基礎(chǔ)上，額外拓展的搜索單元，即ACOBNCS附加可行域。與ACO算法的搜索策略相比，可以看出在搜索可移動單元時軸向方向增加了若干個備選的節(jié)點，可以很大程度上減少搜索迭代次數(shù)。搜索路徑越長，效果就越明顯。

圖4 ACOBNCS示意圖Fig.4 Illustration of ACOBNCS

在桁架式結(jié)構(gòu)中，有多個桁架相連的關(guān)節(jié)處，會成為在與節(jié)點相連桁架上的螞蟻循跡過程中必經(jīng)過的點，而在桁架兩端關(guān)節(jié)之間的最優(yōu)路徑則是較為固定的。這些具有顯著特征的節(jié)點就稱為跳點。在某一區(qū)域的循跡過程中，如果螞蟻需要經(jīng)過這條桁架，那么必定會經(jīng)過桁架兩端的點，在其桁架上運動的路徑就不需要進行重復(fù)運算。

ACOBNCS算法的算法流程如圖5所示。

圖5 ACOBNCS算法流程Fig.5 Flowchart of ACOBNCS

6 仿真分析

本文利用Visual Studio 2019平臺實現(xiàn)上述算法，計算機環(huán)境為Intel(R) Core(TM) i7-8700 CPU @ 3.20 GHz，內(nèi)存32 GB，操作系統(tǒng)為Windows 10。分別對二維空間與三維空間下的ACO算法和ACOBNCS算法進行了對比仿真實驗。實驗中的蟻群算法相關(guān)參數(shù)見表1。

表1 算法參數(shù)設(shè)置Table 1 Algorithm parameter setting

6.1 ACO算法二維地圖與三維地圖對比仿真

ACO算法在30×30的二維隨機地圖和30×30×30的三維地圖仿真結(jié)果如圖6所示。二維地圖和三維地圖仿真結(jié)果詳細(xì)對比見表2。由其可知,隨著每部迭代可移動節(jié)點數(shù)增加,迭代運算時間顯著增加。

圖6 二維隨機地圖仿真結(jié)果Fig.6 Simulation results of 2D random map

表2 ACO算法兩種維度地圖下仿真數(shù)據(jù)對比Table 2 Simulation of ACO on two different dimensional maps

圖6和圖7分別給出了30×30二維隨機地圖和30×30×30三維地圖中最小路徑長度隨著迭代次數(shù)變化的曲線。在二維地圖中，算法的收斂速度和穩(wěn)定性較好。而在三維空間中，算法的收斂速度變慢，路徑結(jié)果較差，存在較多轉(zhuǎn)折點。隨著維度的增加，算法中每一步的可移動節(jié)點數(shù)在無障礙情況下由8個變成了26個，依據(jù)概率選擇公式得到最優(yōu)路徑的概率也隨之變小，導(dǎo)致尋優(yōu)路徑的迭代次數(shù)變多。

圖7 ACO算法最小路徑長度變化曲線Fig.7 Minimum path length curve of ACO

6.2 ACOBNCS算法三維地圖仿真

ACOBNCS蟻群算法仿真結(jié)果如圖8所示。

圖8 ACOBNCS最小路徑長度變化曲線Fig.8 Minimum path length curve of ACOBNCS

圖8和圖9給出了利用ACOBNCS算進進行仿真的結(jié)果。與圖7相比， ACOBNCS算法在迭代初期就有較大幅度收斂速度提升，在迭代57次時就達(dá)到了改進前最優(yōu)路徑的水平；最小路徑長度縮短了29.23%；除此之外，迭代運算時間也大幅縮短，能在短時間內(nèi)有效完成路徑規(guī)劃的任務(wù)。由表3可知，ACOBNCS算法較ACO算法性能上有大幅的提升。

圖9 ACOBNCS仿真結(jié)果Fig.9 Simulation results of ACOBNCS

表3 兩種算法三維地圖仿真數(shù)據(jù)對比Table 3 Simulation results of two algorithms in 3D map

6.3 ACOBNCS算法有無跳點對比仿真

本文將ACOBNCS算法分別在有跳點和無跳點的情況下進行了20次重復(fù)試驗，如圖10和表4所示。從表4統(tǒng)計規(guī)律可以看出有跳點的ACOBNCS算法收斂速度有著明顯的提升：收斂時的迭代次數(shù)平均減少了30.8次；=100時的收斂常數(shù)增加了0.1984；迭代運算的平均時間減少了3.65%，說明跳點規(guī)則可以有效的提升收斂速度；同時，ACOBNCS算法最小路徑的平均長度較ACO方法增加了11.20%，說明ACOBNCS可能陷入局部最優(yōu)。

表4 有無跳點的ACOBNCS算法重復(fù)試驗仿真數(shù)據(jù)對比Table 4 Simulation of the ACOBNCS with or without jump units

圖10 ACOBNCS重復(fù)試驗結(jié)果Fig.10 Results of ACOBNCS repeat tests

6.4 ACOBNCS算法ISS柵格地圖仿真

利用本文所提出的基于拓鄰域搜索的在軌操控機器人三維路徑規(guī)劃算法，選定國際空間站上的某兩點進行三維路徑規(guī)劃仿真，仿真結(jié)果如圖11所示。

圖11 ISS柵格模型上的路徑規(guī)劃結(jié)果Fig.11 Path planning results on ISS 3D raster model

7 結(jié) 論

針對空間在軌操控機器人在桁架式空間站中三維空間路徑規(guī)劃時存在的問題，本文提出的拓鄰域搜索蟻群算法可以滿足在較短的時間內(nèi)完成桁架間穿行且時刻與空間站保持接觸的需求。本文采用三維柵格法建立了桁架式空間站障礙模型并建立機器人剛球中心可行域模型，對地圖數(shù)據(jù)進行了預(yù)處理并基于鄰域延拓思想改進了可移動單元的搜索策略，調(diào)節(jié)搜索步長以提高運算速度，能夠有效的解決空間機器人執(zhí)行在軌操控任務(wù)時的全局路徑規(guī)劃問題，提高了機器人路徑規(guī)劃的速度與全局搜索能力。