Title: On the Dynamical Hierarchy in Gathering Protocols with Circulant Topologies
Abstract: In this talk we investigate the capabilities and limitations of local, distributed strategies for swarms of mobile robots. Such strategies consist of protocols run by the individual robots that 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 . This research direction is well-established in distributed computing which will be briefly introduced in this talk. Here, the speed of the protocols is typically analyzed in terms of runtime complexity, whereas the focus in this talks are ideas from dynamical systems such as stability properties of the prescribed formation. 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. 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.
As a guiding problem, we will consider the so--called gathering problem with fixed circulant topology. That is, the goal of the robots is to gather at a single, not predetermined point in the plane using only local information. In fact, in this model a robot only observes relative positions of its neighbors that are encoded in a circulant interaction graph. After introducing some basic preliminary definitions and ideas how to model such a protocol as a dynamical system, we will study its dynamical properties in terms of linear stability of the gathering point(s). As a result we will identify a hierarchy of configurations in state space with respect to convergence speed to the gathering point. In particular, for an even number of robots, we find a two-dimensional strongly stable subspace. Finally, we will look at some further aspect for ongoing and future research.
Zoom:
https://uni-paderborn-de.zoom.us/j/95086019116?pwd=amxJbUNDQ1pRNEU3NXRlTWhhRXV4Zz09
Meeting ID: 950 8601 9116
Passcode: 744421