多策略蟻群算法求解誘導(dǎo)維修路徑規(guī)劃*

饒楚鋒，韓華亭，瞿 玨，王 崴，彭勃宇

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安 710051）

多策略蟻群算法求解誘導(dǎo)維修路徑規(guī)劃*

饒楚鋒，韓華亭，瞿 玨*，王 崴，彭勃宇

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安 710051）

在誘導(dǎo)維修過(guò)程中，為了幫助維修者快速找到維修對(duì)象，提供高效安全的行走路徑，需要對(duì)復(fù)雜的維修環(huán)境進(jìn)行路徑規(guī)劃。傳統(tǒng)的蟻群算法收斂速度慢、易陷入局部最優(yōu)。為了提高尋優(yōu)效率，對(duì)基本蟻群算法進(jìn)行改進(jìn)。提出了對(duì)α、β的自適應(yīng)調(diào)整，改變信息素增量的更新方式，以及引入雙向搜索策略，有效地提高了算法的收斂速度和全局搜索能力。仿真結(jié)果表明，改進(jìn)的蟻群算法效率高，收斂速度快，能夠?yàn)樘幵趶?fù)雜維修環(huán)境中的維修人員提供高效的行進(jìn)路線。

誘導(dǎo)維修，路徑規(guī)劃，蟻群算法，自適應(yīng)，雙向搜索

0 引言

隨著我軍裝備不斷向大型復(fù)雜、技術(shù)密集的方向發(fā)展，在提升武器性能的同時(shí)還增大了維修的難度，提高了對(duì)維修人員的要求。誘導(dǎo)維修［1-3］是運(yùn)用增強(qiáng)現(xiàn)實(shí)技術(shù)將虛實(shí)疊加的顯示方式呈現(xiàn)在維修人員的市場(chǎng)中，在維修人員注意力集中的“維修區(qū)域”疊加顯示各類(lèi)圖形文字信息，以輔助和引導(dǎo)維修人員進(jìn)行維修作業(yè)，誘導(dǎo)維修系統(tǒng)能夠一步步地指導(dǎo)毫無(wú)經(jīng)驗(yàn)的用戶完成復(fù)雜的任務(wù)。

在進(jìn)行大型裝備的維修時(shí)，維修者所處環(huán)境較為復(fù)雜，加之佩戴頭盔式顯示設(shè)備的維修者視野受限，若不對(duì)其加以引導(dǎo)，很難快速找到和到達(dá)指定區(qū)域并將視角對(duì)準(zhǔn)維修目標(biāo)。此外，若人員在復(fù)雜維修空間內(nèi)隨意走動(dòng)，可能引起人員受傷或設(shè)備損壞等安全事故。因此，根據(jù)維修環(huán)境和維修任務(wù)，研究一種符合實(shí)際地形環(huán)境的維修路徑規(guī)劃方法是很有必要的。

蟻群算法［4］是由意大利學(xué)者M(jìn).Dorigo等人提出的，并最早成功應(yīng)用于解決旅行商問(wèn)題。蟻群算法具有正反饋性、并行性以及較強(qiáng)的魯棒性和較強(qiáng)的全局搜索能力［5］，廣泛應(yīng)用于航跡規(guī)劃、車(chē)輛路徑規(guī)劃、機(jī)器人路徑規(guī)劃等問(wèn)題。

針對(duì)蟻群算法的路徑規(guī)劃方面的研究，文獻(xiàn)［6］分析了蟻群算法的主要參數(shù)對(duì)規(guī)劃路徑的長(zhǎng)度和效率的影響。文獻(xiàn)［7］提出了根據(jù)目標(biāo)點(diǎn)自適應(yīng)調(diào)整啟發(fā)函數(shù)，有效提高了算法的收斂速度；還根據(jù)狼群分配原則對(duì)信息素進(jìn)行更新，避免陷入局部最優(yōu)。文獻(xiàn)［8］將螞蟻當(dāng)前位置與目標(biāo)位置的距離信息反饋到系統(tǒng)中作為航跡規(guī)劃的控制信息，提高了算法的效率。

然而在維修環(huán)境下基于蟻群算法的路徑規(guī)劃研究卻不多見(jiàn)。本文根據(jù)復(fù)雜維修環(huán)境可通行的難易程度劃分了4種不同的區(qū)域，并考慮了時(shí)間代價(jià)和體能代價(jià)作為規(guī)劃的指標(biāo)，構(gòu)建了性能指標(biāo)函數(shù)。針對(duì)傳統(tǒng)蟻群算法的缺點(diǎn)，設(shè)計(jì)了自適應(yīng)的概率轉(zhuǎn)移規(guī)則和雙向搜索策略，改進(jìn)了傳統(tǒng)的蟻群算法，并通過(guò)實(shí)驗(yàn)驗(yàn)證了改進(jìn)蟻群算法的優(yōu)越性。

