Boyang Zhang,, and Henri P. Gavin

Dear editor,

In this letter, we introduce a decentralized, nonlinear, discontinuous, and computationally simple control law for large scale multiagent navigation systems. The control is based on extending Gauss’s principle of least constraint with a dynamic incorporation of inequality constraints, actuator saturation, and actuator dynamics.With no individual path planner, each agent executes its motion and generates its control actions by reacting solely to the evolution of its constrained dynamics, which is equivalent to solving a linear matrix equation with a dimension up to around 20 without iteration at each time instant. Numerical experiments are conducted on hundreds of two-dimensional (2-D) double integrators subjected to path and collision constraints, demonstrating the promise of the proposed method.

Recent years have witnessed an increasing popularity of multiagent navigation systems in diverse applications such as exploration,surveillance, and rescue [1]. Ongoing research efforts have been focusing on synthesizing multiagent control systems equipped with interagent collision avoidance and computational simplicity [2].Velocity obstacles (VOs) [3], [4], artificial potential fields (APFs)[5], [6], mixed-integer programs (MIPs) [7], [8], and control barrier functions (CBFs) [9], [10] are among those endeavors.

With certain levels of success achieved, these methods may have shortcomings under certain circumstances. For examples, constant speeds are assumed in collision avoidance in VO methods with no solution uniqueness guarantee [3], [4]. APF methods [5], [6] presume infinitely large control actions in order to prevent collisions as agents get sufficiently close to each other, and it is acknowledged that trajectories can get stuck into local minima. When the number of agents becomes large, MIPs [7], [8] become computationally expensive. CBF methods [9], [10], instead, do not incorporate actuator dynamics and may be computationally intense when solving the associated quadratic program (QP) in which the goals are moving.

In large scale 2-D multiagent navigation systems, it is more important for multiple agents to cooperate as a team than each agent planing their own individual trajectory [1]. In this letter, we propose a control rule for multiagent systems navigation within a prescribed time, with collision avoidance, actuator saturation and dynamics,computational simplicity, and with no individual path planner.

Related work: Our method is based on extending Gauss’s principle of least constraint (GPLC). The original GPLC [11], along with its equivalency, the Udwadia-Kalaba (U-K) equations [12], has been employed in the control of small scale multiagent systems [13].However, both the original GPLC and the U-K equations are unable to assimilate inequality constraints, actuator saturation, or actuator dynamics and are not applicable for large scale multiagent systems control.

GPLC has been recently extended by allowing for inequality constraints, actuator saturation and dynamics and utilized in the centralized control of 2-D multiagent navigation systems [14], [15].The centralized controls proposed in [14] and [15] formulate constraints in terms of scalar Euclidean distances and vector relative distances, respectively. These formulations, however, cannot allow agents to follow a guiding virtual leader that possesses high-speed,high-curvature trajectories. Moreover, their computational complexities are approximately cubically scaled in the number of agents,making them not suitable for controlling large scale multiagent systems.

In the following, we first lay out foundations for a decentralized control scheme based on a Lagrangian viewpoint of GPLC. We then develop a decentralized multiagent navigation control where constraints are decomposed along different dimensions and partitioned between colliding agents. Next, we present and discuss numerical results for navigating hundreds of agents, followed by the conclusions and future work.

Fig. 1. Trajectories of 200 agents swarming with a virtual leader moving along a figure-eight path. The black dashed line denotes the virtual leader’s path around 5.25-km long executed within 60 s (average speed ～315 km/h).The colored solid lines are the paths of all agents, with * and × respectively denoting the start and end positions. Each agent’s decentralized navigation control law results from reacting purely to its constrained dynamics (13).

Fig. 2. The minimum relative distance over all active colliding agent pairs along the X axis, the Y axis, and between the centroids, respectively. The minimum pairwise distance starts from 3.26 m and is stabilized to around 10 m after the first 5 seconds of initial transients.

Fig. 3. Themaximumandminimumsaturatedandactualcontrol forces,fis and fia, overallagents.fisprecedesfiadueto thefirst-orderactuator dynamics.The green dashed lines denote the actuator saturation bounds.