De-RANSAC: Robust Consensus for Robot Formations

Abstract — This paper studies the problem of distributed consensus in the presence of spurious sensor information. We propose a new method, De-RANSAC, which allows a multi-agent system to detect outliers—erroneous measurements or incorrect hypotheses—when the sensed information is gathered in a distributed way. The method is an extension of the RANSAC (RANdom SAmple Consensus) algorithm, which leads to a consensus result on the goodness of a set of measurements with certain probability. In order to execute the full process in a decentralized way, we propose a distributed voting policy valid for fixed and switching topologies. The algorithm is used to align a set of mobile robots to a configuration that requires small motions for most robots. Index Terms- Robust consensus, distributed algorithms, sensor networks