多智能體路徑規(guī)劃（MAPF）是一個在共享環(huán)境中為多個智能體規(guī)劃無碰撞路徑的問題。傳統(tǒng)上MAPF問題主要在離散環(huán)境中研究，時間和空間都被離散化為固定的步長和網(wǎng)格。隨著實際應(yīng)用需求的增加，如倉庫物流和自動駕駛車輛，研究逐漸轉(zhuǎn)向連續(xù)環(huán)境中的路徑規(guī)劃。在連續(xù)環(huán)境中，時間和空間都是連續(xù)的，智能體的運動需要考慮更復(fù)雜的運動學(xué)和動力學(xué)約束。

在離散環(huán)境中，MAPF問題通常通過圖模型來表示，智能體在圖的頂點之間移動，避免在同一時間步出現(xiàn)在同一頂點。然而在連續(xù)環(huán)境中，智能體的路徑需要表示為平滑曲線，避免在任何時間點發(fā)生碰撞。這種連續(xù)表示更符合實際應(yīng)用場景，如機器人在復(fù)雜環(huán)境中的導(dǎo)航。

在連續(xù)環(huán)境中，時間和空間都是連續(xù)的，智能體的運動需要考慮更復(fù)雜的運動學(xué)和動力學(xué)約束。例如，車輛在路徑規(guī)劃中需要考慮加速度和轉(zhuǎn)彎半徑，以避免突然的方向變化帶來的不穩(wěn)定性。這種連續(xù)表示更符合實際應(yīng)用場景，如機器人在復(fù)雜環(huán)境中的導(dǎo)航。

9 月 18 日arXiv的 熱門論文《Multi-agent Path Finding in Continuous Environment》提出一種在連續(xù)環(huán)境中進行多智能體路徑規(guī)劃的新方法，以解決實際應(yīng)用中的挑戰(zhàn)。研究提出了一種新的連續(xù)環(huán)境沖突基搜索（CE-CBS）算法，該算法結(jié)合了高層次搜索框架的沖突基搜索（CBS）和低層次路徑規(guī)劃的RRT*算法。通過這種方法，智能體能夠在連續(xù)時間和空間中規(guī)劃平滑的無碰撞路徑，滿足各種運動學(xué)約束。

研究的主要挑戰(zhàn)在于如何在連續(xù)環(huán)境中有效地解決智能體之間的沖突。傳統(tǒng)的離散算法在處理連續(xù)時間和空間時效率較低，因此需要新的算法來提高路徑規(guī)劃的效率和可靠性。CE-CBS算法通過結(jié)合RRT*和B樣條曲線平滑處理，展示了在實際應(yīng)用中的潛力。

本研究由布拉格捷克技術(shù)大學(xué)信息技術(shù)學(xué)院的Kristyna Janovská和Pavel Surynek領(lǐng)導(dǎo)。Kristyna Janovská是該學(xué)院的研究員，主要研究領(lǐng)域包括多智能體系統(tǒng)、路徑規(guī)劃和連續(xù)環(huán)境中的智能體運動。Pavel Surynek是該學(xué)院的教授，研究領(lǐng)域涵蓋人工智能、多智能體系統(tǒng)、路徑規(guī)劃和優(yōu)化算法。

他們的研究致力于開發(fā)新的算法和模型，以解決多智能體在連續(xù)環(huán)境中的路徑規(guī)劃問題，旨在提高路徑規(guī)劃的效率和可靠性。通過提出的連續(xù)環(huán)境沖突基搜索（CE-CBS）算法，他們展示了在實際應(yīng)用中的潛力，并為未來的研究方向提供了新的思路。

理論背景?

連續(xù)環(huán)境中的MAPF問題

在多智能體路徑規(guī)劃（MAPF）中，傳統(tǒng)的研究主要集中在離散環(huán)境中，即時間和空間都被離散化為固定的步長和網(wǎng)格。然而隨著實際應(yīng)用需求的增加，如倉庫物流和自動駕駛車輛，研究逐漸轉(zhuǎn)向連續(xù)環(huán)境中的路徑規(guī)劃。在連續(xù)環(huán)境中，時間和空間都是連續(xù)的，智能體的運動需要考慮更復(fù)雜的運動學(xué)和動力學(xué)約束。

