Algorithms for Swarm Robotics: 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 methods and 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.