Embracing uncertainty: Consensus building in a multi-agent swarm
Multi-agent swarms offer the potential to search across large areas quickly, such as to locate multiple survivors for rescue. Issues that hamper performance can be overcome by allowing individual agents to:
- hold maps showing the presence, absence, and uncertainty regarding a survivor’s location;
- communicate with each other to share information.
This causes the agents’ maps to converge on the true situation. Even faster consensus can be reached by reducing the number of agent interactions and designing appropriate communication network topologies.
Project team: Michael Crosscombe, Jonathan Lawry , David Harvey, and Angus Johnson
The eye of the swarm
Rescuing incident survivors requires rapid and reliable identification of their location. Multi-agent swarms of unmanned aerial vehicles (UAVs) are, in principle, ideal for this task as they can survey large areas quickly and share their observations to create an overarching map of potential survivor location.
Real-world operations present challenges to communications and accurate observations though and misreporting a survivor’s location can have serious consequences.
Beyond black and white
Our research has found that embracing the uncertainties of real-world operations allows their effects to be handled much more effectively.
We simulated search activities of multi-agent swarms in which each agent holds its own map of survivor location, and updates this based on its own observations and communication with other agents.
These maps don’t just indicate the presence or absence of a survivor but also the uncertainty of a survivor being present. This uses the degree of belief (i.e., the maximum probability) of a survivor’s presence. In other words, the maps represent each agent’s belief of where survivors might be.
New information modified previous beliefs but didn’t override them completely. Interacting agents that initially held strong but opposite beliefs about a location both became uncertain about the presence of a survivor. Also, agent observations of their location were not made automatically but assigned a probability of success to reflect real-world challenges.
Achieving consensus
Agents sharing their beliefs with each other results all agent maps tending towards the true situation.
This approach is reliable and robust even with a high degree of noise and failed observations.
This consensus was achieved more quickly and still robust to noise if we simplified the possibility of a survivor being present in any location to one of three values: yes (survivor present), no (survivor absent), or don’t know.
Reduced communications and network topology
We investigated the effect of reduced levels of connectivity through removal of connections between random pairs of agents and through designed network topologies.
Remarkably, reduced levels of connectivity often increased the speed with which multi-agent swarms would reach a true consensus of survivor location.
The best performance was obtained by organising agents into small groups with a high degree of agent connectivity within them but limited connections between groups.
This counterintuitive result shows that improved outcomes can result despite having reduced technical requirements.
Multi-agent search operations
This realistic approach to developing reliable multi-agent protocols in search operations can be deployed with current technology. Indeed, allowing agents to develop a consensus through interactions appears to be a highly practical way of achieving rapid results to multi-agent swarm search operations.