基于改進A 星算法對自動導引小車路徑規劃研究*

王永成，楊明漾，張國輝

（鄭州航空工業管理學院管理工程學院，鄭州 450046）

0 引言

自動導引小車（Automatic Guided Vehicle）路徑規劃是AGV 作用在實際生產生活中的重要基礎。有動態障礙物的路徑規劃是當前典型的路徑規劃問題，主要以最短路徑和最短時間等為評價標準，從選定的起始點到目標點找出一條無碰撞的安全路徑，路徑規劃問題可以稱為避碰規劃問題。AGV工作地圖可以分為兩種：靜態地圖和動態地圖，本文主要研究動態地圖中AGV 路徑規劃問題。

AGV 路徑規劃問題是一種約束優化問題，有許多專家學者在研究AGV 路徑規劃算法問題，使用的算法有概率路線圖法（Probabilistic Roadmap，PRM）［1］、Dijkstra 算法［2］、A 星算法［3］、強化學習算法（Reinforcement Learning，RL）［4］、蟻群算法（Ant Colony Algorithm，ACA）［5］、遺傳算法（Genetic Algorithms，GA）［6］、神經網絡算法［7］、狼群算法（Wolf Colony Algorithm，WCA）［8］、粒子群算法（Particle Swarm Optimization，PSO）［9］、人工勢場算法［10］、模糊邏輯算法［11］等。文獻［12-19］也作了相關研究。

A 星算法是一種基于啟發式的路徑規劃算法，也是靜態環境中尋找最短路徑最有效的直接搜索方法之一，相較于其他傳統算法，具有更快的運算速度。

n 是路徑上的一個節點，f（n）是從第n 個節點到終點的估計代價，g（n）是從第n 個節點到終點的實際代價，h（n）是從第n 個節點到終點的最佳路徑的估計代價。在此算法中，估計代價h（n）越好，則運算速度與規劃出的路徑則最優，一般選用曼哈頓距離或歐幾里得距離為估計代價。A 星算法是一種成熟且最有效的路徑規劃直接搜索方法，但A 星算法估計代價選取不好時，會出現運算時間長或路徑不最優的問題。

1 基于改進A 星算法的AGV 路徑動態規劃

1.1 AGV 工作地圖建模改進

路徑規劃地圖建模中包含的元素主要有：AGV本身、靜態障礙物以及動態移動障礙物。傳統建模方式為：在程序中輸入地圖矩陣，地圖中每一個柵格對應二維矩陣中的一個數據，1 為障礙物，0 為無障礙空間。對地圖進行建模，進一步改進的建模方式為：輸入障礙物的頂點坐標，以頂點坐標圍成的封閉圖形作為障礙物。

在柵格數較多且地圖復雜的情況時，使用這兩種建模方式極為復雜，假設地圖大小為n×n，傳統建模方式需要輸入n2個數據，而后一種改進方式也需要輸入極多的數據。在實際應用中，這樣的建模方式不能準確地表示出實際地圖的情況，且極為復雜，針對這個問題，本文對地圖建模進行了改進，使算法能夠直接且準確識別輸入的照片，便于實際應用時工作地圖模型的建立。圖像處理的思路為：先將圖片進行灰度化處理，再對其進行圖像均衡化，對圖像進行增強，然后使用大津閾值法統計整個圖像的直方圖特性，實現全局閾值T 的自動選取，將其進行二值化分割，最終得到輸入圖片的數字特征矩陣。大津閾值法如圖1 所示。

圖1 大津閾值法流程

在圖像均衡化時，使用累積分布函數，對灰度化后的圖片進行均衡化，其映射方法如下：

其中，n 是圖像中像素的總數，nk是第k 灰度級個數，L 是圖像中灰度級總數。

通過對照片圖像處理設計，使得程序可以直接識別所在打開路徑文件夾里的任意格式圖片，黑色部分自動識別為障礙物，白色部分識別為可行路徑，大量減少地圖建模時間，在實際應用時可隨時改變地圖，便于對不同AGV 工作地圖進行路徑規劃。在程序中設置3 個常用地圖map1、map2、map3，利于常用地圖的切換。

