Congratulations to Jingjin Yu for having the project titled
"CAREER: Breaking Through the Optimality-Efficiency Barrier in Multi-Body Motion Planning"
recommended for funding (budget: $549,500) by the National Science Foundation (NSF). The CAREER Program is an NSF-wide activity that offers the National Science Foundation's most prestigious awards in support of early-career faculty, who have the potential to serve as academic role models in research and education and to lead advances in the mission of their department or organization.
Project overview:
The effective motion coordination of many labeled physical bodies in a bounded 2D/3D environment poses a computational problem of both practical and fundamental research interests. From the practical point of view, multi-body motion planning algorithms 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), and digital biology (e.g., microfluidic chips), to list a few. On the other hand, from the theoretical point of view, even under the relatively simple discrete setting, 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 preliminary 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 fundamental theories, effective algorithms, and hardware-software systems that will shatter the optimality-efficiency barrier in multi-body motion planning.
Department of Computer Science