Next Article in Journal
Experimental Investigation of a Cable Robot Recovery Strategy
Next Article in Special Issue
Singularity Avoidance for Cart-Mounted Hand-Guided Collaborative Robots: A Variational Approach
Previous Article in Journal
Impact of Cycle Time and Payload of an Industrial Robot on Resource Efficiency
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Time Coordination and Collision Avoidance Using Leader-Follower Strategies in Multi-Vehicle Missions

1
Department of Mechanical Engineering, University of Iowa, Iowa City, IA 52240, USA
2
Department of Mechanical Science and Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA
*
Author to whom correspondence should be addressed.
Submission received: 13 January 2021 / Revised: 6 February 2021 / Accepted: 9 February 2021 / Published: 13 February 2021
(This article belongs to the Special Issue Women in Robotics)

Abstract

:
In recent years, the increasing popularity of multi-vehicle missions has been accompanied by a growing interest in the development of control strategies to ensure safety in these scenarios. In this work, we propose a control framework for coordination and collision avoidance in cooperative multi-vehicle missions based on a speed adjustment approach. The overall problem is decoupled in a coordination problem, in order to ensure coordination and inter-vehicle safety among the agents, and a collision-avoidance problem to guarantee the avoidance of non-cooperative moving obstacles. We model the network over which the cooperative vehicles communicate using tools from graph theory, and take communication losses and time delays into account. Finally, through a rigorous Lyapunov analysis, we provide performance bounds and demonstrate the efficacy of the algorithms with numerical and experimental results.

1. Introduction

Multi-vehicle cooperative missions have become the focus of many researches, because they allow for the completion of tasks in a faster, safer, and more efficient way than single vehicle missions. Therefore, many efforts have been devoted to developing control algorithms for such missions. Examples can be found in several different applications, such as logistic tasks in industrial warehouses, where Automated Guided Vehicles (AGV) transport and handle products [1]; search and rescue missions, where drones cooperatively search large portions of territory to aid people in distress [2,3]; and, surveillance, where UAVs gather images and information about specific targets or areas [4,5], etc.
In missions involving unmanned vehicles, safety is one of the main concerns and collision avoidance algorithms play an important role toward the safe execution of the tasks. Some of the techniques for collision avoidance found in the literature include (i) trajectory planning, where agents’ trajectories are planned to create collision-free paths [6,7,8]; (ii) velocity obstacle (VO) methods, where the set of velocities that will result in collisions is defined, and the vehicle’s velocity is adjusted accordingly [9,10,11]; (iii) machine learning based methods, such as deep reinforcement learning [12,13]; (iv) and game theory [14,15,16]. Many of the proposed solutions can only guarantee safety in a narrow range of scenarios (e.g., static or slow moving obstacles), and are not always well suited for multi-vehicle missions, as they do not ensure safety among agents.
Multi-vehicle missions pose an extra challenge, as they require control strategies to ensure safety against pop-up moving obstacles as well as inter-vehicle safety. In other words, when one vehicle deviates from its nominal trajectory in order to avert collision with an external obstacle, it must simultaneously consider the presence of cooperative vehicles sharing the same space. Some of the well known approaches that simultaneously address both of the requirements are based on potential fields, where agents are treated as charged particles and repel other cooperative or non-cooperative vehicles [17,18,19,20,21]. However, these techniques are often conservative, and they only provide guaranteed safety within small subsets of initial conditions and vehicle dynamics.
In this work, we consider scenarios in which it is undesirable for a vehicle to deviate from its nominal trajectory and, if possible, it is preferred to perform collision avoidance against moving obstacles by only changing the speed of the agents. Examples of such scenarios include, but are not limited to, air traffic management, where the direction taken by the aircraft is fixed and the speed can be varied within a feasibility range, and highway driving, where vehicles driving can vary their speeds while remaining in their lane. To address the problem at hand, the research group previously introduced a cooperative control framework for collision avoidance [22,23,24]. With this framework, safety is achieved by decoupling the cooperative collision avoidance problem into a coordination problem [25,26] to ensure inter-vehicle safety, and a collision-avoidance problem [23] to guarantee safety against dynamic obstacles. It is shown, using tools from graph theory and Lyapunov analysis, that safe operations are guaranteed under realistic assumptions on the communication network over which the vehicles communicate. Nevertheless, one main limitation of this work lies in the assumption that all of the agents are equipped with sensors that are able to measure position and speed of the obstacle in real-time. It is often more realistic to assume that only a subset of the vehicles (the leaders of the mission) have the necessary on-board equipment to acquire such information.
Concerning coordination, in [25], the authors introduce a time-critical coordination algorithm for the control of multiple vehicles. This time-coordination algorithm is based on a leader-follower structure and allows for a fleet of fixed-wing UAVs to coordinate with each other at a desired constant pace, known to the leaders only. One key limitation of the work in [25] lies in the assumption that the speed of the vehicles under consideration must be lower bounded by a positive constant. Therefore, making this algorithm not employable in missions involves vehicles that allow the existence of zero velocity vectors. In Refs. [26,27,28], the authors depart from [25], and propose a decentralized time-coordination algorithm that guarantees coordination for a broader class of vehicles. Coupled with trajectory generation methods, this time-coordination algorithm ensures spatial separation between the agents and, thus, guarantees inter-vehicle safety throughout the mission. On the other hand, in this work it is assumed that the coordination variables and the desired mission pace are known by all of the agents and not only to a subset of leaders.
Motivated by these ideas, we build on previous results on time-coordination [26,27,28,29], and propose a Lyapunov-based method to the cooperative collision avoidance problem. This work departs from previous solutions to this problem [22,23,24] by adopting a new time-coordination algorithm for inter-vehicle safety. The main novelty of this method concerns the structure of the control system. Conversely from the solutions that were proposed in [26,27,28], this algorithm relies on a leader-follower structure and can be applied to a wide range of autonomous missions. In the proposed scenario, once a possible collision with a non-cooperative obstacle is detected by mission’s leaders (or virtual leaders), these deviate from their nominal trajectory, while the followers, who have no information about the position of the obstacle, are also able to avoid the collision by coordinating with the leaders. Furthermore, we have extended the theoretical results in [24] and provided rigorous performance bounds. It is shown that the coordination and safety guarantees hold even in the presence of communication faults. When combined with trajectory generation algorithms [30,31] and trajectory tracking algorithms [25,32], the control laws that are proposed in this work provide a Cooperative Control Framework that enables safe operations for all agents. Figure 1 presents a schematic of the Cooperative Control Framework.
The paper is organized as follows: Section 2 presents the cooperative control framework that this work is based on. A formulation of the time-coordination problem is given in Section 3, while the collision-avoidance problem is stated in Section 4. A mathematical formulation of the proposed control laws is given in Section 5. Section 6 presents the main results, while the efficacy of the algorithms is demonstrated through the experimental results presented in Section 7. Finally, the conclusions are given Section 8.

2. Cooperative Control Framework

The cooperative control framework comprises (i) an offline optimal motion planning module that generates feasible paths for multiple vehicle missions, (ii) tracking algorithms that enable the vehicles to track virtual targets moving along these paths, (iii) time-coordination algorithms that adjust the rate of progression of the virtual target to follow a desired mission pace and to achieve inter-vehicle coordination, and (iv) collision-avoidance algorithms that adjust the desired pace of the mission to avert collisions with pop-up obstacles and uncooperative vehicles. The framework, which builds on the planning and control framework for multi-vehicle missions presented in previous work [33], is depicted in Figure 1 for the leader and follower, respectively. The present paper is focused on time-coordination and collision-avoidance. Nevertheless, for the sake of clarity and completeness, the remainder of this section introduces the optimal motion planning and virtual target tracking problems.

2.1. Optimal Motion Planning

Given a cooperative multi-vehicle mission involving N vehicles, the optimal motion planning problem can be defined as follows:
Problem 1
(Optimal motion planning). Compute N desired trajectories p i ( t ) : [ 0 , t f ] R d , d { 2 , 3 } , i { 1 , 2 , , N } , which minimize a given cost function, and satisfy boundary conditions, feasibility constraints, and mission-specific constraints.
In the above problem definition, the boundary constraints are the predefined initial and final conditions on trajectories, such as initial and final positions, speeds, and heading angles. The feasibility constraints include vehicle dynamics and input bounds, as well as constraints dealing with the avoidance of obstacles and spatial deconfliction between trajectories to avoid inter-vehicle collisions and ensure the safe simultaneous operation in a common airspace, i.e.,
p i ( t ) p j ( t ) d safe ,
for all i , j { 1 , , N } , i j , with d safe > 0 . Finally, further mission-specific constraints, such as simultaneous or sequential arrival, can be imposed.

