A Unmanned Surface Vehicle (USV) is an autonomous or remotely operated system which is deployed and a wide area of water surface. Since the master plan was first officially released by US Navy in 2007, USVs have received much attention by ocean engineers [1]. As global positioning systems have become more compact and affordable, USVs have become more capable. As a group of autonomous vehicles, USVs are successfully deployed for military operations, search and rescue missions and environmental monitoring as well as tactical oceanography [2]-[4].

In particular, USVs can be used as a mobile interface between heterogeneous unmanned systems such as unmanned underwater vehicles (UUVs) under the sea surface and unmanned aerial vehicles (UAVs) over the sea surface. Acoustic devices are used to communicate with UUVs, and signals are converted and transferred to UAVs via radio frequency communication. Air to underwater data transmission is also a feasible example of USV as a mobile interface.

USVs can be deployed to form a decentralized network, distributed over a spatial area, to provide real-time sensory information with the benefits of scalability, modularity and robustness. A dynamic topology permits the formation of the USVs to optimally position and align its sensors to improve sensing metrics such as error covariance and signal-to-noise ratio (SNR), fast response to dynamically changing environments. Such a formation can then be made autonomous giving each USV decision making capabilities based on the information which is collected by its own sensors.

A human in the loop provides initial directives to a group of USVs regarding location, area of surveillance/mapping and data requested, and USVs then configure their operational mode depending on their required function. Deployment of USVs ultimately depends on the ability to position each vehicle so that it is able to collect data from its surrounding environment in an optimal manner. There are situations where the USVs will reach equilibrium with respect to their spatial distribution (topology), in which case the formation can essentially become stationary once such a configuration is reached.

Figure 1 shows the transition from the arbitrary initial USVs positions to the desired final distribution. To reach this final configuration, each vehicle exchanges information with a small subset of the formation, specifically those USVs which are within the range of its wireless communication or sensor capability. As the range of such hardware may be limited, the basic problem faced by a group of USVs is how to use local information to decide one’s motion so that a global goal is achieved. This is generally achieved by coming up with force-laws that translate the position and/or velocity information being exchanged by the vehicles into force commands for their actuators. [5] presents some force-laws which cause a group of agents to arrange itself in a pattern of hexagons or squares.

Figure 1: 
Move from their arbitrary initial positions to the desired topology

In literatures, motion control scenarios of USVs are usually classified into three main categories (point stabilization, trajectory tracking, and path following), along with the concept of path maneuvering [6]. Among those control issues, the goal of point stabilization is to stabilize the vehicle zeroing the position and orientation error with respect to a given target point with a desired orientation (in the absence of currents). The goal cannot be achieved with smooth or continuous state-feedback control laws when the vehicle has nonholonomic constraints.

Because of hardware constraints, force-laws cease to be effective when the robots move a certain distance away from each other and the graph representing the communication between vehicles keeps changing as the USVs move. Therefore, in addition to the final steady state of the formation, information about the transients is required.

In the following sections, stability properties of the formation are analyzed to determine transient properties, tracking performance and capability to reject noise or disturbances.

Let us start analysis by considering a network of a set of USVs, each having standard second order linear dynamics with viscous friction. Each USV has wireless communication devices which can function to a distance of say r units. All vehicles weigh 1 unit and are assumed to have identical dynamics and communication devices. As USVs move on sea surface, analysis is taken for 2-dimensional space. Then for i-th vehicle,

Here c is the viscous constant and f_ix and f_iy is the force that each USV exerts in the x and y direction respectively to propel itself so that the USV can reach to the final position with respect to other vehicles . The output is its current position x_i and y_i . So

Let n_n be number of vehicles in the network, and n_y be number of outputs per a vehicle = 2. It is assumed that the forces f_ix and f_iy have a certain structure as following.

In other words,

Here X is the stacked state vector of the entire system, i.e. X=[X1T...XnnT]T and Ψi:R4nn→R2 are possibly non-linear functions of X. The summation is over all the j "neighbors" of vehicle i, that is to say all the vehicles in the formation at a distance less than r units from the vehicle i. Let us consider a USVs where each vehicle behaves as if they are attached by springs of stiffness g and unstretched length r with their neighbors.

Then, the force being computed by each vehicle is,

where dij=(xi-xj)2+(yi-yj)2 , the distance between vehicles i and j. By setting U=[UiT...UnnT]T, and with Kronecker algebra notation,

But

where Ψ=[Ψ1T...ΨnnT]T and L is the graph Laplacian defined above. After substituting Equation (14) in Equation (13), we have

Using the property (P⊗Q)(R⊗S) = PR⊗QS, if the dimensions are appropriate and due to the fact that the number of inputs to each node equals the number of outputs, Equation (15) can be simplified to

Now, consider the first part of Equation (16),

