Expediting Solutions to Hard Multi-Robot Path Finding Instances

加速硬多机器人路径查找实例的解决方案

• 批准号: 2330942
• 负责人: Nora Ayanian
• 金额: $ 60万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-11-01 至 2026-10-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2330942&HistoricalAwards=false
• 关键词: Expediting; Solutions; Hard; Multi; Robot

How can many independent robots completing tasks in a shared space move about safely without collisions? There are many scenarios where using many robots working together can improve efficiency, safety, and quality of life. For example, self-driving cars can move people quickly, safely, and efficiently, while reducing delays and vehicular accidents. Warehouse robots can pick and pack items without humans walking around a giant warehouse, which can lead to the human employees’ exhaustion and repetitive injuries. Autonomous drones delivering residential packages can reduce vehicular traffic on the road and provide reliable and extremely quick delivery. Coordinating many robots safely and efficiently in cluttered environments is fundamentally important in these and many other current and future real-world problems. As robots become an increasingly common element of our society, multi-robot coordination will grow exponentially in importance. In this project, we will try to deepen our understanding of the problem of collision-free path finding for many robots in a shared space. The problem of optimally coordinating many robots to maximize efficiency or speed while avoiding collisions is extremely computationally intensive. While there exist a large array of algorithms that can solve these problems, each of these algorithms excel in some instances but flop in others. Currently, experts in solving this problem have a general sense of which algorithms will handle certain instances of a planning problem, but having an expert in the loop is not feasible for large-scale deployment, for example, in self-driving cars or drone package delivery. In this project, we will take a data-driven approach to understanding under what conditions solvers excel, and under what conditions they stumble. The goal of this project is to find novel ways to break down large problems into smaller subproblems that can be more easily solved and understand the gaps that exist in the current array of solvers, so that future solvers can be developed to address those gaps. The problem of finding collision-free paths for multiple agents from start vertices to assigned goal vertices in a graph, known as the labeled multi-agent path finding (MAPF) problem, is NP-Hard. Labeled MAPF is well studied, with many optimal solvers available; however, they are not able to scale to the number of robots present in some modern multi-robot systems, such as autonomous warehouses. Rather than develop new MAPF solvers, this research will use existing machine learning techniques to leverage the strengths of existing labeled MAPF solvers, producing new techniques and algorithms that will allow scaling up for application to large robot swarms and will solve instances that existing solvers cannot yet solve. The approach is threefold. First, the team will exploit the strengths of MAPF solvers by using machine learning to train an algorithm selector to predict the fastest MAPF solver for a particular instance from a portfolio of solvers. Second, they will develop methods for effective decomposition of large MAPF instances into smaller sub-instances that can be solved in parallel using solvers selected by our algorithm selector, increasing speed and scale. Finally, they will develop methods for estimating the empirical hardness of a MAPF instance, i.e., how long each solver will take to solve an instance. Results will be evaluated using established metrics for MAPF solvers, measuring the number of new instances our algorithms solve, and progressively demonstrating them in simulations with hundreds of robots. This project will significantly improve the tractability of many-robot path finding and provide understanding of the hardness of the problem at scale. It will expand the limited understanding of what makes some MAPF instances challenging; develop novel algorithms and techniques to enhance existing and future MAPF algorithms; and significantly increasing the number of robots for which optimal non-colliding paths can be found. It will also produce the largest benchmarking of optimal MAPF solvers to date and help other MAPF researchers understand the strengths and weaknesses of existing MAPF solvers. The work is at the intersection of robotics and combinatorial optimization and will be instantly impactful to those communities. The results will significantly improve planning performance for many-robot systems, and thus will have far-reaching impacts in robotic warehousing, autonomous vehicles, autonomous delivery, just-in-time manufacturing, and many other fields.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.

如何才能让许多独立的机器人在共享空间中完成任务，而不会发生碰撞？在许多情况下，使用许多机器人一起工作可以提高效率，安全性和生活质量。例如，自动驾驶汽车可以快速、安全、高效地运送人员，同时减少延误和交通事故。仓库机器人可以在没有人类的情况下挑选和包装物品，这可能会导致人类员工的疲惫和重复性伤害。自动无人机交付住宅包裹可以减少道路上的车辆交通，并提供可靠和非常快速的交付。在混乱的环境中安全有效地协调许多机器人在这些以及许多其他当前和未来的现实世界问题中至关重要。随着机器人成为我们社会中越来越常见的元素，多机器人协调的重要性将呈指数级增长。在这个项目中，我们将试图加深我们对共享空间中多个机器人的无碰撞路径寻找问题的理解。优化协调多个机器人以最大限度地提高效率或速度，同时避免碰撞的问题是非常计算密集型的。虽然存在大量可以解决这些问题的算法，但这些算法中的每一个都在某些情况下表现出色，但在其他情况下却失败了。目前，解决这个问题的专家对哪些算法将处理规划问题的某些实例有一个大致的了解，但让专家参与大规模部署是不可行的，例如，在自动驾驶汽车或无人机包裹递送中。在这个项目中，我们将采取数据驱动的方法来理解在什么条件下解决者会表现出色，在什么条件下他们会犯错。该项目的目标是找到新的方法将大问题分解为更小的子问题，这些子问题可以更容易地解决，并了解当前求解器阵列中存在的差距，以便未来的求解器可以开发来解决这些差距。在一个图中，为多个智能体寻找从起始点到指定目标点的无冲突路径的问题，称为标记多智能体路径寻找（MAPF）问题，是NP难问题。标记MAPF得到了很好的研究，有许多最优解算器可用;然而，它们无法扩展到一些现代多机器人系统中的机器人数量，例如自主仓库。这项研究不是开发新的MAPF求解器，而是使用现有的机器学习技术来利用现有标记的MAPF求解器的优势，产生新的技术和算法，这些技术和算法将允许扩展应用于大型机器人群，并解决现有求解器无法解决的问题。这一办法有三个方面。首先，该团队将利用MAPF求解器的优势，使用机器学习来训练算法选择器，以从求解器组合中预测特定实例的最快MAPF求解器。 其次，他们将开发将大型MAPF实例有效分解为较小子实例的方法，这些子实例可以使用我们的算法选择器选择的求解器并行求解，从而提高速度和规模。 最后，他们将开发用于估计MAPF实例的经验硬度的方法，即，每个求解器求解一个实例所需的时间。结果将使用MAPF求解器的既定指标进行评估，测量我们的算法解决的新实例的数量，并在数百个机器人的模拟中逐步展示它们。该项目将显着提高多机器人路径寻找的易处理性，并提供规模的问题的难度的理解。它将扩展对某些MAPF实例挑战性的有限理解;开发新的算法和技术来增强现有和未来的MAPF算法;并显着增加可以找到最佳无碰撞路径的机器人数量。它还将产生迄今为止最大的最佳MAPF求解器基准测试，并帮助其他MAPF研究人员了解现有MAPF求解器的优点和缺点。这项工作是机器人和组合优化的交叉点，将立即对这些社区产生影响。该研究成果将显著提高多机器人系统的规划性能，从而在机器人仓储、自动驾驶汽车、自动配送、准时制制造等诸多领域产生深远影响。该奖项体现了NSF的法定使命，通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。