張麗麗，黃辰，杜宇飛

（沈陽(yáng)航空航天大學(xué) 民用航空學(xué)院，遼寧沈陽(yáng)，110136）

0 引言

隨著科技和經(jīng)濟(jì)的蓬勃發(fā)展，移動(dòng)機(jī)器人作為我國(guó)新興科技的重要產(chǎn)業(yè)被各行各業(yè)所大量應(yīng)用。目前，用途不同、型號(hào)不同的移動(dòng)機(jī)器人正在不同的應(yīng)用領(lǐng)域中有著越來(lái)越廣闊的應(yīng)用，我國(guó)移動(dòng)機(jī)器人市場(chǎng)也呈現(xiàn)出了迅速發(fā)展的勢(shì)頭。隨著移動(dòng)機(jī)器人技術(shù)的不斷發(fā)展，移動(dòng)機(jī)器人在導(dǎo)航和外賣(mài)物流等領(lǐng)域得到了迅速的發(fā)展，人們渴望更高效、運(yùn)營(yíng)成本更低廉、更省時(shí)省事的方式。移動(dòng)機(jī)器人具有交付效率高、靈活性強(qiáng)、實(shí)用性強(qiáng)、環(huán)境污染小等特點(diǎn)，并且移動(dòng)機(jī)器人可以通過(guò)自主執(zhí)行任務(wù)來(lái)降低人工成本。因此，掀起了移動(dòng)機(jī)器人物流時(shí)代的攻勢(shì)。

由于政府的大力推進(jìn)，使移動(dòng)機(jī)器人的導(dǎo)航技術(shù)取得了階段性的研究成果，降低了人工成本，但也帶來(lái)了以下挑戰(zhàn)：

(1)移動(dòng)機(jī)器人運(yùn)行時(shí)移動(dòng)的安全仍然面臨著嚴(yán)峻的挑戰(zhàn)。雖然移動(dòng)機(jī)器人的運(yùn)行在企業(yè)中的應(yīng)用越來(lái)越廣泛，但是復(fù)雜環(huán)境中物體的移動(dòng)受到的空間、各種障礙物的混合的制約，給移動(dòng)機(jī)器人的運(yùn)行安全帶來(lái)了很大風(fēng)險(xiǎn)，如移動(dòng)機(jī)器人與障礙物碰撞、移動(dòng)機(jī)器人在復(fù)雜地形運(yùn)行等問(wèn)題。

(2)移動(dòng)機(jī)器人運(yùn)行的效率。各類(lèi)設(shè)備的采購(gòu)成本仍然很高，導(dǎo)致了采購(gòu)成本的居高不下，缺乏合格的設(shè)備。因此，為了平衡移動(dòng)機(jī)器人本身的費(fèi)用，需要規(guī)劃出更快速、更高效的運(yùn)行路徑。但目前規(guī)劃的生成路徑可能在移動(dòng)中有很多轉(zhuǎn)折點(diǎn)、路線不夠平滑，在大規(guī)模搜索的情況下，大量計(jì)算會(huì)降低因操作效率等問(wèn)題導(dǎo)致的低運(yùn)營(yíng)效率。

(3)地形狀況對(duì)移動(dòng)機(jī)器人移動(dòng)姿態(tài)的影響。移動(dòng)機(jī)器人的體積較小，因此，地形因素對(duì)移動(dòng)機(jī)器人的使用的影響更大，例如，路面不平不僅會(huì)影響到移動(dòng)機(jī)器人靈活性與機(jī)動(dòng)性，還會(huì)影響移動(dòng)機(jī)器人的承載能力，使運(yùn)動(dòng)狀態(tài)造成威脅。

綜合上述幾種情況，為了有序、安全、高效、平穩(wěn)地運(yùn)行，移動(dòng)機(jī)器人的運(yùn)行路線需要獨(dú)立規(guī)劃，從合理避障的角度切入，針對(duì)突破路徑優(yōu)化過(guò)程中的技術(shù)難題，在保障安全運(yùn)行的前提下盡量提高效率，達(dá)到最大程度利用移動(dòng)機(jī)器人，降低運(yùn)輸成本。本文在傳統(tǒng)的A*算法規(guī)劃路徑的基礎(chǔ)上進(jìn)行一些改進(jìn)，提高運(yùn)行效率、減少轉(zhuǎn)折點(diǎn)、盡量使路線更加平滑、降低移動(dòng)機(jī)器人運(yùn)行風(fēng)險(xiǎn)，也減少了能源損耗。

