Analysis and implementation of distributed algorithms for multi-robot systems
Analysis and implementation of distributed algorithms for multi-robot systems
复制标题
多机器人系统分布式算法分析与实现
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
James McLurkin
中科院分区：
文献类型：
--
作者：
James McLurkin
多机器人系统的分布式算法依赖于网络通信来共享信息。然而，机器人的运动改变了网络拓扑结构，这影响了呈现给算法的信息。为了使算法产生准确的输出，机器人需要足够快地通信，以保持网络拓扑与它们的物理配置相关。不频繁的通信将导致大多数多机器人分布式算法产生不太准确的结果，并导致一些算法完全停止工作。这项工作的中心主题是，算法的准确性，通信带宽和物理机器人的速度是相关的。
本论文有三个主要贡献：第一，我开发了一个原型多机器人应用和计算模型，提出了一套复杂性指标来评估分布式算法在多机器人系统的性能，并介绍了机器人速度比的想法，机器人速度相对于消息速度的无量纲措施，依赖于多跳通信的网络。机器人速度比捕捉通信带宽、移动性和算法精度之间的关键关系，并且可以在设计时用于在它们之间进行权衡。我用这个速度比来评估现有的分布式多跳通信和导航算法的性能。其次，我提出了一个定义的多机器人系统中的边界，并开发新的分布式算法来检测和表征它们。最后，我定义了动态任务分配问题，并提出了解决该问题的四种分布式算法，每种算法都代表了准确性、运行时间和通信资源之间的不同权衡。
在这项工作中提出的所有算法在理想条件下是可证明正确的，并产生可验证的现实世界的性能。它们具有自我稳定性，对通信故障、人口变化和其他错误具有鲁棒性。所有的算法都在112个机器人上进行了测试。（副本可从麻省理工学院图书馆，RM。14-0551，剑桥，MA 02139-4307。电话：617-253-5668;传真：617-253-1690。）
Distributed algorithms for multi-robot systems rely on network communications to share information. However, the motion of the robots changes the network topology, which affects the information presented to the algorithm. For an algorithm to produce accurate output, robots need to communicate rapidly enough to keep the network topology correlated to their physical configuration. Infrequent communications will cause most multi-robot distributed algorithms to produce less accurate results, and cause some algorithms to stop working altogether. The central theme of this work is that algorithm accuracy, communications bandwidth, and physical robot speed are related.
This thesis has three main contributions: First, I develop a prototypical multi-robot application and computational model, propose a set of complexity metrics to evaluate distributed algorithm performance on multi-robot systems, and introduce the idea of the robot speed ratio, a dimensionless measure of robot speed relative to message speed in networks that rely on multi-hop communication. The robot speed ratio captures key relationships between communications bandwidth, mobility, and algorithm accuracy, and can be used at design time to trade off between them. I use this speed ratio to evaluate the performance of existing distributed algorithms for multi-hop communication and navigation. Second, I present a definition of boundaries in multi-robot systems, and develop new distributed algorithms to detect and characterize them. Finally, I define the problem of dynamic task assignment, and present four distributed algorithms that solve this problem, each representing a different trade-off between accuracy, running time, and communication resources.
All the algorithms presented in this work are provably correct under ideal conditions and produce verifiable real-world performance. They are self-stabilizing and robust to communications failures, population changes, and other errors. All the algorithms were tested on a swarm of 112 robots. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)