基于分形維數(shù)和模糊-A＊算法的移動(dòng)機(jī)器人路徑規(guī)劃研究

李緒，王慧娜，鄧三鵬，祁宇明，李輝

（1.天津職業(yè)技術(shù)師范大學(xué)機(jī)器人及智能裝備研究院，天津 300222；2.天津市智能機(jī)器人技術(shù)及應(yīng)用企業(yè)重點(diǎn)實(shí)驗(yàn)室，天津 300350；3.天津博諾智創(chuàng)機(jī)器人技術(shù)有限公司，天津 300350）

0 引言

移動(dòng)機(jī)器人的實(shí)際工作環(huán)境信息復(fù)雜多變，僅依靠單一算法規(guī)劃路徑無(wú)法最佳滿足應(yīng)用場(chǎng)景的要求，移動(dòng)機(jī)器人在規(guī)劃全局最優(yōu)路徑的同時(shí)，更要具備動(dòng)態(tài)避障的能力[1]。因此，多種路徑規(guī)劃算法之間融合，是目前路徑規(guī)劃的主要研究方向之一。

時(shí)也[2]針對(duì)A*算法轉(zhuǎn)折次數(shù)過(guò)多，路徑不平滑，引入了模糊算法，采用雙層?xùn)鸥竦貓D，優(yōu)化局部路徑的平滑度，但是未考慮動(dòng)態(tài)和復(fù)雜障礙物的情況。王洪斌等[3]利用二次A*算法與動(dòng)態(tài)切點(diǎn)調(diào)整法優(yōu)化路徑的平滑度，結(jié)合改進(jìn)的A*算法和改進(jìn)的人工勢(shì)場(chǎng)算法規(guī)劃局部路徑，解決了傳統(tǒng)算法計(jì)算量大，效率不高等問(wèn)題。Ji等[4]提出一種基于優(yōu)化A*算法和動(dòng)態(tài)窗口法的優(yōu)化算法，提高搜索效率，但存在速度震蕩的問(wèn)題。

對(duì)已有的路徑規(guī)劃算法的研究中發(fā)現(xiàn)，A*算法具有運(yùn)行速度快、路徑規(guī)劃短等優(yōu)點(diǎn)，但是A*算法規(guī)劃的路徑拐點(diǎn)過(guò)多，路徑也沿著障礙物的邊緣前進(jìn)。模糊算法在規(guī)劃路徑時(shí)，規(guī)劃的路徑是一條相對(duì)平滑的路徑，但所規(guī)劃的路徑往往并不是最短路徑。如將兩種算法的優(yōu)點(diǎn)結(jié)合起來(lái)而進(jìn)行路徑規(guī)劃，可為移動(dòng)機(jī)器人規(guī)劃出一條平滑可行的最佳路徑。使用A*算法對(duì)移動(dòng)機(jī)器人進(jìn)行全局路徑規(guī)劃，同時(shí)結(jié)合模糊算法進(jìn)行局部規(guī)劃，提高路徑平滑度。引入分形維數(shù)，評(píng)估移動(dòng)機(jī)器人路徑的復(fù)雜程度，確保其在最佳路徑軌跡下運(yùn)行到目標(biāo)點(diǎn)。

1 A＊算法的描述

1.1 路徑規(guī)劃中的環(huán)境模型

要使用A*算法進(jìn)行全局路徑規(guī)劃首先需要構(gòu)建環(huán)境地圖，通過(guò)構(gòu)建已知的移動(dòng)機(jī)器人工作環(huán)境地圖才能有效地為移動(dòng)機(jī)器人找到最佳路徑。柵格地圖中障礙物用黑色柵格表示，可通行區(qū)域用白色柵格表示。柵格法可隨機(jī)產(chǎn)生障礙物的分布和數(shù)量，適用復(fù)雜環(huán)境的描述。

