[發明專利]基于改進蟻群算法的多農機協同作業遠程管理調度方法

在審

• 申請號: 202010484077.6
• 申請日: 2020-06-01
• 公開（公告）號: CN111639811A
• 公開（公告）日: 2020-09-08
• 發明（設計）人: 張漫;曹如月;李世超;季宇寒;徐弘禎;李寒;李民贊
• 申請（專利權）人: 中國農業大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q50/02;G06N3/00
• 代理公司: 北京中安信知識產權代理事務所(普通合伙) 11248
• 代理人: 李彬;徐林

1.一種基于改進蟻群算法的多農機協同作業遠程管理調度方法，其特征在于：包括如下步驟：

S1、任務規劃；

S1.1、任務分配；

利用遠程管理平臺發布的初始任務信息和農機信息，初始任務信息包括初始任務數量和任務坐標；農機信息包括農機數量和農機坐標；根據農機與任務的供需匹配原則，通過改進蟻群算法獲得最優任務分配方案；

S1.1.1、參數初始化；

設置改進蟻群算法的相關參數，包括螞蟻數量m、信息素揮發因子ρ、信息素常系數Q以及最大迭代次數n；

S1.1.2、通過公式1計算每個農機任務組合的路徑代價，即農機與相應任務地塊的距離：

D(i,j)＝sqrt(sum((worker(i,:)-task(j,:)).^2)) (公式1)

式中，worker(i,:)代表農機i的坐標，task(j,:)代表任務j的坐標，D(i,j)代表農機i和任務j之間的路徑代價，單位為米；

S1.1.3、設置每個農機的最大任務執行能力，即每個農機最多能完成的任務數量，初始化任務執行能力函數，如公式2所示：

worker_quality＝maxT (公式2)

式中，maxT代表每個農機最多能完成的任務數量，worker_quality代表當前任務執行能力；

S1.1.4、每只螞蟻按照農機和任務編號順序選擇下一個農機任務組合，通過公式3更新每個農機的任務執行能力函數；

worker_quality(i)＝worker_quality(i)-1 (公式3)

式中，worker_quality(i)代表農機i的當前任務執行能力；若一個農機的任務執行能力函數worker_quality(i)等于0時，則代表農機i當前任務執行能力為0，此時需要選擇下一個農機；

S1.1.5、判斷是否遍歷所有任務，如果已遍歷所有任務，則通過公式4至公式7計算每個螞蟻相應規劃方案的路徑總長度，記錄路徑代價最小的任務分配方案；否則，返回步驟S1.1.4；

oneant_path(i,j)＝1 (公式4)

all_ant_path＝[all_ant_path；oneant_path] (公式5)

each_ant_path＝all_ant_path(((k-1)*task_number+1):(task_number*k),:) (公式6)

cost＝sum(each_ant_path.*D^T) (公式7)

在公式4至公式7中，oneant_path(i,j)代表螞蟻生成的一組農機任務組合，當任務j分配給農機i時，oneant_path(i,j)賦值為1；all_ant_path存儲所有螞蟻生成的農機任務組合；each_ant_path代表第k只螞蟻生成的農機任務組合；task_number代表任務數量，D^T表示農機和任務之間的路徑代價D的轉置矩陣；cost代表每只螞蟻相應任務分配方案的路徑總長度，單位為米，進而求得路徑代價最小的任務分配方案；

S1.1.6、根據信息素更新規則更新信息素；

利用信息素揮發因子ρ和信息素常系數Q，通過公式8和公式9分別更新所有任務分配方案以及路徑代價最小的任務分配方案的信息素；

pheromoneMatrix(task_number,worker_number)

＝pheromoneMatrix(task_number,worker_number)*ρ (公式8)

pheromoneMatrix(best_ant_path(,2),best_ant_path(,1))

＝pheromoneMatrix(best_ant_path(,2),best_ant_path(,1))*Q (公式9)

在公式8和公式9中，pheromoneMatrix代表每個農機任務組合的信息素矩陣；best_ant_path代表路徑代價最小的農機任務組合；task_number代表任務數量；worker_number代表農機數量；

S1.1.7、判斷是否達到最大迭代次數，如果當前迭代次數小于最大迭代次數n，則重復執行步驟S1.1.4至步驟S1.1.7，直到當前迭代次數等于最大迭代次數n，則輸出最優任務分配方案；

S1.2、任務序列優化；

S1.2.1、參數初始化；

設置改進蟻群算法相關參數，包括螞蟻數量m、信息素重要程度因子α、啟發函數重要程度因子β、信息素揮發因子ρ、信息素常系數Q以及最大迭代次數n；

S1.2.2、根據步驟S1.1獲得的最優任務分配方案，通過公式8計算每個農機分配的任務地塊之間的路徑代價，即根據指定的任務坐標計算任務地塊之間的距離，單位為米；

D(j_i,j_j)＝sqrt(sum((task(j_i,:)-task(j_j,:)).^2)) (公式10)

在公式10中，task(j_i,:)代表任務j_i的坐標，task(j_j,:)代表任務j_j的坐標，D(j_i,j_j)代表任務j_i和任務j_j之間的路徑代價，單位為米；

S1.2.3、迭代尋找最佳路徑；

S1.2.3.1、隨機產生各螞蟻的起點地塊；

S1.2.3.2、根據狀態轉移概率公式11和公式12進行路徑選擇，選擇下一個地塊；

在公式11和公式12中，Eta代表啟發函數；Tau代表任務j_i和任務j_j連接路徑上的信息素濃度；P代表狀態轉移概率；

S1.2.3.3、計算各個螞蟻的路徑長度；

Length(k)＝Length(k)+D(j,j+1) (公式13)

