[發(fā)明專利]一種面向動(dòng)態(tài)任務(wù)的多機(jī)器人分布式任務(wù)分配形成方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710015070.8
• 申請(qǐng)日: 2017-01-09
• 公開（公告）號(hào): CN106875090B
• 公開（公告）日: 2020-05-08
• 發(fā)明（設(shè)計(jì)）人: 裘智峰;陳杰;楊寧;陽春華;郭宇騫;桂衛(wèi)華
• 申請(qǐng)（專利權(quán)）人: 中南大學(xué)
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06;G06Q10/04;G05D1/02
• 代理公司: 北京路浩知識(shí)產(chǎn)權(quán)代理有限公司 11002
• 代理人: 王慶龍

1.一種面向動(dòng)態(tài)任務(wù)的多機(jī)器人分布式任務(wù)分配形成方法，其特征在于，包括：

S1：根據(jù)環(huán)境地圖中信息，理清任務(wù)分配需要考慮的因素及難點(diǎn)；

S2：任務(wù)發(fā)生時(shí)，基于多階段拍賣算法，生成任務(wù)分配方案，機(jī)器人根據(jù)所述任務(wù)分配方案執(zhí)行任務(wù)；

其中，所述步驟S1中，進(jìn)一步包括：

S11：給定一張目標(biāo)環(huán)境地圖，所述地圖上分布有多個(gè)具有任務(wù)執(zhí)行能力的機(jī)器人、屬性隨時(shí)間變化的任務(wù)點(diǎn)和若干個(gè)障礙物；

S12：根據(jù)任務(wù)點(diǎn)的狀態(tài)變化，理清任務(wù)分配需要考慮的因素及難點(diǎn)分析；

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

式中：

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

α_j:第j個(gè)任務(wù)點(diǎn)的狀態(tài)變化率；

β_i:機(jī)器人i的執(zhí)行能力且β_i＞0；

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

ε:任務(wù)量閾值，設(shè)定任務(wù)量閾值ε判斷任務(wù)是否完成，當(dāng)s_j(t)＜ε時(shí)，表示任務(wù)已完成；

m：執(zhí)行任務(wù)j的機(jī)器人數(shù)量；

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

確定N個(gè)任務(wù)點(diǎn)的代理機(jī)器人；

計(jì)算任務(wù)點(diǎn)最佳機(jī)器人需求個(gè)數(shù)S；

代理機(jī)器人發(fā)布拍賣信息，判斷非代理機(jī)器人是否能接收到拍賣信息；

若非代理機(jī)器人能接收到拍賣信息，則競拍機(jī)器人根據(jù)收益函數(shù)確定目標(biāo)任務(wù)點(diǎn)，進(jìn)行競拍，代理機(jī)器人確定任務(wù)點(diǎn)投標(biāo)個(gè)數(shù)n；

若所述任務(wù)點(diǎn)投標(biāo)個(gè)數(shù)n小于等于所述任務(wù)點(diǎn)最佳機(jī)器人需求個(gè)數(shù)S，則將任務(wù)點(diǎn)全部接收；否則，收益函數(shù)高的n個(gè)機(jī)器人中標(biāo)，競拍失敗的機(jī)器人選擇就近任務(wù)點(diǎn)；

確定分配方案，機(jī)器人開始執(zhí)行任務(wù)，有新任務(wù)點(diǎn)完成時(shí)，任務(wù)點(diǎn)完成數(shù)目加一；

判斷任務(wù)點(diǎn)完成數(shù)據(jù)是否達(dá)到N，若達(dá)到，則結(jié)束，否則，回到代理機(jī)器人發(fā)布拍賣信息步驟；

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

若非代理機(jī)器人不能接收到拍賣信息，則通訊盲區(qū)的機(jī)器人選擇最近的任務(wù)點(diǎn)后跳轉(zhuǎn)至確定分配方案步驟。

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

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述步驟S12中，根據(jù)任務(wù)點(diǎn)的狀態(tài)變化，建立任務(wù)點(diǎn)狀態(tài)模型，分析任務(wù)分配需要考慮的因素包括任務(wù)點(diǎn)屬性參數(shù)和機(jī)器人屬性參數(shù)，其中，

任務(wù)點(diǎn)屬性參數(shù)包括：任務(wù)點(diǎn)的任務(wù)量、任務(wù)點(diǎn)的狀態(tài)變化率和任務(wù)點(diǎn)在環(huán)境地圖上所處的位置；

機(jī)器人屬性參數(shù)包括：運(yùn)動(dòng)速度、機(jī)器人能力值和機(jī)器人在環(huán)境地圖上所處的位置。

4.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述步驟S2中，進(jìn)一步包括：

S21：檢測到任務(wù)時(shí)，選擇距離任務(wù)點(diǎn)最近的機(jī)器人作為代理機(jī)器人，若距離數(shù)個(gè)任務(wù)點(diǎn)最近的機(jī)器人為同一個(gè)機(jī)器人i(i＝1,2,…,M)，系統(tǒng)會(huì)選擇數(shù)個(gè)任務(wù)點(diǎn)中選擇距離直角坐標(biāo)系原點(diǎn)最近的任務(wù)點(diǎn)的機(jī)器人i為其代理機(jī)器人；

S22：代理機(jī)器人發(fā)布拍賣信息給通訊半徑內(nèi)的競拍機(jī)器人，等待反饋；

S23:接收到拍賣信息的競拍機(jī)器人根據(jù)自身收益函數(shù)選擇收益最高的任務(wù)點(diǎn)進(jìn)行投標(biāo)；

S24：代理機(jī)器人收集投標(biāo)信息，選擇中標(biāo)的機(jī)器人，并通知中標(biāo)的機(jī)器人執(zhí)行任務(wù)；

S25：未中標(biāo)的競拍機(jī)器人和處在通訊盲區(qū)的機(jī)器人選擇執(zhí)行最近的任務(wù)點(diǎn)。