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

有效

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

本發(fā)明提供一種面向動態(tài)任務(wù)的多機(jī)器人分布式任務(wù)分配形成方法，該方法包括：根據(jù)環(huán)境地圖中任務(wù)點(diǎn)狀態(tài)變化，分析任務(wù)分配需要考慮的因素和難點(diǎn)，任務(wù)點(diǎn)發(fā)生時，基于多階段拍賣算法，生成任務(wù)分配方案，機(jī)器人根據(jù)所述任務(wù)分配方案執(zhí)行任務(wù)。本發(fā)明解決了環(huán)境中動態(tài)任務(wù)分配問題，傳統(tǒng)的拍賣算法采用的一次分配來解決給定的任務(wù)，在面對動態(tài)任務(wù)存在很大局限性。本發(fā)明通過多次拍賣，以時間最優(yōu)為目的，最大程度的利用機(jī)器人的資源，將上述方法在VC++和Csharp平臺上進(jìn)行仿真，通過大量的實(shí)驗(yàn)仿真測試結(jié)果表明，改進(jìn)的拍賣算法較傳統(tǒng)的拍賣算法更能夠很好的解決環(huán)境中的動態(tài)任務(wù)，通過多次分配來滿足實(shí)時性的需求，并能夠給出接近的最優(yōu)解。

技術(shù)領(lǐng)域

本發(fā)明涉及機(jī)器人智能拍賣算法技術(shù)領(lǐng)域，更具體地，涉及一種面向動態(tài)任務(wù)的多機(jī)器人分布式任務(wù)分配形成方法。

背景技術(shù)

隨著人們對人工智能和復(fù)雜系統(tǒng)認(rèn)識的深入，機(jī)器人系統(tǒng)在建筑、軍事、消防、工業(yè)生產(chǎn)等領(lǐng)域有了良好的應(yīng)用前景。而當(dāng)前多機(jī)器人系統(tǒng)中任務(wù)數(shù)量大，任務(wù)點(diǎn)包含信息復(fù)雜，參與的機(jī)器人眾多，全局搜索算法的計算代價呈現(xiàn)指數(shù)增長，這使得全局搜索算法很難在規(guī)定的時間內(nèi)尋找到任務(wù)分配問題的最優(yōu)解。因此，全局搜索算法并不適用大規(guī)模多智能體動態(tài)任務(wù)分配問題的求解。在大規(guī)模系統(tǒng)中任務(wù)分配須滿足實(shí)時性的要求，傾向于在規(guī)定的時間內(nèi)得到“好”的解，而得到的解并不一定是最優(yōu)解。因此對于時間約束的多機(jī)器人動態(tài)任務(wù)分配問題研究具有重要意義。

當(dāng)前任務(wù)分配很多采用拍賣算法，傳統(tǒng)的拍賣算法面向任務(wù)是靜態(tài)的，采用的是一次拍賣算法。但在面對任務(wù)點(diǎn)數(shù)量多且動態(tài)變化情況下存在很大的缺陷，無法實(shí)行更多次調(diào)度，不能滿足實(shí)時性的需要，更得不到理想的效果。

發(fā)明內(nèi)容

本發(fā)明提供一種克服上述問題或者至少部分地解決上述問題的面向動態(tài)任務(wù)的多機(jī)器人分布式任務(wù)分配形成方法，該方法基于改進(jìn)的拍賣算法，以及結(jié)合A-star算法路徑尋優(yōu)，通過機(jī)器人之間協(xié)同合作解決環(huán)境中多個動態(tài)任務(wù)的問題。

為了達(dá)到上述目的，本發(fā)明提供一種面向動態(tài)任務(wù)的多機(jī)器人分布式任務(wù)分配形成方法，該方法包括：

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

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

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

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

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

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

其中，任務(wù)用字母j表示，其中j＝1,2,…,N，任務(wù)在地圖上近似于一個點(diǎn)。機(jī)器人用字母i表示，其中i＝1,2,…,M。障礙物用字母b表示，其中b＝1,2,…,B。

任務(wù)點(diǎn)在地圖上的坐標(biāo)為其中j＝1,2,…,N；機(jī)器人在地圖上的坐標(biāo)為其中i＝1,2…M；障礙物在地圖上的坐標(biāo)為其中k＝1,2,…,B。

任務(wù)點(diǎn)與機(jī)器人之間的距離公式為：

假定任務(wù)點(diǎn)j坐標(biāo)與任務(wù)點(diǎn)j'坐標(biāo)分別為則兩者之間距離公式為：