面向復合地圖的移動機器人分層路徑規劃

武 星 楊俊杰 湯 凱 翟晶晶

樓佩煌南京航空航天大學機電學院，南京，210016

0 引言

路徑規劃是移動機器人研究的重點領域，其主要目的是在給定環境下搜索出一條從起點到終點的優化路徑，該路徑在不與障礙物碰撞的前提下，盡量保證行駛距離最短、安全性最高、行駛時間最優等一個或多個性能指標[1-2]。根據對環境信息的認知程度，路徑規劃可分為兩類：對環境有完整認知的全局路徑規劃、環境未知或動態變化的局部路徑規劃[3-4]。前者旨在利用全局視野尋找一條全局優化路徑，后者旨在躲避障礙物，修正全局路徑。環境建模是機器人理解周圍環境的重要途徑，也是全局路徑規劃的前提，常用的環境地圖有柵格地圖[5-6]、可視圖[7]、拓撲地圖[8]。

隨著移動機器人工作空間的不斷擴大以及作業場景的日益復雜化，跨車間配送、非預期障礙物等因素增加了路徑規劃的難度。現有的全局路徑規劃方法如A*算法[9-10]、蟻群算法[11-12]、粒子群算法[13]、遺傳算法[14-15]等常因搜索空間的膨脹導致搜索效率急劇降低，甚至無法搜索到最優解。傳統局部路徑規劃方法如人工勢場法(artificial potential field, APF)[16]、動態窗口法(dynamic window approach, DWA)[17]等存在易于陷入局部極值點、避障實時性及成功率不高等問題。

針對部分未知的復雜大場景環境，余翀等[18]提出一種分層次多步驟的路徑規劃算法，首先在拓撲層規劃，采用起泡算法生成Voronoi圖來描述全局拓撲關系，然后利用廣義水平集實現拓撲層最優路徑規劃，最后在柵格層利用快速行進法(fast marching method，FMM)實現路徑再規劃。該方法平衡了單一路徑規劃算法的缺陷，發揮了融合算法優勢，但未充分考慮機器人運動特性，生成的路徑較長且拐點較多。MARTINS等[19]提出一種IMOA-star(improved multi-objective a-star)方法，通過重復利用存儲為pickle格式的障礙圖，避免了頻繁計算柵格的啟發函數從而縮短算法的執行時間，同時引入路徑問題感知執行器，減小了路徑長度和提高了路徑平滑度，然而該方法未充分考慮動態障礙物對障礙圖更新的影響。徐開放[20]提出一種基于度量-拓撲分層結構的復合地圖的D*Lite和BP神經網絡融合路徑規劃方法，全局采用低分辨率地圖，并使用D*Lite算法規劃出一組路徑節點序列，路徑節點間利用增強學習實現了相鄰兩個節點的抵達問題。該方法將任務拆解，減少搜索空間，是一種較好的解決方案，但只能輸出離散的動作，不利于機器人連續控制。深度強化學習(deep reinforcement learning，DRL)兼具深度學習的感知能力和強化學習的決策能力，有望改善現有路徑規劃方法在未知環境下的缺陷，這類端到端的方法能夠對周圍環境迅速作出決策，靈活性高、適應能力強，可以更好地處理突發情況。然而，DRL還有些亟待優化的問題，如訓練耗時長、樣本利用率低等問題。

為了克服上述方法的不足且更好適應部分未知的復雜大場景環境，本文提出一種面向復合地圖的移動機器人分層路徑規劃方法，引入層次圖思想，建立了拓撲-柵格-度量復合地圖，實現了不同抽象程度和精細程度的環境表示。在此基礎上進行路徑規劃，先針對拓撲-柵格地圖生成全局優化的初始路徑，機器人沿初始路徑行駛時再探測周圍局部環境，并使用深度強化學習算法進行避障路徑規劃，通過分層分區域方式提高路徑規劃算法的效率和成功率。

1 復合地圖分層路徑規劃框架

1.1 復合地圖描述

1.1.1層次圖定義

目前多數路徑規劃方法均基于某種環境地圖在全局范圍內開展搜索，搜索范圍大導致搜索效率不盡人意。為減小路徑規劃算法的搜索范圍，通常會對大規模場景進行抽象描述和層次分解，層次圖非常適合這種情況。

