# Decentralized Model Predictive Control for Cooperative Multiple Vehicles Subject to Communication Loss

Authors: Hojjat A. Izadi; Brandon W. Gordon; Youmin Zhang
Journal: International Journal of Aerospace Engineering
 (2011)

---

## Abstract

The decentralized model predictive control (DMPC) of multiple cooperative vehicles with the possibility of communication loss/delay is investigated. The neighboring vehicles exchange their predicted trajectories at every sample time to maintain the cooperation objectives. In the event of a communication loss (packet dropout), the most recent available information, which is potentially delayed, is used. Then the communication loss problem changes to a cooperative problem when random large communication delays are present. Such large communication delays can lead to poor cooperation performance and unsafe behaviors such as collisions. A new DMPC approach is developed to improve the cooperation performance and achieve safety in the presence of the large communication delays. The proposed DMPC architecture estimates the tail of neighbor's trajectory which is not available due to the large communication delays for improving the performance. The concept of the tube MPC is also employed to provide the safety of the fleet against collisions, in the presence of large intervehicle communication delays. In this approach, a tube shaped trajectory set is assumed around the trajectory of the neighboring vehicles whose trajectory is delayed/lost. The radius of tube is a function of the communication delay and vehicle's maneuverability (in the absence of model uncertainty). The simulation of formation problem of multiple vehicles is employed to illustrate the effectiveness of the proposed approach.


---

## Body

## 1. Introduction

To address the intervehicle communication loss/delay in a network of cooperative multiple vehicles, a previously developed delay-dependent decentralized model predictive control (DMPC) architecture in [1] is modified and extended to subsystems with generic class of dynamics, subject to intervehicle communication packet loss. The proposed decentralized model predictive control (DMPC) features two main contributions. The first contribution is the development of a new DMPC approach that estimates the trajectory of the neighboring vehicles for the tail of the prediction horizon which would otherwise not be available due to the communication losses leading to random communication delays. In this approach, the tail of the cost function is estimated by adding extra decision variables in the cost function.A relatively small amount of existing works have investigated the implementation issues such as communication loss associated with the exchange of trajectory information, but so far a few works have proposed a systematic tail estimation process to compensate for large delays. For example, in [2–5], it is assumed that the neighboring vehicles remain stationary at the last delayed states broadcasted by them. Such assumptions may yield poor performance for large communication delays, because the stationary state vector is not necessarily an accurate estimate of a time-varying state vector. Similar issues are investigated in [6], where for the hardware implementation of a robust DMPC to wheeled robots, both computation and communication delays are considered. To account explicitly for the time delays a model of the vehicle is used to estimate their state vector when required. Then the uncertainty arising from this estimation is taken into account by accommodating that into the effective disturbance force used for constraint tightening. Also, in [7], the stability, feasibility, and computation issues of a distributed MPC are investigated. The main practical attraction of the proposed architecture in [7] is that it allows terminating the computations at the end of each sampling period even if convergence is not achieved; this feature facilitates the real-time implementation of DMPC.The second contribution of this paper is an extension of the tube-based model predictive control (MPC) approach [8, 9] for the case of the large communication delays in order to guarantee the safety of the fleet against possible collisions during formation control problems. The concept of the tube MPC in the existing works [8, 9] is normally used to calculate a robust bound on the states due to model uncertainty, whereas in this paper the approach is used to calculated bounds on the exchanged neighbor trajectories when large intervehicle communication delays exist.In [10], the wireless communication packet loss/delay is considered; once the packet loss/delay occurs, the previous available trajectory of the faulty vehicle—whose trajectory is delayed—is extrapolated to predict the future reference trajectory. Also, in [11], the communication failure in formation flight of multiple vehicles leads to break in the communicated messages that force the fleet to redefine the communication graph.This paper is organized as follows. Section2 presents a general formulation of the delay-free decentralized model predictive controller and the corresponding algorithm. In Section 3 a new delay-compensated DMPC (DC-DMPC) is developed to address the communication delays arising from communication losses. A safety guarantee method is also developed based on the concept of tube MPC. In Section 4 the proposed algorithms are tested through simulation of a leader-follower formation problem for a fleet of unmanned vehicles.


## 2. Decentralized Model Predictive Control

Consider a team of cooperative vehicles with uncoupled dynamics. Each vehicle is equipped with three main components: (1) measurement sensors, (2) communication device, and (3) computation resource. The measurement sensors of each vehicle measure its own states assuming full state measurement is available. The communication device is used to gather the information from the neighboring vehicles and communicate with human operators. Using the computation resource, each vehicle solves a decentralized optimization problem at each sampling time based on its current measured states (from sensors) and the neighbor’s predicted state trajectories (provided through communication). It is further assumed that there is no sensor error, model uncertainty, or communication noise. These assumptions allow focusing on the main problem concerning intervehicle communication loss/delay. The developed algorithms do not rely on such assumptions; in fact, these assumptions are not restrictive for extending the proposed algorithms to nonideal situations. It is worth mentioning that even if a perfect model of neighboring vehicle is available still there is a possibility of mismatch between the predicted neighboring vehicle’s trajectory and the actual ones, because the neighboring vehicles may use a particular communication topology which leads to different DRHC optimization problems and hence different solutions. This problem can be overcome only by a centralized approach which is beyond the approach of this paper,  because in a centralized approach only one communication topology which connects all the team members exists. Then, it is intended to focus on such mismatches arising from decentralized nature of the problem rather than mismatches coming from model uncertainty, and so forth.Moreover, the termsagent,vehicle,team, member, and subsystem bear the same meaning. And so do the terms group, team, fleet, and network.


### 2.1. Interaction Graph Topologies

Graph theory is a relevant mathematical tool for modeling and analyzing the interactions among the cooperative vehicles (see for instance, [12, 13]). Graph topology is described by two basic elements: nodes and edges. Nodes represent the vehicles, and an edge between two nodes denotes the interaction between those vehicles. The interaction graph is denoted by 𝔾 and represented as follows:(1)G={V,E},
where 𝕍 is the set of nodes (vehicles) and 𝔼⊆𝕍×𝕍 is the set of edges (i,j), with i,j∈𝕍. Hence, considering a set of Nv vehicles cooperating to perform a common mission, the ith vehicle in the team is assigned to the ith node of the graph. If an edge (i,j) connecting the ith and jth node is present in 𝔼, it means that the ith and jth vehicles have an interaction. This relation is termed as neighborhood for ith and jth vehicles, and it is said that(i)
ith and jth vehicles are neighboring vehicles;(ii)
ith vehicle is a follower of the jth vehicle;(iii)
jth vehicle is a leader of the ith vehicle.Also, it is assumed that the interaction graph isdirected, that is, (i,j)∈𝔼 does not necessarily imply (j,i)∈𝔼, unless it appears explicitly in 𝔼. Further, let Nli and Nfi denote the number of the leaders and followers of vehicle i, respectively.In this paper, the information exchange structure coincides the control structure; in fact, an edge(i,j) indicates that (1) vehicle j sends information on its planned trajectory to i and (2) the cost function of vehicle j is coupled to states of vehicle i. Also, it is assumed that the interaction graphs have a particular fixed structure and is set by the human operator prior to the mission.


### 2.2. DMPC Notation and Terminology

With model predictive control, a cost function is optimized over a finite time window called theprediction horizon, N. The first of the computed optimal inputs is applied to the plant. The reader is referred to [14] for a comprehensive review of MPC schemes.In this paper, the DMPC architecture is formulated based on the quasi-infinite-RHC formulation [15] where the key is to tune the terminal cost so that the closed-loop MPC has the property of an infinite horizon controller. In this approach the states are driven to a neighborhood of the origin where it is a positively invariant set under a feedback terminal controller for linearized system.The discrete timing is then shown byk where k∈ℕ. As mentioned for the DMPC scheme presented in this paper the neighboring vehicles exchange their predicted state trajectories to provide cooperation. However, as we will see later for the time periods when the updated leader’s state trajectory is not available, it is estimated by the followers. Hence, considering the trajectory of vehicles, those calculated by themselves and those estimated by followers, an appropriate notation is required to present all these possible trajectories (actual, predicted, and estimated). The possible state vectors are introduced as follows:(i)
xi(k): the actual state vector of the ith vehicle at time step k;(ii)
xki(p): the state vector of the ith vehicle at time p, predicted by the ith vehicle at time step k, where p=0,1,2,…,N;(iii)
xki,j(p): the state vector of the ith vehicle at time step k, estimated by the jth vehicle at time step k where p=0,1,2,…,N.Further, the sequence of states over the prediction horizon is called the state trajectory of vehiclei calculated by itself and is represented by xki(·):
(2)xki(⋅)={xki(p)∣p=0,1,2,…,N},uki(⋅)={uki(p)∣p=0,1,2,…,N-1}.
Then let the following represent the concatenated state and input trajectories of the leader(s) of the ith vehicle at time k:
(3)xk-i(⋅)={xkj(⋅)∣j∈V,(i,j)∈E},uk-i(⋅)={ukj(⋅)∣j∈V,(i,j)∈E}.
If the trajectory is defined on an interval which is different from [k,k+N] by other vehicles, then the beginning and end times are indicated as xki,j(b:e), that is,
(4)xki,j(b:e)={xki,j(p)∣p=b,b+1,…,e,j∈V,(i,j)∈E},
where  [b:e] is the interval on which the trajectory is defined.


### 2.3. Delay-Free DMPC Formulation

