Complexity Metrics for Physical Computation on Multi-Robot Systems
James McLurkin
MIT CSAIL
jamesm@csail.mit.edu

Traditional complexity measures of running time and memory usage do
not completely describe algorithms running on multi-robot systems
because they do not model physical computation. Multi-robot systems
can often be more constrained by physical computation than by
limitations in processor speed and memory. We propose four complexity
measures for characterizing multi-robot distributed algorithms:
accuracy, physical running time, communication complexity, and
configuration complexity. Accuracy is similar to correctness in
traditional algorithms, and measures how well the robots achieve the
desired physical configuration. The physical running time of an
algorithm must take into account the robot's velocity, the speed at
which messages propagate throughout the network, and the complexity of
the environment. Communication resources are used differently in a
multi-robot system than in a sensor network or in multiprocessor
distributed algorithms, so the communication complexity metric
must consider the robots' communication range, available bandwidth
between neighboring robots, and messaging rate needed to adapt to
changing network topology. Multi-robot systems store algorithm state
in the memory of the processors and in the intermediate physical
configurations the group produces on the way to the desired
configuration. This configuration complexity will help us
quantify the minimum number of robots required for an algorithm, the
amount of information stored in their configuration, and the
algorithmic cost of storing and retrieving this information. 

We are working towards defining these complexity metrics, and using
them to evaluate an extensive library of practical multi-robot
algorithms. The algorithms tested will range from simple behaviors,
such as clustering, to complex applications, such as a depth-first
search of an environment. The final result will be a library of
distributed algorithms with well-characterized real-world performance
characteristics.