[發明專利]一種面向動態任務的多機器人分布式任務分配形成方法

有效

• 申請號: 201710015070.8
• 申請日: 2017-01-09
• 公開（公告）號: CN106875090B
• 公開（公告）日: 2020-05-08
• 發明（設計）人: 裘智峰;陳杰;楊寧;陽春華;郭宇騫;桂衛華
• 申請（專利權）人: 中南大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/04;G05D1/02
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王慶龍

1.一種面向動態任務的多機器人分布式任務分配形成方法，其特征在于，包括：

S1：根據環境地圖中信息，理清任務分配需要考慮的因素及難點；

S2：任務發生時，基于多階段拍賣算法，生成任務分配方案，機器人根據所述任務分配方案執行任務；

其中，所述步驟S1中，進一步包括：

S11：給定一張目標環境地圖，所述地圖上分布有多個具有任務執行能力的機器人、屬性隨時間變化的任務點和若干個障礙物；

S12：根據任務點的狀態變化，理清任務分配需要考慮的因素及難點分析；

其中，所述步驟S12中，任務點狀態量隨時間呈現指數函數形式變化，任務點j(j＝1,2,…,N)在(t+1)時刻的狀態量用方程表示為：

式中：

S_j(t+1)，S_j(t):任務j(j＝1,2,…,N)分別在(t+1)和t階段的任務點狀態量；

α_j:第j個任務點的狀態變化率；

β_i:機器人i的執行能力且β_i＞0；

Δt:t與(t+1)之間的時間差；

ε:任務量閾值，設定任務量閾值ε判斷任務是否完成，當s_j(t)＜ε時，表示任務已完成；

m：執行任務j的機器人數量；

其中，所述基于多階段拍賣算法，生成任務分配方案的步驟，具體包括：

確定N個任務點的代理機器人；

計算任務點最佳機器人需求個數S；

代理機器人發布拍賣信息，判斷非代理機器人是否能接收到拍賣信息；

若非代理機器人能接收到拍賣信息，則競拍機器人根據收益函數確定目標任務點，進行競拍，代理機器人確定任務點投標個數n；

若所述任務點投標個數n小于等于所述任務點最佳機器人需求個數S，則將任務點全部接收；否則，收益函數高的n個機器人中標，競拍失敗的機器人選擇就近任務點；

確定分配方案，機器人開始執行任務，有新任務點完成時，任務點完成數目加一；

判斷任務點完成數據是否達到N，若達到，則結束，否則，回到代理機器人發布拍賣信息步驟；

在所述判斷非代理機器人是否能接收到拍賣信息的步驟之后，還包括：

若非代理機器人不能接收到拍賣信息，則通訊盲區的機器人選擇最近的任務點后跳轉至確定分配方案步驟。

2.根據權利要求1所述的方法，其特征在于，所述步驟S11中，所述的環境為機器人工作環境，對給定的環境地圖建立直角坐標系，坐標系以x軸向右為正方向，y軸向上為正方向，并將該工作環境劃分為多個柵格，環境地圖在空間上分布有N(N∈Z⁺)個任務點、M(M∈Z⁺)個機器人以及B(B∈Z⁺)個障礙物，并分別確定每個任務、機器人和障礙物的坐標。

3.根據權利要求1所述的方法，其特征在于，所述步驟S12中，根據任務點的狀態變化，建立任務點狀態模型，分析任務分配需要考慮的因素包括任務點屬性參數和機器人屬性參數，其中，

任務點屬性參數包括：任務點的任務量、任務點的狀態變化率和任務點在環境地圖上所處的位置；

機器人屬性參數包括：運動速度、機器人能力值和機器人在環境地圖上所處的位置。

4.根據權利要求1所述的方法，其特征在于，所述步驟S2中，進一步包括：

S21：檢測到任務時，選擇距離任務點最近的機器人作為代理機器人，若距離數個任務點最近的機器人為同一個機器人i(i＝1,2,…,M)，系統會選擇數個任務點中選擇距離直角坐標系原點最近的任務點的機器人i為其代理機器人；

S22：代理機器人發布拍賣信息給通訊半徑內的競拍機器人，等待反饋；

S23:接收到拍賣信息的競拍機器人根據自身收益函數選擇收益最高的任務點進行投標；

S24：代理機器人收集投標信息，選擇中標的機器人，并通知中標的機器人執行任務；

S25：未中標的競拍機器人和處在通訊盲區的機器人選擇執行最近的任務點。