動態地圖則是在靜態地圖的基礎上增加動態障礙物，以模擬在地圖中運動的人或物。本文在A星算法程序的基礎上加以改進，在地圖建模處理中增加動態障礙物的設計。程序以增加3 個動態障礙物為例，分別將障礙物設置為隨機移動障礙物、橫向隨機移動障礙物、豎向隨機移動障礙物分別仿真人和機器的運動。隨機移動障礙物的運動路徑為上、下、左、右、左上、左下、右上、右下、原地停止；橫向移動障礙物的運動路徑為左、右、原地不動；豎向隨機障礙物的運動路徑為上、下、原地不動；障礙物運動方向等概率出現。

1.2 接收地圖固定縮放處理

在利用A 星算法求解路徑規劃問題時，地圖的大小直接影響著算法的運算速度，由于路徑規劃問題對地圖精確度的要求較低，所以對所有地圖進行縮放處理，增加算法運算速度，提升系統效率以快速得到最優路徑。

在本文中，對縮放比例進行設計，以達到在不影響地圖精確度的前提下使算法運行速度更快。用地圖柵格均分整個地圖，柵格數越多，精確度越高。在這里用柵格個數作為精確度，由于AGV 路徑規劃對精確度要求并不苛刻，所以本文對比了10×10、50×50、100×100、150×150、200×200、1 000×1 000 的柵格數地圖，算法運算速度如表1 所示。路徑規劃精確度分別如圖2 所示。

圖2 各個柵格數地圖路徑規劃精確度

表1 不同地圖尺寸運算速度對比

通過對比發現，100×100、150×150、200×200較為精確，1 000×1 000 最為精確，10×10、50×50精確度很低，從時間上來講，隨著柵格數的增加而增加，且增加越來越快。綜合來講100×100 與150×150 較好，但考慮到在時間可接受的前提下盡量精確，固本文采用150×150 固定大小，此時，A 星算法求解最短路徑運算時間約為0.900 876 s，運算時間受初始點與目標點距離及障礙物復雜程度影響上下浮動。

此時，

n 為地圖柵格尺寸，c 為地圖實際尺寸。

1.3 拉直路徑消除多余拐點

由于A 星算法的啟發式函數，使A 星算法搜索具有方向感，能夠減少大量計算，但在某些特定情況下，這個明確的方向感會導致多余拐角的產生，如圖3 所示。

圖3 方向感導致的多余拐點

使用曼哈頓距離作為A 星算法的估計代價h（x），是用于解決路徑規劃問題的常用方法，且較為準確，但由于搜索的方向感會產生多余拐角。為了減少多余拐角使路徑更短，對A 星算法進行路徑規劃改進。

先進行靜態路徑規劃，在規劃好的路線上利用二階導數檢測路徑拐點，再從起點開始每隔一個拐點依連接，判斷連線上是否存在障礙物。若存在，則保留原路徑；若不存在，則刪除原路徑保留連線，直到判斷到終點為止，消除多余拐點流程圖如圖4 所示。

圖4 消除多余拐點流程圖

改進前后對比，如圖5 所示。

圖5 改進前（上）與改進后（下）對比

1.4 路徑平滑處理

本文在AGV 路徑平滑處理時，利用三次樣條插值法及充氣函數分別對無障礙路徑區域及地圖障礙物邊沿路徑進行平滑處理。

三次樣條插值法原理是在已規劃的路徑上選取相隔n 個單位的樣本點，舍棄這些樣本點之間的規劃點，再用平滑的圓弧連接這些樣本點，形成光滑路徑。三次樣條插值法平滑路徑，如圖6 所示。

圖6 3 次樣條插值法平滑路徑

在本文中，記路徑總點數為P，相隔點數n 的計算公式如下（約定［］為去四舍五入符號）：

在實際AGV 運行環境中，由于AGV 裝載貨物，可能導致無碰撞尺寸會變得更大，利用算法規劃出的路徑可能會導致碰撞，不一定是AGV 可通行路徑。所以對路徑平滑進行更進一步的處理，先對地圖進行膨脹，得出規劃路徑，求出路徑規劃后，再將膨脹地圖變為原地圖，這樣求出的規劃路徑與障礙物就將保持一定距離，增加路徑的可通行性，如圖7 所示。

圖7 原始地圖與膨脹地圖

