無(wú)人快遞機(jī)器人路徑規(guī)劃算法研究綜述

陳鍵CHEN Jian

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

0 引言

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

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

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

1.1 基于幾何模型算法

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

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

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ā)式估計(jì)成本。

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

1.2 基于局部避障算法

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

1.2.1 人工勢(shì)場(chǎng)法

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

圖1 人工勢(shì)場(chǎng)法原理圖

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

1.2.2 動(dòng)態(tài)窗口法

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

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

1.3 智能仿生算法

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

1.3.1 粒子群算法

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

圖2 粒子群算法原理圖

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

1.3.2 蟻群算法

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

圖3 蟻群算法原理圖

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

1.3.3 遺傳算法

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

圖4 遺傳算法原理圖

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

2 總結(jié)與展望

2.1 總結(jié)

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

2.2 展望

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

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

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

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