1 誘導(dǎo)維修路徑規(guī)劃的數(shù)學(xué)模型

1.1 問(wèn)題假定及地圖構(gòu)建

為求維修人員最優(yōu)行進(jìn)路線，首先要對(duì)維修環(huán)境進(jìn)行建模，以生成用于路徑規(guī)劃的地圖模型，本文在此提出了一種為復(fù)雜維修環(huán)境構(gòu)建地圖模型的方法。將維修環(huán)境的可通行情況分為4類(lèi)：無(wú)障礙區(qū)域、1類(lèi)有障礙區(qū)域、2類(lèi)有障礙區(qū)域、不可通行區(qū)域。其中，維修人員可以較快的速度通過(guò)無(wú)障礙區(qū)域并消耗較少的體力，此類(lèi)區(qū)域通常為室外平地或機(jī)艙內(nèi)較寬的通道等；通過(guò)有障礙區(qū)域時(shí)，需要消耗較長(zhǎng)時(shí)間和較多體力，2類(lèi)有障礙區(qū)域比1類(lèi)有障礙區(qū)域通過(guò)難度更高，此類(lèi)區(qū)域通常為機(jī)艙內(nèi)狹小的過(guò)道或可通過(guò)的管道等；不可通行區(qū)域?yàn)椴荒軌蛲ㄟ^(guò)或進(jìn)入的區(qū)域，此類(lèi)區(qū)域通常為艙壁阻隔、擺放大型設(shè)備或危險(xiǎn)區(qū)域等。

根據(jù)事先存儲(chǔ)好的維修環(huán)境的三維CAD模型、危險(xiǎn)區(qū)域位置等信息，利用柵格法［9］建立維修環(huán)境的二維地圖。本文將20 m×20 m的維修環(huán)境劃分40×40的網(wǎng)格空間。此處作如下假設(shè)：維修人員在地圖上的投影看作是一個(gè)網(wǎng)格，可朝與其相鄰的8個(gè)方向前進(jìn)；將地圖中的網(wǎng)格分為4種顏色，用于對(duì)應(yīng)上述不同通行情況維修區(qū)域，圖1為將某型裝備方艙內(nèi)部簡(jiǎn)化得到的維修環(huán)境二維地圖；4種區(qū)域?qū)?yīng)不同的通行速度和體力消耗強(qiáng)度，具體設(shè)置見(jiàn)表1，可根據(jù)不同維修環(huán)境的實(shí)際情況進(jìn)行修改。由于所求最優(yōu)路徑應(yīng)是能使維修者以盡量少的體力消耗和盡快到達(dá)目標(biāo)區(qū)域的行進(jìn)路線。因此，這里認(rèn)為人員在同一類(lèi)型區(qū)域內(nèi)為勻速行進(jìn)，體力消耗代表人員行進(jìn)單位距離所消耗的體力，在此使用無(wú)量綱量p對(duì)其進(jìn)行度量，并設(shè)定體力消耗上限為50 p。此處的“勻速運(yùn)動(dòng)”和“體力消耗”是本文對(duì)實(shí)際維修情況的一種模擬，是為了配合后面的性能指標(biāo)函數(shù)選取一條相對(duì)最優(yōu)的路徑，并不具備實(shí)際度量功能。

圖1 構(gòu)建虛擬環(huán)境地圖

表1 地圖各區(qū)域通過(guò)指標(biāo)

網(wǎng)格序號(hào)i按照從左到右，從下到上的順序依次增加，其與網(wǎng)格坐標(biāo)（x，y）的轉(zhuǎn)換關(guān)系由式（1）確定：

其中，mod（·）為取余操作，int（·）為取整操作，Nh為每行的柵格數(shù)。

地圖以一個(gè)二維數(shù)組map（x，y）的形式存儲(chǔ)在計(jì)算機(jī)中：

1.2 路徑規(guī)劃性能指標(biāo)選取

考慮以時(shí)間代價(jià)和體能代價(jià)作為規(guī)劃的指標(biāo)，構(gòu)造性能指標(biāo)函數(shù)式（3）：

