AF: Small: RUI: Competitive Search, Evacuation and Reconfiguration with Coordinated Mobile Agents

In recent years, innovations in special-purpose sensor hardware and machine-learning algorithms have led to rapid advances in robotics and autonomous vehicle technology. This project aims to develop and analyze algorithms for an ensemble of mobile agents working in parallel to achieve coordinated, goal-directed motion in simple geometric spaces that are abstractions of complex terrains. The agents cooperate among themselves to efficiently search, explore, synchronize and reconfigure into patterns using distributed algorithms with limited memory, sensing and communication capabilities. The research will contribute to a deeper understanding of coordination protocols to complete navigational tasks, even when some of the agents may be faulty. Results from the research will provide critical insights that can be used in robot-assisted applications such as search-and-rescue in hostile or unknown terrains, or surface exploration needed to develop and maintain future colonies and human outposts on other planets. The study of reconfiguration problems will also provide ideas that can shed light on previously unexplained aspects of flocking phenomena in birds, such as murmurations. The project will involve undergraduate students in theoretical research and will train them to develop and maintain an open-source repository of distributed algorithms for robot coordination problems and their animations. In addition, results from the project will be archived as a permanent online resource for the parallel and distributed computing community at large. Two specific annual initiatives for outreach will be a part of the project: firstly, participation by the investigator and undergraduate research students in the Rutgers Future Scholars program, and secondly, conducting workshops for K-12 teachers to teach basic computational and algorithm design skills.

The project addresses fundamental theoretical problems of efficient, coordinated exploration and reconfiguration by a team of mobile agents as they work together to accomplish a computational task in simple geometric spaces. Three basic problem settings are considered: (a) the search problem, where an unknown target location, which can only be sensed when reached, has to be found by at least one robot in the team, (b) the evacuation problem, that requires some subset of the robots to reach an unknown exit location in the region after it has been found, and (c) the reconfiguration problem, where the robots must rearrange themselves in a certain desired configuration based on either a given arrangement or on local rules. Within each problem setting, the goal is to develop an algorithm for the robots so that they can attain the desired configuration or complete the task defined by the problem with the minimum amount of resource usage possible, e.g. total distance traveled or time taken. Many interesting variants of the problems will also be studied, such as the peculiarities of the region's geometry, constraints on the communication capabilities of the robots, and handling faulty robots that may be benign or malicious.

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.