一種MAKLINK 圖多節(jié)點(diǎn)鏈路建模的路徑規(guī)劃研究

孫培剛，張全禹，許春和

（綏化學(xué)院電氣工程學(xué)院，黑龍江綏化 152061）

路徑規(guī)劃建模的智能優(yōu)化問題一直是人們深入研究的方向，特別是在航海、航空及智能機(jī)器人等路徑規(guī)劃研究方面具有非常重要的意義[1]。常用的路徑規(guī)劃建模方法主要有可視圖法、柵格法、人工勢(shì)場(chǎng)法、隨機(jī)樹法和鏈接圖（MAKLINK）法[2]。其中，可視圖法算法靈活，規(guī)劃方法簡(jiǎn)單，但對(duì)障礙物形狀有一定的要求，每次搜索需要重新構(gòu)建視圖模型，處理時(shí)間較長(zhǎng)；柵格法是研究較為廣泛的方法之一，常用于機(jī)器人路徑尋優(yōu)，但計(jì)算復(fù)雜，同時(shí)要兼顧柵格分辨率、環(huán)境信息存儲(chǔ)量及規(guī)劃時(shí)間等因素；人工勢(shì)場(chǎng)法實(shí)時(shí)性較好，但易陷于鎖死狀態(tài)；隨機(jī)樹法存在搜索空間大、效率低等問題[3]；MAKLINK 法優(yōu)點(diǎn)是建模的障礙物固定后，連通圖位置隨之固定，但連通圖構(gòu)建復(fù)雜，并與障礙物的數(shù)量及形狀有關(guān)[4]。

文中主要研究了MAKLINK 圖路徑位置變化時(shí)，獲得的最優(yōu)路徑是否會(huì)與約束條件產(chǎn)生沖突的問題，并通過蟻群算法分別對(duì)基本MAKLINK 圖和多節(jié)點(diǎn)鏈路MAKLINK 圖的規(guī)劃建模進(jìn)行了優(yōu)化，通過改變各自路徑端點(diǎn)位置對(duì)兩種方法優(yōu)化的路徑長(zhǎng)度、迭代次數(shù)、魯棒性等參數(shù)進(jìn)行了比較與分析。

1 MAKLINK建模

1.1 MAKLINK圖的可行路徑構(gòu)建

在構(gòu)造MAKLINK 圖之前，首先設(shè)置障礙物，障礙物的形狀和數(shù)量可自行設(shè)置，將障礙物的某一頂點(diǎn)與其他頂點(diǎn)或空間邊界點(diǎn)相連形成鏈路線，要求鏈路線不得穿過障礙物。在每條鏈路線上設(shè)置節(jié)點(diǎn)，根據(jù)MAKLINK 圖的實(shí)際情況確定節(jié)點(diǎn)與節(jié)點(diǎn)間連線未穿過障礙物的為可行線段，并形成可行線段集合[5]。通常設(shè)置的每條鏈路線的節(jié)點(diǎn)為單節(jié)點(diǎn)，即該鏈路線的中點(diǎn),如圖1 所示。圖中陰影部分為障礙物，S 為路徑起點(diǎn)，T 為終點(diǎn)，V1～V20 為節(jié)點(diǎn)，虛線為鏈路線，細(xì)實(shí)線為可行路徑集合。

該文在每條鏈路線上設(shè)置多個(gè)節(jié)點(diǎn)（以三個(gè)節(jié)點(diǎn)為例，即該鏈路線的三個(gè)等分點(diǎn)，節(jié)點(diǎn)號(hào)為V1～V60）形成多節(jié)點(diǎn)鏈路，以提高次優(yōu)路徑的精確度，并根據(jù)障礙物及節(jié)點(diǎn)位置生成可行性路徑布局圖，可行路徑如圖2 所示。

圖2 多節(jié)點(diǎn)鏈路MAKLINK可行路徑示意圖

由圖2 可知，隨著節(jié)點(diǎn)數(shù)的增加，可行線段數(shù)量增多，路徑的選擇更加廣泛，相對(duì)于傳統(tǒng)的單節(jié)點(diǎn)鏈路，可行路徑更加理想，但增加了MAKLINK 圖路徑規(guī)劃設(shè)計(jì)的冗余性。

