People/Web Search Calendar Emergency Info A-Z Index UVA Email University of Virginia

Computer Science Colloquia

Monday, July 1, 2013
Luther Tychonievich
Advisor: James P. Cohoon
Attending Faculty: Worthy Martin (Chair), John C. Knight, abhi shelat, and Ellen Bass.

4:00 PM, Rice Hall, Rm. 242

Ph.D. Dissertation Presentation
Providing Guaranteed Behaviors for Groups of Low-Capability Mobile Agents

ABSTRACT

I consider the problem of designing algorithms for coordinated groups of low-capability, error-prone robots. It is my thesis that some important collective behaviors of groups of low-capability robots can be guaranteed by the application of provably-correct distributed algorithms. This thesis is demonstrated by the provision of new algorithms that improve the ability of robot designers to provide guarantees in the face of noise and robot error, as well as proofs that characterize the requirements of particular robotics tasks. I develop algorithms to maintain local and global cohesion of a moving group of robots; to cause initially-distant robots to rendezvous with one another; and to emulate explicit communication and localization from stigmergy. Each of these problems is solved for several different classes of robot capability. I also present proofs demonstrating that certain capabilities are necessary algorithms with bounded worst-case performance to exist. The necessity proofs contribute to the understanding of how robot capability and behavior are related, assisting further definition of this field.