基於兩層調度的無人集群協同策略重構方法及設備與流程

2024-04-16 07:03:05

1.本發明屬於無人集群多任務調度技術領域，具體涉及一種基於兩層調度的無人集群協同策略重構方法及設備。


背景技術：

2.無人集群系統(如無人車、無人機等)具有響應速度快、使用成本低、部署靈活、可全天時全天候工作等獨特優勢，是未來信息化發展的重要平臺。但是，由於任務複雜性和多樣性，單一平臺或單個傳感器通常難以滿足很多實際任務需求，故而集群協同執行任務逐漸成為趨勢。相比於單一平臺，擁有分布式特徵的無人集群在協同執行任務方面具有諸多潛在優勢：
3.(1)具有分布並行感知、計算和執行能力。可以通過異質傳感器實現平臺互補，實現總任務的分布執行，系統具有較高的容錯性和魯棒性；
4.(2)可提升任務執行能力。能夠完成單智能體完成不好或不能完成的任務，具備良好的包容性和擴展性；
5.(3)具有更高的經濟可承受性。通過合理的布局和協同控制，能夠使用分散式的低成本無人系統實現更多的經濟效益。
6.隨著智能硬體的發展，無人平臺能力愈發豐富。為了充分發揮上述集群協同優勢，需要提出智能化協同策略生成和重構算法。無人集群協同調度問題有以下難點：
7.(1)策略空間維度極高。隨著平臺數量、工作模式、約束條件的增加，可選策略組合數量呈指數上升，尋優難度大；
8.(2)調度實時性要求高。基於現實環境的複雜性與不確定性，協同任務調度具有迫切的實時性要求，需要實時快速生成集群協同策略。
9.上述難點導致目前的任務調度算法難以兼顧。目前的報導以基於規則的算法和群體智能算法為主，但這兩種算法各有缺陷：
10.(1)基於規則的協同任務調度算法大多採用貪婪算法，在當前可用的平臺(傳感器)範圍內，以最低開銷(或最高收益)為準則，將任務依次進行分配。算法時間複雜度低，但全局搜索性弱，易陷入局部最優，往往在整體評估時並非最佳。
11.(2)基於群體智能的協同任務調度算法，通過模擬粒子群、魚群、蟻群等仿生行為或生物進化行為，構造解的種群並不斷迭代尋找最優協同策略。群體智能算法全局搜索能力較強，多數情況下能輸出優於貪心算法的調度方案，但時間複雜度高達(粒子群算法)，處理大規模調度問題時，無法滿足實時性要求。
12.綜上所述，針對大規模無人集群協同策略生成問題，目前亟需提出一種能夠同時兼顧低時間複雜度和高全局搜索能力的算法。


技術實現要素：

