In-Network Leader Selection for Acyclic Graphs
This work addresses the practical need for decentralized leader selection in multi-agent systems, but the solution is limited to acyclic graphs, making it incremental.
The paper introduces the in-network leader selection problem for multi-agent systems, where agents must collaboratively select a leader minimizing trajectory deviation variance using only neighbor communication. For acyclic graphs, they develop a self-stabilizing algorithm by connecting the problem to facility location.
We study the problem of leader selection in leader-follower multi-agent systems that are subject to stochastic disturbances. This problem arises in applications such as vehicle formation control, distributed clock synchronization, and distributed localization in sensor networks. We pose a new leader selection problem called the in-network leader selection problem. Initially, an arbitrary node is selected to be a leader, and in all consequent steps the network must have exactly one leader. The agents must collaborate to find the leader that minimizes the variance of the deviation from the desired trajectory, and they must do so within the network using only communication between neighbors. To develop a solution for this problem, we first show a connection between the leader selection problem and a class of discrete facility location problems. We then leverage a previously proposed self-stabilizing facility location algorithm to develop a self-stabilizing in-network leader selection algorithm for acyclic graphs.