Algorithms for Swarm Robotics: Distributed Computing meets Dynamical Systems

群体机器人算法：分布式计算与动态系统的结合

• 批准号: 453112019
• 负责人: Professor Dr. Michael Dellnitz
• 金额: --
• 依托单位: Fachgebiet Algorithmen und Komplexität
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/453112019?language=en
• 关键词: Algorithms; Swarm; Robotics; Distributed; Computing

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.

这个项目的目标是调查的能力和局限性的本地，分布式策略成群的移动的机器人。 这些策略由各个机器人运行的协议组成。 它们应该以这样的方式引导机器人的运动，即从机器人的任意初始配置达到全局规定的形成，如聚集，形成线或其他形状。 这一研究方向在分布式计算中得到了广泛的应用。 我们的方法是结合联合收割机的方法和技术，从分布式计算和动力系统的研究，以提高这种形成任务的协议的理解。为此，我们分析的速度的协议在分布式计算的意义上的运行时复杂性，以及使用的想法从动力系统的规定形成的稳定性。 虽然在分布式计算社区中通常只考虑最坏情况的分析，但动态系统的工具允许通过探索状态空间对输入配置进行更细粒度的分析。更具体地说，状态空间叶理更详细地描述了输入配置的长期动态行为，即，它允许识别收敛速度过快或过慢的配置类别，甚至是未能收敛到规定形态的类别。 因此，这两种观点的结合导致了更深刻的理解分布式策略成群的移动的机器人。