In this section, a brief overview of a delay-free DMPC problem and its implementation are described.  More details can be obtained from [6, 12, 16]. For the DMPC scheme presented in this paper, the predicted trajectories are exchanged instead of being estimated, thereby reducing the online computational time. Figure 1 shows the delay-free intervehicle communication between two neighboring vehicles and the information exchange at time step k.Figure 1
The delay-free intervehicle communication between two neighbors.In Figure1, it is assumed that the current leader’s predicted trajectories are always available instantly to their followers. However, at least one step delay has to be considered as the current predicted trajectories are not available instantly, even if an infinite communication bandwidth is used. Then, the information set of the ith vehicle for the case of communication delay-free  DMPC is introduced as follows:(5)Γi(k)={xi(k),xk-1-i(⋅)},
where set Γi(k) contains the updated information available to the ith vehicle at time step k and is referred to the information set in this paper. This collects (1) the instant state vector of the ith vehicle and (2) the concatenated state trajectory of neighbors calculated at the previous time step, xk-1-i(·).For the particular case of formation control, the delay-free decentralized cost function for theith vehicle in the team at time k is defined as follows:(6)Ji(Γi(k),uki(⋅))=∑p=0N-1(‖xki(p)-xT,i‖Q2+‖uki(p)‖R2)+‖xki(N)-xT,i‖P2+∑j∣(i,j)∈E(∑p=0N-1‖xki(p)-xk-1j(p)-ri,j‖S2),
where ∥x∥Q2=x′Qx and P,Q, R, and S are positive definite and symmetric matrices, xT,i is the state vector of target (waypoint) of vehicle i, and ri,j is the vector of desired relative position between vehicles i and j.


#### 2.3.1. Delay-Free DMPC Problem

Assume that the following describes the discrete-time dynamics of the (homogeneous) vehiclei:(7)xi(p+1)=f(xi(p),ui(p)),xi(0)=xi(0).
Then, the delay-free DMPC problem 𝒫i(k) is defined for any vehicle i∈𝕍 at time step k as follows.Problem 1.
Delay-Free DMPC Problem𝒫i(k). Calculate
(8)Ji(Γi(k))=Min⁡{uki(⋅),xki(⋅)}Ji(Γi(k),uki(⋅))
subject to (for p=0,1,2,…,N-1)(9a)xki(p+1)=f(xki(p),uki(p));xki(0)=xi(k),(9b)xki(p)∈Xi,uki(p)∈Ui,(9c)xki(N)∈Xfi, where 𝕏i, 𝕌i, and 𝕏fi⊆𝕏i denote the set of admissible states, inputs, and final states (terminal region), respectively, for the ith vehicle.


#### 2.3.2. Delay-Free DMPC Algorithm

Each vehiclei at each sampling period solves the decentralized problem 𝒫i(k). The output of the optimization problem 𝒫i(k) is the predicted input and state trajectories of vehicle i. The generated state trajectory is sent to followers for cooperation purposes, and the first optimal input is applied to the individual vehicle i. The following algorithm is presented for the online implementation of the delay-free DMPC problem above. The algorithm is formulated for the ith vehicle as in Algorithm 1.Algorithm 1:Delay-free DMPC.
Given𝔼 and initial condition of vehicle i, do:(1)k←0.(2) Measurexi(k) and update the information set Γi(k) based on (4).(3) Solve𝒫i(k) and predict the control and state trajectories uki(·) and xki(·).(4) Send the predicted state trajectoryxki(·) to all followers j (where (j,i)∈𝔼).(5) Apply the control actionuki(0) to vehicle i.(6) Receive the trajectoryxkj(·) from leader(s) j (where (i,j)∈𝔼).(7)k←k+1. GOTO step 2.Initialization
Fork=0 at steps 2 and 3, assume Nli=0 (because no information from leader(s) is available).Algorithm1 is repeated until the assigned targets are reached. The targets are assumed to be known and assigned to each agent a priori.


## 2.1. Interaction Graph Topologies

Graph theory is a relevant mathematical tool for modeling and analyzing the interactions among the cooperative vehicles (see for instance, [12, 13]). Graph topology is described by two basic elements: nodes and edges. Nodes represent the vehicles, and an edge between two nodes denotes the interaction between those vehicles. The interaction graph is denoted by 𝔾 and represented as follows:(1)G={V,E},
where 𝕍 is the set of nodes (vehicles) and 𝔼⊆𝕍×𝕍 is the set of edges (i,j), with i,j∈𝕍. Hence, considering a set of Nv vehicles cooperating to perform a common mission, the ith vehicle in the team is assigned to the ith node of the graph. If an edge (i,j) connecting the ith and jth node is present in 𝔼, it means that the ith and jth vehicles have an interaction. This relation is termed as neighborhood for ith and jth vehicles, and it is said that(i)
ith and jth vehicles are neighboring vehicles;(ii)
ith vehicle is a follower of the jth vehicle;(iii)
jth vehicle is a leader of the ith vehicle.Also, it is assumed that the interaction graph isdirected, that is, (i,j)∈𝔼 does not necessarily imply (j,i)∈𝔼, unless it appears explicitly in 𝔼. Further, let Nli and Nfi denote the number of the leaders and followers of vehicle i, respectively.In this paper, the information exchange structure coincides the control structure; in fact, an edge(i,j) indicates that (1) vehicle j sends information on its planned trajectory to i and (2) the cost function of vehicle j is coupled to states of vehicle i. Also, it is assumed that the interaction graphs have a particular fixed structure and is set by the human operator prior to the mission.


## 2.2. DMPC Notation and Terminology

With model predictive control, a cost function is optimized over a finite time window called theprediction horizon, N. The first of the computed optimal inputs is applied to the plant. The reader is referred to [14] for a comprehensive review of MPC schemes.In this paper, the DMPC architecture is formulated based on the quasi-infinite-RHC formulation [15] where the key is to tune the terminal cost so that the closed-loop MPC has the property of an infinite horizon controller. In this approach the states are driven to a neighborhood of the origin where it is a positively invariant set under a feedback terminal controller for linearized system.The discrete timing is then shown byk where k∈ℕ. As mentioned for the DMPC scheme presented in this paper the neighboring vehicles exchange their predicted state trajectories to provide cooperation. However, as we will see later for the time periods when the updated leader’s state trajectory is not available, it is estimated by the followers. Hence, considering the trajectory of vehicles, those calculated by themselves and those estimated by followers, an appropriate notation is required to present all these possible trajectories (actual, predicted, and estimated). The possible state vectors are introduced as follows:(i)
xi(k): the actual state vector of the ith vehicle at time step k;(ii)
xki(p): the state vector of the ith vehicle at time p, predicted by the ith vehicle at time step k, where p=0,1,2,…,N;(iii)
xki,j(p): the state vector of the ith vehicle at time step k, estimated by the jth vehicle at time step k where p=0,1,2,…,N.Further, the sequence of states over the prediction horizon is called the state trajectory of vehiclei calculated by itself and is represented by xki(·):
(2)xki(⋅)={xki(p)∣p=0,1,2,…,N},uki(⋅)={uki(p)∣p=0,1,2,…,N-1}.
Then let the following represent the concatenated state and input trajectories of the leader(s) of the ith vehicle at time k:
(3)xk-i(⋅)={xkj(⋅)∣j∈V,(i,j)∈E},uk-i(⋅)={ukj(⋅)∣j∈V,(i,j)∈E}.
If the trajectory is defined on an interval which is different from [k,k+N] by other vehicles, then the beginning and end times are indicated as xki,j(b:e), that is,
(4)xki,j(b:e)={xki,j(p)∣p=b,b+1,…,e,j∈V,(i,j)∈E},
where  [b:e] is the interval on which the trajectory is defined.


## 2.3. Delay-Free DMPC Formulation

In this section, a brief overview of a delay-free DMPC problem and its implementation are described.  More details can be obtained from [6, 12, 16]. For the DMPC scheme presented in this paper, the predicted trajectories are exchanged instead of being estimated, thereby reducing the online computational time. Figure 1 shows the delay-free intervehicle communication between two neighboring vehicles and the information exchange at time step k.Figure 1
The delay-free intervehicle communication between two neighbors.In Figure1, it is assumed that the current leader’s predicted trajectories are always available instantly to their followers. However, at least one step delay has to be considered as the current predicted trajectories are not available instantly, even if an infinite communication bandwidth is used. Then, the information set of the ith vehicle for the case of communication delay-free  DMPC is introduced as follows:(5)Γi(k)={xi(k),xk-1-i(⋅)},
where set Γi(k) contains the updated information available to the ith vehicle at time step k and is referred to the information set in this paper. This collects (1) the instant state vector of the ith vehicle and (2) the concatenated state trajectory of neighbors calculated at the previous time step, xk-1-i(·).For the particular case of formation control, the delay-free decentralized cost function for theith vehicle in the team at time k is defined as follows:(6)Ji(Γi(k),uki(⋅))=∑p=0N-1(‖xki(p)-xT,i‖Q2+‖uki(p)‖R2)+‖xki(N)-xT,i‖P2+∑j∣(i,j)∈E(∑p=0N-1‖xki(p)-xk-1j(p)-ri,j‖S2),
where ∥x∥Q2=x′Qx and P,Q, R, and S are positive definite and symmetric matrices, xT,i is the state vector of target (waypoint) of vehicle i, and ri,j is the vector of desired relative position between vehicles i and j.


### 2.3.1. Delay-Free DMPC Problem

Assume that the following describes the discrete-time dynamics of the (homogeneous) vehiclei:(7)xi(p+1)=f(xi(p),ui(p)),xi(0)=xi(0).
Then, the delay-free DMPC problem 𝒫i(k) is defined for any vehicle i∈𝕍 at time step k as follows.Problem 1.
Delay-Free DMPC Problem𝒫i(k). Calculate
(8)Ji(Γi(k))=Min⁡{uki(⋅),xki(⋅)}Ji(Γi(k),uki(⋅))
subject to (for p=0,1,2,…,N-1)(9a)xki(p+1)=f(xki(p),uki(p));xki(0)=xi(k),(9b)xki(p)∈Xi,uki(p)∈Ui,(9c)xki(N)∈Xfi, where 𝕏i, 𝕌i, and 𝕏fi⊆𝕏i denote the set of admissible states, inputs, and final states (terminal region), respectively, for the ith vehicle.


