CAREER: Breaking Through the Optimality-Efficiency Barrier in Multi-Body Motion Planning

多个运动物体(如移动机器人、自主车辆等)的有效运动协调是一个既具有基础研究意义又具有实际意义的计算问题。由于多体运动规划问题涉及计算大量物理物体的无碰撞轨迹，因此在保证良好的最优性的情况下，这是一个极具挑战性的问题。这个职业项目将开展多体运动规划的多推力研究，目标是通过基础理论、有效算法和原型硬件-软件系统的开发来推动该领域的尖端技术。从实践的角度来看，该项目带来的进步将有助于实现广泛的现实世界应用，包括材料处理(例如，仓库和航运港口的自主多机器人系统)、娱乐(例如，与空中车辆群的编排)、数字生物学(例如，微流控芯片)等等。在有限的2D/3D环境中，即使在相对简单的离散设置下，许多标记的物理体的最优运动协调也是已知的计算困难的。直到最近，用于标记多体运动规划的最佳多项式时间算法只保证相对于输入问题的大小是二次的时间最优性，这是高度次优的。这远远不是理想的，因为它表明，计算最佳或接近最佳的多体运动计划的算法可能需要超多项式的运行时间。这个职业项目旨在弥合这一长期存在的差距，这一差距导致多体运动规划中解决方案的最佳性和计算效率之间的分歧。也就是说，我们能否构造出既能计算高度最优解，又能在保证的低多项式时间内运行的算法？我们在过去几年的初步努力表明，这确实可以通过一种新颖的算法技术组合来实现，其中包括分而治之、规则二部完全匹配和网络流等。利用这些技术和我们对其全部潜力的洞察，该项目将开发出理论、方法和系统，以打破多体运动规划中的最佳效率障碍。这项研究将为机器人学和智能系统的研究带来基础性的进展，包括(1)对离散和连续的多体运动规划问题进行彻底的结构分析，导致对影响可实现的最优性下限的关键因素的深入了解；(2)开发最先进的、实用的算法解决方案，同时保证最优性和计算效率，从而突破可实现的最优性上限。同时，该项目的重大系统开发工作，包括将算法适配到受物理限制和不确定性约束的硬件，将有助于暴露和解决热衷于现实世界应用的问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The effective coordination of motions for many moving bodies (e.g., mobile robots, autonomous vehicles, and so on) poses a computational problem with both fundamental research importance and practical significance. Because the multi-body motion planning problem involves computing collision-free trajectories for a large number of physical bodies, it is a highly challenging to solve with good optimality guarantees. This CAREER project will carry out a multi-thrust study on multi-body motion planning with the goal to push the state-of-the-art in the area through the development of fundamental theories, effective algorithms, and prototype hardware-software systems. From a practical point of view, the advances brought forward by this project will help enable a wide range of real-world applications including material handling (e.g., autonomous multi-robot systems at warehouses and shipping ports), entertainment (e.g., choreography with aerial vehicle swarms), digital biology (e.g., microfluidics chips), to list a few. The optimal motion coordination of many labeled physical bodies in a bounded 2D/3D environment, even under the relatively simple discrete setting, is known to be computationally hard. Until very recently, the best polynomial-time algorithm for labeled multi-body motion planning only guarantees time optimality that is quadratic with respect to the size of input problem, which is highly sub-optimal. This is far from ideal because it suggests that algorithms that compute optimal or near-optimal multi-body motion plans could potentially require super-polynomial running time. This CAREER project intends to bridge this long-standing gap that divides solution optimality and computational efficiency in multi-body motion planning. That is, could we construct algorithms that not only compute highly optimal solutions but also run in guaranteed low polynomial time? Our initial efforts over the past few years indicate that this could indeed be possible through a novel composition of algorithmic techniques including divide-and-conquer, regular bipartite perfect matching, and network flow, among others. Exploiting these techniques and our insights to their full potential, the project will develop theories, methods, and systems that will shatter the optimality-efficiency barrier in multi-body motion planning. The proposed research could bring foundational advances to robotics and intelligent systems research, including (1) a thorough structural analysis of discrete and continuous multi-body motion planning problems, leading to a solid understanding of key factors that affect the achievable optimality lower bounds, and (2) the development of state-of-the-art, practical algorithmic solutions with simultaneous optimality and computational efficiency guarantees, pushing the limits on the achievable optimality upper bounds. At the same time, the significant system development effort of the project, which involves the adaptation of algorithms to hardware subject to physical constraints and uncertainty, will help expose and resolve issues keen to real-world applications.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.