|
|
|
|
|
ABSTRACT 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. SPEAKER BIO James McLurkin has been building robots for almost 20 years. As manager of the iRobot Swarm project, he developed one of the world's largest swarm of robots, and distributed algorithms to control them as a group. Previous projects include two other robotic communities and some of the world's smallest robots. Mr. McLurkin holds a S.B. in Electrical Engineering with a Minor in Mechanical Engineering from M.I.T., a M.S. in Electrical Engineering from University of California, Berkeley, and a S.M. in Computer Science from M.I.T.. He is currently pursuing a Ph.D. in Computer Science at the M.I.T. Computer Science and Artificial Intelligence Laboratory. James McLurkin The Stata Center - Building 32 - Room G585 32 Vassar St - Cambridge, MA 02139 Email: jamesm@csail.mit.edu URL: http://people.csail.mit.edu/jamesm/ |
|
Back to CRES |