Robotics is widely perceived today as a key component to flexibility and competitiveness in large-scale manufacturing, to enhanced industrial efficiency and safety, and to more precise and effective agriculture, to name just a few reasons why governments, industry, and academia promote robotics. Fleets of robots are being rapidly adopted in logistics, and are expected to become commonplace in other domains such as agriculture, inspection and guarding, and last-mile delivery. Notwithstanding the proliferation of multi-robot systems, the state-of-the-art in efficient motion-planning for teams of robots is rather limited, and is even more limited when one aims to optimize the motion plans. Even modest contributions to optimal multi-robot motion planning can have a tremendous impact in terms of saving energy, reducing costs, improving response in critical situations, increasing productivity and competitiveness. The goal of this project, jointly funded by NSF and US-Israel Binational Science Foundation, is to develop algorithmic foundations for optimal multi-robot motion-planning in a planar continuous domain. The interdisciplinary nature of this project is likely to appeal to a broad set of both graduate and undergraduate students with diverse backgrounds. The material generated from this project will be disseminated through multiple courses, organizing workshops, and developing course materials, surveys, tutorials, and publicly available open-source software.
This project advances our understanding of the computational complexity of various multi-robot motion-planning problems by investigating three different classes of problems. First, it investigates optimal motion planning under a simple objective function such as the total length of paths traveled by all robots. Next, it studies optimal motion planning under a more complex objective function that aims to optimize multiple criteria such as the total length of paths and the clearance of the robots. In addition to these so-called "one-shot problems", the project also considers scenarios where a perpetual sequence of motion-planning requests need to be fulfilled, namely new requests appear while the robots in the fleet are already in motion, fulfilling other motion-planning requests. A major thrust of the project is on developing fast, simple, robust approximation algorithms for optimal motion planning. The project combines techniques from discrete and computational geometry, robotics, approximation algorithms, probabilistic techniques, and calculus of variation to investigate optimal motion planning for multi-robot systems. The project goes beyond the traditional worst-case-analysis to understand under what circumstances optimal motion-planning problems are computationally tractable. It will also explore dimension-reduction techniques to circumvent the curse of dimensionality, which arises in the standard analysis of multi-robot systems.
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.
