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

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

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.