DANCeRS : A D istributed A lgorithm for N egotiating C ons e nsus in R obot S warms with Gaussian Belief Propagation

Aalok Patwardhan, Andrew J. Davison · 2025

Read DANCeRS : A D istributed A lgorithm for N egotiating C ons e nsus in R obot S warms with Gaussian Belief Propagation by Aalok Patwardhan, Andrew J. Davison (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-18153.txt.

Introduction

Aalok Patwardhan and Andrew Davison present DANCeRS, a 2025 algorithm for agreement in robot swarms. A swarm must settle on shared behavior, from forming shapes to picking one option from many. Past methods treat continuous choices and discrete choices as separate problems. DANCeRS handles both with one tool: Gaussian belief propagation, in which robots pass probabilistic messages to nearby peers and update their beliefs.

The swarm is cast as a factor graph, a structure that keeps the method scalable and robust as conditions change. No central controller is needed. In one demo, robots plan paths and dodge each other to build a shape. In a second, the same frame settles a discrete group choice. Tests showed strong scaling and speed against recent rivals. The authors offer the method as a base for distributed consensus in multi robot systems.

Catalog record

CREATORAalok Patwardhan, Andrew J. Davison
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-18153

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

DANCeRS : A D istributed A lgorithm for N egotiating C ons e nsus in R obot S warms with Gaussian Belief Propagation Aalok Patwardhan, Andrew J. Davison Abstract Robot swarms require cohesive collective behaviour to address diverse challenges, including shape formation and decision-making. Existing approaches often treat consensus in discrete and continuous decision spaces as distinct problems. We present DANCeRS, a unified, distributed algorithm leveraging Gaussian Belief Propagation (GBP) to achieve consensus in both domains. By representing a swarm as a factor graph our method ensures scalability and robustness in dynamic environments, relying on purely peer-to-peer message passing. We demonstrate the effectiveness of our general framework through two applications where agents in a swarm must achieve consensus on global behaviour whilst relying on local communication. In the first, robots must perform path planning and collision avoidance to create shape formations. In the second, we show how the same framework can be used by a group of robots to form a consensus over a set of discrete decisions. Experimental results highlight our method’s scalability and efficiency compared to recent approaches to these problems making it a promising solution for multi-robot systems requiring distributed consensus. We encourage the reader to see the supplementary video demo. I INTRODUCTION In nature swarms such as bird murmurations or schools of fish consist of simple agents that communicate locally and exhibit collective behaviour, often requiring agreement on shared global parameters like velocity or orientation. Similarly, robot swarms must act cohesively, whether for task allocation, arrangement, or coordinated behaviours like exploration or aggregation [ 1 ] . This requires each robot to make individual decisions while aligning with the swarm’s global objectives. Centralised systems offer precise coordination by delegating all computations to a single external entity. However, such approaches lack scalability and are prone to single points of failure. In contrast, decentralised systems rely on distributed computation and local communication, enabling agents to share information and iteratively refine their decisions based on their neighbours’ states. For discrete decision spaces, agents often share probability distributions over the available choices and update their beliefs until consensus is reached [ 2 ] . These methods are effective for a swarm deciding between distinct behaviours like exploration [ 3 ] , aggregation, or task allocation, commonly framed as best-of-N problems [ 4 ] . Fig. 1 : (Top) Robots jointly plan paths to arrange into the ‘A’ shape, achieving consensus over its pose. (Bottom) Robots use the same algorithm to achieve consensus over a discrete set of decisions (colours) through local communication. For continuous spaces, consensus is typically achieved by iteratively updating shared variables, such as positions or orientations, based on differences between neighbouring agents’ states. This allows swarms to converge toward global parameters collaboratively, even with limited local communication. Such approaches have been used for shape formation [ 5 ] , where robots must agree on the position and orientation of a shape for coordinated motion. These distributed methods provide scalability and robustness, enabling swarms to function in dynamic environments without centralised control. Despite significant progress, the literature typically treats consensus over discrete decision spaces and continuous parameter spaces as separate problems. In this work, we propose a unified framework for achieving consensus in both domains. By modelling the swarm as a sparsely connected factor graph and using Gaussian Belief Propagation (GBP) for distributed inference, our method enables robots to reach consensus efficiently and scalably. This fully distributed approach ensures robustness to increasing swarm size and dynamic environments, addressing both discrete and continuous decision-making in a single cohesive framework. We demonstrate our general framework in two example applications of joint path planning for shape formation and collective decision-making over a set of discrete options. Our contributions are: • A unified, distributed framework for consensus in both discrete and continuous decision spaces. • The extension of GBP path planning for non-holonomic unicycle dynamics in shape formation. • A novel distributed shape formation method for discrete target assignment, demonstrated with scalability and efficiency in experiments. • The first application of GBP for discrete consensus in robot swarms. II RELATED WORK Achieving global behaviour in robot swarms relies on decision-making frameworks that balance scalability and robustness. While centralised methods are limited by scalability and single points of failure, decentralised approaches enable collective behaviour through local interactions, whilst addressing challenges such as conflict resolution. The literature focuses on two key problems: consensus over a set of discrete options and over continuous parameter spaces. In discrete consensus problems, each agent in the swarm must select one option from a finite set based on local communication with its neighbours. This problem, often referred to as the “best-of- N ” problem has been widely studied particularly for N\mathord{=}2 options where a swarm estimates the majority value in the environment [ 6 , 7 ] . For larger N , probabilistic approaches involve agents maintaining and sharing a probability distribution over the set of options. In [ 8 ] agents update their internal beliefs based on local communication and knowledge of the local consensus group (agents sharing the same decision) whereas in [ 2 ] agents share decision IDs and levels of certainty of their beliefs based on probabilistic entropy. Other popular distributed approaches include voter methods where robots use information from their neighbours and choose a random decision [ 9 ] , the majority decision [ 10 ] or the most frequent recently observed decision [ 11 ] . Another approach to distributed decision-making is opinion dynamics, which models how agents adjust their opinions through local interactions. Unlike traditional consensus models, it allows for complex social dynamics, including agreement, disagreement, and opinion clustering. The nonlinear model in [ 12 ] introduces tunable sensitivity, enabling flexible opinion transitions. While this provides insight into how opinions evolve in networks, such models do not always ensure that all agents reach the same decision, which is often desirable in multi-agent coordination tasks. Continuous consensus problems involve the swarm negotiating their beliefs about continuous global parameters, such as target locations in search-and-rescue or source-seeking tasks, or the position and orientation of a reference frame for shape formation. Distributed consensus algorithms typically rely on robots effectively averaging their neighbours’ beliefs for formation control [ 13 ] , obstacle avoidance [ 14 ] and saliency detection [ 15 ] . Recent work applied the mean-shift algorithm to shape formation tasks [ 5 ] , where robots negotiated on the pose of the shape, and were able to form and explore complex patterns defined as an artificial potential field. This work was extended in [ 16 ] to consider formations consisting of distinct points. These mean-shift approaches iteratively adjust robots’ velocities to align with local density maxima, enabling collision avoidance and dynamic role assignment, although they are designed for shapes with one continuous connected component. Other approaches, such as local task swapping, have been proposed for distributed shape formation [ 17 ] . In this method, robots iteratively negotiate position assignments by swapping roles, deciding whether to act as anchors or clients based on local priorities. A hop-count strategy propagates goal selection, ensuring collision-free movement in a discretised grid-world. However, this approach assumes robots have already reached consensus on a shared global reference frame.

Read the complete text