多智能体门路布局新打破 AA

多智能体门路布局（MAPF）是一个在机器人、交通控制和智能化仓库等畛域具备宽泛运行的关键疑问。MAPF的外围指标是为一组智能体找到一组无抵触的门路，使它们能够从终点移动到指标位置。传统的MAPF疑问通常限度智能体只能在预约义的图上移动，这种限度在实践运行中或者不够灵敏。

恣意角度门路布局（Any-Angle Pathfinding）是一种更为灵敏的方法，准许智能体在不碰撞阻碍物的状况下在恣意位置之间移动。这种方法在提高门路布局效率和顺应复杂环境方面具备清楚长处。但是恣意角度门路布局也带来了新的应战，特意是在多智能体环境中，如何确保门路的无抵触性和最优性成为一个关键疑问。

被IROS 2024会议接纳论文《Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding》提出了第一个针对恣意角度多智能体门路布局的最优算法，并引见了其有界次优变体。这些算法在处置复杂门路布局疑问时体现杰出，具备关键的实践和实践意义。经过引入延续抵触搜查（CCBS）和安保区间门路布局（TO-AA-SIPP），以及多解放（MC）和分别拆分（DS）技术，论文的算法清楚提高了门路布局的效率和成果。

钻研团队由Konstantin Yakovlev、Anton Andreychuk和Roni Stern组成，他们区分附属于多个出名钻研机构。Konstantin Yakovlev附属于FRC CSC RAS（俄罗斯迷信院计算机迷信与控制钻研中心）、AIRI（人工智能钻研所）、HSE University（初等经济学院）和MIPT（莫斯科物理技术学院）。Anton Andreychuk附属于AIRI（人工智能钻研所）。Roni Stern附属于Ben-Gurion University of the Negev（内盖夫本-古里安大学）。他们在多智能体门路布局畛域具备丰盛的钻研阅历和深沉的学术背景，为论文的钻研提供了松软的基础。

钻研背景

多智能体门路布局（MAPF）是一个在机器人、交通控制和智能化仓库等畛域具备宽泛运行的关键疑问。MAPF的外围指标是为一组智能体找到一组无抵触的门路，使它们能够从终点移动到指标位置。传统的MAPF疑问通常限度智能体只能在预约义的图上移动，这种限度在实践运行中或者不够灵敏。

近年来，钻研人员开局探求放宽这些经典假定的方法。Yakovlev和Andreychuk提出了一种基于优先级布局的恣意角度MAPF算法，这种算法准许智能体在不碰撞阻碍物的状况下在恣意位置之间移动。这一方法在提高门路布局效率和顺应复杂环境方面具备清楚长处。但是恣意角度门路布局也带来了新的应战，特意是在多智能体环境中，如何确保门路的无抵触性和最优性成为一个关键疑问。

其余钻研也提出了支持静止学解放的技术。例如，Yan和Li提出了一种基于优先级搜查的三阶段求解器，能够处置减速和减速举措。这些钻研虽然在必定水平上处置了MAPF中的一些疑问，但它们大多不是最优的。

在最优MAPF求解器方面，许多钻研是对抵触基搜查（CBS）的改良。例如，Solis等人提出了为每个机器人构建路途图并经常使用CBS启动布局的方法，并结合轨迹优化方法为异构智能体团队（如四旋翼机）构建无碰撞门路。Kinodynamic变体的CBS也被提出，用于处置具备不同静止学特性的智能体。

虽然这些钻研在必定水平上处置了MAPF中的一些疑问，但它们大多集中在经典MAPF假定的基础上。论文的钻研旨在进一步放宽这些假定，提出一种新的恣意角度多智能体门路布局算法（AA-CCBS），并经过引入多解放（MC）和分别拆分（DS）技术来提高算法的效率和成果。

疑问陈说

在多智能体门路布局（MAPF）中，指标是为一组智能体找到一组无抵触的门路，使它们能够从终点移动到指标位置。传统的MAPF疑问通常限度智能体只能在预约义的图上移动，这种限度在实践运行中或者不够灵敏。论文钻研的恣意角度多智能体门路布局疑问（AA-MAPF）则放宽了这一限度，准许智能体在不碰撞阻碍物的状况下在恣意位置之间移动。

图1：同一MAPF实例的两个最优解：由基数组成的一个只移动（左），而具备任何角度的一个移动（右）。后者的老本降落了22%。

