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

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

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

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

研究的主要挑戰(zhàn)在于如何在連續(xù)環(huán)境中有效地解決智能體之間的沖突。傳統(tǒng)的離散算法在處理連續(xù)時(shí)間和空間時(shí)效率較低，因此需要新的算法來(lái)提高路徑規(guī)劃的效率和可靠性。CE-CBS算法通過(guò)結(jié)合RRT*和B樣條曲線平滑處理，展示了在實(shí)際應(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)境中的智能體運(yùn)動(dòng)。Pavel Surynek是該學(xué)院的教授，研究領(lǐng)域涵蓋人工智能、多智能體系統(tǒng)、路徑規(guī)劃和優(yōu)化算法。

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

理論背景?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

快速擴(kuò)展隨機(jī)樹(shù)（RRT）和RRT*?

RRT算法

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

RRT算法的工作原理如下：

初始化：從起點(diǎn)開(kāi)始，創(chuàng)建一個(gè)包含起點(diǎn)的樹(shù)。

隨機(jī)采樣：在搜索空間中隨機(jī)生成一個(gè)點(diǎn)。

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

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

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

RRT*

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

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

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

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

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

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

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

路徑平滑處理?

B樣條曲線

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

B樣條曲線的定義如下：

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

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

路徑平滑算法

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

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

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

提出的模型?

CE-CBS算法

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

算法概述

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

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

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

算法步驟

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

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

智能體模型

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

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

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

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

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

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

實(shí)驗(yàn)結(jié)果?

實(shí)驗(yàn)設(shè)置

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

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

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

圖2：顯示每個(gè)代理的平均路徑長(zhǎng)度與ηmax之間關(guān)系的實(shí)驗(yàn)結(jié)果圖。

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

實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

CBS與CE-CBS比較

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

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

路徑質(zhì)量：CE-CBS算法生成的路徑更短、更平滑，因?yàn)樗皇芫W(wǎng)格移動(dòng)限制。實(shí)驗(yàn)結(jié)果顯示，CE-CBS算法在所有測(cè)試案例中都找到了無(wú)沖突的解決方案，而標(biāo)準(zhǔn)CBS算法在某些情況下未能解決時(shí)間沖突。

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

圖12:CE-CBS在地圖4×4網(wǎng)格上，4個(gè)代理從藍(lán)色位置開(kāi)始，綠色目標(biāo)位置。

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

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

討論?

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

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

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

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

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

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

較大的α值可能導(dǎo)致路徑長(zhǎng)度增加，因?yàn)橹悄荏w需要繞過(guò)更多的障礙物。然而，這種增加是可以接受的，因?yàn)樗@著提高了路徑的平滑性和智能體的運(yùn)動(dòng)穩(wěn)定性。

智能體半徑（r）

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

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

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

狹窄通道

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

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

多沖突區(qū)域

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

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

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

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

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