劉二根，譚茹涵，陳藝琳，郭 力

（華東交通大學(xué)1. 理學(xué)院； 2. 系統(tǒng)工程與密碼學(xué)研究所，江西 南昌 330013）

隨著疫情的持續(xù)蔓延，“無接觸式”一詞成為了當(dāng)下熱點(diǎn)。生產(chǎn)生活中部分工作已由機(jī)器人替代人執(zhí)行，抗疫機(jī)器人可以在一線檢測來訪人員體溫，安防機(jī)器人能提醒司機(jī)掃碼登記，送餐機(jī)器人在隔離區(qū)提供遠(yuǎn)程配送等，在特殊時(shí)期，智能巡線機(jī)器人的投入使用在人與人的安全距離上多建立了一道防線。而路徑規(guī)劃是智能機(jī)器人的關(guān)鍵技術(shù)之一。

路徑規(guī)劃是指機(jī)器人在規(guī)劃好的環(huán)境中搜索出一條或路徑長度最短，或耗時(shí)最短的最優(yōu)路徑，還應(yīng)根據(jù)對環(huán)境信息的把握，遵循一定的性能要求，使得路徑與障礙物無碰撞。 蟻群、人工勢場、遺傳算法、A*、Dijkstra 等是常用的路徑規(guī)劃算法。 Khatib 等[1]提出人工勢場算法，是傳統(tǒng)算法中較成熟且高效的規(guī)劃方法，但容易陷入陷阱和局部極小點(diǎn)，徐小強(qiáng)等[2]采用人工勢場法規(guī)劃路徑，障礙物和必經(jīng)點(diǎn)分別對機(jī)器人產(chǎn)生排斥力和吸引力，在此過程中,機(jī)器人對障礙物的斥力比較敏感，使得路徑易在目標(biāo)點(diǎn)附近游離，無法達(dá)到目標(biāo)點(diǎn)。 張馳等[3]將勢場算法結(jié)合蟻群，重建啟發(fā)函數(shù)，更新了信息素規(guī)則，從局部最優(yōu)解中解脫。 王小會(huì)等[4]通過嵌入Dijkstra 算法實(shí)現(xiàn)一種經(jīng)過必經(jīng)點(diǎn)的最短路徑。 曹祥紅等[5]利用Dijkstra 算法搜索到全局路徑后，導(dǎo)入ACO 算法進(jìn)行路徑優(yōu)化，提高了效率，但沒有考慮陷阱的情況。Hart[6]提出了A*算法，引入估價(jià)函數(shù)，如果估價(jià)函數(shù)等于最短距離，那么搜索將嚴(yán)格按照最短路徑進(jìn)行，此時(shí)的搜索效率最高。 羅漢杰等[7]選擇曼哈頓距離作為估價(jià)函數(shù)，計(jì)算出最佳路徑，但未對軌跡做平滑處理，無法滿足現(xiàn)實(shí)情況下的機(jī)動(dòng)性。 余文凱等[8]利用K-Means 對地圖進(jìn)行分區(qū)處理，根據(jù)聚類結(jié)果，對評價(jià)函數(shù)和節(jié)點(diǎn)選擇方式進(jìn)行改善，改善了平滑度，搜索效率更高。蟻群算法1991 年由Dorigo 提出，吸收了螞蟻的行為特性，根據(jù)信息素濃度進(jìn)行路徑的選擇，算法魯棒性較強(qiáng)，設(shè)置簡單，但收斂速度慢，沒有考慮地形的因素。 左敏等[9]引入自適應(yīng)遷移概率函數(shù)，提高了算法的收斂速度，但沒考慮平滑度的需求。

基于對路徑規(guī)劃問題中障礙物的繞過、路徑平滑度、尋路效率等因素的考慮，采用A* 結(jié)合ACO 算法的組合模型對機(jī)器人路徑進(jìn)行規(guī)劃，利用A* 算法的全局搜索能力，找出兩點(diǎn)之間最合適的路徑，在進(jìn)行多點(diǎn)規(guī)劃時(shí)，采用改進(jìn)后的蟻群算法求解多點(diǎn)之間最優(yōu)路徑。

1 全局路徑規(guī)劃

1.1 環(huán)境建模

在仿真環(huán)境中， 障礙物是不可避免的參數(shù)，本實(shí)驗(yàn)采用柵格法對環(huán)境進(jìn)行模擬，將環(huán)境劃分為二值網(wǎng)格單元見圖1，其中柵格大小暫定為1，實(shí)際行駛過程中會(huì)根據(jù)機(jī)器人大小進(jìn)行設(shè)定。 將巡線地圖設(shè)為60×60 的柵格圖，其中黑色區(qū)域?yàn)榈貓D中的障礙物區(qū)域，白色區(qū)域?yàn)榘踩珔^(qū)域。 其中的散點(diǎn)代表著巡線機(jī)器人要巡視的地點(diǎn)。

