基于選擇交叉煙花算法的無人車路徑規(guī)劃

高萬博，朱俊武，章永龍，章小衛(wèi)

（揚州大學(xué) 信息工程學(xué)院，江蘇 揚州 225000）

0 概述

移動機器人路徑規(guī)劃是機器人研究領(lǐng)域中的重要分支，無人車是一種可以遠程控制與自主導(dǎo)航的移動機器人。無人車路徑規(guī)劃問題［1］是指無人車在給定環(huán)境下，尋找一條滿足一定約束條件的無碰撞路徑［2］。目前，群智能算法是解決移動機器人路徑規(guī)劃問題的主要方法［3］，通過迭代生成新的可行解，在搜索空間中不斷探索與改進，最終尋找到滿足約束條件的最佳可行解。群智能算法主要包括粒子群算法［4］、蟻群算法［5］、遺傳算法［6］、煙花算法［7］等。

文獻［8］提出一種新型啟發(fā)式算法，稱為煙花算法，其具有隨機性、局部性、爆發(fā)性、隱式并行性、多樣性、瞬時性等特點，通過煙花在空中爆炸產(chǎn)生火花的過程來模擬算法在搜索空間中求解問題的過程，具有較優(yōu)的優(yōu)化求解能力。

在路徑規(guī)劃問題中，因算法搜索空間較大，規(guī)劃環(huán)境較復(fù)雜，導(dǎo)致煙花算法難以尋找到全局最優(yōu)路徑，甚至尋找到的路徑會穿越障礙物。針對上述問題，研究人員對煙花算法進行改進。文獻［9］結(jié)合煙花算法與蟻群算法提出一種混合算法，用于解決智能移動體避障的問題，通過加入先鋒火花操作提高搜索效率，并使用蟻群算法來實現(xiàn)避障的目的。文獻［10］在基本煙花算法的基礎(chǔ)上增加量子行為作為新的爆炸策略，使得煙花算法對全局和局部最優(yōu)解都具有較優(yōu)的搜索能力。文獻［11］通過可視圖法構(gòu)建士兵視覺場景，利用插入和刪除節(jié)點操作解決路徑不連續(xù)的問題。一些研究人員采用基于深度學(xué)習(xí)的方法來解決該類問題。文獻［12］對卷積神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練，構(gòu)建圖像與動作的映射關(guān)系，實現(xiàn)移動機器人路徑規(guī)劃。文獻［13-15］將圖像作為唯一輸入，訓(xùn)練強化學(xué)習(xí)網(wǎng)絡(luò)實現(xiàn)移動機器人在未知環(huán)境下自主完成避障和區(qū)域覆蓋的任務(wù)。文獻［16］通過改進的深度Q 網(wǎng)絡(luò)（DQN）訓(xùn)練多個機器人進行路徑規(guī)劃，以完成無人倉庫調(diào)度任務(wù)。文獻［17］通過深度強化學(xué)習(xí)模型學(xué)習(xí)改進啟發(fā)式方法，從而解決旅行商問題。文獻［18-20］通過改進的深度強化學(xué)習(xí)模型解決車輛路徑優(yōu)化及其變體問題。

基本煙花算法在三維地形環(huán)境下進行路徑規(guī)劃時，因部分路徑節(jié)點經(jīng)過爆炸操作會遠離原始路徑且種群的路徑片段間缺乏信息交互，導(dǎo)致收斂速度和探索最優(yōu)解的能力降低。針對上述問題，本文提出選擇交叉煙花算法。通過路徑節(jié)點的輪盤選擇操作，根據(jù)路徑節(jié)點的適應(yīng)度函數(shù)進行輪盤賭，以解決部分路徑節(jié)點偏離軌跡的問題。借鑒遺傳算法中的交叉變異操作，引入選擇交叉變異操作，將篩選出的路徑片段與其他路徑片段進行交換，從而提高煙花之間的信息交互性。

1 問題描述

1.1 地形環(huán)境

