Pipelined Consensus for Global State Estimation in Multi-Agent Systems

This paper presents pipelined consensus, an extension of pair-wise gossip-based consensus, for multi-agent systems using mesh net-works. Each agent starts a new consensus in each round of gossip-ing, and stores the intermediate results for the previous k consensus in a pipeline message. After k rounds of gossiping, the results of the first consensus are ready. The pipeline keeps each consensus independent, so any errors only persist for k rounds. This makes pipelined consensus robust to many real-world problems that other algorithms cannot handle, including message loss, changes in net-work topology, sensor variance, and changes in agent population. The algorithm is fully distributed and self-stabilizing, and uses a communication message of fixed size. We demonstrate the effi-ciency of pipelined consensus in two scenarios: computing mean sensor values in a distributed sensor network, and computing a cen-troid estimate in a multi-robot system. We provide extensive sim-ulation results, and real-world experiments with up to 24 agents. The algorithm produces accurate results, and handles all of the dis-turbances mentioned above.