Towards Decentralization of Multi-robot Navigation Functions

We present a navigation function through which a group of mobile agents can be coordinated to achieve a particular formation, both in terms of shape and orientation, while avoiding collisions between themselves and with obstacles in the environment. Convergence is global and complete, subject to the constraints of the navigation function methodology. Algebraic graph theoretic properties associated with the interconnection graph are shown to affect the shape of the navigation function. The approach is centralized but the potential function is constructed in a way that facilitates complete decentralization. The strategy presented will also serve as a point of reference and comparison in quantifying the cost of decentralization in terms of performance.