無人車根據(jù)全局三維地形環(huán)境［21］建立三維空間直角坐標系O-xyz，沿x軸、y軸將空間分割為m×n個柵格，將柵格地形環(huán)境的最大高度值z作為該柵格的內(nèi)容值。通過該方式將地形環(huán)境表示為zi=Map(xi，yi)的柵格矩陣，其中xi、yi表示柵格矩陣的行列坐標位置，zi表示柵格值，即此柵格所在區(qū)域的地形高度。在地圖中的威脅區(qū)域主要是指無人車不能進入的區(qū)域，如沼澤、湖泊等，由一個矩陣G表示，如式（1）所示：

圖1 柵格法構(gòu)建的地形矩陣Fig.1 Terrain matrix constructed by grid method

1.2 適應(yīng)度函數(shù)

本文從燃耗代價、威脅代價和平滑代價3 個角度衡量路徑優(yōu)劣，適應(yīng)度函數(shù)如式（2）所示：

其中：w1、w2、w3為平衡各指標的權(quán)重系數(shù)，且1；Cf為無人車行駛時產(chǎn)生的路程燃耗代價；Cd為無人車經(jīng)過威脅區(qū)域時產(chǎn)生的威脅代價；Cs為無人車轉(zhuǎn)彎行駛時產(chǎn)生的轉(zhuǎn)角平滑代價。

1.2.1 燃耗代價

其中：kl＜1 ＜kh；Xi＝(xi，yj，zi，j)表示xi列yj行，值 為zi，j的柵格塊。

路徑的燃耗代價為各路徑節(jié)點燃耗代價之和，如式（5）所示：

1.2.2 威脅代價

無人車規(guī)劃的路徑需遠離威脅區(qū)域，保證路徑的安全性。路徑點的威脅代價通過路徑點與威脅區(qū)域的圓心距離來描述，距離越遠則路徑點越安全。路徑點Xi的威脅代價如式（6）所示：

其中：R為威脅區(qū)域的半徑；為威脅區(qū)域中心點的坐標和高度值。當路徑節(jié)點的距離小于最小威脅區(qū)域半徑時，Cplot_d大于1，則該點不符合構(gòu)成路徑的要求。

威脅區(qū)域信息表示如圖2 所示。

圖2 威脅區(qū)域坐標圖Fig.2 Coordinate diagram of the threat region

路徑節(jié)點A、B、C距圓心的長度分別為d1、d2、d3，其 中d1＜R＜d2＜d3，因 此Cplot_d(A) ＜1 ＜Cplot_d(B) ＜Cplot_d(C)。路徑節(jié)點A不符合路徑構(gòu)成要求將被舍棄，節(jié)點C的威脅代價比節(jié)點B更低。

路徑的威脅代價為各路徑節(jié)點威脅代價之和，如式（7）所示：

1.2.3 平滑代價

無人車需滿足自身的動力學(xué)要求，避免轉(zhuǎn)彎時角度太小。路徑點平滑代價用路徑點與其前后節(jié)點形成的夾角來描述。夾角越小，無人車的轉(zhuǎn)角越大，路徑越不平滑。路徑節(jié)點Xi的平滑代價如式（8）所示：

其中：α為無人車的最小轉(zhuǎn)角；θi為行駛過程中路徑節(jié)點Xi的夾角。當θi小于無人車的最小轉(zhuǎn)角α?xí)r，Cplot_s大于1，則該路徑節(jié)點不符合路徑構(gòu)成要求，應(yīng)當舍去。平滑代價信息表示如圖3所示，無人車沿著∠OAB方向進行轉(zhuǎn)角，最小轉(zhuǎn)角角度為∠OAA'即α。路徑節(jié)點A的夾角θ大于最小轉(zhuǎn)角α，則保留該節(jié)點。

圖3 平滑代價坐標圖Fig.3 Coordinate diagram of the smooth cost

路徑的平滑代價為各路徑節(jié)點的平滑代價之和，如式（9）所示：

2 基本煙花算法