在離散環(huán)境中，時間通常表示為離散的時間步，環(huán)境則表示為圖的頂點和邊，智能體在圖的頂點之間移動，避免在同一時間步出現(xiàn)在同一頂點。然而在連續(xù)環(huán)境中，時間和空間都是連續(xù)的，智能體的路徑需要表示為平滑曲線，避免在任何時間點發(fā)生碰撞。這種連續(xù)表示更符合實際應(yīng)用場景，如機器人在復(fù)雜環(huán)境中的導(dǎo)航。

為了應(yīng)對連續(xù)環(huán)境中的MAPF問題，研究者們提出了多種算法。例如，連續(xù)沖突基搜索（CCBS）算法、擴展的增量沖突樹搜索（E-ICTS）算法和擴展的沖突基搜索-連續(xù)時間（ECBS-CT）算法。這些算法在處理連續(xù)時間和空間時表現(xiàn)出色，特別是CCBS算法，它無需時間離散化，直接在連續(xù)時間下工作，提供了更為精確的路徑規(guī)劃解決方案。

平滑連續(xù)MAPF（SC-MAPF）

平滑連續(xù)多智能體路徑規(guī)劃（SC-MAPF）問題是指在度量空間中找到一組平滑曲線，使得多個智能體在移動過程中不發(fā)生碰撞。SC-MAPF問題的定義如下：

• 路徑約束：路徑必須滿足一定的運動學(xué)約束，如最小角度約束，確保路徑段之間的角度不小于某個最小值。這是為了避免智能體在路徑上進行突然的方向變化，從而保證運動的平滑性和穩(wěn)定性。
• 沖突定義：沖突定義為兩個智能體在某個時間段內(nèi)重疊。解決沖突的方法是禁止智能體在沖突時間段內(nèi)移動到特定曲線上。

在SC-MAPF問題中，智能體的路徑被定義為平滑曲線，這些曲線需要滿足一定的運動學(xué)約束，以確保智能體在移動過程中不會發(fā)生碰撞。例如，路徑段之間的角度必須大于某個最小值，以避免智能體在路徑上進行突然的方向變化。此外，智能體的路徑還需要考慮其物理尺寸和運動特性，以確保路徑的可行性和安全性。

通過引入平滑機制，如B樣條曲線，可以使路徑更加平滑，從而限制路徑的曲率，防止突然轉(zhuǎn)向變化。這不僅可以處理連續(xù)時間，還可以處理連續(xù)環(huán)境，考慮各種運動學(xué)或動力學(xué)約束，使得路徑規(guī)劃更加符合實際應(yīng)用需求。

沖突基搜索（CBS）和連續(xù)時間沖突基搜索（CCBS）?

沖突基搜索（CBS）是一種用于多智能體路徑規(guī)劃（MAPF）的成本最優(yōu)算法，主要應(yīng)用于離散環(huán)境中。其基本原理是通過分層次的搜索框架來解決智能體之間的路徑?jīng)_突。CBS算法分為兩個層次：高層次和低層次。

在高層次，CBS算法首先為所有智能體計算初始路徑，然后檢查這些路徑是否存在沖突。沖突的定義是在同一時間步內(nèi)，兩個或多個智能體出現(xiàn)在同一個頂點。如果發(fā)現(xiàn)沖突，算法會生成兩個新的約束，每個約束禁止其中一個沖突智能體在沖突時間步內(nèi)進入沖突頂點。然后，算法將這兩個約束分別添加到兩個新的子問題中，并遞歸地解決這些子問題。

在低層次，CBS算法使用單智能體路徑規(guī)劃算法（如A*）為每個智能體計算路徑。路徑必須滿足高層次提供的約束，即智能體不能在特定時間步內(nèi)進入特定頂點。通過這種方式，CBS算法能夠逐步解決沖突，找到一組無沖突的路徑。