2.2. Virtual Target Tracking

Let the virtual time γ i ( t ) , t 0 , be a temporal variable that is defined as follows:
γ i : R + [ 0 , t f ] , i = 1 , , N .
Let p i ( γ i ( t ) ) be the virtual target that is assigned to the ith vehicle. Here, p i ( t ) is the ith trajectory generated at the motion planning level. With this definition, the virtual time is a variable, which conversely to the clock time, can be stretched or compressed to adjust the progression of the virtual target along the geometric path p i ( · ) , in order to achieve some objectives, e.g., coordination or collision avoidance, as we will see later. Notice that, when γ ˙ i ( t ) 1 , then the progression of the virtual time is equal to the progression of the clock time.
On the other hand, γ ˙ i ( t ) > 1 implies that the virtual target that is assigned to the ith vehicle is moving faster than the nominal trajectory generated by the trajectory generation algorithm. Similarly, γ ˙ i ( t ) < 1 implies a slower execution of the mission. With this setup, let the equations of motion of the ith vehicle be given by
x ^ ˙ i ( t ) = f i ( x ^ i ( t ) , u ^ i ( t ) ) , x ^ i ( 0 ) = x ^ i , 0 p ^ i ( t ) = g i ( x ^ i ( t ) ) ,
where p ^ i ( t ) is the actual ith vehicle’s position, x ^ i is the state of the vehicle (e.g., position, attitude, velocity, etc.), u ^ i ( t ) ) is the control input, and f i ( · ) and g i ( · ) are vectors of nonlinear functions describing the vehicle’s dynamics. Subsequently, the objective of the virtual target tracking problem can be stated as follows:
Problem 2
(Virtual target tracking). Design a control law for u ^ i ( t ) such that the virtual target tracking error
x T T , i ( t ) p i ( γ i ( t ) ) p ^ i ( t )
converges to a neighborhood of zero.
Finally, feasibility constraints must be imposed to ensure that the problem above can be solved. In addition to the vehicles’ dynamics constraints, which are taken into account in Problem 1, it is necessary to ensure that the bounds on the dynamics of the virtual time are enforced, so that the virtual targets can be tracked by the agents. In particular, a virtual target can be tracked by the ith vehicle if its trajectory p i ( t ) , i = 1 , , N is a feasible solutions of Problem 1, and the derivatives of its virtual time satisfy
1 γ ˙ i , max γ ˙ i ( t ) 1 + γ ˙ i , max ,
| γ ¨ i ( t ) | γ ¨ i , max ,
with 0 < γ ˙ i , max < 1 and γ ¨ i , max > 0 .
As it will become clear later, the dynamics of the virtual time (in particular, its second derivative γ ¨ i ( t ) ) are explicitly used as control input to achieve time coordination and collision avoidance. For this reason, when deriving control laws for γ ¨ i ( t ) , the bounds in (6) will be taken into consideration.

3. Time Coordination Problem

Recall that, at time t, the virtual target to be tracked by ith vehicle is given by p i ( γ i ( t ) ) , where the path p i ( · ) is given by the optimal motion planning algorithm, and γ i ( t ) is the virtual time. The virtual time and its derivatives play an important role in defining the time-coordination problem. In fact, because the virtual target is parameterized by γ i ( t ) , and the trajectories p i ( t ) satisfy spatial deconfliction constraints (see Equation (1)) and mission-specific requirements (e.g., simultaneous time of arrival, see Section 2), we say that, at time t, the vehicles are coordinated and inter-vehicle safety is guaranteed, if
γ i ( t ) = γ j ( t ) , i , j { 1 , 2 , , N } .
Furthermore, they are all progressing at the same desired pace, if
γ ˙ i ( t ) = γ ˙ d ( t ) , i { 1 , 2 , , N } ,
where γ ˙ d ( t ) > 0 represents the desired pace of the mission. We recall that γ ˙ d ( t ) = 1 means that the vehicles are required to proceed along the assigned trajectories at the rate that was established at the motion planning level.
As it will be clear later, the desired pace of the mission γ ˙ d ( t ) is used as an extra degree of freedom by the collision-avoidance algorithm to adjust the rate of the mission in order to avert collision with obstacles, and it is set to 1 if no obstacle is present.
With this setup, the time-coordination problem can be defined as that of designing control laws for γ ¨ i ( t ) that ensure the satisfaction of Equations (7) and (8). To achieve this objective, information between the vehicles must be exchanged during the mission execution. Thus, we first state a set of assumptions that the communication network, over which the vehicles communicate, must satisfy in order to provide a mathematical formulation of the problem at hand. In what follows, tools from graph theory are used to formulate these assumptions. In particular, consider the Laplacian matrix for the time-varying communication graph Γ ( t ) , L ( t ) R N × N , and let Q R ( N 1 ) × N be a matrix that satisfies the following:
Q 1 N = 0 , Q Q = I N 1 , Q Q = I N 1 N 1 N 1 N .
Remark 1.
In [25], the existence of a matrix Q that satisfies the above properties is demonstrated. An iterative procedure to compute the matrix Q is presented in [26].
Let L ¯ ( t ) = Q L ( t ) Q . The matrix L ¯ ( t ) has the same eigenvalues as the Laplacian matrix, but without the first eigenvalue λ 1 = 0 . The following is assumed in terms of the communication graph.
Assumption 1.
  • The ith vehicle can only communicate with a neighboring set of vehicles, here referred to as N i .
  • The communication between the vehicles is bidirectional and with no time delays.
  • The connectivity of the communication graph Γ ( t ) satisfies the Persistency of Excitation (PE)-like condition:
    t t + T L ¯ ( τ ) d τ μ I N 1 , t 0 ,
    with T > 0 and μ = ( 0 , 1 ] .
Notice that the condition given by Equation (10) implies that the graph Γ ( t ) must be connected in an integral sense, therefore allowing the graph to be disconnected point-wise in time. In this sense, the assumption above captures packet dropouts, communication losses, and switching topologies.
Finally, let N L N be the number of vehicles elected as leaders (and N N L the number of followers). We assume that the desired mission pace γ ˙ d ( t ) is known to the leaders only, e.g., vehicles k = { 1 , , N L } . Thus, one of the main challenges is ensuring the satisfaction of Equation (8) for all i { 1 , 2 , , N L , , N } , with the desired pace γ ˙ d ( t ) only being known to a subset of vehicles.
Letting γ ( t ) = [ γ 1 ( t ) , γ N ( t ) ] , γ ˙ ( t ) = [ γ ˙ 1 ( t ) , γ ˙ N ( t ) ] , we define the time coordination errors as
ξ ( t ) = Q γ ( t ) , z ( t ) = γ ˙ ( t ) γ ˙ d ( t ) 1 N .
Notice that ξ ( t ) = 0 implies that γ i ( t ) = γ j ( t ) (see Equation (9)). Subsequently, the time-coordination problem can be formulated, as follows.
Problem 3
(Time coordination). Consider a cooperative mission with N vehicles. Assume that the vehicles are equipped with optimal motion planning and virtual target tracking algorithms that solve Problems 1 and 2, respectively. Finally, assume that the vehicles are supported by a communication network that satisfies Assumption 1, and that the desired mission pace is known to a subset of N L N vehicles only (leaders). Then, the objective of time-coordination is to design control laws for γ ¨ i ( t ) , for all i { 1 , , N } , such that the time-coordination errors ξ ( t ) and z ( t ) defined in Equation (11) converge to a neighborhood of zero.

4. Collision Avoidance Problem

