Robust Multi-Robot Path Planning and Execution on a Large Scale

大规模鲁棒多机器人路径规划和执行

• 批准号: 2328671
• 负责人: Jiaoyang Li
• 金额: $ 60万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-10-01 至 2026-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2328671&HistoricalAwards=false
• 关键词: Robust; Multi; Robot; Path; Planning

Coordinating a large team of robots to perform navigation tasks in a congested environment is a critical problem in many settings such as automated warehouses. An increasing number of Artificial Intelligence (AI) researchers have been attracted to study an abstract model of this problem, called Multi-Agent Path Finding (MAPF), and made significant progress in the past decade. State-of-the-art MAPF solvers can generate paths in seconds for hundreds of mobile agents (which are simplified versions of robots) in highly congested environments and yet provide important theoretical guarantees such as soundness and even optimality. Yet, these solvers cannot be directly applied to real robots. They ignore constraints on robot dynamics such as limits on acceleration and do not account for the uncertainty in execution such as potential slippage, latency in coordination, and delays in trajectory following. Consequently, in practice, engineers commonly ignore these advanced MAPF solvers and instead opt for much simpler techniques that can often generate poor-quality solutions but are easy to adapt. This project aims to close this gap by investigating how to provide a safe and effective multi-robot path planning and execution framework that enables hundreds of heterogeneous robots to move to their desired locations in the presence of complex obstacles, non-holonomic dynamics, actuation limits, and disturbances while minimizing their travel times and communication efforts.This project builds on the recent work on Temporal Plan Graphs (TPGs), which relaxes an MAPF plan by allowing arbitrary modifications to the robot speeds as long as the ordering with which each robot visits each location is preserved. This project leverages some insights behind TPG but aims to develop a coordination-aware algorithmic framework that interleaves multi-robot planning with coordination and control. The first thrust focuses on handling robot dynamics and temporal tracking errors by developing relaxed and adaptive TPGs that enforce only critical precedence constraints and allow for the re-optimization of TPGs on the fly. The second thrust extends the first one by further considering spatial tracking errors and integrating reachability analysis and controller optimization into MAPF and TPG algorithms. The third thrust aims at developing MAPF algorithms that provide provably fast planning and re-planning times by extending a recently introduced concept of Provably Constant-Time Motion Planning to the domain of multi-agent planning. The last thrust develops an open-source platform for testing MAPF algorithms in a more realistic setting that includes constraints on robot dynamics and uncertainty in execution.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

在自动化仓库等许多环境中，协调大型机器人团队在拥挤的环境中执行导航任务是一个关键问题。越来越多的人工智能（AI）研究人员被吸引来研究这个问题的抽象模型，称为多智能体路径查找（MAPF），并在过去十年中取得了重大进展。最先进的 MAPF 求解器可以在高度拥挤的环境中在几秒钟内为数百个移动代理（机器人的简化版本）生成路径，并提供重要的理论保证，例如健全性甚至最优性。然而，这些求解器不能直接应用于真实的机器人。它们忽略了机器人动力学的约束，例如加速度的限制，并且没有考虑执行中的不确定性，例如潜在的滑动、协调的延迟和轨迹跟踪的延迟。因此，在实践中，工程师通常会忽略这些先进的 MAPF 求解器，而是选择更简单的技术，这些技术通常会生成质量较差的解决方案，但很容易适应。该项目旨在通过研究如何提供安全有效的多机器人路径规划和执行框架来缩小这一差距，该框架使数百个异构机器人能够在存在复杂障碍、非完整动力学、驱动限制和干扰的情况下移动到其所需位置，同时最大限度地减少其行进时间和通信工作。该项目建立在最近关于时间计划图（TPG）的工作的基础上，该框架通过以下方式放宽了 MAPF 计划 只要保留每个机器人访问每个位置的顺序，就允许任意修改机器人速度。该项目利用了 TPG 背后的一些见解，但旨在开发一种协调感知算法框架，将多机器人规划与协调和控制交织在一起。第一个重点是通过开发宽松的自适应 TPG 来处理机器人动力学和时间跟踪误差，这些 TPG 仅强制执行关键优先级约束，并允许动态重新优化 TPG。第二个推力通过进一步考虑空间跟踪误差并将可达性分析和控制器优化集成到 MAPF 和 TPG 算法中来扩展第一个推力。第三个重点旨在开发 MAPF 算法，通过将最近引入的可证明恒定时间运动规划概念扩展到多智能体规划领域，提供可证明的快速规划和重新规划时间。最后一个重点是开发一个开源平台，用于在更现实的环境中测试 MAPF 算法，其中包括对机器人动力学的约束和执行中的不确定性。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。