施建壯，張國偉,，盧秋紅，黃 威，吳松林

（1.上海電力大學(xué)自動化工程學(xué)院，上海 200082；2.上海合時智能科技有限公司，上海 201100）

0 引言

隨著人工智能和物聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，服務(wù)機(jī)器人產(chǎn)品作為智能設(shè)備也在進(jìn)行智能化轉(zhuǎn)型升級，不斷實現(xiàn)更強(qiáng)大的功能和更豐富的應(yīng)用。作為服務(wù)機(jī)器人的一個分支，室內(nèi)移動配送機(jī)器人，實現(xiàn)了一鍵配送餐飲功能，代替很多原有的重復(fù)性勞動工作。在國內(nèi)外疫情爆發(fā)情況下，室內(nèi)移動配送機(jī)器人可以避免人員接觸引起的感染，實現(xiàn)既安全又高效的配送餐飲。并且該室內(nèi)移動機(jī)器人所應(yīng)用的智能導(dǎo)航技術(shù)能夠解決在商場、酒店、餐廳、會議室等不同場所時，遇到地毯或坡面等不平坦道路的運(yùn)行穩(wěn)定性和行走能力問題，環(huán)境或者人為因素發(fā)生改變后的適應(yīng)性問題等。

室內(nèi)移動配送機(jī)器人利用激光雷達(dá)進(jìn)行自主定位和構(gòu)建地圖，再通過導(dǎo)航算法實現(xiàn)機(jī)器人自主路徑規(guī)劃功能。全局路徑規(guī)劃是移動配送機(jī)器人實現(xiàn)自主導(dǎo)航的關(guān)鍵技術(shù)之一，路徑規(guī)劃目的是在機(jī)器人獲得所處環(huán)境的全局信息之后，按照一定評價標(biāo)準(zhǔn)（如轉(zhuǎn)彎次數(shù)、時間及代價等），尋找出一條從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最合適路徑。目前，路徑規(guī)劃算法已經(jīng)非常成熟，使用較多的有A算法、人工勢場法、Dijkstra算法、遺傳算法和蟻群算法等。

由于A算法的可塑性和移植性較強(qiáng)，被應(yīng)用于制造業(yè)、倉儲物流等領(lǐng)域。但傳統(tǒng)A算法存在拐點(diǎn)數(shù)量和遍歷節(jié)點(diǎn)較多、尋路時間較長等問題。目前，國內(nèi)外相關(guān)學(xué)者都對移動機(jī)器人全局路徑規(guī)劃方法展開了研究，且獲得一定的成果。本文以上海合時智能科技公司的室內(nèi)移動配送機(jī)器人作為研究硬件平臺，對移動機(jī)器人進(jìn)行室內(nèi)導(dǎo)航的研究。

1 路徑規(guī)劃算法

1.1 環(huán)境地圖的表示

機(jī)器人在路徑規(guī)劃前，要對所處環(huán)境進(jìn)行地圖構(gòu)建。按照維數(shù)，可將地圖劃分為二維和三維地圖。三維地圖能夠真實地展示外部環(huán)境，但也更容易被環(huán)境影響，且計算量大。二維地圖可以分成柵格、幾何地圖等。柵格地圖由Elfes和Moraves最先提出，將外部環(huán)境分成多個單元格，稱為柵格，用概率值表示柵格被占據(jù)的可能性。柵格地圖是對靜態(tài)環(huán)境的近似表征，易于創(chuàng)建和維護(hù)，因此本文采用柵格法來構(gòu)建地圖。柵格地圖中路徑規(guī)劃如圖1所示，白色表示可以通行的區(qū)域；黑色柵格表示障礙物。

圖1 柵格地圖

1.2 傳統(tǒng)A＊算法

A算法是在指定地圖上根據(jù)移動代價來找到最優(yōu)路徑的啟發(fā)式算法。其評價函數(shù)為：

式中，（）代表從起始節(jié)點(diǎn)經(jīng)過當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估算成本；（）代表起始節(jié)點(diǎn)到的實際成本；（）是A算法的啟發(fā)函數(shù)，代表當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估算成本；在傳統(tǒng)A算法中都會使用歐氏距離計算（）和（）。

