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

协调一大群机器人在拥挤的环境中执行导航任务是自动化仓库等许多环境中的关键问题。越来越多的人工智能（AI）研究者开始研究这一问题的抽象模型--多智能体路径寻找（MAPF），并在过去十年中取得了显著的进展。最先进的MAPF求解器可以在几秒钟内为高度拥挤的环境中的数百个移动的代理（机器人的简化版本）生成路径，但提供了重要的理论保证，如可靠性，甚至最优性。然而，这些求解器不能直接应用于真实的机器人。它们忽略了对机器人动力学的约束，例如加速度限制，并且没有考虑执行中的不确定性，例如潜在的滑动，协调延迟和轨迹跟踪延迟。因此，在实践中，工程师通常会忽略这些先进的MAPF求解器，而是选择更简单的技术，这些技术通常可以生成质量较差的解决方案，但易于适应。该项目旨在通过研究如何提供一个安全有效的多机器人路径规划和执行框架来缩小这一差距，该框架使数百个异构机器人能够在存在复杂障碍物、非完整动力学、驱动限制和干扰的情况下移动到其期望位置，同时最大限度地减少其旅行时间和通信努力。其通过允许任意修改机器人速度来放松MAPF计划，只要保持每个机器人访问每个位置的顺序即可。该项目利用了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.