蟻群算法在無人駕駛園區(qū)參觀路線的應(yīng)用

郭蓬 張金煒 戎輝 王文揚 高嵩 何佳

摘 ?要： 針對無人車在中國汽車技術(shù)研究中心院區(qū)內(nèi)參觀線路的規(guī)劃問題，提出一種基于蟻群算法參觀路線規(guī)劃的方法。首先利用柵格搭建環(huán)境地圖，然后通過蟻群算法設(shè)置始末位置、構(gòu)造解空間、更新信息素、增加迭代次數(shù)、判斷路徑長度，最后輸出最短路線。文中根據(jù)參觀要求做出三種不同路徑規(guī)劃方案以驗證算法的可行性。

關(guān)鍵詞： 無人車; 蟻群算法; 路線規(guī)劃; 信息表; 柵格地圖; 最短路線

中圖分類號： TN911.1?34 ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）11?0149?04

Abstract： A visit route planning method based on ant colony optimization algorithm is presented to solve the planning problem of the visit route of unmanned vehicle in district of China Automotive Technology and Research Center. The grid is used to construct the environment map， and the ant colony optimization algorithm is used to set the beginning and end positions， construct the solution space， update the pheromones， increase the number of iterations， judge the path length， so as to output the shortest route. Three different schemes are made according to visit requirements， which are used to verify the feasibility of the algorithm

Keywords： unmanned vehicle; ant colony optimization algorithm; route planning; pheromone; grid map; shortest route

0 ?引 ?言

無人車路徑規(guī)劃是當(dāng)前無人駕駛領(lǐng)域的關(guān)鍵技術(shù)之一。路徑規(guī)劃可以分為全局路徑規(guī)劃和局部路徑規(guī)劃[1]，全局路徑規(guī)劃又稱為靜態(tài)路徑規(guī)劃，它是在環(huán)境已知的情況下由初始位置到目標(biāo)位置尋找一條最優(yōu)或者近似最優(yōu)的無碰撞路徑。局部路徑規(guī)劃又稱為動態(tài)路徑規(guī)劃，它是在環(huán)境未知的情況下通過感知系統(tǒng)實時感知周圍環(huán)境做出局部行駛路線。路徑規(guī)劃的算法有很多，大致可以分為五大類：傳統(tǒng)路徑規(guī)劃算法（模擬退火法、人工勢場法等）[2]、啟發(fā)式搜索算法（Dijkstra算法、A*算法及其變種等）[3]、離散優(yōu)化算法（模型預(yù)測算法、幾何軌線算法等）[4]、隨機采樣算法（隨機路圖法、快速隨機拓展樹法等）[5?6]和智能仿生算法（遺傳算法、蟻群算法、神經(jīng)網(wǎng)絡(luò)等）[7]。

蟻群算法（ACO）是一種模擬進(jìn)化算法，又稱為螞蟻算法，是由Dorigo等人提出[8]的，主要是仿照螞蟻群體在覓食過程中尋找路徑，即巢與食物之間的最短路徑行為進(jìn)行路徑規(guī)劃。

本文利用基于蟻群算法的無人車在中國汽車技術(shù)研究中心院區(qū)內(nèi)規(guī)劃參觀路線。首先根據(jù)實際需要建立環(huán)境地圖，進(jìn)而選擇初始點和目標(biāo)點，構(gòu)造解空間，更新信息素，增加迭代次數(shù)，判斷路徑長度，最后輸出最短路線。Matlab仿真實驗證明了本文方法的有效性，可用于院區(qū)內(nèi)參觀路線的路徑規(guī)劃。

1 ?問題描述

如圖1所示為中國汽車技術(shù)研究中心院區(qū)，其橫向長度為534 m，縱向長度為462 m，道路寬14 m，共有19個試驗室，按照參觀規(guī)定只開放NVH試驗室、電磁電氣試驗室、零部件試驗室2、性能開放綜合試驗室2、汽車安全試驗室等五個試驗室，圖1中[l]為無人車出發(fā)位置，②～⑥為試驗室停車位置，⑦為出口位置。

