Multi-agent navigation functions: Have we missed something?

This paper presents a methodology for designing (centralized) control laws which can probably steer a group of robotic agents to fall into a formation of arbitrary shape, while following collision free trajectories. The scheme is based on the concept of navigation functions, a special type of artificial potential functions without local minima, and the paper describes how this idea can be generalized from its original formulation for single-robot systems, to multi-robot formations. We indicate why existing solutions that have appeared in literature, although potentially functional, may not have been accompanied with sufficient guarantees against the possibility of the system ever getting stuck in non-optimal configurations. The problem is therefore revisited here under a new set of assumptions, a new construction is proposed, and the properties of this new centralized potential function are analytically demonstrated.This work is supported by NSF under grant #0822845