CBS算法的優(yōu)點在于其解決方案的成本最優(yōu)性，即找到的路徑集的總成本最小。然而，由于其在離散環(huán)境中工作，時間和空間都被離散化為固定的步長和網(wǎng)格，這在處理實際應(yīng)用中的連續(xù)環(huán)境時可能會遇到效率問題。

連續(xù)時間沖突基搜索（CCBS）算法是CBS算法的擴展，旨在解決連續(xù)時間下的多智能體路徑規(guī)劃問題。與CBS算法不同，CCBS算法在連續(xù)時間下工作，不需要將時間離散化為固定的時間步。

在CCBS算法中，沖突的定義和解決方式有所不同。由于時間是連續(xù)的，沖突不再僅僅是兩個智能體在同一時間步內(nèi)出現(xiàn)在同一個頂點，而是兩個智能體在某個時間段內(nèi)的路徑重疊。具體來說，CCBS算法定義了一個不安全時間間隔，如果一個智能體在這個時間間隔內(nèi)到達沖突位置，則認為存在沖突。

CCBS算法的高層次和低層次操作與CBS算法類似，但在處理沖突時需要考慮連續(xù)時間。高層次仍然負責(zé)檢測沖突并生成約束，但這些約束現(xiàn)在包括不安全時間間隔。低層次則使用RRT*算法進行路徑規(guī)劃，確保路徑在連續(xù)時間和空間下無沖突。

結(jié)合RRT*算法和B樣條曲線平滑處理，CCBS算法能夠在連續(xù)環(huán)境中生成平滑的無沖突路徑。與CBS算法相比，CCBS算法在處理實際應(yīng)用中的連續(xù)時間和空間時表現(xiàn)出更高的效率和可靠性。

快速擴展隨機樹（RRT）和RRT*?

RRT算法

快速擴展隨機樹（RRT）是一種用于路徑規(guī)劃的經(jīng)典算法，特別適用于高維度的連續(xù)度量空間。RRT算法的基本概念是通過隨機采樣來構(gòu)建一棵快速擴展的樹，從而探索路徑空間。其主要特點是能夠在復(fù)雜環(huán)境中高效地找到一條從起點到目標點的路徑。

RRT算法的工作原理如下：

初始化：從起點開始，創(chuàng)建一個包含起點的樹。

隨機采樣：在搜索空間中隨機生成一個點。

擴展樹：找到樹中距離隨機點最近的節(jié)點，并嘗試從該節(jié)點向隨機點擴展一條路徑。如果路徑不與障礙物相交，則將隨機點添加到樹中。

迭代：重復(fù)上述步驟，直到找到一條從起點到目標點的路徑，或者達到預(yù)設(shè)的迭代次數(shù)。

RRT算法的優(yōu)點在于其簡單性和高效性，特別是在處理高維度和復(fù)雜環(huán)境時。然而，RRT算法生成的路徑通常不是最優(yōu)的，可能包含許多不必要的繞行和急轉(zhuǎn)彎。

RRT*

為了克服RRT算法的不足，研究者們提出了RRT算法。RRT是RRT的改進版本，通過引入A*算法的成本函數(shù)，使得生成的路徑逐漸收斂到最優(yōu)解。

圖1：成功避開狹窄障礙物的平滑路徑。從藍色圓圈起始位置到綠色圓圈目標位置的結(jié)果路徑以綠色突出顯示。紅色顯示了采樣的RRT*樹。

RRT*算法的改進主要體現(xiàn)在以下幾個方面：

路徑優(yōu)化：在每次擴展樹時，不僅考慮從最近的節(jié)點擴展路徑，還會檢查新節(jié)點是否可以通過其他路徑更優(yōu)地連接到樹中。這種優(yōu)化過程使得路徑逐漸接近最優(yōu)解。

重連操作：在添加新節(jié)點后，RRT*會嘗試重新連接樹中的其他節(jié)點，以進一步優(yōu)化路徑。這種重連操作可以消除不必要的繞行和急轉(zhuǎn)彎，使路徑更加平滑和高效。

