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.