Measuring the Accuracy of Distributed Algorithms on Multi-Robot Systems with Dynamic Network Topologies

Distributed algorithms running on multi-robot systems rely on ad-hoc networks to relay messages throughout the group. The propagation speed of these messages is large, but not infinite, and problems in algorithm execution can arise when the robot speed is a large fraction of the message propagation speed. This implies a robot “speed limit”, as any robot moving away from a message source faster than the message speed will never receive new information, and no algorithm can function properly on it. In this work, we focus on measuring the accuracy of multi-robot distributed algorithms. We define the Robot Speed Ratio (RSR) as the ratio of robot speed to message speed. We express it in a form that is platform-independent and captures the relationship between communications usage, robot mobility, and algorithm accuracy, allowing for trade-offs between these quantities at design time. Finally, we present results from experiments with 30 robots that characterize the accuracy of preexisting distributed algorithms. In all cases, accuracy degrades as the RSR increases.

Author: 
McLurkin J
Publication: 
9th International Symposium on Distributed Autonomous Robotic Systems
Year: 
2008