圖1 環(huán)境仿真柵格圖Fig.1 Environment simulation grid

1.2 A*算法原理

A* 為一種多角度進(jìn)行搜索的全局尋路算法，選取在當(dāng)前位置周圍F 值最小的點(diǎn)為路徑的下一步。 F 為代價(jià)函數(shù)，計(jì)算公式為

式中：G 為從起點(diǎn)移動(dòng)到指定位置的移動(dòng)代價(jià),取橫向及縱向?yàn)?0，對角線為14；H 為從指定位置移動(dòng)到終點(diǎn)的估算成本，其中路徑忽略障礙物，當(dāng)前選用Manhattan 方法進(jìn)行估算

計(jì)算當(dāng)前位置橫或縱向移動(dòng)到達(dá)終點(diǎn)所經(jīng)過的方格數(shù)。

A*算法規(guī)定了路徑的角度，傳統(tǒng)算法有8 個(gè)角度對外擴(kuò)展。 具體步驟如下：

①設(shè)定open 表存放當(dāng)前點(diǎn)可能要經(jīng)過的下一個(gè)點(diǎn)，設(shè)定close 表存放不能經(jīng)過的點(diǎn)；

②搜索與八個(gè)位置對應(yīng)相鄰的柵格，將當(dāng)前位置設(shè)置為父節(jié)點(diǎn)，設(shè)為點(diǎn)A；

③排除掉障礙物和已經(jīng)走過的位置，剩余位置設(shè)置為子節(jié)點(diǎn)，都放入open 列表中，進(jìn)行F 值的計(jì)算，將子節(jié)點(diǎn)中F 值最小的點(diǎn)，設(shè)為點(diǎn)B，加入close 列表；

④將B 點(diǎn)設(shè)置為父節(jié)點(diǎn)后重復(fù)操作；

⑤當(dāng)發(fā)現(xiàn)此點(diǎn)的子節(jié)點(diǎn)已經(jīng)在open 列表中，假設(shè)為點(diǎn)C，則檢查由點(diǎn)A 直接到點(diǎn)C 是否會(huì)比A-B-C的路線更優(yōu)，若是，則退回一步，重新將A 設(shè)置為父節(jié)點(diǎn)，此時(shí)B 點(diǎn)已進(jìn)入close 列表，不會(huì)參與進(jìn)行下一點(diǎn)的路徑選擇。

從圖2 中A* 算法的路徑選擇可以明顯看出路徑結(jié)果角度生硬，轉(zhuǎn)折點(diǎn)過多，不夠平滑。 對此路徑進(jìn)行平滑處理：遍歷路徑上的點(diǎn)，若是兩點(diǎn)之間無障礙物，則可直接連接。 基于此條平滑準(zhǔn)則，需要對兩點(diǎn)之間經(jīng)歷的柵格進(jìn)行判斷，判斷其是否有障礙物。

1.3 障礙物判斷

圖2 A* 算法尋路結(jié)果圖Fig.2 A* algorithm path finding result

①計(jì)算兩點(diǎn)之間直線方程f；

②由于柵格是以整數(shù)坐標(biāo)為中心， 上下左右距離中心0.5 個(gè)位置的正方形， 取距起點(diǎn)縱坐標(biāo)0.5 個(gè)位置為第1 個(gè)測量點(diǎn)， 每距離1 個(gè)位置進(jìn)行測量，生成列表y=［y1，y2，…，y3］；

③基于直線方程，生成列表x=［x1，x2，…，x3］；

④判斷y 中每2 個(gè)相鄰的值間隔幾個(gè)柵格

num=math.ceil（x［i］-）-math.floor（x［i-1］） ( 3 )其中，math.ceil 是向上取整，math.floor 是向下取整。

圖3 一條直線經(jīng)過的柵格Fig.3 A grid with a straight line

平滑后的A* 算法不僅能使路徑更流暢，還能成功脫離“陷阱”，由圖中可看出，在某個(gè)障礙物附近徘徊的線條平滑后成功出逃。

圖4 不同A* 算法結(jié)果比較Fig.4 Comparison of results for different A* algorithms

2 最優(yōu)路徑規(guī)劃

2.1 實(shí)驗(yàn)蟻群算法原理

蟻群算法是一種啟發(fā)式優(yōu)化算法，蟻群在尋找食物時(shí)，總是能找到一條從食物到蟻穴的最短路徑，信息素在其中發(fā)揮了很大作用，螞蟻?zhàn)哌^的路徑都會(huì)留下信息素，剩余的螞蟻選擇路徑時(shí)會(huì)受信息素的濃度影響，在岔路口時(shí)，傾向于選擇濃度更高的一側(cè)。