層次圖采用多叉樹來表達，樹中包含多個抽象層次，抽象程度自上而下逐層降低。每一層由一個或多個關鍵節點構成，節點之間通過邊連接，因此每個抽象層都是一幅圖。構建層次圖是一個迭代的過程，某一層中的關鍵節點是其下一層圖的抽象描述，逐層分解直至對環境做出詳細的描述。每個關鍵節點都代表了某一局部環境，故層次圖不宜過深，否則導致關鍵點間隔過近，抽象程度降低，進而會增加算法的復雜度。層次圖序列L可表示為

L={L0,L1,L2,…,Ld}

其中，Li為第i層抽象。值得注意的是，L0為根層次，是對環境地圖的最高層抽象；Ld為最深層，即最小的子地圖。層次圖中每一層Li都有圖Gi對應，Gi由關鍵節點、普通節點、連接各節點的邊及其權重等信息組成，本文將其演化為拓撲地圖。普通節點僅用于輔助路徑搜索，而關鍵節點負責連接子地圖與其父地圖，在層次圖的同一層次中通過離線先驗路徑連接相鄰子地圖。以制造業公司場景為例，為每個子區域設置關鍵節點，層次圖的表達方式如圖1所示。

圖1 層次圖示例Fig.1 Example of hierarchical graph

在圖1中，紅色方點和藍色圓點分別代表關鍵節點和普通節點，連接節點的黑色線條為先驗路徑(邊)。其中，兩個帶有五角星標記的關鍵節點是同一個點，只不過顯示在不同層級上，可實現相鄰層級間的訪問。根層次L0描述了公司的組織架構，包含行政室、研發室、制造室和休息室，L1則進一步描述制造室的功能布局。

1.1.2復合地圖架構

首先，通過機器人操作系統(robot operating system，ROS)軟件gmapping功能包將移動機器人作業環境描述為柵格地圖形式。然后，利用層次圖將全局柵格地圖劃分為若干個不同層次的子地圖，且每個子地圖均設置關鍵節點，同一層次的關鍵節點間通過離線路徑(邊)連接，具有明顯拓撲特征，進而構建拓撲地圖。柵格地圖中，某物體的坐標通常由它占據柵格的中心點坐標替代，這種表示方式的精度有限，因此，移動機器人在運行過程中利用激光雷達和慣導系統等傳感器維護局部度量地圖，實現更高精度的位置表示。由此建立了一種拓撲-柵格-度量復合地圖，如圖2所示。

圖2 拓撲-柵格-度量復合地圖Fig.2 Hybrid topological-grid-metric map

圖3展示了面向復合地圖的分層路徑規劃架構。拓撲地圖反映了關鍵節點之間的空間位置關系，利用Floyd算法規劃最優點集序列，確保起點所在子地圖的關鍵節點到終點所在子地圖的關鍵節點之間的區間路徑是離線最優的。將關鍵節點代表的子地圖內部展開為柵格地圖，提出改進A*算法進行內部路徑的局部規劃。度量地圖利于移動機器人精細化描述周圍環境，提出改進深度確定性策略梯度(deep deterministic policy gradient, DDPG)算法進行機器人的避障規劃。

圖3 面向復合地圖的分層路徑規劃架構Fig.3 Hierarchical path planning architecture forhybrid map

1.2 分層路徑規劃方案

分層路徑規劃方案的流程如圖4所示，主要分為兩個步驟：首先在拓撲-柵格地圖上規劃出一條全局優化初始路徑;然后移動機器人沿初始路徑在行駛過程中實時檢測其周圍環境并維護局部度量地圖，若離機器人最近障礙物距離小于避障閾值，則運行針對度量地圖的改進DDPG算法進行避障路徑規劃。

圖4 復合地圖分層路徑規劃流程Fig.4 Procedure of hierarchical path planning forhybrid map

分層路徑規劃的處理流程如下：

(1)在柵格地圖上采用細化算法生成離線先驗路徑，提取拓撲特征完畢后，構造拓撲地圖并完善層次圖。

