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

高萬博，朱俊武，章永龍，章小衛

（揚州大學 信息工程學院，江蘇 揚州 225000）

0 概述

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

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

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

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

1 問題描述

1.1 地形環境

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

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

1.2 適應度函數

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

其中：w1、w2、w3為平衡各指標的權重系數，且1；Cf為無人車行駛時產生的路程燃耗代價；Cd為無人車經過威脅區域時產生的威脅代價；Cs為無人車轉彎行駛時產生的轉角平滑代價。

1.2.1 燃耗代價

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

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

1.2.2 威脅代價

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

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

威脅區域信息表示如圖2 所示。

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

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

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

1.2.3 平滑代價

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

其中：α為無人車的最小轉角；θi為行駛過程中路徑節點Xi的夾角。當θi小于無人車的最小轉角α時，Cplot_s大于1，則該路徑節點不符合路徑構成要求，應當舍去。平滑代價信息表示如圖3所示，無人車沿著∠OAB方向進行轉角，最小轉角角度為∠OAA'即α。路徑節點A的夾角θ大于最小轉角α，則保留該節點。

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

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

2 基本煙花算法

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

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

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

其中：fmin為當前種群中的最小適應度值為控制煙花爆炸幅度的常數。

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

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

在煙花爆炸后產生的變異火花和爆炸火花可能會超出可行域范圍，根據映射規則重新映射回可行域內，如式（13）所示：

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

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

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

3 本文算法

3.1 輪盤選擇操作

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

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

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

1）計算路徑節點Xi的適應度值，如式（16）所示：

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

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

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

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

3.2 選擇交叉變異

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

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

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

3.3 算法流程

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

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

輸入地形Map，威脅區域矩陣G，最大迭代次數maxgen

輸出最優路徑pb

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

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

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

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

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

6.依據式（18）在爆炸幅度內對Xselect進行爆炸位移

7.隨機選取路徑節點Xj依據式（12）進行高斯變異

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

9.通過式（13）對變異后超出可行域的路徑節點映射回可行域內

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

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

4 實驗與結果分析

4.1 實驗環境與參數設置

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

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

4.2 結果分析

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

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

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

在簡單地形和復雜地形中，若算法探索到低于適應度函數閾值的路徑時，則終止程序并記錄運行時間，不同算法在簡單地形和復雜地形下的運行時間如表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 運行時間更短，由此可見，通過輪盤選擇操作提高偏離路徑節點的變異概率，從而加快煙花算法的收斂速度。但由于S-FWA 減弱了煙花種群中煙花的多樣性，因此探索最優解的能力降低，當完成所有迭代次數后，路徑適應度值較高。

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

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

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

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

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

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

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

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

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

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

5 結束語

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