Consider a non-cooperative vehicle (or an obstacle) with nominal position p ^ o ( t ) and speed satisfying p ^ ˙ o ( t ) > 0 for all t 0 . Furthermore, let there be values of the virtual time γ * , i [ 0 , t f ] and (clock) time t * [ 0 , ) , such that
p i ( γ * , i ) p ^ o ( t * ) d safe ,
with d safe > 0 . We recall that the planned position of the ith vehicle is given by p i ( γ i ( t ) ) . Thus, Equation (12) implies that a collision between the obstacle and vehicle i occurs if γ i ( t * ) γ * , i , and it is the objective of the collision-avoidance algorithm to ensure that this condition is never met. Moreover, in order to take possible speed variations in the obstacle’s trajectory into consideration, let its trajectory be reparameterized using the virtual time variable γ o ( t ) . Similarly to the vehicles’ trajectories, γ ˙ o ( t ) = 1 indicates that the obstacle is moving according to its nominal trajectory. Subsequently, the trajectory of the non-cooperative vehicle can be rewritten as
p o ( γ o ( t ) ) = p ^ o ( γ o ( t ) γ * , i + t * ) , γ o ( t ) [ γ o ( 0 ) , ) .
Assuming that the instantaneous speed of the obstacle can be measured (no such assumptions are made for the acceleration),the pace of the obstacle can be characterized as the ratio between the obstacle’s actual and nominal speed. In particular, we have
γ ˙ o ( t ) = p ˙ o ( t ) d p ^ o ( γ γ * , i + t * ) d γ | γ = γ o ( t ) , γ o ( 0 ) = γ * , i t * .
With this setup, assumptions on the dynamics of the obstacle can be formulated in terms of its virtual time. In particular, the following is assumed about the obstacle’s speed and acceleration:
1 γ ˙ o , max γ ˙ o ( t ) 1 + γ ˙ o , max , | γ ¨ o ( t ) | γ ¨ o , max ,
for some γ ˙ o , max and γ ¨ o , max .
Finally, we define
γ δ , i ( t ) = γ i ( t ) γ o ( t ) ,
as the difference in virtual time between the ith vehicle and the obstacle. From (13), it follows that if γ δ , i ( t ) = 0 , with γ i ( t ) = γ o ( t ) = γ * , i , then p i ( γ i ( t ) ) p o ( γ o ( t ) ) d safe , where p i ( γ i ( t ) ) is the trajectory of the ith vehicle and d safe is the required safety distance between the vehicle and the obstacle. Instead, keeping | γ δ , i ( t ) | 0 ensures that the vehicle and obstacle will reach the impact location at different times, therefore avoiding a collision. Thus, γ δ , i ( t ) 0 is a sufficient condition for ensuring safety. With this setup, we assume the existence of a minimum virtual time separation that guarantees collision avoidance. This is summarized in the following two cases:
1.
There exists γ safe > 0 such that, if
γ δ , i ( t ) = γ i ( t ) γ o ( t ) γ safe ,
for all γ i ( t ) [ 0 , t f ] , then
p i ( γ i ( t ) ) p o ( γ o ( t ) ) > d safe , γ i ( t ) [ 0 , t f ] .
2.
There exists γ safe < 0 such that, if
γ δ , i ( t ) = γ i ( t ) γ o ( t ) γ safe ,
for all γ i ( t ) [ 0 , t f ] , then
p i ( γ i ( t ) ) p o ( γ o ( t ) ) > d safe , γ i ( t ) [ 0 , t f ] .
Recall, from Section 3, that the rate of progression of the virtual times γ i ( t ) , i { 1 , , N } (and, thus, the speed of the vehicles) can be controlled by adjusting γ ˙ d ( t ) . In fact, the use of the desired mission pace γ ˙ d ( t ) becomes important in the presence of external obstacles to ensure that conditions (16) or (17) are satisfied for all t 0 . This leads to the formulation of the collision avoidance problem.
Problem 4
(Collision avoidance). Consider a cooperative mission with N vehicles. Assume that the vehicles are equipped with optimal motion planning and virtual target tracking algorithms that solve Problems 1 and 2, respectively, and with a time-coordination algorithm that solves Problem 3. Assume the presence of an obstacle with dynamics that satisfy the bounds in Equation (15) for some γ ˙ o , max and γ ¨ o , max . Subsequently, the objective of the collision-avoidance algorithm is to design control laws for γ ˙ d ( t ) , such that the safety conditions that are given by Equations (16) or (17) are satisfied for all t 0 .
Remark 2.
In this paper, we only consider the scenario in which one obstacle is present.
Remark 3.
In practice, the leaders can be "virtual", e.g., ground stations. Therefore, we believe that it is reasonable to assume that most of the computations and sensing necessary to guarantee collision avoidance can be performed by the leaders.

5. Control Law

This section provides a control strategy to solve the time-coordination and collision-avoidance problems.

5.1. Time-Coordination Control Law

To solve Problem 3, we let the evolution of the virtual time (for leaders and followers, respectively) be governed by:
γ ¨ i ( t ) = b γ ˙ i ( t ) γ ˙ d ( t ) a j N i ( γ i ( t ) γ j ( t ) ) , i { 1 , , N L } , γ ¨ i ( t ) = b γ i ˙ ( t ) χ I , i ( t ) a j N i ( γ i ( t ) γ j ( t ) ) , χ ˙ I , i ( t ) = k j N i ( γ i ( t ) γ j ( t ) ) , i { N L + 1 , , N } ,
γ i ( 0 ) = 0 , γ ˙ i ( 0 ) = 1 , χ I , i ( 0 ) = 1 ,
where a, b, and k are the positive coordination control gains and γ ˙ d ( t ) is a desired mission pace satisfying
1 γ ˙ d , max γ ˙ d ( t ) 1 + γ ˙ d , max ,
| γ ¨ d ( t ) | γ ¨ d , max ,
for some γ ˙ d , max , γ ¨ d , max > 0 . The desired pace γ ˙ d ( t ) will be defined later when introducing the collision avoidance algorithm, and can now be considered as a desired time-varying value that is to be tracked by γ ˙ i ( t ) , i = 1 , , N .
The time-coordination control law can also be written in matrix form as
γ ¨ ( t ) = a L γ ( t ) b D γ ˙ ( t ) γ ˙ d ( t ) 1 N L C γ ˙ ( t ) χ I ( t ) χ ˙ I ( t ) = k C L γ ( t ) ,
γ ( 0 ) = 0 N , γ ˙ ( 0 ) = 1 N , χ I ( 0 ) = 1 N N L ,
where
C = 0 I N N L ,
D = I N L 0 .
The objective of the time-coordination control law is to ensure that Equations (7) and (8) are satisfied at all times, even if the desired mission pace γ d ˙ ( t ) is known by the leaders only, as was mentioned earlier. For this reason, we introduce the term χ I ( t ) , which plays the role of an integral term ensuring satisfaction of Equation (8).

5.2. Collision-Avoidance Control Law

To solve Problem 4, the proposed collision-avoidance method uses γ ˙ d ( t ) as a control input to appropriately adjust the speed of the mission. We formulate control laws based on two cases.

5.2.1. Case 1: Collision Avoidance by Setting γ δ , i ( t ) > γ safe

In this scenario, the collision between the ith vehicle and an obstacle can be avoided by maintaining the virtual time γ i ( t ) larger than γ o ( t ) by a value that is greater or equal to γ safe . Therefore, we let γ ˙ d ( t ) be governed by
γ ˙ d ( t ) = 1 + 0 , ω ( t ) < 1 η , ( ω ( t ) 1 ) ρ ( ω ( t ) ) , 1 η ω ( t ) 1 , ω ( t ) 1 , ω ( t ) > 1 ,
where
ω ( t ) = γ safe + ϵ γ δ , i ( t ) γ ˙ o ( t ) ,
ϵ > 0 is a design parameter, and η > 0 is a small positive number. Lastly, ρ : [ 1 η , 1 ] [ 0 , 1 ] is a smooth function (an example for ρ is ρ ( x ) = 1 3 x 1 η 2 2 x 1 η 3 ) that satisfies
ρ ( 1 η ) = 0 , d ρ ( 1 η ) d ω = 0 , ρ ( 1 ) = 1 , d ρ ( 1 η ) d ω = 0 .
In the remainder of this section, we describe the physical meaning of the proposed control laws. We note that, in (22), γ ˙ d ( t ) is a C 1 -continuous approximation of a max function and satisfies
γ ˙ d ( t ) max 1 , ω ( t ) = max 1 , γ safe + ϵ γ δ , i ( t ) γ ˙ o ( t ) .
This is motivated by the fact that γ δ , i ( 0 ) is initially already greater than γ safe . Thus, the pace of the mission may need to be increased, but never decreased. To this end, γ ˙ d ( t ) is defined such that the right hand side of (23) is guaranteed to be always greater or equal to 1.
In the case in which ω ( t ) 1 , the pace of the mission is adjusted as
γ ˙ d ( t ) ω ( t ) = γ safe + ϵ γ δ , i ( t ) γ ˙ o ( t ) .
This implies that, if γ δ , i ( t ) < γ safe + ϵ , the proposed control law ensures that γ ˙ d ( t ) (and, consequently, γ ˙ i ( t ) ) are greater than γ ˙ o ( t ) , which, in turn, cause γ δ , i ( t ) to increase.
Conversely, using the fact that γ ˙ d ( t ) is bounded from below (see Equation (23)), if γ δ , i ( t ) > γ safe + ϵ , then γ ˙ d ( t ) ω ( t ) < γ ˙ o ( t ) , which implies that γ ˙ d ( t ) is guaranteed to remain in a neighbourhood of 1.

