We present an algorithm for stabilizing a hexagonal lattice formation of autonomous robotic agents. The algorithm is decentralized and each agent only needs to detect the relative positions of its neighbors. By partitioning the plane into Voronoi regions we can guarantee collision safety, even when the algorithm is used to produce waypoints for a non-holonomic agent to follow. In each iteration every agent moves to the centroid of the vertices of its Voronoi region, which yields formation cohesion. We define asymptotic formation stability that is independent of rotation or translation of the whole formation and prove local asymptotic stability. Finally we present simulations that confirm the stability analysis and illustrate the use of the algorithm with car-like robots.
QC 20120229