(2)判斷起始柵格S和目標柵格D是否處于同一子地圖中，即判斷是否隸屬于層次圖的同一節點，若是則直接利用改進A*算法規劃出S到D的優化路徑即為全局優化初始路徑，轉至步驟(6)；否則轉至步驟(3)。

(3)分別獲取S和D在層次圖中的深度LS、LD及它們所在子地圖的關鍵節點CS、CD，若LS

(4)以S為起點，CS為終點，利用改進A*算法在S所在子區域的柵格地圖上搜索出一條局部路徑并保存。同理，將CD設為起點，D設為終點，規劃出另一條局部路徑并保存。若無法搜索出可行解，則路徑規劃失敗，算法結束。

(5)將步驟(3)生成的起始關鍵節點和目標關鍵節點之間的離線先驗路徑和步驟(4)搜索到的S和D所在子地圖的局部路徑合并，得到全局優化初始路徑。

(6)機器人沿著初始路徑行進時，一旦機器人離最近障礙物的距離小于避障閾值，利用改進DDPG算法完成避障后重新回到初始路徑；直到機器人到達目標位置D，算法終止。

2 拓撲-柵格分層全局路徑規劃

2.1 拓撲地圖最優先驗離線路徑規劃

拓撲地圖不易構建，原因在于拓撲特征(節點)的定義和識別難度較大。本節將利用細化算法生成離線先驗路徑，以選取拓撲特征，構建拓撲地圖。在此基礎上還研究了離線路徑點集序列的優化方法，最終生成最優先驗路徑。

2.1.1離線先驗路徑生成

細化算法[21]是圖像處理中常用的方法，能夠有效提取原圖像形狀的拓撲結構。二維柵格地圖由“0”和“1”組成，可以視為一幅二值化圖像，通過細化算法將自由柵格區域細化，最終生成安全路徑。需要注意的是，細化算法處理的是值為1的像素，故處理時需把自由柵格視為“1”，障礙柵格視為“0”。

細化算法的主要思想是：檢查圖像中某一像素是否符合刪除的條件，一旦滿足立即刪除該像素(像素值由1變為0)，重復迭代上述過程直到無法繼續刪除為止。檢查像素p1時建立圖5所示的3×3窗口，將p1作為中心單元，并判斷周圍的8鄰域是否滿足細化條件。每次迭代分為如下兩個步驟：

(1)2≤B(p1)≤6；A(p1)=1；p2×p4×p6=0；p4×p6×p8=0；

(2)2≤B(p1)≤6；A(p1)=1；p2×p4×p8=0；p2×p6×p8=0。

其中，B(p1)表示p1周圍8鄰域中數值為1的個數；A(p1)表示以順時針方向統計p2,p3,p4,…,p8,p9,p2數值從0變為1的次數。步驟(1)和步驟(2)交替進行，只有步驟(1)或步驟(2)中所有條件同時滿足，p1才能被刪除。

圖5 細化算法窗口Fig.5 Window of thinning algorithm

2.1.2拓撲特征提取

柵格地圖經過細化算法后會生成較為簡潔的離線先驗路徑，該路徑存在明顯拓撲特征，利于構建拓撲地圖。首先，人工選取區域入口柵格或其他具有代表性的柵格作為子地圖的關鍵節點；其次，提取路徑的分岔點作為拓撲圖中的普通節點；最后，統計連接相鄰節點的邊所占據的柵格數作為邊的權。每個節點存儲自身編號和所有與之相連的節點編號及該拓撲邊的權重，拓撲特征提取完畢后構建各層次對應的拓撲地圖。

圖6 拓撲特征提取示例Fig.6 Example of topological feature extraction

圖6展示了按以上規則提取出來的拓撲特征，圖中黑色柵格為障礙物，白色柵格為自由空間，灰色柵格為細化算法生成的離線先驗路徑，紅色方形為關鍵節點，藍色圓點為普通節點。

2.1.3優化離線路徑點集序列