5.2.2. Case 2: Collision Avoidance by Setting γ δ , i ( t ) < γ safe

In this case, the vehicle can avoid the obstacle by maintaining γ i ( t ) lower than γ o ( t ) by a value lower or equal to γ safe . The pace of the mission may need to be decreased to achieve this.
The proposed control law is given, as follows:
γ ˙ d ( t ) = 1 + ω ( t ) 1 , ω ( t ) < 1 , ( ω ( t ) 1 ) ρ ( ω ( t ) ) , 1 ω ( t ) 1 + η , 0 , 1 + η < ω ( t ) ,
where ω ( t ) is now defined as
ω ( t ) = γ δ , i ( t ) γ safe ϵ γ ˙ o ( t ) ,
ϵ > 0 is a design parameter and η is a small positive number. Finally, ρ : [ 1 , 1 + η ] [ 0 , 1 ] is a smooth function that satisfies
ρ ( 1 ) = 1 , d ρ ( 1 ) d ω = 0 , ρ ( 1 + η ) = 0 , d ρ ( 1 + η ) d ω = 0 .

6. Main Results

6.1. Time Coordination

Recall that the time-coordination objective is captured by the error variables ξ ( t ) and z ( t ) defined in Equation (11), and the time-coordination control law is given by Equation (21). Let us define the time-coordination error vector, as follows:
x T C ( t ) = [ ξ ( t ) , z ( t ) , ( χ I ( t ) γ ˙ d ( t ) 1 N N L ) ] .
Subsequently, the following theorem summarizes one of the main results of this paper.
Theorem 1.
Consider a cooperative mission involving N vehicles, with N L vehicles elected as leaders. Let the vehicles be equipped with optimal motion planning and virtual target tracking algorithms that solve Problems 1 and 2, respectively. Assume that the vehicles are supported by a communication network that satisfies Assumption 1, and that the desired mission pace γ ˙ d ( t ) is known to a subset of N L N vehicles only (leaders). Let the evolution of the virtual time be governed by the control law that is given by (21). Let the time coordination error vector at time t = 0 , i.e., x T C ( 0 ) , and the dynamic limits of the desired mission pace (see Equations (19) and (20)) satisfy
γ ˙ d , max < γ ˙ max ,
and
max x T C ( 0 ) , γ ¨ d , max < min γ ˙ max γ ˙ d , max κ 1 + κ 2 , γ ¨ max 3 b κ 1 + 3 b κ 2 + 1 ,
for given γ ˙ max , γ ¨ max > 0 and for some positive constants κ 1 and κ 2 . Subsequently:
1.
There exist time-coordination control gains a, b and k, such that the time-coordination error vector is bounded by
| | x T C ( t ) | | κ 1 | | x T C ( 0 ) | | e λ T C t + κ 2 sup t 0 ( | γ ¨ d ( t ) | ) ,
with rate of convergence satisfying
λ T C < N L N 1 4 b μ T 1 + a b N T 2 .
2.
The feasibility bounds that are introduced in Equations (5) and (6) are never violated.
Proof. 
The proof of Theorem 1 is given in Appendix A, while a derivation of the dynamics is given in Appendix C. □
Remark 4.
For the sake of simplicity, in this paper we assume that the vehicles are able to perfectly track their virtual targets, i.e., x T T , i ( t ) = 0 (see Equation (4)). However, if this is not true, it can be demonstrated that similar coordination results can be achieved by adding an additional term in Equation (22) in order to take the tracking error into account. We refer the reader to [24], where the problem of coordination in the presence of tracking errors is addressed.
Remark 5.
We note that the rate of convergence is directly affected by the total number of vehicles, the number of leaders, and by the quality of the communication network (i.e., the parameters μ and T). Coordination is achieved with a slower rate of convergence in the case of switching topologies, dropouts, and communication delays, as emphasized by Theorem 1.

6.2. Collision Avoidance

The second and final result of this paper is summarized in the following theorem.
Theorem 2.
Let the desired pace of the mission γ ˙ d ( t ) be governed by Equation (22). Let the dynamics of the obstacle satisfy the following
γ ˙ o , m a x γ s a f e γ s a f e + ϵ 1 + γ ˙ m a x γ s a f e + ϵ γ s a f e , γ ¨ v a r γ ¨ m a x ,
where
κ 1 x T C ( 0 ) + κ 2 sup t [ 0 , t α ] ( | γ ¨ d , m a x ( t ) | ) ϵ γ s a f e γ ˙ m a x , 0 | | x T C ( 0 ) | | γ ˙ m a x κ 2 γ ¨ v a r κ 1 ,
with γ ¨ var given in Equation (A19). Moreover, assume that the collision avoidance error at time t = 0 satisfies γ δ , i ( 0 ) > γ safe , with γ safe satisfying
γ s a f e 2 η ¯ γ ¨ d , m a x ( 1 + γ ˙ o , m a x ) γ ¨ m a x γ s a f e η ¯ γ ¨ d , m a x ( 1 + γ ˙ o , m a x ) ϵ γ ¨ m a x > 0 .
Then:
1.
Collision avoidance is guaranteed for all t 0 , i.e.
γ δ , i ( t ) γ s a f e , t [ 0 , ) .
2.
The dynamic limits of γ d ( t ) , namely γ ˙ d , max and γ ¨ d , max , satisfy the bounds given by Equations (24) and (25).
Proof. 
Appendix B provides the proof of Theorem 2. □
Remark 6.
We notice that the second result above—Theorem 2—guarantees that the dynamics of the desired mission pace never violate the assumptions of Theorem 1. In turn, Theorem 2 implies that time coordination and collision avoidance are both guaranteed with the control laws given by Equations (21)—coordination—and (22)—collision avoidance.
Remark 7.
For the sake of brevity, Theorem 2 has only focused on the control law of Section 5.2.1, i.e., case 1. However, identical results can be concluded for the control law of Section 5.2.2, i.e., case 2.

7. Experimental Results

7.1. Time Coordination

The time-coordination algorithm is demonstrated with the use of two AR Drones 2.0 [34]. The drones need to follow a circular trajectory with a radius of 1.5 m, such that they maintain a constant phase shift between each other and are able to guarantee inter-vehicle safety. The total time of the mission is t f = 60 s and γ ˙ i , m a x = 0.25 , γ ˙ d , m a x = 0.2 , γ ¨ i , m a x = 0.1 and γ ¨ d , m a x = 0.1 .
The trajectories are generated with the use of the trajectory generation algorithm that is described in Section 2.1, and they are formulated as follows:
x 1 ( γ 1 ( t ) ) = 1.5 cos ( 0.15 γ 1 ( t ) ) , y 1 ( γ 1 ( t ) ) = 1.5 sin ( 0.15 γ 1 ( t ) ) , x 2 ( γ 2 ( t ) ) = 1.5 cos ( 0.15 γ 2 ( t ) + π ) , y 2 ( γ 2 ( t ) ) = 1.5 sin ( 0.15 γ 2 ( t ) + π ) .
The drones are enabled to follow their desired orbits by virtue of a simple PID-based trajectory tracking algorithm (see [26]). Finally, the quadrotors are equipped with the time-coordination algorithm that is proposed in this paper (see Equation (21)). The virtual target tracking and time-coordination algorithms are implemented on MATLAB Simulink, and run on a Lenovo ThinkPad P52 laptop with an Intel 8th generation i7 core. Real-time position measurements are performed using Vicon Motion Capture, and communicated to the controllers using the MATLAB ROS Toolbox. Finally, commands velocities in the x, y, and z directions are sent to the drones through ROS.
For this mission scenario, the drones are required to maintain a phase shift of π rad. Vehicle 1 is elected as leader while vehicle 2 is the follower. The drones initially start moving according to a desired mission pace of γ ˙ d = 1 , but, as can be seen from Figure 2, the pace of the mission is decreased twice during the course of the mission. In fact, at t 23 s, the pace is decreased to γ ˙ d ( t ) = 0.9 , and at t 44 s it is decreased again to γ ˙ d ( t ) = 0.8 . The value of γ ˙ d is only communicated to the leader, but the time-coordination algorithm ensures that the pace of the follower also converges to the desired pace of the mission. Furthermore, Figure 3 demonstrates the time-coordination, which shows the convergence of the virtual times to the same values, i.e., γ 1 ( t ) = γ 2 ( t ) . From the definition of the desired drones’ trajectories described in (29), it follows that, if γ 1 ( t ) = γ 2 ( t ) , then the desired phase shift between the drones is maintained. This can also be noticed from Figure 4. Here, the positions of the drones at three different time instances are shown. It can be seen that the drones are able to maintain a phase coordination throughout the mission.

