陳若男 文聰聰 彭玲 尤承增
摘 要:傳統(tǒng)A*算法在面向機(jī)器人室內(nèi)多U型障礙的特殊場景下規(guī)劃路徑時,容易忽略機(jī)器人實(shí)際大小,且計(jì)算時間較長。針對這個問題,提出一種改進(jìn)A*算法。首先引入鄰域矩陣進(jìn)行障礙搜索以提升路徑安全性,然后研究不同類型和尺寸的鄰域矩陣對算法性能的影響,最后結(jié)合角度信息和分區(qū)自適應(yīng)距離信息對啟發(fā)函數(shù)進(jìn)行改進(jìn)以提高計(jì)算效率。實(shí)驗(yàn)結(jié)果表明,改進(jìn)A*算法可以通過更改障礙搜索矩陣的尺寸來獲得不同的安全間距,以保證不同機(jī)器人在不同地圖環(huán)境下的安全性;而且在復(fù)雜大環(huán)境中與傳統(tǒng)A*算法相比尋路速度提高了28.07%,搜索范圍縮小了66.55%,提高了機(jī)器人在遇到動態(tài)障礙時二次規(guī)劃的靈敏性。
關(guān)鍵詞:?A*算法;室內(nèi)路徑規(guī)劃;移動機(jī)器人;啟發(fā)函數(shù)
中圖分類號:TP242.6
文獻(xiàn)標(biāo)志碼:A
Abstract: For indoor path planning for mobile robot in particular scenario with multiple U-shape obstacles, traditional A* algorithm has some problems such as ignoring the actual size of robot and long computational time. An improved A* algorithm was proposed to solve these problems. Firstly, a neighborhood matrix was introduced to perform obstacle search, improving path safety. Then, the effects of different types and sizes of neighborhood matrices on the performance of the algorithm were studied and summarized. Finally, heuristic function was improved by combining the angle information and the distance information (calculated in different expressions when situation changes) to improve the calculation efficiency. The experimental results show that the proposed algorithm can obtain different safety spacing by changing the size of obstacle search matrix to ensure the safety of different types of robots in different environments. Moreover, in the complex environment, compared with traditional A* algorithm, path planning speed is improved by 28.07%, and search range is narrowed by 66.55%, so as to improve the sensitivity of the secondary planning of robot when encountering dynamic obstacles.
Key words: A* algorithm; indoor path planning; mobile robot; heuristic function
0?引言
這些年,受機(jī)器人帶來的影響,人們的生活生產(chǎn)方式發(fā)生了革命性的轉(zhuǎn)變。機(jī)器人產(chǎn)業(yè)在市場需求以及國家政策扶持下,得到了迅速發(fā)展[1],被廣泛應(yīng)用到工業(yè)、服務(wù)業(yè)、安防,甚至醫(yī)療等領(lǐng)域中,對機(jī)器人要求也從原來的單一化和機(jī)械化向智能化和人性化的需求轉(zhuǎn)變[2],激發(fā)了社會各界人士對機(jī)器人的研究興趣。其中,路徑規(guī)劃是機(jī)器人智能化的關(guān)鍵技術(shù),是指移動機(jī)器人按照某一性能指標(biāo)搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或次最優(yōu)的無碰撞路徑[3]。
基于柵格法地圖,常用的路徑規(guī)劃算法[4-7]有Dijkstra算法、最佳優(yōu)先算法、啟發(fā)式搜索算法。Dijkstra算法是典型的廣度優(yōu)先算法,優(yōu)點(diǎn)在于總是可以找到最優(yōu)化路徑;但搜索效率低,難以滿足快速規(guī)劃路徑的需求。最佳優(yōu)先算法BFS(Best-First-Search)與Dijkstra算法最大的差異是以與目標(biāo)節(jié)點(diǎn)之間的距離作為評估,這種算法能夠快速引導(dǎo)向目標(biāo)節(jié)點(diǎn)搜索,大幅度提高算法搜索效率;但往往不能獲取合理的最短路徑。A*算法[8-10]是結(jié)合上述兩種算法優(yōu)勢提出的一種啟發(fā)式搜索算法。它利用啟發(fā)信息來引導(dǎo)搜索方向,從而減小搜索范圍,提高搜索效率。
繼A*算法之后,還有諸多新算法的提出,如D*算法(又稱動態(tài)A*算法)[11],該算法遇到動態(tài)環(huán)境時無需重新規(guī)劃,但是針對環(huán)境復(fù)雜的大區(qū)域地圖,存儲量會激增,且動態(tài)障礙頻繁出現(xiàn)時仍要重新規(guī)劃。還有諸多智能生物算法,如遺傳算法模擬進(jìn)化論觀點(diǎn),執(zhí)行效率較高;缺點(diǎn)在于占用存儲空間大,個體編碼方式和初始種群的確定難度高[12-13]。
因此,A*作為經(jīng)典算法,以其實(shí)用性至今被廣泛應(yīng)用,并且對不同場景具有很強(qiáng)的擴(kuò)展性和適應(yīng)性。研究學(xué)者們針對不同應(yīng)用場景,作出不同改進(jìn)。在移動機(jī)器人路徑規(guī)劃方面,王殿君[14]解決了傳統(tǒng)A*算法路徑包含過多冗余點(diǎn)的問題,并得到拐點(diǎn)處的最小轉(zhuǎn)折角度,明確機(jī)器人轉(zhuǎn)向;辛煜等[15]提出無限鄰域的A*算法思想解決了運(yùn)動方向被限定為π/4的倍數(shù)問題,但搜索速度會降低;顧辰[16]通過采用優(yōu)先級的子節(jié)點(diǎn)生成策略來避免了生成穿過障礙物柵格頂點(diǎn)的路徑,但路徑依然存在較大安全問題;Botea等[17]提出了HPA*(Hierarchical Path-finding A*)算法,該算法通過減少搜索空間來提高速度,但往往不能獲取最優(yōu)路徑;Goldberg等[18]通過提高啟發(fā)函數(shù)的準(zhǔn)確度來提高效率,但空間復(fù)雜度高;高民東等[19]提出了一種雙向時效A*算法尋找路徑,并采用多近鄰柵格距離計(jì)算方案,以達(dá)到提高效率、平滑路徑的效果,但不適合大尺寸復(fù)雜地圖。
從以上分析可看出,雖然不少研究人員針對A*算法進(jìn)行了改進(jìn),但仍未能很好地解決以下問題:忽略了機(jī)器人大小而造成的安全性問題;多U型障礙的室內(nèi)環(huán)境中算法效率不高的問題。
為解決上述問題,本文主要對傳統(tǒng)A*算法進(jìn)行兩方面的改進(jìn):1)采用鄰域矩陣的方式來進(jìn)行障礙搜索,以此達(dá)到通過選擇矩陣大小來適應(yīng)機(jī)器人實(shí)際大小的目的,解決傳統(tǒng)A*算法規(guī)劃路徑過于緊貼障礙物的問題。
2)設(shè)計(jì)新啟發(fā)函數(shù),以分區(qū)加權(quán)方式來表達(dá)距離信息,以叉積距離來表達(dá)角度信息,提高大地圖復(fù)雜環(huán)境下的算法效率,縮短遇到動態(tài)障礙再次規(guī)劃耗費(fèi)的時間。
1?環(huán)境模型
路徑規(guī)劃依賴地圖,常見的地圖構(gòu)建方法有可視圖法、拓?fù)鋱D法、柵格法。其中柵格法簡潔有效,易于維護(hù),應(yīng)用廣泛[20-22],所以,本文采用柵格法來建立移動機(jī)器人工作環(huán)境靜態(tài)二維地圖,以存儲機(jī)器人工作環(huán)境的基本情況,并在此基礎(chǔ)上進(jìn)行全局路徑規(guī)劃工作。通常室內(nèi)環(huán)境由于被分割成多個相鄰空間,并散落分布家居等障礙物,存在多個U型類障礙。為保證本文算法的可靠性和穩(wěn)定性,將多個U型障礙和簡單矩形障礙拼接,構(gòu)建了比真實(shí)室內(nèi)場景復(fù)雜度更高的模擬環(huán)境,地圖尺寸為600×600像素,如圖1所示。圖1中:深灰色區(qū)域?yàn)檎系K,淺灰區(qū)域?yàn)樽杂煽赏ㄐ袇^(qū)域,黑色圓點(diǎn)為起點(diǎn),白色原點(diǎn)為終點(diǎn)。
2?傳統(tǒng)A*算法
A*算法是一種典型的啟發(fā)式搜索算法,其結(jié)合了Dijkstra和BFS兩種算法各自的優(yōu)勢,在保證搜索效率的同時,可以得到最優(yōu)的路徑規(guī)劃[23]。傳統(tǒng)A*算法的核心思想體現(xiàn)在綜合考慮了起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的真實(shí)代價和當(dāng)前節(jié)點(diǎn)到終點(diǎn)的估計(jì)代價,因此可以引導(dǎo)搜索方向。
基本規(guī)劃路徑思路是以起點(diǎn)為第一個計(jì)算點(diǎn),計(jì)算其八鄰域中每個節(jié)點(diǎn)的代價值f(n),若某個節(jié)點(diǎn)被占用即為障礙物則不入棧。然后取其中f(n)值最小的節(jié)點(diǎn)作為下一個計(jì)算點(diǎn),并存儲其父節(jié)點(diǎn),直到搜索到終點(diǎn),最后從終點(diǎn)追溯其父節(jié)點(diǎn)獲取規(guī)劃路徑。圖2為傳統(tǒng)A*算法尋路的計(jì)算過程示例(此處假定障礙物頂點(diǎn)不可穿越)。
在上述計(jì)算路徑過程中,忽略了機(jī)器人實(shí)際大小,將其看作質(zhì)點(diǎn),只有障礙物所占用的節(jié)點(diǎn)不可通行,其相鄰節(jié)點(diǎn)均在可通行范圍內(nèi),所以最終獲取的路徑將會如圖2所示,緊貼障礙物,此類規(guī)劃路徑不適合機(jī)器人運(yùn)動,容易發(fā)生碰撞。
另外,在評價函數(shù)中,啟發(fā)函數(shù)h(n)對A*算法起主要影響作用:h(n)估值越小,A*算法需要計(jì)算的節(jié)點(diǎn)就越多,此時算法效率就會降低,逐步趨近Dijkstra算法;但如果h(n)估值很大,甚至遠(yuǎn)大于g(n),此時g(n)的作用便會失效,逐步趨于BFS算法,只追求速度無法獲取合理路徑。因此在設(shè)計(jì)啟發(fā)函數(shù)時,h(n)和g(n)必須要單位相對一致,保證兩者對f(n)的貢獻(xiàn)相對平等。
本文針對傳統(tǒng)A*算法忽略物體本身大小問題,提出一種面向機(jī)器人的障礙鄰域搜索方法。同時,針對室內(nèi)環(huán)境,構(gòu)建新的啟發(fā)函數(shù),提高遇到動態(tài)障礙時再次規(guī)劃的敏銳度。
3?本文算法
3.1?障礙搜索方式的改進(jìn)
本文提出一種基于鄰域矩陣的障礙搜索方式,在實(shí)際應(yīng)用中,需要根據(jù)機(jī)器人自身尺寸及地圖分辨率選擇合適尺寸的搜索矩陣,來確定路徑與障礙物的間距,保證機(jī)器人運(yùn)行過程中的安全問題。
鄰域矩陣搜索對路徑規(guī)劃的影響主要與類型和尺寸有關(guān),本文將通過實(shí)驗(yàn)分析這兩方面對路徑產(chǎn)生的具體影響。
3.1.1?鄰域矩陣類型選擇
本文中鄰域搜索矩陣是指以矩陣中1的個數(shù)命名的。以12鄰域搜索矩陣(S12)為例,判斷當(dāng)前節(jié)點(diǎn)是否可通行的依據(jù)是:矩陣中心點(diǎn)(3,3)對應(yīng)當(dāng)前節(jié)點(diǎn),此時標(biāo)識為1的位置對應(yīng)節(jié)點(diǎn)若均為自由節(jié)點(diǎn)(非障礙),則認(rèn)為當(dāng)前節(jié)點(diǎn)可通行;反之認(rèn)為不可通行。根據(jù)鄰域搜索方向分布可分為十字搜索和米字搜索兩類。兩者的區(qū)別是后者搜索矩陣四個頂點(diǎn)上值也為1。
基于前文構(gòu)建的地圖環(huán)境,分別對兩類搜索矩陣進(jìn)行測試,圖3是兩類方法規(guī)劃路徑的對比。表1是兩類方法規(guī)劃效率的對比,以搜索范圍、搜索時間、路徑長度為評價標(biāo)準(zhǔn)。其中搜索范圍是指搜索過程中所涉及計(jì)算的節(jié)點(diǎn)柵格總數(shù),搜索時間是指搜索總過程耗費(fèi)的時長,路徑長度是指從起點(diǎn)到終點(diǎn)規(guī)劃路徑的柵格節(jié)點(diǎn)總數(shù)。
圖3表明在矩陣大小相同的情況下,兩種搜索方式獲取的路徑與障礙物的最小間隔一致且不影響基本路徑走勢。從定性角度分析,兩種方法的搜索范圍(深灰色區(qū)域)差距不明顯。
表1定量地對比了相同間隔時,不同搜索矩陣類型對算法效率和規(guī)劃路徑的影響。表1中間隔為路徑與障礙物間的空閑節(jié)點(diǎn)數(shù),根據(jù)實(shí)驗(yàn)對比可知:在三組實(shí)驗(yàn)中,從搜索效率分析只有間隔為1個節(jié)點(diǎn)時,米字搜索范圍比十字搜索少42個節(jié)點(diǎn),略占優(yōu)勢,但由于米字搜索中每一單元格都比十字多四個節(jié)點(diǎn)的計(jì)算量,因此即使搜索范圍較小,耗費(fèi)的總搜索時間卻依然相對更長。且隨著間隔的擴(kuò)大,米字搜索對搜索范圍的縮小能力逐漸弱于十字搜索。從路徑角度分析,米字搜索法獲取的路徑始終比十字搜索要長??偟膩砜矗终系K搜索法比米字效率更高,規(guī)劃路徑更優(yōu),因此采用十字障礙搜索鄰域。
3.1.2?鄰域矩陣大小的選擇
在確定十字障礙搜索法后,需要選取合適鄰域矩陣的大小,矩陣大小決定了障礙物與路徑之間的間隔,對計(jì)算效率也有相應(yīng)影響。圖4為鄰域變化與路徑、障礙間隔大小間的關(guān)系。隨著鄰域的增大,規(guī)劃路徑與障礙物的最小間隔增大,如在傳統(tǒng)A*算法中,規(guī)劃路徑緊貼障礙物,即忽略了機(jī)器人大小。而利用36鄰域搜索障礙得到的路徑與障礙物間保有明顯的間隔,從而大幅降低了移動機(jī)器人在執(zhí)行命令時的碰撞概率。
從另一方面考慮,隨著鄰域的增大,可達(dá)到與建圖時“障礙膨脹”相同的效果,所以搜索鄰域越大,認(rèn)為是不可通行的節(jié)點(diǎn)數(shù)就會增加,相應(yīng)地減少了需要計(jì)算的節(jié)點(diǎn),總體上會提高規(guī)劃速度。與此同時,為了遠(yuǎn)繞障礙,規(guī)劃的路徑長度會有所增加。圖5量化了路徑長度、搜索時間與鄰域變化的關(guān)系,可看出鄰域增大對算法確實(shí)有雙向影響,一方面提高搜索效率,但另一方面卻會使路徑長度增加。
在應(yīng)用中,需要結(jié)合機(jī)器人的尺寸以及室內(nèi)地圖的分辨率,計(jì)算出安全間隔對應(yīng)的柵格數(shù),然后選擇一個能滿足安全性前提且路徑較短的鄰域矩陣。
由于障礙搜索的改進(jìn)方式側(cè)重路徑的安全性與最優(yōu)性,效率的提升是下一步啟發(fā)函數(shù)的側(cè)重點(diǎn),所以在選擇矩陣時,路徑長度短比搜索時間短優(yōu)先級高。
3.2?啟發(fā)函數(shù)的改進(jìn)
結(jié)合距離信息和角度信息本文設(shè)計(jì)的新啟發(fā)函數(shù)如下:
3.2.1?距離信息表達(dá)
常用的距離估算方式有曼哈頓距離、切比雪夫距離、歐幾里得距離。曼哈頓距離是標(biāo)準(zhǔn)A*的啟發(fā)函數(shù),以X、Y方向上的距離差的絕對值之和作為估計(jì)距離,意味著只允許向上下左右四個格網(wǎng)運(yùn)動;切比雪夫距離取X、Y方向距離差中較大的為距離估算值,即允許對角線運(yùn)動,且對角線運(yùn)動和水平垂直運(yùn)動的代價一致;歐幾里得距離則是最常見的兩點(diǎn)一線距離計(jì)算方式,可用于沿任意角度移動的情況,其比前兩種距離都短,在有障礙的情況下這種計(jì)算方式和實(shí)際距離會有較大差距。因?yàn)闅W幾里得距離和切比雪夫距離在障礙復(fù)雜環(huán)境下與真實(shí)代價的偏差較大,所以本文選擇在多障礙環(huán)境下距離估計(jì)更準(zhǔn)的曼哈頓距離更為合適。
為避免鄰域中代價相同而造成的路徑不確定性和抖動現(xiàn)象,將坐標(biāo)差加權(quán)后再求和。通過設(shè)置十組權(quán)值比{1∶9, 2∶8,…,9∶1}進(jìn)行路徑搜索,最后確定權(quán)值比6∶10效率最高,即p=6,q=10。
而分區(qū)加權(quán)是為了起到一定的方向引導(dǎo)作用。分區(qū)加權(quán)對引導(dǎo)作用的體現(xiàn)如圖6所示,以終點(diǎn)為坐標(biāo)原點(diǎn),以X=Y作為分割線,左下方區(qū)域中當(dāng)前點(diǎn)到終點(diǎn)在X方向距離差大于在Y方向距離差,此時定義Y1的權(quán)重為大系數(shù),由于在選擇計(jì)算點(diǎn)時優(yōu)先選擇代價小的節(jié)點(diǎn),故將會引導(dǎo)搜索方向朝Y1小的方向前進(jìn)(箭頭標(biāo)識),同理分割線右上方的區(qū)域則會朝X1小的方向前進(jìn)(箭頭標(biāo)識),從而引導(dǎo)搜索方向朝起止最短連線靠近。分析起止線左偏的情況同樣適用。
3.2.2?角度信息表達(dá)
在式(3)中還加入了角度信息,它是兩個向量叉積結(jié)果的模,這兩個向量分別是起點(diǎn)到終點(diǎn)的向量和當(dāng)前點(diǎn)到終點(diǎn)的向量。
其中:角度信息表達(dá)cross是依據(jù)叉積計(jì)算獲取的;通常情況下起止點(diǎn)距離|AB|是常量;而|CD|是隨著兩向量夾角變化而變化的量,當(dāng)兩者平行時|CD|達(dá)最小值,當(dāng)兩者垂直時|CD|達(dá)最大值,它很好地以距離的形式反映了兩者間的角度關(guān)系。
因此,在啟發(fā)函數(shù)中加入角度信息變量cross可誘導(dǎo)A*算法偏向拓展分布在起始點(diǎn)到目標(biāo)點(diǎn)連線附近的節(jié)點(diǎn)。
此外,因?yàn)閏ross的量綱是距離的平方,前文提及過,g(n)和h(n)必須要保持量綱平衡,不然可能會導(dǎo)致g(n)或h(n)的失效。本該對cross作開方然后疊加到h(n)中,考慮到開方對計(jì)算機(jī)而言是高復(fù)雜度的計(jì)算方式,所以選擇乘上系數(shù)m來達(dá)到近似開方的效果。m*cross=cross,即m=1/cross 本文實(shí)驗(yàn)地圖為600×600像素, 故本文實(shí)驗(yàn)crossmax=360000經(jīng)計(jì)算預(yù)估m(xù)≈0.0017。由于m是遞減函數(shù),隨著L增大而縮小。且cross最大值位于100000~1000000,根據(jù)單調(diào)遞減函數(shù)特性,可知對應(yīng)m閾值為[0.001,0.003]。
但由于式(3)中距離信息中進(jìn)行了加權(quán)操作,為了保持角度信息和距離信息貢獻(xiàn)量一致,取距離權(quán)值6,10的平均值8對角度信息進(jìn)行操作,即w=8*m。故w預(yù)估值為0.0136,閾值為[0.008,0.024]。通過二分法,進(jìn)行實(shí)驗(yàn),最終確定w為0.014,與預(yù)估值相近。
4?實(shí)驗(yàn)與結(jié)果分析
為了驗(yàn)證本文算法的可行性和有效性,基于Matlab2017a環(huán)境進(jìn)行仿真實(shí)驗(yàn)。將本文算法與傳統(tǒng)A*算法、雙向時效A*算法[19]以及提升安全性的文獻(xiàn)[16]算法進(jìn)行對比,分析定性和定量結(jié)果。實(shí)驗(yàn)中本文算法的障礙搜索方式采用12鄰域十字搜索矩陣(S12)。
圖8是本文算法與傳統(tǒng)A*算法路徑效果的定性對比:傳統(tǒng)A*算法路徑緊貼障礙物,規(guī)劃搜索范圍大;改進(jìn)其障礙搜索方式后,路徑與障礙物間有了安全間隔(淺灰色區(qū)域),且搜索范圍(深灰色區(qū)域)有所縮減,主要縮減量體現(xiàn)在靠近障礙物的區(qū)域。在此基礎(chǔ)上,進(jìn)一步改良啟發(fā)函數(shù)后獲取的路徑,在無障時基本走兩點(diǎn)間最短直線,在遇障時以小短折線形式繞過障礙,與原先隨機(jī)轉(zhuǎn)向相比,更加契合人類思維。與此同時,發(fā)現(xiàn)搜索范圍明顯縮小了,表明新啟發(fā)函數(shù)的導(dǎo)向能力更強(qiáng)。
表2是算法改進(jìn)前后規(guī)劃效率的定量對比。與傳統(tǒng)A*算法相比,本文路徑長度增加了6.63%,這主要消耗在保證路徑安全性上(增加了6.16%),是為了避開障礙物才產(chǎn)生的路徑長度增加效應(yīng)。除此項(xiàng)性能降低外,搜索柵格范圍縮小66.55%,體現(xiàn)了本文算法搜索方向聚攏效果增強(qiáng);操作總次數(shù)減少了37.93%,體現(xiàn)出搜索方向的引導(dǎo)效果好,減少了需要比較計(jì)算的節(jié)點(diǎn)數(shù);搜索耗費(fèi)時間降低了28.07%。
本文算法最大的特點(diǎn)是保證了路徑安全性,目前A*優(yōu)化算法中少有研究考慮路徑安全性問題,而這對機(jī)器人導(dǎo)航來說這至關(guān)重要。
文獻(xiàn)[16]提出了一種采用優(yōu)先級的子節(jié)點(diǎn)生成策略來避免路徑穿過障礙物柵格頂點(diǎn),效果如圖9(b)所示。該算法得到的路徑所在柵格依然與障礙物為相鄰單元格,并無間隔。
在實(shí)際應(yīng)用中,真實(shí)地圖的分辨率往往遠(yuǎn)小于機(jī)器人的實(shí)際體積,因此依然存在很大的安全隱患。且文獻(xiàn)[16]提出的優(yōu)先級策略從一定程度上加大了一些計(jì)算量:當(dāng)前點(diǎn)N的上下左右為一級節(jié)點(diǎn),對角線為二級節(jié)點(diǎn)。二級節(jié)點(diǎn)是否擴(kuò)展除了要判斷其自身是否為障礙物外,還需要考慮相鄰一級節(jié)點(diǎn)是否為障礙物。
而本文算法不僅能夠保證路徑整體與障礙物間有空閑單元格(如圖9(c)),還減少了算法的擴(kuò)展節(jié)點(diǎn)。此外,間格的多少可以通過改變障礙鄰域搜索矩陣大小來控制。因此可以滿足不同機(jī)器人尺寸和不同柵格地圖分辨率的應(yīng)用需求。
此外,本文算法的效率在復(fù)雜大地圖環(huán)境下有一定的優(yōu)勢。文獻(xiàn)[19]提出了一種雙向時效A*算法,并采用多近鄰柵格距離計(jì)算方案,以達(dá)到提高效率、平滑路徑的效果。表3是雙向時效A*算法和本文算法分別與傳統(tǒng)A*算法效率對比的結(jié)果。文獻(xiàn)[19]中設(shè)立了5個實(shí)驗(yàn)場景(表3中的實(shí)驗(yàn)1~5),分析表3可知該算法相對傳統(tǒng)A*算法,計(jì)算效率顯著提高,但也有一定的局限性。首先對比實(shí)驗(yàn)1~3,發(fā)現(xiàn)該算法對橢圓障礙的搜索效率遠(yuǎn)大于對矩形障礙。對比實(shí)驗(yàn)3和4,發(fā)現(xiàn)隨著地圖尺寸增大,算法效率提升效果降低。說明該算法的高效率特性需要建立在一定的前提下,對障礙類型和地圖尺寸有一定的要求。
在實(shí)驗(yàn)5中,以大地圖和中等復(fù)雜程度的障礙物為實(shí)驗(yàn)環(huán)境,文獻(xiàn)[19]算法計(jì)算速度比傳統(tǒng)A*算法提高36.11%。
而本文以600×600的大地圖和高復(fù)雜程度的障礙為實(shí)驗(yàn)環(huán)境(圖8),較傳統(tǒng)A*算法,效率提高28.07%。因此,而文獻(xiàn)[19]算法在簡單小地圖環(huán)境里表現(xiàn)突出,而本文算法更合適復(fù)雜大地圖的應(yīng)用場景。
綜合評價,本文算法雖然在路徑長度上有所犧牲,但保證了路徑的安全性,能夠在一定程度上避免機(jī)器人運(yùn)行過程中發(fā)生碰撞;與此同時,算法的效率得到了提升,適用于室內(nèi)多U型障礙的應(yīng)用場景,使得機(jī)器人在遇到動態(tài)障礙時再次規(guī)劃實(shí)時性更好。
5?結(jié)語
本文針對傳統(tǒng)A*算法在室內(nèi)機(jī)器人路徑規(guī)劃應(yīng)用中的問題進(jìn)行改進(jìn):首先,采用十字多鄰域矩陣搜索障礙解決原先忽略機(jī)器人大小造成的安全性問題;然后,設(shè)計(jì)新啟發(fā)函數(shù),引入分區(qū)加權(quán)距離信息和角度信息,提高復(fù)雜多U型障礙的室內(nèi)環(huán)境下的搜索效率,以縮短遇到動態(tài)障礙再次規(guī)劃所耗費(fèi)的時間。
仿真實(shí)驗(yàn)結(jié)果表明:本文算法可通過選擇不同尺寸的搜索矩陣來自定義路徑與障礙物的間距,方便地解決了不同尺寸機(jī)器人安全路徑的問題;且在復(fù)雜大環(huán)境下計(jì)算效率得到提高,使得遇到動態(tài)障礙時再次規(guī)劃的靈敏度提升。下一步工作將會考慮刪除路徑中的冗余節(jié)點(diǎn),以進(jìn)一步提高機(jī)器人運(yùn)行效率。
參考文獻(xiàn)(References)
[1] 王麗蘋. 機(jī)器人技術(shù)變遷及產(chǎn)業(yè)發(fā)展戰(zhàn)略研究[D]. 天津, 天津大學(xué), 2016: 1. (WANG L P. The study of development strategy and technological change of robot industry [D]. Tianjin: Tianjin University, 2016: 1.)
[2] 康凱. 基于機(jī)器視覺的移動機(jī)器人定位與三維地圖重建方法研究[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 2017: 1-2. (KANG K. Research on localization and mapping of mobile robot based on machine vision [D]. Harbin: Harbin Institute of Technology, 2017: 1-2.)
[3] JEDDISARAVI K, ALOTAPPEH R J, PIMEMTA L C A, et al. Multi-objective approach for robot motion planning in search tasks [J]. Applied Intelligence, 2016, 45(2): 305-321.
[4] 彭利民. 基于廣度優(yōu)先搜索的虛擬網(wǎng)絡(luò)映射算法[J]. 四川大學(xué)學(xué)報(bào)(工程科學(xué)版), 2015, 47(2): 117-122. (PENG L M. Virtual network embedding algorithm based on breadth-first search [J]. Journal of Sichuan University (Engineering Science Edition), 2015, 47(2): 117-122.)
[5] 劉艷麗, 樊曉平, 張恒. 基于啟發(fā)式搜索的移動機(jī)器人主動定位[J]. 機(jī)器人, 2012, 34(5): 590-595. (LIU Y L, FAN X P, ZHANG H. Heuristic search assisted active localization for mobile robot [J]. Robot, 2012, 34(5): 590-595.)
[6] 房佳, 杜震洪, 張豐, 等. 應(yīng)用于城市道路網(wǎng)的啟發(fā)式深度優(yōu)先有向搜索算法[J]. 浙江大學(xué)學(xué)報(bào)(理學(xué)版), 2013, 40(4): 469-474. (FANG J, DU Z H, ZHANG F, et al. Heuristic depth-first directional algorithm for shortest path searching in traffic networks[J]. Journal of Zhejiang University (Science Edition), 2013, 40(4): 469-474.)
[7] BURNS E, LEMONS S, ZHOU R, et al. Best-first heuristic search for multi-core machines [J]. Journal of Artificial Intelligence Research, 2010, 39(1): 689-743.
[8] FRANTISEK D, ANDREJ B. Path planning with modified a star algorithm for a mobile robot [J]. Procardia Engineering, 2014, 96(1): 59-69.
[9] UTTENDORF S, EILERT B, OVERMEYER L. Combining a fuzzy inference system with an A* algorithm for the automated generation of roadmaps for automated guided vehicles [J]. at-Automatisierungstechnik, 2017, 65(3): 189-197.
[10] WODZINSKI M, KRZYZANOWSKA A. Sequential classification of palm gestures based on A* algorithm and MLP neural network for quadrocopter control [J]. Metrology and Measurement Systems, 2017, 24(2): 265-276.
[11] 張曉冉, 居鶴華. 采用改進(jìn)D*Lite算法的自主移動機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)測量與控制, 2011, 19(1): 155-157. (ZHANG X R, JU H H. Developed D* Lite algorithm for path planning of autonomous mobile robots [J]. Computer Measurement & Control, 2011, 19(1): 155-157.)
[12] 徐美清, 孫晨亮. 基于柵格地圖的遺傳算法路徑規(guī)劃[J]. 科技信息, 2011(31): 76-77. (XU M Q, SUN C L. The occupancy grid map-building with neural network [J]. Science & Technology Information, 2011(31): 76-77.)
[13] 李天旭, 陳廣大.基于改進(jìn)遺傳算法的室內(nèi)移動機(jī)器人路徑規(guī)劃[J]. 制造業(yè)自動化, 2015, 37(20): 31-35. (LI T X, CHEN G D. Indoor mobile robot path planning based on improved genetic algorithm [J]. Manufacturing Automation, 2015, 37(20): 31-35.)
[14] 王殿君. 基于改進(jìn)A*算法的室內(nèi)移動機(jī)器人路徑規(guī)劃[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 52(8): 1085-1089. (WANG D J. Indoor mobile-robot path planning based on an improved A* algorithm [J]. Journal of Tsinghua University (Science and Technology), 2012, 52(8): 1085-1089.)
[15] 辛煜, 梁華為, 杜明博, 等. 一種可搜索無限個鄰域的改進(jìn)A*算法 [J]. 機(jī)器人, 2014, 36(5): 627-633. (XIN Y, LIANG H W, DU M B, et al. An improved A* algorithm for searching infinite neighborhoods [J]. Robot, 2014, 36(5): 627-633.)
[16] 顧辰.改進(jìn)的A*算法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J]. 電子設(shè)計(jì)工程, 2014, 22(19): 96-98, 102. (GU C. Application of improved A* algorithm in robot path planning [J]. Electronic Design Engineering, 2014, 22(19): 96-98, 102.)
[17] BOTEA A, MULLER M, SCHAEFFER J. Near optimal hierarchical path-finding [J]. Journal of Game Development, 2004, 1(1): 7-28.
[18] GOLDBERG A V, HARRELSON C. Computing the shortest path: A*search meets graph theory[C]// Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM, 2005: 156-165.
[19] 高民東, 張雅妮, 朱凌云. 應(yīng)用于機(jī)器人路徑規(guī)劃的雙向時效A*算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2019, 36(3): 792-795,800. (GAO M D, ZHANG Y N, ZHU L Y. Bidirectional time-efficient A* algorithm for robot path planning [J]. Application Research of Computers, 2019, 36(3): 792-795,800.)
[20] 余翀, 邱其文. 基于柵格地圖的分層式機(jī)器人路徑規(guī)劃算法[J]. 中國科學(xué)院大學(xué)學(xué)報(bào), 2013, 30(4): 528-538, 546. (YU C, QIU Q W. Hierarchical robot path planning algorithm based on grid map [J]. Journal of University of Chinese Academy of Sciences, 2013, 30(4): 528-538, 546.)
[21] 程向紅, 祁藝. 基于柵格法的室內(nèi)指示路徑規(guī)劃算法[J]. 中國慣性技術(shù)學(xué)報(bào), 2018, 26(2): 236-240, 267. (CHENG X H, QI Y. Indoor indicator path planning algorithm based on grid method[J]. Journal of Chinese Inertial Technology, 2018, 26(2): 236-240, 267.)
[22] 朱愛斌, 劉洋洋, 何大勇, 等. 解決路徑規(guī)劃局部極小問題的勢場柵格法[J]. 機(jī)械設(shè)計(jì)與研究, 2017, 33(5): 46-50. (ZHU A B, LIU Y Y, HE D Y, et al. An improved potential field-grid method for local minimization problem in path planning [J]. Machine Design and Research, 2017, 33(5): 46-50.)
[23] PETER E, NILSSON J, RAHEAL B. A formal basis for the heuristic determination of minimum cost paths [J]. ACM SIGART Bulletin, 1972, 4(37): 28-29.