Prioritized group navigation with Formation Velocity Obstacles

We introduce the problem of navigating a group of robots having prioritized formations amidst static and dynamic obstacles. Our formulation allows users to define a number of template formations, each with a specified priority value. At each planning cycle, we compute a new formation which accounts for both these priority values and the safe progress of the robots towards their goal. To this end, we introduce a new velocity-based navigation approach which we denote as Formation Velocity Obstacles (FVO). Like other velocity-based approaches, FVO allows anticipatory collision avoidance accounting for the likely future motion of nearby obstacles. However, we extend these previous approaches and allow anisotropic agents which rotate themselves to orient along their direction of travel. We integrate these FVOs with a Bayesian framework to infer priority values for arbitrary formations from the user-given templates. The result is a complete framework for prioritized formation planning.

I. Introduction

Multiple robots walking together as a group while maintaining specific configurations are nowadays commonly used to perform critical tasks, such as search and rescue op-erations, exploration and security patrols. In robotics, the formation control problem has been extensively studied and different methods have been proposed to control the dynamics and stability of a group formation, including behavioral-based approaches [1], [2], leader-follower models [3], [4], virtual structure techniques [5], [6], social potential fields [7] and roadmap-based methods [8], [9]. Recently, the problem of pattern formation has also been studied, where the task is to generate smooth and collision-free transitions between arbitrary formations in obstacle-free environments [10], [11].