基于分形維數和模糊-A＊算法的移動機器人路徑規劃研究

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

（1.天津職業技術師范大學機器人及智能裝備研究院，天津 300222；2.天津市智能機器人技術及應用企業重點實驗室，天津 300350；3.天津博諾智創機器人技術有限公司，天津 300350）

0 引言

移動機器人的實際工作環境信息復雜多變，僅依靠單一算法規劃路徑無法最佳滿足應用場景的要求，移動機器人在規劃全局最優路徑的同時，更要具備動態避障的能力[1]。因此，多種路徑規劃算法之間融合，是目前路徑規劃的主要研究方向之一。

時也[2]針對A*算法轉折次數過多，路徑不平滑，引入了模糊算法，采用雙層柵格地圖，優化局部路徑的平滑度，但是未考慮動態和復雜障礙物的情況。王洪斌等[3]利用二次A*算法與動態切點調整法優化路徑的平滑度，結合改進的A*算法和改進的人工勢場算法規劃局部路徑，解決了傳統算法計算量大，效率不高等問題。Ji等[4]提出一種基于優化A*算法和動態窗口法的優化算法，提高搜索效率，但存在速度震蕩的問題。

對已有的路徑規劃算法的研究中發現，A*算法具有運行速度快、路徑規劃短等優點，但是A*算法規劃的路徑拐點過多，路徑也沿著障礙物的邊緣前進。模糊算法在規劃路徑時，規劃的路徑是一條相對平滑的路徑，但所規劃的路徑往往并不是最短路徑。如將兩種算法的優點結合起來而進行路徑規劃，可為移動機器人規劃出一條平滑可行的最佳路徑。使用A*算法對移動機器人進行全局路徑規劃，同時結合模糊算法進行局部規劃，提高路徑平滑度。引入分形維數，評估移動機器人路徑的復雜程度，確保其在最佳路徑軌跡下運行到目標點。

1 A＊算法的描述

1.1 路徑規劃中的環境模型

要使用A*算法進行全局路徑規劃首先需要構建環境地圖，通過構建已知的移動機器人工作環境地圖才能有效地為移動機器人找到最佳路徑。柵格地圖中障礙物用黑色柵格表示，可通行區域用白色柵格表示。柵格法可隨機產生障礙物的分布和數量，適用復雜環境的描述。

通過16×16的柵格圖法來構建環境地圖，對障礙物及邊界區域的柵格進行賦值，將障礙物信息在柵格環境地圖中顯現，確定環境地圖的環境邊界、障礙物、起始點及目標點，黑色部分包含障礙物和邊界。柵格地圖如圖1所示。

圖1 柵格地圖

1.2 A＊算法

A*是一種啟發式的路徑搜索方法，它通過評價函數包含的啟發信息快速鎖定目標方向[4]。評價函數的一般形式如（1）式：

其中，f（n）是從起點經過節點n到終點的估價函數，表示節點n到終點的總體代價值。g（n）是起點到節點n所經過路徑的實際代價值。h（n）是啟發函數，表示節點n到終點的預計代價值。h（n）直接影響算法的成功率。故h（n）的選擇對于整個算法至關重要。

所用的啟發函數h（n）為曼哈頓距離：

其中，xg和yg表示目標點的橫縱坐標，xs和ys表示當前點的橫縱坐標。

1.3 分形維數

目前有許多維數的定義和計算方法，主要包括豪斯多夫維數、盒維數、關聯維數、容量維數等多種分形維數[5]。其定義為用邊長為ε的正方形去覆蓋平面所需要的正方形的個數為N（ε），公式可得：

式中，D代表盒維數。

盒維數運行速度快，占用內存少，利用柵格地圖規劃的路徑是一維線性的，所以采用盒維數評估規劃路徑的復雜度。

2 融合算法

2.1 模糊啟發式函數

融合算法通過A*算法規劃出安全可通行的全局路徑，在遇到障礙物時，通過引入模糊算法，增強h（n）啟發性。設計的模糊啟發式函數h’（n）為

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

以A*算法規劃的全局路徑為指引，融合模糊算法實現移動機器人的避障，從而保證移動機器人路徑規劃的有效性與安全性，同時引入分形維數，評估路徑的復雜程度。

以5×5柵格作為一個分形維數評估區域，如圖2所示，通過判斷這5×5柵格中路徑的盒維數，來評估5×5柵格區域中路徑的復雜程度。

圖2 5×5評估區域

融合算法首先通過A*算法規劃出安全可通行的全局路徑，在遇到障礙物時，通過模糊算法規劃局部路徑，使移動機器人進行避障。最后通過分形維數來評估規劃出路徑的復雜程度。融合算法流程圖如圖3所示。

圖3 算法流程圖

2.2 基于模糊算法的移動機器人避障

將移動機器人的左側、前方、右側與障礙物的距離LD、FD、RD，以及移動機器人當前的運動方向與目標方向的夾角θ及當前速度v作為模糊控制的輸入，將移動機器人左右輪加速度a1和ar為模糊控制的輸出。將距離輸入模糊語言定為{NEAR，FAR}；將移動機器人運動方向與目標方向夾角θ模糊語言定為{LEFT，FRONT，RIGHT}；將當前速度v模糊語言定為{SLOW，FAST}；將移動機器人左右輪加速度模糊語言定為{NB，NS，Z，PS，PB}。下面列舉部分模糊控制規則庫，如表1所示。

表1 模糊規則庫

在此使用Mamdani推理，用質心法去模糊化，最終得到移動機器人所需的加速度。

3 仿真實驗與分析

為檢驗算法的性能，在Intel（R）Core（TM）i7-7700HQ CPU@2.80GHz計算機上利用MATLAB 2020b對模糊算法、傳統A*算法和融合算法在相同的柵格地圖場景中進行仿真驗證。構建了一個16×16環境柵格地圖，模糊算法、傳統A*算法及融合算法的仿真實驗結果，如圖4所示。

圖4 算法仿真對比圖

圖4中淺灰色小正方形為起始點，起始點為（1，1），深灰色小正方形為目標點，目標點為（15，15），黑色柵格為障礙物。對比圖（a）、圖（b）和圖（c）可以看出，融合算法中移動機器人路徑更加平滑，冗余點及拐點也更少。因此，融合算法在移動機器人路徑規劃的實際應用中，具有更高的安全性。三種算法在路徑規劃時的相關參數見表2。

通過分析表2中相關參數，融合算法比其他兩個算法更加優越，主要表現以下方面：路徑距離減少了38.49%，拐點數減少了66.67%，同時路徑平滑度（拐角）提高了66.67%。以上數據充分證明融合算法在移動機器人路徑規劃時，規劃出的路徑更平滑，距離較優，更適合移動機器人日常的工作。

表2 三種算法相關參數

4 結語

基于分形維數的模糊-A*控制算法的移動機器人路徑規劃方法，對A*算法進行改進。引入模糊算法，優化路徑平滑度，減少路徑轉折點，與障礙物保持一定的安全距離；引入分形維數，進一步優化路徑。通過實驗結果表明，基于分形維數和模糊-A*算法能夠使移動機器人避開觸碰障礙物，運動路徑更為平滑，節點數明顯減少。