拓撲地圖包含關鍵節點、普通節點和連接節點的邊，是一張帶權的路徑網絡圖，從起始節點出發可以有多條路徑到達目標節點。機器人路徑規劃期望路徑長度盡可能地短，因此拓撲地圖上的路徑規劃問題等價于在帶權圖中尋找起點到終點的最優點集序列問題。本文選用Floyd算法在帶權圖中求取多源點之間的最短距離。由于Floyd算法作用于拓撲地圖，而拓撲地圖又是對環境的高度抽象，局部細微的變動對拓撲結構影響不大，因此真實環境的細微變化不必在拓撲地圖上頻繁調用Floyd算法。

2.2 基于柵格地圖的改進A*算法

A*算法通過包含啟發信息的代價函數來搜索最優路徑，代價函數f(n)由兩部分組成：起點沿著已生成的路徑到達當前節點的開銷g(n)和當前節點到終點的預估開銷h(n)，可表示為

f(n)=g(n)+h(n)

(1)

A*算法建立并維護兩個列表：存放已經探測到但還未訪問節點的Open列表和存放已經訪問過節點的Close列表。初始化時只包含起點，Close初始化為空。從起點開始，遍歷周圍8鄰域節點，若該節點在Open表中不存在，則加入至Open，否則判斷是否需要更新Open表中該節點的代價。然后從Open表中彈出代價值最小的節點，同時移入Close表，以該節點為路徑當前節點繼續向目標點拓展，重復以上過程直至Open表為空或搜索到終點。路徑上每個節點都有一個指向父節點的指針，通過跟蹤指針向前回溯即可找到最佳路徑。

標準A*算法在擴展節點時比較盲目，可能將多余節點加入Open表，增加了維護Open表代價的同時擴大了搜索空間，導致算法在大范圍空間下的搜索效率不夠理想。此外，規劃出來的路徑拐點較多，不利于移動機器人跟蹤。針對以上問題，對A*算法進行改進，如圖7所示。本文采用雙向搜索機制，同時開展從起點向終點的正向搜索和從終點向起點的反向搜索，逐步生成路徑節點向中間靠攏；在擴展過程中依據方向信息對候選的節點進行篩選，過濾掉一些無效節點，提高搜索效率；最后對生成的路徑進行修飾，刪除冗余點，提高路徑質量。

圖7 改進A*流程圖Fig.7 Flow chart of improved A* algorithm

2.2.1篩選擴展點

圖8展示了A*算法擴展過程，其中S為起始位置，m為被擴展到的節點，D為目標位置。路徑規劃期望路徑長度盡可能地短，即路徑方向盡可能貼合起點指向終點的方向SD。θ為當前節點到終點的方向mD與期望方向SD的角度偏差，可表示為

(2)

|θ|越小，節點m被加入Open表的可能性越大。

圖8 A*算法擴展過程Fig.8 Extension process of A* algorithm

式(2)中涉及反三角函數運算，在實際運用過程中會占用較多算力。為了簡化擴展節點和預期路徑符合程度的表示，同時放大各擴展節點之間的這種差異，本文選用圖8中綠色矩形面積來引導路徑規劃過程。以m為原點分別向標準坐標系的X軸和Y軸延伸，并與邊SD、DT相交于兩點，可構成一個矩形，矩形面積φ(m)可表示為

(3)

φ(m)越小，當前被擴展到的節點和預期路徑符合程度越高，越有機會加入Open表中繼續擴展。設置面積閾值φ0，當φ(m)>φ0且滿足p(m)>p0時(其中p(m)為隨機概率，p0為信任閾值概率)，忽略當前被擴展的點m，重新選擇新的擴展點。其余情況對m的處理方式和標準A*算法保持一致。通過引入方向指引信息，有一定概率忽略方向性不強的節點，進而減少了Open表中候選點的個數，縮小了算法的搜索空間。

2.2.2剔除冗余點

雖然上述改進步驟能夠有效規劃出一條路徑，但依舊遵從8鄰域擴展，即以45°為分辨率選擇下個柵格，該方式生成路徑會存在較多拐點，且并不一定是最優路徑，故改進路徑生成策略。首先在前文獲得的初始路徑中每對相鄰節點距離二等分處插入新節點。然后將所有節點按起點指向終點方向從小到大編號，從終點向前搜索是否有可以略過的冗余點。當兩節點連線經過障礙物時，則說明編號小的節點無法被刪除，否則即可刪除。重復以上過程直到搜索到起點，最后按順序連接剩余的節點，如圖9所示，其中虛線即刪除冗余點后的路徑。

