基于蟻群算法的無(wú)人設(shè)備路徑規(guī)劃?

孫雨婷 楊紗紗 高新春

（1.江蘇科技大學(xué)電子信息學(xué)院 鎮(zhèn)江 212003）（2.江南造船（集團(tuán)）有限責(zé)任公司 上海 201913）

1 引言

隨著城市建設(shè)的發(fā)展，越來(lái)越多的科技園區(qū)正在興起［1］，因此如何解決園區(qū)內(nèi)的交通問(wèn)題是十分迫切的。在園區(qū)內(nèi)需要大量的通勤車作為后勤保障，并且園區(qū)內(nèi)可能建有涉及國(guó)家機(jī)密的企業(yè)，因此本文提出自動(dòng)駕駛汽車的路徑規(guī)劃，可減少與企業(yè)無(wú)關(guān)的人員進(jìn)入園區(qū)，減少意外的發(fā)生。

無(wú)人駕駛汽車是一種通過(guò)電腦系統(tǒng)實(shí)現(xiàn)無(wú)人駕駛的智能汽車。在互聯(lián)網(wǎng)時(shí)代正得到長(zhǎng)足的發(fā)展，無(wú)人駕駛汽車?yán)枚喾N傳感器、定位導(dǎo)航系統(tǒng)以及人工智能算法，自動(dòng)安全的實(shí)現(xiàn)汽車駕駛［2］，而自動(dòng)駕駛汽車中的路徑規(guī)劃決策功能則為自動(dòng)駕駛車輛研究中最基礎(chǔ)以及最關(guān)鍵的內(nèi)容［3］。

國(guó)內(nèi)外學(xué)者已經(jīng)做出了很多的研究與發(fā)展。陳衛(wèi)等人在蟻群算法應(yīng)用在自動(dòng)撿球機(jī)器人路徑規(guī)劃算法中取得了一定的成果［4］；杜鵬楨，唐振民等研究了一種面向?qū)ο蟮亩嘟巧伻核惴捌渎眯猩虇?wèn)題求解的解決方案，并進(jìn)行仿真實(shí)驗(yàn)［5］；李巧玲對(duì)蟻群算法做出了改進(jìn)，實(shí)現(xiàn)了對(duì)制造系統(tǒng)的物流配送路徑的優(yōu)化［6］；王紅軍等借助改進(jìn)的并行蟻群算法實(shí)現(xiàn)了設(shè)施溫室機(jī)器人的多點(diǎn)路徑規(guī)劃［7］；Chaari I等采用了新的啟發(fā)函數(shù)，使得算法的全局搜索能力更強(qiáng)，但限制了算法的精度與收斂速度［8］。

本文基于蟻群算法，提出園區(qū)內(nèi)通勤車自動(dòng)駕駛路徑規(guī)劃方案，首先根據(jù)園區(qū)內(nèi)通勤車停靠站點(diǎn)建立環(huán)境地圖，根據(jù)欲乘車人員所選擇的站點(diǎn)結(jié)合環(huán)境地圖構(gòu)造解空間，更新算法參數(shù)進(jìn)行迭代，最終輸出最短路徑進(jìn)行駕駛。

2 問(wèn)題描述

