Robot Line Formation

Pattern formation is one of the main research topics in swarm robotics. Its goal is to control the motion of a set of robots in order to form the desired shape. In this thesis, a scalable solution is proposed for the particular case of line formation of differential drive robots, focused on minimizing formation time. The problem is divided into three steps: line formation, target assignment and navigation. The first step consists of choosing the specific line the robots should form, and principal components analysis is used to minimize perpendicular offsets of robot positions to the line. The second step is an assignment problem of N robots to N target positions along the chosen line, and an optimal solution is proposed to minimize formation time, assuming no collisions. The third step is the navigation algorithm that make the robots go from their position to their assigned target, and different algorithms are presented. Simulations with different setups are done to compare the navigation algorithms and to observe how the target assignment algorithm behaves in a less idealistic scenario, where collisions have to be avoided.