通過(guò)16×16的柵格圖法來(lái)構(gòu)建環(huán)境地圖，對(duì)障礙物及邊界區(qū)域的柵格進(jìn)行賦值，將障礙物信息在柵格環(huán)境地圖中顯現(xiàn)，確定環(huán)境地圖的環(huán)境邊界、障礙物、起始點(diǎn)及目標(biāo)點(diǎn)，黑色部分包含障礙物和邊界。柵格地圖如圖1所示。

圖1 柵格地圖

1.2 A＊算法

A*是一種啟發(fā)式的路徑搜索方法，它通過(guò)評(píng)價(jià)函數(shù)包含的啟發(fā)信息快速鎖定目標(biāo)方向[4]。評(píng)價(jià)函數(shù)的一般形式如（1）式：

其中，f（n）是從起點(diǎn)經(jīng)過(guò)節(jié)點(diǎn)n到終點(diǎn)的估價(jià)函數(shù)，表示節(jié)點(diǎn)n到終點(diǎn)的總體代價(jià)值。g（n）是起點(diǎn)到節(jié)點(diǎn)n所經(jīng)過(guò)路徑的實(shí)際代價(jià)值。h（n）是啟發(fā)函數(shù)，表示節(jié)點(diǎn)n到終點(diǎn)的預(yù)計(jì)代價(jià)值。h（n）直接影響算法的成功率。故h（n）的選擇對(duì)于整個(gè)算法至關(guān)重要。

所用的啟發(fā)函數(shù)h（n）為曼哈頓距離：

其中，xg和yg表示目標(biāo)點(diǎn)的橫縱坐標(biāo)，xs和ys表示當(dāng)前點(diǎn)的橫縱坐標(biāo)。

1.3 分形維數(shù)

目前有許多維數(shù)的定義和計(jì)算方法，主要包括豪斯多夫維數(shù)、盒維數(shù)、關(guān)聯(lián)維數(shù)、容量維數(shù)等多種分形維數(shù)[5]。其定義為用邊長(zhǎng)為ε的正方形去覆蓋平面所需要的正方形的個(gè)數(shù)為N（ε），公式可得：

式中，D代表盒維數(shù)。

盒維數(shù)運(yùn)行速度快，占用內(nèi)存少，利用柵格地圖規(guī)劃的路徑是一維線性的，所以采用盒維數(shù)評(píng)估規(guī)劃路徑的復(fù)雜度。

2 融合算法

2.1 模糊啟發(fā)式函數(shù)

融合算法通過(guò)A*算法規(guī)劃出安全可通行的全局路徑，在遇到障礙物時(shí)，通過(guò)引入模糊算法，增強(qiáng)h（n）啟發(fā)性。設(shè)計(jì)的模糊啟發(fā)式函數(shù)h’（n）為

其中，（1+m）為模糊因子，m的值為5×5柵格中障礙物占地面積與5×5柵格總面積的比值，取值區(qū)間為[0，1]。

以A*算法規(guī)劃的全局路徑為指引，融合模糊算法實(shí)現(xiàn)移動(dòng)機(jī)器人的避障，從而保證移動(dòng)機(jī)器人路徑規(guī)劃的有效性與安全性，同時(shí)引入分形維數(shù)，評(píng)估路徑的復(fù)雜程度。

以5×5柵格作為一個(gè)分形維數(shù)評(píng)估區(qū)域，如圖2所示，通過(guò)判斷這5×5柵格中路徑的盒維數(shù)，來(lái)評(píng)估5×5柵格區(qū)域中路徑的復(fù)雜程度。

圖2 5×5評(píng)估區(qū)域

融合算法首先通過(guò)A*算法規(guī)劃出安全可通行的全局路徑，在遇到障礙物時(shí)，通過(guò)模糊算法規(guī)劃局部路徑，使移動(dòng)機(jī)器人進(jìn)行避障。最后通過(guò)分形維數(shù)來(lái)評(píng)估規(guī)劃出路徑的復(fù)雜程度。融合算法流程圖如圖3所示。

圖3 算法流程圖

2.2 基于模糊算法的移動(dòng)機(jī)器人避障

