Computational Efficiency and Efficacy in the Autonomous, Cooperative Multi-Agent Complete Coverage Problem
Open Access
- Author:
- Luff, Jacqueline Marie
- Area of Honors:
- Electrical Engineering
- Degree:
- Bachelor of Science
- Document Type:
- Thesis
- Thesis Supervisors:
- Shashi Phoha, Thesis Supervisor
Shashi Phoha, Thesis Supervisor
Dr. Sven G Bilén, Thesis Honors Advisor - Keywords:
- autonomy
multi-agent
complete coverage - Abstract:
- Current mine countermeasure (MCM) missions utilize unmanned underwater vehicles (UUVs) for the detection, classification, and neutralization of mines. More generally, autonomous agents are used for the surveillance of a field. Multiple UUVs or agents gather data through sonar sensors and compile it into numerous, asynchronous data streams. Anomalies with specific characteristics in these data streams represent the detection of a mine and are classified and stored in memory as such. This feature extraction has been presented in a data-processing algorithm deriving from symbolic dynamics and automata theory. Once information has been extracted and stored from sensor readings, each agent must intelligently navigate to collect more data and effectively categorize it. A navigational system must be completely autonomous, be adaptive to learning in an unknown environment, and optimized its efficiency while still guaranteeing close to complete surveillance of the assigned search region. Physical limitations, especially in underwater missions, prove to be difficult as computation and communication are limited. This work addresses all of these problems: it efficiently and effectively guarantees coverage of an entire search area. First, each agent is equipped with a computationally-lightweight navigational tool that ensures the total coverage of the assigned search region. The group of agents interacts, sharing limited information and exploiting relative preferences on where they wish to navigate. Cooperative decisions are made by judging the relative worth of a divide-and-conquer strategy or a joint scan of the same region. Thus, missions can be accomplished in less total time than if individual agents worked independently. This work creates two autonomous, navigational systems, one for a single agent and one for multiple agents. Each has a lightweight algorithm to determine how to navigate, using a novel energy function to determine the relative worth of moving to a specific position. The multi-agent system also has an algorithm to communicate between agents using a probability vector that is simplistic but yields valuable information. It also has an algorithm for cooperation that utilizes game theory as the agents interact. This endeavor demonstrates the valid and successful continuation of a statistical mechanics approach and is modeled after MCM missions that utilize UUVs but it is completely generalizable to any problem that requires surveillance and search with autonomous agents.