多智能體路徑規(guī)劃（MAPF）是一個(gè)在機(jī)器人、交通控制和自動(dòng)化倉庫等領(lǐng)域具有廣泛應(yīng)用的重要問題。MAPF的核心目標(biāo)是為一組智能體找到一組無沖突的路徑，使它們能夠從起點(diǎn)移動(dòng)到目標(biāo)位置。傳統(tǒng)的MAPF問題通常限制智能體只能在預(yù)定義的圖上移動(dòng)，這種限制在實(shí)際應(yīng)用中可能不夠靈活。

任意角度路徑規(guī)劃（Any-Angle Pathfinding）是一種更為靈活的方法，允許智能體在不碰撞障礙物的情況下在任意位置之間移動(dòng)。這種方法在提高路徑規(guī)劃效率和適應(yīng)復(fù)雜環(huán)境方面具有顯著優(yōu)勢(shì)。然而任意角度路徑規(guī)劃也帶來了新的挑戰(zhàn)，特別是在多智能體環(huán)境中，如何確保路徑的無沖突性和最優(yōu)性成為一個(gè)關(guān)鍵問題。

被IROS 2024會(huì)議接收論文《Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding》提出了第一個(gè)針對(duì)任意角度多智能體路徑規(guī)劃的最優(yōu)算法，并介紹了其有界次優(yōu)變體。這些算法在解決復(fù)雜路徑規(guī)劃問題時(shí)表現(xiàn)出色，具有重要的理論和實(shí)際意義。通過引入連續(xù)沖突搜索（CCBS）和安全區(qū)間路徑規(guī)劃（TO-AA-SIPP），以及多約束（MC）和分離拆分（DS）技術(shù)，論文的算法顯著提高了路徑規(guī)劃的效率和效果。

研究團(tuán)隊(duì)由Konstantin Yakovlev、Anton Andreychuk和Roni Stern組成，他們分別隸屬于多個(gè)知名研究機(jī)構(gòu)。Konstantin Yakovlev隸屬于FRC CSC RAS（俄羅斯科學(xué)院計(jì)算機(jī)科學(xué)與控制研究中心）、AIRI（人工智能研究所）、HSE University（高等經(jīng)濟(jì)學(xué)院）和MIPT（莫斯科物理技術(shù)學(xué)院）。Anton Andreychuk隸屬于AIRI（人工智能研究所）。Roni Stern隸屬于Ben-Gurion University of the Negev（內(nèi)蓋夫本-古里安大學(xué)）。他們?cè)诙嘀悄荏w路徑規(guī)劃領(lǐng)域具有豐富的研究經(jīng)驗(yàn)和深厚的學(xué)術(shù)背景，為論文的研究提供了堅(jiān)實(shí)的基礎(chǔ)。

研究背景

多智能體路徑規(guī)劃（MAPF）是一個(gè)在機(jī)器人、交通控制和自動(dòng)化倉庫等領(lǐng)域具有廣泛應(yīng)用的重要問題。MAPF的核心目標(biāo)是為一組智能體找到一組無沖突的路徑，使它們能夠從起點(diǎn)移動(dòng)到目標(biāo)位置。傳統(tǒng)的MAPF問題通常限制智能體只能在預(yù)定義的圖上移動(dòng)，這種限制在實(shí)際應(yīng)用中可能不夠靈活。

近年來，研究人員開始探索放寬這些經(jīng)典假設(shè)的方法。Yakovlev和Andreychuk提出了一種基于優(yōu)先級(jí)規(guī)劃的任意角度MAPF算法，這種算法允許智能體在不碰撞障礙物的情況下在任意位置之間移動(dòng)。這一方法在提高路徑規(guī)劃效率和適應(yīng)復(fù)雜環(huán)境方面具有顯著優(yōu)勢(shì)。然而任意角度路徑規(guī)劃也帶來了新的挑戰(zhàn)，特別是在多智能體環(huán)境中，如何確保路徑的無沖突性和最優(yōu)性成為一個(gè)關(guān)鍵問題。

其他研究也提出了支持運(yùn)動(dòng)學(xué)約束的技術(shù)。例如，Yan和Li提出了一種基于優(yōu)先級(jí)搜索的三階段求解器，能夠處理加速和減速動(dòng)作。這些研究雖然在一定程度上解決了MAPF中的一些問題，但它們大多不是最優(yōu)的。

