Local distributed algorithms for multi-robot systems

The field of swarm robotics focuses on controlling large populations of simple robots to accomplish tasks more effectively than what is possible using a single robot. This thesis develops distributed algorithms tailored for multi-robot systems with large populations. Specifically we focus on local distributed algorithms since their performance depends primarily on local parameters on the system and are guaranteed to scale with the number of robots in the system. The first part of this thesis considers and solves the problem of finding a trajectory for each robot which is guaranteed to preserve the connectivity of the communication graph, and when feasible it also guarantees the robots advanced towards a goal defined by an arbitrary motion planner. We also describe how to extend our proposed approach to preserve the k-connectivity of a communication graph. Finally, we show how our connectivity-preserving algorithm can be combined with standard averaging procedures to yield a provably correct flocking algorithm. The second part of this thesis considers and solves the problem of having each robot localize an arbitrary subset of robots in a multi-robot system relying only on sensors at each robot that measure the angle, relative to the orientation of each robot, towards neighboring robots in the communication graph. We propose a distributed localization algorithm that computes the relative orientations and relative positions, up to scale, of an arbitrary subset of robots. For the case when the robots move in between rounds we show how to use odometry information to allow each robot to compute the relative positions complete with scale, of an arbitrary subset of robots. Finally we describe how to use the our localization algorithm to design a variety of multi-robot tasks.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2013

Author dc:creator

• Cornejo Collado, Alejandro

Advisor dc:contributor.advisor

• Nancy Lynch.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/79220

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/79220