基本煙花算法將煙花看作空間中的一個解，通過對煙花進行爆炸操作，選擇不同的火花對鄰域進行搜索。其基本原理是煙花對應(yīng)的適應(yīng)度值越小，則該煙花爆炸產(chǎn)生的火花數(shù)量越多，爆炸幅度越??；相反，若煙花對應(yīng)的適應(yīng)度值越大，則該煙花爆炸產(chǎn)生的火花數(shù)量越少，且爆炸幅度越大。

在基本煙花算法中，第i個煙花的爆炸強度如式（10）所示：

第i個煙花的爆炸幅度如式（11）所示：

其中：fmin為當前種群中的最小適應(yīng)度值為控制煙花爆炸幅度的常數(shù)。

為了增加種群中煙花的多樣性，基本煙花算法隨機選擇j個維度對煙花進行高斯變異，如式（12）所示：

其中：g表示均值為1、方差為1且滿足高斯分布的隨機數(shù)。

在煙花爆炸后產(chǎn)生的變異火花和爆炸火花可能會超出可行域范圍，根據(jù)映射規(guī)則重新映射回可行域內(nèi)，如式（13）所示：

其中：為三維地形環(huán)境中第k維的上邊界；為三維地形環(huán)境中第k維的下邊界；為 第i號煙花的第m個路徑節(jié)點在第k維的位置。

煙花算法通過選擇操作對產(chǎn)生的新火花進行篩選，并選擇部分火花作為下一代煙花，如式（14）和式（15）所示：

其中：R(pi)為火花pi與其他火花之間的距離求和；K為當前種群中所有火花的個數(shù)；Pr(pi)為煙花pi被選中的概率。

3 本文算法

3.1 輪盤選擇操作

本文通過分析基本煙花算法迭代生成的路徑，發(fā)現(xiàn)路徑中可能存在部分路徑節(jié)點偏離軌跡的問題。煙花算法的爆炸操作示意圖如圖4 所示。

圖4 煙花算法爆炸操作示意圖Fig.4 Schematic diagram of explosion operation of fireworks algotithm

路徑節(jié)點Xi、Xj的適應(yīng)度值遠大于路徑中的其他節(jié)點。因此，本文提出針對路徑節(jié)點的輪盤選擇操作，提升具有高適應(yīng)度值的路徑節(jié)點被選擇并進行變異的概率。圖4 中為經(jīng)過輪盤選擇后再變異操作得到的新路徑節(jié)點。本文輪盤選擇操作分為以下3 個步驟：

1）計算路徑節(jié)點Xi的適應(yīng)度值，如式（16）所示：

2）通過輪盤賭［22］的方法對需要爆炸的節(jié)點進行選擇，路徑節(jié)點Xi被選擇進行爆炸的概率如式（17）所示：

其中：Q(i)為P(i)的累計概率；select(k)為用于保存k個被選中的路徑維度；rand 為生成均勻分布的0～1隨機數(shù)，若rand 在[Q(i)，Q(i+1)]區(qū)間內(nèi)，則將i存入select 中。

3）對被選擇的路徑節(jié)點進行位移操作，如式（18）所示：

因此，本文通過爆炸位移使路徑節(jié)點在爆炸幅度內(nèi)進行一次位置變化。

3.2 選擇交叉變異

基本煙花算法通過高斯變異和爆炸操作對煙花的節(jié)點進行單點變異，并未考慮煙花之間路徑片段的交互變異。例如，在一次迭代過程中，一個煙花Pi=，會在某一段路徑片段中出現(xiàn)較高的適應(yīng)度值，假設(shè)為P'=，而單一路徑節(jié)點的變異方式并不能顯著提高煙花適應(yīng)度值。