在最優(yōu)MAPF求解器方面，許多研究是對(duì)沖突基搜索（CBS）的改進(jìn)。例如，Solis等人提出了為每個(gè)機(jī)器人構(gòu)建路線圖并使用CBS進(jìn)行規(guī)劃的方法，并結(jié)合軌跡優(yōu)化方法為異構(gòu)智能體團(tuán)隊(duì)（如四旋翼機(jī)）構(gòu)建無碰撞路徑。Kinodynamic變體的CBS也被提出，用于處理具有不同運(yùn)動(dòng)學(xué)特性的智能體。

盡管這些研究在一定程度上解決了MAPF中的一些問題，但它們大多集中在經(jīng)典MAPF假設(shè)的基礎(chǔ)上。論文的研究旨在進(jìn)一步放寬這些假設(shè)，提出一種新的任意角度多智能體路徑規(guī)劃算法（AA-CCBS），并通過引入多約束（MC）和分離拆分（DS）技術(shù)來提高算法的效率和效果。

問題陳述

在多智能體路徑規(guī)劃（MAPF）中，目標(biāo)是為一組智能體找到一組無沖突的路徑，使它們能夠從起點(diǎn)移動(dòng)到目標(biāo)位置。傳統(tǒng)的MAPF問題通常限制智能體只能在預(yù)定義的圖上移動(dòng)，這種限制在實(shí)際應(yīng)用中可能不夠靈活。論文研究的任意角度多智能體路徑規(guī)劃問題（AA-MAPF）則放寬了這一限制，允許智能體在不碰撞障礙物的情況下在任意位置之間移動(dòng)。

圖1：同一MAPF實(shí)例的兩個(gè)最優(yōu)解：由基數(shù)組成的一個(gè)只移動(dòng)（左），而具有任何角度的一個(gè)移動(dòng)（右）。后者的成本降低了22%。

具體來說，AA-MAPF問題的目標(biāo)是找到一組將智能體從起點(diǎn)傳送到目標(biāo)位置的無沖突路徑，并且這些路徑的總成本最小。每個(gè)智能體可以在任意角度上移動(dòng)，只要它們的路徑不與障礙物相交。這種任意角度的移動(dòng)方式使得路徑規(guī)劃更加靈活和高效，但也帶來了新的挑戰(zhàn)，特別是在多智能體環(huán)境中，如何確保路徑的無沖突性和最優(yōu)性成為一個(gè)關(guān)鍵問題。

圖2：vanilla AA-CCBS多約束的示例。

論文提出的AA-CCBS算法結(jié)合了連續(xù)沖突搜索（CCBS）和安全區(qū)間路徑規(guī)劃（TO-AA-SIPP），旨在解決這些挑戰(zhàn)。CCBS算法通過在連續(xù)時(shí)間間隔上進(jìn)行搜索，避免了時(shí)間離散化的問題，而TO-AA-SIPP算法則能夠處理動(dòng)態(tài)障礙物環(huán)境中的任意角度路徑規(guī)劃。通過結(jié)合這兩種方法，AA-CCBS算法能夠在保證路徑最優(yōu)性的同時(shí)，提高路徑規(guī)劃的效率。

此外，為了進(jìn)一步提高算法的性能，論文引入了多約束（MC）和分離拆分（DS）技術(shù)。多約束技術(shù)通過添加多個(gè)約束來減少高層搜索迭代次數(shù)，而分離拆分技術(shù)則通過在沖突解決時(shí)添加正負(fù)約束來減少搜索工作量。這些技術(shù)的結(jié)合使得AA-CCBS算法在處理復(fù)雜路徑規(guī)劃問題時(shí)表現(xiàn)出色。

算法介紹

研究團(tuán)隊(duì)提出了一種新的任意角度多智能體路徑規(guī)劃算法，稱為AA-CCBS（Any-Angle Continuous Conflict-Based Search）。該算法結(jié)合了連續(xù)沖突搜索（CCBS）和安全區(qū)間路徑規(guī)劃（TO-AA-SIPP），并通過引入多約束（MC）和分離拆分（DS）技術(shù)來提高算法的效率和效果。

連續(xù)沖突搜索（CCBS）

CCBS是沖突基搜索（CBS）的變體，適用于非離散時(shí)間線。它通過在連續(xù)時(shí)間間隔上進(jìn)行搜索，避免了時(shí)間離散化的問題。CCBS的工作原理是為每個(gè)智能體單獨(dú)找到路徑，檢測(cè)這些路徑之間的沖突，并通過對(duì)個(gè)別智能體重新規(guī)劃來解決沖突。CCBS通過高層搜索選擇要約束的智能體，并通過低層搜索找到滿足約束的路徑。

安全區(qū)間路徑規(guī)劃（TO-AA-SIPP）

TO-AA-SIPP是SIPP（Safe Interval Path Planning）的變體，旨在為在動(dòng)態(tài)障礙物環(huán)境中導(dǎo)航的智能體找到最優(yōu)的任意角度路徑。TO-AA-SIPP的搜索節(jié)點(diǎn)由一個(gè)元組（頂點(diǎn)，安全時(shí)間間隔）標(biāo)識(shí)，表示智能體可以在該時(shí)間間隔內(nèi)安全地駐留在該頂點(diǎn)。與SIPP不同，TO-AA-SIPP不會(huì)通過擴(kuò)展搜索節(jié)點(diǎn)來迭代構(gòu)建搜索樹，而是預(yù)先生成所有搜索節(jié)點(diǎn)，并迭代嘗試識(shí)別節(jié)點(diǎn)之間的正確父子關(guān)系，以獲得最優(yōu)解。

多約束（MC）

多約束技術(shù)通過添加多個(gè)約束來減少高層搜索迭代次數(shù)。論文提出了三種MC方法。

MC1：識(shí)別出所有源頂點(diǎn)相同的動(dòng)作子集，并為每個(gè)智能體添加相應(yīng)的多約束。盡管MC1方法有效，但在AA-MAPF中，互相沖突的動(dòng)作數(shù)量可能很大，導(dǎo)致不安全區(qū)間過短，從而削弱約束效果。

MC2：為解決上述問題，MC2方法通過僅考慮有限的動(dòng)作集和過濾掉導(dǎo)致原始不安全區(qū)間縮短的動(dòng)作來增強(qiáng)約束效果。MC2方法在約束效果上更強(qiáng)。

MC3：進(jìn)一步擴(kuò)展MC2，包含不同源頂點(diǎn)但相同目標(biāo)頂點(diǎn)的動(dòng)作。這些動(dòng)作可能導(dǎo)致相同智能體在幾乎相同位置發(fā)生碰撞，因此自然地包含在同一多約束中。

圖3：包含多約束的不同版本的動(dòng)作。請(qǐng)注意，MC2和MC3中動(dòng)作的時(shí)間間隔明顯大于MC1。因此，預(yù)計(jì)MC2和MC3將表現(xiàn)出更大的修剪能力。

分離拆分（DS）

分離拆分技術(shù)通過在沖突解決時(shí)添加正負(fù)約束來減少搜索工作量。一個(gè)CCBS子節(jié)點(diǎn)對(duì)智能體i添加負(fù)約束，另一個(gè)子節(jié)點(diǎn)對(duì)智能體i添加正約束并對(duì)智能體j添加負(fù)約束。論文提出了兩種實(shí)現(xiàn)方式：

直接使用DS：這種方式較為直接，通過在沖突解決時(shí)添加正負(fù)約束來減少搜索工作量。

結(jié)合MC使用DS：這種方式需要處理多個(gè)起點(diǎn)位置的連續(xù)搜索，較為復(fù)雜。為了簡(jiǎn)化DS和MC的集成，論文建議避免將多約束作為地標(biāo)，而是使用常規(guī)的負(fù)多約束。

通過結(jié)合這些技術(shù)，AA-CCBS算法能夠在保證路徑最優(yōu)性的同時(shí)，提高路徑規(guī)劃的效率和效果。實(shí)驗(yàn)結(jié)果表明，這些改進(jìn)顯著提高了算法的性能，使其在處理復(fù)雜路徑規(guī)劃問題時(shí)表現(xiàn)出色。

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

為了評(píng)估AA-CCBS算法的性能，研究團(tuán)隊(duì)在MovingAI基準(zhǔn)測(cè)試中進(jìn)行了廣泛的實(shí)驗(yàn)。實(shí)驗(yàn)使用了多個(gè)不同類型的地圖，包括空地圖、隨機(jī)地圖、迷宮地圖和倉庫地圖。每個(gè)地圖提供了25個(gè)場(chǎng)景，每個(gè)場(chǎng)景包含一組起點(diǎn)和目標(biāo)位置。實(shí)驗(yàn)通過逐步增加智能體數(shù)量，直到算法在300秒的時(shí)間限制內(nèi)無法找到解決方案為止。

