Motion Planning for Multi-Agent Systems with Obstacles based on Buffered Voronoi Cell
Abstract
This paper 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 to be used and robots won’t be stuck in local minimum. In each time step, the robot finds the largest obstacle-free convex area containing its current position and builds a buffered Voronoi cell, within which the robot can move freely without collision, based on the position information of the robots in its obstacle-free convex area. A prediction and recovery mechanism is also employed to solve the deadlock caused between robots and obstacles. The simulation results show that the proposed algorithm can solve the problem effectively for robots with single integrator dynamics and which do not have non-holonomic constraints in 2D dimension. The idea of the algorithm can also be extended into 3D dimensions for Unmanned Aerial Vehicles (UAV).