對平滑處理前后路徑進行對比，發現平滑處理后的路徑明顯優于處理前的規劃路徑，如圖8所示。

圖8 平滑處理前后路徑

1.5 局部動態地圖路徑規劃

在局部動態環境中，引入D 星算法思想，尋求局部有障礙物時的路徑。D 星算法與A 星算法類似，但運算是從目標點開始進行反向搜索，直到搜索到機器人當前位置。在D 星算法中，主要運用兩個函數：Process-State 函數和Modify-Cost 函數，前者用于從目標點到當前位置的路徑搜索；后者用于改變A 星算法中的估價函數h（n），當遇到動態障礙物時，Modify-Cost 函數將實時改變估價函數h（n），從而使機器人規避動態障礙物，得到可通行路徑。

與A 星算法相比，D 星算法搜索是由搜索點向臨接點發散的，無A 星算法的方向感，且搜索方向是由目標點到當前點，可有效搜尋避障路徑。局部動態規劃流程如圖9 所示。其中，初始點為AGV 出發的點，目標點為AGV 所要到達的點，當前點為AGV 此時運動到的點，搜索點為此時動態路徑規劃搜索的點。

圖9 局部動態規劃流程圖

在動態環境中，對AGV 尺寸、動態障礙物尺寸及AGV 小車圓心到動態障礙物圓心之間的距離安全程度劃分的設計如下。

AGV 小車半徑：2 柵格，動態障礙物半徑：1 柵格。

AGV 小車到障礙物執行不同命令的距離設計：5 柵格：暫時停車等待，5-15 柵格：重新規劃路徑，15-25 柵格：減速行駛，25 柵格以上：正常行駛。

2 AGV 復雜環境路徑規劃仿真實驗及結果分析

2.1 改進A 星算法仿真開發

為了驗證改進算法的可行性與有效性，并使問題求解過程形象化和與視化，我們對改進A 星算法進行仿真開發，開發出基于改進A 星算法的AGV小車動態路徑規劃仿真平臺，用戶可以上傳自己的地圖來進行路徑規劃。

為了使動態規劃時更好地顯示AGV 小車的避撞路徑規劃，對AGV 小車進行設計，在仿真環境中，創建了一個半徑為0.2 m 的紅色圓圈作為機器人，并設置了3 個半圓作為探測障礙物的激光。藍色的圓圈是危險區域，如果一個物體出現在這個區域，機器人將暫停等待；綠色的圓圈是安全區域，如果一個物體出現在這個區域，機器人會重新規劃路徑；黃色的圓圈是感知距離區域，如果一個物體出現在這個區域，機器人就會減速，如圖10 所示。

圖10 不同情況下機器人性能

該平臺主要分為3 大部分：靜態地圖路徑規劃、動態地圖路徑規劃、AGV 小車命令顯示窗口。靜態地圖路徑規劃部分包含地圖選擇、地圖顯示、起始點和目標點設定、操作命令4 個小模塊。動態地圖路徑規劃部分包含動態地圖路徑顯示、隨機移動障礙物設定、橫向移動障礙物設定、豎向移動障礙物設定、操作命令5 個小模塊，命令顯示窗口部分可實時顯示所有執行的命令及AGV 小車的實時狀態，如下頁圖11 所示。

圖11 仿真平臺

2.2 改進A 星算法MATLAB 仿真結果

在本文中，分別對3 種地圖進行AGV 路徑規劃仿真實驗：靜態趣味迷宮地圖、復雜不規則地圖、車間模擬地圖，如圖12 所示。分別驗證改進A 星算法在靜態地圖、動態地圖和實際運用中的可行性和高效性。

圖12 3 種仿真地圖

分別對地圖1～地圖3 進行靜態路徑規劃實驗，如圖13～第136 頁圖15 所示。

圖13 地圖1：靜態路徑規劃仿真

圖14 地圖2：靜態路徑規劃仿真

圖15 地圖3：靜態路徑規劃仿真

通過3 種地圖靜態規劃仿真結果，驗證了改進的有效性。改進A 星算法的圖像處理可以直接接收輸入的圖片，無需進行地圖建模，可直接在程序中輸出150×150 地圖；靜態規劃輸出路徑更加平滑且遠離靜態障礙物。