### 2.3.2. Delay-Free DMPC Algorithm

Each vehiclei at each sampling period solves the decentralized problem 𝒫i(k). The output of the optimization problem 𝒫i(k) is the predicted input and state trajectories of vehicle i. The generated state trajectory is sent to followers for cooperation purposes, and the first optimal input is applied to the individual vehicle i. The following algorithm is presented for the online implementation of the delay-free DMPC problem above. The algorithm is formulated for the ith vehicle as in Algorithm 1.Algorithm 1:Delay-free DMPC.
Given𝔼 and initial condition of vehicle i, do:(1)k←0.(2) Measurexi(k) and update the information set Γi(k) based on (4).(3) Solve𝒫i(k) and predict the control and state trajectories uki(·) and xki(·).(4) Send the predicted state trajectoryxki(·) to all followers j (where (j,i)∈𝔼).(5) Apply the control actionuki(0) to vehicle i.(6) Receive the trajectoryxkj(·) from leader(s) j (where (i,j)∈𝔼).(7)k←k+1. GOTO step 2.Initialization
Fork=0 at steps 2 and 3, assume Nli=0 (because no information from leader(s) is available).Algorithm1 is repeated until the assigned targets are reached. The targets are assumed to be known and assigned to each agent a priori.


## 2.3.1. Delay-Free DMPC Problem

Assume that the following describes the discrete-time dynamics of the (homogeneous) vehiclei:(7)xi(p+1)=f(xi(p),ui(p)),xi(0)=xi(0).
Then, the delay-free DMPC problem 𝒫i(k) is defined for any vehicle i∈𝕍 at time step k as follows.Problem 1.
Delay-Free DMPC Problem𝒫i(k). Calculate
(8)Ji(Γi(k))=Min⁡{uki(⋅),xki(⋅)}Ji(Γi(k),uki(⋅))
subject to (for p=0,1,2,…,N-1)(9a)xki(p+1)=f(xki(p),uki(p));xki(0)=xi(k),(9b)xki(p)∈Xi,uki(p)∈Ui,(9c)xki(N)∈Xfi, where 𝕏i, 𝕌i, and 𝕏fi⊆𝕏i denote the set of admissible states, inputs, and final states (terminal region), respectively, for the ith vehicle.


## 2.3.2. Delay-Free DMPC Algorithm

Each vehiclei at each sampling period solves the decentralized problem 𝒫i(k). The output of the optimization problem 𝒫i(k) is the predicted input and state trajectories of vehicle i. The generated state trajectory is sent to followers for cooperation purposes, and the first optimal input is applied to the individual vehicle i. The following algorithm is presented for the online implementation of the delay-free DMPC problem above. The algorithm is formulated for the ith vehicle as in Algorithm 1.Algorithm 1:Delay-free DMPC.
Given𝔼 and initial condition of vehicle i, do:(1)k←0.(2) Measurexi(k) and update the information set Γi(k) based on (4).(3) Solve𝒫i(k) and predict the control and state trajectories uki(·) and xki(·).(4) Send the predicted state trajectoryxki(·) to all followers j (where (j,i)∈𝔼).(5) Apply the control actionuki(0) to vehicle i.(6) Receive the trajectoryxkj(·) from leader(s) j (where (i,j)∈𝔼).(7)k←k+1. GOTO step 2.Initialization
Fork=0 at steps 2 and 3, assume Nli=0 (because no information from leader(s) is available).Algorithm1 is repeated until the assigned targets are reached. The targets are assumed to be known and assigned to each agent a priori.


## 3. Delay-Compensated DMPC (DC-DMPC)

This section develops a new delay-compensated DMPC (DC-DMPC) approach. The safety issues are also discussed.


### 3.1. Delayed Cost Function and Information Set

Assume at time stepk the vehicle i receives the information from neighbor j with time-delay d, where d∈ℕ and d≥1, see Figure 2. Then, the term large communication delays denotes the time delays which are larger than the sampling period, that is, d>1.Figure 2
Delayed intervehicle communication between two neighboring vehicles.When a vehicle receives the delayed information from neighbors the information set is updated as follows (compare with (5)):(10)ΓDi(k)={xi(k),xk-d-i(⋅)}.
The information setΓDi(k) represents updated information available to the ith vehicle at time step k. It implies at time step k that each vehicle i has access to its own delay-free information and delayed information from neighbors. Then, the decentralized delayed cost function for all i∈𝕍 at time step k is defined as follows (compare with (6)):(11)JDi(ΓDi,uki(⋅))=∑p=0N-1(‖xki(p)-xT,i‖Q2+‖uki(p)‖R2)+‖xki(N)-xT,i‖P2+∑j∣(i,j)∈E(∑p=0N-d‖xki(p)-xk-dj(p)-ri,j‖S2).The communication delay affects the cooperation cost for the periods when the leader’s trajectory is not available. In fact, for the tail of the cost function during[N-d:N] the leader’s trajectory is not available due to communication delay to calculate the cost function. More precisely, assume at time step k the vehicle i receives the information from neighbor j with time-delay d, where d∈ℕ and d≥1. Then, the trajectory of neighbor j for only the time interval [k-d,k+N-d] is available to vehicle i, while according to cost function of (6) vehicle i needs the trajectory of neighbor j for the entire interval [k,k+N]. Hence for the portion [k+N-d,k+N] the trajectory of j is not available due to the delay (see Figure 3). When the time delay is small this lack of information is not important, but for large communication delays the tail of cost function during [k+N-d,k+N] becomes large and as shown by simulations in Section 4 it can lead to poor performance and unsafe behaviors (see also [13, 17]). One remedy to this problem is proposed here by estimating the tail of the cost function by including extra decision variables in the cost function.Figure 3
Tail of the leader’s trajectory in the presence of large communication delayd.


### 3.2. Delay-Compensated Cost Function

The main idea with the proposed cost function is that it replaces the missing information due to communication loss, with the decision variables. Then, the decision variables are used to approximate the missing information. More specifically, communication losses prevent access to updated leader’s trajectory, and then the available delayed neighbor’s trajectory is utilized. However, the delayed leader’s trajectories do not cover the entire time slot required by follower to calculate its cost function; hence, a delay-compensated cost function is proposed as follows (for theith vehicle in the team at time step k):(12)JDCi(ΓDi(k),uki(⋅),xk-i(N-d:N),uk-i(N-d:N))=JDi(ΓDi(k),u⋅∣ki)+JTaili(xk-i(N-d:N),uk-i(N-d:N)),
where JDi is calculated from (11) and(13)JTaili(xk-i(N-d:N),uk-i(N-d:N))=∑j∣(i,j)∈E[∑p=N-d+1N(‖xki(p)-xkj,i(p)-ri,j‖S2+‖xkj,i(p)-xT,j‖Q2+‖ukj,i(p)‖R2)+‖xkj,i(N)-xT,j‖P2∑p=N-d+1N].
The subscript “D” stands for “Delay”. The delay-compensated decentralized cost function JDCi includes two main parts.(1)
The delayed costJDi which includes the cost of local vehicle i and the cost of neighboring vehicles calculated from the delayed information. Literally, this part is calculated using the information available from communication (and measurement sensors for local vehicle).(2)
The tail costJTaili (13) which calculates the cost associated with the neighbors over the tail of the cost function during [N-d+1:N] where information is not available due to the communication loss/delay.  In fact, the added extra decision variables are used to calculate this part.Although it is assumed that there is model uncertainty and communication noise, the lack of updated information due to communication loss will impose an uncertainty on the updated leader’s trajectory, because, in the event of communication loss, the followers will utilize the leader’s delayed trajectory, which may differ from the updated unavailable trajectories. Such uncertainty which is derived from the mismatch between updated and delayed trajectories may lead to poor performance of the decentralized DMPC.


### 3.3. Safety Guarantee Using Tube DMPC

For the particular case of formation control, consider a group of vehicles that are required (1) to keep certain relative positions (local objective) and (2) to visit a set of waypoints (global objective). In general, incorporating the collision avoidance constraint into the optimization problem of DMPC is not trivial because of the nonconvexity nature of the distance constraint. To address this problem, in [18] a hybrid rule-based extension of the decentralized model predictive control (DMPC) is proposed to avoid possible collisions. Also, in [19] a mixed integer linear programming (MLIP) approach is utilized to handle the nonconvex collision avoidance constraint using a DMPC architecture.The problem becomes even more serious when the large communication delays exist because communication delay leads to a lack of updated information on the trajectory of neighboring vehicles and this can make the formation unsafe and put the team in jeopardy. Hence, a discussion on the collision avoidance is required.In practice, normally the desired distance in formation control is chosen large enough to ensure safety against overshoots and uncertainties. In this paper another approach which is applicable to both delay-free and delayed situations is proposed. In this approach, instead of using an assumed trajectory for neighboring vehicles, a tube-shaped trajectory is assumed around the trajectory of leader, where the tube radius is the radius of the reachable set of leaders. This way, the leader is put in a protection zone where the followers cannot enter. The radius of tube is a function of maneuverability and communication delay; the smaller the communication delays the thinner the tube. Note that at the end the desired relative distance in the formation is chosen to be larger than the tube radius. This is the main distinction between this work and the cooperative or noncooperative approaches aiming at online estimation of the reachable set. In contrast, here the tube is calculated offline and is used for the online purposes.The idea of tube MPC was first used to calculate a robust bound on the states for uncertain systems [8, 9].To avoid conservative reachability sets (thick tubes) the maneuverability of each vehicle is restricted, and then the reachable set of each vehicle is calculated; in fact, the leader imposes an input constraint to its optimization problem, that is, at any time instant the computed input trajectories of leader do not deviate too far from the previous one.Note that, although restricting the maneuverability can lead to less conservative results, it can be restrictive to application where an agile vehicle is needed. Hence, for applications where, for example, slow moving ground vehicles are used such as automated highway systems [20] or mobile robots [21, 22], this approach can be beneficial. In such application since aggressive maneuvers are not required, restricting the maneuverability is not prohibitive, and hence the proposed approach is well suited.