1 構(gòu)建運(yùn)行環(huán)境模型

在復(fù)雜的環(huán)境中，移動(dòng)機(jī)器人的路徑規(guī)劃的第一要素是安全，安全的移動(dòng)才是實(shí)現(xiàn)一切行動(dòng)的前提，第二則考慮規(guī)劃出更短的移動(dòng)路徑，更短的路徑會(huì)讓移動(dòng)機(jī)器人的耗能和運(yùn)行時(shí)間變少。移動(dòng)機(jī)器人的障礙區(qū)域主要包括桌椅板凳、特殊地形等，根據(jù)障礙物的特點(diǎn)進(jìn)行簡(jiǎn)化，構(gòu)建適合移動(dòng)機(jī)器人運(yùn)行的環(huán)境模型地圖。移動(dòng)機(jī)器人在運(yùn)行時(shí)，可能會(huì)遇到因道路不平等地形威脅，需要考慮不同地形情況對(duì)規(guī)劃移動(dòng)機(jī)器人路徑的影響并保障其移動(dòng)安全。

規(guī)劃路徑的第一步是規(guī)劃運(yùn)行環(huán)境模型，通常使用的環(huán)境圖形的構(gòu)建方法有柵格法［1］、可視圖法［2］、拓?fù)鋱D法。根據(jù)移動(dòng)時(shí)的地形障礙物等特征構(gòu)建運(yùn)行環(huán)境模型，采用可視圖法模擬移動(dòng)機(jī)器人的移動(dòng)條件，可視圖法建立的環(huán)境模型簡(jiǎn)單，易于使用和維護(hù)，路線觀測(cè)較為直觀，因此建立適合移動(dòng)機(jī)器人運(yùn)行環(huán)境的三維地形圖。

(1)設(shè)置坐標(biāo)軸范圍為1到MAX_X，1到MAX_Y，1到MAX_Z，創(chuàng)建一個(gè)曲面圖，并將Z中元素的列索引和行索引用作x坐標(biāo)和y坐標(biāo)，以10為單位長(zhǎng)度對(duì)x軸和y軸進(jìn)行劃分，2000為單位長(zhǎng)度對(duì)z軸進(jìn)行劃分，同時(shí)對(duì)坐標(biāo)系中文字的字體規(guī)定為宋體，方向節(jié)點(diǎn)也進(jìn)行了限定。

(2)繪制異常地形區(qū)，將地面中不平的低洼地區(qū)用球體進(jìn)行模擬，確定球體自變量，對(duì)異常地形區(qū)域進(jìn)行限制，并將綠色地區(qū)設(shè)定為異常地形區(qū)，確定出異常地形區(qū)進(jìn)行模擬。對(duì)異常數(shù)據(jù)設(shè)置限制進(jìn)行封頂處理。

(3)設(shè)置障礙物，用0標(biāo)記的節(jié)點(diǎn)代表可以通過(guò)的節(jié)點(diǎn)，用1標(biāo)記的節(jié)點(diǎn)代表不能通過(guò)的節(jié)點(diǎn)，繪制符合規(guī)劃路徑的不同方位的障礙物地形圖。

2 A*算法

2.1 A*算法

A*算法是N.J.Nilsson、B.Raphael和 P.E.Hart在1968年提出來(lái)的一種啟發(fā)式搜索算法[3]。這種方法將Dijkstra和BFS兩種方法的優(yōu)勢(shì)相融合，并且Dijkstra算法與BFS算法的距離代價(jià)同時(shí)被A*算法考慮到，摒棄了部分劣勢(shì)構(gòu)造了新的代價(jià)函數(shù)用來(lái)搜索路徑。從規(guī)劃路徑的起始點(diǎn)出發(fā)，根據(jù)節(jié)點(diǎn)的擴(kuò)展方向，通過(guò)柵格圖繼續(xù)搜索目標(biāo)點(diǎn)的最優(yōu)搜索方向，獲得最優(yōu)路徑，保證搜索效率。其基本思想是利用啟發(fā)式函數(shù)計(jì)算柵格周?chē)?個(gè)節(jié)點(diǎn)的估計(jì)值，選擇生成最低成本的節(jié)點(diǎn)作為下一個(gè)搜索步驟的父節(jié)點(diǎn)，繼續(xù)不斷搜索該父節(jié)點(diǎn)周?chē)噜彽墓?jié)點(diǎn)，直到找到目標(biāo)節(jié)點(diǎn)為止來(lái)確定搜索方向[4]。因此搜索算法的效率不僅被提高了，還優(yōu)化了規(guī)劃的路徑以至保證路徑最優(yōu)，代價(jià)函數(shù)的計(jì)算方式可表示為：

