李生，李明宇，方 舟，黃俊杰，王楨，易朋興

（1.海裝駐武漢地區(qū)第三軍代表室，湖北 武漢 430000；2.武漢第二船舶設計研究所，湖北 武漢 430205；3.華中科技大學 機械科學與工程學院，湖北 武漢 430074）

0 引言

在艦船維修環(huán)境中，往往存在大量其他零部件障礙物阻礙維修人員的通行、視線及工具拿取，極大影響了維修效率。在艦船維修的問題上如能提前對前往維修點做好相應的路徑規(guī)劃，那么將節(jié)省大量的人力物力與時間。因此，在艦船維修問題上對維修人員進行路徑規(guī)劃尤為重要。

路徑規(guī)劃問題分為全局路徑規(guī)劃與局部路徑規(guī)劃，或根據(jù)地形是否發(fā)生改變分為靜態(tài)路徑規(guī)劃與動態(tài)路徑規(guī)劃，目前常用的路徑規(guī)劃算法主要有：傳統(tǒng)算法，如人工勢場法[1]等；智能仿生學算法，如強化學習[2]、遺傳算法[3]、退火算法[4]、粒子群算法[5]等；圖搜索算法，如A*算法[6]。Lu等提出了基于環(huán)境多尺度分解的擴展LPA*算法，即使在最壞的情況下也比LPA*算法的頂點擴展少，但并未適應到動態(tài)路徑規(guī)劃中[7]。國內的許多高校針對路徑規(guī)劃問題也提出一些解決方案。卜新萍等通過融合最大最小蟻群算法與蟻群系統(tǒng)算法的信息素更新方式，改進了蟻群算法，比基本蟻群算法相比具有更快的收斂度，且結果適應性更強[8]。王嘉祺等研究了虛擬人基于并行計算構架的視覺感覺與記憶模型，提出了一種基于A*算法的雙層全局路徑規(guī)劃的方法[9]。根據(jù)對近年來國內外學者對虛擬維修與路徑規(guī)劃的研究成果分析，發(fā)現(xiàn)目前的路徑規(guī)劃算法在面對復雜地形和空間環(huán)境下存在不足，難以提出合理的路徑，本研究的路徑規(guī)劃算法采用啟發(fā)式搜索算法，針對復雜環(huán)境中的虛擬維修問題，結合虛擬人通行方式的研究，對當前流行的LPA*算法進行了適當?shù)母倪M，并對算法進行了實驗與驗證。

1 LPA＊算法

LPA*算法屬于基于圖的啟發(fā)式搜索算法[10]，因此在使用啟發(fā)式搜索算法前，需要先進行網格繪制。

LPA*算法從第一個網格sstart開始向下擴展，直到擴展到最后一個網格send或者向下沒有可擴展的網格為止。LPA*算法中存在優(yōu)先級函數(shù)k（s），其定義如下：

其中，g（s）表示從sstart到s的各種損失，rhs（s）是g（s）的一步前瞻估計值，即在擴展到s點前的一個前瞻損失。rhs（s）的定義如下：

其中，c（s，s'）表示從s網格到達s'網格的損失，pred（s）是s的路徑直接前驅的集合。當時g（s）＞rhs（s），稱網格是過一致的；當g（s）＞rhs（s）時，稱網格s是欠一致的；當g（s）=rhs（s）時，稱網格s是一致的。

基于LPA*算法進行路徑規(guī)劃，在準備擴展到某一網格s前，會比較g（s）和rhs（s）的值。如果g（s）＞rhs（s），直接確定g（s）=rhs（s），從而讓其取值一致。與此同時，繼續(xù)計算s周邊未被擴展到的網格s'的rhs（s'）值，讓其加入到優(yōu)先級隊列中，直到擴展到最后一個網格。

2 對虛擬人通行方式的研究

在實際環(huán)境下，維修人員會將舒適度置于首位，即把選擇身體舒適度更高的路徑放在首位。因此，可以將身體舒適度視為路徑規(guī)劃過程的一項重要指標。

2.1 直行與側行的通行要求

維修人員行走時通常會手持工具或零部件。因此相比于側行，直行方式的舒適程度更高，工作人員更傾向于直行，因此虛擬人的行動方式也應該選擇為直行。不同的行走方式在前進方向上身體寬度均不相同，因此在計算簡便的要求下網格寬度需要根據(jù)身體寬度情況進行調整。李保和依據(jù)國標GB10000-1988針對中國海軍軍人的身體尺寸進行網格尺寸優(yōu)化[11]。本設置虛擬人直行狀態(tài)下肩部是最寬部位，寬度為465 mm；側行狀態(tài)下臀部是最寬部位，寬度為222 mm。