實(shí)驗(yàn)結(jié)果顯示，AA-CCBS算法的多種變體在不同場(chǎng)景下表現(xiàn)出色。具體來說，MC3、DS和DS+MC3變體顯著優(yōu)于其他變體。MC3在快速解決簡(jiǎn)單實(shí)例方面表現(xiàn)尤為突出，而DS和DS+MC3在處理復(fù)雜實(shí)例時(shí)表現(xiàn)更佳。

在評(píng)估有界次優(yōu)AA-CCBS時(shí)，研究團(tuán)隊(duì)使用了不同的次優(yōu)性界限（w = 1.01, 1.1, 1.25）進(jìn)行實(shí)驗(yàn)。結(jié)果表明，MC3在尋找有界次優(yōu)解時(shí)顯著提高了AA-CCBS的性能，而DS變體未能超越原始AA-CCBS。這可能是因?yàn)镈S的正約束在次優(yōu)搜索中效果較差，不能立即消除沖突，而MC3通過對(duì)更多動(dòng)作施加約束，在貪婪搜索中更有效地消除沖突。

具體實(shí)驗(yàn)結(jié)果如下：

• 覆蓋率：MC3、DS和DS+MC3變體在300秒時(shí)間限制內(nèi)解決了更多的實(shí)例。MC3在快速解決簡(jiǎn)單實(shí)例方面表現(xiàn)尤為突出，而DS和DS+MC3在處理復(fù)雜實(shí)例時(shí)表現(xiàn)更佳。
• 解決時(shí)間：MC3在次優(yōu)性界限較小時(shí)（w = 1.01）表現(xiàn)最佳，而DS和DS+MC3在次優(yōu)性界限較大時(shí)（w = 1.25）表現(xiàn)更佳。這表明MC3適合快速解決較容易的實(shí)例，而DS和DS+MC3更適合解決較難的實(shí)例。
• 高層迭代次數(shù)：在解決不同MAPF問題實(shí)例時(shí)，MC3需要的高層迭代次數(shù)較少，尤其是在較容易的實(shí)例中。DS和DS+MC3在較難的實(shí)例中表現(xiàn)更佳，盡管需要更多的高層迭代次數(shù)。

圖4:AA-CCBS不同變體的評(píng)估。左側(cè)窗格顯示了AA-CCBS每個(gè)版本在5分鐘時(shí)間限制內(nèi)完全解決的實(shí)例數(shù)量。中間窗格顯示了找到解決方案所需的時(shí)間（Y軸以對(duì)數(shù)刻度表示）。

每個(gè)數(shù)據(jù)點(diǎn)告訴算法在一定時(shí)間內(nèi)（Y軸）能夠解決多少個(gè)實(shí)例（X軸）。右側(cè)面板展示了解決不同MAPF問題實(shí)例所需的高級(jí)迭代次數(shù)。X軸顯示實(shí)例id。每個(gè)數(shù)據(jù)點(diǎn)告訴算法（Y軸）對(duì)特定問題實(shí)例（X軸）進(jìn)行了多少次高級(jí)迭代。

實(shí)驗(yàn)結(jié)果表明，AA-CCBS算法及其增強(qiáng)版本在處理任意角度多智能體路徑規(guī)劃問題時(shí)表現(xiàn)出色。MC3在快速解決簡(jiǎn)單實(shí)例和尋找有界次優(yōu)解方面表現(xiàn)尤為突出，而DS和DS+MC3在處理復(fù)雜實(shí)例時(shí)表現(xiàn)更佳。這些結(jié)果驗(yàn)證了多約束和分離拆分技術(shù)在提高算法性能方面的有效性。

有界次優(yōu)AA-CCBS

在實(shí)際應(yīng)用中，找到最優(yōu)解往往需要耗費(fèi)大量時(shí)間和計(jì)算資源。為了在保證解的質(zhì)量的同時(shí)提高算法的效率，論文提出了有界次優(yōu)（Bounded Suboptimal, BS）AA-CCBS算法。該算法通過允許解的成本在最優(yōu)解成本的某個(gè)倍數(shù)范圍內(nèi)，從而在一定程度上放寬了最優(yōu)性的要求，以換取更快的求解速度。

圖5:AA-CCBS的評(píng)估結(jié)果及其在不同次優(yōu)因素下的修改。

實(shí)現(xiàn)方法