式中：g(n)是指從起始點(diǎn)到待擴(kuò)展點(diǎn)n的實(shí)際路程的代價(jià)，一般是固定數(shù)值；啟發(fā)函數(shù)是A*算法的關(guān)鍵，具有一致性和可接受性的啟發(fā)函數(shù)可使A*算法收斂到既滿足局部最優(yōu)的解又滿足全局最優(yōu)的解[5]，h(n)是待擴(kuò)展點(diǎn)n到終止點(diǎn)的預(yù)估路程，為了減少該算法的計(jì)算量，選用歐式距離來(lái)近似代替啟發(fā)函數(shù)，啟發(fā)式函數(shù)如下式：

從式(2)可以看出，h(n)函數(shù)表示待擴(kuò)展路徑點(diǎn)n到目標(biāo)節(jié)點(diǎn)的x軸、y軸和z軸的相對(duì)距離的絕對(duì)值的和。

2.2 A*算法存在的問(wèn)題

A*算法作為最常用的全局算法之一，該算法可以快速確定靜態(tài)環(huán)境下的最優(yōu)路徑[6]，但傳統(tǒng)的A*算法仍然存在搜索范圍少、擴(kuò)展方向盲目等一些缺點(diǎn)。

使用傳統(tǒng)的A*算法搜索移動(dòng)機(jī)器人路徑時(shí)，會(huì)存在以下問(wèn)題：

(1)當(dāng)傳統(tǒng)A*算法擴(kuò)展路徑點(diǎn)時(shí)，計(jì)算量會(huì)隨著地圖增大而增加，從而導(dǎo)致搜索效率降低、規(guī)劃路線不平滑等問(wèn)題。

(2)傳統(tǒng)的A*算法搜索出來(lái)的算法只有躲避障礙物的路徑，沒(méi)有考慮在復(fù)雜的地形條件下執(zhí)行運(yùn)行任務(wù)的路徑。為了解決上述在移動(dòng)機(jī)器人運(yùn)行中存在的問(wèn)題，對(duì)A*算法進(jìn)行如下改進(jìn)。

3 改進(jìn)A*算法

3.1 擴(kuò)展搜索節(jié)點(diǎn)

在傳統(tǒng)A*算法中，簡(jiǎn)化了移動(dòng)機(jī)器人在移動(dòng)運(yùn)輸中與周?chē)系K物碰撞的問(wèn)題，將移動(dòng)機(jī)器人在三維坐標(biāo)系中的投影視為一個(gè)質(zhì)點(diǎn)，提出了一種擴(kuò)大搜索范圍、拓展節(jié)點(diǎn)的方法。傳統(tǒng)A*算法在當(dāng)前目標(biāo)點(diǎn)擴(kuò)展領(lǐng)域節(jié)點(diǎn)時(shí)，擴(kuò)展的路徑通常使用八向區(qū)域擴(kuò)展，也就是八個(gè)搜索方向的搜索方式，八向領(lǐng)域擴(kuò)展偏向于存儲(chǔ)搜索模式，擴(kuò)展節(jié)點(diǎn)如圖1所示，每次當(dāng)前路徑點(diǎn)臨近的8個(gè)鄰域可以被算法搜索到，每一個(gè)轉(zhuǎn)角都為45°，導(dǎo)致有效搜索方向是有限的。

圖1 八向擴(kuò)展圖

為準(zhǔn)確確定A*算法的搜索范圍，將物流無(wú)人機(jī)的搜索方向擴(kuò)展到16個(gè)，如圖2所示，移動(dòng)機(jī)器人可以從當(dāng)前路徑點(diǎn)直接搜索到鄰近區(qū)域的8+16個(gè)節(jié)點(diǎn)中是否存在障礙物，因此移動(dòng)機(jī)器人的最小轉(zhuǎn)角減小到22.5°，有效地?cái)U(kuò)展了搜索范圍。在選擇下一個(gè)擴(kuò)展節(jié)點(diǎn)之前，長(zhǎng)遠(yuǎn)的搜索范圍可以更好地規(guī)劃路徑來(lái)搜索下一路徑點(diǎn)，為了更快地到達(dá)終止路徑點(diǎn)，更快速地完成運(yùn)行任務(wù)打下基礎(chǔ)。

圖2 16個(gè)搜索方向

3.2 特殊地形威脅

