[發明專利]一種面向應急的多飛艇對地觀測任務協同分配方法

有效

• 申請號: 201210370878.5
• 申請日: 2012-09-28
• 公開（公告）號: CN102903028A
• 公開（公告）日: 2013-01-30
• 發明（設計）人: 朱曉敏;江建清;邱滌珊;祝江漢;馬滿好
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

1.一種面向應急的多飛艇對地觀測任務協同分配方法，其特征在于包括以下步驟：

第一步，任務動態達到后，將新到任務和等待執行任務按優先級排序，構建飛艇觀測任務集合T，設定待分配任務集合臨時分配任務集合T={T₁,T₂,…,T_n}，任務個數n為正整數，任意一個元任務T_i表示為T_i=(Ta_i,Td_i,Tl_i,P_i),1≤i≤n，其中Ta_i為任務T_i的到達時間，Td_i為任務Ti需求的截止時間，Tl_i為任務T_i需求的持續執行時間，P_i為任務T_i的優先級，表示任務T_i的重要程度；

第二步，將滿足基本能力約束的任務加入到待分配任務集合AT中；

2.1，判斷T是否為空，如果為空，轉第三步；如果不為空，則執行2.2步；

2.2，按優先級順序從T中取出任務T_i，將T_i與資源進行匹配；

2.3，如果任務T_i與資源匹配成功，轉2.4步；否則轉2.5步；

2.4，將任務T_i加入待分配任務集合AT中，之后將任務T_i從T中移除，轉2.1步；

2.5，將任務T_i從T中移除，轉2.1步；

第三步，將待分配任務集合AT中滿足截止期要求的任務放入臨時任務集合TT中，方法是：

3.1，拷貝AT中的所有任務到空集合Temp中；

3.2，判斷Temp是否為空，如果為空，轉第四步；如果不為空，則轉3.3步；

3.3，按優先級順序從Temp中取出任務T_p,1≤p≤n，計算任務T_p的最早可開始執行時間Tb_pj：

Tbpj=max{Tap,Sej+Stjp-1,p}---(4)]]>

其中，Ta_p為任務T_p的到達時間，Se_j為飛艇資源S_j完成已安排任務時刻，為資源S_j在完成任務T_p-1后到執行任務T_p前需準備的時間，表示飛艇資源S_j的可用時間；

3.4，如果任務T_p滿足截止期，即Tb_pj+Tl_p≤Td_p，Tb_pj為T_p的最早開始執行時間，Tl_p為T_p需求的持續執行時間，Td_p為T_p的截止期，轉第3.5步；如果Tb_pj+Tl_p>Td_p，將T_p從集合Temp中移除，轉3.2步；

3.5，將任務T_p加入到臨時分配任務集合TT中，之后將T_p從集合Temp中移除，轉3.2步；

第四步，如果TT不為空，轉第五步，如果TT為空，轉第十七步；

第五步，將TT中任一任務映射為一個任務Agent，即一個任務對應一個任務Agent，T_k映射成的Agent表示為1≤k≤n，將資源集合S中的任一資源映射為一個資源Agent，即一個資源對應一個資源Agent，S_j映射成的Agent表示為1≤j≤m，任務Agent指任務所映射的智能主體，所述資源Agent是指資源所影射的智能主體；

第六步，將所有滿足基本能力約束的發送給管理者Agent?AD_Agent，并將放入資源競爭輪盤集合SA中，即所述管理者Agent是指協調任務Agent和資源Agent的智能主體；

第七步，AD_Agent對SA中發送任務的詳細招標信息，包括任務到達時間Ta_k、持續時間Tl_k、截止時間Td_k和優先權P_k；

第八步，設定緩沖池容量c，

其中，n表示任務個數，s表示放入S^A中的資源個數；

第九步，設定p=0，q=0；

第十步，如果p=c或q=s，轉第十五步；如果p<c且q<s，轉第十一步；

第十一步，計算的正向標值TenderValue_0_kj，方法是：

11.1，計算資源能力富裕度a_kj，a_kj指任務T_k若要分配給資源S_j，任務T_k的開始執行時間具有的可調節時間范圍，對有：

其中，T_dk為任務T_k的截止時間，Tl_k為任務T_k需求的持續執行時間，Se_j為飛艇資源S_j完成已安排任務時刻，為資源S_j在完成任務T_k-1后到執行任務T_k前需準備的時間；

11.2，設定正向標值TenderValue_0_kj：

TenderValue_0_kj=α_kj????（7）

第十二步，如果TenderValue_0_kj≥0，轉第十三步；如果TenderValue_0_ij<0，則轉第十四步；

第十三步，資源投標，設定p=p+1，q=q+1，將放入緩沖池中，資源競爭輪盤旋轉到下一扇區，一個扇區對應資源競爭輪盤集合中的一個資源Agent，轉第十步；所述投標是指資源表示愿意獲得任務的執行權；

第十四步，資源不投標，設定p=p+1，資源競爭輪盤旋轉到下一扇區，轉第十步；

第十五步，采用Max策略對緩沖池中的投標資源進行選擇，確定任務的中標資源方法是：

15.1，計算緩沖池中所有正向招標標值；

15.2，選擇正向招標標值最大的資源中標，即：

∀smA,tenderValue_0km=max{tenderValue_0kj}---(8)]]>

其中tenderValue_0_kj表示緩沖池中所有投標資源的標值；

第十六步，將任務對應的任務T_k從TT中移除，轉第四步；

第十七步，判斷S^A是否為空，如果為空，轉第二十二步；否則轉第十八步；

第十八步，設定集合C為空集，集合D為空集；

第十九步，對S^A中每個資源進行反向招標，計算反向招標標值，方法是：

19.1，將所有招標后資源中標的任務Agent放入集合C中；

19.2，如果集合C不為空，轉19.3步，否則轉第二十步；

19.3，計算集合C中任務的需求緊迫度β_ij，β_ij指任務重要性與任務持續執行時間相對截止期的可調節性的乘積，對有

βij=Piθ·Tli/(Tdi-Tbij)---(9)]]>

θ為常數；

19.4，設定反向標值TenderValue_1_ij；

TenderValue_1ij=βijΣj=1mαij---(10)]]>

19.5，將從集合C中移除，放入集合D中，轉19.2步；

第二十步，采用輪盤賭策略對集合D中的投標任務進行選擇，確定資源的中標任務方法是：

20.1，計算集合D中d個反向投標的資源任務Agent的反向招標標值；

20.2，計算投標方的中標概率p_h：

ph=TenderValue_1jhΣj=1dTenderValue_1ij---(11)]]>

其中，d為集合D中任務個數，對于h為正整數，p_h表示集合D中第h個任務Agent的反向招標標值占D中所有任務Agent的反向招標標值的和的比重，

20.3，選擇反向投標的任務作為中標對象，須滿足：

r為隨機數????（12）

第二十一步，將從資源Agent集合S^A中移除，將從待分配任務集合AT中移除，轉第十七步；

第二十二步，判斷待分配任務集合AT是否為空，如果AT為空，則轉第二十三步；如果AT不為空，則轉第三步；

第二十三步，結束。