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

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

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.