其中，Jt和Js分別為該段路徑的時(shí)間代價(jià)和體能代價(jià)；k為權(quán)系數(shù)

時(shí)間代價(jià)由各區(qū)域內(nèi)路程和通行速度決定：

體能代價(jià)由各區(qū)域內(nèi)路程和體力消耗決定：

式（4）、式（5）中的 L0、L1、L2分別代表該次規(guī)劃中通過(guò)無(wú)障礙區(qū)域、1類(lèi)障礙區(qū)域、2類(lèi)障礙區(qū)域的路徑長(zhǎng)度。

2 算法改進(jìn)

2.1 基本蟻群算法

螞蟻在覓食過(guò)程中會(huì)在所經(jīng)過(guò)的路徑上留下一種被稱為信息素的化學(xué)物質(zhì)，而螞蟻們能感受到這種信息素的存在并傾向于向著信息素濃度高的區(qū)域移動(dòng)，信息素會(huì)隨時(shí)間揮發(fā)以達(dá)到更新的目的。因此，當(dāng)路徑上的信息素濃度越高時(shí)，其被螞蟻選中的概率就越大，反過(guò)來(lái)也促進(jìn)這條路徑上信息素濃度增加。螞蟻之間就這樣依靠信息素進(jìn)行交流并找到最優(yōu)路徑。

真實(shí)自然環(huán)境中信息素會(huì)隨著時(shí)間推移而揮發(fā)，螞蟻的經(jīng)過(guò)會(huì)帶來(lái)新的信息素，因此，每循環(huán)一次后都要對(duì)各小段路徑上的信息素濃度進(jìn)行更新。本文根據(jù)式（7）對(duì)網(wǎng)格i到j(luò)上的信息素進(jìn)行更新。

針對(duì)蟻群算法在路徑規(guī)劃問(wèn)題中存在的不足歸納如下：①隨機(jī)性強(qiáng)，搜索的準(zhǔn)確性不高；②全局搜索能力不強(qiáng)，容易陷入局部最優(yōu)；③螞蟻之間的協(xié)作性不強(qiáng)；④收斂速度低，搜索速度慢［10］。

2.2 自適應(yīng)調(diào)整策略

2.2.1 參數(shù)α、β的動(dòng)態(tài)調(diào)整

傳統(tǒng)蟻群算法中α和β為常數(shù)，然而在算法初始運(yùn)行時(shí)信息素基本不起作用，將α，β設(shè)為常數(shù)顯然不合理，因此，本文將其設(shè)為隨迭代次數(shù)動(dòng)態(tài)調(diào)整，在第N次前α由小增大，此時(shí)β值較大，啟發(fā)因子對(duì)轉(zhuǎn)移概率起主導(dǎo)作用；在第N次后β逐漸減小，α維持不變，此時(shí)信息素濃度為主導(dǎo)，α，β變化可由式（8）和式（9）表示：

2.2.2 改變信息素增量的更新方式

由于每個(gè)螞蟻尋求到的解的質(zhì)量會(huì)有所不同，有的螞蟻找到的解跟最優(yōu)解很接近，有的螞蟻找到的解卻背離最優(yōu)解，然而它們釋放的信息素卻是相同的，這似乎對(duì)于它們很不“公平”。我們總是希望找到優(yōu)質(zhì)解的螞蟻在其所經(jīng)過(guò)的路徑上釋放的信息素要多一些。為此，本文引入信息素增量調(diào)節(jié)因子ω，根據(jù)不同螞蟻找到的不同路徑性能指標(biāo)值，對(duì)所經(jīng)過(guò)的路徑上的信息素自適應(yīng)地更新。

其中，信息素增量調(diào)節(jié)因子ω可由下式求得

其中，Jk為第k只螞蟻得到路徑的性能指標(biāo)值，Jave為螞蟻在本次循環(huán)得到的路徑平均性能指標(biāo)值。

通過(guò)引入信息素增量調(diào)節(jié)因子，可以使找到較優(yōu)解的螞蟻能夠釋放更多的信息素，從而可以增大較好路徑和較差路徑之間的差距，促使螞蟻能夠更快地找到最優(yōu)路徑，提高了收斂的速度，縮短了搜索時(shí)間。

2.3 雙向路徑搜索策略