RRT算法在路徑規(guī)劃中的優(yōu)勢在于其能夠生成更優(yōu)的路徑，同時保持RRT算法的高效性。通過結(jié)合路徑優(yōu)化和重連操作，RRT能夠在復(fù)雜環(huán)境中找到更短、更平滑的路徑，適用于需要高精度路徑規(guī)劃的應(yīng)用場景。

在連續(xù)環(huán)境中的多智能體路徑規(guī)劃中，RRT算法被廣泛應(yīng)用于低層次路徑規(guī)劃。通過結(jié)合高層次的沖突基搜索（CBS）算法，RRT能夠在連續(xù)時間和空間中生成無沖突的平滑路徑，滿足各種運動學(xué)約束。

路徑平滑處理?

B樣條曲線

B樣條曲線是一種廣泛應(yīng)用于計算機圖形學(xué)和路徑規(guī)劃中的數(shù)學(xué)工具。它是一種分段多項式曲線，通過一組控制點來定義曲線的形狀。B樣條曲線的一個顯著特點是它能夠生成平滑的曲線，這對于路徑規(guī)劃中的平滑處理尤為重要。

B樣條曲線的定義如下：

• 控制點：B樣條曲線由一組控制點定義，這些點決定了曲線的形狀。
• 節(jié)點向量：節(jié)點向量是一個非遞減序列，用于定義曲線的參數(shù)范圍。
• 基函數(shù)：B樣條基函數(shù)是分段多項式函數(shù)，用于計算曲線上的點。

通過這些元素，B樣條曲線可以表示為控制點和基函數(shù)的線性組合。具體來說，給定一組控制點和節(jié)點向量，B樣條曲線上的任意一點都可以通過基函數(shù)的加權(quán)和來計算。

路徑平滑算法

在多智能體路徑規(guī)劃中，路徑平滑處理是為了確保生成的路徑不僅無碰撞，而且平滑且符合運動學(xué)約束。使用B樣條曲線進行路徑平滑處理的步驟如下：

1. 路徑生成：首先，通過RRT算法生成初始路徑。RRT算法能夠在連續(xù)度量空間中高效地找到一條從起點到目標點的路徑，但生成的路徑可能包含許多急轉(zhuǎn)彎和不必要的繞行。
2. 控制點選擇：從RRT*生成的路徑中選擇一組關(guān)鍵點作為B樣條曲線的控制點。這些控制點通常是路徑上的轉(zhuǎn)折點或關(guān)鍵位置。
3. 曲線擬合：使用選定的控制點和節(jié)點向量，計算B樣條基函數(shù)，并通過基函數(shù)的加權(quán)和生成B樣條曲線。這個過程將初始路徑轉(zhuǎn)換為一條平滑的曲線。
4. 路徑插值：在生成的B樣條曲線上插值出更多的點，以確保路徑的平滑性和連續(xù)性。通常，每個路徑長度單位插值一個新點。
5. 路徑驗證：驗證生成的平滑路徑是否滿足所有運動學(xué)約束和避障要求。具體來說，需要檢查路徑上的每個點是否與障礙物相交，以及路徑段之間的角度是否滿足最小角度約束。
6. 調(diào)整和優(yōu)化：如果生成的平滑路徑不滿足約束，可以調(diào)整控制點或節(jié)點向量，重新計算B樣條曲線，直到找到滿足要求的平滑路徑。

通過上述步驟，使用B樣條曲線進行路徑平滑處理，可以有效地生成符合實際應(yīng)用需求的平滑路徑。這種方法不僅提高了路徑的可行性和安全性，還能夠顯著減少智能體在路徑上的急轉(zhuǎn)彎和不必要的繞行，從而提高路徑規(guī)劃的效率和可靠性。

提出的模型?

CE-CBS算法

連續(xù)環(huán)境沖突基搜索（CE-CBS）算法是本文提出的一種新方法，旨在解決連續(xù)環(huán)境中的多智能體路徑規(guī)劃問題。該算法結(jié)合了沖突基搜索（CBS）和快速擴展隨機樹（RRT*）算法，并通過B樣條曲線進行路徑平滑處理。

算法概述