详细来说，AA-MAPF疑问的指标是找到一组将智能体从终点传送到指标位置的无抵触门路，并且这些门路的总老本最小。每个智能体可以在恣意角度上移动，只需它们的门路不与阻碍物相交。这种恣意角度的移动模式使得门路布局愈加灵敏和高效，但也带来了新的应战，特意是在多智能体环境中，如何确保门路的无抵触性和最优性成为一个关键疑问。

图2：vanilla AA-CCBS多解放的示例。

论文提出的AA-CCBS算法结合了延续抵触搜查（CCBS）和安保区间门路布局（TO-AA-SIPP），旨在处置这些应战。CCBS算法经过在延续时时期隔上启动搜查，防止了时期团圆化的疑问，而TO-AA-SIPP算规律能够处置灵活阻碍物环境中的恣意角度门路布局。经过结合这两种方法，AA-CCBS算法能够在保障门路最优性的同时，提高门路布局的效率。

此外，为了进一步提高算法的功能，论文引入了多解放（MC）和分别拆分（DS）技术。多解放技术经过参与多个解放来缩小上层搜查迭代次数，而分别拆分技术则经过在抵触处置时参与正负解放来缩小搜查上班量。这些技术的结合使得AA-CCBS算法在处置复杂门路布局疑问时体现杰出。

算法引见

钻研团队提出了一种新的恣意角度多智能体门路布局算法，称为AA-CCBS（Any-Angle Continuous Conflict-Based Search）。该算法结合了延续抵触搜查（CCBS）和安保区间门路布局（TO-AA-SIPP），并经过引入多解放（MC）和分别拆分（DS）技术来提高算法的效率和成果。

延续抵触搜查（CCBS）

CCBS是抵触基搜查（CBS）的变体，适用于非团圆时期线。它经过在延续时时期隔上启动搜查，防止了时期团圆化的疑问。CCBS的上班原理是为每个智能体独自找到门路，检测这些门路之间的抵触，并经过对一般智能体从新布局来处置抵触。CCBS经过上层搜查选用要解放的智能体，并经过低层搜查觅到满足解放的门路。

安保区间门路布局（TO-AA-SIPP）

TO-AA-SIPP是SIPP（Safe Interval Path Planning）的变体，旨在为在灵活阻碍物环境中导航的智能体找到最优的恣意角度门路。TO-AA-SIPP的搜查节点由一个元组（顶点，安保时时期隔）标识，示意智能体可以在该时时期隔内安保地驻留在该顶点。与SIPP不同，TO-AA-SIPP不会经过裁减搜查节点来迭代构建搜查树，而是预先生成一切搜查节点，并迭代尝试识别节点之间的正确父子相关，以取得最优解。

多解放（MC）

多解放技术经过参与多个解放来缩小上层搜查迭代次数。论文提出了三种MC方法。

MC1：识别出一切源顶点相反的举措子集，并为每个智能体参与相应的多解放。虽然MC1方法有效，但在AA-MAPF中，相互抵触的举措数量或者很大，造成不安保区间过短，从而削弱解放成果。

MC2：为处置上述疑问，MC2方法经过仅思考有限的举措集和过滤掉造成原始不安保区间缩短的举措来增强解放成果。MC2方法在解放成果上更强。

MC3：进一步裁减MC2，蕴含不同源顶点但相反指标顶点的举措。这些举措或者造成相反智能体在简直相反位置出现碰撞，因此人造地蕴含在同一多解放中。

图3：蕴含多解放的不同版本的举措。请留意，MC2和MC3中举措的时时期隔清楚大于MC1。因此，估量MC2和MC3将体现出更大的修剪才干。

分别拆分（DS）

分别拆分技术经过在抵触处置时参与正负解放来缩小搜查上班量。一个CCBS子节点对智能体i参与负解放，另一个子节点对智能体i参与正解放并对智能体j参与负解放。论文提出了两种成功模式：

间接经常使用DS：这种模式较为间接，经过在抵触处置时参与正负解放来缩小搜查上班量。

结合MC经常使用DS：这种模式须要处置多个终点位置的延续搜查，较为复杂。为了简化DS和MC的集成，论文倡导防止将多解放作为地标，而是经常使用惯例的负多解放。

经过结合这些技术，AA-CCBS算法能够在保障门路最优性的同时，提高门路布局的效率和成果。试验结果标明，这些改良清楚提高了算法的功能，使其在处置复杂门路布局疑问时体现杰出。

试验结果

为了评价AA-CCBS算法的功能，钻研团队在MovingAI基准测试中启动了宽泛的试验。试验经常使用了多个不同类型的地图，包括空地图、随机地图、迷宫地图和仓库地图。每个地图提供了25个场景，每个场景蕴含一组终点和指标位置。试验经过逐渐参与智能体数量，直到算法在300秒的时期限度内不可找到处置打算为止。

