Motion Planning for Multi-Agent Systems with Obstacles Based on Buffered Voronoi Cell

This thesis presents a decentralized motion planning algorithm for multi-robot systems in the environment with static obstacles. In the proposed algorithm, the environment is divided into several obstacle-free convex spaces to make sure tools like convex programming can be used and the algorithm do not lead the robot to local minima points. In each time step, the robot finds the largest obstacle-free convex area containing its current position and builds a buffered Voronoi cell based on the position information of the robots in its obstacle-free convex area. Within the buffered Voronoi Cell the robot can move freely without collision. A prediction and recovery mechanism is employed to solve the deadlock that occurred between robots and obstacles. The simulation results indicate that the proposed algorithm can solve the problem effectively for single integrator dynamics robots without non-holonomic constraints in 2D. The idea of the algorithm can also be extended into 3D for Unmanned Aerial Vehicles (UAVs).