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

在審

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

1.一種基于Voronoi圖的群組機器人自組裝路徑規劃方法，其特征在于：所述方法包括以下步驟：

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

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

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

步驟4：根據當前所有機器人的所在位置，在可活動區域內生成Voronoi圖；

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

2.根據權利要求1所述的一種基于Voronoi圖的群組機器人自組裝路徑規劃方法，其特征在于：所述步驟3中，采用匈牙利算法為每個機器人分配目標點包括以下步驟：

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

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

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

步驟3.4：針對Z₂，從單個0元素的行或列開始，將其中的0元素變為Θ，將這個0元素所在列或行的其它0元素置為Φ，重復，直到處理完所有列或行的單個0元素；

步驟3.5：判斷Z₂中是否還存在0元素，若否，進行下一步，否則，從剩余的0元素最少的行開始，如果0元素不止一個，將標志位Flag置為1并隨機取其中的一個0元素置為Θ，然后將同行同列的其它0元素置為Φ，重復步驟3.5；

步驟3.6：若Θ元素的數目m與n相等，則將所有Θ元素所在位置的元素置為1，其他位置的元素置為0，記為指派矩陣X，進行步驟4；否則，進行下一步；

步驟3.7：記錄沒有Θ元素的行的行坐標，記為集合M，記錄M的行中含有Φ元素的列的列坐標，記為集合N，記錄集合N包含的列中Θ元素的所在行的行坐標，記錄于集合M中，重復，直到滿足條件的行坐標和列坐標全部收錄于集合M或集合N中；

步驟3.8：將沒有記錄于集合M的行的個數與記錄于集合N中的列的個數之和記為l，若l＜n，則進行下一步，若l＝n，判斷Flag是否為1，若是，則返回步驟3.5并以步驟3.3得到的Z₂重新操作，若否，則返回步驟3.4，將處理方式改為列處理或行處理；

步驟3.9：定義M_i∈M，N_i∈N，i∈[1,n]，取矩陣中非的矩陣元素中的最小值，記為a，其中，非指非Z₂矩陣中橫縱坐標由(M_i,N_i)組成的矩陣元素；對所有非M_i行的非0元素減去a，對所有N_i列的非0元素加上a，將矩陣中的Θ元素和Φ元素變回0元素，將更新后的矩陣傳送回步驟3.4中。

3.根據權利要求2所述的一種基于Voronoi圖的群組機器人自組裝路徑規劃方法，其特征在于：若步驟3.8中，l＝n且Flag為1，則返回步驟3.5后，當Z₂中還存在0元素時，從剩余的0元素不止一個且數量最少的行中隨機取出并置為Θ的0元素與所有之前取出的不同。