[發(fā)明專利]用于群組感知的多智能體運動路徑規(guī)劃的方法和設備

在審

• 申請?zhí)枺?/td>: 202110464443.6
• 申請日: 2021-04-28
• 公開（公告）號: CN113655783A
• 公開（公告）日: 2021-11-16
• 發(fā)明（設計）人: L·帕爾米耶里;T·林德
• 申請（專利權）人: 羅伯特·博世有限公司
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 任一方;周學斌

用于群組感知的多智能體運動路徑規(guī)劃的方法和設備。本發(fā)明涉及一種用于為多個智能體（2）規(guī)劃運動路徑的計算機實現(xiàn)的方法，包括以下步驟：?為多個智能體（2）執(zhí)行（S4）基于沖突的運動規(guī)劃，其中取決于移動成本來確定用于每個智能體（2）的無沖突運動路徑，?確定（S2）一個或多個個體對象（）和一個或多個對象群組（G）的姿態(tài)和速度；?取決于每個智能體（2）與所述一個或多個對象（）和/或所述一個或多個對象群組（G）的相互作用成本來計算（S3）移動成本。

技術領域

本發(fā)明涉及考慮多個對象和/或個體存在的多智能體系統(tǒng)的運動路徑規(guī)劃領域。

背景技術

一般而言，用于多智能體系統(tǒng)的路徑規(guī)劃方法在解耦路徑規(guī)劃與集中式路徑規(guī)劃之間進行區(qū)分。在解耦路徑規(guī)劃方法中，每個智能體通過避免沖突來計算其路徑。由于并行計算，解耦路徑規(guī)劃可以相對快速地執(zhí)行，但是最優(yōu)性以及甚至完整性不總是得到保證。

與之相反，耦合路徑規(guī)劃方法考慮所有智能體的狀態(tài)來搜索整個狀態(tài)空間，諸如從基于A^*的算法已知的。

雖然大多數(shù)路徑規(guī)劃算法將對象或個體的存在考慮為運動路徑的障礙物，但是更難考慮個體群組的存在，因為也應當避免單個群組的個體之間的運動路徑。

發(fā)明內容

根據(jù)本發(fā)明，提供了根據(jù)權利要求1的用于在多智能體系統(tǒng)中的多個智能體的運動路徑規(guī)劃的方法，以及根據(jù)另外的獨立權利要求的設備、智能體和多智能體系統(tǒng)。

從屬權利要求中指示了另外的實施例。

根據(jù)第一方面，提供了用于為多個智能體規(guī)劃運動路徑的計算機實現(xiàn)的方法，包括以下步驟：

- 為多個智能體執(zhí)行基于沖突的運動規(guī)劃，其中取決于移動成本來確定用于每個智能體的無沖突運動路徑，

- 確定一個或多個個體對象和一個或多個對象群組的姿態(tài)和速度；

- 取決于每個智能體與一個或多個對象和/或一個或多個對象群組的相互作用成本來計算移動成本。

以上方法涉及根據(jù)耦合路徑規(guī)劃方法的多智能體路徑尋找問題，該方法在與多個智能體通信的中央單元中執(zhí)行。中央單元獲得關于多個智能體、對象和對象群組的姿態(tài)的所有信息，并確定所有多個智能體的運動路徑。通過在中央單元中實行的路徑規(guī)劃算法，避免了一個智能體與其他智能體以及與障礙物、對象、個體和對象/個體群組的沖突。

一種常見的多智能體路徑規(guī)劃算法被稱為基于沖突的搜索（CBS），如在G. Sharon等人的“Conflict-based search for optimal multi-agent path finding”（Proceedings of the 26th AAAE Conference on Artificial Intelligence，p. 563 to569）中公開的。

特別地，基于沖突的運動規(guī)劃可以包括考慮利用為至少一個智能體定義約束的節(jié)點構建的約束樹。

基本上，基于沖突的搜索是兩級算法，其中高級搜索在約束樹中執(zhí)行，約束樹的節(jié)點包括針對單個智能體的時間和位置的約束。在約束樹中的每個節(jié)點處，執(zhí)行低級搜索以在高級節(jié)點給出的約束下為所有多個智能體找到路徑。在高級算法部分中，搜索約束樹。約束樹中的每個節(jié)點包含施加在每個智能體上的約束集合、單個一致的解決方案以及當前解決方案的總成本，該單個一致的解決方案包括用于每個智能體的一個路徑，該路徑與對于相應節(jié)點給出的約束集合相一致。

一旦通過任何合適的路徑尋找算法為每個智能體找到了一致的路徑，就必須通過模擬智能體沿著它們的規(guī)劃路徑的移動來相對于每個其他智能體的路徑檢查找到的路徑。如果所有智能體都在沒有任何沖突的情況下達到他們的目標，例如，兩個智能體沒有發(fā)生沖突，則約束樹的節(jié)點被聲明為目標節(jié)點，并且可以返回解決方案。然而，如果在執(zhí)行驗證時，對于兩個或更多個智能體找到了沖突，則驗證停止，并且節(jié)點被聲明為非目標。