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

职业生涯：突破多体运动规划中的最优效率障碍

• 批准号: 1845888
• 负责人: Jingjin Yu
• 金额: $ 55万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1845888&HistoricalAwards=false
• 关键词: CAREER; Breaking; Through; Optimality; Efficiency

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.

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

项目成果

Polynomial Time Near-Time-Optimal Multi-Robot Path Planning in Three Dimensions with Applications to Large-Scale UAV Coordination

三维多项式时间近时最优多机器人路径规划及其在大规模无人机协调中的应用

• DOI: 10.1109/iros47612.2022.9982231
• 发表时间: 2022
• 期刊: 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS
• 作者: Guo, Teng;Feng, Si Wei;Yu, Jingjin
• 通讯作者: Yu, Jingjin

Effective Heuristics for Multi-Robot Path Planning in Warehouse Environments

• DOI: 10.1109/mrs.2019.8901065
• 发表时间: 2019-08
• 期刊: 2019 International Symposium on Multi-Robot and Multi-Agent Systems (MRS)
• 作者: Shuai D. Han;Jingjin Yu

Effectively Rearranging Heterogeneous Objects on Cluttered Tabletops

有效地重新排列杂乱桌面上的异构对象

• DOI: 10.1109/iros55552.2023.10342164
• 发表时间: 2023
• 期刊: 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS
• 作者: Gao, Kai;Yu, Justin;Punjabi, Tanay Sandeep;Yu, Jingjin
• 通讯作者: Yu, Jingjin

Optimal and Stable Multi-Layer Object Rearrangement on a Tabletop

桌面上优化且稳定的多层对象重新排列

• DOI: 10.1109/iros55552.2023.10342446
• 发表时间: 2023
• 期刊: 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS
• 作者: Xu, Andy;Gao, Kai;Feng, Si Wei;Yu, Jingjin
• 通讯作者: Yu, Jingjin

Optimizing Space Utilization for More Effective Multi-Robot Path Planning

优化空间利用率以实现更有效的多机器人路径规划

• 发表时间: 2022
• 期刊: IEEE International Conference on Robotics and Automation
• 作者: Han, Shuai;Yu, Jingjin
• 通讯作者: Yu, Jingjin