多智能体路径规划（MAPF）是一个在共享环境中为多个智能体规划无碰撞路径的问题。传统上MAPF问题主要在离散环境中研究，时间和空间都被离散化为固定的步长和网格。随着实际应用需求的增加，如仓库物流和自动驾驶车辆，研究逐渐转向连续环境中的路径规划。在连续环境中，时间和空间都是连续的，智能体的运动需要考虑更复杂的运动学和动力学约束。
在离散环境中，MAPF问题通常通过图模型来表示，智能体在图的顶点之间移动，避免在同一时间步出现在同一顶点。然而在连续环境中，智能体的路径需要表示为平滑曲线，避免在任何时间点发生碰撞。这种连续表示更符合实际应用场景，如机器人在复杂环境中的导航。
在连续环境中，时间和空间都是连续的，智能体的运动需要考虑更复杂的运动学和动力学约束。例如，车辆在路径规划中需要考虑加速度和转弯半径，以避免突然的方向变化带来的不稳定性。这种连续表示更符合实际应用场景，如机器人在复杂环境中的导航。
9 月 18 日arXiv的 热门论文《Multi-agent Path Finding in Continuous Environment》提出一种在连续环境中进行多智能体路径规划的新方法，以解决实际应用中的挑战。研究提出了一种新的连续环境冲突基搜索（CE-CBS）算法，该算法结合了高层次搜索框架的冲突基搜索（CBS）和低层次路径规划的RRT*算法。通过这种方法，智能体能够在连续时间和空间中规划平滑的无碰撞路径，满足各种运动学约束。
研究的主要挑战在于如何在连续环境中有效地解决智能体之间的冲突。传统的离散算法在处理连续时间和空间时效率较低，因此需要新的算法来提高路径规划的效率和可靠性。CE-CBS算法通过结合RRT*和B样条曲线平滑处理，展示了在实际应用中的潜力。
本研究由布拉格捷克技术大学信息技术学院的Kristyna Janovská和Pavel Surynek领导。Kristyna Janovská是该学院的研究员，主要研究领域包括多智能体系统、路径规划和连续环境中的智能体运动。Pavel Surynek是该学院的教授，研究领域涵盖人工智能、多智能体系统、路径规划和优化算法。
他们的研究致力于开发新的算法和模型，以解决多智能体在连续环境中的路径规划问题，旨在提高路径规划的效率和可靠性。通过提出的连续环境冲突基搜索（CE-CBS）算法，他们展示了在实际应用中的潜力，并为未来的研究方向提供了新的思路。
理论背景
连续环境中的MAPF问题
在多智能体路径规划（MAPF）中，传统的研究主要集中在离散环境中，即时间和空间都被离散化为固定的步长和网格。然而随着实际应用需求的增加，如仓库物流和自动驾驶车辆，研究逐渐转向连续环境中的路径规划。在连续环境中，时间和空间都是连续的，智能体的运动需要考虑更复杂的运动学和动力学约束。
在离散环境中，时间通常表示为离散的时间步，环境则表示为图的顶点和边，智能体在图的顶点之间移动，避免在同一时间步出现在同一顶点。然而在连续环境中，时间和空间都是连续的，智能体的路径需要表示为平滑曲线，避免在任何时间点发生碰撞。这种连续表示更符合实际应用场景，如机器人在复杂环境中的导航。
为了应对连续环境中的MAPF问题，研究者们提出了多种算法。例如，连续冲突基搜索（CCBS）算法、扩展的增量冲突树搜索（E-ICTS）算法和扩展的冲突基搜索-连续时间（ECBS-CT）算法。这些算法在处理连续时间和空间时表现出色，特别是CCBS算法，它无需时间离散化，直接在连续时间下工作，提供了更为精确的路径规划解决方案。
平滑连续MAPF（SC-MAPF）
平滑连续多智能体路径规划（SC-MAPF）问题是指在度量空间中找到一组平滑曲线，使得多个智能体在移动过程中不发生碰撞。SC-MAPF问题的定义如下：
在SC-MAPF问题中，智能体的路径被定义为平滑曲线，这些曲线需要满足一定的运动学约束，以确保智能体在移动过程中不会发生碰撞。例如，路径段之间的角度必须大于某个最小值，以避免智能体在路径上进行突然的方向变化。此外，智能体的路径还需要考虑其物理尺寸和运动特性，以确保路径的可行性和安全性。
通过引入平滑机制，如B样条曲线，可以使路径更加平滑，从而限制路径的曲率，防止突然转向变化。这不仅可以处理连续时间，还可以处理连续环境，考虑各种运动学或动力学约束，使得路径规划更加符合实际应用需求。
冲突基搜索（CBS）和连续时间冲突基搜索（CCBS）
冲突基搜索（CBS）是一种用于多智能体路径规划（MAPF）的成本最优算法，主要应用于离散环境中。其基本原理是通过分层次的搜索框架来解决智能体之间的路径冲突。CBS算法分为两个层次：高层次和低层次。
在高层次，CBS算法首先为所有智能体计算初始路径，然后检查这些路径是否存在冲突。冲突的定义是在同一时间步内，两个或多个智能体出现在同一个顶点。如果发现冲突，算法会生成两个新的约束，每个约束禁止其中一个冲突智能体在冲突时间步内进入冲突顶点。然后，算法将这两个约束分别添加到两个新的子问题中，并递归地解决这些子问题。
在低层次，CBS算法使用单智能体路径规划算法（如A*）为每个智能体计算路径。路径必须满足高层次提供的约束，即智能体不能在特定时间步内进入特定顶点。通过这种方式，CBS算法能够逐步解决冲突，找到一组无冲突的路径。
CBS算法的优点在于其解决方案的成本最优性，即找到的路径集的总成本最小。然而，由于其在离散环境中工作，时间和空间都被离散化为固定的步长和网格，这在处理实际应用中的连续环境时可能会遇到效率问题。
连续时间冲突基搜索（CCBS）算法是CBS算法的扩展，旨在解决连续时间下的多智能体路径规划问题。与CBS算法不同，CCBS算法在连续时间下工作，不需要将时间离散化为固定的时间步。
在CCBS算法中，冲突的定义和解决方式有所不同。由于时间是连续的，冲突不再仅仅是两个智能体在同一时间步内出现在同一个顶点，而是两个智能体在某个时间段内的路径重叠。具体来说，CCBS算法定义了一个不安全时间间隔，如果一个智能体在这个时间间隔内到达冲突位置，则认为存在冲突。
CCBS算法的高层次和低层次操作与CBS算法类似，但在处理冲突时需要考虑连续时间。高层次仍然负责检测冲突并生成约束，但这些约束现在包括不安全时间间隔。低层次则使用RRT*算法进行路径规划，确保路径在连续时间和空间下无冲突。
结合RRT*算法和B样条曲线平滑处理，CCBS算法能够在连续环境中生成平滑的无冲突路径。与CBS算法相比，CCBS算法在处理实际应用中的连续时间和空间时表现出更高的效率和可靠性。
快速扩展随机树（RRT）和RRT*
RRT算法
快速扩展随机树（RRT）是一种用于路径规划的经典算法，特别适用于高维度的连续度量空间。RRT算法的基本概念是通过随机采样来构建一棵快速扩展的树，从而探索路径空间。其主要特点是能够在复杂环境中高效地找到一条从起点到目标点的路径。
RRT算法的工作原理如下：
初始化：从起点开始，创建一个包含起点的树。
随机采样：在搜索空间中随机生成一个点。
扩展树：找到树中距离随机点最近的节点，并尝试从该节点向随机点扩展一条路径。如果路径不与障碍物相交，则将随机点添加到树中。
迭代：重复上述步骤，直到找到一条从起点到目标点的路径，或者达到预设的迭代次数。
RRT算法的优点在于其简单性和高效性，特别是在处理高维度和复杂环境时。然而，RRT算法生成的路径通常不是最优的，可能包含许多不必要的绕行和急转弯。
为了克服RRT算法的不足，研究者们提出了RRT算法。RRT是RRT的改进版本，通过引入A*算法的成本函数，使得生成的路径逐渐收敛到最优解。
图1：成功避开狭窄障碍物的平滑路径。从蓝色圆圈起始位置到绿色圆圈目标位置的结果路径以绿色突出显示。红色显示了采样的RRT*树。
RRT*算法的改进主要体现在以下几个方面：
路径优化：在每次扩展树时，不仅考虑从最近的节点扩展路径，还会检查新节点是否可以通过其他路径更优地连接到树中。这种优化过程使得路径逐渐接近最优解。
重连操作：在添加新节点后，RRT*会尝试重新连接树中的其他节点，以进一步优化路径。这种重连操作可以消除不必要的绕行和急转弯，使路径更加平滑和高效。
RRT算法在路径规划中的优势在于其能够生成更优的路径，同时保持RRT算法的高效性。通过结合路径优化和重连操作，RRT能够在复杂环境中找到更短、更平滑的路径，适用于需要高精度路径规划的应用场景。
在连续环境中的多智能体路径规划中，RRT算法被广泛应用于低层次路径规划。通过结合高层次的冲突基搜索（CBS）算法，RRT能够在连续时间和空间中生成无冲突的平滑路径，满足各种运动学约束。
路径平滑处理
B样条曲线
B样条曲线是一种广泛应用于计算机图形学和路径规划中的数学工具。它是一种分段多项式曲线，通过一组控制点来定义曲线的形状。B样条曲线的一个显著特点是它能够生成平滑的曲线，这对于路径规划中的平滑处理尤为重要。
B样条曲线的定义如下：
通过这些元素，B样条曲线可以表示为控制点和基函数的线性组合。具体来说，给定一组控制点和节点向量，B样条曲线上的任意一点都可以通过基函数的加权和来计算。
路径平滑算法
在多智能体路径规划中，路径平滑处理是为了确保生成的路径不仅无碰撞，而且平滑且符合运动学约束。使用B样条曲线进行路径平滑处理的步骤如下：
通过上述步骤，使用B样条曲线进行路径平滑处理，可以有效地生成符合实际应用需求的平滑路径。这种方法不仅提高了路径的可行性和安全性，还能够显著减少智能体在路径上的急转弯和不必要的绕行，从而提高路径规划的效率和可靠性。
提出的模型
CE-CBS算法
连续环境冲突基搜索（CE-CBS）算法是本文提出的一种新方法，旨在解决连续环境中的多智能体路径规划问题。该算法结合了冲突基搜索（CBS）和快速扩展随机树（RRT*）算法，并通过B样条曲线进行路径平滑处理。
算法概述
高层次搜索：CE-CBS算法的高层次部分基于传统的CBS算法。首先为所有智能体计算初始路径，然后检查这些路径是否存在冲突。如果发现冲突，算法会生成新的约束，禁止冲突智能体在冲突时间段内进入冲突位置。
低层次搜索：在低层次部分，CE-CBS使用RRT算法进行路径规划。RRT算法通过随机采样和路径优化，生成无冲突的路径。与传统的RRT*不同，CE-CBS在路径规划过程中考虑了连续时间和空间的约束。
路径平滑处理：生成的路径可能包含急转弯和不必要的绕行。为了提高路径的平滑性和可行性，CE-CBS使用B样条曲线对路径进行平滑处理。通过控制点和基函数的线性组合，生成平滑的曲线，确保路径满足运动学约束。
算法步骤
通过这种方法，CE-CBS算法能够在连续时间和空间中生成无冲突的平滑路径，适用于实际应用中的复杂环境。
智能体模型
在CE-CBS算法中，智能体被定义为具有固定半径和速度的圆形物体。智能体在已知环境中移动，避开静态和动态障碍物。具体来说，智能体模型包括以下几个方面。
智能体定义：智能体被定义为具有固定半径和速度的圆形物体。智能体的初始位置和目标位置在环境中预先设定。
运动学约束：智能体的路径必须满足一定的运动学约束，如最小转弯半径和最大加速度。这些约束确保智能体在路径上移动时不会发生突然的方向变化，从而保证运动的平滑性和稳定性。
避障策略：智能体在路径规划过程中需要避开静态和动态障碍物。静态障碍物是环境中的固定物体，如墙壁和家具。动态障碍物是其他智能体，它们在环境中移动，可能与当前智能体发生碰撞。
路径验证：生成的路径需要经过验证，确保路径段之间的角度满足最小角度约束，路径上的每个点都不与障碍物相交。如果路径不满足约束，需要重新规划和调整，直到找到满足要求的路径。
通过结合RRT*算法和B样条曲线平滑处理，CE-CBS算法能够生成符合实际应用需求的平滑路径。智能体在已知环境中移动，避开静态和动态障碍物，确保路径的可行性和安全性。
实验结果
实验设置
为了验证CE-CBS算法在连续环境中的性能，研究团队设计了一系列实验，测试不同参数设置和场景类型下的模型表现。实验主要关注以下几个参数。
实验场景包括不同大小和复杂度的环境，包含静态和动态障碍物。智能体的起点和目标位置在环境中随机分布，以模拟实际应用中的多种情况。
图2：显示每个代理的平均路径长度与ηmax之间关系的实验结果图。
图3：显示CE-CBS迭代次数如何根据不同的ηmax而变化的图。
实验结果分析
实验结果显示，随着ηmax的增加，路径质量显著提高。较大的ηmax值允许RRT*更深入地探索环境，生成更接近最优的路径。然而较大的ηmax值也增加了计算时间，特别是在复杂环境中。实验还发现，当ηmax超过一定值（如5000）后，路径质量的提升变得不明显，但计算时间显著增加。因此，在实际应用中，需要在路径质量和计算时间之间找到平衡。
图 6：不同设置参数ηmax的运行结果比较——样本RRT*节点的最大数量。
实验表明，较大的α值可以有效避免路径中的急转弯，提高路径的平滑性和可行性。然而，较大的α值也可能导致路径长度增加，因为智能体需要绕过更多的障碍物。实验结果显示，当α值在90度左右时，路径质量和计算时间之间的平衡效果最佳。
实验结果显示，随着智能体半径r的增加，路径成本总和也随之增加。较大的智能体需要更长的绕行路径以避免与障碍物和其他智能体发生碰撞。实验还发现，较大的智能体半径可以减少路径规划中的冲突次数，因为智能体需要保持更大的安全距离，从而减少了搜索空间。
图9：不同设置参数r-代理半径的运行结果比较。
图10：关于试剂半径r的实验结果。
CBS与CE-CBS比较
为了评估CE-CBS算法在连续环境中的优势，研究团队将其与标准CBS算法进行了比较。实验设置为将连续环境转换为2D网格，使用A*作为低层算法的标准CBS进行比较。结果显示，CE-CBS算法在连续环境中表现出显著优势。
图11：使用离散CBS（左）和连续CE-CBS（右）规划的路径。
路径质量：CE-CBS算法生成的路径更短、更平滑，因为它不受网格移动限制。实验结果显示，CE-CBS算法在所有测试案例中都找到了无冲突的解决方案，而标准CBS算法在某些情况下未能解决时间冲突。
计算时间：尽管CE-CBS算法在某些情况下需要更多的计算时间，但其生成的路径质量显著提高，特别是在复杂环境中。实验结果表明，CE-CBS算法在处理连续时间和空间时表现出更高的效率和可靠性。
图12:CE-CBS在地图4×4网格上，4个代理从蓝色位置开始，绿色目标位置。
图13:CE-CBS在地图4×4网格上，一个矩形障碍物阻挡了两个单元和三个代理。
从实验结果来看，CE-CBS算法在连续环境中的多智能体路径规划中展示了显著的优势，能够生成高质量的无冲突路径，适用于实际应用中的复杂环境。
讨论
在实验中，不同参数对CE-CBS算法的解决方案质量和计算时间产生了显著影响。
RRT*的最大节点数（ηmax）
随着ηmax的增加，RRT算法能够更深入地探索环境，生成更接近最优的路径。然而，当ηmax超过一定值（如5000）后，路径质量的提升变得不明显。这是因为RRT在较大搜索空间中已经找到了接近最优的路径，进一步增加节点数对路径质量的影响有限。
较大的ηmax值显著增加了计算时间，特别是在复杂环境中。实验结果显示，随着ηmax的增加，CE-CBS算法的迭代次数和计算时间也相应增加。因此，在实际应用中，需要在路径质量和计算时间之间找到平衡。
路径段之间的最小角度值（α）
较大的α值可以有效避免路径中的急转弯，提高路径的平滑性和可行性。实验表明，当α值在90度左右时，路径质量和计算时间之间的平衡效果最佳。
较大的α值可能导致路径长度增加，因为智能体需要绕过更多的障碍物。然而，这种增加是可以接受的，因为它显著提高了路径的平滑性和智能体的运动稳定性。
智能体半径（r）
随着智能体半径r的增加，路径成本总和也随之增加。较大的智能体需要更长的绕行路径以避免与障碍物和其他智能体发生碰撞。
较大的智能体半径可以减少路径规划中的冲突次数，因为智能体需要保持更大的安全距离，从而减少了搜索空间。这种减少冲突的效果在复杂环境中尤为明显。
CE-CBS算法在不同类型的环境中展示了良好的适应性，特别是在狭窄通道和多冲突区域中的导航能力。
狭窄通道
在狭窄通道中，智能体需要精确地规划路径，以避免与障碍物发生碰撞。CE-CBS算法通过结合RRT*和B样条曲线，能够生成平滑且无冲突的路径，确保智能体在狭窄通道中顺利导航。
在狭窄通道中，智能体之间的冲突更容易发生。CE-CBS算法通过高效的冲突检测和解决机制，能够及时发现并解决冲突，确保智能体的安全移动。
多冲突区域
在多冲突区域中，智能体需要频繁调整路径以避免与其他智能体发生碰撞。CE-CBS算法通过动态调整RRT*的最大节点数和路径段之间的最小角度值，能够灵活应对复杂环境中的多种冲突情况。
尽管多冲突区域增加了路径规划的复杂性，CE-CBS算法仍然能够在合理的计算时间内找到无冲突的路径。实验结果表明，CE-CBS算法在处理多冲突区域时表现出较高的计算效率和路径质量。
总体而言，CE-CBS算法在不同类型的环境中展示了良好的适应性和鲁棒性，能够有效解决连续环境中的多智能体路径规划问题。通过合理调整参数，CE-CBS算法能够在保证路径质量的同时，显著提高计算效率，适用于实际应用中的复杂场景。（END）
参考资料：
本文转载自，作者：