無人快遞機器人路徑規劃算法研究綜述

陳鍵CHEN Jian

（重慶交通大學，重慶400074）

0 引言

近年來，隨著互聯網的發展，智能手機的普及，短視頻平臺的發展與直播帶貨的推廣，電子商務規模日益龐大，網購已然成為人們生活中不可缺少的一環。根據中國報告大廳對2020 年1-12 月全國快遞量進行監測統計顯示：2020 年全國快遞量8335789.42 億件，我國快遞體量穩居世界第一。快遞員增長率較包裹增長率較低，快遞業亂象層出不窮——不送貨上門、暴力分揀、快遞掉件、用戶隱私泄露等。為解決快遞行業“最后一公里”亂象，提高用戶體驗，減輕快遞員勞動壓力，眾多國內外公司投入到無人快遞機器人的研發生產[1]。

對無人快遞機器人的安全性、高效性、可行性而言，路徑規劃技術顯得尤為重要。無人快遞機器人應具備在復雜的社區環境中從起始位置抵達目標位置的能力，此路徑應具備耗時少、行駛安全、高效率等特點。并對沿途的動態與靜態障礙物做出決策，具有躲避動態障礙物與繞行靜態障礙物的能力，同時應實時監測當前已規劃路線是否堵塞，是否發生事故，當前客戶是否取消取件需求，若發生變故，應具備重新規劃路徑的能力，合理的路徑規劃不但能提高無人快遞機器人的效率、續航、安全性、使用壽命等，還能減少成本[2]。本文對無人快遞機器人的路徑規劃進行分類總結，剖析各個算法的優缺點，為研究無人快遞機器人的學者提供參考。

1 路徑規劃算法的分類

1.1 基于幾何模型算法

在復雜環境下，針對外形不一的障礙物，建立外凸多邊形包裹模型，無人快遞機器人采取合適的路徑繞過障礙物的包裹模型，此方法得到的路徑較為平滑，能減少無人快遞機器人與障礙物的碰撞。

A*算法是一種啟發式算法，啟發信息強，變化靈活，可以降低搜索工作量，能用于各式各樣的環境，在路徑規劃中廣受歡迎。基本原理：A*算法搜索路徑由其估值函數引導方向，A*算法主要由已訪問列表與待訪問列表組成，列表內每個節點都要存儲其父節點，后面生成鏈路時會用到這個父節點，找到開始節點附近節點，加入到待訪問節點，并且選擇代價最小節點進行優先訪問計算，并且記錄已訪問節點位置信息和父節點信息到已訪問列表中，然后將找到這個節點附近的節點，計算代價值。碰到障礙節點，將其排除在外，不參與計算，如果碰到相同代價值節點，隨機選擇一個節點走下去，若選擇的那一條路徑中的節點總代價值大于另一路徑，則先放置此路徑到待訪問列表，換另一總代價值小的路徑，所以算法總會從等待隊列找最小代價的節點訪問，這樣的路徑是最優的，以此類推，將走到最終目標節點，然后我們根據最后找到的目標節點的父節點，一級一級往回找，直到找到最開始節點，各節點連起來的路徑就是最終路徑。

f*（n）表示從起始點到目標點途中n 點的估值函數，g*（n）表示從起始點到 n 點的已用成本，h*（n）表示從當前n 點到目標點的啟發式估計成本。

A*算法較為完備，得出的解較好，但此算法較為復雜，難以用于障礙物移動的情況。為解決此問題，趙曉[3]等人將跳點搜索算法結合A*算法，優化在搜索過程中的搜索策略，A*算法是挑出周圍所有節點進行估值擴展，而跳點搜索算法選擇出具有代表性的跳點進行估值擴展。劉子豪[4]等人將反向搜索算法與跳躍點搜索算法相結合，優化傳統A*算法用于路徑規劃時出現的冗余點過多問題和拐點過多問題，林俊等人提出針對L 型路徑環境的改進A*算法，優化路徑規劃中存在的轉折問題，減小了轉彎次數與轉彎角度，提升了無人快遞機器人的安全性[5]。

1.2 基于局部避障算法

局部避障算法相對于全局避障算法更為靈活，全局避障算法多為靜態環境下的避障，而局部避障算法多考慮動態障礙物的出現，無人快遞機器人結合局部避障算法能減少碰撞，使行走更為安全。

1.2.1 人工勢場法

