[發明專利]一種基于改進的A*算法的路徑規劃方法

在審

• 申請號: 202110758838.7
• 申請日: 2021-07-05
• 公開（公告）號: CN113359768A
• 公開（公告）日: 2021-09-07
• 發明（設計）人: 王英立;韓彬
• 申請（專利權）人: 哈爾濱理工大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 哈爾濱三目知識產權代理事務所(普通合伙) 23214
• 代理人: 劉冰;馮慶柱

1.一種基于改進的A*算法的路徑規劃方法，其特征在于：所述方法是指對采集的路況地圖采用柵格法進行處理，得到柵格地圖；之后，利用蟻群算法對A*算法進行優化和改進；之后，采用人工勢場法進行局部路徑規劃，并針對人工勢場法的局部極小值和目標不可達的缺點進行改進優化；之后，將改進A*算法與人工勢場法相結合設計出混合路徑規劃算法，為后續的車輛路徑規劃提供合適的控制算法；之后，通過采用合適的路徑規劃算法，由系統自動規劃出一條可行性路徑，車輛按照該路徑避開障礙物，從而到達目標位置。

2.根據權利要求1所述的一種基于改進的A*算法的路徑規劃方法，其特征在于：所述的將改進A*算法與人工勢場法相結合設計出混合路徑規劃算法，具體包括：

步驟一、利用改進后的A*算法進行全局路徑規劃，得到一條初始路徑；

步驟二、檢測地圖環境中是否具有動態障礙物；

若是，則采用改進的人工勢場法進行局部路徑規劃，并針對局部極小值和目標不可達的缺點對其進行改進優化；

若否，則認為完成路徑規劃，得到最終混合算法規劃路徑。

步驟三、在采用改進的人工勢場法進行局部路徑規劃之后，判斷是否到達目的點；

若否，則返回步驟二；

若是，則認為完成路徑規劃，得到最終混合算法規劃路徑。

3.根據權利要求2所述的一種基于改進的A*算法的路徑規劃方法，其特征在于：所述的采用改進的人工勢場法進行局部路徑規劃的過程為，

通過修正勢場以及引入逃逸力的方法對人工勢場法進行改進。

4.根據權利要求3所述的一種基于改進的A*算法的路徑規劃方法，其特征在于：所述的對采集的路況地圖采用柵格法進行處理，得到柵格地圖柵格法的過程包括：

柵格法是指按照引導車能夠在每一單元格內自由運動的標準將引導車所處的待規劃空間分解為一個個獨立的單元格，得到柵格，并且柵格之間相互連接但不重疊；柵格化之后給每一個柵格賦予一個通行因子，將移動機器人在柵格地圖中的路徑規劃問題轉變成在兩個柵格節點間尋找最短路徑問題；若柵格中沒有障礙物，那么機器人在該柵格中可自由通行，此種柵格稱為為自由柵格，反之，稱為障礙柵格；柵格標識完成后，移動機器人根據坐標或序號搜索并顯示路徑。

5.根據權利要求1、2或4所述的一種基于改進的A*算法的路徑規劃方法，其特征在于：所述的基于改進A*算法的全局路徑規劃的步驟為，

通過蟻群算法的迭代優化性能來對A*算法進行優化改進，具體包括：

建立螞蟻尋路模型的步驟；

假設有如下等式成立的步驟：

τ₁＝τ₂＝τ₃＝C＞0

在后續的迭代中，建立如下信息素增量的計算公式的步驟：

式中：Q信息素的總量，是一個定值；Num螞蟻種群數量；螞蟻k，取值為1，2，3，…Num，從i到j的這一過程釋放的信息素量Δτ_ij(t)t周期后路段ij上增加的總信息素濃度；蟻群算法在進行迭代時，在不同的周期結束時刻，路線上信息素會揮發一次；

建立轉移概率公式的步驟：

式中：ρ信息素揮發系數，一般在0-1之間取值；τ_ij(t)周期的信息素量；τ_ij(t+1)t+1的信息量；螞蟻算法的核心在于模擬了螞蟻的轉移概率選擇行為，轉移概率是根據信息素與啟發式函數值來計算的，經過計算得到轉移概率，后續螞蟻據此可以進行路徑的選擇；其中，啟發式信息為d_ij為i到j間的長度。

6.根據權利要求5所述的一種基于改進的A*算法的路徑規劃方法，其特征在于：所述的基于改進人工勢場法的局部路徑規劃具體為：

在進行路徑規劃時，將引導車周圍看做一個勢場環境，目標點對引導車產生一個吸引力，障礙物對引導車產生一個排斥力，這樣引導車在兩種模擬力的合成作用下便可向著目標點前進；利用引導車受到障礙物的斥力以及目標點的吸引力的共同作用，在這兩個力的共同作用下，引導車可以避開障礙物向著目標點前進。由力的疊加可知，引導車所處環境中的總勢場函數為：

U_t＝U_a+U_r

上式中，U_a引力勢場；U_r斥力勢場；U_t車輛所處環境總勢場。車輛所受到合力為：

F_t＝F_a+F_r

上式中，F_a車輛所受到的引力；F_r車輛所受到的斥力。假設車輛的坐標為X＝(x,y)^T，那么對于引力勢場函數可以定義為：

上式中，λ引力勢場常量；X引導車位置向量；X_t引導車所在環境中的目標位置，那么此時引力可以用引力勢場函數的負梯度表示：

F_a＝-grad(U_a)＝-λ(X-X_t)＝λ(X_t-X)

由上式可知，當引導車越來越靠近目標點的時候吸引力越來越小，反之越來越大；當引導車到達目標位置時，所受到的引力為0。將斥力勢場函數定義為：

上式中，μ斥力勢場常量；α引導車與障礙物之間的距離最小值；α_o障礙物能夠對引導車產生作用的距離上限，是個常量，當引導車與障礙物的距離超過α_o時，引導車受到的斥力為0，也即是引導車不再受斥力作用。可知，斥力等于自身勢場負梯度：

上式中，在引導車行進在具有多種障礙物的復雜環境中的時候，引導車此時受到多個障礙物力的作用，勢場總和可以表示為：

U＝U_a+∑U_r

那么引導車受到的總力為：

F＝F_a+∑F_r。