郭蓬 張金煒 戎輝 王文揚(yáng) 高嵩 何佳

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

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

中圖分類號(hào)： TN911.1?34 ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 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ī)劃又稱為動(dòng)態(tài)路徑規(guī)劃，它是在環(huán)境未知的情況下通過感知系統(tǒng)實(shí)時(shí)感知周圍環(huán)境做出局部行駛路線。路徑規(guī)劃的算法有很多，大致可以分為五大類：傳統(tǒng)路徑規(guī)劃算法（模擬退火法、人工勢(shì)場(chǎng)法等）[2]、啟發(fā)式搜索算法（Dijkstra算法、A*算法及其變種等）[3]、離散優(yōu)化算法（模型預(yù)測(cè)算法、幾何軌線算法等）[4]、隨機(jī)采樣算法（隨機(jī)路圖法、快速隨機(jī)拓展樹法等）[5?6]和智能仿生算法（遺傳算法、蟻群算法、神經(jīng)網(wǎng)絡(luò)等）[7]。

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

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

1 ?問題描述

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

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

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

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

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

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

2 ?蟻群算法

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

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

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

圖2 ?蟻群算法流程圖

2） 節(jié)點(diǎn)選擇

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

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

3） 信息素更新

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

3 ?仿真實(shí)驗(yàn)與驗(yàn)證

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

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

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

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

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

3.2 ?仿真實(shí)驗(yàn)一

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

圖4 ?仿真實(shí)驗(yàn)一

3.3 ?仿真實(shí)驗(yàn)二

三個(gè)試驗(yàn)室之間選擇最短路徑，選擇電磁電氣試驗(yàn)室、零部件試驗(yàn)室2以及汽車安全試驗(yàn)室，在三個(gè)試驗(yàn)室之間經(jīng)過6種不同組合的仿真實(shí)驗(yàn)，選擇如圖5曲線所示路線，參觀順序?yàn)槠鹗键c(diǎn)、電磁電氣試驗(yàn)室、汽車安全試驗(yàn)室、零部件試驗(yàn)室2、出口，此順序?yàn)閰⒂^這三個(gè)試驗(yàn)室最短行駛路徑，其中1號(hào)柵格是無人車起始點(diǎn)，609號(hào)柵格是無人車出口位置。

圖5 ?仿真實(shí)驗(yàn)二

3.4 ?仿真實(shí)驗(yàn)3

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

圖6 ?仿真實(shí)驗(yàn)三

參觀順序?yàn)槠鹗键c(diǎn)、NVH試驗(yàn)室、電磁電氣試驗(yàn)室、零部件試驗(yàn)室2、汽車安全試驗(yàn)室、出口。

4 ?結(jié) ?論

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

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

2） 在開放三個(gè)試驗(yàn)室的情況下，通過6組實(shí)驗(yàn)可得到正確的參觀順序和最短路徑。

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

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

參考文獻(xiàn)

[1] 孫梅.移動(dòng)機(jī)器人路徑規(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] 霍鳳財(cái)，任偉建，劉東輝.基于改進(jìn)的人工勢(shì)場(chǎng)法的路徑規(guī)劃方法研究[J].自動(dòng)化技術(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] 余卓平，李奕姍，熊璐.無人車運(yùn)動(dòng)規(guī)劃算法綜述[J].同濟(jì)大學(xué)學(xué)報(bào)（自然科學(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] 孫豐財(cái)，張亞楠，史旭華.改進(jìn)的快速擴(kuò)展隨機(jī)樹路徑規(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] 于樹科，瞿國慶，祁宏宇，等.蟻群遺傳融合算法在移動(dòng)機(jī)器人路徑規(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)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J].機(jī)械設(shè)計(jì)與制造，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] 史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，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.