7.2. Collision Avoidance

The efficacy of the collision-avoidance algorithm is demonstrated with experimental results involving three Turtlebot3 Burger ground robots [35] and one AR Drone 2.0. The mission requires the ground robots to cooperatively move along a circular trajectory with a radius of 1.5 m, while the drone is hovering. The drone is elected as a (virtual) leader while the robots are followers. Figure 5 shows the experimental setup for this mission, which is identical to the one used for the previous experiment.
The agents’ trajectories are planned offline, such that a minimum safety distance d safe = 0.4 m is maintained at all time, and γ safe = 2 s, t f = 80 s , γ ˙ i , m a x = 0.2 , γ ˙ d , m a x = 0.2 , γ ¨ i , m a x = 0.1 and γ ¨ d , m a x = 0.1 .
The evolution of the mission can be seen in Figure 6. In the considered scenario, a dynamic obstacle is moving towards the vehicles. At t 15 s, the obstacle starts decreasing its speed and now poses a threat to ground robot 1, which is shown by the blue circle in Figure 6. However, all three ground robots are able to avoid the collision, as it can be seen in the second panel of Figure 6, by virtue of the collision-avoidance algorithm. This can be better seen in Figure 7. The figure on the left shows the distance between the ground robots and the obstacle. It can be noticed that all the vehicles are able to successfully avoid the obstacle. However, this is not true in the case in which the collision-avoidance algorithm was not used, as shown by the light blue line. Furthermore, the right panel of Figure 7 shows the inter-vehicle distances between the ground robots. It can be noticed that, by virtue of the time-coordination algorithm, the agents are able to maintain a safe distance throughout the mission.
Figure 8 shows the evolution of γ δ , i ( t ) , which in this case is the difference in virtual time between the leader and the obstacle, throughout the mission. At t 15 s, when the obstacle starts to decrease its speed, γ δ , 1 ( t ) begins to increase. However, with the use of the collision-avoidance algorithm, γ δ , 1 ( t ) converges to a value that is less than γ safe = 2 s, guaranteeing that a minimum safe distance is kept and the collision can be avoided. The value of γ safe is calculated based on the average nominal linear and angular velocities of a Turtlebot3 Burger and it is selected to achieve d safe = 0.4 m.
The top row of Figure 9 shows the evolution of the pace of the mission. Initially, the desired pace is γ ˙ d = 1 , which indicates an ideal evolution of the mission. However, when the obstacle starts to endanger one of the vehicles, the pace of the mission is decreased to γ ˙ d 0.9 , according to the control law that is presented in this article. The bottom row of Figure 9 presents the evolution of the virtual time. It can be seen that, even with the collision-avoidance algorithm in use, the vehicles maintain time-coordination with γ 1 ( t ) = γ 2 ( t ) = γ 3 ( t ) = γ 4 ( t ) . We note that, at t = 65 s, the collision-avoidance algorithm is turned off, and γ δ , i ( t ) = 3 s and γ ˙ d = 1 . However, this does not affect collision-avoidance, as the obstacle has already left the impact area. Lastly, Figure 9 shows the evolution of the coordination errors. It can be noticed that, despite changes in the desired pace throughout the mission, the coordination errors are quickly driven to 0.
It is highlighted here that only the drone is able to detect changes in the speed profile of the obstacle, but, by virtue of the combined action of the time-coordination and collision-avoidance algorithms, the ground robots are able to avoid the impact, even without knowing the actual position and speed of the obstacle.

8. Conclusions

In this paper, we propose a collision-avoidance method that is based on a leader-follower time-coordination algorithm. The time-coordination algorithm ensures that all of the the vehicles are able to not only coordinate with each other, but follow a desired mission pace, which is known to to be a subset of vehicles only. Furthermore, the collision-avoidance algorithm relies on the knowledge of the nominal trajectory of obstacles and takes bounded deviations in their speed profiles into account. Together, the time-coordination and collision avoidance algorithms guarantee the safe execution of cooperative multi-vehicle missions in the presence of moving obstacles. A rigorous mathematical analysis, as well as experimental results, are provided to demonstrate the efficacy of the algorithm.

Author Contributions

Control Design, C.T., V.C., S.B.M., T.M. and N.H.; Original draft preparation, C.T. and V.C.; Review and edition, C.T., V.C., S.B.M., T.M. and N.H. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported by ONR, AFOSR, NSF and NASA.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. Proof of Theorem 1