本文借鑒遺傳算法中的交叉變異因子［23］思想，提出選擇交叉變異，并將其作為新的火花變異方式，通過3.1 節(jié)輪盤選擇的方式選擇其中兩個節(jié)點作為路徑片段，并將其與另一個煙花之間的路徑片段進行交換，通過該方式增大最優(yōu)解出現(xiàn)的概率［24］，以加強種群中煙花之間的信息交互。隨機選擇的兩個父代煙花par1、par2通過輪盤選擇操作產(chǎn)生路徑節(jié)點，對選中的路徑節(jié)點進行路徑片段交叉，以得到選擇交叉火花child1、child2，如式（19）所示：

圖5 選擇交叉火花的產(chǎn)生流程Fig.5 Generation procedure of selection crossover spark

3.3 算法流程

選擇交叉煙花算法的具體流程如算法1 所示。

算法1選擇交叉煙花算法（SC-FWA）

輸入地形Map，威脅區(qū)域矩陣G，最大迭代次數(shù)maxgen

輸出最優(yōu)路徑pb

1.隨機初始煙花種群路徑P={p1，p2，…，pN}

2.for i=1，i ≤maxgen，i++

3.通過式（2）計算種群中每個煙花適應(yīng)度值fcost

4.通過式（10）和式（11）計算煙花的爆炸幅度和火花個數(shù)

5.通過輪盤選擇操作式（17）篩選出需要位移的路徑節(jié)點Xselect

6.依據(jù)式（18）在爆炸幅度內(nèi)對Xselect進行爆炸位移

7.隨機選取路徑節(jié)點Xj依據(jù)式（12）進行高斯變異

8.通過式（19）將被選擇的路徑par1、par2進行交叉變換，產(chǎn)生選擇交叉火花

9.通過式（13）對變異后超出可行域的路徑節(jié)點映射回可行域內(nèi)

10.保留最優(yōu)煙花，將其余爆炸火花、高斯變異火花、選擇交叉火花通過式（14）選擇下一代煙花。

步驟1 在搜索空間中通過隨機選擇符合適應(yīng)度值要求的n個路徑節(jié)點作為初始路徑，并構(gòu)建N條初始路徑以構(gòu)成煙花種群。步驟2～步驟10 在給定的最大迭代次數(shù)內(nèi)循環(huán)使用選擇交叉煙花算法，其中步驟3 和步驟4 計算適應(yīng)度函數(shù)，得到爆炸幅度與爆炸強度，步驟5～步驟8 產(chǎn)生爆炸火花、高斯變異火花和選擇交叉火花，步驟9 對超出可行域的路徑節(jié)點進行映射，步驟10 通過選擇操作對火花進行篩選，形成下一代煙花。當達到最大迭代次數(shù)后，算法輸出最優(yōu)煙花，并作為無人車的規(guī)劃路徑。

4 實驗與結(jié)果分析

4.1 實驗環(huán)境與參數(shù)設(shè)置

本文在MATLAB 2018b 上進行仿真實驗，計算機配置為2.60 GHz CPU，16 GB RAM、64 位操作系統(tǒng)。

本文將蟻群算法（ACO）［25］、基本煙花算法（FWA）、改進煙花算法（IFWA）［11］、選擇尋優(yōu)煙花算法（SC-FWA）進行對比實驗。SC-FWA 的實驗參數(shù)：最大迭代次數(shù)max_gen=300，初始煙花個數(shù)N=10，最小轉(zhuǎn)角α=π/2，最大爆炸幅度=10，最大爆炸強度=10，威脅代價C1=0.2，平滑代價C2=0.2，燃耗代價C3=0.6，上坡燃耗系數(shù)kh=0.2，下坡燃耗系數(shù)kl=0.5，搜索空間上界=100，搜索空間下界=1，簡單地形環(huán)境適應(yīng)度函數(shù)閾值Fs=270，復(fù)雜地形環(huán)境適應(yīng)度函數(shù)閾值Fc=750。

4.2 結(jié)果分析