以圖1所示的某地圖為例，圖中箭頭所指為通勤車的起點(diǎn)站與終點(diǎn)站，途中星星所示為通勤車沿途的?？空??？梢?jiàn)，若不行駛過(guò)無(wú)人候車的站點(diǎn)，不僅可以節(jié)約車上乘客的時(shí)間，也節(jié)約了通勤車的能源，減少道路的擁擠情況。在園區(qū)內(nèi)各個(gè)站點(diǎn)均設(shè)有壓力傳感裝置，當(dāng)壓力傳感裝置檢測(cè)到站臺(tái)有人候車時(shí)，則立即向正在行駛的通勤車發(fā)出信號(hào)，通勤車收到站臺(tái)的信號(hào)后開(kāi)始進(jìn)行路徑規(guī)劃計(jì)算，以最短的路徑行駛?cè)ゴ钶d乘客。車輛在站臺(tái)?？康却丝蜕宪嚂r(shí)，利用此段時(shí)間進(jìn)行此段行駛時(shí)間內(nèi)收到的有乘客的站臺(tái)信息，并進(jìn)行路徑規(guī)劃，使用統(tǒng)籌學(xué)的原理盡量減少乘客的等待時(shí)間。為保證通勤車不會(huì)一直在部分站點(diǎn)之間徘徊，規(guī)定當(dāng)車輛駛過(guò)此站點(diǎn)后，不再對(duì)此站點(diǎn)進(jìn)行新的路徑規(guī)劃，即當(dāng)通勤車A駛過(guò)1號(hào)站點(diǎn)后，若壓力傳感裝置檢測(cè)到1號(hào)站臺(tái)有乘客，此時(shí)通勤車A不會(huì)返回去搭載1號(hào)站臺(tái)的乘客，乘客需等待下一輛通勤車。為保障行車安全防止出現(xiàn)安全事故，在同一路段每次僅有一輛通勤車在路上行駛。通勤車行駛時(shí)的起點(diǎn)和終點(diǎn)均為固定的停車場(chǎng)，方便通勤車進(jìn)行停放和檢修等操作。

圖1 某地圖與?？空?/p>

3 蟻群算法

3.1 蟻群算法原理

昆蟲學(xué)家在研究螞蟻的蟻群算法是由意大利學(xué)者Dorigo M提出的一種模仿螞蟻尋覓食物的新興群智能算法［9～10］，在后續(xù)的研究中，其他學(xué)者又將此算法運(yùn)用在了旅行商問(wèn)題（traveling salesman problem，TSP）的求解上［11～12］。該方法利用螞蟻在路上留下的信息素含量來(lái)判斷的優(yōu)化程度，具有正反饋與分布協(xié)作式的特點(diǎn)，有較強(qiáng)的魯棒性，易與其他算法結(jié)合［13］。

通勤車在園區(qū)內(nèi)行駛類似于旅行商問(wèn)題，基本蟻群算法求解TSP的方式如下，初始時(shí)刻有m個(gè)螞蟻隨機(jī)分布，并保證沒(méi)有螞蟻在同一位置，蟻群須經(jīng)歷n個(gè)城市［14］，dij（i，j=1，2，3，…，n）表示不同城市i與j間的距離，且記城市i與城市j在t時(shí)刻二者路徑上的信息素的濃度為τij（t），而第k（k=1，2，3，…，m）個(gè)螞蟻從城市i向城市j走訪的關(guān)鍵因素是狀態(tài)轉(zhuǎn)移概率Pkij，狀態(tài)轉(zhuǎn)移概率Pkij由多個(gè)參數(shù)綜合計(jì)算得來(lái)［15］，計(jì)算公式為式（1）：

其中allowk（k=1，2，3…，m）表示了螞蟻k需要走過(guò)的城市的集合［16］；ηij(t)代表了螞蟻在城市i向城市j移動(dòng)的期望值，其是按照自身的適應(yīng)性定義的一種啟發(fā)式函數(shù)ηij=1/dij；α的值越大，城市路徑間信息素越重要，β的值越大，啟發(fā)函數(shù)對(duì)城市選擇的影響越大；taubk表示螞蟻禁忌表，禁忌表能夠跟隨螞蟻的行走進(jìn)行更新記錄，克服了真實(shí)環(huán)境下蟻群不能實(shí)時(shí)更新的不足［17］。

信息素在環(huán)境找中是存在揮發(fā)現(xiàn)象的，為了模仿螞蟻在進(jìn)行城市中轉(zhuǎn)移時(shí)路徑上的信息素持續(xù)揮發(fā)的狀態(tài)［18］，在路徑信息計(jì)算時(shí)加入了揮散因子ρ對(duì)路徑上的信息素進(jìn)行優(yōu)化和更新，這樣可以減少路徑上的信息素持續(xù)累計(jì)過(guò)高帶來(lái)的影響，ρ一般取0～1之間的值。

當(dāng)全部的螞蟻實(shí)現(xiàn)了完成了一次完整的城市走訪后，計(jì)算更新所有城市間的信息素的值［19］，如式（2）：

3.2 算法實(shí)現(xiàn)

采用圖2的算法流程進(jìn)行路徑規(guī)劃。