在公式13中，D(j,j+1)代表任務j和任務j+1之間的路徑代價，單位為米；Length(k)代表螞蟻k的路徑長度，單位為米；

S1.2.3.4、記錄路徑代價最小的任務序列方案；

min_Length＝min(Length) (公式14)

Length_best(t)＝min(Length_best(t-1),min_Length) (公式15)

在公式14和公式15中，min_Length代表每次迭代中m只螞蟻中路徑代價最小的任務序列方案；Length_best(t)代表經過t次迭代后路徑代價最小的任務序列方案；

S1.2.3.5、利用信息素揮發因子ρ和信息素常系數Q更新每條路徑上的信息素；

Tau＝(1-ρ)*Tau+Q/Length(k) (公式16)

在公式16中，Length(k)代表螞蟻k的路徑長度，單位為米，Tau代表任務j_i和任務j_j連接路徑上的信息素濃度；

S1.2.4、判斷是否達到最大迭代次數，如果當前迭代次數小于最大迭代次數n，則重復執行步驟S1.2.3至步驟S1.2.4，直到當前迭代次數等于最大迭代次數n，則輸出最優任務序列方案；

S2、路徑規劃；

根據初始環境信息建立環境地圖模型，根據步驟S1獲得的最優任務分配方案、最優任務序列方案以及動靜態障礙物、任務地塊之間的路徑代價、路徑平滑因素，通過改進蟻群算法進行路徑規劃，獲得最優路徑規劃方案，尋求一條無碰撞的最優路徑；

S2.1、全局路徑規劃；

S2.1.1、根據初始環境信息建立環境地圖模型；

S2.1.2、參數初始化；設置改進蟻群算法相關參數，包括螞蟻數量m、信息素重要程度因子α、啟發函數重要程度因子β、信息素揮發因子ρ、信息素常系數Q以及最大迭代次數n；

S2.1.3、根據任務規劃生成的最優任務序列方案，通過公式1計算每個作業農機與指定任務地塊之間的路徑代價，即作業農機與最優任務序列方案中下一個待完成任務地塊的距離；

D(i,j)＝sqrt(sum((worker(i,:)-task(j,:)).^2)) (公式1)

在公式1中，worker(i,:)代表農機i的坐標，task(j,:)代表任務j的坐標，D(i,j)代表農機i和任務j之間的路徑代價，單位為米；

S2.1.4、每只螞蟻根據轉移概率選擇下一個節點；

在公式11和公式12中，Eta代表啟發函數；Tau代表節點s_i和節點s_j連接路徑上的信息素濃度；P代表轉移概率；

S2.1.5、將已訪問過的節點放到節點禁忌表TABUkm中；

S2.1.6、計算每只螞蟻相應規劃方案的路徑長度，記錄路徑代價最小的路徑規劃方案；

Length(k)＝Length(k)+D(s,s+1) (公式13)

min_Length＝min(Length) (公式14)

Length_best(t)＝min(Length_best(t-1),min_Length) (公式15)

在公式13至公式15中，D(s,s+1)代表節點s和節點s+1之間的路徑代價，單位為米；Length(k)代表螞蟻k的路徑長度，單位為米；min_Length代表每次迭代中m只螞蟻中路徑代價最小的路徑規劃方案；Length_best(t)代表經過t次迭代后路徑代價最小的路徑規劃方案；

S2.1.7、利用信息素揮發因子ρ和信息素常系數Q更新每條路徑上的信息素；

Tau＝(1-ρ)*Tau+Q/Length(k) (公式16)

在公式16中，Length(k)代表螞蟻k的路徑長度，單位為米，Tau代表節點s_i和節點s_j連接路徑上的信息素濃度；

S2.1.8、判斷是否達到最大迭代次數，如果當前迭代次數小于最大迭代次數n，則重復執行步驟S2.1.4至步驟S2.1.8，直到當前迭代次數等于最大迭代次數n，則輸出最優路徑規劃方案；

S2.2、局部路徑規劃；

S2.2.1、在農機根據步驟S2.1獲得的最優路徑規劃方案行進過程中，利用車載傳感器對周邊環境信息進行實時檢測并上傳至遠程管理平臺，遠程管理平臺將實時采集的周邊環境信息與初始環境信息進行比較，獲得動態環境信息；設置時間閾值并根據動態環境信息，判斷行進前方是否有障礙物，如果行進前方沒有障礙物，則根據最優路徑規劃方案繼續行進；如果行進前方有障礙物，則根據等待時間與時間閾值的關系進行行為決策；

S2.2.2、若等待時間大于時間閾值，則判斷為靜態障礙物；反之，則判斷為動態障礙物；

如果為靜態障礙物，首先繪制障礙物范圍，判斷農機是否可以安全通過，若可以通過，則調整作業路徑以避開障礙物，根據步驟S2.1獲得的最優路徑規劃方案繼續行進；若無法避開障礙物，則根據目標地塊位置和農機當前位置，按照S2.1重新規劃路徑；

如果為動態障礙物，首先繪制障礙物范圍，根據障礙物的位置、運動速度和方向信息，判斷農機是否可以安全通過，若可以，則調整農機作業路線以避開障礙物，繼續沿著全局規劃路線行進；若無法避開障礙物，根據遠程管理平臺發布的各農機當前坐標信息判斷障礙物是否為其他農機，若不是，則直接根據目標地塊位置和農機當前位置，按照S2.1重新規劃路徑；否則，在最小安全距離以外停車，并根據目標地塊位置和農機當前位置，利用公式1計算兩個農機與目標地塊的剩余路徑代價，剩余路徑代價較大的農機按照S2.1重新規劃路徑。