多智能体门路布局（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）
参考资料：
本文转载自，作者：