移動(dòng)機(jī)器人的體積更小，對(duì)地面威脅的感知更加敏感。因此，移動(dòng)機(jī)器人的路徑規(guī)劃要考慮地形對(duì)運(yùn)行姿態(tài)的威脅。

在路徑規(guī)劃中，以移動(dòng)機(jī)器人的安全為主要目標(biāo)，考慮到地面不平整有凹陷問(wèn)題，使規(guī)劃的路線滿足運(yùn)行需求，因此首先對(duì)安全方面進(jìn)行優(yōu)化，其次考慮優(yōu)化時(shí)間消耗。為了規(guī)劃出高安全度和高效率的移動(dòng)機(jī)器人運(yùn)行路徑，對(duì)搜索路徑進(jìn)行約束。

本文主要研究地面凹陷對(duì)移動(dòng)機(jī)器人運(yùn)行時(shí)規(guī)劃路徑的影響，將凹陷區(qū)域表示為一個(gè)球體，球體半徑就是凹陷的范圍，因此，凹陷的最大半徑記為Rmax。凹陷的危險(xiǎn)度W如下式：

式中：xs、ys為與當(dāng)前點(diǎn)相鄰的點(diǎn)的立方體周?chē)鴺?biāo)。

式中，Tw為移動(dòng)機(jī)器人到凹陷區(qū)域中心的距離。

4 仿真實(shí)驗(yàn)

4.1 仿真實(shí)驗(yàn)分析及初始化

仿真采用的計(jì)算機(jī)型號(hào)為CPUi5-8265U，4G內(nèi)存，1.6GHz的主頻，使用MATLAB R2018b版本軟件進(jìn)行仿真實(shí)驗(yàn)。規(guī)劃環(huán)境長(zhǎng)度、寬度和高度分別為100×100×6000的空間區(qū)域?yàn)檫\(yùn)行的環(huán)境地圖，在此基礎(chǔ)上輸入起始點(diǎn)、終止點(diǎn)、障礙物特性、特殊地形區(qū)域、啟發(fā)式函數(shù)、實(shí)際成本函數(shù)等限制條件，并從生成的三種不同地圖環(huán)境中的規(guī)劃路徑地面投影長(zhǎng)度、規(guī)劃路徑長(zhǎng)度、路線形狀與傳統(tǒng)A*算法進(jìn)行對(duì)比，再使用通過(guò)MATLAB程序得到的數(shù)據(jù)進(jìn)行計(jì)算，從而驗(yàn)證改進(jìn)A*算法在移動(dòng)機(jī)器人路徑規(guī)劃中的可行性。

4.2 實(shí)現(xiàn)步驟

Step1：輸入移動(dòng)機(jī)器人尋路程序、路徑起始坐標(biāo)和結(jié)束坐標(biāo)；

Step2：繪制改進(jìn)A*算法路徑規(guī)劃的不同方位的地圖，包括：三維環(huán)境地圖，垂直剖面視圖，水平剖面視圖；

Step3：創(chuàng)建OPEN集數(shù)據(jù)結(jié)構(gòu)和CLOSE集數(shù)據(jù)結(jié)構(gòu)，設(shè)置起點(diǎn)為第一個(gè)點(diǎn)，Node為當(dāng)前點(diǎn)，F(xiàn)Node為父節(jié)點(diǎn)；

Step4：設(shè)置g(n)起點(diǎn)到指定方格和h(n)指定方格到終點(diǎn)。判斷是否有可行路徑，并且把1設(shè)置為可行路徑，把0設(shè)置為不可行路徑；

Step5：判斷搜索到的路徑點(diǎn)是否為目標(biāo)點(diǎn)，選擇最小f(n)值的點(diǎn)為下一路徑點(diǎn)；

Step6：當(dāng)路徑點(diǎn)已經(jīng)到終止路徑點(diǎn)所在的節(jié)點(diǎn)，或未擴(kuò)展到終止巡航點(diǎn)但 OPEN 列表為空時(shí)搜索完成。

Step7：移動(dòng)機(jī)器人的運(yùn)行軌跡從終止路徑點(diǎn)，經(jīng)過(guò)每個(gè)路徑點(diǎn)的父節(jié)點(diǎn)，反向回溯直到達(dá)起始點(diǎn)，算法可以停止。

4.3 結(jié)果分析