13.本發明目的是針對大規模無人集群協同策略重構問題，提出一種基於兩層調度的
無人集群協同策略重構方法及設備，旨在解決平臺/傳感器數量大、工作模式選項多、約束條件複雜、實時性要求高情形下的傳感器調度與任務分配問題，克服了現有無人集群協同調度算法的缺陷，能夠同時兼顧低時間複雜度和高全局搜索能力的算法。當傳感器資源或外界任務輸入發生變化時，本發明提出的基於兩層調度的無人集群協同策略重構方法分為兩個層級，分別完成(1)協同工作模式設定和(2)多任務分配，形成綜合調度方案。本發明的基於兩層調度的無人集群協同策略重構方法具有與貪婪算法相近的時間複雜度，具備優於貪婪算法的全局搜索能力，部分計算過程支持分布式並行處理。
14.具體地說，一方面，本發明提供了一種基於兩層調度的無人集群協同策略重構方法，包括：
15.無人集群協同策略重構問題初始化：設定任務收益、智能體數量、各智能體可選擇的工作模式數量、智能體工作模式約束條件、智能體資源總量、智能體能力與任務需求的匹配網絡、任務開銷、智能體協同策略整體方案輸出格式、輸出的綜合調度方案需滿足的約束、協同策略評價標準；
16.智能體協同工作模式優化：採用粒子群算法實現第一層調度，輸出智能體協同工作模式方案；
17.智能體任務分配：採用市場行為建模結合改進型匈牙利算法實現第二層調度，輸出智能體任務分配方案。
18.進一步的，所述無人集群協同策略重構問題初始化包括：
19.將所述任務收益gain表示為一個1
×
ntask的向量，ntask為並發任務數，向量元素代表每個任務完成的收益；
20.設將所述智能體數量表示為nagent；
21.將各智能體可選擇的工作模式數量，表示為nagent
×
1的向量nmode，nmode的第i個向量元素nmode[i]表示第i個智能體可選的工作模式數；
[0022]
將智能體工作模式約束條件設為每個智能體同一時間只能工作在一種模式下，對於任意一個智能體，其自身的多個工作模式呈現互斥性；
[0023]
將智能體資源總量capacity表示為一個nagent
×
1的元胞數組，capacity的第i個元胞capacity{i}是一個尺寸為nmode[i]
×
1的向量，向量元素數值表示相應智能體的相應工作模式的資源總量。例如第i個智能體的第j個工作模式的資源餘量參見公式1，
[0024]
capacity{i}[j],i∈[1,nagent],j∈[1,nmode[i]]
ꢀꢀ
(公式1)
[0025]
將智能體能力與任務需求的匹配網絡match表示為一個nagent
×
1的元胞數組，match的第i個元胞match{i}是一個尺寸為nmode[i]
×
ntask的矩陣，矩陣元素為邏輯值，1表示智能體能力與任務需求匹配，0表示智能體能力與任務需求不匹配，參見公式2，
[0026]
match{i}[j,k]∈{0,1},i∈[1,nagent],j∈[1,nmode[i]],k∈[1,ntask]
ꢀꢀ
(公式2)
[0027]
將任務開銷cost表示為一個nagent
×
1的元胞數組，cost的第i個元胞cost{i}是一個尺寸為nmode[i]
×
ntask的矩陣，矩陣元素表示相應智能體的工作模式執行相應任務的開銷，第i個智能體的第j個工作模式執行第k個任務的開銷參見公式3，
[0028]
cost{i}[j,k],i∈[1,nagent],j∈[1,nmode[i]],k∈[1,ntask]
ꢀꢀ
(公式3)
[0029]
所述綜合調度方案輸出格式包括智能體協同工作模式選擇方案和任務分配方案，
其中，將經過第一層調度優化後的智能體協同工作模式表徵為nagent
×
1的一維向量idxmode，idxmode的第i個向量元素idxmode[i]∈[1,nmode[i]]表示第i個智能體選擇的工作模式；任務分配方案表徵為nagent
×
ntask的矩陣assignment，矩陣元素為邏輯值，矩陣元素為1，表示所屬列的任務分配給了所屬行的智能體，矩陣元素為0，表示所屬列的任務未分配給所屬行的智能體；
[0030]
設定綜合調度方案約束條件，即輸出的綜合調度方案需滿足以下約束：
[0031][0032][0033]
其中，assignment表示任務分配方案，是一個矩陣；任務開銷cost中元素為cost{i}[j,k]，表示當第i個智能體工作在它的第j個工作模式下時，對該智能體而言，第k個任務的任務開銷；capacity為智能體資源總量，idxmode為智能體協同工作模式，idxmode[i]表示第i個智能體的工作模式，cost{i}[j,k]中的j＝idxmode[i]，nagent為智能體數量，ntask為任務數量；符號表示「對所有」，表示對所有j等於1至ntask之間的數，公式4都成立；公式4表示每個任務最多被執行1次，不存在重複執行的情況；公式5表示分配給每個智能體的任務的開銷之和不能超過該智能體工作模式的資源總量；
[0034]
設定協同策略評價標準包含兩項：任務完成率f和任務收益率s，定義如下：
[0035][0036]
公式6中，nagent為智能體數量，ntask為任務數量，assignment為任務分配方案，gain為任務收益。
[0037]
進一步的，所述智能體協同工作模式優化包括：
[0038]
2-1確定種群規模nparticals、最大迭代次數maxiteration，建立初始粒子種群，隨機初始化各粒子，將各歷史最優粒子idxmode_pi設為該粒子的初始值；
[0039]
2-2設定粒子取值上界idxmode_ub和下界idxmode_lb，分別為：
[0040][0041]
公式7中，ones(nagent,1)表示nagent
×
1的向量元素全為1的向量，nmode表示各智能體可選擇的工作模式數量；
[0042]
2-3計算各粒子適應度fit(idxmode)，包括：
[0043]
將任務開銷針對智能體資源總量進行歸一化，得到歸一化後任務開銷cost'，參見公式8，
[0044][0045]
公式8中，歸一化後任務開銷cost'中元素為cost』{i}[j,k]，表示當第i個智能體工作在它的第j個工作模式下時，對該智能體而言，第k個任務的歸一化任務開銷；nagent為智能體數量，ntask為任務數量，nmode為每個智能體的工作模式數量，是長度為nagent
×
1的向量；
[0046]
建立收益-開銷矩陣g，參見公式9，尺寸為nagent
×
ntask，收益-開銷矩陣g的含義是單位開銷所得收益，
[0047][0048]
對收益-開銷矩陣g每列從大到小排序，取g每列前n項求和，結果組成1
×
ntask行向量g'，再對g'求和，得到各粒子適應度fit(idxmode)，其中，n為小於等於nagent的正整數；
[0049]
2-4根據粒子群中各粒子適應度fit(idxmode)更新歷史最優粒子idxmode_pi，如果當前粒子idxmode的適應度高於歷史最優粒子idxmode_pi的適應度，則將idxmode賦值給idxmode_pi；其它情況下idxmode_pi保持不變，參見公式10，
[0050][0051]
公式10中，idxmode_pi表示歷史最優粒子，fit函數表示求粒子適應度；
[0052]
取全部歷史最優粒子的最優，作為全局最優粒子idxmode_pg，參見公式11，
[0053]
idxmode_pg＝argmax(fit(idxmode_pi))
ꢀꢀ
(公式11)
[0054]
公式11中，argmax函數表示在所有歷史最優粒子idxmode_pi中，選取適應度fit最高的，賦值給全局最優粒子idxmode_pg；
[0055]
2-5計算所有歷史最優粒子的平均值idxmode_m，參見公式12，
[0056][0057]
2-7更新每個粒子的位置；
[0058]
2-8判斷是否符合退出循環條件，若符合，則退出循環，輸出當前的idxmode_pg為優化後的智能體協同工作模式idxmode作為智能體工作模式選擇方案，否則執行步驟2-3。
[0059]
進一步的，所述粒子群算法為量子行為粒子群算法。
[0060]
進一步的，所述更新每個粒子的位置的方法包括：
[0061]
計算自適應擴張因子ω，設當前粒子群迭代次數為m，參見公式13，
[0062]
ω＝ωmax-(m/maxiteration)2×
(ωmax-ωmin)
ꢀꢀ
(公式13)
[0063]
公式13中，ωmax是預設的最大擴張因子，ωmin是預設的最小擴張因子，均為標量數值，m是當前迭代次數，maxiteration是步驟2-1確定的粒子群算法最大迭代次數；
[0064]
引入獨立分布的隨機變量rand1,rand2,rand3，每個隨機變量在0～1區間均勻分布，每個粒子的位置的計算公式參見公式14，
[0065][0066]
公式14中，參數p,b,v是臨時變量，函數log表示自然對數，函數max表示取大，函數min表示取小，參數rand1、rand2、rand3是隨機變量，idxmode_pi是歷史最優粒子，idxmode_pg是全局最優粒子，ω是自適應擴張因子，idxmode_m是歷史最優粒子的平均值，idxmode_lb和idxmode_ub是粒子取值的下界和上界，表示向上取整，[.]表示就近取整。
[0067]
進一步的，所述智能體任務分配包括：
[0068]
3-1初始化任務分配方案assignment，其中任務分配方案assignment的nagent
×
ntask個矩陣元素均設為0；初始化每個智能體剩餘資源量capacity_remain為智能體資源總量capacity；對於第i個智能體，智能體任務分配方案assignment剩餘資源量capacity_remain{i}滿足公式16，
[0069]
capacity_remain{i}＝capacity{i}[idxmode_pg[i]]
ꢀꢀ
(公式16)
[0070]
公式16中，idxmode_pg是智能體工作模式優化步驟中輸出的智能體工作模式選擇方案，idxmode_pg是一個向量，idxmode_pg[i]表示智能體工作模式選擇方案的第i個元素；
[0071]
3-2將全部任務按照收益從大到小排序，存入任務池；
[0072]
3-3按照收益大小順序從任務池讀取與智能體數量相應的個任務，其中0＜α≤1；
[0073]
3-4在市場行為建模下，每個智能體對步驟3-3得到的任務進行報價，第i個智能體對第j個任務的報價準則c[i,j]的計算公式參見公式17，
[0074][0075]
公式16中，idx為智能體工作模式優化步驟中輸出的全局最優idxmode_pg的簡寫，bignum表示第i個智能體無法執行第j個任務時，給出的高額報價；
[0076]
3-5在報價矩陣c右側補零，將報價矩陣c增廣為nagent
×
nagent的方陣c2，以增廣後的報價矩陣c2為輸入，執行標準匈牙利算法，輸出一對一最小匹配結果cout；
[0077]
3-6對步驟3-5輸出的一對一最小匹配結果cout中分配了虛任務的智能體，不將分配結果記錄到任務分配方案assignment中，該智能體的資源餘量不減去相應的任務開銷；對一對一最小匹配結果cout中分配了任務且報價小於高額報價bignum的智能體，將分配結果記錄到任務分配方案assignment中，該智能體的資源餘量減去相應的任務開銷；對一對一最小匹配結果cout中分配了任務且報價大於等於高額報價bignum的智能體，相應任務分配失敗，嘗試重新分配，重新放回任務池，放於任務池最上層；記錄該任務分配失敗次數，當
失敗次數超過設定的最大嘗試次數maxtry時，移除該任務；
[0078]
3-7當任務池不為空，返回步驟3-3，否則結束任務分配，輸出任務分配方案assignment。
[0079]
進一步的，對所述步驟3-3得到的任務進行報價通過分布式計算並行加速。
[0080]
進一步的，所述基於兩層調度的無人集群協同策略重構方法，還包括：
[0081]
當所述智能體資源餘量變動或有新任務輸入時，若計算資源充裕或時間要求不緊迫，進行大閉環跳轉，即跳轉至智能體協同工作模式優化的步驟，更新智能體工作模式選擇方案idxmode_pg和任務分配方案assignment；當時間緊迫時，進行小閉環跳轉，即跳轉至智能體任務分配的步驟，更新任務池和資源餘量，僅計算任務分配方案assignment。
[0082]
另一方面，本發明還提供一種基於兩層調度的無人集群協同策略重構設備，所述設備包括存儲器和處理器；所述存儲器存儲有實現基於兩層調度的無人集群協同策略重構方法的電腦程式，所述處理器執行所述電腦程式，以實現根據上述基於兩層調度的無人集群協同策略重構方法的步驟。
[0083]
再一方面，本發明還提供一種計算機可讀存儲介質，其上存儲有電腦程式，所述的電腦程式被處理器執行時實現上述基於兩層調度的無人集群協同策略重構方法的步驟。
[0084]
本發明的基於兩層調度的無人集群協同策略重構方法及設備的有益效果如下：
[0085]
本發明的基於兩層調度的無人集群協同策略重構方法及設備，時間複雜度遠低於群體智能算法。以粒子群算法為代表的群體智能算法時間複雜度量級高達o(n！)，n為問題的規模。本發明針對的綜合調度問題解的總規模大，若直接使用粒子群算法求解，時間開銷極大。本發明的基於兩層調度的無人集群協同策略重構方法採用兩層調度，先採用具有全局尋優能力的粒子群算法進行粗粒度調度，再採用改進型匈牙利算法進行細粒度調度。因為僅第一層調度使用粒子群算法，且粒子為nagent
×
1的一維向量，使粒子群問題規模縮小數個量級，求解速度快。
[0086]
本發明的基於兩層調度的無人集群協同策略重構方法及設備，第一層調度使用量子行為粒子群算法，降低迭代時計算量。相比於經典粒子群算法，量子行為粒子群算法每步迭代不引入速度矢量。更進一步，使用自適應擴張因子，改善量子行為粒子群算法收斂性。
[0087]
本發明的基於兩層調度的無人集群協同策略重構方法及設備，相比於貪婪算法，本發明算法靈活性更高，全局尋優能力更強，利用第一層調度有效避免了陷入局部最優。
[0088]
本發明的基於兩層調度的無人集群協同策略重構方法，第二層調度中進行了市場行為建模，市場行為建模是一種分布式處理框架，面對實際問題時，問題建模過程中的大量計算內容均可以分布式處理，包括計算任務開銷、計算歸一化開銷、計算智能體能力與任務需求的匹配網絡、存儲和維護智能體資源餘量。在本發明提出的框架下，這些計算均可以並行加速，適用於無人集群應用場景。各智能體報價計算支持分布式並行處理，各智能體僅需讀取和維護自身的資源餘量，無需知曉其他智能體的資源餘量；引入任務池機制，並對池中任務按照優先級排序，供取出分配；採用改進型匈牙利算法，每次先從任務池中讀取個任務，引入虛任務，將報價矩陣增廣為方陣，再以增廣後的報價矩陣為輸入，再執行標準匈牙利算法；引入最大失敗次數，一次分配不成功的任務重新回入任務池，可再次被讀取並參與下次分配，只有分配失敗次數累計達到閾值後的任務才會被捨棄。
[0089]
本發明的基於兩層調度的無人集群協同策略重構方法及設備，既可以處理靜態規劃問題，也可以處理動態任務分配問題。通過選擇兩種循環(大閉環和小閉環)分別用於協同策略重構和任務實時重分配。當新任務持續輸入但無需變更協同模式時，可直接進行第二層調度，第二層調度自成閉環，實現任務實時分配。當智能體資源餘量變動或有新任務輸入時，本發明算法支持不同層級的協同策略重構
附圖說明
[0090]
圖1是本發明實施例的方法流程圖。
[0091]
圖2是本發明實施例的第一層調度算法流程圖。
[0092]
圖3是本發明實施例的第二層調度算法流程圖。
[0093]
圖4是本發明實施例的輸出結果圖。
具體實施方式
[0094]
下面結合實施例並參照附圖對本發明作進一步詳細描述。
[0095]
實施例1：
[0096]
本發明的一個實施例，為一種基於兩層調度的無人集群協同策略重構方法，流程如圖1所示。
[0097]
一、無人集群協同策略重構問題初始化
[0098]
無人集群協同策略重構問題初始化包含讀取任務輸入和問題建模。前者具體為讀取任務的輸入參數，作為已知條件；後者具體為對上述輸入參數進行建模，將輸入參數表徵為各數據結構，以便於後續計算。
[0099]
本發明的基於兩層調度的無人集群協同策略重構方法中，無人集群的基本調度單元是單個無人平臺或單個傳感器，以下內容中統一用智能體指代。無人集群協同策略重構問題的輸入參數建模，包括設定任務收益、智能體數量、各智能體可選擇的工作模式數量、智能體工作模式約束條件、智能體資源總量、智能體能力與任務需求的匹配網絡、任務開銷、智能體協同策略整體方案輸出格式、輸出的綜合調度方案需滿足的約束、協同策略評價標準。
[0100]
設共有ntask個並發任務，則任務收益gain表示為一個1
×
ntask的向量，向量元素代表每個任務完成的收益。
[0101]
設共有nagent個智能體，即智能體數量為nagent。
[0102]
將各智能體可選擇的工作模式數量，表示為nagent
×
1的向量nmode，nmode的第i個向量元素nmode[i]表示第i個智能體可選的工作模式數。
[0103]
智能體工作模式約束條件設為每個智能體同一時間只能工作在一種模式下，對於任意一個智能體，其自身的多個工作模式呈現互斥性。
[0104]
將智能體資源總量capacity表示為一個nagent
×
1的元胞數組，capacity的第i個元胞capacity{i}是一個尺寸為nmode[i]
×
1的向量，向量元素數值表示相應智能體的相應工作模式的資源總量。例如第i個智能體的第j個工作模式的資源餘量為：
[0105]
capacity{i}[j],i∈[1,nagent],j∈[1,nmode[i]]
ꢀꢀ
(公式1)
[0106]
將智能體能力與任務需求的匹配網絡match表示為一個nagent
×
1的元胞數組，
match的第i個元胞match{i}是一個尺寸為nmode[i]
×
ntask的矩陣，矩陣元素為邏輯值，1表示智能體能力與任務需求匹配，0表示智能體能力與任務需求不匹配。具體如下：
[0107]
match{i}[j,k]∈{0,1},i∈[1,nagent],j∈[1,nmode[i]],k∈[1,ntask]
ꢀꢀ
(公式2)
[0108]
將任務開銷cost表示為一個nagent
×
1的元胞數組，cost的第i個元胞cost{i}是一個尺寸為nmode[i]
×
ntask的矩陣，矩陣元素表示相應智能體的工作模式執行相應任務的開銷。任務開銷cost的量綱與智能體資源總量capacity的量綱相統一，可以都設為時間，也可以設為能量。例如，第i個智能體的第j個工作模式執行第k個任務的開銷為：
[0109]
cost{i}[j,k],i∈[1,nagent],j∈[1,nmode[i]],k∈[1,ntask]
ꢀꢀ
(公式3)
[0110]
本發明的基於兩層調度的無人集群協同策略重構方法分為兩個層級，分別完成智能體協同工作模式設定和多任務分配，形成綜合調度方案。定義綜合調度方案輸出格式，包括智能體協同工作模式選擇方案和任務分配方案。其中，將經過第一層調度優化後的智能體協同工作模式表徵為nagent
×
1的一維向量idxmode，idxmode的第i個向量元素idxmode[i]∈[1,nmode[i]]表示第i個智能體選擇的工作模式；任務分配方案表徵為nagent
×
ntask的矩陣assignment，矩陣元素為邏輯值。矩陣元素為1，表示所屬列的任務分配給了所屬行的智能體；矩陣元素為0，表示所屬列的任務未分配給所屬行的智能體。
[0111]
設定綜合調度方案約束條件，即輸出的綜合調度方案需滿足以下約束：
[0112][0113][0114]
其中，assignment表示任務分配方案，是一個矩陣；cost為任務開銷，任務開銷cost中元素為cost{i}[j,k]，表示當第i個智能體工作在它的第j個工作模式下時，對該智能體而言，第k個任務的任務開銷。capacity為智能體資源總量，idxmode為智能體協同工作模式，nagent為智能體數量，ntask為任務數量；符號表示「對所有」，表示對所有j等於1至ntask之間的數，公式4都成立。公式4表示每個任務最多被執行1次，不存在重複執行的情況；公式5表示分配給每個智能體的任務的開銷之和不能超過該智能體工作模式的資源總量。
[0115]
設定協同策略評價標準包含兩項：任務完成率f和任務收益率s。任務完成率物理意義是已分配的任務數量佔總任務數量的比例；任務收益率物理意義是已分配的任務的收益之和佔全部任務總收益的比例。無人集群協同策略重構問題的目標是在其他輸入條件的約束下，最大化任務完成率f和任務收益率s。任務完成率f和任務收益率s的定義如下：
[0116][0117]
根據公式4可知，公式6中任務完成率f和任務收益率s均為大於0小於1的數。公式6
中，nagent為智能體數量，ntask為任務數量，assignment為任務分配方案，gain為任務收益，assignment為矩陣，gain為向量。
[0118]
二、智能體協同工作模式優化
[0119]
第一層調度輸出智能體協同工作模式方案，定義粒子為各智能體工作模式選擇組成的向量，採用粒子群算法實現第一層調度。如圖2所示，此步驟具體流程包括：
[0120]
2-1確定種群規模nparticals、最大迭代次數maxiteration，建立初始粒子種群。
[0121]
每個粒子代表工作模式的一種選擇，每個粒子的格式和含義如前文所述的表徵智能體協同工作模式的向量idxmode。
[0122]
隨機初始化各粒子，將各歷史最優粒子idxmode_pi設為該粒子的初始值。
[0123]
2-2設定粒子取值上界idxmode_ub和下界idxmode_lb，分別為：
[0124][0125]
公式7中ones(nagent,1)表示nagent
×
1的向量元素全為1的向量。nmode表示各智能體可選擇的工作模式數量。
[0126]
2-3計算各粒子適應度fit(idxmode)。
[0127]
將任務開銷針對智能體資源總量進行歸一化，得到歸一化開銷cost'，參見公式8。
[0128][0129]
公式8中，歸一化後任務開銷cost'中元素為cost』{i}[j,k]，表示當第i個智能體工作在它的第j個工作模式下時，對該智能體而言，第k個任務的歸一化任務開銷。nagent為智能體數量，ntask為任務數量，nmode為每個智能體的工作模式數量，是長度為nagent
×
1的向量。
[0130]
建立收益-開銷矩陣g，參見公式9，尺寸為nagent
×
ntask，收益-開銷矩陣g的含義是單位開銷所得收益：
[0131][0132]
對收益-開銷矩陣g每列從大到小排序，取g每列前n項求和，結果組成1
×
ntask行向量g'，再對g'求和，得到各粒子適應度fit(idxmode)。其中，n可取小於等於nagent的正整數。
[0133]
上述各粒子適應度fit(idxmode)的計算綜合考慮了收益-開銷性價比、工作模式資源總量、工作模式互補性。
[0134]
2-4根據粒子群中各粒子適應度fit(idxmode)更新歷史最優粒子idxmode_pi，如果當前粒子idxmode的適應度高於歷史最優粒子idxmode_pi的適應度，則將idxmode賦值給idxmode_pi。其它情況下idxmode_pi保持不變，參見公式10。
[0135][0136]
公式10中，idxmode_pi表示歷史最優粒子，fit函數表示求粒子適應度。
[0137]
取全部歷史最優粒子的最優，設為全局最優idxmode_pg，參見公式11。
[0138]
idxmode_pg＝argmax(fit(idxmode_pi))
ꢀꢀ
(公式11)
[0139]
公式11中，argmax函數表示在所有歷史最優粒子idxmode_pi中，選取適應度fit最高的，賦值給全局最優粒子idxmode_pg。
[0140]
2-5計算所有歷史最優粒子的平均值idxmode_m，參見公式12。
[0141][0142]
以下以採用自適應擴張因子的量子行為粒子群算法為例，介紹更新每個粒子的位置的步驟。可以理解，採用其它類型的粒子群算法，需要將公式13和公式14替換成該類型粒子群算法相應的公式。
[0143]
2-6(可選)計算自適應擴張因子v，設當前粒子群迭代次數為m，參見公式13。
[0144]
ω＝ωmax-(m/maxiteration)2×
(ωmax-ωmin)
ꢀꢀ
(公式13)
[0145]
公式13中，ωmax是預設的最大擴張因子，ωmin是預設的最小擴張因子，均為標量數值。m是當前迭代次數，maxiteration是步驟2-1確定的粒子群算法最大迭代次數。ωmax和ωmin可分別取0.9和0.4。可以看出中，擴張因子ω呈二階變化。
[0146]
若採用粒子群算法或者量子行為粒子群算法更新每個粒子的位置，則不需要步驟2-6。
[0147]
2-7依據量子行為更新每個粒子的位置。
[0148]
引入獨立分布的隨機變量rand1,rand2,rand3，每個隨機變量在0～1區間均勻分布，每個粒子的位置的計算公式參見公式14。
[0149][0150]
公式14中，參數p,b,v是臨時變量，函數log表示自然對數，函數max表示取大，函數min表示取小，參數rand1、rand2、rand3是隨機變量，idxmode_pi是歷史最優粒子，idxmode_pg是全局最優粒子，ω是自適應擴張因子，idxmode_m是歷史最優粒子的平均值，idxmode_lb和idxmode_ub是粒子取值的下界和上界，表示向上取整，[.]表示就近取整。
[0151]
2-8判斷是否退出循環。
[0152]
引入最小迭代次數miniteration，定義如下：
[0153]
miniteration＝[maxiteration/3]
ꢀꢀ
(公式15)
[0154]
公式15中，maxiteration是步驟2-1定義的最大迭代次數，[.]表示就近取整數。
[0155]
如果當前迭代次數m大於最大迭代次數maxiteration，則循環退出，輸出當前的全局最優粒子idxmode_pg為優化後的智能體協同工作模式idxmode，作為智能體工作模式選擇方案，否則執行步驟2-3。當算法持續運轉時，全局最優粒子idxmode_pg不固定，會隨著迭
代次數增長而改變，不斷地向更優的解靠近。在每一次迭代時，都存儲這一步的全局最優的適應度fit(idxmode_pg)，作為歷史值用於比較。第m次迭代的全局最優適應度fit(idxmode_pg)相比於第(m-miniteration)次迭代時的全局最優適應度(即存儲的第(m-miniteration)次迭代的全局最優歷史值)不再增長，則表明算法已經收斂，全局最優idxmode_pg已經不隨迭代次數增加而改變，沒有必要繼續迭代下去了，循環退出。引入最小迭代次數作為退出粒子群迭代的條件之一，使得量子行為粒子群算法有充裕的時間跳出局部最優。
[0156]
三、智能體任務分配
[0157]
第二層調度輸出智能體任務分配方案，採用市場行為建模結合改進型匈牙利算法實現。如圖3所示，具體包括以下步驟。
[0158]
3-1初始化任務分配方案assignment，assignment是一個矩陣，共有nagent
×
ntask個矩陣元素。nagent
×
ntask個矩陣元素均設為0。初始化每個智能體剩餘資源量capacity_remain為智能體資源總量capacity。對於第i個智能體，智能體剩餘資源量滿足公式16：
[0159]
capacity_remain{i}＝capacity{i}[idxmode_pg[i]]
ꢀꢀ
(公式16)
[0160]
公式16中，idxmode_pg是步驟二最終輸出的智能體工作模式選擇方案，idxmode_pg是一個向量，idxmode_pg[i]表示智能體工作模式選擇方案的第i個元素。
[0161]
3-2更新任務池。將全部任務按照收益從大到小排序，存入任務池。
[0162]
3-3按照收益大小順序從任務池讀取與智能體數量相應的任務，例如個任務，其中0＜α≤1，可取0.75。
[0163]
3-4在市場行為建模下，每個智能體對步驟3.3得到的任務進行報價，第i個智能體對第j個任務的報價準則c[i,j]的計算公式參見公式17：
[0164][0165]
公式17中，idx為智能體工作模式優化步驟中輸出的全局最優idxmode_pg的簡寫，bignum表示第i個智能體無法執行第j個任務時，給出的高額報價，bignum設為一個較大的數，例如100。當第i個智能體可以執行第j個任務時，報價與任務對該智能體而言的開銷(成本)呈正相關，與任務收益(利益)呈負相關，與該智能體資源餘量(資金)呈負相關。
[0166]
現有的集中式計算報價的算法必須使用全部智能體的信息，由中心處理器通過通信網絡收集全部智能體上存儲的信息後才能計算報價，計算速度較慢，不能分布式並行計算。優選的，在另一個實施例中，對步驟3-4得到的任務進行報價可通過分布式計算並行加速。本發明的基於兩層調度的無人集群協同策略重構方法中計算報價算法是分布式的，每個智能體只需依據自身存儲和維護的信息，即可獨立地給出報價，在計算報價環節，無需智能體之間的通信，且計算速度更快。
[0167]
3-5通過引入虛任務，即在報價矩陣c右側補零，將報價矩陣c增廣為nagent
×
nagent的方陣c2。以增廣後的報價矩陣c2為輸入，執行標準匈牙利算法，輸出一對一最小匹配結果cout。一對一最小匹配結果指給每個智能體分配且僅分配一個任務。
[0168]
3-6對步驟3.5輸出的一對一最小匹配結果cout中分配了虛任務的智能體，不將分
配結果記錄到任務分配方案assignment中，該智能體的資源餘量不減去相應的任務開銷；對一對一最小匹配結果cout中分配了任務且報價小於高額報價bignum的智能體，將分配結果記錄到任務分配方案assignment中，該智能體的資源餘量減去相應的任務開銷；對一對一最小匹配結果cout中分配了任務且報價大於等於高額報價bignum的智能體，相應任務分配失敗，嘗試重新分配，重新放回任務池，放於任務池最上層，放於任務池最上層的任務在下次讀取任務時會被優先取出。記錄該任務分配失敗次數，當失敗次數超過設定的最大嘗試次數maxtry時，移除該任務。可取maxtry＝nagent
×
2。其中，nagent是智能體數量
[0169]
3-7當任務池不為空，返回步驟3.3，否則結束任務分配，輸出任務分配方案assignment。
[0170]
四、輸出無人集群協同策略重構綜合方案，包括智能體工作模式選擇方案idxmode_pg和任務分配方案assignment。
[0171]
優選的，在另一個實施例中，當參與組網的智能體數量、工作模式發生變化，例如設備損毀、新設備接入時，重新從步驟一開始執行上述步驟，進行協同策略重構。
[0172]
優選的，在另一個實施例中，當智能體資源餘量變動或有新任務輸入時，本發明的基於兩層調度的無人集群協同策略重構方法支持根據實時性要求等約束，進行不同方式的迭代，實現不同層級的協同策略重構。具體而言，當計算資源充裕或時間要求不緊迫時，可進行大閉環跳轉，即跳轉至步驟一，更新無人集群協同策略重構綜合方案，包括智能體工作模式選擇方案idxmode_pg和任務分配方案assignment；當時間緊迫時，可進行小閉環跳轉，即直接跳轉至步驟3.2，在不改變協同模式的情況下，更新任務池和資源餘量，僅計算任務分配方案assignment，以滿足高實時性要求。
[0173]
實施例2：
[0174]
本發明的另一個實施例，為一種基於兩層調度的無人集群協同策略重構方法，重構5個智能體協同策略。當智能體資源餘量變動或有新任務輸入時，本實施例的基於兩層調度的無人集群協同策略重構方法更新無人集群協同策略重構綜合方案，包括智能體工作模式選擇方案idxmode_pg和任務分配方案assignment。
[0175]
具體包括如下步驟：
[0176]
一、使用蒙特卡洛方法生成協同策略重構問題輸入參數，包括：
[0177]
參照實施例1中步驟一，隨機生成各智能體可選擇的工作模式數量(nmode向量)、智能體資源總量、任務收益gain、智能體能力與任務需求匹配網絡、任務開銷cost。
[0178]
本實施例中5個智能體可選工作模式數分別為[3,3,4,2,2]。智能體資源總量如圖4右側數字所示，圖4右側的數字表示每個智能體每個工作模式的資源總量，例如從上到下前三個數值為智能體1的三個工作模式各自的資源總量。圖4上半部分表示智能體能力與任務需求匹配網絡，其中，染色格點表示能力匹配，顏色深淺正比於任務收益，將任務收益從左到右由大到小排序，智能體能力與任務需求匹配網絡隨之重排。圖4下半部分表示任務分配方案。
[0179]
二、執行第一層調度，輸出智能體協同工作模式方案，參照實施例1中步驟二。具體包括：
[0180]
2.1設置種群規模nparticals為20，最大迭代次數maxiteration為100，設置粒子下界為[1,1,1,1,1]，粒子上界為[3,3,4,2,2]，初始化種群。
[0181]
2.2計算各粒子適應度，更新每個歷史最優粒子，計算所有歷史最優粒子的平均值，計算自適應擴張因子，根據量子行為更新每個粒子的位置，參見公式8～公式14，並執行粒子群迭代。
[0182]
2.3滿足迭代退出條件時，輸出協同工作模式方案idxmode。本實施例中，經過量子行為粒子群算法，第一層調度輸出的協同模式idxmode即為量子行為粒子群算法計算出的全局最優協同模式idxmode_pg，idxmode_pg＝[2,1,1,2,2]。優化後的各智能體的協同工作模式idxmode在圖4的右側用方框標明，從圖4中可見，第1個智能體選擇第2個工作模式，第2個智能體選擇第1個工作模式，智能體3採用第1個工作模式，智能體4採用第2個工作模式，智能體5採用第2個工作模式。
[0183]
三、執行第二層調度，輸出智能體的任務分配方案，參照實施例1中步驟三。
[0184]
3.1將任務分配方案assignment初始化為5
×
100全零矩陣，各智能體資源餘量初始化為資源總量[64,67,67,65,67]。
[0185]
3.2將任務按收益從高到低排序，放入任務池。
[0186]
3.3從任務池中每次取4個任務。
[0187]
3.4各智能體分布式計算對上述從任務池中取出的4個任務的報價，計算公式參見公式15，其中，bignum取100，得到大小為5
×
4的報價矩陣c。
[0188]
3.5將報價矩陣c右側補零，增廣為5
×
5的方陣c2，以c2為輸入執行匈牙利算法，得到一對一最小匹配結果cout。
[0189]
3.6對得到的一對一最小匹配結果cout中分配了報價為0的任務的智能體，不將分配結果記錄到任務分配方案assignment中，該智能體的資源餘量不減去相應的任務開銷；對一對一最小匹配結果cout中分配了任務且報價小於100的智能體，將分配結果記錄到任務分配方案assignment中，該智能體的資源餘量減去相應的任務開銷；對一對一最小匹配結果cout中分配了任務且報價大於等於100的智能體，相應任務分配失敗，重新放回任務池，放於任務池最上層，記錄該任務分配失敗次數，當累計失敗次數超過10次時，移除該任務，該任務不再嘗試分配。
[0190]
3.7當任務池不為空，返回3.3步，否則結束任務分配，輸出任務分配方案assignment。本實施例中，任務分配方案assignment如圖4下方所示，可見100個任務中共有97個被成功分配，另外3個任務累計分配失敗次數超過10次，未能分配給智能體。
[0191]
四、輸出無人集群協同策略重構綜合方案，包括步驟2.3得到的工作模式選擇方案idxmode_pg和步驟3.7得到的任務分配方案assignment。
[0192]
實施例3：
[0193]
本發明的另一個實施例，採用基於兩層調度的無人集群協同策略重構方法進行實時任務分配。
[0194]
如圖1中小閉環所示，實時任務分配場景下智能體工作模式已經確定，無需再執行第一層調度。
[0195]
當智能體資源餘量變動或有新任務輸入時，本實施例的基於兩層調度的無人集群協同策略重構方法在不改變協同模式的情況下更新任務池和資源餘量，僅計算任務分配方案assignment，以滿足高實時性要求。本實施例僅針對第二層調度進行介紹，流程主要參考圖3所示。
[0196]
1.將任務分配方案assignment初始化為不定長矩陣，行數為nagent，列數不固定(因為不能確定未來輸入的任務數)，assignment用於記錄任務的歷史分配結果。初始化智能體資源餘量。初始化任務池並按任務收益從大到小排序。
[0197]
2.檢查新輸入的任務，將新輸入的任務按優先級採用插入排序方式存入任務池。
[0198]
3.從任務池讀取個任務，其中，0＜α≤1，可取0.75。
[0199]
4.在市場行為建模下，每個智能體對任務進行分布式報價，計算公式參見公式15，得到報價矩陣c。
[0200]
5.將報價矩陣c右側補零，增廣為nagent
×
nagent的方陣c2。以增廣後的報價矩陣c2為輸入，執行標準匈牙利算法，輸出一對一最小匹配結果cout。
[0201]
6.對得到的一對一最小匹配結果cout中任務——智能體最小匹配結果進行判斷處理，處理規則與實施例1中步驟3.6相同。將成功分配的任務依次記入任務分配方案assignment，各智能體更新資源餘量；需要重新分配的任務按優先級插入排序放入任務池；累計分配失敗次數超過閾值的任務判定為捨棄。
[0202]
7.在任務執行同時，當智能體反饋任務執行完成時，相應智能體資源餘量增加，增量為該任務的開銷，各智能體更新自身資源餘量。
[0203]
返回步驟2。
[0204]
本發明的基於兩層調度的無人集群協同策略重構方法及設備，時間複雜度遠低於群體智能算法。以粒子群算法為代表的群體智能算法時間複雜度高達o(n！)，n為問題的規模。本發明針對的綜合調度問題解的總規模大，若直接使用粒子群算法求解，時間開銷極大。本發明的基於兩層調度的無人集群協同策略重構方法採用兩層調度，僅第一層調度使用粒子群算法，且粒子為nagent
×
1的一維向量，使粒子群問題規模縮小數個量級，求解速度快。
[0205]
本發明的基於兩層調度的無人集群協同策略重構方法及設備，第一層調度使用量子行為粒子群算法，降低迭代時計算量。相比於經典粒子群算法，量子行為粒子群算法每步迭代不引入速度矢量。更進一步，使用自適應擴張因子，改善量子行為粒子群算法收斂性。
[0206]
本發明的基於兩層調度的無人集群協同策略重構方法及設備，相比於貪婪算法，本發明算法靈活性更高，全局尋優能力更強，利用第一層調度有效避免了陷入局部最優。
[0207]
本發明的基於兩層調度的無人集群協同策略重構方法，第二層調度中進行了市場行為建模，支持分布式計算與並行處理，適用於無人集群應用場景。
[0208]
本發明的基於兩層調度的無人集群協同策略重構方法及設備，既可以處理靜態規劃問題，也可以處理動態任務分配問題。通過選擇兩種循環(大閉環和小閉環)分別用於協同策略重構和任務實時重分配。當新任務持續輸入但無需變更協同模式時，可直接進行第二層調度，實現任務實時分配。
[0209]
雖然本發明已以較佳實施例公開如上，但實施例並不是用來限定本發明的。在不脫離本發明之精神和範圍內，所做的任何等效變化或潤飾，同樣屬於本發明之保護範圍。因此本發明的保護範圍應當以本技術的權利要求所界定的內容為標準。