First, consider the following system:
ϕ ˙ ( t ) = a b L ¯ ϕ ( t ) ,
where the matrix L ¯ satisfies the (PE)-like condition. Equation (A1) can be shown to be Globally Uniformly Exponentially Stable [36] (Lemma 5):
| | ϕ ( t ) | | k λ | | ϕ ( 0 ) | | e γ λ t ,
with k λ = 1 and γ λ γ ¯ λ = a b N μ T ( 1 + a b N T ) 2 . Using [37] (Theorem 4.14), we can imply that there exists a continuously differentiable, symmetric, positive definite matrix P ( t ) that satisfies the inequalities:
0 < c ¯ 1 I c ¯ 3 2 N I P ( t ) c ¯ 4 2 γ λ I c ¯ 2 I , P ˙ a b L ¯ P a b P L ¯ c ¯ 3 I .
The time-coordination states can be redefined as:
x ¯ T C = [ χ , z , ζ ] ,
where
χ = b ξ + Q z , z = γ ˙ γ ˙ d 1 N , ζ = χ I γ ˙ d 1 N N L k a C Q χ ,
with dynamics given by:
χ ˙ = a b L ¯ χ + b k a Q C C Q χ + a b L ¯ Q z + b Q C ζ , z ˙ = ( b I a b L ) z a b L Q χ + b k a C C Q χ + b C ζ γ ¨ d 1 N , ζ ˙ = k b a C Q Q C ζ b k 2 a 2 C Q Q C C Q χ γ ¨ d 1 N N L .
Consider the following Lyapunov candidate function:
V = χ P χ + β 2 z z + a 2 k 2 ζ C Q C Q 1 ζ = x ¯ T C W x ¯ T C ,
where β > 0 , P was introduced above, λ m i n C Q C Q = N L N and
W = P 000000 0 0 0 000000 β 2 I 0 0 000000 0 a 2 k 2 C Q C Q 1 .
Using (A5), the time derivative of (A6) can be computed to yield:
V ˙ = χ P a b L ¯ χ + b k a Q C C Q χ + a b L ¯ Q z + b Q C ζ + ( a b χ L ¯ + b k a χ Q C C Q + a b z L ¯ Q + b ζ C Q ) P χ + χ P ˙ χ + β z ( b I a b L z a b L Q χ + b k a C C Q χ + b C ζ γ ¨ d 1 N ) + a 2 k 2 ( k b a ζ C Q Q C b k 2 a 2 χ Q C C Q Q C 1 N N L γ ¨ d ) ( C Q Q C ) 1 ζ + a 2 k 2 ζ ( C Q Q C ) 1 ( k b a C Q Q C ζ b k 2 a 2 C Q Q C C Q χ γ ¨ d 1 N N L ) .
Finally, using the fact that | | L | | N , the above inequality implies
V ˙ χ P ˙ a b P L ¯ a b L ¯ P + 2 k b a Q C C Q P χ β z b I a b L z a 2 k 2 ζ 2 k b a ζ + 2 a b N | | P | | + β k b a + β a b N | | χ | | | | z | | + 2 b | | P | | + 2 b | | χ | | | | z | | + β b | | z | | | | ζ | | + β N + 2 a 2 k 2 N N L N L N | | x ¯ T C | | | γ ¨ d ( t ) | .
Using (A2), and after straightforward computations, we obtain:
V ˙ c ¯ 3 2 b k a c ¯ 2 | | χ | | 2 β b a b N | | z | | 2 2 b a k | | ζ | | 2 + 2 a b N c ¯ 2 + β k b a + β a b N | | χ | | | | z | | + ( 2 b c ¯ 2 + 2 b ) | | χ | | | | ζ | | + β b | | z | | | | ζ | | + η | | x ¯ T C | | | γ ¨ d ( t ) | ,
where η = β N + 2 a 2 k 2 N N L N L N . Finally, using c ¯ 2 = c ¯ 4 2 γ ¯ λ , letting c ¯ 4 = c ¯ 3 , we get
V ˙ c ¯ 3 2 b k a c ¯ 3 γ λ | | χ | | 2 β b a b N | | z | | 2 2 k b a | | ζ | | 2 + a N c ¯ 3 b γ λ + β k b a + β a b N | | χ | | | | z | | + b c ¯ 3 γ λ + 2 b | | χ | | | | ζ | | + β b | | z | | | | ζ | | + η | | x ¯ T C | | | γ ¨ d ( t ) | ,
if
M 2 λ T C W c ¯ 3 b k a c ¯ 3 γ ¯ λ c ¯ 3 γ ¯ λ λ T C a b N c ¯ 3 γ ¯ λ + β k b a + β a b N b c ¯ 3 γ ¯ λ + 2 b a b N c ¯ 3 γ ¯ λ + β k b a + β a b N β b a b N β λ T C β b b c ¯ 3 γ ¯ λ + 2 b β b 2 b a k 2 a 2 k 2 N N L λ T C 0 .
Then, the time derivative of the Lyapunov function is bounded as follows:
V ˙ 2 λ T C V + β N + 2 a 2 k 2 N L N L N | | x ¯ T C | | | γ ¨ d ( t ) | .
It can be demonstrated that by setting a = b N , k = 1 4 γ ¯ λ b N , λ T C = δ γ ¯ λ , β = 2 c ¯ 3 γ ¯ λ , c 3 ¯ = k a and δ < N L N 1 4 b , inequality (A7) holds for sufficiently large values of b. Therefore, one can conclude that the system (A5) is input to state stable, and the following bound holds:
| | x ¯ T C ( t ) | | max c ¯ 2 , β 1 2 , a 2 k 2 N N L min c ¯ 1 , β 1 2 , a 2 k 2 | | x ¯ T C ( 0 ) | | e λ T C t + max c ¯ 2 , β 1 2 , a 2 k 2 N N L min c ¯ 1 , β 1 2 , a 2 k 2 η 2 γ ¯ λ min c ¯ 1 , β 1 2 , a 2 k 2 sup t 0 | γ ¨ d ( t ) | .
Finally, from the definition
x ¯ T C S x T C , S = b I N 1 Q 0 0 I N 0 k a C Q 0 I N N L ,
we can conclude that
| | x T C ( t ) | | κ 1 | | x T C ( 0 ) | | e λ T C t + κ 2 sup t 0 ( | γ ¨ d ( t ) | ) ,
with
κ 1 = | | S 1 | | max c ¯ 2 , β 1 2 , a 2 k 2 N N L min c ¯ 1 , β 1 2 , a 2 k 2 | | S | | ,
and
κ 2 = | | S 1 | | max c ¯ 2 , β 1 2 , a 2 k 2 N N L min c ¯ 1 , β 1 2 , a 2 k 2 β N + 2 a 2 k 2 N N L N L N 2 γ ¯ λ min c ¯ 1 , β 1 2 , a 2 k 2 .
In conclusion, we need to demonstrate that γ ˙ i and γ ¨ i i { 1 , N } , satisfy the inequalities shown in (5) and (6). From Equation (A10) it follows that
| γ ˙ i ( t ) 1 | | γ ˙ d ( t ) 1 | + κ 1 | | x T C ( 0 ) | | e λ T C t + κ 2 sup t 0 ( | γ ¨ d ( t ) | ) .
Using (19) and (20), we can write the equation above as
| γ ˙ i ( t ) 1 | γ ˙ d , max + κ 1 + κ 2 max { x T C ( 0 ) , γ ¨ d , max } .
Finally, the assumptions given by Equations (24) and (25) allow us to conclude that inequality (5) holds. Now we consider bounds on γ ¨ i ( t ) . From Equation (A23) we get
| γ ¨ i | b | | z | | + b | | ζ | | + + a N max j N i | γ i ( t ) γ j ( t ) | .
Recalling that b = a N , it follows that
| γ ¨ i ( t ) | 3 b x T C ( t ) .
Using (A10), it can be seen that γ i ¨ ( t ) remains bounded as follows
| γ ¨ i ( t ) | ( 3 b κ 1 + 3 b κ 2 + 1 ) max x T C ( 0 ) , γ ¨ d , max .
The above inequality, together with Equations (24) and (25), imply that inequality (6) holds, which completes the proof of Theorem 1.

Appendix B. Proof of Theorem 2

First, we demonstrate the feasibility of the collision-avoidance algorithm showing that inequalities (24) and (25) hold. Using (22) and (24), we obtain
γ ˙ d γ safe + ϵ γ safe ( 1 + γ ˙ o , max ) .
Choosing a value of γ ˙ o , max that satisfy the following
γ ˙ o , max γ safe γ safe + ϵ 1 + γ ˙ max γ safe + ϵ γ safe ,
with ϵ < γ safe γ ˙ max , we can demonstrate that inequality (24) is not violated for every given value of γ ˙ d .
Furthermore, using a similar method, we consider the bound for γ ¨ d , max
γ ¨ d η ¯ γ safe + ϵ γ safe 2 κ 1 | | x T C ( 0 ) | | + κ 2 γ ¨ d , max + γ safe + ϵ γ safe 1 γ ˙ o , max ( 1 + γ ˙ o , max ) + γ safe + ϵ γ safe γ ¨ o , max ,
where
η ¯ = max 1 , max ω [ 1 η , 1 ] ρ ( ω ) d ρ ( ω ) d ω + ω d ρ ( ω ) d ω .
Choosing a value of γ safe that satisfies the following
γ safe 2 η ¯ γ ¨ d , max ( 1 + γ ˙ o , max ) γ ¨ max γ safe η ¯ γ ¨ d , max ( 1 + γ ˙ o , max ) ϵ γ ¨ max > 0 ,
it can be shown that γ ¨ d remains bounded as follows
γ ¨ d η ¯ γ safe + ϵ γ safe 2 ( κ 1 | | x T C ( 0 ) | | + κ 2 γ ¨ d , max | γ safe + ϵ γ safe 1 | γ ˙ o , max ) ( 1 + γ ˙ o , max ) + γ safe + ϵ γ safe γ ¨ o , max γ ¨ var < γ ¨ max ,
and thus inequality (25) is not violated.
Finally, to demonstrate collision avoidance, we show that Equation (28) is satisfied for all t 0 . Recall that by assumption γ δ , i ( t ) γ safe for some interval t [ 0 , t α ] (case 1). We perform a proof by contradiction, therefore we now assume that
γ δ , i ( t α ) = γ safe , γ ˙ δ , i ( t α ) < 0 .
In what follows we demonstrate (A20) to be false. First, we bound γ ˙ δ , i from below as follows:
γ ˙ δ , i ( t ) = γ ˙ i ( t ) γ ˙ o ( t ) = γ ˙ d ( t ) γ ˙ o ( t ) + γ ˙ i ( t ) γ ˙ d ( t ) γ ˙ d ( t ) γ ˙ o ( t ) | γ ˙ i ( t ) γ ˙ d ( t ) | .
From Equation (A10), it follows that at t = t α . We have
γ ˙ δ i ( t α ) γ ˙ d ( t α ) γ ˙ o ( t α ) κ 1 x T C ( 0 ) κ 2 sup t [ 0 , t α ] ( | γ ¨ d , max ( t ) | ) .
Using the definition of γ ˙ d ( t ) , we have
γ ˙ δ i ( t α ) γ safe + ϵ γ δ , i ( t α ) γ ˙ o ( t α ) γ ˙ o ( t α ) κ 1 x T C ( 0 ) κ 2 sup t [ 0 , t α ] | γ ¨ d , max | .
Since γ δ , i ( t ) γ safe for t [ 0 , t α ] , γ δ , i ( t α ) = γ safe and γ ˙ o ( t ) γ ˙ o , max + 1 , it follows that
γ ˙ δ i ( t α ) γ safe + ϵ γ safe ( γ ˙ o , max + 1 ) ( γ ˙ o , max + 1 ) κ 1 x T C ( 0 ) κ 2 sup t [ 0 , t α ] | γ ¨ d , max | .
By defining
ϵ min = γ safe ( κ 1 x T C ( 0 ) + κ 2 sup t [ 0 , t α ] | γ ¨ d , max | ) ,
with
0 < | | x T C ( 0 ) | | < γ ˙ max κ 2 γ ¨ var κ 1 ,
it follows that if ϵ ϵ min , as it is assumed in the theorem, then
γ ˙ δ i ( t α ) 0 ,
which contradicts (A20), completing the proof.

