Expediting Solutions to Hard Multi-Robot Path Finding Instances

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

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.