Multi-robot Path Planning with Safety Based Control Applied to the Small Size League Robots

Abstract

This work provides a comparison between two path planners, the coordinated Multi-Robot A Star (MRA*) and uncoordinated Dynamic Visibility Graph A Star (DVG+A*) algorithms when applied to the highly dynamic, uncertain, multi-robot environment of the RoboCup Small Size League. To consider dynamic obstacles and uncertainties, the path planners were combined with the Probabilistic Safety Barrier Certificates (PrSBC) collision avoidance algorithm. Two experiments were proposed to evaluate the performance of the algorithms: the antipodal and the marking tests. Both tests evaluated the algorithms regarding their navigation time, computational time, and minimum distance to other robots. Through the antipodal test, the influence of barrier gain and safety radius of the PrSBC for collision avoidance were analyzed, along with the benefits of using a coordinated path planner versus an uncoordinated one. The marking test explored the capacity of the navigation system to deal with dynamic obstacles. The results have shown that the PrSBC is capable of avoiding collisions in an environment where all robots use the same avoidance algorithm. Furthermore, the coordinated path planner has shown a significantly lower computational time when compared to the uncoordinated algorithms. However, it did not outperform the other algorithms in the navigation time or safety during the marking test. In conclusion, for multi-robot applications, there is a performance improvement when using coordinated path planners. Nevertheless, avoiding every collision is not trivial in the presence of dynamic obstacles, especially at velocities higher than ${2}\,\mathrm{m/s}$.

This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001.