Swarm Robotics: Measurement and Sorting

To measure is an important ability for robots to sense the environment and nearby robots. Although camera, laser, and ultrasonic provide very accurate measurements, they are expensive and not scalable for large swarm of low-cost robots. The r-one robot designed at Rice University is equipped with infrared transmitters and receivers, which are designed for remote control and are very inexpensive in mass production. They are a good solution for short-range communication, since the signal attenuates at about 1 to 2 meters with appropriate voltage. This work describes my results in using them to measure bearing, orientation, and distance between nearby robots. However, infrared receivers are not designed for this kind of use, so I present a variable transmit power approach to allow useful and efficient local geometry measurements. With the ability to measure bearing and distance, I am able to solve the problem of sorting a group of n robots in a two-dimensional space. I want to organize robots into a sorted and equally-spaced path between the robots with lowest and highest label, while maintaining a connected communication network throughout the process. I begin with a straightforward geometry-based version of sorting algorithm, and point out there are many difficulties when communication range becomes limited. Then I describe a topology-based distributed algorithm for this task. I introduce operations to break the symmetry between minimum and maximum, in order to keep time, travel distance, and communication costs low without using central control. I run a set of algorithms (leader election, tree formation, path formation, path modification, and geometric straightening) in parallel. I show that my overall approach is safe, correct, and efficient. It is robust to population changes, network connectivity changes, and sensor errors. I validate my theoretical results with simulation results. My algorithm implementation uses communication messages of fixed size and constant memory on each robot, and is a practical solution for large populations of low-cost robots