圖1 ?中國汽車技術(shù)研究中心院區(qū)

本文根據(jù)具體要求，利用蟻群算法給出三種方案，以驗證蟻群算法在院區(qū)內(nèi)規(guī)劃參觀路線的可行性。

方案一：驗證蟻群算法是否能夠搜索最短路徑，采用在任意兩個試驗室之間尋找最短行駛路線的方法，以驗證蟻群算法搜索最短路徑的可行性。

方案二：根據(jù)參觀要求，在特殊情況下僅開放三個試驗室，磁電氣試驗室、汽車安全試驗室以及零部件試驗室2。利用蟻群算法計算出三個實驗室的參觀順序以及最短路線。

方案三：五個試驗室全部開放，并且規(guī)定NVH試驗室為第一個參觀的實驗室，汽車安全試驗室為最后一個參觀的實驗室，利用蟻群算法計算出五個實驗室的參觀順序以及最短路線。

2 ?蟻群算法

螞蟻尋找路徑不是單只螞蟻的行為，而是一個群體性的行為。它們互相協(xié)作，每只螞蟻都會在所走的路徑上留下信息素（路徑長度的倒數(shù)）[9?10]，當(dāng)下一只螞蟻路過該路徑時就會利用信息素做出下一步的判斷，并且會釋放出自己的信息素，這樣就形成了信息素的積累[11]，使得后續(xù)螞蟻可以選擇信息素強的路徑，隨著大量螞蟻在信息素的作用下不斷搜索路徑，最終會得到一條最優(yōu)或者次優(yōu)路徑[12?13]。蟻群算法流程圖如圖2所示。

1） 構(gòu)造解空間

采用在二維空間內(nèi)構(gòu)建解空間的方法，構(gòu)造柵格地圖，用白色柵格表示可行駛區(qū)域，黑色柵格表示障礙物區(qū)域，對柵格進(jìn)行數(shù)字標(biāo)號處理，只有白色柵格才能成為搜索路徑的節(jié)點，設(shè)置出發(fā)點和目標(biāo)點，然后通過選擇概率公式選擇下一個節(jié)點，直至選擇到目標(biāo)點，這樣所有經(jīng)過的柵格就組成了解空間。

圖2 ?蟻群算法流程圖

2） 節(jié)點選擇

每次迭代有[M]只螞蟻搜索路徑，一共經(jīng)過[N]次迭代，設(shè)置出發(fā)點為[S]，目標(biāo)點為[E]，每只螞蟻選擇下一個節(jié)點[j]的方法是：計算當(dāng)前節(jié)點[j]與四周節(jié)點[i]之間的選擇概率[Pi，j]，利用選擇概率[Pi，j]選擇下一節(jié)點。[Pi，j]的計算方法如下：

式中：[i]代表當(dāng)前節(jié)點的周圍八個節(jié)點數(shù)字標(biāo)號集合;[τi，j]為信息素;[ηi，j]為啟發(fā)值;[B]為影響因子;[w]表示沒有被選擇點的集合。

3） 信息素更新

通常有兩種信息素更新方法，第一種如式（2）所示，叫做實時信息素更新，即當(dāng)前螞蟻在路徑搜索中每過一個節(jié)點就會對該節(jié)點進(jìn)行信息素更新。本文即采用該方法。

3 ?仿真實驗與驗證

本文將蟻群算法應(yīng)用于無人車院區(qū)參觀路線的規(guī)劃中，為驗證本文方法的可行性和有效性，采用Matlab進(jìn)行大量仿真實驗。算法運行環(huán)境如下：Windows7，64 bit;Matlab，R2017a;處理器Intel[?] Xeon[?] CPU E5?1620;主頻3.50 GHz;內(nèi)存32 GB。

