Swarms of Bouncing Robots

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Pacheco, Eduardo




We study models of mobile robots with limited capabilities that are deployed either on a cycle or an
infinite line or on a segment. Robots start moving at the same time and when two robots collide their
speeds and movement directions are instantaneously updated. Each of them has a collision
detector and a clock to measure the times of its collisions. They do not have any knowledge on the
total number of robots and do not have a common sense of direction. Besides, they neither have
visibility nor control over their movements.
We investigate the feasibility of the localization task in the
cycle and the segment by bouncing
robots: every robot should figure out the starting position and initial velocity of all the other robots.
We consider two different scenarios when robots have common masses and speeds and robots of
arbitrary masses and speeds. We give complete characterizations of all feasible configurations for
the cycle in both scenarios.
We study the survivability of bouncing robots. We say a robot survives if it never returns to
its starting position. Non-surviving robots disappear from the environment. We provide sufficient
and necessary conditions to have
surviving robots in the cycle and in the segment. Finally we
investigate communication protocols for bouncing robots that only communicate at the time of their
collisions. We establish necessary and sufficient conditions for bouncing robots to perform gossiping,
broadcasting and convergecast.


Computer Science




Carleton University

Thesis Degree Name: 

Doctor of Philosophy: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).