Scalability and schedulability in large, coordinated, distributed robot systems

Multiple, independent robot platforms promise significant advantage with respect to robustness and flexibility. However, coordination between otherwise independent robots requires the exchange of information; either implicitly (as in gestural communication), or explicitly (as in message passing in a communication network.) In either case, control processes resident on all coordinated peers must participate in the collective behavior. This paper evaluates the potential to scale such a coupled control framework to many participating individuals, where scalability is evaluated in terms of the schedulability of coupled, distributed control processes. We examine how schedulability affects the scalability of a robot system, and discuss an algorithm used for off-line schedulability analysis of a distributed task model. We present a distributed coordinated search task and analyze the schedulability of the designed task structure. We are able to analyze communication delays in the system that put upper bounds on the size of the robot teams. We show that hierarchical methods can be used to overcome the scalability problem. We propose that schedulability analysis should be an integrated part of a multi-robot team design process.