Distributed collision avoidance and object sorting for robot swarms

Abstract

A robotics swarm is a set of simple distributed agents cooperating to achieve a certain goal. Each robot works independently of the others based on its own local knowledge without any central coordination. These systems are often inspired by social insects which work collaboratively to perform complicated tasks such as sorting their brood or waste in certain patterns through local interactions. Swarm robotics take inspirations from these natural phenomena to design scalable and robust systems. The work in this thesis can be divided into two main objectives. The first is a general purpose distributed collision avoidance algorithm that enables multiple robots to seamlessly share their environment without colliding or blocking each other's paths. The proposed algorithm is very fast with O(n) complexity and only requires relative positions of neighboring robots. It also has special mechanisms for early deadlock prediction and recovery to prevent robots from getting stuck. The second objective is proposing a distributed sorting algorithm. It builds upon the previous algorithm, which guarantees collisions avoidance and minimizes deadlocks while driving the robots to their goals, and incorporates the ability for a robotic swarm system to cooperatively sort a collection of objects from different classes into desired areas for each class. The design and implementation of this swarm system on a simulation platform and on physical robots will be detailed. A web-based multi-robot simulation platform is developed as a general robotics simulation and will be used to evaluate the different algorithms in our system. We will also showcase and evaluate the proposed swarm system by deploying these algorithms on actual robots.