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

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

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.