James McLurkin, Measuring the Accuracy of Computation on a Complex System (Why Multi-Robot Systems Shouldn't Move Faster than They Can Talk)

Computation on complex systems has two key components: the processing that occurs on individual agents, and the interactions between agents. The performance of the system as a whole is affected by the computational resource constraints of either component. On a multi-robot system, agents interact by sending messages between nearby robots, and by relaying messages throughout the group via ad-hoc networks. 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. In the worst case, a robot moving away from a message source faster than the message speed will never receive new information, and cannot execute any distributed algorithm properly. 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 made 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. Our experiments show that accuracy degrades as speed increases or communication bandwidth decreases. 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.