The Multi-Agent Navigation Transformation: Tuning-Free Multi-Robot Navigation

Abstract

This paper proposes a novel methodology for decentralized multi-robot navigation with multiple arbitrarily shaped obstacles in 2-dimensional environments. The proposed methodology is based on the novel concepts of the Navigation Transformation and the Harmonic Function based Navigation Functions. A version of the Navigation Transformation -the Multi-Agent Navigation Transformation -is proposed in this paper to map geometrically complex topologies resulting from moving workspace entities to simple topologies enabling the construction of Harmonic Function based Navigation Functions. The resulting vector field is guaranteed to be free of local minima by construction. A construction of a candidate Multi-Agent Navigation Transformation is proposed. In addition to the theoretical guarantees, the effectiveness of the proposed methodology is demonstrated through non-trivial computer simulations utilizing the proposed construction.