圖2 算法流程

4 實(shí)驗(yàn)分析

本文將蟻群算法應(yīng)用于科技園區(qū)內(nèi)無(wú)人駕駛通勤車行駛路徑的規(guī)劃中，使用Matlab進(jìn)行算法仿真實(shí)驗(yàn)，算法仿真的環(huán)境為Windows 10，64bit；Matlab 2014a，處理器為inter core i7；主頻2.8GHz；內(nèi)存為16.0GB。

目前較為常用的兩大類構(gòu)建仿真環(huán)境的方法，一是基于網(wǎng)格的方法，二是基于網(wǎng)路或圖的方法。本文采用柵格法屬于基于網(wǎng)格模型，柵格法結(jié)構(gòu)較為簡(jiǎn)單并且易于實(shí)現(xiàn)，是比較常用的模型環(huán)境［21］。

4.1 環(huán)境建立

本文建立20*20共400格的柵格地圖，在Mat?lab中按順序使用矩陣對(duì)柵格進(jìn)行初始化，黑色柵格表示建筑物，白色柵格表示道路，如圖所示，通勤車的始發(fā)站處于1號(hào)柵格，終點(diǎn)站處于400號(hào)柵格，在85號(hào)柵格，237號(hào)柵格，305號(hào)柵格均設(shè)有站點(diǎn)，圖3中淺色色塊所示。

4.2 不鄰近站臺(tái)仿真實(shí)驗(yàn)

在任意兩個(gè)不鄰近站臺(tái)之間搜索最短路徑。如圖3所示，選擇兩個(gè)不鄰近站臺(tái)，初始點(diǎn)選為85號(hào)柵格，終點(diǎn)選為237號(hào)柵格，派出50只螞蟻，共100波次，圖4為搜索出的最短路徑。

圖3 道路和建筑初始化

圖4 某不鄰近站臺(tái)的路徑規(guī)劃

4.3 鄰近站臺(tái)仿真實(shí)驗(yàn)

在任意兩個(gè)鄰近站臺(tái)之間搜索最短路徑。如圖5所示，選擇兩不鄰近站臺(tái)，初始點(diǎn)選為1號(hào)柵格起點(diǎn)站，終點(diǎn)選為85號(hào)柵格，派出50只螞蟻，共100波次，圖5所示為搜索出的最短路徑。

圖5 某鄰近站臺(tái)的路徑規(guī)劃

4.4 全部站臺(tái)仿真實(shí)驗(yàn)

當(dāng)全部站臺(tái)均有乘客時(shí)，通勤車行駛模式僅在有乘客候車的最近的兩個(gè)站臺(tái)間進(jìn)行路徑規(guī)劃，當(dāng)全部站臺(tái)均有乘客時(shí)，通勤車將從起始站開(kāi)始在兩兩站臺(tái)間進(jìn)行路徑規(guī)劃，最終合成結(jié)果圖如圖6所示。派出50只螞蟻，共100波次。

圖6 全部站臺(tái)均有乘客圖

4.5 僅首尾站臺(tái)仿真實(shí)驗(yàn)

僅在起點(diǎn)處有乘客乘車，此時(shí)通勤車行駛的線路最短。如圖7所示，此時(shí)的收斂曲線如圖8，可見(jiàn)算法較快達(dá)到收斂并保持穩(wěn)定。

圖7 最短路徑

圖8 收斂曲線

5 結(jié)語(yǔ)

本文闡述了蟻群算法的原理，并分析了蟻群優(yōu)勢(shì)與缺陷，將蟻群算法應(yīng)用在無(wú)人駕駛的通勤車的路徑規(guī)劃上，并基于柵格法建立仿真環(huán)境進(jìn)行模型仿真。仿真表明算法可用于科技園區(qū)內(nèi)無(wú)人駕駛的通勤車進(jìn)行搭載乘客的路徑規(guī)劃，實(shí)驗(yàn)表明本文方法具有一定的可靠性和實(shí)時(shí)性。規(guī)劃的路徑在轉(zhuǎn)彎處離建筑物較近，在實(shí)際應(yīng)用中可能存在危險(xiǎn)，計(jì)劃在后續(xù)工作中將其作為工作方向。