式中，（x，y）是當(dāng)前節(jié)點(diǎn)坐標(biāo)，（，）和（x，y）分別是起始點(diǎn)和目標(biāo)點(diǎn)坐標(biāo)。（）大小可以決定A算法的搜索效率和搜索路徑的長短，（）的估值越小，A需要計算的節(jié)點(diǎn)越多，算法搜索的效率也就越低，當(dāng)（）趨于0時，A就變成了Dijkstra算法；但是當(dāng)（）估值遠(yuǎn)超（）或者（）等于0時，A就變成了最佳優(yōu)先搜索（BFS），此時算法只追求速度，不能得到最合適的路徑。

首先，在規(guī)劃路徑前需要定義兩個列表：一個是Openlist列表，用來存放即將要遍歷的節(jié)點(diǎn)；另一個是Closelist列表，用來存放已遍歷過的節(jié)點(diǎn)。在尋路過程中，先要挑出Openlist列表中代價最低的節(jié)點(diǎn)添加進(jìn)Closelist列表中，再把代價最低節(jié)點(diǎn)周圍的鄰節(jié)點(diǎn)添加進(jìn)Openlist列表中。與此同時更新起始節(jié)點(diǎn)到各節(jié)點(diǎn)的代價（）和各節(jié)點(diǎn)到目標(biāo)點(diǎn)的代價（），依次進(jìn)行迭代，直到目標(biāo)點(diǎn)加入了Openlist列表，尋路完成。傳統(tǒng)A算法尋路如圖2所示，黑色和白色分別表示不可通行和可通行區(qū)域，黑色線段表示路徑；表示起點(diǎn)、表示目標(biāo)點(diǎn)，淺灰色區(qū)域為規(guī)劃中遍歷的節(jié)點(diǎn)。

圖2 傳統(tǒng)A＊尋路

2 改進(jìn)A＊算法

傳統(tǒng)A算法存在遍歷節(jié)點(diǎn)和轉(zhuǎn)折點(diǎn)多，內(nèi)存消耗嚴(yán)重等問題。本文首先提出改進(jìn)啟發(fā)函數(shù)的計算方式，再結(jié)合選取關(guān)鍵點(diǎn)替換傳統(tǒng)A中Openlist和Closelist的兩個列表，剔除多余的冗余節(jié)點(diǎn)，尋找出一條更優(yōu)路徑。

2.1 改進(jìn)啟發(fā)函數(shù)

傳統(tǒng)的A通常是采用歐氏距離計算（），定義移動機(jī)器人是八個方向，因此歐氏距離計算出（）的代價值都小于當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的實際代價，從而導(dǎo)致尋路過程中遍歷的節(jié)點(diǎn)較多。

本文采用改進(jìn)曼哈頓距離計算函數(shù)，傳統(tǒng)曼哈頓距離是指兩個點(diǎn)在標(biāo)準(zhǔn)坐標(biāo)系上絕對軸距之和，其基本距離公式為：

兩種啟發(fā)函數(shù)仿真結(jié)果對比如圖3所示，歐氏距離函數(shù)遍歷節(jié)點(diǎn)數(shù)為75個，曼哈頓距離函數(shù)遍歷節(jié)點(diǎn)數(shù)是48個，大大提高了搜索效率。

圖3 兩種啟發(fā)函數(shù)仿真結(jié)果

2.2 結(jié)合JPS改進(jìn)A＊

在A算法規(guī)劃出路徑前采用JPS算法跳點(diǎn)搜索原理進(jìn)行預(yù)處理，JPS算法尋路可以分成兩個部分：第一是從Openlist列表中取一個最佳節(jié)點(diǎn)，從幾個特定方向進(jìn)行搜索，將各個方向得到的跳躍點(diǎn)加入Openlist中；第二部分就是找到一個跳躍點(diǎn)。對于起始點(diǎn)是向所有方向進(jìn)行搜索；對于其它節(jié)點(diǎn)，需要看父節(jié)點(diǎn)指向該節(jié)點(diǎn)的方向，再面向所有自然鄰節(jié)點(diǎn)和被迫鄰節(jié)點(diǎn)方向進(jìn)行搜索。

