Decentralized collision-free control of multiple robots in 2D and 3D spaces

Decentralized control of robots has attracted huge research interests. However, some of the research used impractical assumptions without collision avoidance. This thesis focuses on the collision-free control for multiple robots in complete coverage and search tasks in 2D and 3D areas. Algorithms are decentralized as robots have limited abilities. The areas are arbitrary unknown and all algorithms are mathematically proved.The thesis starts with the grid selection in complete coverage and search tasks. Grid patterns simplify the representation of the area and robots only need to move straightly between neighbor vertices. For a 100% complete 2D coverage, the equilateral triangular grid is proposed. For the complete coverage ignoring the boundary effect, the grid with the fewest vertices is calculated in every situation for both 2D and 3D areas. The second part is for the complete coverage in 2D and 3D areas using a robot network. A decentralized collision-free algorithm with the selected grid pattern above is presented driving robots to sections which are furthest from the reference point. The areas can be static or expanding and the algorithm is simulated in MATLAB. Thirdly, three grid-based decentralized random algorithms with collision avoidance are provided to search targets in 2D or 3D areas. The number of targets can be known or unknown. In the first algorithm, robots choose vacant neighbors randomly with priorities on unvisited vertices while the second one adds the repulsive force to disperse robots if robots have neighbors in the sensing range. In the third algorithm, robots use the breadth-first search algorithm to go to the nearest unvisited vertices through the grid if surrounded by visited vertices. The second search algorithm is verified on Pioneer 3-DX robots and the way to generate the formula to estimate the search time in a general situation is demonstrated. Algorithms are compared with five other algorithms in MATLAB to show their effectiveness