[發(fā)明專利]一種基于Voronoi-APF算法的群組機器人路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202110255098.5
• 申請日: 2021-03-09
• 公開（公告）號: CN113110412B
• 公開（公告）日: 2022-06-14
• 發(fā)明（設計）人: 侯向輝;王雪龍;李亞倫;陳傳聰;蔡鑫偉
• 申請（專利權）人: 浙江工業(yè)大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 杭州之江專利事務所(普通合伙) 33216
• 代理人: 張慧英

本發(fā)明涉及一種基于Voronoi?APF算法的群組機器人路徑規(guī)劃方法，首先利用柵格法進行環(huán)境建模，并對障礙物進行預處理；然后采用匈牙利算法和替換策略為群組機器人進行目標指派；最后通過群組機器人的實時位置構建Voronoi圖，各機器人各自使用人工勢場算法進行路徑規(guī)劃，并對其運動空間進行劃分，限制其路徑在構建的Voronoi圖的對應分割空間中，即機器人單次運動到終點或分隔空間的邊界便停止；重復該步驟，直到所有群組機器人到達指定終點。本發(fā)明在時間消耗和路徑長度上的改進效果，另外在通用性、時間消耗、路程消耗方面都有著一定程度的優(yōu)化。

技術領域

本發(fā)明涉及計算機人工智能技術領域，尤其涉及一種基于Voronoi-APF算法的群組機器人路徑規(guī)劃方法。

背景技術

自組裝是群組機器人協(xié)作中的重要研究領域，為了達成目標配置，路徑規(guī)劃尤為關鍵。路徑規(guī)劃和障礙躲避是該領域的核心問題。而在復雜的實際應用環(huán)境中，保證機器人之間的碰撞避免和躲避地圖障礙物問題則越來越受重視。人工勢場算法(APF)及其改進在機器人路徑規(guī)劃中應用廣泛但其在動態(tài)目標指派、迭代速度、機器人抖動等方面表現(xiàn)不盡如人意，其中在OAPF算法中，距離因子即指在原人工勢場算法的斥力計算公式中添加距離要素，該方法的引入導致機器人路徑規(guī)劃與機器人運動終點高度緊密聯(lián)系。而在復雜地圖中單純考慮距離要素并不一定達成最優(yōu)規(guī)劃。例如外圍的機器人優(yōu)先到達終點將導致內圍機器人無法進入。當機器人在越過復雜地形后需要交換目標點時，若不考慮動態(tài)指派策略，勢必會影響算法的魯棒性和收斂性。

在碰撞避免問題上，雖然OAPF算法將機器人自身以外的個體視作障礙物，很好地解決了碰撞問題。但是，這意味著在每一次迭代過程中，每個機器人都需要知道其他所有機器人當前位置以構建斥力場，考慮實際情況下的機器人通訊問題，這個問題極大程度地限制了模型的效率與實際應用。

在OAPF算法中，通過限制機器人單次迭代中運動的步長來避免機器人同時運動時發(fā)生碰撞，大大增加算法復雜度，所以導致完成目標配置的時間開銷提升同時群組機器人逐漸聚集導致機器人之間的斥力勢增大，機器人則越不容易接近目標點，路程方面的開銷勢必增加。

通過以上分析可知，人工勢場改進算法OAPF不適應動態(tài)的目標指派策略，在該方面有較大的改進空間，其次，機器人之間的斥力勢，雖然解決了機器人間的碰撞問題，但大大降低了算法的性能和實際應用的可行性。

發(fā)明內容

本發(fā)明為克服上述的不足之處，目的在于提供一種基于Voronoi-APF算法的群組機器人路徑規(guī)劃方法，本發(fā)明首先使用匈牙利算法和替換策略為各機器人指定目標點，然后通過群組機器人的實時位置構建Voronoi圖，各機器人各自使用人工勢場算法進行路徑規(guī)劃，限制其路徑在構建的Voronoi圖的對應分割空間中，即機器人單次運動到終點或分隔空間的邊界便停止。重復以上步驟，直到所有機器人到達指定終點。VAPF算法既保留人工勢場算法的優(yōu)勢，又實現(xiàn)了機器人間的碰撞避免。通過matlab仿真對比實驗可證明其在時間消耗和路徑長度上的改進效果。本發(fā)明在通用性、時間消耗、路程消耗方面都有著一定程度的優(yōu)化。

本發(fā)明是通過以下技術方案達到上述目的：一種基于Voronoi-APF算法的群組機器人路徑規(guī)劃方法，包括如下步驟：

(1)利用柵格法進行環(huán)境建模，并對障礙物進行預處理；

(2)采用匈牙利算法和替換策略為群組機器人進行目標指派；

(3)通過群組機器人的實時位置構建Voronoi圖，各機器人各自使用人工勢場算法進行路徑規(guī)劃，并對其運動空間進行劃分，限制其路徑在構建的Voronoi圖的對應分割空間中，即機器人單次運動到終點或分隔空間的邊界便停止；重復該步驟，直到所有群組機器人到達指定終點。

作為優(yōu)選，所述基于Voronoi-APF算法的群組機器人路徑規(guī)劃方法還包括步驟(4)，對群組機器人的運動控制進行優(yōu)化，實現(xiàn)群組機器人的運動控制。