在A*算法找到全局路徑后， 構(gòu)建信息素矩陣， 信息素矩陣中的元素會(huì)在迭代過程中隨著路徑不斷變化，迭代完成后，信息素濃度最高的路徑就是最優(yōu)的結(jié)果。

傳統(tǒng)蟻群算法對信息素處理分為全局和局部兩種，全局處理是在螞蟻循環(huán)完整個(gè)路徑后，對整個(gè)信息素矩陣進(jìn)行更新，局部信息素處理是在螞蟻每完成一步后更新信息素。本實(shí)驗(yàn)引入雙信息素策略，局部與全局同時(shí)進(jìn)行，能有效克服傳統(tǒng)蟻群易陷入局部最優(yōu)解的問題。

2.2 算法描述

1） 設(shè)置螞蟻數(shù)量，輸入必訪問點(diǎn)列表，設(shè)置迭代次數(shù)，初始化點(diǎn)之間的距離矩陣，信息素矩陣，啟發(fā)函數(shù)矩陣；

2） 將螞蟻放在不同點(diǎn)上，盡量保證螞蟻的起始點(diǎn)不同，并記錄下螞蟻訪問的點(diǎn)下標(biāo)，將其加入禁忌表，表示下次不會(huì)再重復(fù)訪問此點(diǎn)；

3） 根據(jù)狀態(tài)轉(zhuǎn)移概率對下一次訪問點(diǎn)做出選擇

式中：α 為信息啟發(fā)式因子；β 為期望啟發(fā)式因子；τ 為信息素濃度；η為啟發(fā)式信息，取值為

一般取為點(diǎn)間距離的倒數(shù)；

4） 在自然界中，螞蟻遺留的信息素會(huì)隨著時(shí)間流逝而揮發(fā)，模擬此過程，更新信息素矩陣，螞蟻移動(dòng)到下一點(diǎn)后，對信息素進(jìn)行局部更新

5） 重復(fù)以上步驟，一直到路徑形成閉環(huán)，即螞蟻回到起始點(diǎn)。 對表現(xiàn)最優(yōu)的精英螞蟻采用全局信息素更新策略

式（6）中：ρ 為人為定義的信息素?fù)]發(fā)率，一般位于0～1 之間，由于實(shí)驗(yàn)所用到的地圖較小，選擇較低的揮發(fā)率能達(dá)到較好的實(shí)驗(yàn)結(jié)果，故選取ρ 為0.1。 全局更新策略不作用于所有螞蟻，只對每次循環(huán)中的精英螞蟻（路徑最短）使用，這樣做可以減少迭代次數(shù)，加快搜索效率。

3 實(shí)驗(yàn)與比較

采用局部信息素更新策略的蟻群算法稱為蟻量模型，而使用全局信息素更新策略的蟻群算法稱為蟻周模型。 分別對蟻量模型、蟻周模型及雙信息素蟻群算法進(jìn)行實(shí)驗(yàn)，對改進(jìn)蟻群算法的兩種信息素加以權(quán)重，經(jīng)過多次實(shí)驗(yàn)，確定全局信息素權(quán)重為1，局部信息素權(quán)重為2。

圖5 不同ACO 算法結(jié)果對比圖Fig.5 Comparison grid of results for different ACO algorithms

表1 基于不同數(shù)目必經(jīng)點(diǎn)算法所用時(shí)間結(jié)果比較Tab.1 Comparison of time results for algorithms based on different number of required points s

從算法時(shí)間比較表來看， 雙信息素策略對算法時(shí)間影響不大，與另兩類蟻群算法相比，時(shí)間差距在0.5 s 內(nèi)。 在效率對比圖上有15 個(gè)點(diǎn)以及20個(gè)點(diǎn)的三種蟻群算法最優(yōu)解進(jìn)化過程， 可以看出改進(jìn)蟻群算法比兩種傳統(tǒng)算法收斂更快， 且傳統(tǒng)算法易陷入局部最優(yōu)，改進(jìn)算法得到的路徑更優(yōu)。

圖6 效率比較圖Fig.6 Comparison chart of efficiency

5 結(jié)論

本文利用A* 算法得到繞過障礙物的全局路徑，平滑后成功繞過“陷阱”，且得到結(jié)果更優(yōu)的全局路徑，再引進(jìn)雙信息素改進(jìn)傳統(tǒng)蟻群算法，有效克服了蟻群算法易陷入局部最優(yōu)解的缺陷，使得性能顯著提升，且必經(jīng)點(diǎn)越多，路徑越復(fù)雜，優(yōu)化效果越明顯。