We tackle the problem of achieving any given shape defined as a point cloud in a distributed manner with a swarm of robots. The contributions of this paper are (i) An algorithm that transforms a point cloud into a acyclic directed graph; (ii) A motion control law that, from the acyclic directed graph, allows a swarm of robots to achieve the target shape in a decentralized manner; and (iii) A theoretical model, which provides sufficient conditions on the convergence of the control law. The key idea of our approach is to achieve the target shape progressively by inducing an ordering among the robots. More precisely, we construct an acyclic directed graph so that any free robot (i.e., not part of the shape) finds its location with respect to the already placed robots. We prove that, for a 2D shape, it is sufficient for a free robot to calculate its location with respect to two already placed robots to achieve this objective. We validate our method through accurate physics-based simulations of non-holonomic robots.
展开▼