基于蟻群算法的無人設備路徑規劃?

孫雨婷 楊紗紗 高新春

（1.江蘇科技大學電子信息學院 鎮江 212003）（2.江南造船（集團）有限責任公司 上海 201913）

1 引言

隨著城市建設的發展，越來越多的科技園區正在興起［1］，因此如何解決園區內的交通問題是十分迫切的。在園區內需要大量的通勤車作為后勤保障，并且園區內可能建有涉及國家機密的企業，因此本文提出自動駕駛汽車的路徑規劃，可減少與企業無關的人員進入園區，減少意外的發生。

無人駕駛汽車是一種通過電腦系統實現無人駕駛的智能汽車。在互聯網時代正得到長足的發展，無人駕駛汽車利用多種傳感器、定位導航系統以及人工智能算法，自動安全的實現汽車駕駛［2］，而自動駕駛汽車中的路徑規劃決策功能則為自動駕駛車輛研究中最基礎以及最關鍵的內容［3］。

國內外學者已經做出了很多的研究與發展。陳衛等人在蟻群算法應用在自動撿球機器人路徑規劃算法中取得了一定的成果［4］；杜鵬楨，唐振民等研究了一種面向對象的多角色蟻群算法及其旅行商問題求解的解決方案，并進行仿真實驗［5］；李巧玲對蟻群算法做出了改進，實現了對制造系統的物流配送路徑的優化［6］；王紅軍等借助改進的并行蟻群算法實現了設施溫室機器人的多點路徑規劃［7］；Chaari I等采用了新的啟發函數，使得算法的全局搜索能力更強，但限制了算法的精度與收斂速度［8］。

本文基于蟻群算法，提出園區內通勤車自動駕駛路徑規劃方案，首先根據園區內通勤車停靠站點建立環境地圖，根據欲乘車人員所選擇的站點結合環境地圖構造解空間，更新算法參數進行迭代，最終輸出最短路徑進行駕駛。

2 問題描述

以圖1所示的某地圖為例，圖中箭頭所指為通勤車的起點站與終點站，途中星星所示為通勤車沿途的停靠站。可見，若不行駛過無人候車的站點，不僅可以節約車上乘客的時間，也節約了通勤車的能源，減少道路的擁擠情況。在園區內各個站點均設有壓力傳感裝置，當壓力傳感裝置檢測到站臺有人候車時，則立即向正在行駛的通勤車發出信號，通勤車收到站臺的信號后開始進行路徑規劃計算，以最短的路徑行駛去搭載乘客。車輛在站臺停靠等待乘客上車時，利用此段時間進行此段行駛時間內收到的有乘客的站臺信息，并進行路徑規劃，使用統籌學的原理盡量減少乘客的等待時間。為保證通勤車不會一直在部分站點之間徘徊，規定當車輛駛過此站點后，不再對此站點進行新的路徑規劃，即當通勤車A駛過1號站點后，若壓力傳感裝置檢測到1號站臺有乘客，此時通勤車A不會返回去搭載1號站臺的乘客，乘客需等待下一輛通勤車。為保障行車安全防止出現安全事故，在同一路段每次僅有一輛通勤車在路上行駛。通勤車行駛時的起點和終點均為固定的停車場，方便通勤車進行停放和檢修等操作。

圖1 某地圖與停靠站

3 蟻群算法

3.1 蟻群算法原理

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

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

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

信息素在環境找中是存在揮發現象的，為了模仿螞蟻在進行城市中轉移時路徑上的信息素持續揮發的狀態［18］，在路徑信息計算時加入了揮散因子ρ對路徑上的信息素進行優化和更新，這樣可以減少路徑上的信息素持續累計過高帶來的影響，ρ一般取0～1之間的值。

當全部的螞蟻實現了完成了一次完整的城市走訪后，計算更新所有城市間的信息素的值［19］，如式（2）：

3.2 算法實現

采用圖2的算法流程進行路徑規劃。

圖2 算法流程

4 實驗分析

本文將蟻群算法應用于科技園區內無人駕駛通勤車行駛路徑的規劃中，使用Matlab進行算法仿真實驗，算法仿真的環境為Windows 10，64bit；Matlab 2014a，處理器為inter core i7；主頻2.8GHz；內存為16.0GB。

目前較為常用的兩大類構建仿真環境的方法，一是基于網格的方法，二是基于網路或圖的方法。本文采用柵格法屬于基于網格模型，柵格法結構較為簡單并且易于實現，是比較常用的模型環境［21］。

4.1 環境建立

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

4.2 不鄰近站臺仿真實驗

在任意兩個不鄰近站臺之間搜索最短路徑。如圖3所示，選擇兩個不鄰近站臺，初始點選為85號柵格，終點選為237號柵格，派出50只螞蟻，共100波次，圖4為搜索出的最短路徑。

圖3 道路和建筑初始化

圖4 某不鄰近站臺的路徑規劃

4.3 鄰近站臺仿真實驗

在任意兩個鄰近站臺之間搜索最短路徑。如圖5所示，選擇兩不鄰近站臺，初始點選為1號柵格起點站，終點選為85號柵格，派出50只螞蟻，共100波次，圖5所示為搜索出的最短路徑。

圖5 某鄰近站臺的路徑規劃

4.4 全部站臺仿真實驗

當全部站臺均有乘客時，通勤車行駛模式僅在有乘客候車的最近的兩個站臺間進行路徑規劃，當全部站臺均有乘客時，通勤車將從起始站開始在兩兩站臺間進行路徑規劃，最終合成結果圖如圖6所示。派出50只螞蟻，共100波次。

圖6 全部站臺均有乘客圖

4.5 僅首尾站臺仿真實驗

僅在起點處有乘客乘車，此時通勤車行駛的線路最短。如圖7所示，此時的收斂曲線如圖8，可見算法較快達到收斂并保持穩定。

圖7 最短路徑

圖8 收斂曲線

5 結語

本文闡述了蟻群算法的原理，并分析了蟻群優勢與缺陷，將蟻群算法應用在無人駕駛的通勤車的路徑規劃上，并基于柵格法建立仿真環境進行模型仿真。仿真表明算法可用于科技園區內無人駕駛的通勤車進行搭載乘客的路徑規劃，實驗表明本文方法具有一定的可靠性和實時性。規劃的路徑在轉彎處離建筑物較近，在實際應用中可能存在危險，計劃在后續工作中將其作為工作方向。