Now let us consider the imaginary center of gravity (CoG) of the USV formation. Since the dynamics in the y-direction are analogous to the ones in the x-direction, we only write out the x dynamics of the system below. Then,

xcg=1nn∑i=1nnxi,x˙cg=1nn∑i=1nnx˙i

and

x¨cg=1nn∑i=1nnx¨i,x¨cg=1nn∑i=1nn(−cx˙i−gδxi)

Therefore,

Because the term ∑i=1nnδxi

is equivalent to 1^TLx and 1 is the eigenvector of the symmetric matrix L corresponding to the zero eigenvalue, the second term in Equation (18) is zero. Thus,

If the initial condition of the formation is such that ∑i=1nnx˙i=0 and ∑i=1nny˙i=0 , the CoG of the entire system is stationary. Equation (19) also shows that the dynamics of the CoG is not subject to inter-vehicle forces. The CoG of the system, if it is subject to a non zero initial velocity condition, will eventually come to rest.

Now if we define Z=[...zxiz˙xizyiz˙yi...]T where

Then, by substituting Equation (19) into Equation (17), we have

Now Z=X-[... xcg x.cg ycg y.cg]T . Therefore, we have

For the matrices B, C and any L, the second term of Equation (22) is zero. This is because the 1^T vector is and eigenvalue of L corresponding to the zero eigenvalue, and we have (L⊗BC)Z = (L⊗BC)X - (L⊗BC. Hence, we can rewrite Equation (21) as

Even though Equation (23) looks like a linear dynamical equation, the graph Laplacian is not constrained to be constant. It varies as a discontinuous function of the vehicle positions and thus the right hand side of this equation is discontinuous. The set of points at which it changes value are ones where one or more pairs of vehicles in the formation are at a distance r from each other. Between such points, there is a continuum of points where the Laplacian is constant.

It is notable that since the number of USVs is finite, there are a finite number of possible graphs, connected or disconnected. Thus there is a finite number of points at which a change of Laplacian takes place.

Let Ω be the set of zero measure of points at which the L matrix switches value and Ω_l, l = 1,2,...,q be the continuous sets of non-zero measure in which the graph is constant with the Laplacian L_l. Then the absolutely continuous function X(t) is a Filippov solution ([7] and Equation (6)) of Equation (23) if it satisfies the differential inclusion,

When the current state of formation Z(t) ∈ Ω_l, then K[f(Z)](Z) = f(Z). At the points of discontinuity, the derivative Z. lies in the convex hull of the points representing the limits of the value of Z. as Z approaches the point of discontinuity from various directions. So

K[f(Z)](Z)=∑l=1qαl(Inn⊗A-gLl⊗BC)Z αl≥0,∑lαl=1=(Inn⊗A)Z-g∑l=11αl(Ll⊗BC)Z=[z.ξ,(-cz.ξ-g∑l=1qαlδzξl),z.yi,(-cz.yi-g∑l=1qαlδzξl)]T

where i = 1,2...,n_n. At points Z ∈ Ω_l, α_l=1 and all other α_l = 0. δz_xil and δz_yil are δz_zi and δz_yi corresponding to the graph represented by the Laplacian L_l.

To check the stability of the system described in Equation (23) which has a dynamic equation with discontinuous right hand side, we start with the Lyapunov Stability Theorem.

Lyapunov Theorem: Let x.=f(x) be essentially locally bounded and 0∈K[f(x)](0) in a domain D ⊂ Rⁿ containing x = 0. Let x(⋅) be a Filippov solution of the system. Let V(x) : Rⁿ→R be a Lipschitz, regular function. Then,

1. V(x) is asolutely continuous, V.(x) exists almost everywhere and

ddtV(x)∈a.eV˜˙(x)

where V˜˙(x):=∪ξ∈∂V(x)ξTK[f](x), and ∂ V(x) is the generalized gradient of V(x). In addition, the function V(x) satisfies that V(0) = 0, and V(x) ≥ 0 in D - {0}.

2. V˜˙(x)<0 in D implies x = 0 is a stable equilibrium point.

3. V˜˙(x)<0 in D - {0} implies x = 0 is an asymptotically stable equilibrium point.

Proof: See [9] and [10]. ￭

We not state the stability of the system described in the previous section.

Corollary 1: The dynamic system represented by Equation (23) is stable.

Proof: Let us choose the following Lyapunov function

where zx, z.x, zy, z.y are the vectors in R4nn representing the positions and velocities of the vehicles with respect to the CoG. This function is defined on the domain D = R4nn . The matrix L, representing a connected graph, has a single zero eigenvalue whose eigenspace is spanned by the vector. Hence the given Lyapunov function can have value zero at the non-zero state vector Z. However, this value of the state vector, physically means that all the vehicles are converged at one single point while the CoG of the system is at a point (a,b) units away from them. This is clearly impossible unless both a and b are zero. Hence the state-space for this problem, naturally excludes the eigen-space corresponding to the zero eigen- vector of the connected L matrix. Hence the Lyapunov Function chosen is positive definite. Also note that V(Z) is a discontinuous function of Z because of the discontinuity of L. Hence we have to define the generalized gradient of V(Z) as

where i = 1,2,...n_n. At point Z ∈ Ω_l and α_l=1, all other α_l = 0. Then, from Lyapunov theorem and Equations (26),

Now in the regions Z ∈ Ω_l, α_l = β_l = 1, and all other α_l = β_l = 0 and the summation in the equation simplifies to

∑i=1nn-cx.i2-cy.i2≤0 ∀X. When the corresponding αs and βs match, the summation in Equation (27) simplifies as above but at other times, its value is indefinite. However, V˜˙ is an intersection of all these sets and since we have some sets which are strictly non-positive, the intersection of all these sets is strictly non-positive. So

Therefore, the system is stable with Lyapunov theorem. ￭

We now attempt to use the discontinuous version of the LaSalle’s theorem from [10] to get a better idea of the equilibrium states of the system.

LaSalle’s Theorem: Let Γ be a compact set such that the Filippov solution to the autonomous system x.=f(x) , x(0) = x₀ starting in Γ is unique and remains in Γ for all t ≥ t₀ . Let V:Γ→R be a time independent regular function Lsuch that υ ≤ 0 for all υ∈V˜˙. Define S={x∈Γ0∈V˜˙} . Then every trajectory in Γ converges to the largest invariant set M, in the closure of S.

Proof: See [10]. ￭

Corollary 2: The dynamic system represented by Equation (23) is asymptotically stable about its Center of Gravity, i.e. around Z = 0.

Proof: Consider the function V defined in Equation (23). This function is defined on a large enough ball Γ of R^4n_n. This can be done because as stated above the final states of the system are bounded. From Equation (28), we know that the set S={Z∣z.x=0, z.y=0} . The largest invariant set in S is M={Z∣zx=0, zy=0, z.x=0, z.y=0} . This is true because of our assumption of connectedness of the graph which implies that L has only a single zero eigen-value with corresponding eigenvector 1 and because as argued above, a and b have to be zero. Hence by applying Lasalle’s Theorem, we can conclude that all the vehicles will converge to a single point in the 2-dimensional space, which will also be its center of gravity. The CoG has been shown to be always stable and bounded above. Hence, the system is asymptotically stable around its C.G. ￭

Corollary 3: For the dynamical system in Equation (23), there exists a positive constant a independent of t₀ and a class KL function β(.,.) such that

∥Z(t)∥≤β(∥Z(to)∥,t-t0),∀t≥to≥0,∀∥Z(t0)∥<α

Furthermore, this bound is of the form

Proof: The dynamical system in Equation (23) is asymptotically stable as shown above. Also, this stability is independent of t₀. Hence it is also uniformly asymptotically stable. In addition, the dynamics of the system are piecewise continuous in t and locally Lipschitz in Z. Hence, using the definition of uniform asymptotic stability from [9], Equation (18) holds. Furthermore the dynamics of the system are piecewise constant and linear. The states of the system are thus continuous, though not differentiable, exponential functions. Thus the Equation (19) holds for some k and some γ. ￭

To verify above results, let us design a force law which acts like a spring of unstretched length d attached between neighboring vehicles as described in equation.

fix=Ψix(X)-g∑j∈Ni(xi-xj)=gd∑j∈Ni(xi-xj)r-gδxi

fiy=Ψiy(X)-g∑j∈Ni(yi-yj)=gd∑j∈Ni(yi-yj)r-gδyi

Three vehicles are initially positioned at (0,0), (300,100), (-200,300) with zero velocities. As shown in Figure 4, the state norm of the entire vehicles is maintained within a limit. The connectivity is assumed to be lost when the distance between the vehicles is larger than 400m. d is set to be 100N/m,

Figure 4: 
Variation of state norm for a system with the force law

To keep the formation of a group of USVs, it is necessary to set the relationship between vehicles and forcing functions such as potential fields have been widely used in multi-agent systems. The system including the forcing mechanism is discontinuous in nature as the analysis is not limited to a constant topology. However, an assumption is made that the communication topology, while changing, remains connected at all times. Filippov’s calculus of differential equations with discontinuous right hand sides is used in the analysis. The stability analysis is then used to come up with converse Lyapunov theorems for the discontinuous system. This result is expected to be used in designing force law to deploy and keep formation for multiple surface vehicles which usually have strong nonlinearities in both system dynamics and forcing laws. Environmental forces such as hydrodyanmics terms will be incorporated to represent more realistic systems.