#### 3.3.1. Tube Formulation and Calculation

This section presents a numerical method for offline calculation of the tube for subsystems with generic dynamics. Any other computational or analytical reachability set calculation method may be used for this purpose. The main advantage of the presented tube calculation algorithm is that it can be computed offline and does not impose significant online computation load. Besides, the available analytical bounds are usually too conservative and are not in the desired format for tube analysis (often a bound on the norm of states is available).Figure4 shows the tube ℍ around a nominal trajectoryxi(·,u0). The tube ℍ is formulated as follows (see also [23]):(14)Hki={(p,x̂i)∈[0:N]×Rn∣|x̂i(p,u)-xi(p,u0)|<αki,u∈U},
where |·| represents the component-wise absolute value of vector and αki denotes the radius of tube ℍ around the trajectory of vehicle i at time step k.Figure 4
A tube around a nominal trajectory, of vehiclei.The following theorem represents a method for calculating the tube for a generic class of systems. Roughly speaking, tube is a generalization of reachability set; the reachability set is normally calculated around an initial state; however, tube is calculated around a trajectory of state vector. In other words, the deviation from some nominal trajectory over a given time is called tube.Theorem 1.
Assume that at time stepk the d step delayed trajectory of leader j(i.e.,xk-dj(·)) is available to vehicle i. If
(15)|ukj(p)-uk-dj(p+d)|≤βj,p=0,1,2,….,N-d,
then the trajectory of vehicle j at time step k belongs to the tube around xk-dj(·); the tube is formulated as:
(16)Hkj,i={(p,x̂k-dj)∈[0:N-d]×Rn∣|x̂k-dj(p)-xk-dj(p+d)|<αkj,i(p)},
where ℍkj,i represents the tube around the trajectory of vehicle j, calculated by vehicle i at time step k. Also, αkj,i denotes the tube radius and is the solution of the following maximization problem.Problem 2.
Givenβj, calculate for all p=0,1,2,…,N(17)αkj,i(p)=Max⁡{x̂k-dj(⋅),ûk-dj(⋅),xk-dj(⋅),uk-dj(⋅)}[|∑p=0N-d[f(x̂k-dj(p),ûk-dj(p))-f(xk-dj(p),uk-dj(p))]∑p=0N-d[f(x̂k-dj(p),ûk-dj(p))|]subjecttox̂k-dj(p+1)=f(x̂k-dj(p),ûk-dj(p)),x̂k-dj(tk-d)=xj(tk-d)∈X,xk-dj(p+1)=f(xk-dj(p),uk-dj(p)),xk-dj(tk-d)=xj(tk-d)∈X,x̂k-dj(p)∈X;xk-dj(p)∈X,ûk-dj(p)∈U;uk-dj(p)∈U,|ûk-dj(p)-uk-dj(p)|≤βj.Proof.
At time stepk vehicle j uses the input trajectory ukj(·) which yields the state trajectory xkj(·), then the solution of the differential equation (8) is calculated as:
(18)xkj(p)=xj(k)+∑s=0p-1f(xkj(s),ukj(s))p=0,1,…,N.
But if vehicle j uses the assumed input ûkj(·), then the trajectory will be as follows:
(19)x̂kj(p)=xj(k)+∑s=0p-1f(x̂kj(s),ûkj(s))p=0,1,…,N.
Subtracting (18) from (19) yields
(20)x̂kj(p)-xkj(p)=∑s=0p-1[f(xkj(s),ukj(s))-f(x̂kj(s),ûkj(s))]p=0,1,…,N.By findingαkj,i the tube ℍkj,i is determined. αkj,i is the upper bound on|x̂kj(p)-xkj(p)| and then is calculated by solving the following maximization problem.Problem 3.
Givenukj(·), xkj(·) and βj calculate for all p=0,1,2,…,N(21)αkj,i(p)=Max⁡{x̂kj(⋅),ûkj(⋅)}[|∑s=0p-1[f(xkj(s),ukj(s))-f(x̂kj(s),ûkj(s))]|]subjecttox̂kj(p+1)=f(x̂kj(p),ûkj(p)),x̂kj(0)=xj(0)x̂kj(p)∈Xûkj(p)∈U|ûkj(p)-ukj(p)|≤βj.In optimization Problem3 a nominal trajectory xkj(·) is given as input. In other words the optimal value depends on any nominal trajectory. On the other hand, at any time step DMPC generates a new trajectory which is served as nominal trajectory in Problem 3. Hence, Problem 3 should be modified to be independent of any nominal trajectory and be applicable for a general trajectory xkj(·). Hence, considering xkj(·) and ukj(·) as new decision variables in the optimization Problem 3 and shifting the time from k to k-d will lead to Problem 2. This way, the tube can be computed offline and used for online applications, and no online computation is required.


#### 3.3.2. Tube Calculation Algorithm

The application of Theorem1 allows calculating the tube ℍkj,i around the trajectory of each neighboring vehicle. Assume that the control input at each sample time for vehicle j is bounded as follows:(22)|ukj(p)-uk-1j(p+1)|≤μ,p=0,1,…,N-2,
where μ is a vector with appropriate dimension and is called the maneuverability vector. It allows restricting the maneuverability of each vehicle during the time segments when the actual predicted trajectory of vehicle may not be available to followers. The neighboring vehicles by considering such restrictions can compute a bound on the trajectories. Then, if at any time step k vehicle i receives the information from leader j with d steps time delay, that is, xk-dj(·), then the results of Theorem 1 are applicable by finding βj(μ,d). To find βj(μ,d) the input constraint (22) can be used sequentially as follows (the superscript j is dropped temporarily):(23)-μ≤uk(p)-uk-1(p+1)≤μ,-μ≤uk-1(p+1)-uk-2(p+2)≤μ,⋮-μ≤uk-d+1(p+d-1)-uk-d(p+d)≤μ,⋮-d⋅μ≤uk(p)-uk-d(p+d)≤d⋅μ,p=0,1,2,…,N-d.
Hence, (24)βj=d⋅μ,p=0,1,2,3,…,N-d.
Therefore, we have(25)βj(p,μ,d)={0,p=0,μ,p=1,2μ,p=2,⋮⋮(d-1)μ,p=d-1,dμ,p=d,d+1,…,N-d.Thenαkj,i, the radius of tube ℍkj,i, is calculated from Problem 2 after calculating βj from (25). The output of Problem 2 is the trajectory of vector αkj,i(·) and will be used in the online DMPC algorithm.The main benefit of using this procedure for tube calculation is that calculation ofαkj,i does not impose any online computation load as it can be computed offline. The only parameter which may be unknown prior to mission is the time delay d. Hence, the tube can be computed for different delays, and the results are given to the DMPC controller as some tabulated data, to be used in online applications. In this way no online computation is imposed.


#### 3.3.3. Nonconvexity Avoidance

Using a tube instead of a trajectory in the cost function (12) can lead to nonconvexity for the optimization problem due to the nonconvex nature of the tube. Thus, in order to avoid the nonconvexity, in the cost function (12), xk-dj(p) is not modified (or replaced by tube ℍkj,i), instead the desired relative position ri,j(p) will be modified as follows:(26)ri,j(p)⟵ri,j(p)+sign⁡(ri,j(p))⋅αj,i(p),
where αkj,i is the tube radius at time step k and is calculated from Problem 2. In fact, the margin αkj,i(p)≥0 is added to the desired distance to ensure the safety. Since ri,j(·) is the relative position vector, αkj,i is multiplied by the diagonal matrix sign(ri,j(·)) to ensure that adding αkj,i increases the magnitude of ri,j(·); in fact ri,j(·) is preserved, and extra margin is added.


### 3.4. Delay-Compensated DMPC Problem

The delay-compensated DMPC (DC-DMPC) problem𝒫DCi(k) is defined below at time step k for any ith vehicle. The outputs of this decentralized optimization problem are (1) the input and (2) the state trajectory of the local vehicle over the prediction horizon and (3) the trajectory of neighboring vehicles during the tail of the cost function.Problem 4.
DC-DMPC Problem𝒫DCi(k). Given ΓDi(tk) calculate
(27)JDCi(ΓDi(k))=Min⁡{xki(⋅),uki(⋅),uk-i(N-d:N)}JDCi×(ΓDi(k),uki(⋅),xk-i(N-d:N),uk-i(N-d:N))
subject to (i)
forp=0,1,2,…,N-1: (9a)–(9c)(ii)
and forp=N-d,…,N and (i,j)∈𝔼:(28a)xkj,i(p+1)=f(xkj,i(p),ukj,i(p));xkj,i(N-d)=xk-dj(N)(28b)xkj,i(p)∈Xj,ukj,i(p)∈Uj(28c)xkj,i(N)∈Xfj,(iii)
and forp=0,1,2,…,N-2:
(28d)|uki(p)-uk-1i(p+1)|≤μ,where constraints (9a)–(9c) are the same as in the delay-free DMPC problem 𝒫i(tk) and correspond to the trajectory for calculating the delayed cost function JDi. Constraints (28a) and (28b) correspond to the tail cost function JTaili (13). Constraint (28c) is the terminal constraint and is the same as (9c) in 𝒫i(tk). Moreover, constraint (28d) is added for safety guarantee purpose, where |·| represents the component-wise absolute value of vector and μ is a vector with appropriate dimension and called the maneuverabilityvector. Constraint (28d) is called maneuverability constraints (such constraint is also known as compatibility constraints in similar literatures, [24, 25]). It allows restricting the maneuverability of each vehicle and hence calculating the tube as explained in Theorem 1.  Roughly speaking, constraints (28a)–(28c) are added for cooperation performance improvement, and constraint (28d) is added for safety purpose.Remark 2.
Expressing equations (28d) in the norm form instead of component-wise absolute value leads to more conservative results in practice.


### 3.5. DC-DMPC Algorithm

Algorithm2 is presented for the online implementation of the proposed DC-DMPC problem 𝒫DCi(k). The algorithm is formulated for the ith vehicle; in fact, all vehicles run this algorithm during the mission simultaneously.Algorithm 2:DC-DMPC.
Givenμ, 𝔼 and initial condition of vehicle i, do:(1)k←0.(2) Measurexi(k), calculate delay from leader and update the delayed information  vector of (10).(3)Calculate the tube of all leaders:For  ∀j∈𝕍 where  (i,j)∈𝔼(i)Calculateβj(·,μ,d)from (25).(ii)Calculateαkj,i(·)from the data provided by offline solution of  Problem2.(iii)Updateri,j(·)←ri,j(·)+sign(ri,j(·))·αkj,i(·)and updateri,jin the cost function(12).END(4) Solve𝒫DCi(k) and calculate the control action uki(·) and xki(·).(5) Send the state trajectoryxki(·) to the followers where(j,i)∈𝔼.(6) Apply the control actionuki(0) to individual vehicle i.(7) Receivexk-dj(·) from leaders where(i,j)∈𝔼.(8)k←k+1. Goto step  2.Initialization
Fork=0 to k=d-1 at steps 2, 3, and 4 assume that Nli=0. For k=0 to k=d-2 at step 7 assume Nli=0 (because no information from leader(s) is available).This algorithm is a modified version of Algorithm1 and handles the large communication delays; it also provides the safety guarantee by executing the step 3 using the tube DMPC approach.Remark 3.
In step  2 of Algorithm2, to measure the time delays, it is assumed that all the vehicles are equipped with synchronous clocks. Then at each sampling time, each vehicle, in addition to its predicted trajectory, broadcasts the time it is calculated the trajectory. Hence, the knowledge on the amount of delay is not required a priori.


## 3.1. Delayed Cost Function and Information Set

Assume at time stepk the vehicle i receives the information from neighbor j with time-delay d, where d∈ℕ and d≥1, see Figure 2. Then, the term large communication delays denotes the time delays which are larger than the sampling period, that is, d>1.Figure 2
Delayed intervehicle communication between two neighboring vehicles.When a vehicle receives the delayed information from neighbors the information set is updated as follows (compare with (5)):(10)ΓDi(k)={xi(k),xk-d-i(⋅)}.
The information setΓDi(k) represents updated information available to the ith vehicle at time step k. It implies at time step k that each vehicle i has access to its own delay-free information and delayed information from neighbors. Then, the decentralized delayed cost function for all i∈𝕍 at time step k is defined as follows (compare with (6)):(11)JDi(ΓDi,uki(⋅))=∑p=0N-1(‖xki(p)-xT,i‖Q2+‖uki(p)‖R2)+‖xki(N)-xT,i‖P2+∑j∣(i,j)∈E(∑p=0N-d‖xki(p)-xk-dj(p)-ri,j‖S2).The communication delay affects the cooperation cost for the periods when the leader’s trajectory is not available. In fact, for the tail of the cost function during[N-d:N] the leader’s trajectory is not available due to communication delay to calculate the cost function. More precisely, assume at time step k the vehicle i receives the information from neighbor j with time-delay d, where d∈ℕ and d≥1. Then, the trajectory of neighbor j for only the time interval [k-d,k+N-d] is available to vehicle i, while according to cost function of (6) vehicle i needs the trajectory of neighbor j for the entire interval [k,k+N]. Hence for the portion [k+N-d,k+N] the trajectory of j is not available due to the delay (see Figure 3). When the time delay is small this lack of information is not important, but for large communication delays the tail of cost function during [k+N-d,k+N] becomes large and as shown by simulations in Section 4 it can lead to poor performance and unsafe behaviors (see also [13, 17]). One remedy to this problem is proposed here by estimating the tail of the cost function by including extra decision variables in the cost function.Figure 3
Tail of the leader’s trajectory in the presence of large communication delayd.


## 3.2. Delay-Compensated Cost Function

The main idea with the proposed cost function is that it replaces the missing information due to communication loss, with the decision variables. Then, the decision variables are used to approximate the missing information. More specifically, communication losses prevent access to updated leader’s trajectory, and then the available delayed neighbor’s trajectory is utilized. However, the delayed leader’s trajectories do not cover the entire time slot required by follower to calculate its cost function; hence, a delay-compensated cost function is proposed as follows (for theith vehicle in the team at time step k):(12)JDCi(ΓDi(k),uki(⋅),xk-i(N-d:N),uk-i(N-d:N))=JDi(ΓDi(k),u⋅∣ki)+JTaili(xk-i(N-d:N),uk-i(N-d:N)),
where JDi is calculated from (11) and(13)JTaili(xk-i(N-d:N),uk-i(N-d:N))=∑j∣(i,j)∈E[∑p=N-d+1N(‖xki(p)-xkj,i(p)-ri,j‖S2+‖xkj,i(p)-xT,j‖Q2+‖ukj,i(p)‖R2)+‖xkj,i(N)-xT,j‖P2∑p=N-d+1N].
The subscript “D” stands for “Delay”. The delay-compensated decentralized cost function JDCi includes two main parts.(1)
The delayed costJDi which includes the cost of local vehicle i and the cost of neighboring vehicles calculated from the delayed information. Literally, this part is calculated using the information available from communication (and measurement sensors for local vehicle).(2)
The tail costJTaili (13) which calculates the cost associated with the neighbors over the tail of the cost function during [N-d+1:N] where information is not available due to the communication loss/delay.  In fact, the added extra decision variables are used to calculate this part.Although it is assumed that there is model uncertainty and communication noise, the lack of updated information due to communication loss will impose an uncertainty on the updated leader’s trajectory, because, in the event of communication loss, the followers will utilize the leader’s delayed trajectory, which may differ from the updated unavailable trajectories. Such uncertainty which is derived from the mismatch between updated and delayed trajectories may lead to poor performance of the decentralized DMPC.


## 3.3. Safety Guarantee Using Tube DMPC

For the particular case of formation control, consider a group of vehicles that are required (1) to keep certain relative positions (local objective) and (2) to visit a set of waypoints (global objective). In general, incorporating the collision avoidance constraint into the optimization problem of DMPC is not trivial because of the nonconvexity nature of the distance constraint. To address this problem, in [18] a hybrid rule-based extension of the decentralized model predictive control (DMPC) is proposed to avoid possible collisions. Also, in [19] a mixed integer linear programming (MLIP) approach is utilized to handle the nonconvex collision avoidance constraint using a DMPC architecture.The problem becomes even more serious when the large communication delays exist because communication delay leads to a lack of updated information on the trajectory of neighboring vehicles and this can make the formation unsafe and put the team in jeopardy. Hence, a discussion on the collision avoidance is required.In practice, normally the desired distance in formation control is chosen large enough to ensure safety against overshoots and uncertainties. In this paper another approach which is applicable to both delay-free and delayed situations is proposed. In this approach, instead of using an assumed trajectory for neighboring vehicles, a tube-shaped trajectory is assumed around the trajectory of leader, where the tube radius is the radius of the reachable set of leaders. This way, the leader is put in a protection zone where the followers cannot enter. The radius of tube is a function of maneuverability and communication delay; the smaller the communication delays the thinner the tube. Note that at the end the desired relative distance in the formation is chosen to be larger than the tube radius. This is the main distinction between this work and the cooperative or noncooperative approaches aiming at online estimation of the reachable set. In contrast, here the tube is calculated offline and is used for the online purposes.The idea of tube MPC was first used to calculate a robust bound on the states for uncertain systems [8, 9].To avoid conservative reachability sets (thick tubes) the maneuverability of each vehicle is restricted, and then the reachable set of each vehicle is calculated; in fact, the leader imposes an input constraint to its optimization problem, that is, at any time instant the computed input trajectories of leader do not deviate too far from the previous one.Note that, although restricting the maneuverability can lead to less conservative results, it can be restrictive to application where an agile vehicle is needed. Hence, for applications where, for example, slow moving ground vehicles are used such as automated highway systems [20] or mobile robots [21, 22], this approach can be beneficial. In such application since aggressive maneuvers are not required, restricting the maneuverability is not prohibitive, and hence the proposed approach is well suited.


### 3.3.1. Tube Formulation and Calculation

This section presents a numerical method for offline calculation of the tube for subsystems with generic dynamics. Any other computational or analytical reachability set calculation method may be used for this purpose. The main advantage of the presented tube calculation algorithm is that it can be computed offline and does not impose significant online computation load. Besides, the available analytical bounds are usually too conservative and are not in the desired format for tube analysis (often a bound on the norm of states is available).Figure4 shows the tube ℍ around a nominal trajectoryxi(·,u0). The tube ℍ is formulated as follows (see also [23]):(14)Hki={(p,x̂i)∈[0:N]×Rn∣|x̂i(p,u)-xi(p,u0)|<αki,u∈U},
where |·| represents the component-wise absolute value of vector and αki denotes the radius of tube ℍ around the trajectory of vehicle i at time step k.Figure 4
A tube around a nominal trajectory, of vehiclei.The following theorem represents a method for calculating the tube for a generic class of systems. Roughly speaking, tube is a generalization of reachability set; the reachability set is normally calculated around an initial state; however, tube is calculated around a trajectory of state vector. In other words, the deviation from some nominal trajectory over a given time is called tube.Theorem 1.
Assume that at time stepk the d step delayed trajectory of leader j(i.e.,xk-dj(·)) is available to vehicle i. If
(15)|ukj(p)-uk-dj(p+d)|≤βj,p=0,1,2,….,N-d,
then the trajectory of vehicle j at time step k belongs to the tube around xk-dj(·); the tube is formulated as:
(16)Hkj,i={(p,x̂k-dj)∈[0:N-d]×Rn∣|x̂k-dj(p)-xk-dj(p+d)|<αkj,i(p)},
where ℍkj,i represents the tube around the trajectory of vehicle j, calculated by vehicle i at time step k. Also, αkj,i denotes the tube radius and is the solution of the following maximization problem.Problem 2.
Givenβj, calculate for all p=0,1,2,…,N(17)αkj,i(p)=Max⁡{x̂k-dj(⋅),ûk-dj(⋅),xk-dj(⋅),uk-dj(⋅)}[|∑p=0N-d[f(x̂k-dj(p),ûk-dj(p))-f(xk-dj(p),uk-dj(p))]∑p=0N-d[f(x̂k-dj(p),ûk-dj(p))|]subjecttox̂k-dj(p+1)=f(x̂k-dj(p),ûk-dj(p)),x̂k-dj(tk-d)=xj(tk-d)∈X,xk-dj(p+1)=f(xk-dj(p),uk-dj(p)),xk-dj(tk-d)=xj(tk-d)∈X,x̂k-dj(p)∈X;xk-dj(p)∈X,ûk-dj(p)∈U;uk-dj(p)∈U,|ûk-dj(p)-uk-dj(p)|≤βj.Proof.
At time stepk vehicle j uses the input trajectory ukj(·) which yields the state trajectory xkj(·), then the solution of the differential equation (8) is calculated as:
(18)xkj(p)=xj(k)+∑s=0p-1f(xkj(s),ukj(s))p=0,1,…,N.
But if vehicle j uses the assumed input ûkj(·), then the trajectory will be as follows:
(19)x̂kj(p)=xj(k)+∑s=0p-1f(x̂kj(s),ûkj(s))p=0,1,…,N.
Subtracting (18) from (19) yields
(20)x̂kj(p)-xkj(p)=∑s=0p-1[f(xkj(s),ukj(s))-f(x̂kj(s),ûkj(s))]p=0,1,…,N.By findingαkj,i the tube ℍkj,i is determined. αkj,i is the upper bound on|x̂kj(p)-xkj(p)| and then is calculated by solving the following maximization problem.Problem 3.
Givenukj(·), xkj(·) and βj calculate for all p=0,1,2,…,N(21)αkj,i(p)=Max⁡{x̂kj(⋅),ûkj(⋅)}[|∑s=0p-1[f(xkj(s),ukj(s))-f(x̂kj(s),ûkj(s))]|]subjecttox̂kj(p+1)=f(x̂kj(p),ûkj(p)),x̂kj(0)=xj(0)x̂kj(p)∈Xûkj(p)∈U|ûkj(p)-ukj(p)|≤βj.In optimization Problem3 a nominal trajectory xkj(·) is given as input. In other words the optimal value depends on any nominal trajectory. On the other hand, at any time step DMPC generates a new trajectory which is served as nominal trajectory in Problem 3. Hence, Problem 3 should be modified to be independent of any nominal trajectory and be applicable for a general trajectory xkj(·). Hence, considering xkj(·) and ukj(·) as new decision variables in the optimization Problem 3 and shifting the time from k to k-d will lead to Problem 2. This way, the tube can be computed offline and used for online applications, and no online computation is required.


### 3.3.2. Tube Calculation Algorithm

The application of Theorem1 allows calculating the tube ℍkj,i around the trajectory of each neighboring vehicle. Assume that the control input at each sample time for vehicle j is bounded as follows:(22)|ukj(p)-uk-1j(p+1)|≤μ,p=0,1,…,N-2,
where μ is a vector with appropriate dimension and is called the maneuverability vector. It allows restricting the maneuverability of each vehicle during the time segments when the actual predicted trajectory of vehicle may not be available to followers. The neighboring vehicles by considering such restrictions can compute a bound on the trajectories. Then, if at any time step k vehicle i receives the information from leader j with d steps time delay, that is, xk-dj(·), then the results of Theorem 1 are applicable by finding βj(μ,d). To find βj(μ,d) the input constraint (22) can be used sequentially as follows (the superscript j is dropped temporarily):(23)-μ≤uk(p)-uk-1(p+1)≤μ,-μ≤uk-1(p+1)-uk-2(p+2)≤μ,⋮-μ≤uk-d+1(p+d-1)-uk-d(p+d)≤μ,⋮-d⋅μ≤uk(p)-uk-d(p+d)≤d⋅μ,p=0,1,2,…,N-d.
Hence, (24)βj=d⋅μ,p=0,1,2,3,…,N-d.
Therefore, we have(25)βj(p,μ,d)={0,p=0,μ,p=1,2μ,p=2,⋮⋮(d-1)μ,p=d-1,dμ,p=d,d+1,…,N-d.Thenαkj,i, the radius of tube ℍkj,i, is calculated from Problem 2 after calculating βj from (25). The output of Problem 2 is the trajectory of vector αkj,i(·) and will be used in the online DMPC algorithm.The main benefit of using this procedure for tube calculation is that calculation ofαkj,i does not impose any online computation load as it can be computed offline. The only parameter which may be unknown prior to mission is the time delay d. Hence, the tube can be computed for different delays, and the results are given to the DMPC controller as some tabulated data, to be used in online applications. In this way no online computation is imposed.


### 3.3.3. Nonconvexity Avoidance

Using a tube instead of a trajectory in the cost function (12) can lead to nonconvexity for the optimization problem due to the nonconvex nature of the tube. Thus, in order to avoid the nonconvexity, in the cost function (12), xk-dj(p) is not modified (or replaced by tube ℍkj,i), instead the desired relative position ri,j(p) will be modified as follows:(26)ri,j(p)⟵ri,j(p)+sign⁡(ri,j(p))⋅αj,i(p),
where αkj,i is the tube radius at time step k and is calculated from Problem 2. In fact, the margin αkj,i(p)≥0 is added to the desired distance to ensure the safety. Since ri,j(·) is the relative position vector, αkj,i is multiplied by the diagonal matrix sign(ri,j(·)) to ensure that adding αkj,i increases the magnitude of ri,j(·); in fact ri,j(·) is preserved, and extra margin is added.


## 3.3.1. Tube Formulation and Calculation

This section presents a numerical method for offline calculation of the tube for subsystems with generic dynamics. Any other computational or analytical reachability set calculation method may be used for this purpose. The main advantage of the presented tube calculation algorithm is that it can be computed offline and does not impose significant online computation load. Besides, the available analytical bounds are usually too conservative and are not in the desired format for tube analysis (often a bound on the norm of states is available).Figure4 shows the tube ℍ around a nominal trajectoryxi(·,u0). The tube ℍ is formulated as follows (see also [23]):(14)Hki={(p,x̂i)∈[0:N]×Rn∣|x̂i(p,u)-xi(p,u0)|<αki,u∈U},
where |·| represents the component-wise absolute value of vector and αki denotes the radius of tube ℍ around the trajectory of vehicle i at time step k.Figure 4
A tube around a nominal trajectory, of vehiclei.The following theorem represents a method for calculating the tube for a generic class of systems. Roughly speaking, tube is a generalization of reachability set; the reachability set is normally calculated around an initial state; however, tube is calculated around a trajectory of state vector. In other words, the deviation from some nominal trajectory over a given time is called tube.Theorem 1.
Assume that at time stepk the d step delayed trajectory of leader j(i.e.,xk-dj(·)) is available to vehicle i. If
(15)|ukj(p)-uk-dj(p+d)|≤βj,p=0,1,2,….,N-d,
then the trajectory of vehicle j at time step k belongs to the tube around xk-dj(·); the tube is formulated as:
(16)Hkj,i={(p,x̂k-dj)∈[0:N-d]×Rn∣|x̂k-dj(p)-xk-dj(p+d)|<αkj,i(p)},
where ℍkj,i represents the tube around the trajectory of vehicle j, calculated by vehicle i at time step k. Also, αkj,i denotes the tube radius and is the solution of the following maximization problem.Problem 2.
Givenβj, calculate for all p=0,1,2,…,N(17)αkj,i(p)=Max⁡{x̂k-dj(⋅),ûk-dj(⋅),xk-dj(⋅),uk-dj(⋅)}[|∑p=0N-d[f(x̂k-dj(p),ûk-dj(p))-f(xk-dj(p),uk-dj(p))]∑p=0N-d[f(x̂k-dj(p),ûk-dj(p))|]subjecttox̂k-dj(p+1)=f(x̂k-dj(p),ûk-dj(p)),x̂k-dj(tk-d)=xj(tk-d)∈X,xk-dj(p+1)=f(xk-dj(p),uk-dj(p)),xk-dj(tk-d)=xj(tk-d)∈X,x̂k-dj(p)∈X;xk-dj(p)∈X,ûk-dj(p)∈U;uk-dj(p)∈U,|ûk-dj(p)-uk-dj(p)|≤βj.Proof.
At time stepk vehicle j uses the input trajectory ukj(·) which yields the state trajectory xkj(·), then the solution of the differential equation (8) is calculated as:
(18)xkj(p)=xj(k)+∑s=0p-1f(xkj(s),ukj(s))p=0,1,…,N.
But if vehicle j uses the assumed input ûkj(·), then the trajectory will be as follows:
(19)x̂kj(p)=xj(k)+∑s=0p-1f(x̂kj(s),ûkj(s))p=0,1,…,N.
Subtracting (18) from (19) yields
(20)x̂kj(p)-xkj(p)=∑s=0p-1[f(xkj(s),ukj(s))-f(x̂kj(s),ûkj(s))]p=0,1,…,N.By findingαkj,i the tube ℍkj,i is determined. αkj,i is the upper bound on|x̂kj(p)-xkj(p)| and then is calculated by solving the following maximization problem.Problem 3.
Givenukj(·), xkj(·) and βj calculate for all p=0,1,2,…,N(21)αkj,i(p)=Max⁡{x̂kj(⋅),ûkj(⋅)}[|∑s=0p-1[f(xkj(s),ukj(s))-f(x̂kj(s),ûkj(s))]|]subjecttox̂kj(p+1)=f(x̂kj(p),ûkj(p)),x̂kj(0)=xj(0)x̂kj(p)∈Xûkj(p)∈U|ûkj(p)-ukj(p)|≤βj.In optimization Problem3 a nominal trajectory xkj(·) is given as input. In other words the optimal value depends on any nominal trajectory. On the other hand, at any time step DMPC generates a new trajectory which is served as nominal trajectory in Problem 3. Hence, Problem 3 should be modified to be independent of any nominal trajectory and be applicable for a general trajectory xkj(·). Hence, considering xkj(·) and ukj(·) as new decision variables in the optimization Problem 3 and shifting the time from k to k-d will lead to Problem 2. This way, the tube can be computed offline and used for online applications, and no online computation is required.


## 3.3.2. Tube Calculation Algorithm

The application of Theorem1 allows calculating the tube ℍkj,i around the trajectory of each neighboring vehicle. Assume that the control input at each sample time for vehicle j is bounded as follows:(22)|ukj(p)-uk-1j(p+1)|≤μ,p=0,1,…,N-2,
where μ is a vector with appropriate dimension and is called the maneuverability vector. It allows restricting the maneuverability of each vehicle during the time segments when the actual predicted trajectory of vehicle may not be available to followers. The neighboring vehicles by considering such restrictions can compute a bound on the trajectories. Then, if at any time step k vehicle i receives the information from leader j with d steps time delay, that is, xk-dj(·), then the results of Theorem 1 are applicable by finding βj(μ,d). To find βj(μ,d) the input constraint (22) can be used sequentially as follows (the superscript j is dropped temporarily):(23)-μ≤uk(p)-uk-1(p+1)≤μ,-μ≤uk-1(p+1)-uk-2(p+2)≤μ,⋮-μ≤uk-d+1(p+d-1)-uk-d(p+d)≤μ,⋮-d⋅μ≤uk(p)-uk-d(p+d)≤d⋅μ,p=0,1,2,…,N-d.
Hence, (24)βj=d⋅μ,p=0,1,2,3,…,N-d.
Therefore, we have(25)βj(p,μ,d)={0,p=0,μ,p=1,2μ,p=2,⋮⋮(d-1)μ,p=d-1,dμ,p=d,d+1,…,N-d.Thenαkj,i, the radius of tube ℍkj,i, is calculated from Problem 2 after calculating βj from (25). The output of Problem 2 is the trajectory of vector αkj,i(·) and will be used in the online DMPC algorithm.The main benefit of using this procedure for tube calculation is that calculation ofαkj,i does not impose any online computation load as it can be computed offline. The only parameter which may be unknown prior to mission is the time delay d. Hence, the tube can be computed for different delays, and the results are given to the DMPC controller as some tabulated data, to be used in online applications. In this way no online computation is imposed.


## 3.3.3. Nonconvexity Avoidance

Using a tube instead of a trajectory in the cost function (12) can lead to nonconvexity for the optimization problem due to the nonconvex nature of the tube. Thus, in order to avoid the nonconvexity, in the cost function (12), xk-dj(p) is not modified (or replaced by tube ℍkj,i), instead the desired relative position ri,j(p) will be modified as follows:(26)ri,j(p)⟵ri,j(p)+sign⁡(ri,j(p))⋅αj,i(p),
where αkj,i is the tube radius at time step k and is calculated from Problem 2. In fact, the margin αkj,i(p)≥0 is added to the desired distance to ensure the safety. Since ri,j(·) is the relative position vector, αkj,i is multiplied by the diagonal matrix sign(ri,j(·)) to ensure that adding αkj,i increases the magnitude of ri,j(·); in fact ri,j(·) is preserved, and extra margin is added.


## 3.4. Delay-Compensated DMPC Problem

The delay-compensated DMPC (DC-DMPC) problem𝒫DCi(k) is defined below at time step k for any ith vehicle. The outputs of this decentralized optimization problem are (1) the input and (2) the state trajectory of the local vehicle over the prediction horizon and (3) the trajectory of neighboring vehicles during the tail of the cost function.Problem 4.
DC-DMPC Problem𝒫DCi(k). Given ΓDi(tk) calculate
(27)JDCi(ΓDi(k))=Min⁡{xki(⋅),uki(⋅),uk-i(N-d:N)}JDCi×(ΓDi(k),uki(⋅),xk-i(N-d:N),uk-i(N-d:N))
subject to (i)
forp=0,1,2,…,N-1: (9a)–(9c)(ii)
and forp=N-d,…,N and (i,j)∈𝔼:(28a)xkj,i(p+1)=f(xkj,i(p),ukj,i(p));xkj,i(N-d)=xk-dj(N)(28b)xkj,i(p)∈Xj,ukj,i(p)∈Uj(28c)xkj,i(N)∈Xfj,(iii)
and forp=0,1,2,…,N-2:
(28d)|uki(p)-uk-1i(p+1)|≤μ,where constraints (9a)–(9c) are the same as in the delay-free DMPC problem 𝒫i(tk) and correspond to the trajectory for calculating the delayed cost function JDi. Constraints (28a) and (28b) correspond to the tail cost function JTaili (13). Constraint (28c) is the terminal constraint and is the same as (9c) in 𝒫i(tk). Moreover, constraint (28d) is added for safety guarantee purpose, where |·| represents the component-wise absolute value of vector and μ is a vector with appropriate dimension and called the maneuverabilityvector. Constraint (28d) is called maneuverability constraints (such constraint is also known as compatibility constraints in similar literatures, [24, 25]). It allows restricting the maneuverability of each vehicle and hence calculating the tube as explained in Theorem 1.  Roughly speaking, constraints (28a)–(28c) are added for cooperation performance improvement, and constraint (28d) is added for safety purpose.Remark 2.
Expressing equations (28d) in the norm form instead of component-wise absolute value leads to more conservative results in practice.


## 3.5. DC-DMPC Algorithm

Algorithm2 is presented for the online implementation of the proposed DC-DMPC problem 𝒫DCi(k). The algorithm is formulated for the ith vehicle; in fact, all vehicles run this algorithm during the mission simultaneously.Algorithm 2:DC-DMPC.
Givenμ, 𝔼 and initial condition of vehicle i, do:(1)k←0.(2) Measurexi(k), calculate delay from leader and update the delayed information  vector of (10).(3)Calculate the tube of all leaders:For  ∀j∈𝕍 where  (i,j)∈𝔼(i)Calculateβj(·,μ,d)from (25).(ii)Calculateαkj,i(·)from the data provided by offline solution of  Problem2.(iii)Updateri,j(·)←ri,j(·)+sign(ri,j(·))·αkj,i(·)and updateri,jin the cost function(12).END(4) Solve𝒫DCi(k) and calculate the control action uki(·) and xki(·).(5) Send the state trajectoryxki(·) to the followers where(j,i)∈𝔼.(6) Apply the control actionuki(0) to individual vehicle i.(7) Receivexk-dj(·) from leaders where(i,j)∈𝔼.(8)k←k+1. Goto step  2.Initialization
Fork=0 to k=d-1 at steps 2, 3, and 4 assume that Nli=0. For k=0 to k=d-2 at step 7 assume Nli=0 (because no information from leader(s) is available).This algorithm is a modified version of Algorithm1 and handles the large communication delays; it also provides the safety guarantee by executing the step 3 using the tube DMPC approach.Remark 3.
In step  2 of Algorithm2, to measure the time delays, it is assumed that all the vehicles are equipped with synchronous clocks. Then at each sampling time, each vehicle, in addition to its predicted trajectory, broadcasts the time it is calculated the trajectory. Hence, the knowledge on the amount of delay is not required a priori.


## 4. Simulation Results

In this section, the proposed approach is tested on the formation problem of a fleet of unmanned vehicles with the following 2DOF dynamics. This dynamics can capture the motion of a mini-hovercraft equipped with two sets of thrusters to control the side and forward motions; also, a small damping term is added as the typical resistance of water to hovercraft motion is small:(29)ẋ1=x2,ẋ2=-0.1x2+u1,ẋ3=x4,ẋ4=-0.1x4+u2,
where x1 and x2 represent the components of position vector in x-y coordinate and x3 and x4 are their corresponding velocity components. The input vector is given by u=[u1,u2]. This dynamics is discretized by sampling time h=0.1sec. The MPC problem is solved using optimization toolbox of MATLAB. When Algorithm 1 is used a set of 2N decision variables are used for each vehicle to model the control inputs (because each vehicle has only two control inputs). Once Algorithm 2 is used, two extra sets of decision variables are used; 2N+2d decision variables are used. It means the computation grows with communication delay.In the first simulation example, it is desired to examine the effect of the tail cost added to the cost function. The simulation was run for two cases.(1)
Using the cost functionwithout the tail cost. In this case the control input is set to u=0 for the tail of the cost function.  The extra decision variables for tail cost estimation are not included in the optimization problem.(2)
Using the cost functionwith the tail cost. In this case the tail of the cost function (12) is estimated using the extra decision variables in the optimization problem 𝒫DCi(k).The matrix penalties in the cost function are chosen as follows:Q=I (where I is identity matrix), and R=0.10I  then
(30)P=[0.86341.4470.0000.0001.44712.8000.0000.0000.00000.0000.8631.4470.00000.0001.4472.800]
andS=20I. The final penalty matrixP is calculated from the Lyapunov equation [15].  The optimization horizon is chosen to beN=10. In all cases no disturbances, sensor noise, or model uncertainty is considered in the simulations in order to focus on the effect of the communication delay.A triangular leader-follower formation of three vehicles is first considered, where the moving vehicles are controlled to form an isosceles triangle with edges of 10, 7.02, and 7.02 m. The actual cooperation cost is chosen as the cooperation performance index of any followeri∈𝕍 as follows: (31)Ii(k)=∑j|(i,j)∈E‖xi(k)-xj(k)-ri,j(k)‖S2∀i∈V.This performance index represents the deviation (error) from the desired formation shape; hence, a smallerIi is desired. Then, the total error of the group at time step k is presented as follows:(32)I(k)=∑i∈VIi(k).


### 4.1. Performance Improvement

The simulation was repeated for cases with different communication delays, and the results are gathered in Figures5 and 6.  Figure 5 shows the average of the formation error (32) with each point representing a single simulation. It can be seen from Figure 5 that estimating the tail of the cost function leads to smaller errors.  Figure 6 shows the percentage of performance improvement (error reduction) when the tail estimation method is used comparing with the case where no tail estimation is performed. It shows also that for large communication delays the proposed approach can reduce the error by 350%. It can also enhance the stability of the formation; for this particular example, it is seen that if the communication delay is increased to around d=10 time steps, the formation becomes unstable when using the cost function without the tail cost.  However, it is still stable with the proposed cost function including the tail cost. This result is consistent with that of [26, 27] where a final cost is added to the cost function for formation stability, although they did not consider communication delays. The overall trend of the graphs in Figure 5 shows that the error goes up with delay.Figure 5
Average of error versus communication delay for a triangle formation of three vehicles.Figure 6
Percentage of average of error versus communication delay for a triangle formation of three vehicles.Note that, since we assume no uncertainty in the model, the main source of error arises from communication delay and decentralized nature of the problem. The communication delay forces the decentralized controllers to use delayed information instead of updated information, which adds some degree of uncertainty into the problem, leading to error and degraded cooperation performance. Also, the decentralized nature of the problem restricts the decentralized controllers to access all the information about neighboring vehicles intention and control calculation procedure. For example, vehicles do not take into account the interaction graph topology of neighboring vehicles, in order to reduce the computation load. The second source of error does not exist in a centralized framework.


### 4.2. Safety Using Tube DMPC

It is observed that in some simulations in presence of large communication delays although adding the final cost can lead to better performance and stable formation, the vehicles may get too close to each other and collide. For example, the minimum distance among the vehicles for a set of simulations is depicted in Figure7. The desired distance between each pair of neighboring vehicles is 7.07 m. As seen even for the case where tail cost estimation is used the vehicles may get too close to each other.Figure 7
Minimum distance between vehicles in the presence of a communication delays.Therefore, in the next simulation the proposed Algorithm2 which includes the tube DMPC is used. This case involves the triangular formation control of six vehicles. The communication graph topology is set as follows:(33)V={1,2,3,4,5,6},E={(2,1),(3,1),(4,2),(5,4),(6,3)}.The results are shown in Figure8 through Figure 10. In this case, two sets of way points are considered to be visited by the fleet. At the beginning the intervehicle communication delay is d=0 but after 3 sec (around point (22,22)) communication loss begins which leads to d=7 time step intervehicle communication delay. As seen from Figure 8 the vehicles start to keep a larger distance, and the formation is expanded for safety upon communication loss. Figure 9 shows the same scenario when Algorithm 1 is used.Trajectory (a) and formation snapshot (b) of six vehicles in triangular formations when Algorithm2 is used.
(a)(b)Trajectory (a) and formation snapshot (b) of six vehicles in triangular formations when Algorithm1 is used.
(a)(b)Distances between each pair of vehicles for Algorithm2 (a) and Algorithm 1 (b).
(a)(b)The distances between each pair of neighboring vehicles are shown in Figure10 for two cases: (1) Algorithm 1 and (2) Algorithm 2. It is desired that vehicles keep a 7.07 m distance from neighbors. As seen from Figure 10(b) in the case of Algorithm 1, vehicles get too close to each other and may collide. However, Algorithm 2 offers a loose (Figure 8) but safe formation (Figure 10(a)) as the consequence of using tube DMPC for safety.For this case the minimum desired separation between two neighboring vehicle is 7.07 m. The corresponding required minimum relative distance, when Algorithm2 is used for a delay of d=7 time-step, is about 10 m as measured from Figure 10(a). Hence, for this case the added margin due to using tube DRHC is calculated as 10-7.07≈3m; then for such relatively large delay, the added margin is about 42.8%, which does not seem conservative. In the presence of model uncertainty and communication noise this margin will grow.


## 4.1. Performance Improvement

The simulation was repeated for cases with different communication delays, and the results are gathered in Figures5 and 6.  Figure 5 shows the average of the formation error (32) with each point representing a single simulation. It can be seen from Figure 5 that estimating the tail of the cost function leads to smaller errors.  Figure 6 shows the percentage of performance improvement (error reduction) when the tail estimation method is used comparing with the case where no tail estimation is performed. It shows also that for large communication delays the proposed approach can reduce the error by 350%. It can also enhance the stability of the formation; for this particular example, it is seen that if the communication delay is increased to around d=10 time steps, the formation becomes unstable when using the cost function without the tail cost.  However, it is still stable with the proposed cost function including the tail cost. This result is consistent with that of [26, 27] where a final cost is added to the cost function for formation stability, although they did not consider communication delays. The overall trend of the graphs in Figure 5 shows that the error goes up with delay.Figure 5
Average of error versus communication delay for a triangle formation of three vehicles.Figure 6
Percentage of average of error versus communication delay for a triangle formation of three vehicles.Note that, since we assume no uncertainty in the model, the main source of error arises from communication delay and decentralized nature of the problem. The communication delay forces the decentralized controllers to use delayed information instead of updated information, which adds some degree of uncertainty into the problem, leading to error and degraded cooperation performance. Also, the decentralized nature of the problem restricts the decentralized controllers to access all the information about neighboring vehicles intention and control calculation procedure. For example, vehicles do not take into account the interaction graph topology of neighboring vehicles, in order to reduce the computation load. The second source of error does not exist in a centralized framework.


## 4.2. Safety Using Tube DMPC

It is observed that in some simulations in presence of large communication delays although adding the final cost can lead to better performance and stable formation, the vehicles may get too close to each other and collide. For example, the minimum distance among the vehicles for a set of simulations is depicted in Figure7. The desired distance between each pair of neighboring vehicles is 7.07 m. As seen even for the case where tail cost estimation is used the vehicles may get too close to each other.Figure 7
Minimum distance between vehicles in the presence of a communication delays.Therefore, in the next simulation the proposed Algorithm2 which includes the tube DMPC is used. This case involves the triangular formation control of six vehicles. The communication graph topology is set as follows:(33)V={1,2,3,4,5,6},E={(2,1),(3,1),(4,2),(5,4),(6,3)}.The results are shown in Figure8 through Figure 10. In this case, two sets of way points are considered to be visited by the fleet. At the beginning the intervehicle communication delay is d=0 but after 3 sec (around point (22,22)) communication loss begins which leads to d=7 time step intervehicle communication delay. As seen from Figure 8 the vehicles start to keep a larger distance, and the formation is expanded for safety upon communication loss. Figure 9 shows the same scenario when Algorithm 1 is used.Trajectory (a) and formation snapshot (b) of six vehicles in triangular formations when Algorithm2 is used.
(a)(b)Trajectory (a) and formation snapshot (b) of six vehicles in triangular formations when Algorithm1 is used.
(a)(b)Distances between each pair of vehicles for Algorithm2 (a) and Algorithm 1 (b).
(a)(b)The distances between each pair of neighboring vehicles are shown in Figure10 for two cases: (1) Algorithm 1 and (2) Algorithm 2. It is desired that vehicles keep a 7.07 m distance from neighbors. As seen from Figure 10(b) in the case of Algorithm 1, vehicles get too close to each other and may collide. However, Algorithm 2 offers a loose (Figure 8) but safe formation (Figure 10(a)) as the consequence of using tube DMPC for safety.For this case the minimum desired separation between two neighboring vehicle is 7.07 m. The corresponding required minimum relative distance, when Algorithm2 is used for a delay of d=7 time-step, is about 10 m as measured from Figure 10(a). Hence, for this case the added margin due to using tube DRHC is calculated as 10-7.07≈3m; then for such relatively large delay, the added margin is about 42.8%, which does not seem conservative. In the presence of model uncertainty and communication noise this margin will grow.


## 5. Conclusions

A new delay-compensated decentralized model predictive controller (DC-DMPC) is proposed that can address communication delays arising from any source including packet losses. The proposed approach provides two key features. The first feature is that the tail of the cost function is estimated for performance improvement in the presence of the large intervehicle communication delays. Simulation results show that this method can lead to 350% improvement in the cooperation performance. The added online computation load depends on the communication delay and should be taken into account for any particular application. The second feature is the development of the tube-based MPC to provide guaranteed formation safety against possible collisions in the presence of large intervehicle communication delays. Together, these results provide a new approach to deal with the large intervehicle communication delays in DMPC problems that ensures safe formations and improved cooperation performance.



---

*Source: 198308-2011-05-29.xml*