3.1 ?建立仿真環(huán)境

針對無人車參觀路線的規(guī)劃問題，本文需要根據(jù)真實環(huán)境搭建環(huán)境模型。有兩大類構(gòu)建環(huán)境模型的方法：一是基于網(wǎng)絡(luò)或圖的模型方法;二是基于網(wǎng)格的模型方法。如前文所述，蟻群算法利用建立柵格圖的方法，此方法屬于網(wǎng)格模型中的一種。柵格圖法結(jié)構(gòu)簡單、易于實現(xiàn)，是常用的建模方法。

本文建立25×25的柵格地圖，共有625個正方形柵格，按照從左往右、從上到下的順序?qū)鸥襁M(jìn)行1～625編號。白色柵格代表道路，黑色柵格代表建筑物。按照院區(qū)實際尺寸規(guī)劃柵格地圖，因為真實道路寬約20 m，所以設(shè)計每單位長度柵格表示實際長度20 m，如圖3所示。

圖3 ?仿真環(huán)境圖

3.2 ?仿真實驗一

任意兩個試驗室之間搜索最短路徑。如圖4所示，選擇兩個試驗室，NVH試驗室和性能開發(fā)綜合試驗室2。選擇初始點84號柵格，目標(biāo)點294號柵格，設(shè)置80只螞蟻，迭代100次，將搜索出的路徑進(jìn)行長度比較選擇出最短路徑，如圖中曲線所示為最短路徑。

圖4 ?仿真實驗一

3.3 ?仿真實驗二

三個試驗室之間選擇最短路徑，選擇電磁電氣試驗室、零部件試驗室2以及汽車安全試驗室，在三個試驗室之間經(jīng)過6種不同組合的仿真實驗，選擇如圖5曲線所示路線，參觀順序為起始點、電磁電氣試驗室、汽車安全試驗室、零部件試驗室2、出口，此順序為參觀這三個試驗室最短行駛路徑，其中1號柵格是無人車起始點，609號柵格是無人車出口位置。

圖5 ?仿真實驗二

3.4 ?仿真實驗3

五個試驗室之間搜索最短路徑，按照規(guī)定NVH試驗室第一個參觀，汽車安全試驗室最后一個參觀，所以共有24種不同組合方式，經(jīng)過仿真驗證，圖6曲線所示為最短行駛路徑。

圖6 ?仿真實驗三

參觀順序為起始點、NVH試驗室、電磁電氣試驗室、零部件試驗室2、汽車安全試驗室、出口。

4 ?結(jié) ?論

本文在院區(qū)靜態(tài)環(huán)境下，利用柵格對無人車在院區(qū)的行駛環(huán)境創(chuàng)建模型圖，通過蟻群算法規(guī)劃出參觀線路，得到以下三種實驗結(jié)論：

1） 利用蟻群算法可以得到參觀院區(qū)內(nèi)任意兩個試驗室的最短路線。

2） 在開放三個試驗室的情況下，通過6組實驗可得到正確的參觀順序和最短路徑。

3） 在五個試驗室全部開放的情況下，通過24組實驗可得到正確的參觀順序和最短路徑。

實驗仿真結(jié)果證明，蟻群算法可用于中汽中心院區(qū)三種參觀需求的全局路徑規(guī)劃。后續(xù)擬將基于蟻群算法的全局路徑規(guī)劃和局部路徑規(guī)劃進(jìn)行結(jié)合算法開發(fā)并上車進(jìn)行實際運行。

參考文獻(xiàn)

[1] 孫梅.移動機器人路徑規(guī)劃技術(shù)綜述[J].山東工業(yè)技術(shù)，2016（21）：164.

SUN Mei. Overview of path planning technology for mobile robots [J]. Shandong industrial technology， 2016（21）： 164.

