Measuring the Accuracy of Distributed Algorithms on Multi-Robot Systems

Measuring the Accuracy of Distributed Algorithms on Multi-Robot Systems

James McLurkin (UW CSE postdoc, MIT) 
October 9, 2008, 3:30 pm
EE-105

Abstract
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. We show that trade-offs between these key quantities can be balanced at design time. Finally, we present results from experiments with 50 robots that characterize the accuracy of preexisting distributed algorithms for network communication, navigation, boundary detection, and dynamic task assignment. In all cases, accuracy degrades as speed increases or communication bandwidth is reduced. In our experiments, a RSR of 0.005 allows good accuracy in all algorithms, a RSR of 0.02 allows reasonable accuracy in simple algorithms, and all algorithms tested are essentially useless at a RSR of 0.10 or higher.

[link]