采用傳統(tǒng)A*算法與改進(jìn)A*算法得到移動(dòng)機(jī)器人路徑結(jié)果，3D仿真結(jié)果如圖3、圖4所示，垂直剖面視圖如圖5和圖6所示，水平剖面視圖如圖7和圖8所示。在起始路徑點(diǎn) start 坐標(biāo)為（20，20，7），終止路徑點(diǎn) end 坐標(biāo)為（90，70，5）時(shí)，利用改進(jìn)的A*算法在三維地圖和垂直水平兩個(gè)剖面地圖下得到的路徑規(guī)劃圖。

圖3 傳統(tǒng)A*算法的3D仿真結(jié)果

圖4 改進(jìn)A*算法的3D仿真結(jié)果

圖5 傳統(tǒng)A*算法的垂直剖面視圖

圖6 改進(jìn)A*算法的垂直剖面視圖

圖7 傳統(tǒng)A*算法的水平剖面視圖

圖8 改進(jìn)A*算法的水平剖面視圖

由圖可以直觀地看出，改進(jìn)A*算法在三種表示方式不同的地圖上，比傳統(tǒng)的A*算法規(guī)劃的路徑擁有更小的轉(zhuǎn)彎角度、更大的路徑平滑度、更短的運(yùn)行路徑長(zhǎng)度，安全性和效率都得到了明顯的提高，移動(dòng)機(jī)器人從起始點(diǎn)通過(guò)新規(guī)劃的路徑到終止點(diǎn)所經(jīng)的路徑更短，且能夠適應(yīng)不同方位表達(dá)的空域環(huán)境地圖，同時(shí)和障礙物保持一定的距離，避免與障礙物發(fā)生碰撞，保障了移動(dòng)機(jī)器人在運(yùn)行時(shí)候的安全。改進(jìn)A*算法的擴(kuò)展搜索節(jié)點(diǎn)通過(guò)減少路徑折角使路徑變得更加平滑，以此高效、平穩(wěn)地避開(kāi)了對(duì)環(huán)境中的障礙物。同時(shí)考慮環(huán)境中的特殊的地形凹陷對(duì)移動(dòng)機(jī)器人的威脅，對(duì)運(yùn)行路徑進(jìn)行約束，提高了移動(dòng)機(jī)器人運(yùn)行時(shí)的安全性。

表1 路徑規(guī)劃對(duì)比結(jié)果

由表1可知，傳統(tǒng)A*算法規(guī)劃路徑長(zhǎng)度為13091.44 m，改進(jìn)后的A*算法規(guī)劃路徑長(zhǎng)度為11813.24 m，傳統(tǒng)A*算法規(guī)劃路徑地面投影長(zhǎng)度為12266.90 m，改進(jìn)后的A*算法規(guī)劃路徑地面投影長(zhǎng)度為10959.80m。通過(guò)計(jì)算可知，改進(jìn)后的A*算法比傳統(tǒng)A*算法規(guī)劃路徑長(zhǎng)度縮短了9.8%，地面投影長(zhǎng)度縮短了10.7%，也表明了上文對(duì)擴(kuò)展搜索節(jié)點(diǎn)和考慮運(yùn)行時(shí)特殊地形威脅的合理性，改進(jìn)后的A*算法在移動(dòng)機(jī)器人運(yùn)行時(shí)能夠規(guī)劃出更短的路徑。

5 結(jié)論

A*算法在路徑規(guī)劃方面具有一定的優(yōu)勢(shì)，可以為最優(yōu)安全運(yùn)行路徑提供快速求解方法。因此，本文在傳統(tǒng)A*算法的基礎(chǔ)上提出了一種改進(jìn)算法，通過(guò)把搜索節(jié)點(diǎn)數(shù)擴(kuò)大搜索范圍，搜索方向擴(kuò)展成16個(gè)，鄰域則擴(kuò)展為24個(gè)，解決了路徑拐點(diǎn)個(gè)數(shù)多、路徑不平滑、搜索范圍有限等問(wèn)題，可以快速有效地規(guī)劃在靜態(tài)環(huán)境下的一條最優(yōu)路徑來(lái)避免碰撞保障運(yùn)行安全，同時(shí)也提高了搜索精度，縮短了移動(dòng)機(jī)器人的運(yùn)行路徑；仿真實(shí)驗(yàn)結(jié)果表明，基于該算法的移動(dòng)機(jī)器人在保證安全避障的前提下，改進(jìn)后的A*算法在規(guī)劃路徑長(zhǎng)度和規(guī)劃路徑地面投影長(zhǎng)度等方面都優(yōu)于原算法，更加符合移動(dòng)機(jī)器人的運(yùn)行狀態(tài)，為后續(xù)移動(dòng)機(jī)器人的研究提供思路。