[發明專利]多智能體在物理空間中的成形方法

在審

• 申請號: 202111241097.1
• 申請日: 2021-10-25
• 公開（公告）號: CN113936115A
• 公開（公告）日: 2022-01-14
• 發明（設計）人: 張偉;趙海燕;褚文杰;金芝;梅宏
• 申請（專利權）人: 北京大學
• 主分類號: G06T17/20
• 分類號: G06T17/20;G06T15/50
• 代理公司: 北京睿智保誠專利代理事務所(普通合伙) 11732
• 代理人: 韓迎之

本發明公開了一種多智能體在物理空間中的成形方法，應用于智能體系統的分布式控制技術領域，具體步驟包括如下：將連續的物理空間離散化為網格空間，并定義多智能體成形問題；每一個智能體向協調器報告在網格空間中的位置；在接收到每個智能體的位置后，協調器獲取每個位置的系統狀態；開始迭代，在每一輪迭代中，每一個智能體順序執行1)局部光場計算；2)優先級隊列生成；3)確定下一時刻的位置；4)移動到下一位置；當所有智能體都占據目標形狀中的一個網格；或者目標形狀中的每一個網格都被一個智能體占據，迭代結束。本發明公開了一種高效、可拓展和穩定的多智能體在物理空間中的成形方法。

技術領域

本發明涉及對智能體系統的分布式控制技術領域，更具體的說是涉及多智能體在物理空間中的成形方法。

背景技術

對于物理空間中的多智能體系統，一種典型的控制問題是如何控制系統中的每一個智能體在物理空間中進行移動，使得所有智能體在物理空間中形成特定的形狀。例如，控制無人機群體形成環形，以實現對特定目標的包圍。又例如，控制一組無人駕駛的車輛以固定的隊形在道路上行駛，以實現對道路資源的高效使用。一般意義上，可以將這種問題稱為多智能體的成形問題。

關于這一問題，現有的技術大致可以分為三類，且每一類技術都存在一定程度的缺陷：

1、基于邊緣跟隨的多智能體成形技術，會導致自成形過程的效率極低，主要原因在于系統過低的并行度(只有處于群體邊緣的智能體才能進行移動)；

2、基于全局目標分配和路徑規劃的多智能體自成形技術，具有較差的群體規模可擴展性；隨著智能體數量的增加，進行目標分配和路徑規劃所需的計算成本成3次方的速度增長；

3、基于虛擬勢能場的多智能體成形技術，具有較差的穩定性(不總是能夠正確的形成目標形狀)，因為這種技術會導致局部最小點的產生(智能體陷入局部最小點后，就再也無法移動了)，且局部最小點出現的可能性隨著智能體數量的增加而不斷增加。

因此，如何提供一種高效、可拓展和穩定的多智能體在物理空間中的成形方法是本領域技術人員亟需解決的問題。

發明內容

有鑒于此，本發明提供了一種多智能體在物理空間中的成形方法，基于該技術的多智能體成形過程具有較高的效率；隨著群體規模的增加，基于該技術的多智能體成形過程的計算成本具有較低的增長速度；基于該技術的多智能體成形結果具有較高的成功率。

為了實現上述目的，本發明提供如下技術方案：

多智能體在物理空間中的成形方法，具體步驟包括如下：

將連續的物理空間離散化為網格空間，并定義多智能體成形問題；

每一個智能體向協調器報告在網格空間中的位置；在接收到每個智能體的位置后，協調器獲取每個位置的系統狀態；

開始迭代，在每一輪迭代中，每一個智能體順序執行1)局部光場計算：計算每一個智能體當前所在位置以及與其鄰接的所有網格上的光場強度；2)優先級隊列生成：確定每一個智能體對下一時刻位置的偏好，并根據每一個智能體的狀態以及偏好對所有候選位置進行排序，形成一個優先級隊列；3)確定下一時刻的位置：通過與協調器進行交互，確定每一個智能體在下一時刻的位置；4)移動到下一位置；

當所有智能體都占據目標形狀中的一個網格；或者目標形狀中的每一個網格都被一個智能體占據，迭代結束。

優選的，在上述多智能體在物理空間中的成形方法中，將連續的物理空間離散化為網格空間具體步驟如下：利用矩陣式離散化或蜂巢式離散化，對物理空間進行離散化，形成的網格空間可以表示為一組網格以及網格之間的鄰接關系。