Appendix C. Proof of Equation (A5)

Consider the following time coordination control law:
γ ¨ = a L γ b D γ ˙ γ ˙ d 1 N L C γ ˙ χ I = a b L Q χ + a b L Q Q z b z + b C ζ + k b a C C Q χ ,
where
χ ˙ I = k C L γ .
Consider the following time coordination error vector:
χ = b ξ + Q z ,
and notice that
ξ = 1 b χ 1 b Q z .
Using (A4), the time derivative of χ can be written as
χ ˙ = b Q γ ˙ + Q ( γ ¨ γ ¨ d 1 N ) .
Recalling the properties of matrix Q, the equation above can be simplified to
χ ˙ = b Q γ ˙ + Q γ ¨ .
Using (A23), it follows that:
χ ˙ = a b L ¯ χ + b k a Q C C Q χ + a b L ¯ Q z + b Q C ζ .
Then, using a similar approach as the one followed above, we derive the dynamics of z and ζ . Using (A4), we obtain
z ˙ = ( b I a b L ) z a b L Q χ + b k a C C Q χ + b C ζ γ ¨ d 1 N .
Using (A4), (A24) and (A25), we obtain
ζ ˙ = k C L Q 1 b χ 1 b Q z γ ¨ d 1 N N L k a C Q χ ˙ .
After straightforward computations, the dynamics of ζ can be written as
ζ ˙ = k b a C Q Q C ζ b k 2 a 2 C Q Q C C Q χ γ ¨ d 1 N N L .
Thus, the dynamics presented in (A5) are derived.

References

  1. Digani, V.; Sabattini, L.; Secchi, C.; Fantuzzi, C. Ensemble Coordination Approach in Multi-AGV Systems Applied to Industrial Warehouses. IEEE Trans. Autom. Sci. Eng. 2015, 12, 922–934. [Google Scholar] [CrossRef]
  2. Bernard, M.; Kondak, K.; Maza, I.; Ollero, A. Autonomous transportation and deployment with aerial robots for search and rescue missions. J. Field Robot. 2011, 28, 914–931. [Google Scholar] [CrossRef] [Green Version]
  3. Sherman, T.; Tellez, J.; Cady, T.; Herrera, J.; Haideri, H.; Lopez, J.; Caudle, M.; Bhandari, S.; Tang, D. Cooperative Search and Rescue using Autonomous Unmanned Aerial Vehicles. J. Guid. Control Dyn. 2014, 37, 750–765. [Google Scholar] [CrossRef]
  4. Adaldo, A.; Mansouri, S.S.; Kanellakis, C.; Dimarogonas, D.V.; Johansson, K.H.; Nikolakopoulos, G. Cooperative coverage for surveillance of 3D structures. In Proceedings of the 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, Canada, 24–28 September 2017. [Google Scholar] [CrossRef]
  5. Capitan, J.; Merino, L.; Ollero, A. Cooperative decision-making under uncertainties for multi-target surveillance with multiples UAVs. J. Intell. Robot. Syst. 2016, 84, 371–386. [Google Scholar] [CrossRef]
  6. Hamer, M.; Widmer, L.; D’andrea, R. Fast generation of collision-free trajectories for robot swarms using GPU acceleration. IEEE Access 2018, 7, 6679–6690. [Google Scholar] [CrossRef]
  7. Ji, J.; Khajepour, A.; Melek, W.W.; Huang, Y. Path Planning and Tracking for Vehicle Collision Avoidance Based on Model Predictive Control With Multiconstraints. IEEE Trans. Veh. Technol. 2017, 66, 952–964. [Google Scholar] [CrossRef]
  8. Hausler, A.J.; Saccon, A.; Aguiar, A.P.; Hauser, J.; Pascoal, A.M. Energy-Optimal Motion Planning for Multiple Robotic Vehicles With Collision Avoidance. IEEE Trans. Control Syst. Technol. 2016, 24, 867–883. [Google Scholar] [CrossRef]
  9. Fiorini, P.; Shiller, Z. Motion planning in dynamic environments using velocity obstacles. Int. J. Robot. Res. 1998, 17, 760–772. [Google Scholar] [CrossRef]
  10. Huang, Y.; Chen, L.; Van Gelder, P. Generalized velocity obstacle algorithm for preventing ship collisions at sea. Ocean Eng. 2019, 173, 142–156. [Google Scholar] [CrossRef]
  11. Velasco, G.A.M.; Borst, C.; Ellerbroek, J.; Van Paassen, M.; Mulder, M. The use of intent information in conflict detection and resolution models based on dynamic velocity obstacles. IEEE Trans. Intell. Transp. Syst. 2015, 16, 2297–2302. [Google Scholar] [CrossRef]
  12. Chen, Y.F.; Liu, M.; Everett, M.; How, J.P. Decentralized non-communicating multiagent collision avoidance with deep reinforcement learning. In Proceedings of the 2017 IEEE International Conference on Robotics and Automation (ICRA), Singapore, 29 May–3 June 2017; pp. 285–292. [Google Scholar]
  13. Long, P.; Fanl, T.; Liao, X.; Liu, W.; Zhang, H.; Pan, J. Towards optimally decentralized multi-robot collision avoidance via deep reinforcement learning. In Proceedings of the 2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, QLD, Australia, 21–25 May 2018; pp. 6252–6259. [Google Scholar]
  14. Cappello, D.; Garcin, S.; Mao, Z.; Sassano, M.; Paranjape, A.; Mylvaganam, T. A hybrid controller for multi-agent collision avoidance via a differential game formulation. IEEE Trans. Control Syst. Technol. 2020, 1–8. [Google Scholar] [CrossRef]
  15. Mylvaganam, T.; Sassano, M.; Astolfi, A. A differential game approach to multi-agent collision avoidance. IEEE Trans. Autom. Control 2017, 62, 4229–4235. [Google Scholar] [CrossRef] [Green Version]
  16. Mylvaganam, T.; Sassano, M. Autonomous collision avoidance for wheeled mobile robots using a differential game approach. Eur. J. Control 2018, 40, 53–61. [Google Scholar] [CrossRef]
  17. Singh, Y.; Bibuli, M.; Zereik, E.; Sharma, S.; Khan, A.; Sutton, R. A Novel Double Layered Hybrid Multi-Robot Framework for Guidance and Navigation of Unmanned Surface Vehicles in a Practical Maritime Environment. J. Mar. Sci. Eng. 2020, 8, 624. [Google Scholar] [CrossRef]
  18. Sun, J.; Tang, J.; Lao, S. Collision avoidance for cooperative UAVs with optimized artificial potential field algorithm. IEEE Access 2017, 5, 18382–18390. [Google Scholar] [CrossRef]
  19. Eun, Y.; Bang, H. Cooperative control of multiple unmanned aerial vehicles using the potential field theory. J. Aircr. 2006, 43, 1805–1814. [Google Scholar] [CrossRef]
  20. Tony, L.A.; Ghose, D.; Chakravarthy, A. Avoidance maps: A new concept in uav collision avoidance. In Proceedings of the 2017 International Conference on Unmanned Aircraft Systems (ICUAS), IEEE, Miami, FL, USA, 13–16 June 2017; pp. 1483–1492. [Google Scholar]
  21. Lalish, E.; Morgansen, K.A. Distributed reactive collision avoidance. Auton. Robots 2012, 32, 207–226. [Google Scholar] [CrossRef]
  22. Cichella, V.; Choe, R.; Mehdi, B.S.; Xargay, E.; Hovakimyan, N.; Trujillo, A.C.; Kaminer, I. Trajectory generation and collision avoidance for safe operation of cooperating UAVs. In Proceedings of the AIAA Guidance, Navigation, and Control Conference, National Harbor, MD, USA, 13–17 January 2014; p. 0972. [Google Scholar]
  23. Mehdi, S.B.; Cichella, V.; Marinho, T.; Hovakimyan, N. Collision avoidance in multi-vehicle cooperative missions using speed adjustment. In Proceedings of the 2017 IEEE 56th Annual Conference on Decision and Control (CDC), Melbourne, VIC, Australia, 12–15 December 2017; pp. 2152–2157. [Google Scholar]
  24. Tabasso, C.; Cichella, V.; Mehdi, S.B.; Marinho, T.; Hovakimyan, N. Guaranteed Collision Avoidance in Multivehicle Cooperative Missions Using Speed Adjustment. J. Aerosp. Inf. Syst. 2020, 17, 436–453. [Google Scholar] [CrossRef]
  25. Xargay, E.; Kaminer, I.; Pascoal, A.; Hovakimyan, N.; Dobrokhodov, V.; Cichella, V.; Aguiar, A.; Ghabcheloo, R. Time-critical cooperative path following of multiple unmanned aerial vehicles over time-varying networks. J. Guid. Control Dyn. 2013, 36, 499–516. [Google Scholar] [CrossRef] [Green Version]
  26. Cichella, V.; Kaminer, I.; Dobrokhodov, V.; Xargay, E.; Choe, R.; Hovakimyan, N.; Aguiar, A.P.; Pascoal, A.M. Cooperative Path Following of Multiple Multirotors Over Time-Varying Networks. IEEE Trans. Autom. Sci. Eng. 2015, 12, 945–957. [Google Scholar] [CrossRef]
  27. Kaminer, I.; Pascoal, A.M.; Xargay, E.; Hovakimyan, N.; Cichella, V.; Dobrokhodov, V. Time-Critical Cooperative Control of Autonomous Air Vehicles; Butterworth-Heinemann: Oxford, UK, 2017. [Google Scholar]
  28. Cichella, V. Cooperative Autonomous Systems: Motion Planning and Coordinated Tracking Control for Multi-Vehicle Missions. Ph.D. Thesis, University of Illinois at Urbana-Champaign, Champaign, IL, USA, 2018. [Google Scholar]
  29. Tabasso, C.; Cichella, V. Multiple Leader-Follower Coordination for Cooperative Missions. In Proceedings of the AIAA Scitech 2021 Forum, Virtual Event, 19–21 January 2021; p. 1766. [Google Scholar]
  30. Choe, R.; Puig-Navarro, J.; Cichella, V.; Xargay, E.; Hovakimyan, N. Cooperative Trajectory Generation Using Pythagorean Hodograph Bézier Curves. J. Guid. Control Dyn. 2016, 39, 1744–1763. [Google Scholar] [CrossRef]
  31. Cichella, V.; Kaminer, I.; Walton, C.; Hovakimyan, N. Optimal motion planning for differentially flat systems using Bernstein approximation. IEEE Control Syst. Lett. 2018, 2, 181–186. [Google Scholar] [CrossRef]
  32. Cichella, V.; Kaminer, I.; Xargay, E.; Dobrokhodov, V.; Hovakimyan, N.; Aguiar, A.; António, M.; Pascoal, A. A Lyapunov-based Approach for Time-Coordinated 3D Path-Following of Multiple Quadrotors. In Proceedings of the 2012 IEEE 51st Annual Conference on Decision and Control (CDC), Maui, HI, USA, 10–13 December 2012; pp. 1776–1781. [Google Scholar] [CrossRef]
  33. Cichella, V.; Choe, R.; Mehdi, S.B.; Xargay, E.; Hovakimyan, N.; Dobrokhodov, V.; Kaminer, I.; Pascoal, A.M.; Aguiar, A.P. Safe Coordinated Maneuvering of Teams of Multirotor Unmanned Aerial Vehicles: A Cooperative Control Framework for Multivehicle, Time-Critical Missions. IEEE Control Syst. 2016, 36, 59–82. [Google Scholar] [CrossRef]
  34. Parrot AR Drone 2. Parrot. Available online: https://support.parrot.com/us/support/products/parrot-ar-drone-2 (accessed on 9 February 2021).
  35. TurtleBot 3 Burger. Robotis. Available online: https://www.robotis.us/turtlebot-3-burger-us/ (accessed on 9 February 2021).
  36. Loría, A.; Panteley, E. Uniform Exponential Stability of Linear Time-Varying Systems: Revisited. Syst. Control Lett. 2002, 47, 13–24. [Google Scholar] [CrossRef]
  37. Khalil, H.K. Nonlinear Systems; Prentice Hall: Englewood Cliffs, NJ, USA, 2002. [Google Scholar]