1.2 dijkstra 算法

dijkstra 算法功能是在眾多的可行路徑中搜尋一條距離最短的次優(yōu)化路徑，并將次優(yōu)化路徑所經(jīng)過的節(jié)點(diǎn)序列號(hào)記錄下來，作為蟻群優(yōu)化的一個(gè)初始條件[6-8]，其算法流程如圖3 所示。

圖3 dijkstra算法流程

通過dijkstra 算法先對(duì)各節(jié)點(diǎn)間距離進(jìn)行計(jì)算，并將節(jié)點(diǎn)距離數(shù)據(jù)存儲(chǔ)到指定變量中。然后根據(jù)計(jì)算的數(shù)據(jù)對(duì)可行節(jié)點(diǎn)間路徑的最小值進(jìn)行全局搜索，并更新和存儲(chǔ)節(jié)點(diǎn)號(hào)。當(dāng)路徑節(jié)點(diǎn)到達(dá)終點(diǎn)后結(jié)束搜索，輸出最小路徑節(jié)點(diǎn)的序列號(hào)[9]。通過程序算法計(jì)算的節(jié)點(diǎn)間距離數(shù)據(jù)中1 000 代表節(jié)點(diǎn)間路徑不可行，其他數(shù)據(jù)為可行路徑各節(jié)點(diǎn)間的距離數(shù)據(jù)。根據(jù)圖2 中的鏈路、節(jié)點(diǎn)及障礙物的位置，計(jì)算的S-V1 的距離數(shù)據(jù)為22.360 6，表示起點(diǎn)S 與節(jié)點(diǎn)V1 間的路徑距離為22.360 6 m；S 與節(jié)點(diǎn)V4 間的計(jì)算數(shù)據(jù)為1 000，表示S 與節(jié)點(diǎn)V4 間路徑不可行。根據(jù)搜索結(jié)果，輸出的最小路徑節(jié)點(diǎn)號(hào)為S、V6、V10、V45、V31、V20、V42、V49、T，計(jì)算的次優(yōu)路徑距離為238.904 1 m。

2 蟻群算法的路徑優(yōu)化

對(duì)dijkstra 算法得到的次優(yōu)化路徑通過蟻群算法做進(jìn)一步優(yōu)化，以獲得MAKLINK 圖的最優(yōu)路徑。優(yōu)化流程如圖4 所示。

圖4 蟻群優(yōu)化算法流程

蟻群初始化參數(shù)主要包括能見度參數(shù)、信息素?fù)]發(fā)系數(shù)、信息素增強(qiáng)系數(shù)及螞蟻個(gè)數(shù)等[10-12]。設(shè)在t時(shí)刻的信息素強(qiáng)度為τij(t)，則：

其中，ρ為蒸發(fā)系數(shù)，為第k只螞蟻在節(jié)點(diǎn)Vi與Vj的路徑上釋放的信息素濃度啟發(fā)信息素信息后，螞蟻開始依次在每條鏈路上搜索最佳路徑點(diǎn)，鏈路Li上的搜索點(diǎn)可表示為：

其中，hi∈[0,1]為比例參數(shù)，Pi1和Pi2為鏈路Li上的端點(diǎn)[13]。當(dāng)螞蟻搜索到終點(diǎn)后，更新信息素信息，并判斷是否滿足終止條件，若滿足則輸出最優(yōu)化路徑信息，否則重新搜索[14-16]。

3 優(yōu)化結(jié)果分析

基本MAKLINK 圖單節(jié)點(diǎn)鏈路路徑示意圖如圖5 所示。圖中S[5,130]為設(shè)置的起點(diǎn)，T[190,70]為設(shè)置的終點(diǎn)，在次優(yōu)化路徑的基礎(chǔ)上通過蟻群算法對(duì)其進(jìn)行了優(yōu)化計(jì)算，獲得最優(yōu)路徑。圖中，粗點(diǎn)劃線為dijkstra 算法得到的次優(yōu)化節(jié)點(diǎn)路徑，粗實(shí)線為經(jīng)過蟻群算法優(yōu)化的最優(yōu)路徑。

