Overlapping Coalition Formation for Efficient Data Fusion in Multi-Sensor Networks

Viet Dung Dang, Rajdeep K. Dash, Alex Rogers, Nicholas R. JenningsAAAI 2006

Introduction

In multi-agent systems, Coalition Formation (CF) is the foundational process by which agents aggregate their capabilities to perform tasks more effectively than they could individually. Traditional CF research typically assumes that coalitions are disjoint, meaning an agent is restricted to a single group at any given time. However, in the context of wide-area surveillance and sensor networks, this assumption is often impractical.

Modern sensors, such as those used for intruder detection or environmental monitoring, are frequently capable of multi-tasking. A single sensor can track multiple targets simultaneously across different sectors of its field of view, naturally forming "overlapping coalitions." Furthermore, the value of adding sensors to a specific task is rarely linear. When multiple sensors provide correlated data, the resulting information gain is often less than the sum of individual contributions—a property known as sub-additivity. This paper introduces a framework and algorithms specifically designed to optimize coordination in these overlapping, sub-additive scenarios.

Overlapping sensor coalitions tracking multiple targets.

Methodology

The authors formalize the sensor coordination problem as a configuration of $n$ sensors tracking $m$ targets to maximize total system welfare, defined as the total information gain minus sensing costs. Information gain is modeled using Fisher Information, a statistical measure of the precision of observations regarding a target's position.

Two primary algorithmic solutions are proposed:

  1. Polynomial (Greedy) Algorithm: A fast, $O(n^2m)$ approach where sensors sequentially select their optimal state based on the prior choices of other agents. While its theoretical worst-case bound is $n$ times the optimal, empirical results suggest significantly higher performance.
  2. Optimal Branch-and-Bound Algorithm: To achieve exact optimality without exhaustive search, the authors developed a pruning procedure. By leveraging the sub-additivity property, the algorithm calculates mathematical upper bounds to identify and discard branches of the search tree that cannot contain the optimal solution.

The algorithms were validated using a generic simulation model where sensors and targets were randomly distributed. Configurations ranged from 4 to 20 agents, with each sensor having four distinct sensing states and randomized costs.

Key Results and Insights

The research demonstrates that sub-additivity, typically a hurdle in optimization, can be leveraged as a powerful tool for defining search bounds. A key heuristic introduced is the "weak state"—a sensor orientation that observes no targets. The authors prove that any state vector containing a weak state is non-optimal, allowing for the immediate removal of vast portions of the search space.

Empirically, the greedy algorithm performed remarkably well, maintaining a mean bound within 1% of the optimal solution across all tested configurations. For smaller networks (up to 8 agents), it identified the absolute optimal solution in over 80% of cases.

The branch-and-bound algorithm showed exceptional pruning efficiency. As the number of agents increased, the fraction of the search space required to prove optimality dropped exponentially. For a network of 20 agents, the algorithm successfully identified the optimal solution by searching only approximately $10^{-8}$ (one hundred-millionth) of the total possible states.

Pruning efficiency of the branch-and-bound algorithm across different network sizes.

Conclusion and Future Work

This work bridges the gap between theoretical agent coordination and the practical requirements of multi-tasking hardware. By allowing for overlapping coalitions and sub-additive values, the model provides a more realistic representation of sensor network dynamics.

Future research will focus on transitioning from static "snapshots" to dynamic environments where target movement requires real-time coalition updates. Additionally, the authors aim to develop distributed versions of these algorithms to handle scenarios with incomplete information and validate the framework against real-world sensor data to account for environmental noise.

Summary updated

BibTeX
@inproceedings{dang2006overlapping,
  author = {Viet Dung Dang and Rajdeep K. Dash and Alex Rogers and Nicholas R. Jennings},
  title = {{Overlapping Coalition Formation for Efficient Data Fusion in Multi-Sensor Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure