Taming Heterogeneity and Complexity of Embedded Control

A Formation Control Algorithm using Voronoi Regions

 

Magnus Lindhé —Karl Henrik Johansson

Automatic Control Lab KTH, Electrical Engineering SE-100 44 Stockholm Suède {lindhe | kallej}@ee.kth.se

ABSTRACT. 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.

KEYWORDS: Cooperative control, Multi-agent systems, Decentralized control, Voronoi, Flocking, Formation control

1. Introduction

Recent advances in fields such as microcontrollers, integrated radio circuits, adhoc networking protocols and sensors have made it feasible to manufacture small and cheap robots with many of the capabilities needed for autonomous operation. By using groups of such simple robots to perform tasks, several advantages can be gained. Robustness against vehicle failure is increased, the ...