高層次搜索：CE-CBS算法的高層次部分基于傳統(tǒng)的CBS算法。首先為所有智能體計算初始路徑，然后檢查這些路徑是否存在沖突。如果發(fā)現(xiàn)沖突，算法會生成新的約束，禁止沖突智能體在沖突時間段內(nèi)進入沖突位置。

低層次搜索：在低層次部分，CE-CBS使用RRT算法進行路徑規(guī)劃。RRT算法通過隨機采樣和路徑優(yōu)化，生成無沖突的路徑。與傳統(tǒng)的RRT*不同，CE-CBS在路徑規(guī)劃過程中考慮了連續(xù)時間和空間的約束。

路徑平滑處理：生成的路徑可能包含急轉(zhuǎn)彎和不必要的繞行。為了提高路徑的平滑性和可行性，CE-CBS使用B樣條曲線對路徑進行平滑處理。通過控制點和基函數(shù)的線性組合，生成平滑的曲線，確保路徑滿足運動學(xué)約束。

算法步驟

1. 初始化：從起點開始，為每個智能體生成初始路徑。
2. 沖突檢測：檢查所有智能體的路徑，檢測是否存在沖突。如果存在沖突，生成新的約束。
3. 路徑規(guī)劃：使用RRT*算法為每個智能體重新規(guī)劃路徑，確保路徑滿足新的約束。
4. 路徑平滑：使用B樣條曲線對生成的路徑進行平滑處理，確保路徑平滑且無沖突。
5. 迭代：重復(fù)上述步驟，直到找到無沖突的平滑路徑。

通過這種方法，CE-CBS算法能夠在連續(xù)時間和空間中生成無沖突的平滑路徑，適用于實際應(yīng)用中的復(fù)雜環(huán)境。

智能體模型

在CE-CBS算法中，智能體被定義為具有固定半徑和速度的圓形物體。智能體在已知環(huán)境中移動，避開靜態(tài)和動態(tài)障礙物。具體來說，智能體模型包括以下幾個方面。

智能體定義：智能體被定義為具有固定半徑和速度的圓形物體。智能體的初始位置和目標位置在環(huán)境中預(yù)先設(shè)定。

運動學(xué)約束：智能體的路徑必須滿足一定的運動學(xué)約束，如最小轉(zhuǎn)彎半徑和最大加速度。這些約束確保智能體在路徑上移動時不會發(fā)生突然的方向變化，從而保證運動的平滑性和穩(wěn)定性。

避障策略：智能體在路徑規(guī)劃過程中需要避開靜態(tài)和動態(tài)障礙物。靜態(tài)障礙物是環(huán)境中的固定物體，如墻壁和家具。動態(tài)障礙物是其他智能體，它們在環(huán)境中移動，可能與當前智能體發(fā)生碰撞。

路徑驗證：生成的路徑需要經(jīng)過驗證，確保路徑段之間的角度滿足最小角度約束，路徑上的每個點都不與障礙物相交。如果路徑不滿足約束，需要重新規(guī)劃和調(diào)整，直到找到滿足要求的路徑。

通過結(jié)合RRT*算法和B樣條曲線平滑處理，CE-CBS算法能夠生成符合實際應(yīng)用需求的平滑路徑。智能體在已知環(huán)境中移動，避開靜態(tài)和動態(tài)障礙物，確保路徑的可行性和安全性。

實驗結(jié)果?

實驗設(shè)置

為了驗證CE-CBS算法在連續(xù)環(huán)境中的性能，研究團隊設(shè)計了一系列實驗，測試不同參數(shù)設(shè)置和場景類型下的模型表現(xiàn)。實驗主要關(guān)注以下幾個參數(shù)。

• RRT*的最大節(jié)點數(shù)（ηmax）：這是RRT算法在路徑規(guī)劃過程中能夠采樣的最大節(jié)點數(shù)。較大的ηmax值允許RRT更深入地探索環(huán)境，但也會增加計算時間。
• 路徑段之間的最小角度值（α）：這是路徑段之間的最小允許角度，用于確保路徑的平滑性和可行性。較大的α值可以避免急轉(zhuǎn)彎，但可能會增加路徑長度。
• 智能體半徑（r）：這是智能體的物理尺寸，影響智能體在路徑規(guī)劃過程中避開障礙物和其他智能體的能力。