將移動(dòng)機(jī)器人的左側(cè)、前方、右側(cè)與障礙物的距離LD、FD、RD，以及移動(dòng)機(jī)器人當(dāng)前的運(yùn)動(dòng)方向與目標(biāo)方向的夾角θ及當(dāng)前速度v作為模糊控制的輸入，將移動(dòng)機(jī)器人左右輪加速度a1和ar為模糊控制的輸出。將距離輸入模糊語(yǔ)言定為{NEAR，F(xiàn)AR}；將移動(dòng)機(jī)器人運(yùn)動(dòng)方向與目標(biāo)方向夾角θ模糊語(yǔ)言定為{LEFT，F(xiàn)RONT，RIGHT}；將當(dāng)前速度v模糊語(yǔ)言定為{SLOW，F(xiàn)AST}；將移動(dòng)機(jī)器人左右輪加速度模糊語(yǔ)言定為{NB，NS，Z，PS，PB}。下面列舉部分模糊控制規(guī)則庫(kù)，如表1所示。

表1 模糊規(guī)則庫(kù)

在此使用Mamdani推理，用質(zhì)心法去模糊化，最終得到移動(dòng)機(jī)器人所需的加速度。

3 仿真實(shí)驗(yàn)與分析

為檢驗(yàn)算法的性能，在Intel（R）Core（TM）i7-7700HQ CPU@2.80GHz計(jì)算機(jī)上利用MATLAB 2020b對(duì)模糊算法、傳統(tǒng)A*算法和融合算法在相同的柵格地圖場(chǎng)景中進(jìn)行仿真驗(yàn)證。構(gòu)建了一個(gè)16×16環(huán)境柵格地圖，模糊算法、傳統(tǒng)A*算法及融合算法的仿真實(shí)驗(yàn)結(jié)果，如圖4所示。

圖4 算法仿真對(duì)比圖

圖4中淺灰色小正方形為起始點(diǎn)，起始點(diǎn)為（1，1），深灰色小正方形為目標(biāo)點(diǎn)，目標(biāo)點(diǎn)為（15，15），黑色柵格為障礙物。對(duì)比圖（a）、圖（b）和圖（c）可以看出，融合算法中移動(dòng)機(jī)器人路徑更加平滑，冗余點(diǎn)及拐點(diǎn)也更少。因此，融合算法在移動(dòng)機(jī)器人路徑規(guī)劃的實(shí)際應(yīng)用中，具有更高的安全性。三種算法在路徑規(guī)劃時(shí)的相關(guān)參數(shù)見(jiàn)表2。

通過(guò)分析表2中相關(guān)參數(shù)，融合算法比其他兩個(gè)算法更加優(yōu)越，主要表現(xiàn)以下方面：路徑距離減少了38.49%，拐點(diǎn)數(shù)減少了66.67%，同時(shí)路徑平滑度（拐角）提高了66.67%。以上數(shù)據(jù)充分證明融合算法在移動(dòng)機(jī)器人路徑規(guī)劃時(shí)，規(guī)劃出的路徑更平滑，距離較優(yōu)，更適合移動(dòng)機(jī)器人日常的工作。

表2 三種算法相關(guān)參數(shù)

4 結(jié)語(yǔ)

基于分形維數(shù)的模糊-A*控制算法的移動(dòng)機(jī)器人路徑規(guī)劃方法，對(duì)A*算法進(jìn)行改進(jìn)。引入模糊算法，優(yōu)化路徑平滑度，減少路徑轉(zhuǎn)折點(diǎn)，與障礙物保持一定的安全距離；引入分形維數(shù)，進(jìn)一步優(yōu)化路徑。通過(guò)實(shí)驗(yàn)結(jié)果表明，基于分形維數(shù)和模糊-A*算法能夠使移動(dòng)機(jī)器人避開(kāi)觸碰障礙物，運(yùn)動(dòng)路徑更為平滑，節(jié)點(diǎn)數(shù)明顯減少。