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背后的一些见解，但旨在开发一种协调感知的算法框架，该算法将多机器人计划与协调和控制交织在一起。第一个推力重点是通过开发放松和适应性的TPG来处理机器人动力学和时间跟踪误差，这些误差仅执行关键的优先限制，并允许即时进行TPG重新挑选。第二个推力通过进一步考虑空间跟踪误差以及将可及性分析和控制器优化整合到MAPF和TPG算法中来扩展第一个推力。第三个推力旨在开发MAPF算法，这些算法通过将最近引入的恒定时间运动计划的概念扩展到多代理计划的领域，从而提供快速的计划和重新计划时间。最后的推力开发了一个开源平台，用于在更现实的环境中测试MAPF算法，其中包括对机器人动态的限制和执行中的不确定性。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准来通过评估来支持的。