為驗證選擇交叉煙花算法的收斂性和高效性，本文將選擇交叉煙花算法的兩類改進操作分開進行對比分析。其中加入輪盤選擇操作的煙花算法（S-FWA）是在基本煙花算法的基礎(chǔ)上對不同適應(yīng)度值的路徑節(jié)點進行輪盤賭操作；加入選擇交叉變異的煙花算法（C-FWA）是在基本煙花算法的基礎(chǔ)上隨機選擇不同的路徑片段進行交換。本文將ACO、FWA、IFWA、S-FWA、C-FWA、SC-FWA 在簡單地形和復(fù)雜地形下進行實驗對比。當執(zhí)行完給定的最大迭代次數(shù)后，不同算法在簡單地形和復(fù)雜地形下的路徑適應(yīng)度值如表1 所示。

表1 不同算法的路徑適應(yīng)度值對比Table 1 Path fitness values comparison among different algorithms

FWA、IFWA、S-FWA、C-FWA、SC-FWA 均找到了低于ACO 適應(yīng)度值的路徑，說明煙花算法具有較優(yōu)的空間探索能力，其中C-FWA 相較于IFWA、S-FWA、FWA 適應(yīng)度值更低。因此，C-FWA 通過選擇交叉變異進行煙花間的片段交換，以增強煙花算法中煙花間的交互性，從而有效提升探索最優(yōu)解的能力，但其不足是加入了新的交叉操作會導(dǎo)致運行時間較高于其他基本煙花算法。

在簡單地形和復(fù)雜地形中，若算法探索到低于適應(yīng)度函數(shù)閾值的路徑時，則終止程序并記錄運行時間，不同算法在簡單地形和復(fù)雜地形下的運行時間如表2 所示。

表2 不同算法的運行時間對比Table 2 Running time comparison among different algorithms

FWA、IFWA、S-FWA、C-FWA、SC-FWA 運行時間均低于ACO，說明煙花算法具有高效性。其中S-FWA 相較于IFWA、C-FWA、FWA 運行時間更短，由此可見，通過輪盤選擇操作提高偏離路徑節(jié)點的變異概率，從而加快煙花算法的收斂速度。但由于S-FWA 減弱了煙花種群中煙花的多樣性，因此探索最優(yōu)解的能力降低，當完成所有迭代次數(shù)后，路徑適應(yīng)度值較高。

SC-FWA 通過輪盤選擇操作和選擇交叉變異操作，結(jié)合S-FWA 中收斂速度快和C-FWA 中搜索全局最優(yōu)解能力強的特點，在簡單和復(fù)雜地形中，運行時間和路徑適應(yīng)度值均優(yōu)于IFWA、FWA、ACO。因此，SC-FWA 具有一定的收斂性和高效性，規(guī)劃的路徑適應(yīng)度值更低，運行時間更短。

在100 km×100 km的仿真簡單和復(fù)雜地形環(huán)境下，ACO、FWA、IFWA、SC-FWA算法的路徑對比分別如圖6和圖7所示（彩色效果見《計算機工程》官網(wǎng)HTML版）。其中，（0，0）為起始點，（100，100）為目標點。不同顏色代表區(qū)塊的高度值（如山丘、山峰等），藍色區(qū)域為平原區(qū)，黃色區(qū)域為山峰，圓圈標識的圓形區(qū)域為威脅區(qū)域。

圖6 在簡單地形下不同算法的路徑規(guī)劃對比Fig.6 Path planning comparison among different algorithms in simple terrain

圖7 在復(fù)雜地形下不同算法的路徑規(guī)劃對比Fig.7 Path planning comparison among different algorithms in complex terrain

