Stabilizing flocking via leader election in robot networks

Flocking is the ability of a group of robots to follow a leader or head whenever it moves in the plane (two dimensional Cartesian space). In this paper we propose and prove correct an architecture for a self-organizing and stabilizing flocking system. Contrary to the existing work on this topic our flocking architecture do not relies on the existence of a specific leader a priori known to every node in the network. In our approach robots are uniform, start in a arbitrary configuration and the head of the group is democratically elected via algorithmic tools. Our architecture includes three modules: a leader election module, a preprocessing module and a motion module. The leader election module returns to each robot its status : leader or follower. The preprocessing module aims to arrange robots in a moving formation. The motion module provides the rules that will make robots change their positions whenever the leader moves. Every modification of robots position will be done maintaining alive the moving formation. For each of these modules we propose deterministic or probabilistic algorithms (in the case when a deterministic solution is impossible). Moreover, we prove their correctness and compute their complexity. Our contribution is three fold. We propose novel deterministic and probabilistic solutions for leader election when robots evoluate in an asynchronous environment. We also prove the impossibility of deterministic leader election when robots have no common coordinates and start in an arbitrary configuration. Secondly, we propose a collision free deterministic algorithm for circles formation designed for asynchronous networks. Thirdly, we propose a deterministic flocking algorithm totally independent of the existence of a priori known leader. The proposed algorithm also works in asynchronous networks and does not assume common coordinates