實驗場景包括不同大小和復(fù)雜度的環(huán)境，包含靜態(tài)和動態(tài)障礙物。智能體的起點和目標位置在環(huán)境中隨機分布，以模擬實際應(yīng)用中的多種情況。

圖2：顯示每個代理的平均路徑長度與ηmax之間關(guān)系的實驗結(jié)果圖。

圖3：顯示CE-CBS迭代次數(shù)如何根據(jù)不同的ηmax而變化的圖。

實驗結(jié)果分析

實驗結(jié)果顯示，隨著ηmax的增加，路徑質(zhì)量顯著提高。較大的ηmax值允許RRT*更深入地探索環(huán)境，生成更接近最優(yōu)的路徑。然而較大的ηmax值也增加了計算時間，特別是在復(fù)雜環(huán)境中。實驗還發(fā)現(xiàn)，當ηmax超過一定值（如5000）后，路徑質(zhì)量的提升變得不明顯，但計算時間顯著增加。因此，在實際應(yīng)用中，需要在路徑質(zhì)量和計算時間之間找到平衡。

圖 6：不同設(shè)置參數(shù)ηmax的運行結(jié)果比較——樣本RRT*節(jié)點的最大數(shù)量。

實驗表明，較大的α值可以有效避免路徑中的急轉(zhuǎn)彎，提高路徑的平滑性和可行性。然而，較大的α值也可能導(dǎo)致路徑長度增加，因為智能體需要繞過更多的障礙物。實驗結(jié)果顯示，當α值在90度左右時，路徑質(zhì)量和計算時間之間的平衡效果最佳。

實驗結(jié)果顯示，隨著智能體半徑r的增加，路徑成本總和也隨之增加。較大的智能體需要更長的繞行路徑以避免與障礙物和其他智能體發(fā)生碰撞。實驗還發(fā)現(xiàn)，較大的智能體半徑可以減少路徑規(guī)劃中的沖突次數(shù)，因為智能體需要保持更大的安全距離，從而減少了搜索空間。

圖9：不同設(shè)置參數(shù)r-代理半徑的運行結(jié)果比較。

圖10：關(guān)于試劑半徑r的實驗結(jié)果。

CBS與CE-CBS比較

為了評估CE-CBS算法在連續(xù)環(huán)境中的優(yōu)勢，研究團隊將其與標準CBS算法進行了比較。實驗設(shè)置為將連續(xù)環(huán)境轉(zhuǎn)換為2D網(wǎng)格，使用A*作為低層算法的標準CBS進行比較。結(jié)果顯示，CE-CBS算法在連續(xù)環(huán)境中表現(xiàn)出顯著優(yōu)勢。

圖11：使用離散CBS（左）和連續(xù)CE-CBS（右）規(guī)劃的路徑。

路徑質(zhì)量：CE-CBS算法生成的路徑更短、更平滑，因為它不受網(wǎng)格移動限制。實驗結(jié)果顯示，CE-CBS算法在所有測試案例中都找到了無沖突的解決方案，而標準CBS算法在某些情況下未能解決時間沖突。

計算時間：盡管CE-CBS算法在某些情況下需要更多的計算時間，但其生成的路徑質(zhì)量顯著提高，特別是在復(fù)雜環(huán)境中。實驗結(jié)果表明，CE-CBS算法在處理連續(xù)時間和空間時表現(xiàn)出更高的效率和可靠性。

圖12:CE-CBS在地圖4×4網(wǎng)格上，4個代理從藍色位置開始，綠色目標位置。

圖13:CE-CBS在地圖4×4網(wǎng)格上，一個矩形障礙物阻擋了兩個單元和三個代理。

從實驗結(jié)果來看，CE-CBS算法在連續(xù)環(huán)境中的多智能體路徑規(guī)劃中展示了顯著的優(yōu)勢，能夠生成高質(zhì)量的無沖突路徑，適用于實際應(yīng)用中的復(fù)雜環(huán)境。