網格寬度設定為125 mm×125 mm。沿網格邊直行與側行分別需要橫跨kstraightEdge與ksideEdge個網格，沿網格對角線直行與側行分別需要橫跨kstraightDiag與ksideDiag個網格。經過計算，kstraightEdge、ksideEdge、kstraightDiag與ksideDiag滿足的要求分別為4、2、3、2。

虛擬人通過的網格為多網格通行，需要將周圍多個網格的狀態(tài)綜合考慮。為便于網格狀態(tài)分析，將修改參考點的位置。若將問題簡單化，可以設定網格邊長為500 mm，以確保橫行與側行時虛擬人都可以在單網格中通過。但在復雜環(huán)境中，此法可能會導致無法規(guī)劃出可行路徑。以8網格通道為例子，將網格與網格的交界點作為路徑參考點，則虛擬人將以交界點為參考通行如圖1所示。將規(guī)劃路徑的寬度設定為2個網格邊長之和或為1個網格的對角線長。沿邊通過時，需要考慮該邊左右兩網格的狀態(tài)；沿對角線通過時，需要考慮此對角線末端點左右兩格的狀態(tài)，因此，在圖1中路徑A→B→C→D合理。

圖1 多網格通行的路徑規(guī)劃

對參考點提出了更嚴格要求。根據(jù)前文計算的kstraightEdge、ksideEdge、kstraightDiag與ksideDiag，在直行情況下：（1）沿邊通過下該邊左右各2格（總計4格）應為可通行狀態(tài)；（2）沿對角線通過時對角線所在的網格、對角線左右各1格（總計3格）應為可通行狀態(tài)，并且對角線末端點的左1格、右2格或是左2格、右1格應為可通行狀態(tài)。在側行情況下：（1）沿邊通過下該邊左右各1格（總計2格）可通行；（2）沿對角線通過時需要對角線所在網格、對角線左1格或右1格（總計2格）可通行，并且對角線末端點左右各1格網格可通行。

2.2 爬行與攀爬的通行要求

上述二維網格路徑規(guī)劃方法對三維空間高度不敏感。在實際艦船維修過程中，維修人員一般借助梯子進行攀爬越障，當攀爬上某些設備后，在設備上或在有懸空障礙物的地面上行進時，無法站立行走，只能通過爬行。下面對虛擬人爬行與攀爬的路徑規(guī)劃的進行了研究。

二維網格存在Hblock與Hspace屬性，其中Hblock是影響攀爬的關鍵因素，而Hspace是影響行進方式的關鍵因素。當前后兩個參考點的Hblock差值較大，虛擬人需要攀爬。當Hspace較大，可以站立前進；Hspace較小，虛擬人只能爬行。直行與側行過程中虛擬人站立前進，而爬行過程中虛擬人跪著前進，前進需要的空間高度分別由虛擬人在站立時高度與跪著時的高度決定。本設置虛擬人站立身體高度均值為1696 mm，爬行身體高度均值為550 mm。據(jù)此可計算站立前進需要的空間高度最小值HspaceStand和爬行前進需要的空間最小值HspaceCrawl，分別為9和4。

在Hblok＞0時，由于不在地面上，虛擬人需向上攀爬，攀爬時需要用雙手抓建筑，身體的寬度理論應與直行寬度一致，同時實際條件下高處側行較危險，故規(guī)定攀爬后只能直行或爬行，在二維網格加入Hblok與Hspace屬性的限制下，網格增加可爬行屬性。網格的狀態(tài)與其Hblock與Hspace值的關系見表1。

表1 網格的條件與狀態(tài)

據(jù)此，得到各通行方式在考慮攀爬與爬行后對對網格與參考點的高度與寬度的通行要求：（1）當?shù)孛嬷毙谢蚺佬醒剡厱r，邊左右各2格網格可通行或爬行；沿對角線時，對角線左右各1格、總計3格網格可通行或爬行；對角線末端點左1格、右2格或左2格、右1格可通行或爬行。（2）當?shù)貍刃醒剡厱r，邊左右各1格網格可通行；沿對角線時，對角線左或右1格、總計2格網格可通行；對角線末端點的左右各1格網格可通行。（3）當攀爬直行或爬行沿邊時，邊左右各2格網格可通行且具有一致Hblok＞0；沿對角線時，對角線左右各1格、總計3格網格可通行或爬行且具有一致Hblok＞0；對角線末端點左1格、右2格或左2格、右1格可通行或爬行且具有一致Hblok＞0。由此可知有6種狀態(tài)：地面直行、地面?zhèn)刃小⒌孛媾佬?、攀爬后直行，攀爬后爬行與不可通過。