有界次優(yōu)AA-CCBS的實(shí)現(xiàn)基于在高層搜索中引入焦點(diǎn)搜索（Focal Search）。具體來說，在每次高層迭代中，算法會(huì)創(chuàng)建一個(gè)名為FOCAL的節(jié)點(diǎn)列表。FOCAL包含所有生成的節(jié)點(diǎn)，這些節(jié)點(diǎn)的成本不超過 ( w \cdot f_{\text{min}} )，其中 ( w ) 是次優(yōu)性界限， ( f_{\text{min}} ) 是常規(guī)AA-CCBS將擴(kuò)展的節(jié)點(diǎn)的成本。

在FOCAL中，算法選擇沖突最少的節(jié)點(diǎn)進(jìn)行擴(kuò)展，并在節(jié)點(diǎn)數(shù)量相同時(shí)優(yōu)先選擇約束更多的節(jié)點(diǎn)。這種方法迫使搜索更貪婪地解決沖突，同時(shí)保持所需的次優(yōu)性界限。

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

研究團(tuán)隊(duì)對(duì)BS AA-CCBS進(jìn)行了廣泛的實(shí)驗(yàn)，評(píng)估了不同次優(yōu)性界限（ ( w = 1.01, 1.1, 1.25 ) ）下的算法性能。實(shí)驗(yàn)結(jié)果顯示：

• 覆蓋率：MC3在尋找有界次優(yōu)解時(shí)顯著提高了AA-CCBS的性能，而DS變體未能超越原始AA-CCBS。這可能是因?yàn)镈S的正約束在次優(yōu)搜索中效果較差，不能立即消除沖突，而MC3通過對(duì)更多動(dòng)作施加約束，在貪婪搜索中更有效地消除沖突。
• 解決時(shí)間：MC3在次優(yōu)性界限較小時(shí)（ ( w = 1.01 ) ）表現(xiàn)最佳，而DS和DS+MC3在次優(yōu)性界限較大時(shí)（ ( w = 1.25 ) ）表現(xiàn)更佳。這表明MC3適合快速解決較容易的實(shí)例，而DS和DS+MC3更適合解決較難的實(shí)例。
• 解決方案成本：MC3版本的解決方案成本溢出不超過2%，即使在次優(yōu)性界限 ( w = 1.25 ) 時(shí)也是如此。這表明MC3在保持較低成本溢出的同時(shí)，顯著提高了算法的求解速度。

結(jié)論與未來工作

論文提出了第一個(gè)針對(duì)任意角度多智能體路徑規(guī)劃（AA-MAPF）的最優(yōu)算法AA-CCBS，并通過引入多約束（MC）和分離拆分（DS）技術(shù)顯著提升了算法的性能。實(shí)驗(yàn)結(jié)果表明，這些改進(jìn)在處理復(fù)雜路徑規(guī)劃問題時(shí)表現(xiàn)出色，能夠有效地解決沖突并找到最優(yōu)解。

具體來說，MC3在快速解決簡(jiǎn)單實(shí)例和尋找有界次優(yōu)解方面表現(xiàn)尤為突出，而DS和DS+MC3在處理復(fù)雜實(shí)例時(shí)表現(xiàn)更佳。這些結(jié)果驗(yàn)證了多約束和分離拆分技術(shù)在提高算法性能方面的有效性。

未來工作可以從以下幾個(gè)方面進(jìn)一步探索和改進(jìn)。

多約束形成過程：探索更復(fù)雜和高效的多約束形成過程，以進(jìn)一步提高算法的剪枝能力和搜索效率。

增量搜索技術(shù)：在任意角度低層搜索中適應(yīng)增量搜索技術(shù)，以減少重復(fù)計(jì)算和提高求解速度。

實(shí)際應(yīng)用場(chǎng)景：將AA-CCBS算法應(yīng)用于更多實(shí)際場(chǎng)景，如自動(dòng)駕駛、無人機(jī)編隊(duì)和智能交通系統(tǒng)，驗(yàn)證其在真實(shí)環(huán)境中的性能和魯棒性。

算法優(yōu)化：進(jìn)一步優(yōu)化算法的實(shí)現(xiàn)，減少計(jì)算資源的消耗，提高算法的可擴(kuò)展性和適用性。

總之，研究團(tuán)隊(duì)為任意角度多智能體路徑規(guī)劃提供了一種高效且實(shí)用的解決方案，具有重要的理論和實(shí)際意義。通過進(jìn)一步的研究和改進(jìn)，AA-CCBS算法有望在更多領(lǐng)域中得到廣泛應(yīng)用，為復(fù)雜路徑規(guī)劃問題提供更優(yōu)的解決方案。（END）

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

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