圖5 單節(jié)點(diǎn)鏈路最優(yōu)路徑示意圖

同等條件下，采用多節(jié)點(diǎn)鏈路法對(duì)起點(diǎn)S[5,130]到終點(diǎn)T[190,70]之間的路徑進(jìn)行了優(yōu)化設(shè)計(jì)，最優(yōu)路徑示意圖如圖6 所示。

圖6 多節(jié)點(diǎn)鏈路最優(yōu)路徑示意圖

文中對(duì)基本單節(jié)點(diǎn)鏈路MAKLINK 算法和多節(jié)點(diǎn)鏈路MAKLINK 圖算法的適應(yīng)度值進(jìn)行了比較分析，適應(yīng)度值變化曲線如圖7 所示。其中點(diǎn)劃線表示基本單節(jié)點(diǎn)鏈路MAKLINK 圖的適應(yīng)度值進(jìn)化曲線，迭代102 次后接近最優(yōu)解，最短路徑為230.6；細(xì)實(shí)線為多節(jié)點(diǎn)鏈路MAKLINK 圖的適應(yīng)度值進(jìn)化曲線，迭代147 次后接近最優(yōu)解，最短路徑為227.3。可以看出，多節(jié)點(diǎn)鏈路相比于單節(jié)點(diǎn)鏈路優(yōu)化的路徑減小了1.43%，但由于多節(jié)點(diǎn)鏈路的MAKLINK 圖路徑規(guī)劃較為復(fù)雜，可行線段數(shù)量多，需要較多的迭代計(jì)算。

圖7 適應(yīng)度值變化曲線

當(dāng)MAKLINK 圖中起點(diǎn)S 和終點(diǎn)T 的坐標(biāo)位置分別改為[5,100]和[190,45]時(shí)，dijkstra 算法得到的次優(yōu)化節(jié)點(diǎn)路徑、最優(yōu)化路徑和距離都隨之發(fā)生變化。由于單節(jié)點(diǎn)鏈路的優(yōu)化算法以中心節(jié)點(diǎn)為中心，在整條鏈路上進(jìn)行全局搜索尋優(yōu)，容易破壞適應(yīng)度函數(shù)的約束條件，單節(jié)點(diǎn)鏈路的優(yōu)化路徑如圖8 所示。可以看出，最優(yōu)路徑已穿過障礙物，破壞了MAKLINK 圖算法的約束條件[17-18]。

圖8 單節(jié)點(diǎn)鏈路最優(yōu)路徑示意圖

圖9 為多節(jié)點(diǎn)鏈路路徑，雖然建模算法復(fù)雜，但是次優(yōu)化路徑較為理想，算法以次優(yōu)化路徑經(jīng)過的節(jié)點(diǎn)為中心，在小范圍內(nèi)進(jìn)行局部尋優(yōu)，獲得的最優(yōu)路徑比較接近最優(yōu)解。并且當(dāng)路徑端點(diǎn)坐標(biāo)變化時(shí)，仍然滿足約束條件,具有較強(qiáng)的魯棒性。

圖9 多節(jié)點(diǎn)鏈路最優(yōu)路徑示意圖

4 結(jié)束語(yǔ)

文中基于MAKLINK 圖的路徑規(guī)劃及蟻群優(yōu)化算法，提出了一種多節(jié)點(diǎn)鏈路的路徑規(guī)劃算法，解決了基本MAKLINK 圖路徑規(guī)劃算法易于破壞適應(yīng)度函數(shù)約束條件的缺陷，提高了MAKLINK 圖路徑規(guī)劃建模的靈活性和對(duì)環(huán)境條件的適應(yīng)性。算法也存在一些不足，如隨著鏈路上節(jié)點(diǎn)數(shù)目的增多，存在可行路徑的建模繁瑣、迭代次數(shù)增加、程序運(yùn)行時(shí)間較長(zhǎng)等問題，在最優(yōu)路徑的優(yōu)化算法等問題上還有待于進(jìn)一步改進(jìn)。