Analyzing Symmetries of Swarms of Mobile Robots Using Equivariant Dynamics

Abstract

A commonly investigated problem in distributed computing is the general pattern formation (GPF) problem: A swarm of simple autonomous, disoriented robots must form a predefined planar pattern. This task is to be solved by the robots autonomously, i. e., without being controlled externally but instead by performing individual computations based on the observation of the other robots’ positions. The strategy that each robot pursues is called a (distributed) protocol. It is well-known, that the distributed nature of the model induces limitations on the patterns that can be formed. In particular, if the initial configuration of the robots has a certain (rotational) symmetry the reachable target patterns necessarily have this symmetry as well. The only known algorithm to form large patterns with limited perception range and without memory requires the robots to first move closely together, referred to as near-gathering. Common protocols that solve this (partial) task, however, increase the symmetries of the robot swarm which in turn reduces the number of target patterns that can be realized eventually. Here, we demonstrate how the collective dynamics of a robot swarm can be modelled conveniently in the language of dynamical systems. These mathematical models naturally come with certain equivariance (i. e., symmetry) properties which can be exploited to study the effect of an algorithm on the symmetries of the swarm. We derive a condition on a general protocol under which the increase of symmetries is impossible. Then, we introduce two example protocols which satisfy this condition. Both induce non-trivial collective dynamics and at least partly solve the near-gathering problem without increasing symmetries of the swarm.

Sören von der Gracht

PostDoc in Dynamical Systems

Research in network dynamical systems and its applications.