Collaborative Research: A Comprehensive Dynamic Search Framework for Asynchronous Multi-Objective Multi-Agent Planning

Natural disasters are causing significant economic and human losses more than ever. The increase in frequency and intensity of these wide-scale disasters places additional strains on rescue workers in their heroic struggle to save lives and mitigate the impacts on health and the economy. As such, rescue workers must make critical decisions at high tempo.

In these scenarios, information is key, and obtaining such information, as quickly as possible, saves lives. Therefore, this project develops search methods that can direct multiple heterogeneous agents to efficiently search and acquire information. This multi-agent planning is not just a problem in Humanitarian Assistance Disaster Relief (HADR) missions, but also in customized manufacturing, critical infrastructure management, pandemic response, automated construction of field hospitals, and post-disaster forensics.

Since lives are on the line, the approaches used must not only find feasible paths that maximize the likelihood of finding life, but also finds “best” possible solutions within a given response time. Therefore, this project seeks to create a comprehensive framework to address a wide family of multi-agent multi-objective planning problems operating under several logistic constraints.

The intellectual merit of this project investigates how to couple, partially decouple, or completely decouple the coordinated planning of the agent's trajectories, and therefore defer planning until absolutely needed. As such, the work develops formal guarantees, either in terms of completeness and optimality properties, or approximation bounds, for the sub-optimal solutions obtained for various generalizations of the multi-agent problem.

The performance of the approaches will be corroborated through large-scale simulations, and experiments on real robots. As part of the experimental process, this project will also define relevant metrics against which the new methods will be measured. This project will aim to substantiate that deferred planning, until necessary, offers computational, as well as path quality, and efficacy, benefits for several important generalizations of multi-agent path finding

problems.

This project is supported by the cross-directorate Foundational Research in Robotics program, jointly managed and funded by the Directorates for Engineering (ENG) and Computer and Information Science and Engineering (CISE).

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.