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

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

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.