A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems

Kathryn Sarah Macarthur, Ruben Stranders, Sarvapali D. Ramchurn, Nicholas R. JenningsAAAI 2011 · DOI

Introduction

In complex multi-agent systems (MAS), such as robotic search-and-rescue or distributed sensor networks, the efficient allocation of tasks to agents is a critical challenge. These environments are often characterized by high dynamism—where agents and tasks appear or disappear unexpectedly—and require decentralized coordination to avoid single points of failure. Furthermore, many real-world tasks exhibit synergies, where the utility of a coalition of agents is greater than the sum of their individual contributions.

This paper presents BnB FMS (Branch-and-Bound Fast-Max-Sum), a decentralized algorithm designed to address these challenges. By integrating online domain pruning with branch-and-bound search techniques, BnB FMS significantly reduces computational and communication overhead while maintaining high solution quality.

The BnB FMS Framework

The authors build upon the Fast-Max-Sum (FMS) algorithm, which operates on factor graphs to represent dependencies between agents and tasks. BnB FMS introduces two primary optimization layers to break the computational bottleneck inherent in standard message-passing approaches:

1. Online Domain Pruning (ODP)

ODP allows agents to locally identify and discard "dominated" tasks—those that cannot possibly be part of an optimal solution given the current bounds on utility. Unlike static pruning methods, ODP is designed for dynamic environments, allowing agents to update their pruned task sets incrementally as the system state changes. This prevents the need for full re-computations when minor environmental shifts occur.

Within the factor graph, function nodes (representing tasks) must evaluate combinations of agent assignments. Standard FMS faces an exponential computational bottleneck here, as it must check $2^n$ combinations. BnB FMS replaces exhaustive evaluation with a search tree approach. By estimating the maximum potential utility of various branches, the algorithm can prune large sections of the search space that are guaranteed to be sub-optimal.

Experimental Evaluation

The algorithm was tested using synthetic benchmarks simulating environments with up to 500 tasks and 250 agents. The researchers explored various network topologies, including random, tree, and scale-free graphs, to assess performance across different connectivity patterns. Dynamic scenarios were modeled using a Poisson distribution to simulate the arrival and departure of agents and tasks.

Performance metrics of BnB FMS compared to baselines across varying task counts.

As shown in Figure 3, BnB FMS consistently outperforms existing methods. In terms of utility (a), it achieves significantly higher scores than decentralized stochastic algorithms like DSA and OPGA, which often converge to local optima. In terms of wall time (b), BnB FMS demonstrates superior scalability compared to standard FMS, completing computations up to 31% faster as the number of tasks increases. Notably, while exact solvers like SDPOP ran out of memory at just 50 tasks, BnB FMS scaled comfortably to the maximum test size of 500 tasks.

Communication Efficiency

A key advantage of BnB FMS is its reduction in communication overhead. In distributed systems, the cost of sending messages often outweighs local computation. By pruning the search space and agent domains, the algorithm drastically reduces the volume of data exchanged.

Communication overhead of BnB FMS and BnB MS relative to standard FMS.

Figure 5 illustrates that BnB FMS requires approximately 30% fewer messages than the standard FMS algorithm. It also outperforms BnB MS, a non-dynamic variant, highlighting the effectiveness of the online domain pruning strategy in maintaining efficiency during environmental changes.

Conclusion and Future Work

BnB FMS represents a significant step forward in decentralized task allocation. By combining the reliability of exact solvers with the speed of pruning heuristics, it enables MAS to scale to hundreds of entities in real-time. While the algorithm currently shows empirical success on cyclic graphs, future research will focus on providing theoretical "anytime" bounds to guarantee solution quality even when the algorithm is interrupted. Additionally, balancing the computational load across heterogeneous agents remains an open area for optimization.

Summary updated

BibTeX
@inproceedings{macarthur2011distributed,
  author = {Kathryn Sarah Macarthur and Ruben Stranders and Sarvapali D. Ramchurn and Nicholas R. Jennings},
  title = {{A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.1609/aaai.v25i1.7866},
}
Figure