簡單地形較為單一，大部分為平原地區(qū)。從圖6可以看出，4 種算法均找到了近似全局最優(yōu)解，威脅代價與轉(zhuǎn)角代價均相近。但SC-FWA 路徑長度更短，燃耗更低。而ACO 經(jīng)過部分山地區(qū)域，導(dǎo)致燃耗增加。從圖7 可以看出，在復(fù)雜地形下，由于加入了燃耗代價，將轉(zhuǎn)角代價和威脅代價作為適應(yīng)度函數(shù)，SC-FWA 規(guī)劃的路徑遠離了威脅區(qū)域，并且路徑更加平滑，無人車選擇行駛的路徑地形更加平坦，減少了上坡下坡的燃耗，因此規(guī)劃的路徑適應(yīng)度值更低。IFWA 找到了與SC-FWA 相近的路徑，但是生成的路徑經(jīng)過山地地形，增加了燃耗消耗。而FWA 和ACO 陷入了局部最優(yōu)解，沒有找到最合理的路徑。FWA 相對ACO 產(chǎn)生的路徑更加平滑，但是規(guī)劃的路徑經(jīng)過了山地，導(dǎo)致燃耗代價升高。相對于SC-FWA和IFWA，F(xiàn)WA 規(guī)劃的路徑距離威脅區(qū)域更近，ACO雖然繞過了山地地形，但是規(guī)劃的路徑不平滑，轉(zhuǎn)角過多，距離威脅區(qū)域較近。

在簡單地形和復(fù)雜地形下FWA、IFWA、ACO 和SC-FWA 算法的收斂曲線分別如圖8 和圖9 所示。

圖8 在簡單地形下不同算法的收斂曲線對比Fig.8 Convergence curves comparison among different algorithms in simple terrain

圖9 在復(fù)雜地形下不同算法的收斂曲線對比Fig.9 Convergence curves comparison among different algorithms in complex terrain

煙花適應(yīng)度值越低則表示生成的路徑代價越小、產(chǎn)生的路徑更加遠離威脅區(qū)域、路徑更加平滑且燃耗更低。在簡單地形下，SC-FWA 各個時期的適應(yīng)度值均優(yōu)于FWA、ACO、IFWA，并且在迭代第65 次時，SC-FWA 算法已基本收斂。FWA、ACO、IFWA 算法適應(yīng)度函數(shù)變化不大，說明產(chǎn)生的解均靠近全局最優(yōu)解。在復(fù)雜地形下，SC-FWA 的適應(yīng)度值在前期下降更快，當?shù)螖?shù)為150～200 時，陷入了與IFWA 同樣的局部最優(yōu)解，通過選擇交叉操作，在迭代200 次后跳出局部最優(yōu)解，以搜尋到適應(yīng)度值更小的路徑。在迭代后期，SC-FWA 找到了相比于FWA、ACO、IFWA更優(yōu)的路徑。

實驗結(jié)果表明，通過構(gòu)建適應(yīng)度函數(shù)，使得SC-FWA 規(guī)劃的路徑更加平滑且遠離威脅區(qū)域。在FWA 的基礎(chǔ)上加入了輪盤選擇操作和選擇交叉變異，提高了低適應(yīng)度節(jié)點被選擇進行變異的概率，并使得煙花之間可以進行信息交互。因此，SC-FWA在保證煙花多樣性的同時提高了算法的搜索效率，使算法在不同的地形環(huán)境下都具有良好的適應(yīng)性，不易陷入局部最優(yōu)解，使其具有更快的收斂速度，規(guī)劃出更安全、高效的路徑。

5 結(jié)束語

本文將三維地形環(huán)境下無人車路徑規(guī)劃問題轉(zhuǎn)化為多約束條件的優(yōu)化問題［26］，提出選擇交叉煙花算法。為了更真實地模擬無人車在三維地形環(huán)境下的行駛過程，引入燃耗代價、威脅代價和平滑代價作為適應(yīng)度函數(shù)對路徑進行評價，使產(chǎn)生的路徑更加平滑且遠離威脅區(qū)域。仿真實驗結(jié)果表明，相比ACO、FWA、IFWA等算法，本文算法具有較優(yōu)的求解性能和較快的收斂速度，使無人車在較短的時間內(nèi)規(guī)劃出更優(yōu)的路徑。下一步將考慮在三維地形環(huán)境下融合改進的煙花算法與強化學(xué)習(xí)模型，使多個無人車可以學(xué)習(xí)合作避障策略，以有效規(guī)避動態(tài)障礙物。