將無人快遞機器人在環境中的路徑規劃問題，虛擬為在人工勢場中的運動問題。目標位置對無人快遞機器人有著“吸引力”，環境中的障礙物對無人快遞機器人有著“排斥力”，無人快遞機器人在兩種力的合力下改變運動軌跡，使無人快遞機器人行走于無障礙路徑，人工勢場法結構簡單，能實時躲避障礙物，路徑較為平滑且安全。但在復雜環境時，會陷入局部最優，在狹窄環境中易產生劇烈震蕩。基本原理如圖1。

圖1 人工勢場法原理圖

陳曉娥等人[6]提出一種基于地圖柵格化的路徑規劃算法，提前將已知環境柵格化，用分區算法構建地圖模型。在分區中采取VORONOI 圖算法與深度優先算法和Dijkstra算法結合，最終得到無人機器人在分區內的最終路線，通過仿真實驗，驗證了該方法的可行性，該方法能使機器人行進路徑縮短，適用于任意形狀障礙物。李二超等人[7]針對人工勢場法在全局路徑規劃在多障礙物環境下易陷入狹窄區域與局部最小點問題，提出一種簡化障礙物預測碰撞人工勢場法，該方法提出簡化障礙物模型，引入預測碰撞思想，通過仿真并對比傳統方法，得出該方法解決人工勢場法在復雜環境，易陷入狹窄環境與局部最小點問題。

1.2.2 動態窗口法

一種基于速度空間的局部規劃算法，對當前周圍環境進行采樣，計算出無碰撞狀態下到達目標點的最佳速度，過于依賴全局數據，在未知環境中難以運用。

西安電子科技大學李文剛等人[8]針對動態窗口法與A*算法各自缺點，提出將兩種方法結合用于無人機器人路徑規劃的方法，通過仿真實驗，提出的方法比動態窗口法路徑短59%，比A*算法搜索路徑短21%，驗證了所提方法的優越性。哈爾濱工程大學原新等人[9]針對無人機器人在路徑規劃中動態避障與尋求最優路線問題，提出將動態窗口法與蝙蝠算法結合的方法，用于路徑規劃的混合規劃，該方法在蝙蝠算法部分引入柯西擾動與對數遞減策略，并將多個路徑指標作為適應度函數；在動態窗口法部分把全局路徑規劃的路徑節點作為局部目標點，將局部避障與全局避障結合。通過仿真實驗表明該方法將路徑變短，且實現了動態避障。

1.3 智能仿生算法

智能仿生算法是模擬自然界動物昆蟲覓食筑巢等行為與生物進化的智能算法。路徑規劃中常用的方法有神經網諾算法、蟻群算法、遺傳算法、粒子群算發、人工魚群算法、煙花算法以及灰狼化算法等。本文介紹其中幾種算法在無人機器人路徑規劃中的研究現狀與進展。

1.3.1 粒子群算法

粒子群算法是模仿鳥群在自然界的覓食行為，鳥群中的個體會互相分享自我的位置信息，個體與群體間的相互交流，最終使群體能鎖定食物所處位置，這種模仿鳥群覓食行為中個體與群體的信息交流而得到全局最優解的方法稱為粒子群算法。基本原理如圖2。

圖2 粒子群算法原理圖

江西理工大學巫光福等人[10]針對無人機器人在路徑規劃中使用粒子群算法出現的收斂緩慢，路徑不平滑等不足，通過改善粒子群算法，當粒子困于局部最優數值，對全局表現最優粒子速度的大小方向進行擾動，從而加快粒子的收斂速度。提出一個關于路徑平滑性和最短路徑的函數，且著重考慮非線性慣性的權重。通過仿真實驗測試，在動態變化環境中，改良的粒子群算法能及時躲避障礙物，且收斂速度快，所求路徑較優。重慶郵電大學胡章芳等人[11]探討在路徑規劃中使用單一算法時，大多算法易陷入局部最優解或陷入狹窄空間等問題，提出一種改進的粒子群算法，將粒子群算法，細菌覓食算法與遺傳算法相結合，針對粒子在不同環境中的關聯性將粒子群分兩類，并對各算法進行局部優化，對改進后的方法進行路徑規劃測試，驗證所提方法用于移動機器人路徑規劃，不僅耗時少，路徑短，魯棒性強，且全局和局部搜索能力提高。

1.3.2 蟻群算法

蟻群算法模仿自然界中螞蟻覓食行為，螞蟻覓食會派出多個螞蟻前往不同方向覓食，并在途中分泌信息素，不同螞蟻間的信息素可相互識別，螞蟻會調整到前往信息素高的方向覓食，大量螞蟻在食物所處路徑留下信息素，螞蟻會調整到信息素高的方向覓食，從而形成一個正反饋系統，經過反復迭代，最終形成覓食路徑。基本原理如圖3。

圖3 蟻群算法原理圖

廣西大學雷金羨等人[12]探討傳統蟻群算法易陷入局部最優問題，通過改進蟻群算法信息素更新階段不同路徑信息素的更新規則，著重更新最優路徑信息素，并在前期迭代搜索中增加一個獎勵機制，并在蟻群算法中加入順序插入策略，順序交換策略，2-opt 算法。將改進后的方法經過仿真測試，所提改進方法路徑的最優解優于改進前，驗證算法更優。華中科技大學馮振輝等人[13]探討傳統蟻群算法單一正反饋機制，導致易陷入局部最優與收斂緩慢問題，提出一種混合反饋機制的擴展蟻群算法，定義一種擴展性螞蟻，此螞蟻具有全局搜索能力。當遇見局部最優情況，此螞蟻能跳出局部最優，參照蟻群分工，加入刺激-響應分工負反饋機制，調節算法全局搜索與收斂能力，改進螞蟻信息素策略，從而改善蟻群算法收斂速度，經過仿真測試與實際實驗，此方法用于無人機器人路徑規劃時，相較于傳統蟻群算法具有優越性。

1.3.3 遺傳算法

遺傳算法參考生物進化總朝向適應環境的方向發展，將問題轉化為遺傳物質交叉變異問題，利用遺傳算子變異模擬進化，逐步進化適用于當前路徑規劃，此算法收斂快，實現簡單，多用于簡單地圖，在復雜地圖中表現較差。基本原理如圖4。

圖4 遺傳算法原理圖

山東科技大學王吉岱等人[14]探討當下無人機器人路徑規劃效率低下問題，提出一種改進模糊自適應遺傳算法，運用領域策略對起初路徑進行篩選，篩選出可行路徑，再采取模糊控制器調節遺傳算法，改良遺傳算法在路徑規劃中的擇優速度，在測評遺傳因子時，加入余弦函數平滑度。調節不同路徑夾角，進而使移動機器人路徑更平滑。通過仿真實驗驗證此方法比改進前更優。上海工程技術大學袁夢飛等人[15]探討快遞物流車行駛不規范，對物流車路徑規劃采取自適應精英遺傳算法。通過定位系統，實時監控車輛運行路線，在路徑規劃地圖上建立快遞物流點位置模型，建立適應函數匹配物流點位置經緯度坐標，以距離作為種群評價標準，引入自適應變異算子和自適應交叉算子，把精英個體通過遺傳算法保留，平衡算法全局優化與局部搜索能力，通過仿真對比試驗，驗證改進后的遺傳算法收斂快，精度高。

2 總結與展望

2.1 總結

本文主要講述無人快遞機器人路徑規劃常用算法優缺點，以及一些學者對相應算法的應用與改進，但大多數學者僅僅進行仿真實驗，并未實際應用。移動機器人路徑規劃不僅需要考慮全局路徑規劃，也要結合局部路徑規劃。室外環境復雜，不僅對移動機器人的路徑規劃算法有著高要求，對移動機器人的傳感器也是挑戰，要求機器人能對突發狀況進行處理，實現精確避障，且要求路徑短，轉彎平滑。

2.2 展望

隨著科學技術發展，快遞配送的“最后一公里”相對落后，無人快遞機器人的路徑規劃問題面臨許多挑戰[16,17]，無人快遞機器人路徑規劃在以下幾個方面還需提高：

①局部路徑規劃與全局路徑規劃相結合。全局路徑規劃一般是建立在已知環境信息的基礎上，適應范圍相對有限。局部路徑規劃能適應未知環境，但有時反應速度不快，對局部路徑規劃系統品質要求較高，因此，如果把兩者結合可達到更好的規劃效果。

②提高動態環境的處理能力。城市環境多為動態環境，路面移動物體復雜多變，考慮提高移動機器人自主性，優化移動機器人決策方案，結合5G 通信，提前獲取前方位置環境信息，提高移動機器人應急處理能力。

③多傳感器數據融合。移動機器人未能將攝像頭、激光雷達、溫度傳感器、姿態傳感器等數據完善處理。對于復雜環境，采用多傳感器信息融合，由于局部路徑規劃移動機器人在動態環境中進行路徑規劃所需的信息都是從傳感器獲得，因此單一傳感器難以保證輸入信息的準確性與可靠性，多傳感器所獲得的信息具有冗余性、互補性、實時性，無人快遞機器人若能將算法與多傳感器數據結合，可快速并行分析現場環境，提高效率與安全性。