Distributed Progressive Formation Control with One-Way Communication for Multi-Agent Systems

摘要

The cooperation of multiple robots towards a common goal requires a certain spatial distribution, or formation configuration, of the agents in order to succeed. Centralized controllers that have information about the absolute or relative positions of all agents, or distributed approaches using communication to share system-wide information between agents, are able to calculate optimal individual paths. However, this reserves important computational resources as the number of agents in the system increases. We address the problem of distributed formation control with minimal communication and minimal computational power required. The algorithm introduced in this paper progressively generates a directed path graph to uniquely assign formation positions to all agents. The benefits of the proposed algorithm compared to previous include the need for one-way communication only, low computational complexity, ability to converge without any a priori assignments under certain geometric conditions and need for limited sensing information only. The algorithm can be deployed to computationally constrained devices, enabling its deployment in robots with simpler hardware architectures. The ability to converge and distributively assign positions, or roles, with only one-way communication makes this algorithm robust during deployment, at which time all agents are equivalent and anonymous. Moreover, we account for limited communication and sensing range, and agents only need to have information about other agents in their vicinity in order to make decisions. Communication is simple and allows for scalability without an impact on performance or convergence latency, with a linear dependence on the number of agents. Agents only need to broadcast their status to other neighboring agents and do not reply any message. Finally, this algorithm enables almost-arbitrary configurations. The main limitation for the choice of formation configuration is that all pairs of points forming an edge in the polygonal line defining the boundary of the convex hull must be within sensing range.