A Decentralised Coordination Algorithm for Mobile Sensors

Ruben Stranders, Francesco Maria Delle Fave, Alex Rogers, Nicholas R. JenningsAAAI 2010 · DOI

Abstract

Coordinating teams of autonomous mobile sensors for real-time information gathering is a complex task, particularly in irregular or "wild" environments. This paper proposes a decentralized coordination framework that leverages the max-sum message-passing algorithm combined with a novel adaptive clustering technique for path selection. By grouping reachable locations into clusters and negotiating over high-value points, the system adapts to the environment's actual geometry. Experimental results in pursuit-evasion and patrolling scenarios show that this approach, dubbed MS K-M, significantly outperforms traditional greedy and fixed-path methods, offering up to a 52% performance improvement in irregular environments.

Introduction

The deployment of autonomous mobile sensors, such as UAVs or ground robots, in disaster zones or surveillance missions requires sophisticated coordination. Centralized control systems represent a single point of failure, while purely greedy decentralized approaches often lead to redundant coverage or significant gaps. Existing decentralized solutions are frequently limited by their reliance on fixed movement directions (e.g., compass points), which fail to account for the physical constraints of irregular environments like office buildings or urban ruins.

Methods: Max-Sum and Adaptive Clustering

The proposed framework is built upon the Max-Sum algorithm, a decentralized coordination technique where sensors and utility functions exchange messages on a factor graph to maximize collective information value.

The core innovation is the introduction of Adaptive Clustering for path selection. Instead of choosing from a fixed set of directions, a sensor analyzes its neighborhood—all locations reachable within $m$ steps. It then uses k-means clustering to group these locations into $c$ distinct clusters and identifies the most valuable point within each. The sensor then negotiates with its neighbors over paths leading to these specific high-value targets. This allows the coordination logic to adapt dynamically to the map's geometry rather than being constrained by a rigid grid.

Experimental Evaluation

The algorithm was evaluated in two simulated environments: an irregular "Office" environment based on a real laboratory and a structured "Lattice" grid. The sensors were tasked with Pursuit-Evasion (capturing a moving target) and Patrolling (minimizing loss from unpredictable intrusions).

Snapshots of the "Office" environment simulation at t=1, 6, and 13, showing sensor paths and coordination.

Key Results and Insights

The proposed MS K-M (Max-Sum with K-Means) algorithm demonstrated superior performance and consistency across all tests:

  • Irregular Environment Dominance: In the "Office" environment, MS K-M outperformed standard greedy algorithms by 30% in pursuit-evasion and 44% in patrolling.
  • Adaptive Advantage: The use of adaptive clustering provided a 42% performance boost over previous state-of-the-art methods that relied on fixed compass directions in non-lattice graphs.
  • Robustness and Consistency: As shown in the performance distributions, MS K-M not only achieved better average results but also exhibited lower variance compared to benchmark methods like the Traveling Salesman Problem (TSP) fixed-path strategy or random movement.
Performance comparison of the proposed MS K-M algorithm against benchmarks in Pursuit-Evasion (Capture Time) and Patrolling (Loss) scenarios.

Conclusion

By integrating decentralized message-passing with geometry-aware path selection, this framework provides a robust solution for mobile sensor coordination. Future work will address communication constraints in shielded environments and aim to provide mathematical guarantees on the optimality gaps of the max-sum approximations.

Summary updated

BibTeX
@inproceedings{stranders2010decentralised,
  author = {Ruben Stranders and Francesco Maria Delle Fave and Alex Rogers and Nicholas R. Jennings},
  title = {{A Decentralised Coordination Algorithm for Mobile Sensors}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7608},
}
Figure