Optimal Multilayered Motion Planning for Multiple Differential Drive Mobile Robots with Hierarchical Prioritization (OM-MP)
作者: Zong Chen, Songyuan Fa, Yiqun Li
分类: cs.RO
发布日期: 2024-05-11
💡 一句话要点
提出一种多层优化运动规划方法OM-MP，用于解决多差分驱动机器人编队控制问题。
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 多智能体规划 运动规划 编队控制 差分驱动机器人 分层优化
📋 核心要点
- 现有MAPF方法难以处理复杂动态环境下的多智能体轨迹规划问题，尤其是在差分驱动机器人编队控制方面。
- 该方法采用多层优化策略，将MAPF问题转化为MATP问题，通过全局和局部规划器的协同优化，实现高效的轨迹规划。
- 实验结果表明，该方法在容量、可扩展性和任务最优性方面优于CBS、ECBS等现有算法，验证了其有效性。
📝 摘要（中文）
本文提出了一种新的框架，用于解决复杂和动态环境中多智能体规划和编队控制的挑战。该框架将多智能体路径寻找（MAPF）问题转化为多智能体轨迹规划（MATP）问题。与传统的MAPF解决方案不同，我们的多层优化方案包括一个全局规划器优化求解器，专门用于确定每个机器人的简洁全局路径，以及一个局部规划器，其中嵌入了优化求解器，旨在确保局部机器人轨迹的可行性。通过实施分层优先级策略，我们提高了机器人的效率并逼近全局最优解。具体来说，在全局规划器中，我们采用增强图搜索（AGS）算法，该算法显著提高了求解速度。同时，在局部规划器优化求解器中，我们利用控制屏障函数（CBF），并引入了基于时间轴的倾斜圆柱形障碍物边界框以进行避障，并构建了一个单机器人局部感知通信圈，以确保局部优化解决方案的简单性、速度和准确性。此外，我们还集成了路径轨迹的权重和优先级，以防止在限制场景中出现死锁。与其他最先进的方法（包括CBS、ECBS和其他衍生算法）相比，我们的方法在容量、灵活的可扩展性和整体任务最优性方面表现出卓越的性能，这已通过仿真和实验得到验证。
🔬 方法详解
问题定义：论文旨在解决多差分驱动移动机器人在复杂动态环境中进行高效、无碰撞的编队控制问题。现有MAPF方法通常只关注路径规划，忽略了机器人运动学约束和动态环境的影响，导致实际应用中性能下降，甚至无法实现编队控制。此外，现有方法在处理大规模机器人编队时，计算复杂度较高，难以满足实时性要求。
核心思路：论文的核心思路是将多智能体路径寻找（MAPF）问题转化为多智能体轨迹规划（MATP）问题，并采用分层优化策略。全局规划器负责生成粗略的全局路径，局部规划器负责生成满足机器人运动学约束和避障要求的局部轨迹。通过全局和局部规划器的协同优化，实现高效、安全的编队控制。分层优先级策略用于解决多机器人之间的冲突，提高规划效率。
技术框架：该方法包含两个主要模块：全局规划器和局部规划器。全局规划器采用增强图搜索（AGS）算法，快速生成每个机器人的全局路径。局部规划器利用控制屏障函数（CBF）进行避障，并构建单机器人局部感知通信圈，简化局部优化问题。全局规划器将路径信息传递给局部规划器，局部规划器根据全局路径和环境信息生成局部轨迹。
关键创新：该方法的主要创新点在于：1) 将MAPF问题转化为MATP问题，考虑了机器人运动学约束和动态环境的影响；2) 采用分层优化策略，将全局路径规划和局部轨迹规划解耦，降低了计算复杂度；3) 引入倾斜圆柱形障碍物边界框和单机器人局部感知通信圈，提高了避障效率和局部优化的速度。
关键设计：全局规划器中的AGS算法通过增加额外的节点和边来扩展搜索空间，从而提高搜索效率。局部规划器中的控制屏障函数（CBF）用于保证机器人之间的安全距离，避免碰撞。倾斜圆柱形障碍物边界框用于简化障碍物表示，降低计算复杂度。单机器人局部感知通信圈用于限制局部优化的范围，提高优化速度。
🖼️ 关键图片
📊 实验亮点
实验结果表明，与CBS、ECBS等现有算法相比，该方法在容量、可扩展性和任务最优性方面均有显著提升。具体来说，在相同环境下，该方法能够处理更多数量的机器人，并且能够更快地找到最优解。此外，该方法在动态环境下的鲁棒性也优于现有算法。
🎯 应用场景
该研究成果可应用于仓储物流、自动驾驶、救援等领域。在仓储物流中，可用于实现多机器人协同搬运，提高效率。在自动驾驶领域，可用于实现多车辆编队行驶，提高道路利用率。在救援领域，可用于实现多机器人协同搜索，提高救援效率。该方法具有良好的可扩展性，可以应用于更大规模的机器人编队控制。
📄 摘要（原文）
We present a novel framework for addressing the challenges of multi-Agent planning and formation control within intricate and dynamic environments. This framework transforms the Multi-Agent Path Finding (MAPF) problem into a Multi-Agent Trajectory Planning (MATP) problem. Unlike traditional MAPF solutions, our multilayer optimization scheme consists of a global planner optimization solver, which is dedicated to determining concise global paths for each individual robot, and a local planner with an embedded optimization solver aimed at ensuring the feasibility of local robot trajectories. By implementing a hierarchical prioritization strategy, we enhance robots' efficiency and approximate the global optimal solution. Specifically, within the global planner, we employ the Augmented Graph Search (AGS) algorithm, which significantly improves the speed of solutions. Meanwhile, within the local planner optimization solver, we utilize Control Barrier functions (CBFs) and introduced an oblique cylindrical obstacle bounding box based on the time axis for obstacle avoidance and construct a single-robot locally aware-communication circle to ensure the simplicity, speed, and accuracy of locally optimized solutions. Additionally, we integrate the weight and priority of path traces to prevent deadlocks in limiting scenarios. Compared to the other state-of-the-art methods, including CBS, ECBS and other derivative algorithms, our proposed method demonstrates superior performance in terms of capacity, flexible scalability and overall task optimality in theory, as validated through simulations and experiments.