[發明專利]一種基于改進PI算法的分布式多AUV任務分配方法

在審

• 申請號: 202110038319.3
• 申請日: 2021-01-12
• 公開（公告）號: CN112862251A
• 公開（公告）日: 2021-05-28
• 發明（設計）人: 楊惠珍;王強
• 申請（專利權）人: 西北工業大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 華金

1.一種基于改進PI算法的分布式多AUV任務分配方法，其特征在于，包括以下步驟：

步驟1：定義有n個AUV(v₁,v₂,...,v_n)，需要執行m個任務(t₁,t₂,...,t_m)；采用集中式的方法對需要執行的任務進行預分配，預分配結果使得對應位置的AUV執行對應位置的任務，得出的分配結果作為分布式任務分配的迭代初值，并開始迭代過程；

步驟2：對步驟1中AUV進行分區塊配置，其中每個塊中的AUV的數量大于等于2，且要求所有塊的并集包含通信圖的所有邊緣；每個AUV根據塊配置確定本次迭代自身所屬的塊，并計算塊內總任務其中，T′表示塊內總任務，T^j表示塊內成員的執行任務集合，B表示當前塊；

步驟3：基于性能影響算法(PI算法)，得到共識后的任務分配結果；

步驟4：判斷步驟3中的分配任務結果和上次的迭代一樣，則進入任務交換階段；否則，跳至步驟5；其中進入任務交換階段包括以下子步驟：

子步驟4.1：AUV將對自身所在塊內的所有任務執行步驟4.2至步驟4.12以其中的某一任務Task_p為例；

子步驟4.2：由任務分配列表β找出Task_p所屬的AUV，記為v_i；

子步驟4.3：找出塊內除了v_i的所有AUV所包含的任務集合T^*＝T′\a_i；

子步驟4.4：對T^*內的所有任務，循環執行步驟4.5至步驟4.9；

子步驟4.5：將當前所要交換的任務記為Task_q；

子步驟4.6：由任務分配列表β找出Task_q所屬的AUV，記為v_j；

子步驟4.7：找出當v_i放棄執行Task_p轉而去執行Task_q的收益，記為

子步驟4.8：找出當v_j放棄執行Task_q轉而去執行Task_p的收益，記為

子步驟4.9：如果則將profit及Task_p、Task_q作為一組數據記錄在表Data中；

子步驟4.10：找出表Data中profit最大的數據所對應的Task_p、Task_q；

子步驟4.11：更新任務分配列表β，β_p＝j,β_q＝i；

子步驟4.12：更新RPI列表γ_p，其中找出v_i放棄執行Task_p轉而去執行Task_q則所執行的所有任務的RPI變化情況，并在對應任務位置更新γ_p；v_j同上；

步驟5：若更新結果已經收斂，則結束；否則，跳至步驟2，進行新一輪任務分配。

2.如權利要求1所述的一種基于改進PI算法的分布式多AUV任務分配方法，其特征在于，所述步驟3中的PI算法采用A Heuristic Distributed Task Allocation Method forMultivehicle Multitask Problems and Its Application to Search and RescueScenario及A novel distributed scheduling algorithm for time-critical multi-agent systems文中的描述。

3.如權利要求1所述的一種基于改進PI算法的分布式多AUV任務分配方法，其特征在于，所述步驟2中的分區塊配置采用The block-information-sharing strategy for taskallocation:A case study for structure assembly with aerial robots文中的塊配置。