db-LaCAM: Fast and Scalable Multi-Robot Kinodynamic Motion Planning with Discontinuity-Bounded Search and Lightweight MAPF
作者: Akmaral Moldagalieva, Keisuke Okumura, Amanda Prorok, Wolfgang Hönig
分类: cs.RO
发布日期: 2025-12-07 (更新: 2025-12-09)
💡 一句话要点
提出db-LaCAM，加速可扩展的多机器人运动规划，提升动态环境适应性。
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 多机器人运动规划 运动原语 多智能体路径寻找 动力学约束 机器人集群
📋 核心要点
- 现有运动规划器计算量大，难以扩展到大量机器人，限制了规划速度和应用范围。
- db-LaCAM结合MAPF的速度和运动规划器的动力学感知，利用预计算的运动原语生成运动序列。
- 实验表明，db-LaCAM在高达50个机器人的场景中，速度提升10倍，并保持了相当的解质量。
📝 摘要（中文）
本文提出了一种名为discontinuity-Bounded LaCAM (db-LaCAM) 的多机器人运动规划器，旨在解决现有方法计算负担高、难以扩展到大量机器人的问题。db-LaCAM结合了多智能体路径寻找（MAPF）算法的速度和可扩展性，以及运动规划器对动力学的感知能力。该方法利用预先计算的、符合机器人动力学的运动原语生成固定时域的运动序列，并允许连续运动之间存在用户定义的不连续性。db-LaCAM在运动原语的粒度上是完备的，并支持任意机器人动力学。实验结果表明，db-LaCAM能够高效地扩展到最多50个机器人的场景，与现有方法相比，运行时间最多可加快十倍，同时保持相当的解质量。该方法已在2D和3D环境中进行了验证，并支持如单轮车和3D双积分器等动力学模型。通过飞行机器人和带拖车汽车机器人的物理实验，验证了db-LaCAM规划轨迹的安全性。
🔬 方法详解
问题定义：现有最先进的多机器人运动规划器由于计算负担过重，难以处理大量机器人，这限制了它们的可扩展性并导致规划时间过长。因此，需要一种既能处理复杂动力学约束，又能高效扩展到大规模机器人群体的运动规划方法。
核心思路：db-LaCAM的核心思路是将多智能体路径寻找（MAPF）算法的可扩展性和速度与运动规划器对动力学的感知能力相结合。通过预先计算一组符合机器人动力学的运动原语，并允许在连续运动之间存在一定程度的不连续性，从而在保证解质量的同时显著提高规划速度。
技术框架：db-LaCAM的整体框架包括以下几个主要阶段：1) 预计算运动原语：根据机器人动力学模型，预先计算一组运动原语，这些原语代表了机器人可以执行的基本运动单元。2) MAPF规划：使用MAPF算法在离散化的状态空间中寻找机器人的初始路径。3) 运动序列生成：基于MAPF的路径，利用预计算的运动原语生成机器人的运动序列。4) 冲突解决：检测并解决机器人之间的潜在冲突，例如通过调整运动序列或重新规划路径。
关键创新：db-LaCAM的关键创新在于它将MAPF算法与运动原语相结合，从而实现了在保证动力学约束的同时，显著提高了规划速度和可扩展性。与传统的运动规划方法相比，db-LaCAM避免了在连续空间中进行搜索，而是利用预计算的运动原语在离散空间中进行规划，从而大大降低了计算复杂度。
关键设计：db-LaCAM的关键设计包括：1) 运动原语的生成：运动原语需要充分覆盖机器人的状态空间，并满足机器人动力学约束。2) 不连续性约束：允许连续运动之间存在一定程度的不连续性，可以提高规划的灵活性，但也需要仔细控制，以避免产生不安全的轨迹。3) MAPF算法的选择：选择合适的MAPF算法对于保证规划速度和解质量至关重要。论文中使用的MAPF算法未知。
🖼️ 关键图片
📊 实验亮点
实验结果表明，db-LaCAM在高达50个机器人的场景中，运行速度比现有最先进的规划器快10倍，同时保持了相当的解质量。该方法在2D和3D环境中进行了验证，并支持单轮车和3D双积分器等动力学模型。此外，通过飞行机器人和带拖车汽车机器人的物理实验，验证了db-LaCAM规划轨迹的安全性。
🎯 应用场景
db-LaCAM适用于需要大量机器人协同工作的场景，例如仓库自动化、物流配送、农业机器人、搜索救援等。该方法能够快速生成安全可靠的运动轨迹，提高机器人系统的效率和安全性，并降低人工干预的需求。未来，该技术有望应用于更复杂的动态环境和更大规模的机器人集群。
📄 摘要（原文）
State-of-the-art multi-robot kinodynamic motion planners struggle to handle more than a few robots due to high computational burden, which limits their scalability and results in slow planning time. In this work, we combine the scalability and speed of modern multi-agent path finding (MAPF) algorithms with the dynamic-awareness of kinodynamic planners to address these limitations. To this end, we propose discontinuity-Bounded LaCAM (db-LaCAM), a planner that utilizes a precomputed set of motion primitives that respect robot dynamics to generate horizon-length motion sequences, while allowing a user-defined discontinuity between successive motions. The planner db-LaCAM is resolution-complete with respect to motion primitives and supports arbitrary robot dynamics. Extensive experiments demonstrate that db-LaCAM scales efficiently to scenarios with up to 50 robots, achieving up to ten times faster runtime compared to state-of-the-art planners, while maintaining comparable solution quality. The approach is validated in both 2D and 3D environments with dynamics such as the unicycle and 3D double integrator. We demonstrate the safe execution of trajectories planned with db-LaCAM in two distinct physical experiments involving teams of flying robots and car-with-trailer robots.