本文通過(guò)設(shè)計(jì)雙向路徑搜索策略提高算法效率，即將同樣數(shù)量螞蟻放在起點(diǎn)和終點(diǎn)，從兩邊進(jìn)行搜索并引入相遇機(jī)制增強(qiáng)蟻群個(gè)體間的信息交流。具體方法是，將螞蟻分為2只一組，先由起點(diǎn)釋放一只螞蟻，當(dāng)螞蟻找到目標(biāo)或進(jìn)入“不可用點(diǎn)”時(shí)銷(xiāo)毀螞蟻；然后在終點(diǎn)釋放一只螞蟻，遇到下列情況銷(xiāo)毀該螞蟻：①該螞蟻路徑與上一只螞蟻路徑在非起點(diǎn)和終點(diǎn)處產(chǎn)生交點(diǎn)；②該螞蟻進(jìn)入“不可用點(diǎn)”；③路徑搜索成功。

當(dāng)兩只螞蟻都成功到達(dá)起點(diǎn)和終點(diǎn)時(shí)會(huì)產(chǎn)生兩條路徑，此時(shí)選擇代價(jià)小的一條作為最終路徑；當(dāng)兩只螞蟻都遇到“不可用點(diǎn)”時(shí)則此次搜索未找到路徑；以上情況除外，可將達(dá)到路徑合并為一條連通起點(diǎn)和目標(biāo)點(diǎn)的路徑。其中“不可用點(diǎn)”是指當(dāng)前網(wǎng)格周?chē)?個(gè)網(wǎng)格均屬于不可通行區(qū)域或已經(jīng)過(guò)的網(wǎng)格。將同組由起點(diǎn)和終點(diǎn)釋放的螞蟻分別記為螞蟻A和螞蟻B，A、B所經(jīng)過(guò)的路徑用LA，LB表示，L′A代表LA中路徑交點(diǎn)處到終點(diǎn)的部分，Lk表示本次搜索得到的路徑，上述路徑的代價(jià)由式（3）求得，用 JA、JB、L′A、Lk表示。用圖 2 描述雙向搜索策略的流程。

圖2 搜索策略流程圖

2.4 改進(jìn)蟻群算法步驟

利用改進(jìn)蟻群算法進(jìn)行維修路徑規(guī)劃的具體步驟如下：

①在離線狀態(tài)下，根據(jù)維修環(huán)境三維CAD模型和危險(xiǎn)區(qū)域位置等信息人工劃定各類(lèi)區(qū)域，并建立地圖 map（x，y）；

②根據(jù)當(dāng)前維修人員位置和目標(biāo)任務(wù)設(shè)定路徑規(guī)劃的起點(diǎn)（xstart，ystart）和終點(diǎn)（xend，yend），初始化并令n=1；

③將m只螞蟻兩等份，并將相同數(shù)量螞蟻置于起點(diǎn)和目標(biāo)點(diǎn)處，開(kāi)始第n次迭代；

④第k組的兩只螞蟻進(jìn)行雙向搜索，若成功獲取路徑Lk則記錄下來(lái)，并對(duì)信息素值進(jìn)行更新。

⑥判斷近十次迭代得到的最優(yōu)路徑是否一致，若是則輸出第n次迭代的最優(yōu)路徑并結(jié)束，否則轉(zhuǎn)下一步；

⑦判斷n＜Nmax是否成立，若是則n=n+1并跳轉(zhuǎn)③，否則輸出第n次迭代的最優(yōu)路徑并結(jié)束。

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

表2 算法各指標(biāo)對(duì)比

兩次規(guī)劃的最優(yōu)路徑如圖3所示，性能指標(biāo)隨迭代次數(shù)的收斂情況如下頁(yè)圖4所示。

圖3 路徑搜索結(jié)果

由上述實(shí)驗(yàn)結(jié)果可知，本文的改進(jìn)蟻群算法和基本蟻群算法都能夠找到同一條最優(yōu)行進(jìn)路線。由于本文算法引入了自適應(yīng)調(diào)整策略、雙向匹配策略，使得其和基本蟻群算法相比有更快的收斂速度，能以較少的迭代次數(shù)找到最優(yōu)路徑。在兩次規(guī)劃中，本文算法所消耗的時(shí)間分別比傳統(tǒng)蟻群算法要少34.2%和29.6%。本文所提出的改進(jìn)蟻群算法能夠快速有效地為處在復(fù)雜維修環(huán)境中的維修人員提供高效的行進(jìn)路線。

圖4 算法收斂情況對(duì)比

4 結(jié)論