討論?

在實驗中，不同參數(shù)對CE-CBS算法的解決方案質(zhì)量和計算時間產(chǎn)生了顯著影響。

RRT*的最大節(jié)點數(shù)（ηmax）

隨著ηmax的增加，RRT算法能夠更深入地探索環(huán)境，生成更接近最優(yōu)的路徑。然而，當ηmax超過一定值（如5000）后，路徑質(zhì)量的提升變得不明顯。這是因為RRT在較大搜索空間中已經(jīng)找到了接近最優(yōu)的路徑，進一步增加節(jié)點數(shù)對路徑質(zhì)量的影響有限。

較大的ηmax值顯著增加了計算時間，特別是在復(fù)雜環(huán)境中。實驗結(jié)果顯示，隨著ηmax的增加，CE-CBS算法的迭代次數(shù)和計算時間也相應(yīng)增加。因此，在實際應(yīng)用中，需要在路徑質(zhì)量和計算時間之間找到平衡。

路徑段之間的最小角度值（α）

較大的α值可以有效避免路徑中的急轉(zhuǎn)彎，提高路徑的平滑性和可行性。實驗表明，當α值在90度左右時，路徑質(zhì)量和計算時間之間的平衡效果最佳。

較大的α值可能導(dǎo)致路徑長度增加，因為智能體需要繞過更多的障礙物。然而，這種增加是可以接受的，因為它顯著提高了路徑的平滑性和智能體的運動穩(wěn)定性。

智能體半徑（r）

隨著智能體半徑r的增加，路徑成本總和也隨之增加。較大的智能體需要更長的繞行路徑以避免與障礙物和其他智能體發(fā)生碰撞。

較大的智能體半徑可以減少路徑規(guī)劃中的沖突次數(shù)，因為智能體需要保持更大的安全距離，從而減少了搜索空間。這種減少沖突的效果在復(fù)雜環(huán)境中尤為明顯。

CE-CBS算法在不同類型的環(huán)境中展示了良好的適應(yīng)性，特別是在狹窄通道和多沖突區(qū)域中的導(dǎo)航能力。

狹窄通道

在狹窄通道中，智能體需要精確地規(guī)劃路徑，以避免與障礙物發(fā)生碰撞。CE-CBS算法通過結(jié)合RRT*和B樣條曲線，能夠生成平滑且無沖突的路徑，確保智能體在狹窄通道中順利導(dǎo)航。

在狹窄通道中，智能體之間的沖突更容易發(fā)生。CE-CBS算法通過高效的沖突檢測和解決機制，能夠及時發(fā)現(xiàn)并解決沖突，確保智能體的安全移動。

多沖突區(qū)域

在多沖突區(qū)域中，智能體需要頻繁調(diào)整路徑以避免與其他智能體發(fā)生碰撞。CE-CBS算法通過動態(tài)調(diào)整RRT*的最大節(jié)點數(shù)和路徑段之間的最小角度值，能夠靈活應(yīng)對復(fù)雜環(huán)境中的多種沖突情況。

盡管多沖突區(qū)域增加了路徑規(guī)劃的復(fù)雜性，CE-CBS算法仍然能夠在合理的計算時間內(nèi)找到無沖突的路徑。實驗結(jié)果表明，CE-CBS算法在處理多沖突區(qū)域時表現(xiàn)出較高的計算效率和路徑質(zhì)量。

總體而言，CE-CBS算法在不同類型的環(huán)境中展示了良好的適應(yīng)性和魯棒性，能夠有效解決連續(xù)環(huán)境中的多智能體路徑規(guī)劃問題。通過合理調(diào)整參數(shù)，CE-CBS算法能夠在保證路徑質(zhì)量的同時，顯著提高計算效率，適用于實際應(yīng)用中的復(fù)雜場景。（END）

?參考資料：???https://arxiv.org/pdf/2409.10680??

本文轉(zhuǎn)載自??大噬元獸??，作者： FlerkenS ????