[發(fā)明專利]基于Voronoi圖的群組機器人自組裝路徑規(guī)劃方法

在審

• 申請?zhí)枺?/td>: 201810455645.2
• 申請日: 2018-05-14
• 公開（公告）號: CN108681323A
• 公開（公告）日: 2018-10-19
• 發(fā)明（設(shè)計）人: 簡琤峰;盧濤
• 申請（專利權(quán)）人: 浙江工業(yè)大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 杭州賽科專利代理事務(wù)所(普通合伙) 33230
• 代理人: 郭薇

本發(fā)明涉及一種基于Voronoi圖的群組機器人自組裝路徑規(guī)劃方法，將目標點具象化為若干的坐標點，由這些目標點來描述目標配置，通過匈牙利算法在此基礎(chǔ)上分配機器人和目標點之間的對應(yīng)關(guān)系，當機器人與目標點之間的對應(yīng)關(guān)系確定后，分別做機器人與其對應(yīng)目標點之間的連線，相應(yīng)地這條直線會與每個機器人所在的單元有一個交點或目標點已經(jīng)位于單元內(nèi)，如有交點，則這個交點將被作為該機器人下一次運動的目標點，否則直接移動到目標點，如此迭代，使得每個機器人都運動到目標位置。本發(fā)明所實現(xiàn)的路徑規(guī)劃方法在時間消耗、方案適用性以及路徑長度上均有很大程度的提升，目標配置精度高，“死鎖”概率小，節(jié)約時間，減少能源消耗。

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

本發(fā)明涉及一般的控制或調(diào)節(jié)系統(tǒng)；這種系統(tǒng)的功能單元；用于這種系統(tǒng)或單元的監(jiān)視或測試裝置的技術(shù)領(lǐng)域，特別涉及一種數(shù)量較為龐大的機器人群體的自組裝實現(xiàn)且可拓展應(yīng)用于路徑規(guī)劃的基于Voronoi圖的群組機器人自組裝路徑規(guī)劃方法。

背景技術(shù)

群組機器人是指數(shù)量較為龐大的機器人群體，互相關(guān)聯(lián)、各自分配任務(wù)。

現(xiàn)有技術(shù)中，群組機器人自組裝方法普遍存在著耗時長、路徑不合理等缺陷。群組機器人的路徑規(guī)劃方法主要包括領(lǐng)導者-跟隨者策略、行為和規(guī)則方法、基于壓縮voronoi圖實現(xiàn)自組裝的方法。領(lǐng)導者-跟隨者策略通過選舉出領(lǐng)導機器人，其它機器人保持一定距離的跟隨來實現(xiàn)，這一方法存在著精度低，碰撞可能性高等缺陷。行為和規(guī)則方法是將人類或生物群體的活動規(guī)律引入到群組機器人的路徑規(guī)劃當中，這類方法最大的不足在于隨著機器人數(shù)量的增多，時間消耗會大幅增加。基于壓縮Voronoi圖實現(xiàn)自組裝的方法雖然在時間消耗上有較大的改善，但仍存在著目標配置精度低、高維狀態(tài)下“死鎖”頻發(fā)而造成時間損耗再次加長的問題。

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

為了解決現(xiàn)有技術(shù)中存在的問題，本發(fā)明提供一種優(yōu)化的基于Voronoi圖的群組機器人自組裝路徑規(guī)劃方法，在時間消耗、方案適用性以及路徑長度上均有很大程度的提升，節(jié)約時間，減少能源消耗。

本發(fā)明所采用的技術(shù)方案是，一種基于Voronoi圖的群組機器人自組裝路徑規(guī)劃方法，所述方法包括以下步驟：

步驟1：得到目標配置，基于目標配置確認所有目標點的坐標位置、所有機器人的初始位置及可活動區(qū)域；

步驟2：若當前所有機器人到達各自對應(yīng)目標點的坐標位置處，則算法結(jié)束，否則，進行下一步；

步驟3：采用匈牙利算法為每個機器人分配目標點；

步驟4：根據(jù)當前所有機器人的所在位置，在可活動區(qū)域內(nèi)生成Voronoi圖；

步驟5：判斷每個目標點是否在對應(yīng)機器人所在的單元內(nèi)，如是，則直接將機器人移動到目標點，否則，獲得當前機器人到對應(yīng)目標點的連線，取連線與當前機器人所在的單元的交點，將當前機器人移動到所述交點；當所有機器人移動完后，返回到步驟2。

優(yōu)選地，所述步驟3中，采用匈牙利算法為每個機器人分配目標點包括以下步驟：

步驟3.1：建立資源分配的效益矩陣Z₀，Z₀為n*n的矩陣；

步驟3.2：將Z₀以行為單位，每行減去當前行中最小的元素，得到Z₁，Z₁中每行均有至少一個0元素；

步驟3.3：將Z₁以列為單位，每列減去當前列中最小的元素，得到Z₂，Z₂中每列均有至少一個0元素；

步驟3.4：針對Z₂，從單個0元素的行或列開始，將其中的0元素變?yōu)棣ǎ瑢⑦@個0元素所在列或行的其它0元素置為Φ，重復，直到處理完所有列或行的單個0元素；