如圖4所示，節(jié)點(diǎn)周圍是無障礙物的，由于從父節(jié)點(diǎn)()出發(fā)到所有灰色擴(kuò)展節(jié)點(diǎn)的移動代價都小于或等于()經(jīng)過再到灰色節(jié)點(diǎn)，因此不用計算灰色節(jié)點(diǎn)，只用裁剪規(guī)則剪去灰色節(jié)點(diǎn)即可。

圖4 無障礙鄰節(jié)點(diǎn)

直線移動：

斜線移動：

如圖5所示，當(dāng)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)有障礙物時，就不能修剪灰色節(jié)點(diǎn)。如果每一條從()出發(fā)經(jīng)過節(jié)點(diǎn)后到達(dá)節(jié)點(diǎn)的路徑都比不經(jīng)過節(jié)點(diǎn)的路徑短，那么節(jié)點(diǎn)就是強(qiáng)制鄰節(jié)點(diǎn)，強(qiáng)制鄰節(jié)點(diǎn)的公式為：

圖5 障礙鄰節(jié)點(diǎn)

一個節(jié)點(diǎn)是否為跳點(diǎn)可以從三個方面來判斷：①節(jié)點(diǎn)是起點(diǎn)或終點(diǎn)；②節(jié)點(diǎn)在當(dāng)前搜索方向的前提下有強(qiáng)迫鄰居；③當(dāng)前搜索方向是斜向，且在節(jié)點(diǎn)處經(jīng)過該斜向的水平分量或垂直分量方向移動可以找到跳點(diǎn)，那么當(dāng)前節(jié)點(diǎn)是跳點(diǎn)。

3 仿真分析

在柵格地圖上模擬公司環(huán)境搭建仿真地圖，將前臺設(shè)置為室內(nèi)移動機(jī)器人的起點(diǎn)，收到送咖啡指令后將咖啡送到會議桌和展廳等不同的目標(biāo)點(diǎn)。在柵格地圖上通過采用改進(jìn)前后的A算法進(jìn)行對比，在CPU為i7-8565U@1.80Ghz的電腦上對其搜索路徑的效果進(jìn)行驗證。從圖6所示的仿真結(jié)果可以看出，改進(jìn)后的A算法拐點(diǎn)數(shù)量和尋路過程中遍歷的節(jié)點(diǎn)數(shù)都大大減少，并且在尋路時間上也有所改善。

圖6 改進(jìn)A＊前后仿真結(jié)果

表1列出了三組仿真結(jié)果中各項指標(biāo)的對比，改進(jìn)前后兩種算法路徑長度基本一樣，三條路徑的拐點(diǎn)數(shù)量相較于傳統(tǒng)A依次減少了50%、64%和60%，可以解決咖啡機(jī)器人運(yùn)送過程中拐彎次數(shù)多的問題；遍歷的節(jié)點(diǎn)數(shù)依次減少了75%、89%和89%，可以很大程度提高算法的搜索效率和內(nèi)存的占用率。

表1 仿真結(jié)果指標(biāo)對比

4 結(jié)語

針對傳統(tǒng)A算法在室內(nèi)移動配送機(jī)器人中存在轉(zhuǎn)折點(diǎn)和遍歷節(jié)點(diǎn)過多等問題，通過使用改進(jìn)曼哈頓作為啟發(fā)函數(shù)，即在傳統(tǒng)曼哈頓距離函數(shù)中允許對角移動，這樣既可以解決歐氏距離的路徑最短但運(yùn)行時間長和傳統(tǒng)曼哈頓距離搜索時間短但路徑不是最短的問題，再結(jié)合跳點(diǎn)搜索改進(jìn)A算法轉(zhuǎn)折點(diǎn)過多的問題，避免運(yùn)送過程中咖啡灑落和機(jī)器多次轉(zhuǎn)彎發(fā)生電機(jī)堵轉(zhuǎn)的問題，提高了室內(nèi)移動咖啡機(jī)器人導(dǎo)航中的路徑搜索效率，符合室內(nèi)移動機(jī)器人的實際運(yùn)用。