本文以柵格地圖上的誘導(dǎo)維修路徑規(guī)劃為研究背景，在分析不同維修區(qū)域?qū)S修者通行的綜合影響后，通過(guò)設(shè)計(jì)自適應(yīng)調(diào)整策略和雙向搜索策略，提出了多策略蟻群算法。為了增加路徑搜索的有效性，將α、β設(shè)為隨迭代次數(shù)增加而改變的自適應(yīng)函數(shù)，提高了搜索的精度；改變信息素增量的更新方式，可以促使螞蟻更好地區(qū)分較好路徑和較差路徑，提高了收斂速度，縮短了搜索時(shí)間。引入雙向搜索策略，增強(qiáng)了螞蟻之間的協(xié)作能力，路徑搜索的成功率更高，也使得迭代次數(shù)優(yōu)于基本的蟻群算法。仿真結(jié)果表明，改進(jìn)的蟻群算法效率高，收斂速度快，能夠?yàn)樘幵趶?fù)雜維修環(huán)境中的維修人員提供高效的行進(jìn)路線。

［1］趙新?tīng)N，左洪福，徐興民.增強(qiáng)現(xiàn)實(shí)維修誘導(dǎo)系統(tǒng)關(guān)鍵技術(shù)研究［J］.中國(guó)機(jī)械工程，2008，19（6）:678-681.

［2］靳冬冬，王崴，劉曉衛(wèi)，等.增強(qiáng)現(xiàn)實(shí)誘導(dǎo)維修在外軍的發(fā)展現(xiàn)狀和趨勢(shì)［J］.現(xiàn)代防御技術(shù)，2014，42（6）：134-139.

［3］趙守偉.增強(qiáng)現(xiàn)實(shí)輔助維修技術(shù)研究進(jìn)展［J］.圖形學(xué)報(bào)，2014，35（4）：648-653.

［4］DORIGO M，MANIEZZO V，COLORNI A.Ant system：optimization by a colony of cooperating agent［J］.IEEE Transactions on Systems，Man， and Cybernetics，1996，26（1）：29-41.

［5］康冰，王曦輝，劉富.基于改進(jìn)蟻群算法的搜索機(jī)器人路徑規(guī)劃 ［J］. 吉林大學(xué)學(xué)報(bào) （工學(xué)版），2014，44（4）：1062-1068.

［6］史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究［J］.農(nóng)業(yè)機(jī)械學(xué)報(bào)，2014，45（6）：53-57.

［7］柳長(zhǎng)安，鄢小虎，劉春陽(yáng)，等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法［J］. 電子學(xué)報(bào)，2011，39（5）：1220-1223.

［8］牛治永，李炎，李曉嵐.基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃［J］.控制理論與應(yīng)用，2011，3（7）：1-4.

［9］溫如春等.改進(jìn)蟻群算法在迷宮路徑尋優(yōu)中的應(yīng)用研究［J］.自動(dòng)化儀表，2010，31（11）：8-10.

［10］吳天羿，許繼恒.多策略蟻群算法求解越野路徑規(guī)劃［J］.解放軍理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，15（2）：158-164.

Route Planning of Induced Maintenance Based on Improved ant Colony Algorithm

RAO Chu-feng，HAN Hua-ting，QU Jue*，WANG Wei，PENG Bo-yu
（School of Air-Defense and Anti-Missile，Air Force Engineering University，Xi’an 710051，China）

In the process of inducing maintenance，in order to help the maintenance person to find the maintenance of the image quickly，and to provide a safe and efficient way to walk，there is a need to make a maintenance path planning for its complex maintenance environment.The traditional ant colony algorithm is slow convergence and easy to fall into local optimum.In order to improve the optimization efficiency，the basic ant colony algorithm is improved.The adaptive adjustment of α、β，pheromone increment adjustment factor and the bidirectional search strategy are introduced to improve the basic ant colony algorithm，which improve the solution effciency of the algorithm greatly.The simulation results shows that the improved ant colony algorithm has high efficiency and fast convergence speed and is able to provide efficient route for the maintenance personnel in complex maintenance environment.

inducing maintenance，path planning，ant colony algorithm，self-adaptation，bidirectional search strategy

1002-0640（2017）10-0082-05

TP301

A

10.3969/j.issn.1002-0640.2017.10.018

2016-08-12

2016-10-27

國(guó)家自然科學(xué)基金資助項(xiàng)目（51405505）

饒楚鋒（1993- ），男，湖北黃岡人，碩士研究生。研究方向：增強(qiáng)現(xiàn)實(shí)誘導(dǎo)維修。

*通信作者：瞿 玨（1985- ），男，湖南汨羅人，副教授，在讀博士。研究方向：虛擬維修，人機(jī)工程和機(jī)器視覺(jué)。