Distributed MPC for multi-vehicle systems moving in formation

Highlights

• A novel distributed model predictive strategy for multi-vehicle systems is proposed.

• Trajectories are modeled as splines and constraints on them are efficiently enforced.

• Computations are distributed among the agents by using the ADMM.

• One ADMM iteration is used per MPC update to reduce computations and communication.

• Simulations and experiments with formations of UAVs and UGVs validate the method.

Abstract

This work presents a novel distributed model predictive control (DMPC) strategy for controlling multi-vehicle systems moving in formation. The vehicles’ motion trajectories are parameterized as polynomial splines and by exploiting the properties of the B-spline basis functions, constraints on the trajectories are efficiently enforced. The computations for solving the resulting optimization problem are distributed among the agents by the Alternating Direction Method of Multipliers (ADMM). In order to reduce the computation time and the amount of inter-vehicle interaction, only one ADMM iteration is performed per control update. In this way the method converges over the subsequent control updates. Simulations for various nonholonomic vehicle types and an experimental validation on in-house developed robotic platforms prove the capability of the proposed approach. A supporting software toolbox is provided that implements the proposed approach and that facilitates its use.

Introduction

Boosted by enhancements in communication technologies and computational power, networked multi-vehicle systems have received increasing attention over the last decades. A particular application hereof is formation control of multi-vehicle systems, which forms the basis for applications such as cooperative transportation by small automated guided vehicles or cooperative surveillance. Furthermore, it is well known that the flight efficiency substantially increases when aerial vehicles fly in close formation [1].

State-of-the-art formation control approaches for unmanned vehicles are divided in three main groups: leader–follower techniques [2], [3], virtual structure approaches [4], [5] and behavioral methods [6], [7]. Recent research in these areas mainly focuses on formation stabilization [8], [9] and formation following a predefined path [10], [11]. Integrating motion planning in the formation control structure is typically achieved by separating the problem in (i) finding a trajectory for the (virtual) leader and (ii) controlling the other vehicles to attain a desired relative position with respect to the leader [12]. This architecture is however not robust against failures of the leader. Therefore, this paper aims for an approach in which all members of the formation are equal. This implies that each vehicle searches for its own trajectory. By allowing communication, the vehicles are able to adapt their trajectories in order to satisfy the formation constraints. Such distributed control structure benefits from the flexibility to add or discard agents from the controlled multi-agent system, the possibility to hide local information and the ability to choose and optimize the information flow between the agents. An appealing framework allowing for such architecture is distributed model predictive control (DMPC). It can explicitly address input and state constraints, account for multiple control objectives, and incorporate forecasts of disturbances. Moreover, DMPC distributes the computational load of solving the control problem among the different agents. DMPC has been a very active research area since the end of the 1990s. The reader is referred to [13], [14], [15], [16] for an overview and comparison of various existing approaches.

The control of multi-vehicle systems is in general a complex problem. Various existing MPC approaches have only been applied to the use of linear vehicle dynamics or lack the flexibility to add arbitrary (nonconvex) constraints to the problem formulation such as collision avoidance constraints [17], [18]. Approaches considering realistic nonconvex multi-vehicle problems are mostly limited to solving offline optimal control problems [19], [20]. Decoupling the multi-vehicle control problem efficiently imposes an extra difficulty. Existing DMPC strategies typically solve in every update cycle an optimization problem in a distributed fashion [21], [22]. This generally involves multiple iterations, each of which requires solving local optimization problems and substantial communication between neighboring agents. This often results in too slow update rates in practice as the control law should be implemented on the vehicle’s embedded hardware, which has restricted computational power and communication capabilities.

This paper aims at reducing the existing gap in the literature by presenting a novel DMPC strategy for controlling multi-vehicle systems. The approach focuses on realistic complex problems, including nonlinear vehicle dynamics and collision avoidance constraints. It applies to a particular class of vehicles, including holonomic vehicles, quadrotors and differential wheeled robots. Although various types of vehicle interaction can be incorporated, this paper focuses on vehicles moving in formation.

The approach is based on two main ingredients that allow to solve the resulting optimal control problem in an efficient manner. First, the multi-vehicle problem is decoupled such that the computational load can be distributed over the agents. This is achieved by applying the Alternating Direction Method of Multipliers (ADMM) [23]. In order to reduce the amount of communication, an updating scheme is proposed that solves only one ADMM iteration per control update. Second, a spline parameterization for the vehicles’ motion trajectories and a related enforcement of constraints on these trajectories allow an efficient reformulation of an agent’s local subproblem [24], [25], [26]. This further reduces the computational load of one control update. Although no formal stability proof is provided, various numerical results and an experimental validation demonstrate that the ADMM iterations converge over the subsequent control updates. These updates are performed at a sufficiently fast rate with only a limited loss of optimality. As a complement to the paper, a software toolbox is provided that implements the proposed approach and that forms a user-friendly interface for modeling and simulating the considered problems [27]. Furthermore, additional illustrative examples are supplied in the toolbox.

Section 2 describes the considered vehicle types and the multi-vehicle control problem. Section 3 shows how this problem is reformulated in a small-scale optimization problem, how it is solved in receding-horizon and how it is decoupled over the agents. The proposed approach is further analyzed and illustrated with simulation and experimental examples in Section 4. Finally, Section 5 draws concluding remarks. A preliminary version of this paper considering only linear vehicle dynamics in simulation was presented in [28].