[2] 霍鳳財，任偉建，劉東輝.基于改進(jìn)的人工勢場法的路徑規(guī)劃方法研究[J].自動化技術(shù)與應(yīng)用，2016，35（3）：63?67.

HUO Fengcai， ?REN Weijian， LIU Donghui. Research on path planning method based on improved artificial potential field method [J]. Automation technology and application， 2016， 35（3）： 63?67.

[3] ZHANG L， SUN L， ZHANG S， et al. Trajectory planning for an indoor mobile robot using quintic Bezier curves [C]// 2015 IEEE International Conference on Robotics and Biomimetics. Zhuhai： IEEE， 2015： 757?762.

[4] CHU K， LEE M， SUNWOO M. Local path planning for off?road autonomous driving with avoidance of static obstacles [J]. IEEE transactions on intelligent transportation systems， 2012， 13（4）： 1599?1616.

[5] 余卓平，李奕姍，熊璐.無人車運動規(guī)劃算法綜述[J].同濟大學(xué)學(xué)報（自然科學(xué)版），2017，45（8）：1150?1159.

YU Zhuoping， LI Yishan， XIONG Lu. Unmanned vehicle motion planning algorithm review [J]. Journal of Tongji University （Natural Science Edition）， 2017， 45（8）： 1150?1159.

[6] 孫豐財，張亞楠，史旭華.改進(jìn)的快速擴展隨機樹路徑規(guī)劃算法[J].傳感器與微系統(tǒng)，2017，36（9）：129?131.

SUN Fengcai， ZHANG Yanan， SHI Xuhua. Improved rapid expansion of random tree path planning algorithm [J]. Transducer and microsystem technologies， 2017， 36（9）： 129?131.

[7] 于樹科，瞿國慶，祁宏宇，等.蟻群遺傳融合算法在移動機器人路徑規(guī)劃中的應(yīng)用[J].火力與指揮控制，2017，42（12）：88?91.

YU Shuke， QU Guoqing， QI Hongyu， et al. Application of ant colony genetic fusion algorithm in mobile robot path planning [J]. Fire control and command control， 2017， 42（12）： 88?91.

[8] 王志中.基于改進(jìn)蟻群算法的移動機器人路徑規(guī)劃研究[J].機械設(shè)計與制造，2018（1）：242?244.

WANG Zhizhong. Based on improved ant colony algorithm for mobile robot path planning study [J]. Journal of mechanical design and manufacturing， 2018（1）： 242?244.

[9] HASSAN S， YOON J. Virtual maintenance system with a two?staged ant colony optimization algorithm [C]// 2011 IEEE International Conference on Robotic and Automation. Shanghai： IEEE， 2011： 931?936.

[10] DENG Yan， HU Hongyu， TIAN Xiaolu， et al. A path planning method for substation laser inspection robot based on improved ant colony algorithm [C]// The 2nd International Conference on Computer Engineering， Information Science & Application Technology. [S.l.]： Atlantis Press， 2017： 62?69.

[11] ESCARIO J B， JIMENEZ J F， GIRON?SIERRA J M. Ant co?lony extended： experiments on the traveling salesman problem [J]. Expert systems with applications，2015， 42： 390?410.

[12] ERIN B， ABIYEV R， IBRAHIM D. Teaching robot navigation in the presence of obstacles using a computer simulation program [J]. Procedia： social and behacioral sciences， 2010， 2（2）： 565?571.

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

SHI Enxiu， CHEN Minmin， LI Jun， et al. Study on global path planning for mobile robot based on ant colony algorithm [J]. Transactions of the Chinese society of agricultural machi?nery， 2014， 45（6）： 53?57.

[14] 胡玉文.城市環(huán)境中基于混合地圖的智能車輛定位方法研究[D].北京：北京理工大學(xué)，2014.

HU Yuwen. Hybrid map based localization method for unmanned ground vehicle in urban scenario [D]. Beijing： Beijing Institute of Technology， 2014.