圖9 刪除冗余點后的路徑Fig.9 Path after removing redundant points

3 度量地圖局部路徑規劃

當移動機器人沿全局優化初始路徑運行時，針對部分未知場景中的動態障礙物，研究了基于深度強化學習的避障路徑規劃方法，其研究方案如圖10所示。移動機器人負責將自身感知到的狀態數據輸送至Actor網絡中，經過基于價值分類經驗回放機制的深度確定性策略梯度(deep deterministic policy gradient based on value-classified experience replay, VCER-DDPG)算法決策后，控制器輸出信號指導機器人做出相應動作。

圖10 基于VCER-DDPG算法的局部路徑規劃框架Fig.10 Local path planning framework based on VCER-DDPG algorithm

VCER-DDPG算法的核心由兩部分組成：價值分類經驗回放池和Actor-Critic網絡架構。價值經驗回放池主要負責存儲訓練過程中產生的經驗樣本，并按一定的采樣策略抽取部分樣本用于訓練。Actor稱為策略網絡，完成狀態空間到動作空間的映射；Critic稱為價值網絡，使用價值函數對Actor輸出的動作進行評價，指導Actor改進策略。為降低損失函數震蕩發散概率，提高算法的穩定性，Actor和Critic均采用雙重神經網絡架構，即在線網絡(online)和目標網絡(target)。VCER-DDPG算法共包含4個深層神經網絡，即

(4)

(5)

其中，μ、μ′分別為online動作策略函數和target動作策略函數；θμ、θμ′分別為online Actor和target Actor網絡參數；Q、Q′分別為online價值函數和target價值函數，θQ、θQ′分別為online Critic和target Critic網絡參數；S為狀態，時間步為t時的狀態表示為St。VCER-DDPG訓練的本質是利用深度學習更新優化Actor和Critic的網絡參數，最終獲得能應對復雜避障問題的online Actor網絡。

完整的局部路徑規劃過程如下：首先，激光雷達的距離點云數據、機器人當前位姿、目標位姿被合并成一維狀態數組St，在線策略網絡依據狀態St生成動作μ(St)，疊加行為策略β后得到機器人最終執行的動作at。動作at由線速度和角速度組成，機器人控制器將at轉化為實際控制信號，執行完畢后到達新的狀態St+1。環境判斷當前回合是否結束，同時利用獎勵函數對動作at進行評價，給出獎勵值rt。這一過程產生的經驗樣本(St，at，rt，St+1，done)由價值分類經驗回放池進行存儲。模型訓練時，根據分層采樣策略從經驗回放池抽取小批量樣本送入Actor和Critic網絡進行訓練，重復上述過程直到模型網絡收斂至最佳避障策略。

3.1 價值分類經驗回放池

原始經驗回放機制采用等概率采樣，未區分經驗樣本的價值，重復學習簡單樣本對網絡指導效率有限，網絡收斂速度較緩慢，因此，在訓練過程中根據樣本價值，將經驗樣本分類存放至不同的子經驗回放池中。制定合適的樣本價值衡量標準是對經驗樣本進行分類的前提，大多數強化學習算法采用時間差分誤差δ作為狀態值函數的估計，|δ|越大，向預期動作值的校正就越積極，因此δ很大程度上與樣本的學習價值相關聯。十分成功和失敗的經驗樣本通常擁有較高的|δ|，重復回放這類樣本能夠及時審視當前策略的學習效果，加快網絡收斂，提高訓練效率。然而訓練初期，對環境的探索有限，策略還未成熟，在狀態空間的邊緣也可能出現較大的|δ|，可能改變網絡的收斂方向，僅僅依據時間差分誤差δ無法準確衡量樣本價值。從短期來看，獎勵值r直接表現了動作的好壞程度，高獎勵值樣本在訓練初期具有學習價值。本文將時間差分誤差δ和獎勵值r結合起來，制定了價值衡量方法，其表達式為

Vj=α|rj|+(1-α)|δj|

(6)