Figure 1. Cooperative control framework.
Figure 1. Cooperative control framework.
Robotics 10 00034 g001
Figure 2. Evolution of the pace of the mission on the left, and coordination error between leader and follower on the right.
Figure 2. Evolution of the pace of the mission on the left, and coordination error between leader and follower on the right.
Robotics 10 00034 g002
Figure 3. Evolution of the virtual time on the left, and coordination error between leader and follower on the right.
Figure 3. Evolution of the virtual time on the left, and coordination error between leader and follower on the right.
Robotics 10 00034 g003
Figure 4. Evolution of mission at three different time instants. The trajectory of the leader is shown in blue while the trajectories of follower is shown in red.
Figure 4. Evolution of mission at three different time instants. The trajectory of the leader is shown in blue while the trajectories of follower is shown in red.
Robotics 10 00034 g004
Figure 5. Experimental setup for the collision-avoidance experiment.
Figure 5. Experimental setup for the collision-avoidance experiment.
Robotics 10 00034 g005
Figure 6. Evolution of mission at three different time instants. The trajectory of the leader is shown in cyan while the trajectories of the three robots are shown in blue, green, and yellow, and the trajectory of the obstacle is shown in red. The nominal positions of the vehicles are also shown in a lighter shade of the color.
Figure 6. Evolution of mission at three different time instants. The trajectory of the leader is shown in cyan while the trajectories of the three robots are shown in blue, green, and yellow, and the trajectory of the obstacle is shown in red. The nominal positions of the vehicles are also shown in a lighter shade of the color.
Robotics 10 00034 g006
Figure 7. The figure on the left shows the distance between the ground robots and the obstacle shown as solid blue, yellow, and green lines along with the minimum required safety distance shown by the red dashed line. The light blue line shows the distance for robot 1 if the collision-avoidance algorithm was not used. We note that the distance between the leader and the obstacle is omitted, since a collision between the two is impossible. The figure on the right shows the inter-vehicle distances between the followers, along with the minimum safe distance being shown by the dashed red line.
Figure 7. The figure on the left shows the distance between the ground robots and the obstacle shown as solid blue, yellow, and green lines along with the minimum required safety distance shown by the red dashed line. The light blue line shows the distance for robot 1 if the collision-avoidance algorithm was not used. We note that the distance between the leader and the obstacle is omitted, since a collision between the two is impossible. The figure on the right shows the inter-vehicle distances between the followers, along with the minimum safe distance being shown by the dashed red line.
Robotics 10 00034 g007
Figure 8. Evolution of γ δ ( t ) .
Figure 8. Evolution of γ δ ( t ) .
Robotics 10 00034 g008
Figure 9. Evolution of the pace of the mission (top row), and evolution of the virtual time (bottom row) for case 2.
Figure 9. Evolution of the pace of the mission (top row), and evolution of the virtual time (bottom row) for case 2.
Robotics 10 00034 g009
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Tabasso, C.; Cichella, V.; Mehdi, S.B.; Marinho, T.; Hovakimyan, N. Time Coordination and Collision Avoidance Using Leader-Follower Strategies in Multi-Vehicle Missions. Robotics 2021, 10, 34. https://0-doi-org.brum.beds.ac.uk/10.3390/robotics10010034

AMA Style

Tabasso C, Cichella V, Mehdi SB, Marinho T, Hovakimyan N. Time Coordination and Collision Avoidance Using Leader-Follower Strategies in Multi-Vehicle Missions. Robotics. 2021; 10(1):34. https://0-doi-org.brum.beds.ac.uk/10.3390/robotics10010034

Chicago/Turabian Style

Tabasso, Camilla, Venanzio Cichella, Syed Bilal Mehdi, Thiago Marinho, and Naira Hovakimyan. 2021. "Time Coordination and Collision Avoidance Using Leader-Follower Strategies in Multi-Vehicle Missions" Robotics 10, no. 1: 34. https://0-doi-org.brum.beds.ac.uk/10.3390/robotics10010034

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop