陳鍵CHEN Jian

（重慶交通大學(xué)，重慶400074）

0 引言

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

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

1 路徑規(guī)劃算法的分類

1.1 基于幾何模型算法

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

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

f*（n）表示從起始點(diǎn)到目標(biāo)點(diǎn)途中n 點(diǎn)的估值函數(shù)，g*（n）表示從起始點(diǎn)到 n 點(diǎn)的已用成本，h*（n）表示從當(dāng)前n 點(diǎn)到目標(biāo)點(diǎn)的啟發(fā)式估計成本。

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

1.2 基于局部避障算法

局部避障算法相對于全局避障算法更為靈活，全局避障算法多為靜態(tài)環(huán)境下的避障，而局部避障算法多考慮動態(tài)障礙物的出現(xiàn)，無人快遞機(jī)器人結(jié)合局部避障算法能減少碰撞，使行走更為安全。

1.2.1 人工勢場法

將無人快遞機(jī)器人在環(huán)境中的路徑規(guī)劃問題，虛擬為在人工勢場中的運(yùn)動問題。目標(biāo)位置對無人快遞機(jī)器人有著“吸引力”，環(huán)境中的障礙物對無人快遞機(jī)器人有著“排斥力”，無人快遞機(jī)器人在兩種力的合力下改變運(yùn)動軌跡，使無人快遞機(jī)器人行走于無障礙路徑，人工勢場法結(jié)構(gòu)簡單，能實時躲避障礙物，路徑較為平滑且安全。但在復(fù)雜環(huán)境時，會陷入局部最優(yōu)，在狹窄環(huán)境中易產(chǎn)生劇烈震蕩?；驹砣鐖D1。

圖1 人工勢場法原理圖

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

1.2.2 動態(tài)窗口法

一種基于速度空間的局部規(guī)劃算法，對當(dāng)前周圍環(huán)境進(jìn)行采樣，計算出無碰撞狀態(tài)下到達(dá)目標(biāo)點(diǎn)的最佳速度，過于依賴全局?jǐn)?shù)據(jù)，在未知環(huán)境中難以運(yùn)用。

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

1.3 智能仿生算法

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

1.3.1 粒子群算法

粒子群算法是模仿鳥群在自然界的覓食行為，鳥群中的個體會互相分享自我的位置信息，個體與群體間的相互交流，最終使群體能鎖定食物所處位置，這種模仿鳥群覓食行為中個體與群體的信息交流而得到全局最優(yōu)解的方法稱為粒子群算法?；驹砣鐖D2。

圖2 粒子群算法原理圖

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

1.3.2 蟻群算法

蟻群算法模仿自然界中螞蟻覓食行為，螞蟻覓食會派出多個螞蟻前往不同方向覓食，并在途中分泌信息素，不同螞蟻間的信息素可相互識別，螞蟻會調(diào)整到前往信息素高的方向覓食，大量螞蟻在食物所處路徑留下信息素，螞蟻會調(diào)整到信息素高的方向覓食，從而形成一個正反饋系統(tǒng)，經(jīng)過反復(fù)迭代，最終形成覓食路徑?；驹砣鐖D3。

圖3 蟻群算法原理圖

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

1.3.3 遺傳算法

遺傳算法參考生物進(jìn)化總朝向適應(yīng)環(huán)境的方向發(fā)展，將問題轉(zhuǎn)化為遺傳物質(zhì)交叉變異問題，利用遺傳算子變異模擬進(jìn)化，逐步進(jìn)化適用于當(dāng)前路徑規(guī)劃，此算法收斂快，實現(xiàn)簡單，多用于簡單地圖，在復(fù)雜地圖中表現(xiàn)較差。基本原理如圖4。

圖4 遺傳算法原理圖

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

2 總結(jié)與展望

2.1 總結(jié)

本文主要講述無人快遞機(jī)器人路徑規(guī)劃常用算法優(yōu)缺點(diǎn)，以及一些學(xué)者對相應(yīng)算法的應(yīng)用與改進(jìn)，但大多數(shù)學(xué)者僅僅進(jìn)行仿真實驗，并未實際應(yīng)用。移動機(jī)器人路徑規(guī)劃不僅需要考慮全局路徑規(guī)劃，也要結(jié)合局部路徑規(guī)劃。室外環(huán)境復(fù)雜，不僅對移動機(jī)器人的路徑規(guī)劃算法有著高要求，對移動機(jī)器人的傳感器也是挑戰(zhàn)，要求機(jī)器人能對突發(fā)狀況進(jìn)行處理，實現(xiàn)精確避障，且要求路徑短，轉(zhuǎn)彎平滑。

2.2 展望

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

①局部路徑規(guī)劃與全局路徑規(guī)劃相結(jié)合。全局路徑規(guī)劃一般是建立在已知環(huán)境信息的基礎(chǔ)上，適應(yīng)范圍相對有限。局部路徑規(guī)劃能適應(yīng)未知環(huán)境，但有時反應(yīng)速度不快，對局部路徑規(guī)劃系統(tǒng)品質(zhì)要求較高，因此，如果把兩者結(jié)合可達(dá)到更好的規(guī)劃效果。

②提高動態(tài)環(huán)境的處理能力。城市環(huán)境多為動態(tài)環(huán)境，路面移動物體復(fù)雜多變，考慮提高移動機(jī)器人自主性，優(yōu)化移動機(jī)器人決策方案，結(jié)合5G 通信，提前獲取前方位置環(huán)境信息，提高移動機(jī)器人應(yīng)急處理能力。

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