δj=rj+γQ′(Sj+1,aj+1;θQ′)-Q(Sj,aj;θQ)

(7)

其中，Vj為樣本j的價值，|rj|為樣本j的獎勵值的絕對值，γ∈(0,1]為獎勵值折扣因子，α為|rj|的權重，|δj|為樣本j的時間差分誤差的絕對值，(1-α)為|δj|的權重，α隨著訓練過程動態更新。訓練初期α取1，主要利用獎勵值引導智能體快速學習策略，隨著訓練深入，時間差分誤差δ能更好地指導策略更新，α逐漸減小以提高δ的權重。

價值分類經驗回放池的結構如圖11所示，分別由存放高價值樣本的子回放池B1、存放近期樣本的子回放池B2、存放普通樣本的子回放池B3組成。子回放池均采用隊列作為存儲容器，新樣本從隊尾插入，容量達到上限時從隊頭彈出樣本。

圖11 價值分類經驗回放池結構Fig.11 Structure of value-classified experience replay pool

價值分類經驗回放池的構建步驟為：初始化時設置B1、B3兩個子回放池中所有樣本價值的平均值Vm為0，同時將獎勵值的權重系數α設為1，訓練過程中每產生一條樣本先加入B2隊尾，若B2達容量上限則從隊頭彈出一個樣本，并計算該樣本的價值，若高于Vm則將該樣本添加至B1，反之存入B3。存儲完畢后，更新Vm和α，重復以上過程直至訓練結束。

為了保證采樣所得樣本的時效性和多樣性，本文設計了分層采樣策略，分別從B1、B2、B3子回放池中隨機抽取適量樣本。記小批量采樣總數為N，包括子回放池B1采樣數N1、子回放池B2采樣數N2、子回放池B3采樣數N3，即

N=N1+N2+N3

(8)

其中，N2為固定值，確保每次小批量采樣均有近期樣本，該類樣本具有時效性，有助于及時調整網絡收斂方向。訓練初期，N1取較大值，通過選取大量高質量樣本來促進網絡朝正確方向收斂。隨著訓練推進，策略網絡的成熟，機器人表現越發優異，高價值樣本出現頻率越來越高，為避免過擬合，應適當降低N1、提高N3。

3.2 VCER-DDPG算法流程

VCER-DDPG的算法偽代碼如下：

4 實驗分析

為了驗證本文所提方法的有效性，將采用計算機軟件仿真與機器人樣機實驗相結合的手段，分別在C++開發環境下進行全局路徑規劃仿真實驗；然后在Gazebo仿真引擎中驗證所提局部路徑規劃算法的避障性能；最后在真實場景中驗證本文所提復合地圖分層路徑規劃方法的有效性。

4.1 全局路徑規劃仿真實驗

本次實驗的環境由100×100個網格組成，每個網格邊長為10像素，黑色柵格為障礙物，白色柵格可自由通行。實驗選擇標準A*算法、蟻群算法作為對比算法，以驗證拓撲-柵格地圖分層路徑規劃方法的性能，實驗參數設置如表1所示。

表1 全局路徑規劃仿真實驗參數

每種方法分別進行了3次路徑規劃任務，圖12所示為采用標準A*算法進行路徑規劃的結果，圖13所示為由蟻群算法規劃獲得的路徑，圖14所示為本文分層規劃方法生成的路徑。圖12～圖14中紅色線條是算法生成的最終路徑，灰色部分為初始路徑或離線路徑，算法搜索過的柵格(可反映規劃算法的計算量)會被標記為綠色。

從圖12、圖13中可以看出，標準A*算法和蟻群算法生成的路徑安全性不高，部分路段長距離貼合障礙物，機器人沿路徑行走時較易發生碰撞。此外，算法在搜索過程中缺少方向性引導，搜索空間較大，路徑擺動較為明顯，不利于機器人運動控制。由圖14可知，基于拓撲-柵格地圖的分層路徑規劃方法利用細化算法可生成安全度較高的離線先驗路徑，同時在子地圖內部運用改進A*算法時，對目標點的搜索更具有方向性，路徑拐點更少，利于機器人控制。

