Multi-Agent Motion Planning For Differential Drive Robots Through Stationary State Search

📄 arXiv: 2412.13359v1 📥 PDF

作者: Jingtian Yan, Jiaoyang Li

分类: cs.RO, cs.AI, cs.MA

发布日期: 2024-12-17

💡 一句话要点

提出MASS框架，通过静止状态搜索解决差速驱动机器人多智能体运动规划问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 多智能体运动规划 差速驱动机器人 运动学约束 静止状态搜索 MAPF 仓库自动化

📋 核心要点

  1. 现有MAPF方法在差速驱动机器人多智能体运动规划中，对机器人运动学模型简化，限制了实际应用。
  2. 提出MASS框架，结合MAPF和静止状态搜索规划器，生成运动学可行的高质量规划。
  3. 实验结果表明，MASS在吞吐量方面比现有方法提高了高达400%。

📝 摘要（中文）

多智能体运动规划（MAMP）在交通管理、机场运营和仓库自动化等领域有着广泛的应用。在这些环境中，差速驱动机器人被广泛使用。这些机器人具有运动学模型，只允许原地旋转和沿当前方向移动，并受到速度和加速度的限制。然而，现有的基于多智能体路径寻找（MAPF）的方法通常使用简化的机器人运动学模型，这限制了它们的实用性和真实性。本文介绍了一个名为MASS的三层框架来解决这些挑战。MASS结合了基于MAPF的方法和我们提出的静止状态搜索规划器，以生成高质量的、运动学上可行的计划。我们进一步使用自适应窗口机制扩展了MASS，以解决终身MAMP问题。在单次网格地图域和终身仓库域中对我们的方法进行了实验测试。与现有方法相比，我们的方法在吞吐量方面提高了高达400%。

🔬 方法详解

问题定义：论文旨在解决差速驱动机器人的多智能体运动规划（MAMP）问题。现有基于MAPF的方法通常采用简化的运动学模型，忽略了差速驱动机器人的运动约束（如速度、加速度限制以及只能原地旋转和沿当前方向移动的特性），导致规划结果在实际中难以执行，限制了其在真实场景中的应用。

核心思路：论文的核心思路是将MAMP问题分解为高层路径规划和底层运动规划两个阶段。高层使用MAPF方法进行粗略的路径规划，底层则使用提出的静止状态搜索规划器（Stationary State Search Planner）生成满足差速驱动机器人运动学约束的轨迹。通过这种分层方法，可以在保证规划效率的同时，生成运动学上可行的轨迹。

技术框架：MASS框架包含三个层次：1. 高层MAPF规划：使用现有的MAPF算法（如Conflict-Based Search）在高层进行路径规划，生成每个机器人的粗略路径。2. 静止状态搜索规划：针对高层路径中的每个节点，使用提出的静止状态搜索规划器在局部生成满足运动学约束的轨迹。该规划器以机器人的静止状态为目标，搜索可行的运动序列。3. 自适应窗口机制：为了解决终身MAMP问题，MASS采用自适应窗口机制，动态调整规划范围，以适应环境变化和新的任务需求。

关键创新：论文的关键创新在于提出的静止状态搜索规划器。与传统的运动规划方法不同，该规划器直接在机器人的状态空间中搜索，以静止状态为目标，避免了复杂的运动学建模和约束处理。此外，MASS框架的分层结构也使得MAMP问题得以有效分解，提高了规划效率和可行性。

关键设计：静止状态搜索规划器通过离散化机器人的控制空间（例如，不同的角速度和线速度组合），并使用A搜索算法在状态空间中寻找最优路径。关键设计包括：1. 状态表示：使用机器人的位置、方向角、线速度和角速度来表示机器人的状态。2. 启发式函数：设计启发式函数来估计从当前状态到静止状态的代价，例如，考虑剩余距离和速度的降低。3. 代价函数*：定义代价函数来评估每个运动序列的代价，例如，考虑时间和能量消耗。自适应窗口机制则根据机器人的速度和任务需求动态调整规划范围的大小。

📊 实验亮点

实验结果表明，MASS框架在单次网格地图域和终身仓库域中均表现出色。在吞吐量方面，MASS比现有方法提高了高达400%。这表明MASS能够有效地解决差速驱动机器人的多智能体运动规划问题，并显著提高机器人的协同工作效率。

🎯 应用场景

该研究成果可应用于仓库自动化、交通管理、机场地面车辆调度等领域，尤其是在需要大量差速驱动机器人协同工作的场景中。通过生成运动学可行的轨迹，可以提高机器人的工作效率和安全性，降低能源消耗。未来，该方法可以进一步扩展到更复杂的机器人系统和动态环境中。

📄 摘要（原文）

Multi-Agent Motion Planning (MAMP) finds various applications in fields such as traffic management, airport operations, and warehouse automation. In many of these environments, differential drive robots are commonly used. These robots have a kinodynamic model that allows only in-place rotation and movement along their current orientation, subject to speed and acceleration limits. However, existing Multi-Agent Path Finding (MAPF)-based methods often use simplified models for robot kinodynamics, which limits their practicality and realism. In this paper, we introduce a three-level framework called MASS to address these challenges. MASS combines MAPF-based methods with our proposed stationary state search planner to generate high-quality kinodynamically-feasible plans. We further extend MASS using an adaptive window mechanism to address the lifelong MAMP problem. Empirically, we tested our methods on the single-shot grid map domain and the lifelong warehouse domain. Our method shows up to 400% improvements in terms of throughput compared to existing methods.