Algorithms for swarms: Distributed Computing meets Dynamical Systems

The goal of this project is to investigate the capabilities and limitations of local, distributed strategies for swarms of mobile robots. Such strategies consist of protocols run by the individual robots. They are supposed to guide the movements of the robots in such a way that globally a prescribed formation like gathering, forming a line or other shapes is reached from an arbitrary initial configuration of the robots. This research direction is well-established in distributed computing. Our approach is to combine techniques from distributed computing and dynamical systems research in order to enhance the understanding of protocols for such formation tasks. To this end, we analyze the speed of the protocols in terms of runtime complexity in the distributed computing sense as well as stability properties of the prescribed formation with the use of ideas from dynamical systems. While in the distributed computing community often only a worst-case analysis is considered, the tools of dynamical systems allow a more fine-grained analysis of the input configurations by exploring the state space. More concretely, the state space foliation describes the long-term dynamical behavior of input configurations in more detail, i.e. it allows to identify classes of configurations that converge comparably fast or slow and even classes that fail to converge to the prescribed formation. Thus, the combination of both views leads to a more profound understanding of distributed strategies for swarms of mobile robots.

Persons

• Prof. Dr. Michael Dellnitz
• Prof. Dr. Friedhelm Meyer auf der Heide
• Dr. Raphael Gerlach
• MSc Jannik Castenow
• MSc Jonas Harbig
• Myself

Organisations

• Chair of Applied Mathematics at Paderborn University
• Chair of Algorithms and Complexity at Paderborn University

Time

The project kicked off in 2022.

Funding

This work is funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project number 453112019.