(a)任務1 (b)任務2 (c)任務3圖12 標準A*算法生成路徑Fig.12 Path generated by the original A* algorithm

(a)任務1 (b)任務2 (c)任務3圖13 蟻群算法生成路徑Fig.13 Path generated by the ACO algorithm

(a)任務1 (b)任務2 (c)任務3圖14 分層路徑規劃算法生成路徑Fig.14 Path generated by the hierarchical path planning algorithm

為了通過量化性能指標對比分析三種路徑規劃方法的性能，對上述實驗過程的路徑長度、危險柵格數(經過障礙柵格周圍8鄰域)、搜索柵格數、運行時間進行統計，實驗數據如表2所示。從表2中數據可知，相比標準A*算法，拓撲-柵格分層路徑規劃方法的路徑長度平均增大了4.89%，但危險柵格數減少了42.99%，搜索柵格數減少了80.20%，運行時間縮短了91.75%；相比蟻群算法，拓撲-柵格分層路徑規劃方法的路徑長度平均增大了11.1%，但危險柵格數減少了50.5%，搜索柵格數減少了84.8%，運行時間減少了4個數量級。綜合以上實驗數據可以發現，本文所提的拓撲-柵格分層路徑規劃方法顯著縮小了算法的搜索空間，極大提高了搜索效率，最終生成的路徑兼具安全性和平滑度，能夠有效解決復雜大場景環境下的路徑規劃問題。

表2 全局路徑規劃實驗數據

4.2 避障仿真實驗

為了驗證VCER-DDPG避障路徑規劃方法的有效性，首先結合ROS軟件和TensorFlow框架進行DDPG深度學習程序的開發，并根據表3中的參數進行訓練，訓練完畢后，可通過加載模型網絡參數以應用最終習得的避障策略。然后，在Gazebo軟件中設計一個混合障礙場景：方形立柱充當靜態障礙物，圓柱體以0.4 rad/s速度逆時針旋轉充當動態障礙物。移動機器人在該場景中依次到達5個指定目標點記作成功，否則記為失敗。

表3 訓練超參數

實驗過程中，使用了較為成熟的move_base導航功能包作為對比算法，分別對采用VCER-DDPG算法和move_base算法的機器人進行15次測試，統計成功率、路徑長度、行駛時間等性能指標(其中路徑長度和行駛時間只統計導航成功的測試數據)。兩種方法的機器人運行軌跡如圖15所示，實驗數據如表4所示。

(a)VCER-DDPG的軌跡 (b) move_base的軌跡圖15 動態避障的仿真軌跡Fig.15 Simulation trajectories of dynamicobstacle avoidance

表4 動態避障的實驗數據

由實驗結果可見，move_base功能包由全局路徑規劃器A*算法和局部路徑規劃器DWA算法構成，不易陷入局部最優，故move_base方法規劃的路徑長度更短。然而，復雜的決策機制同時可能會導致短期無可行解時機器人在原地等待，直至出現可行解。該行為也導致平均行駛時間稍長，甚至路徑規劃失敗。而本文所提的深度強化學習算法是端到端的方法，根據狀態直接輸出動作，決策迅速，面對障礙主動進行避障，雖然犧牲了一些路徑長度性能，但具有較高實時性且避障成功率更高，更適應動態未知環境。

4.3 復合地圖分層路徑規劃實驗

真實場景實驗中采用的移動機器人平臺如圖16所示。該機器人采用差速驅動方式，前面有兩個主動輪，后面兩個萬向輪作為從動輪，并安裝有多種進行環境/機器人狀態感知的傳感器，包括用于建圖和定位的倍加福R2000激光雷達、用于探測周圍障礙物的RPLIDARA2激光雷達、加速度計、陀螺儀模塊等。

圖16 移動機器人平臺Fig.16 Mobile robot platform

為了模擬大范圍的工作空間，本次實驗由一個400 m2的實驗室和50 m長的走廊及若干個房間組成，實驗環境如圖17所示。R2000激光雷達安裝高度為60 cm，部分物體未被掃描到，建圖時無法獲取這些物體信息，對全局路徑規劃可能產生一定影響。然而，RPLIDARA2激光雷達的安裝高度為46 cm，能夠保證掃描到大多數障礙物，機器人運行過程中將建圖時未能探測的物體視為障礙物從而采取避障策略。