3 改進LPA＊算法及驗證分析

3.1 虛擬人通行方式對路徑規(guī)劃的改進

在LPA*算法中，不同的參考點具有的不同通行方式與是否攀爬是路徑規(guī)劃中的評判因素，這些因素導致rhs（s）發(fā)生變化。原始算法中的rhs（s）可以看作直行且未攀爬從sstart到s，而側行、爬行會增加通行的損失。在每兩個網格s、s'之間，給rhs（s）的組成項c（s，s'）增加一個系數(shù)w（s），以系數(shù)w（s）體現(xiàn)虛擬人通行特征對算法的影響，得到新的rhs1（s）的表達式，不考慮s=sstart時，rhs1（s）如下式所示：

其中w（s）∈{w0，w1，w2}為不同通行方式所對應的系數(shù)，且w0≤w1≤w2，w0、w1、w2分別代表直行、側行、爬行。

在此之外，當Hblock變化時需要進行攀爬動作。攀爬分為向上和向下攀爬兩個方向。攀爬的難度根據(jù)前后兩個參考點的Hblock差值的絕對值來確定，差值越大攀爬難度越大。以線性方式計算攀爬帶來的損失，從而可得rhs2（s）的表達式如下：

其中Hblock（s）與Hblock（s'）分別是s與s'的Hblock，的值需要一個上限，用來限制虛擬人的攀爬上限，將其設置為10。w3（s）∈{0，w3，∞}為系數(shù)，其值視障礙物高度差而定，當高度差小于等于1時為0（高度差小于等于1表示虛擬人在實際環(huán)境中能直接跨越，高度差大于1時認為需要攀爬），當高度差超過所設上限時取無窮大，代表該網格無法通過，其他情況取常數(shù)。根據(jù)不同的通行方式，w0、w1、w2、w3的非極限取值見表2。

表2 通行損失系數(shù)取值

結合式5與式6得到改進的rhs（s）的表達式如下。

當路勁規(guī)劃過程到某網格時，其g（s）=rhs（s），即該參考點一致，需要擴展其周圍8個參考點。根據(jù)周圍網格的狀態(tài)，利用式5分別計算這8個參考點的rhs（s）值以及h（s）值，然后計算k（s）放入優(yōu)先級隊列并排序，其余步驟與原LPA*算法一致，從而規(guī)劃出一條符合當下環(huán)境的路徑。

3.2 實驗驗證

根據(jù)上述改進的LPA*算法，進行路徑規(guī)劃實驗。在實驗中，根據(jù)虛擬維修的環(huán)境復雜特性，對三維空間進行了均勻網格劃分，并將三維網格通過附加屬性的方式轉換為二維網格。三維網格轉換為二位網格后帶攀爬的路徑規(guī)劃如圖2所示。圖2中，白色網格為可通行狀態(tài)，黑色網格為不可通行狀態(tài)，灰色網格為具有一定高度的障礙物，細線路徑為地面直行，中等粗線路徑為地面?zhèn)刃?，粗線路徑為攀爬后的直行，不考慮直行與側行轉換的代價。在不考慮攀爬時，圖2中虛線部分路徑通道較窄導致虛擬人無法通過，從而無法規(guī)劃出一條合理的路徑。在考慮攀爬后，虛擬人可以通過攀爬到達灰色障礙物上，在其上直行然后再攀爬下障礙物，最終目標點，結果見表3。

圖2 改進路徑規(guī)劃圖

表3 規(guī)劃對比結果表

根據(jù)上述實驗結果可知，改進LPA*算法通過引入通行方式，在路徑規(guī)劃中，能夠根據(jù)障礙物的特點，以不同的通行方式通過，從而可以規(guī)劃出額外可通行的路徑。

4 結語

本研究主要對路徑規(guī)劃研究中的LPA*算法進行了改進。主要是針對中國人體尺寸信息，結合艦船虛擬維修過程中的虛擬人通行特點，提出了虛擬人的4種通行方式：直行、側行、攀爬和爬行，最后根據(jù)各種通行方式對LPA*算進行了改進，使虛擬維修中面臨的路徑規(guī)劃問題可以解決更復雜的情況。對于一般的路徑規(guī)劃算法，只能對較長路徑進行規(guī)劃，無法解決短路徑問題。