[發明專利]一種基于改進蟻群算法和A*算法的履帶車路徑規劃方法

在審

• 申請號: 202110096087.7
• 申請日: 2021-01-25
• 公開（公告）號: CN112925315A
• 公開（公告）日: 2021-06-08
• 發明（設計）人: 李旭杰;張東穩;胡居榮;顧燕;張云飛;李建霓
• 申請（專利權）人: 河海大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 孟紅梅

1.一種基于改進蟻群算法和A*算法的履帶車路徑規劃方法，其特征在于，包括如下步驟：

(1)獲取車身周圍障礙物位置信息，將規劃區域進行網格切分，并根據障礙物位置信息將網格進行障礙物與可通過區域的標記，構建柵格地圖；

(2)設置初始參數，包括螞蟻數量、信息素啟發因子、初始信息素濃度、期望啟發因子、信息素揮發常數、最大的迭代次數、履帶車的起始點S和終點E；

(3)將螞蟻放在起始點S的位置上，并將起始點S的位置加入禁忌表中；

(4)在優化蟻群算法作用下進行履帶車的路徑規劃，其中對于每個時刻t，要計算t時刻螞蟻k在當前節點i選擇下一個節點j的概率并前往下一個節點；當螞蟻k到達下一個節點j的時候，將節點i加入到禁忌表中；其中概率采用的啟發函數基于A*算法中的自適應比例進行優化，螞蟻k每次在選擇下一個節點時，會預估當前節點與終點E之間的距離，與終點E近的節點被賦予更大的權值；

(5)判斷螞蟻是否到達終點E，如果是，則根據禁忌表中的路徑節點計算路徑長短，否則繼續尋找下一個節點直到找到終點E為止；循環所有螞蟻，直到所有螞蟻都遍歷完成；

(6)結合履帶車轉彎時間代價函數，計算各路徑的耗時，選擇每輪迭代的最佳路徑；

(7)判斷當前迭代次數是否達到最大迭代次數，如果是，則結合履帶車轉彎代價，輸出耗時最短的路徑；否則重新規劃路徑，直到達到最大迭代次數，輸出耗時最短的路徑。

2.根據權利要求1所述的基于改進蟻群算法和A*算法的履帶車路徑規劃方法，其特征在于，所述步驟(4)中t時刻螞蟻k在當前節點i選擇下一個節點j的概率利用下式計算：

其中，allowed(k)是螞蟻k當前節點i周圍能夠選擇的節點的集合，T_ij(t)表示螞蟻k在t時刻從節點i到節點j的信息素含量，η_ij(t)是優化的啟發函數，為啟發權值與啟發函數強度的乘積，α是信息素啟發因子，β是期望啟發因子。

3.根據權利要求2所述的基于改進蟻群算法和A*算法的履帶車路徑規劃方法，其特征在于，啟發函數按照節點與終點E之間的距離來劃分權重，呈比例分布。

4.根據權利要求3所述的基于改進蟻群算法和A*算法的履帶車路徑規劃方法，其特征在于，螞蟻周圍能夠選擇的節點是八個，按照與終點距離的由遠至近設置的啟發權值比例為1:2:2:3:3:4:4:5。

5.根據權利要求1所述的基于改進蟻群算法和A*算法的履帶車路徑規劃方法，其特征在于，所述步驟(4)中對初始信息素分布進行如下優化：

其中，λ_ij(0)表示從節點i到節點j上的初始信息素濃度，d(j,E)表示節點j到終點E之間的距離，x_j、y_j是節點j在柵格地圖中的橫、縱坐標，x_E、y_E是終點E在柵格地圖中的橫縱坐標，C為常數。

6.根據權利要求1所述的基于改進蟻群算法和A*算法的履帶車路徑規劃方法，其特征在于，履帶車的轉彎時間代價函數為：

其中，t₂為履帶車轉彎時間，單位是s，n₁是履帶車轉彎外側驅動輪的轉速，單位是r/min，n₂是履帶車轉彎內側主動輪的轉速，單位是r/min，r是驅動輪的半徑，單位是m，B為兩側履帶中心間距，單位是m，G為履帶車傳動效率，θ為轉向角度。