Optimum k-Nearest Neighbors for Heading Synchronization on a Swarm of UAVs under a Time-Evolving Communication Network

Abstract

Heading synchronization is fundamental in flocking behaviors. If a swarm of unmanned aerial vehicles (UAVs) can exhibit this behavior, the group can establish a common navigation route. Inspired by flocks in nature, the k-nearest neighbors algorithm modifies the behavior of a group member based on the k closest teammates. This algorithm produces a time-evolving communication network, due to the continuous displacement of the drones. Nevertheless, this is a computationally expensive algorithm, especially for large groups. This paper contains a statistical analysis to determine an optimal neighborhood size for a swarm of up to 100 UAVs, that seeks heading synchronization using a simple P-like control algorithm, in order to reduce the calculations on every UAV, this is especially important if it is intended to be implemented in drones with limited capabilities, as in swarm robotics. Based on the literature of bird flocks, that establishes that the neighborhood of every bird is fixed around seven teammates, two approaches are treated in this work: (i) the analysis of the optimum percentage of neighbors from a 100-UAV swarm, that is necessary to achieve heading synchronization, and (ii) the analysis to determine if the problem is solved in swarms of different sizes, up to 100 UAVs, while maintaining seven nearest neighbors among the members of the group. Simulation results and a statistical analysis, support the idea that the simple control algorithm behaves like a flock of starlings.

Keywords

• k-nearest neighbors
• time varying network
• heading synchronization
• flocking