在動態規劃部分，首先要進行地圖的靜態規劃，選用地圖2 的靜態規劃，得到靜態規劃路徑后，對靜態規劃后的路徑進行平坦化處理，在靜態規劃平坦化處理后的地圖上分別設置隨即動態障礙物、水平動態障礙物、豎直動態障礙物。為了模擬實際環境中的復雜情況，驗證動態規劃的有效性，在此加大了動態路徑規劃的難度，將動態障礙物全部設置到原路徑上，且處于通道較窄的位置，以得到實時改進路徑，動態障礙物設置如圖16 所示，動態路徑規劃如下頁圖17 所示。

圖16 動態障礙物設置

圖17 動態路徑規劃

動態規劃與靜態規劃路徑對比如下頁圖18 所示，粉紅色粗線為原規劃路徑，藍色細線為動態規劃實際路線。

圖18 動態規劃與靜態規劃路線對比

動態規劃仿真結果驗證了改進A 星算法具有在動態地圖中搜索路徑的能力，且可根據障礙物的位置實時改進路徑，規避動態障礙物。

MATLAB 仿真實驗驗證了改進A 星算法的有效性。

2.3 仿真結果對比分析

通過MATLAB 仿真結果，驗證了改進A 星算法靜態規劃與動態規劃的有效性，接下來通過改進A星算法與其他幾個常用算法的仿真結果對比，驗證改進A 星算法的優越性。

在求解路徑規劃問題中，規劃路徑優劣的主要指標有3 個：路徑長度、平滑程度、求解速度。路徑長度是主要指標，也是優化路徑的根本問題，平滑程度影響實際應用中AGV 運行快慢及安全程度，求解速度則是影響實際應用時系統能否迅速做出應對策略。所以，在此對改進A 星算法、改進遺傳算法、改進蟻群算法、改進粒子群算法從路徑長度、運算時間及平滑程度3 方面進行對比，平滑程度可以用彎折數和銳角彎折個數來表現。4 種算法的路徑規劃仿真效果如下頁圖19 所示，4 種算法運算速度及平滑程度如下頁表2 所示。

表2 4 種算法運算速度及彎折數對比

圖19 改進A 星算法與其他3 種算法路徑規劃對比

將4 種算法的各種指標進行打分，1 分為最差，4 分為最優，并根據指標重要程度進行加權綜合評分，其中，路徑長度權重為0.5，運算速度與彎折數權重都為0.2，銳角彎折數權重為0.1，得出評分如表3 所示。

表3 4 種算法綜合評分

通過MATLAB 仿真對比，驗證了改進A 星算法得出的規劃路徑更短更平滑，且運算速度較快，優于其他3 種改進算法。

3 結論

本文通過對當前較為普遍的路徑規劃算法進行對比，采用了較為成熟的A 星算法，并且通過自動識別圖片、固化地圖柵格數、拉直路徑消除多余拐點，使用3 次樣條插值法和地圖膨脹函數對路徑進行平滑處理、結合D 星算法思想處理動態規劃等對A 星算法進行改進，應用MATLAB GUI 開發工具進行了仿真平臺的開發，通過仿真實驗結果及與其他算法的對比，驗證了改進A 星算法的可行性與優越性。

與其他算法相比，自動識別圖片可減少大量的地圖建模時間，可以直接識別Auto CAD、Viso 等繪圖工具繪制的圖片，在實際應用中操作簡單省時。固化地圖柵格數則在不影響算法精度的前提下，大量減少算法時間，提高了路徑規劃的時效性，在實際應用中更加高效。拉直路徑消除多余拐點減少了路徑的彎折數且使路徑更短。通過3 次樣條插值法和地圖膨脹函數對路徑進行平滑處理，可以得到更加光滑的路徑，在實際AGV 運行時，減少了大量彎折，使AGV 運行速度更快且更加安全。在傳統A 星算法的基礎上引入D 星算法，使算法可以實時規劃AGV 路徑，在遇到障礙物時可以做到有效避障，使此程序適應的場合更廣，能夠適應更復雜的情況，在實際應用中具有很大意義。

相對于當前流行的智能算法而言，本文所用的改進A 星算法在路徑長度、運算速度、彎折數3 方面都較優，但在系統魯棒性及與其他算法相結合方面還需深入研究。