试验结果显示，AA-CCBS算法的多种变体在不同场景下体现杰出。详细来说，MC3、DS和DS+MC3变体清楚优于其余变体。MC3在极速处置便捷实例方面体现尤为突出，而DS和DS+MC3在处置复杂实例时体现更佳。

在评价有界次优AA-CCBS时，钻研团队经常使用了不同的次优性界限（w = 1.01, 1.1, 1.25）启动试验。结果标明，MC3在寻觅有界次优解时清楚提高了AA-CCBS的功能，而DS变体未能逾越原始AA-CCBS。这或者是由于DS的正解放在次优搜查中成果较差，不能立刻消弭抵触，而MC3经过对更多举措施加解放，在贪心搜查中更有效地消弭抵触。

详细试验结果如下：

图4:AA-CCBS不同变体的评价。左侧窗格显示了AA-CCBS每个版本在5分钟时期限度内齐全处置的实例数量。两边窗格显示了找到处置打算所需的时期（Y轴以对数刻度示意）。

每个数据点通知算法在必定时期内（Y轴）能够处置多少个实例（X轴）。右正面板展现了处置不同MAPF疑问实例所需的初级迭代次数。X轴显示实例id。每个数据点通知算法（Y轴）对特定疑问实例（X轴）启动了多少次初级迭代。

试验结果标明，AA-CCBS算法及其增强版本在处置恣意角度多智能体门路布局疑问时体现杰出。MC3在极速处置便捷实例和寻觅有界次优解方面体现尤为突出，而DS和DS+MC3在处置复杂实例时体现更佳。这些结果验证了多解放和分别拆分技术在提高算法功能方面的有效性。

有界次优AA-CCBS

在实践运行中，找到最优解往往须要消耗少量时期和计算资源。为了在保障解的品质的同时提高算法的效率，论文提出了有界次优（Bounded Suboptimal, BS）AA-CCBS算法。该算法经过准许解的老本在最优解老本的某个倍数范围内，从而在必定水平上放宽了最优性的要求，以换取更快的求解速度。

图5:AA-CCBS的评价结果及其在不同次优起因下的修正。

成功方法

有界次优AA-CCBS的成功基于在上层搜查中引入焦点搜查（Focal Search）。详细来说，在每次上层迭代中，算法会创立一个名为FOCAL的节点列表。FOCAL蕴含一切生成的节点，这些节点的老本不超越 ( w \cdot f_{\text{min}} )，其中 ( w ) 是次优性界限， ( f_{\text{min}} ) 是惯例AA-CCBS将裁减的节点的老本。

在FOCAL中，算法选用抵触起码的节点启动裁减，并在节点数量相反时优先选用解放更多的节点。这种方法迫使搜查更贪心地处置抵触，同时坚持所需的次优性界限。

试验结果

钻研团队对BS AA-CCBS启动了宽泛的试验，评价了不同次优性界限（ ( w = 1.01, 1.1, 1.25 ) ）下的算法功能。试验结果显示：

论断与未来上班

论文提出了第一个针对恣意角度多智能体门路布局（AA-MAPF）的最优算法AA-CCBS，并经过引入多解放（MC）和分别拆分（DS）技术清楚优化了算法的功能。试验结果标明，这些改良在处置复杂门路布局疑问时体现杰出，能够有效地处置抵触并找到最优解。

详细来说，MC3在极速处置便捷实例和寻觅有界次优解方面体现尤为突出，而DS和DS+MC3在处置复杂实例时体现更佳。这些结果验证了多解放和分别拆分技术在提高算法功能方面的有效性。

未来上班可以从以下几个方面进一步探求和改良。

多解放构成环节：探求更复杂和高效的多解放构成环节，以进一步提高算法的剪枝才干和搜查效率。

增量搜查技术：在恣意角度低层搜查中顺应增量搜查技术，以缩小重复计算和提高求解速度。

实践运行场景：将AA-CCBS算法运行于更多实践场景，如智能驾驶、无人机编队和智能交通系统，验证其在实在环境中的功能和鲁棒性。

算法优化：进一步优化算法的成功，缩小计算资源的消耗，提高算法的可裁减性和适用性。

总之，钻研团队为恣意角度多智能体门路布局提供了一种高效且适用的处置打算，具备关键的实践和实践意义。经过进一步的钻研和改良，AA-CCBS算法有望在更多畛域中获取宽泛运行，为复杂门路布局疑问提供更优的处置打算。（END）

参考资料：

本文转载自​​，作者：