(a)實驗室

機器人平臺基于ROS開發，具體步驟如下：首先配置系統環境，包括搭建分布式通信網絡，利用SSH協議從遠程端登錄機器人主機，運行rviz工具；然后運用gmapping功能包建立整體環境的柵格地圖，為后期定位和路徑規劃做準備；再者利用ROS插件機制，將move_base框架中的全局和局部路徑規劃器分別替換為本文所提的拓撲-柵格路徑規劃方法和VCER-DDPG局部路徑規劃方法；最后機器人運行基于move_base和amcl的導航算法，并通過筆記本上的rviz工具選取目標點，進行導航實驗。

本次導航實驗的運行軌跡如圖18所示，其中紅色圓圈處是機器人所處的初始位置，綠色箭頭的末端是目標位置，機器人導航過程中的實際運行軌跡如圖中的藍色線條所示。在實驗室和房間的門口設置關鍵節點，在它們內部主要由改進A*算法生成局部路徑，在保證安全的前提下以路徑最短為優化目標，因此路徑相對徑直。而走廊用于連接實驗室和房間，機器人由離線路徑引導，故軌跡更靠近區域中心。由圖18可知，機器人絕大多數時間都沿著全局優化初始路徑運行，當激光雷達探測到建圖時未掃描到的障礙物或突然出現的障礙物時會自主進行局部路徑規劃。

圖18 導航實驗Fig.18 Navigation experiment

以圖18中橙色線段分析主要的避障過程，圖19通過時間序號的形式展現了各時刻機器人和行人的位置。面向衛生間走動的行人和長方體紙箱分別充當動態和靜態的障礙物。記最近障礙物相對機器人前進方向的角度為ao，位于左側的障礙物ao∈[-60°,0)，位于右側的障礙物ao∈(0,60°]；記最近障礙物相對機器人的距離為do。這兩個指標作為狀態空間的組成部分，很大程度上影響了機器人的避障策略，故表5列舉了不同時刻下的ao和do，并結合線速度v和角速度ω的變化情況(圖20)來分析避障過程。

圖19 避障過程Fig.19 Obstacle avoidance process

由圖20可以看出，開始時，機器人沿初始路徑向前行駛，在t=1.7 s時，探測到右前方行人，為避免發生碰撞，角速度迅速調整為負值，向左前方避障；t=3 s時，行人位于機器人右前方0.56 m處，由于距離較近，隨即減小線速度，等待行人通過；t=4 s左右，行人位于機器人左前方，且已穿過走廊大半，基本不再產生干擾，機器人提高線速度的同時降低角速度幅值，并減小左拐的幅度；t=5.4 s時，紙箱成為主要避障目標，角速度變為正值，向右側避障；t=9 s時，機器人即將繞過紙箱，同時位于走廊中間，角速度穩定在0附近，徑直向前行駛。避障完成，回到初始路徑上，最終安全、準確地到達目標點。

表5 避障路段的實驗數據

圖20 避障線速度和角速度Fig.20 Linear velocity and angular velocity duringobstacle avoidance

真實場景下的移動機器人路徑規劃實驗結果表明，本文所提的復合地圖分層路徑規劃方法在實際場景應用中也具有較好的效果。

5 結語

針對部分未知復雜大場景環境，提出一種基于拓撲-柵格-度量復合地圖的移動機器人分層路徑規劃方法。首先采用層次圖思想，將機器人作業環境劃分為多個以柵格表示的子地圖，并建立多個子地圖的拓撲架構及局部區域的精細化描述模型。其次，在不同地圖層級上分區域搜索機器人路徑，在拓撲地圖上采用Floyd算法規劃子區域之間的區間路徑，面向柵格地圖提出搜索子區域內部路徑的改進A*算法，針對動態障礙物在度量地圖上提出VCER-DDPG避障路徑規劃方法。最后，采用計算機軟件仿真與機器人樣機實驗相結合的手段，驗證了所提分層路徑規劃方法的有效性，路徑搜索效率和避障成功率有明顯提高，生成的路徑兼具安全性和平滑性。