Stable emergent formations for a swarm of autonomous car-like vehicles

Abstract

A biological swarm is an ideal multi-agent system that collectively self-organizes into bounded, if not stable, formations. A mathematical model, developed appropriately from some principle of swarming, should enable one, therefore, to study formation strategies for multiple autonomous robots. In this article, based on the hypothesis that swarming is an interplay between long-range attraction and short-range repulsion between the individuals in the swarm, a planar individual-based or Lagrangian swarm model is constructed using the Direct Method of Lyapunov. While attraction ensures the swarm is cohesive, meaning that the individuals in the swarm remain close to each other at all times, repulsion ensures that the swarm is well-spaced, meaning that no two individuals in the swarm occupy the same space at the same time. Via a novel Lyapunov-like function with attractive and repulsive components, the article establishes the global existence, uniqueness, and boundedness of solutions about the centroid. This paves the way to prove that the swarm model, governed by a system of first-order ordinary differential equations (ODEs), is cohesive and well-spaced. The article goes on to show that the artificial swarm can collectively self-organize into two stable formations: (i) a constant arrangement about the centroid when the system has equilibrium points, and (ii) a highly parallel formation when the system does not have equilibrium points. Computer simulations not only illustrate these but also reveal other emergent patterns such as swirling structures and random-like walks. As an application, we tailor the model accordingly and propose new autonomous steering laws giving rise to pattern-forming for multiple nonholonomic car-like vehicles.

Keywords

Multi-agent system formation control pattern formation Lagrangian swarm Lyapunov stability

Introduction

An interesting research domain in robotics is formation control. This involves the design of controllers for multiple mobile agents such that the agents move in some bounded, if not stable, formation without colliding with each other or with obstacles.¹ Recent applications are seen in the control of pattern formation of fleets of autonomous car-like vehicles or swarms of unmanned aerial vehicles for tasks such as aiding traffic management of automated highways, environmental monitoring, search-and-rescue in hazardous environments, and area coverage and reconnaissance.^2
–4

An exciting development in this area of research is the use of swarm principles to design the controllers. Animal swarming is considered an instance of collective self-organization, which is defined in the study by Camazine et al.⁵ as “a broad range of pattern-formation processes in both physical and biological systems, with the pattern being an emergent property of the system, rather than a property imposed on the system by an external ordering influence.” It has been hypothesized that animal swarming is an interplay between long-range attraction and short-range repulsion between the individuals in the swarm; attraction ensures a cohesive swarm while repulsion ensures a well-spaced swarm.^6
–8 An artificial swarm model developed appropriately from such a notion should thus exhibit emergent patterns such as (i) constant arrangements about a stationary centroid as seen, for example, in myxobacterial fruiting body formation,^9,10 (ii) parallel formations seen in columns of ants,^11,12 (iii) circular or oscillatory formations such as milling structures in schools of fish,¹³ and (iv) random walks such as the Lévy flight which describes a seemingly random but bounded pattern of foraging and animal hunting.¹⁴ An exhaustive list of emergent patterns is provided in the study by Camazine et al.⁵ An interesting new direction of enquiry in formation control deals with how to control an artificial swarm to settle into a desired pattern.¹⁵

The efforts of researchers over the last three decades to understand swarming have resulted in two different approaches to modeling; the Eulerian and the Lagrangian approaches.¹⁶ In the Eulerian approach, the swarm is considered a continuum described by its density in one-, two- or three-dimensional space. The time evolution of swarm density is described by partial differential equations. In the Lagrangian approach, the state (position, instantaneous velocity and instantaneous acceleration) of each individual and its relationship with other individuals in the swarm is studied; it is an individual-based approach, in which the velocity and acceleration can be influenced by spatial coordinates of the individual. The time evolution of the state is described by ordinary or stochastic differential equations. A review of different approaches can be found in the study by Carrillo et al.¹⁷ A recent analysis of cohesiveness in a Lagrangian-type model incorporating collision avoidance is given in the study by Li.¹⁸

An alternative approach to understanding coherent swarm structures can be traced to the work of physicists who consider individuals in a swarm as self-propelling particles governed by discrete equations.¹⁹ These models of discrete swarm structure use iterative methods which provide recursion formulas that update the position, velocity, and orientation of an individual with respect to other individuals. Extensive simulations are required to validate the models, the simplest of which merely assume that individuals move at a constant speed, and, at each time step, each one travels in the average direction of motion of those within a local neighborhood. A similar approach adopted by computer scientists is called the particle swarm optimization, wherein the velocity and position of a point mass is governed by a computer algorithm rather than differential or discrete equations. A recent survey of methods can be found in.²⁰

The swarm model proposed in this study is individual-based or Lagrangian. Adopting the hypothesis that swarming is an interplay between long-range attraction and short-range repulsion between the individuals in the swarm, we consider spacing between individuals, each of which moves with the velocity of the swarm centroid, of primary importance. While attraction ensures cohesiveness, meaning that the individuals in the swarm remain close to each other at all times, repulsion ensures it is well-spaced, meaning that no two individuals in the swarm occupy the same space at the same time. To our knowledge, the cohesiveness and well-spaced notions are being treated for the first in a rigorous manner in this article. The method utilized is the Direct Method of Lyapunov via which a Lyapunov-like function with attractive and repulsive components is constructed. The function enables us to establish the existence, uniqueness, and boundedness of solutions about the centroid. This paves the way to prove that the swarm model, governed by a system of first-order ordinary differential equations (ODEs), is cohesive and well-spaced. We go on to show that the model can collectively self-organize into two stable formations: (i) a constant arrangement about the centroid when the system has equilibrium points, and (ii) a highly parallel formation when the system has no equilibrium points. Computer simulations not only illustrate these but also reveal other emergent patterns such as swirling structures and random-like walks. The results in this article are new or are a refinement of the author’s work thus far in this area.^21,22

We begin by developing the model in the “A two-dimensional Lagrangian swarm model” section, deriving the velocity controller of each individual via a Lyapunov-like function in the “Velocity controllers” section and discussing the properties of the function in the “Roles of the parameters in the Lyapunov-like function” section. Before we provide the main result of this article in the “A well-placed and cohesive system” section, which is on boundedness, we give several illuminating and insightful examples of the model dynamics in the “Examples of system behavior” section. We then proceed to look at situations when equilibrium points can exist (“Equilibrium points of system (4)” section) and when they cannot, in which case a pattern emerges, namely the parallel formation (“Parallel formation in the absence of equilibrium” section). The results are applied accordingly to a swarm of autonomous nonholonomic planar vehicles (“Application to planar mobile car-like vehicles” section).

A two-dimensional Lagrangian swarm model

We begin the construction of our swarm model by adopting two terms from Mogilner et al.¹⁶ as working definitions of a swarm. The rigorous definitions of the terms are given at the end of this section.

A system is well-spaced if the system represents a group which does not collapse into a tight cluster.

A system is cohesive if the system represents a group in which the distances between individuals in the group are bounded from above.

A swarm is a well-spaced and cohesive system that represents a group or aggregate of individuals.

Consider a swarm of $n \in ℕ$ individuals. Following previous work such as those in Mogilner et al.¹⁶ and Gazi and Passino,⁶ we consider the individuals as point masses. At time $t \geq 0$ , let $(x_{i} (t), y_{i} (t))$ , $i = 1, 2, \dots, n$ , be the planar position of the ith individual, which we shall define as a point mass residing in a disk of radius $r_{V} > 0$ ,

A_{i} : = {(z_{1}, z_{2}) \in ℝ^{2} : (z_{1} - x_{i})^{2} + {(z_{2} - y_{i})}^{2} \leq r_{V}^{2}}

The disk is described in Mogilner et al.¹⁶ as a bin, and in Gazi and Passino⁶ as a private or safety area of each individual. We shall use the former term, with the bin size being the radius r_V of the disk. As noted in Mogilner et al.,¹⁶ the members of a cohesive swarm tend to stay together and avoid dispersing. In a well-spaced swarm, some minimal bin size exists such that each bin contains at most one individual. Moreover, the size of such a bin is independent of the number of individuals in the group.

Let us define the centroid of the swarm as

(x_{C}, y_{C}) : = (\frac{1}{n} \sum_{k = 1}^{n} x_{k}, \frac{1}{n} \sum_{k = 1}^{n} y_{k})

At time $t \geq 0$ , let $(v_{i} (t), w_{i} (t)) : = ({x^{'}}_{i} (t), {y^{'}}_{i} (t))$ be the instantaneous velocity of the ith point mass. Using the above notations, we have thus a system of first-order ODEs for the ith individual, assuming the initial condition at $t = t_{0} \geq 0$

{x^{'}}_{i} (t) = v_{i} (t), {y^{'}}_{i} (t) = w_{i} (t), x_{i 0} : = x_{i} (t_{0}), y_{i 0} : = y_{i} (t_{0})

Suppressing t, we let $x_{i} : = (x_{i}, y_{i}) \in ℝ^{2}$ and $x : = (x_{1}, \dots, x_{n}) \in ℝ^{2 n}$ be our state vectors. Also, let $x_{0} = (x_{10}, y_{10}, \dots, x_{n 0}, y_{n 0}) : = x (t_{0}) \in ℝ^{2 n}$ . If the instantaneous velocity $(v_{i}, w_{i})$ has a state feedback law of the form $(v_{i} (t), w_{i} (t)) = (- μ_{i} f_{i} (x (t)), - φ_{i} g_{i} (x (t)))$ , $i \in 1, \dots, n$ , for some constants $μ_{i}, φ_{i} > 0$ and some continuous functions $f_{i} (x (t))$ and $g_{i} (x (t))$ , to be constructed appropriately later, and if we define $g_{i} (x) : = (- μ_{i} f_{i} (x), - φ_{i} g_{i} (x)) \in ℝ^{2}$ and $G (x) : = (g_{1} (x), \dots, g_{n} (x)) \in ℝ^{2 n}$ , then our swarm of n individuals is

\overset{•}{x} = G (x), x_{0} = x (t_{0})

If the system has an equilibrium point, we shall denote it by

x_{e} : = (x_{1 e}, x_{2 e}, \dots, x_{n e}) : = (x_{1 e}, y_{1 e}, x_{2 e}, y_{2 e}, \dots, x_{n e}, y_{n e}) \in ℝ^{2 n}

We end this section by rigorously defining a well-spaced and cohesive system. Let $x_{C} : = (x_{C}, y_{C}, \dots, x_{C}, y_{C}) \in ℝ^{2 n}$ ,

∥ x - x_{C} ∥ : = \sqrt{\sum_{i = 1}^{n} [{(x_{i} - x_{C})}^{2} + {(y_{i} - y_{C})}^{2}]},

and $d_{i C} : = \sqrt{{[x_{i} - x_{C}]}^{2} + {[y_{i} - y_{C}]}^{2}},$ for $i = 1, \dots, n$ .

Definition 2.1

System (4) is well-spaced if the solution of system (4) exists for all $t \geq 0$ and

d_{i j} (t) : = ∥ x_{i} (t) - x_{j} (t) ∥ = \sqrt{{[x_{i} (t) - x_{j} (t)]}^{2} + {[y_{i} (t) - y_{j} (t)]}^{2}} > 2 r_{V}

for all $i, j = 1, \dots, n$ , $i \neq j$ , and $t \geq 0$ .

Lemma 2.2

If system (4) is well-spaced, then $r_{V} < ∥ x (t) - x_{C} (t) ∥$ for all $t \geq 0$ .

Proof

If the outcome of Lemma 2.2 is false, then there must be a time $t^{'} \geq 0$ such that $∥ x (t^{'}) - x_{C} (t^{'}) ∥ \leq r_{V}$ . Then for every $i = 1, \dots, n$ , we have that $d_{i C} (t^{'}) \leq ∥ x (t^{'}) - x_{C} (t^{'}) ∥ \leq r_{V}$ . Consequently, for some two $i, j$ , $i \neq j$ , $i, j = 1, \dots, n$ , it is possible that $d_{i j} (t^{'}) \leq d_{i C} (t^{'}) + d_{i C} (t^{'}) \leq 2 r_{V}$ , which contradicts Definition 2.1.

Note if $n = 1$ , then $∥ x - x_{C} ∥ = 0$ . Hence, the idea of a well-spaced swarm makes sense only if $n \geq 2$ .

For cohesiveness, we adopt the following rigorous definition by Lemmon and Sun²³:

Definition 2.3

System 4 is cohesive if there exist real constants $\bar{K}, \underline{K} > 0$ such that ${lim sup}_{t \to \infty} ∥ x (t) - x_{C} (t) ∥ \leq \bar{K}$ and ${lim inf}_{t \to \infty} ∥ x (t) - x_{C} (t) ∥ \geq \underline{K}$ .

Obviously the two limits exist if $∥ x (t) - x_{C} (t) ∥ < \infty$ for all $t \geq 0$ .

Velocity controllers

Our control objective is to construct the functions $f_{i} (x (t))$ and $g_{i} (x (t))$ , and hence the instantaneous velocity $(v_{i} (t), w_{i} (t))$ , $t \geq 0$ , for every individual $i = 1, \dots, n$ , via a Lyapunov-like function that should establish the boundedness and therefore the cohesiveness of system (4).

Attraction to the centroid

We can ensure that individuals are attracted to each other and also form a cohesive group by having a measure of the distance from the ith individual to the swarm centroid. This is the concept behind flock-centering or cohesion, which is one of the well-known three heuristic flocking rules of Reynolds’ applied to virtual agents he called boids ²⁴:

Separation: Each boid must steer to avoid colliding with local flock-mates;

Alignment: Each boid must steer toward the average heading of local flock-mates; and

Cohesion: Each boid must steer to move toward the average position (center of mass or centroid) of local flock-mates.

Flock-centering minimizes the exposure of a member of a flock to the flock’s exterior by having the member move toward the perceived center of the flock. It is therefore a form of attraction between individuals. Centering necessitates a measure of the distance from the ith individual to the swarm centroid. For this purpose, we consider the function

R_{i} (x) : = \frac{1}{2} [{(x_{i} - x_{C})}^{2} + {(y_{i} - y_{C})}^{2}] + ε_{i}^{2}, i = 1, \dots, n

where $ε_{i} > 0$ are sufficiently small constants. As we shall see later, the role of the constants is to ensure that system (4) has a global solution $x (t)$ which is defined for all time $t \geq 0$ . We remind ourselves of the importance of the existence of global solutions for system (4) to be well-spaced (see Definition 2.1).

Interindividual collision avoidance

The short-range repulsion between individuals necessitates utilizing a measurement of the distance between the i th and the j th individuals, $j \neq i$ , $i, j = 1, \dots, n$ . For this purpose, we consider the function

Q_{i j} (x) : = \frac{1}{2} [{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2} - {(2 r_{V})}^{2}]

A Lyapunov-like function

To obtain the appropriate instantaneous velocity of the individuals, we construct a Lyapunov-like function. Accordingly, let there be constants $γ_{i} > 0$ and $β_{i j} > 0$ , and define, for $i, j = 1, \dots, n$

L_{i} (x) : = γ_{i} R_{i} (x) + \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j} R_{i} (x)}{Q_{i j} (x)}

Consider as a tentative Lyapunov-like function for system (4)

L (x) : = \sum_{i = 1}^{n} L_{i} (x_{i})

It is positive over the domain

D (L) : = {x \in ℝ^{2 n} : Q_{i j} (x) > 0 \forall i, j = 1, \dots, n, i \neq j}

The time-derivative of L along every solution of system (4) is

{\overset{•}{L}}_{(4)} (x) = \sum_{i = 1}^{n} (γ_{i} {\overset{•}{R}}_{i} (x) + \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j}}{Q_{i j} (x)} {\overset{•}{R}}_{i} (x) - \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j} R_{i} (x)}{Q_{i j}^{2} (x)} {\overset{•}{Q}}_{i j} (x))

where

\sum_{i = 1}^{n} {\overset{•}{R}}_{i} (x) = \sum_{i = 1}^{n} [(x_{i} - \frac{1}{n} \sum_{k = 1}^{n} x_{k}) - \frac{1}{n} \sum_{m = 1}^{n} (x_{m} - \frac{1}{n} \sum_{k = 1}^{n} x_{k})] {x^{'}}_{i} + \sum_{i = 1}^{n} [(y_{i} - \frac{1}{n} \sum_{k = 1}^{n} y_{k}) - \frac{1}{n} \sum_{m = 1}^{n} (y_{m} - \frac{1}{n} \sum_{k = 1}^{n} y_{k})] {y^{'}}_{i}

Noting that $\frac{1}{n} \sum_{m = 1}^{n} (u_{m} - \frac{1}{n} \sum_{k = 1}^{n} u_{k}) = 0$ for any $u_{i} \in ℝ$ , $i = 1, 2, \dots, n$ , we simplify the expression to

\sum_{i = 1}^{n} {\overset{•}{R}}_{i} (x) = \sum_{i = 1}^{n} [(x_{i} - \frac{1}{n} \sum_{k = 1}^{n} x_{k}) x_{i}' + (y_{i} - \frac{1}{n} \sum_{k = 1}^{n} y_{k}) {y^{'}}_{i}]

Also, we can show that

\sum_{i = 1}^{n} \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} {\overset{•}{Q}}_{i j} (x) = 2 \sum_{i = 1}^{n} \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} (x_{i} - x_{j}) {x^{'}}_{i} + 2 \sum_{i = 1}^{n} \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} (y_{i} - y_{j}) {y^{'}}_{i}

Collecting terms with $x_{i}'$ and $y_{i}'$ , and substituting ${x^{'}}_{i} = {\overset{•}{x}}_{i} = v_{i}$ and ${y^{'}}_{i} = {\overset{•}{y}}_{i} = w_{i}$ from system (3), we have, along a trajectory of system (4) (on suppressing $x$ )

{\overset{•}{L}}_{(4)} = \sum_{i = 1}^{n} {(γ_{i} + \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j}}{Q_{i j}}) (x_{i} - \frac{1}{n} \sum_{k = 1}^{n} x_{k}) - 2 \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j} R_{i}}{Q_{i j}^{2}} (x_{i} - x_{j})} {\overset{•}{x}}_{i} + \sum_{i = 1}^{n} {(γ_{i} + \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j}}{Q_{i j}}) (y_{i} - \frac{1}{n} \sum_{k = 1}^{n} y_{k}) - 2 \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j} R_{i}}{Q_{i j}^{2}} (y_{i} - y_{j})} {\overset{•}{y}}_{i}

Let

f_{i} : = f_{i} (x) = (γ_{i} + \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j}}{Q_{i j}}) (x_{i} - \frac{1}{n} \sum_{k = 1}^{n} x_{k}) - 2 \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j} R_{i}}{Q_{i j}^{2}} (x_{i} - x_{j})

and

g_{i} : = g_{i} (x) = (γ_{i} + \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j}}{Q_{i j}}) (y_{i} - \frac{1}{n} \sum_{k = 1}^{n} y_{k}) - 2 \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j} R_{i}}{Q_{i j}^{2}} (y_{i} - y_{j})

Thus

{\overset{•}{L}}_{(4)} = \sum_{i = 1}^{n} (f_{i} {x^{'}}_{i} + g_{i} {y^{'}}_{i}) = \sum_{i = 1}^{n} (f_{i} v_{i} + g_{i} w_{i})

Let there be numbers $μ_{i} > 0$ and $φ_{i} > 0$ such that

v_{i} : = - μ_{i} f_{i} and w_{i} : = - φ_{i} g_{i}

Then

{\overset{•}{L}}_{(4)} (x) = - \sum_{i = 1}^{n} [μ_{i} f_{i}^{2} (x) + φ_{i} g_{i}^{2} (x)] \leq 0

for all $x \in D (L)$ .

We have thus obtained a simple Lagrangian swarm model in the form of system (4) with components (3), where the velocity components are given in (11).

Roles of the parameters in the Lyapunov-like function

As we shall see in later sections, the parameters in the Lyapunov-like function play the major role in inducing a particular stable pattern. In this section, we provide an overview of the roles of the parameters.

Consider again our Lyapunov-like function (7). At large distances between the i th and the j th individuals, the ratio

\sum_{i = 1}^{n} \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j} R_{i} (x)}{Q_{i j} (x)}

is negligible, and the term $\sum_{i = 1}^{n} γ_{i} R_{i} (x)$ dominates and acts as the attraction function; each individual is attracted to the centroid, and therefore system (4), as we shall show rigorously in the “A well-placed and cohesive system” section, maintains cohesiveness at all times. Thus, the parameter $γ_{i} > 0$ can be considered as a measurement of the strength of attraction between an individual i and the swarm centroid $(x_{C}, y_{C})$ . The smaller the parameter is, the weaker the cohesion of the swarm is. Hence, $γ_{i}$ can be called a cohesion parameter.

Consider now the situation where any two individuals i and j approach each other. In this case, $Q_{i j}$ decreases and ratio (12) increases, with $β_{i j} > 0$ acting as a coupling parameter that is a measurement of the strength of interaction between the individuals. In this way, ratio (12) acts as an interindividual collision avoidance function, because it can be allowed to increase in value (corresponding to avoidance) as individuals approach each other. However, as we show rigorously in the “A well-placed and cohesive system” section, collision avoidance occurs without the danger of the individuals getting too close to each other, or the swarm collapsing on itself; simply put, $Q_{i j} = 0$ is not possible in $D (L)$ . We have therefore met the short-range repulsion requirement in an individual-based model. Note that the increase in the ratio (12) does not translate to an increase in $L \equiv L (t)$ , simply because L is nonincreasing in t and any increase in the ratio gives a smaller or the same value of L at time t compared to all previous values of L.

We have used two other parameters, $μ_{i} > 0$ and $φ_{i} > 0$ in system (4). Because the parameters are a measure of the rate of decrease of $L \equiv L (t)$ at time $t \geq 0$ , we name them convergence parameters. The larger the convergence parameters, the quicker the movements of the individuals toward and about the centroid.

In summary, the cohesion parameters ( $γ_{i} > 0$ ), the coupling parameters ( $β_{i j} > 0$ ), and the convergence parameters ( $μ_{i}, φ_{i} > 0$ ) make up the control parameters of the system.

Examples of system behavior

Before we consider the existence, uniqueness, and boundedness of solutions of system (4) in the next section, we look at some interesting dynamics of the system. These illustrations will deepen our intuitive insight into the behavior of the solutions.

Example 5.1 (constant arrangement about the centroid)

In this example, we consider a swarm of three individuals, each with bin size $r_{V} = 1 / 2$ . With $ε_{i} {= 10}^{- 6}$ and the control parameters set at $μ_{i} = φ_{i} = γ_{i} = β_{i j} = 1$ , $i, j = 1, 2, 3$ , it is seen in Figure 1 that system (4) has an equilibrium point.

Figure 1.

The initial positions of the three point masses A₁, A₂, and A₃ are shown in diagram (a). They are $x_{1} (0) = (21.3, 15.9)$ , $x_{2} (0) = (10.2, 4.6)$ , and $x_{3} (0) = (8.4, 14.7)$ , respectively. Diagram (b) shows the positions where A₁, A₂, and A₃ ceased motion. They are $x_{1 e} = (14.9, 11.6)$ , $x_{2 e} = (13.8, 10.3)$ , and $x_{3 e} = (13.2, 11.9)$ , respectively. Thus, $x_{e} = (x_{1 e}, x_{2 e} . x_{2 e})$ . Diagram (c) shows the monotonic Lyapunov-like function with $4.5 \leq L \leq 89.8$ and $- 174.6 \leq d L / d t \leq 0$ for all $t \geq 0$ . Diagram (d) shows that the solution $x$ are bounded about the centroid $x_{C}$ .

Example 5.2 (parallel formation)

In this example, with $n = 10$ individuals, each with bin size $r_{V} = 1 / 2$ , the swarm eventually moves in a straight line, with the each individual heading in the same direction and angle. The individuals A₄, A₇, A₆, and A₅ follow the centroid’s trajectory (central thick line in Figure 2), with the emergent leader being A₄. The others follow paths parallel to it, with A₁, A₃, A₈, and $A_{10}$ in the outer lanes, and A₂ and A₉ in the inner lanes.

Figure 2.

With the given initial positions shown in (a), and the choices $ε_{i} {= 10}^{- 6}$ and $μ_{i} = ϕ_{i} = γ_{i} = β_{i j} = 1$ , $i, j = 1, \dots,8$ , the point masses eventually move in a parallel formation, as shown in diagram (b) by $t = 50$ units of time. In diagram (c), the monotonic Lyapunov-like function is shown, with $109.28 \leq L \leq 657.04$ and $- 1058.14 \leq d L / d t \leq - 0.91$ which implies that the system of point masses does not cease motion and eventually cruises with a constant speed. Diagram (d) shows that the solution $x$ of system (4) is bounded about the centroid.

Example 5.3 (swirling structure)

In this example, with $n = 12$ , the point masses, each with bin size $r_{V} = 1 / 2$ , seem to wander randomly before settling down to a swirling pattern. The cohesion parameters, γ_i, are set at 1, the coupling parameters, $β_{i j}$ , are randomized between and including 1 and 30, and the convergence parameters, μ_i and φ_i, at set at 1. The constants ε_i are chosen to be $10^{- 6}$ . Figure 3 shows the positions of the point masses at $t = 387$ units of time, the monotone nature of the Lyapunov-like function, and the boundedness of solution $x$ with respect to the centroid $x_{C}$ .

Figure 3.

The dashed line in diagram (a) plots the trajectory of the centroid, which clearly shows an emergent swirling structure with an empty core. In diagram (b), we have that $1703.03 \leq L \leq 11, 074.60$ and $- 45, 014.90 \leq d L / d t \leq - 42.99$ which implies that the system of point masses does not cease motion. Diagram (c) shows that around the centroid, the movements are erratic but bounded before settling down.

Example 5.4 (random-like walks)

A random walk is a random process consisting of a sequence of discrete steps of fixed length.²⁵ In this example, with $n = 30$ , the point masses, each with bin size $r_{V} = 10$ , display random-like walks. The cohesion parameters are $γ_{i} = 1$ , the coupling parameters, $β_{i j}$ , are randomized between and including 100 and 600, the convergence parameters μ_i and φ_i, are set at 5, and the constants ε_i are chosen to be $10^{- 6}$ . In Figure 4, the grayish areas are trajectories of each individual, whereas the black trajectory is the trace of the centroid, given over the time period $t \in [0, 3000]$ .

Figure 4.

The simulation shows a cohesive group with individuals hovering excitedly about the centroid in a random fashion. As they change positions, the centroid traces out a series of straight segments interrupted by tight turns. As in previous examples, the Lyapunov-like function is monotonic, and the solution is bounded about the centroid. (a) A random-like walk and (b) a zoomed-in centroid path at t = 500.

A well-spaced and cohesive system

The examples in the previous section provide helpful intuitive insights into the behavior of system (4). They seem to suggest that the solutions are bounded about the centroid. In this section, we will show that, indeed, it is the case. We begin by showing that system (4) is well-spaced, which, according to Definition 2.1, means that the solution $x (t)$ of system (4) exists and is unique for all time $t \geq 0$ in the domain $D (L)$ .

A well-spaced system

Looking at the right-hand side of equations (9) and (10), we see that the functions that appear in the denominator are $Q_{i j}$ , $i, j \in ℕ$ , $i \neq j$ . Hence, we can easily conclude that $G \in C [D (L), ℝ^{2 n}]$ , which implies that at least on some time interval $[t_{0}, α]$ , $α > 0$ , the solution $x (t)$ of system (4) exists and is in $D (L)$ . Indeed, since the functions $Q_{i j}$ appear in the denominator in (9) and (10), they will also appear in the denominator in higher-order partial derivatives, with each derivative continuous on $D (L)$ . This means that $G$ is locally Lipschitz on $D (L)$ , that is, $G \in C^{1} [D (L), ℝ^{2 n}]$ . This implies the solution $x (t)$ of system (4) exists and is unique in $D (L)$ on the time interval $[t_{0}, α]$ .

We shall next attempt to show that $x (t)$ exists and is unique for all time $t \geq t_{0} \geq 0$ in $D (L)$ .

We begin by observing that since the time-derivative of L along the solution of (4) is nonpositive, we have

L (x (t)) \leq L_{0} : = L (x_{0}), t \in [t_{0}, α]

From the form of L in (7), equation (13) implies that for every $i \neq j$ , $i, j = 1, \dots, n$

γ_{i} R_{i} (x (t)) \leq L_{0} and β_{i j} \frac{R_{i} (x (t))}{Q_{i j} (x (t))} \leq L_{0}, t \in [t_{0}, α]

Let $r_{0} : = max {L_{0} / γ_{i}, i = 1, \dots, n}$ and $q_{0} : = max {L_{0} / β_{i j}, i \neq j, i, j = 1, \dots, n}$ . Then from (14), we get

R_{i} (x (t)) \leq r_{0} and \frac{R_{i} (x (t))}{Q_{i j} (x (t))} \leq q_{0}, t \in [t_{0}, α]

Given the form of $R_{i} (x (t))$ in (5), the second inequality in (15) gives

ε_{i}^{2} \frac{1}{Q_{i j} (x (t))} \leq \frac{R_{i} (x (t))}{Q_{i j} (x (t))} \leq q_{0}, t \in [t_{0}, α]

and hence, if ${\hat{q}}_{0} : = ε_{i}^{- 2} q_{0}$

\frac{1}{Q_{i j} (x (t))} \leq ε_{i}^{- 2} \frac{R_{i} (x (t))}{Q_{i j} (x (t))} \leq {\hat{q}}_{0}, t \in [t_{0}, α]

Now, consider $f_{i}$ and $g_{i}$ given in (9) and (10), respectively. If we let $γ_{0} : = max {γ_{i}, i = 1, \dots, n}$ and $β_{0} : = max {β_{i j}, i \neq j, i, j = 1, \dots, n}$ , then we estimate them as follows

| f_{i} | \leq (γ_{0} + β_{0} \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{1}{Q_{i j}}) | x_{i} - x_{C} | + 2 β_{0} \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{R_{i}}{Q_{i j}^{2}} (| x_{i} | + | x_{j} |)

and

| g_{i} | \leq (γ_{0} + β_{0} \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{1}{Q_{i j}}) | y_{i} - y_{C} | + 2 β_{0} \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{R_{i}}{Q_{i j}^{2}} (| y_{i} | + | y_{j} |)

Recalling $G (x) = (- μ_{1} f_{1} (x), - φ_{1} g_{1} (x), \dots, - μ_{n} f_{n} (x), - φ_{n} g_{n} (x))$ , we have

∥ G ∥ = \sqrt{\sum_{i = 1}^{n} (μ_{i}^{2} f_{i}^{2} + φ_{i}^{2} g_{i}^{2})} \leq \sum_{i = 1}^{n} (μ_{i} | f_{i} | + φ_{i} | g_{i} |)

Then with respect to the solution $x (t)$ that exists on $[t_{0}, α]$ , we have, therefore, from the inequalities (15) to (18), the estimate, for some constants $k_{i} > 0$ independent of $α$

∥ G (x (t)) ∥ \leq \sum_{i = 1}^{n} k_{i} (| x_{i} (t) | + | y_{i} (t) |)

It follows from (19), therefore, that for some $M > 0$ independent of $α$ , we have the estimate

∥ G (x (t)) ∥ \leq M ∥ x (t) ∥

which implies that the function $G (x (t))$ is linearly bounded on $[t_{0}, α]$ . We shall now show that by this estimate and the comparison theorem the solution can be extended on $[t_{0}, \infty)$ . To this end, consider again system (4). By taking the inner product of the first equation of (4) and $x (t)$ , we have, by estimate (20)

\frac{1}{2} \frac{d}{d t} ∥ x (t) ∥^{2} = 〈 \dot{x} (t), x (t) 〉 = 〈 G (t), x (t) 〉 \leq ∥ G (x (t)) ∥ \cdot ∥ x (t) ∥ \leq M ∥ x (t) ∥^{2}

Let $y (t) : = ∥ x (t) ∥^{2}$ . Then we have the differential inequality

\frac{1}{2} \frac{d}{d t} y (t) \leq M y (t), y (t_{0}) = ∥ x_{0} ∥^{2}

Comparing (22) and (21), it is easy to see that

∥ x (t) ∥^{2} \leq ∥ x_{0} ∥^{2} e^{2 M (t - t_{0})}, t \in [t_{0}, α]

The a priori boundedness (23) of $∥ x (t) ∥^{2}$ implies the extension of the solution of (4) on $[t_{0}, α + β]$ , $β > 0$ being independent of α. Hence, we are assured of the existence and uniqueness of $x (t)$ in $D (L)$ for all time $t \geq 0$ . It follows therefore that system (4) is well-spaced.

Theorem 6.1

System (4) is well-spaced.

Cohesiveness of system (4)

We establish the cohesiveness of system (4) by proving the boundedness of $x$ about $x_{C}$ over the domain $D (L)$ . We follow the classical work of Yoshizawa,²⁶ who worked on the boundedness of solutions with Lyapunov-like functions.

Definition 6.2

The solution $x (t)$ of (4) is equi-bounded about $x_{C} (t)$ if for every $λ > 0$ and $t_{0} \geq 0$ , there exists a $B (t_{0}, λ) > 0$ such that if $∥ x (t_{0}) - x_{C} (t_{0}) ∥ \leq λ$ , then $∥ x (t) - x_{C} (t) ∥ < B (t_{0}, λ)$ for all $t \geq t_{0}$ .

Definition 6.3

The solution $x (t)$ of (4) is uniformly bounded about $x_{C} (t)$ if B in Definition 6.2 is independent of $t_{0}$ .

Lemma 6.4

The solution $x (t)$ of (4) is uniformly bounded about $x_{C} (t)$ .

Proof

Given $λ > 0$ and $t_{0} > 0$ , let $x (t) = x (t; t_{0}, x_{0})$ be a solution of (4) in $D (L)$ such that $∥ x (t_{0}) - x_{C} (t_{0}) ∥ \leq λ$ . Let $γ_{min} : = min {γ_{1}, \dots, γ_{n}}$ , $γ_{max} : = max {γ_{1}, \dots, γ_{n}}$ , and $ε_{max} = max {ε_{1}, \dots, ε_{n}}$ . Further, define the functions $a (r)$ and $b (r)$ by

a (r) : = \frac{1}{2} γ_{min} r^{2} and b (r) : = \frac{1}{2} γ_{max} r^{2} + n ε_{max}^{2} + L (x (t_{0}))

respectively, where L is the Lyapunov-like function given in (7). It is clear that the functions are independent of $t_{0}$ and $0 \leq a (r) \leq b (r)$ for all $r > 0$ . Given that a and b are continuously increasing functions in r and $a, b \to \infty$ as $r \to \infty$ , we can choose a $B = B (λ) > 0$ so large that

a (B) > b (λ)

We shall now show, by contradiction, that there exists a constant $B (λ) > 0$ such that if $∥ x (t_{0}) - x_{C} (t_{0}) ∥ \leq λ$ , then $∥ x (t) - x_{C} (t) ∥ \leq B (λ)$ for all $t \geq t_{0}$ . At the onset, we note that since

\sum_{i = 1}^{n} R_{i} (x) = \frac{1}{2} ∥ x - x_{C} ∥^{2} + \sum_{i = 1}^{n} ε_{i}^{2}

we have

a (∥ x - x_{C} ∥) \leq L (x) \forall x \in ℝ^{2 n}

Moreover, since ${\overset{•}{L}}_{(4)} (x (t)) \leq 0$ , which implies that

L (x (t)) \leq L (x (t_{0})) \leq L (x (0)) \forall t \geq t_{0} \geq 0

we can see that

L (x (t)) \leq L (x (t_{0})) \leq b (∥ x (t) - x_{C} (t) ∥) \forall t \geq 0

Now, assume contrarily that for any $B > λ$ , there exists a $t_{1} \geq t_{0}$ such that $∥ x (t_{0}) - x_{C} (t_{0}) ∥ \leq λ$ but

∥ x (t_{1}) - x_{C} (t_{1}) ∥ \geq B (λ)

By the continuity of solutions, we can find t′ and t″ such that $t_{0} \leq t^{'} \leq t ″ \leq t_{1}$ and

∥ x (t^{'}) - x_{C} (t^{'}) ∥ = λ and ∥ x (t ″) - x_{C} (t ″) ∥ = B

Set

t_{1} : = sup {t^{'} : ∥ x (t^{'}) - x_{C} (t^{'}) ∥ = λ}

and

t_{2} : = inf {t ″ : ∥ x (t ″) - x_{C} (t ″) ∥ = B}

Then $t_{1} < t_{2}$

∥ x (t_{1}) - x_{C} (t_{1}) ∥ = λ, ∥ x (t_{2}) - x_{C} (t_{2}) ∥ = B

and

λ < ∥ x (t) - x_{C} (t) ∥ < B \forall t \in (t_{1}, t_{2})

Thus, by (27), we have

L (x (t_{1})) \leq b (∥ x (t_{1}) - x_{C} (t_{1}) ∥) = b (λ)

and by (25)

a (∥ x (t_{2}) - x_{C} (t_{2}) ∥) = a (B) \leq L (x (t_{2}))

Since $t_{1} < t_{2}$ , we have, by (26)

L (x (t_{2})) \leq L (x (t_{1}))

so that

a (B) \leq L (x (t_{2})) \leq L (x (t_{1})) \leq b (λ)

which however clearly contradicts (24) and, thus, our choice of $B (λ)$ in (28). Hence $∥ x (t) - x_{C} (t) ∥ < B (λ)$ for all $t \geq t_{0}$ . This ends the proof of Lemma 6.4. □

We can now readily establish cohesiveness via Lemma 2.2 and Lemma 6.4.

Theorem 6.5

System (4) is cohesive.

Proof

By Lemma 2.2 and Lemma 6.4, we have that

r_{V} < ∥ x (t) - x_{C} (t) ∥ < \infty \forall t \geq 0

Hence both

\underset{t \to \infty}{lim s u p} ∥ x (t) - x_{C} (t) ∥ and \underset{t \to \infty}{lim i n f} ∥ x (t) - x_{C} (t) ∥

exist. Now, from the decreasing property of the Lyapunov-like function (7), we have, for all $t \geq 0$

\frac{1}{2} γ_{min} ∥ x - x_{C} ∥^{2} < \sum_{i = 1}^{n} γ_{i} R_{i} (x (t)) \leq L (x (t)) \leq L (x (0))

Thus

r_{V} < ∥ x (t) - x_{C} (t) ∥ \leq \sqrt{\frac{2 L (x (0))}{γ_{min}}}

Hence, Definition 2.3 is satisfied if we choose

\bar{K} = \sqrt{\frac{2 L (x (0))}{γ_{min}}} and \underline{K} = r_{V}

Equilibrium points of system (4)

In this section, we show that system (4) can have equilibrium points, which must correspond to $x$ that solves $d L / d t = 0$ . In other words, we need to simultaneously solve $f_{i} (x) = 0$ and $g_{i} (x) = 0$ given in (9) and (10), respectively. Now, we note by observation that these equalities hold if $R_{i} (x) = 0$ for all $i = 1, \dots, n$ . However, this means that for some sufficiently small $ε_{i} > 0$ , $(x_{i}, y_{i}) \approx (x_{j}, y_{j})$ for all $i \neq j$ , $i, j \in {1, \dots, n}$ , at some time $t \geq 0$ . This violates our requirement that $Q_{i j} > 0$ or $d_{i j} (t) > 2 r_{V}$ at every $t > 0$ in $D (L)$ . Hence, we proceed to solve $f_{i} (x) = 0$ and $g_{i} (x) = 0$ with $R_{i} (x) \neq 0$ . Accordingly, let

F_{i} : = γ_{i} + \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j}}{Q_{i j}} and G_{i j} : = \frac{2 β_{i j} R_{i}}{Q_{i j}^{2}}

Then (9) becomes

\begin{matrix} f_{i} (x) = F_{i} (x_{i} - x_{C}) - \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} G_{i j} (x_{i} - x_{j}) \\ = F_{i} (\frac{n - 1}{n} x_{i} - \frac{1}{n} \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} x_{j}) - \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} G_{i j} (x_{i} - x_{j}) \\ = (\frac{(n - 1) F_{i}}{n} - \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} G_{i j}) x_{i} - \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} (\frac{F_{i}}{n} - G_{i j}) x_{j} \end{matrix}

Then letting $f_{i} = 0$ , we have

[(n - 1) F_{i} - n \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} G_{i j}] x_{i} - \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} [F_{i} - n G_{i j}] x_{j} = 0

Similarly, on solving $g_{i} = 0$ , we get

[(n - 1) F_{i} - n \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} G_{i j}] y_{i} - \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} [F_{i} - n G_{i j}] y_{j} = 0

In solving $f_{i} = 0$ and $g_{i} = 0$ , we want to avoid the trivial solution. Since we only want to know whether we will have equilibrium points, let us consider the special case where

F_{i} = n G_{i j} for all i \neq j

Then the second term of (30) and (31) reduces to zero. The first term also reduces to zero since

\begin{array}{l} (n - 1) F_{i} - n \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} G_{i j} \\ = (n - 1) F_{i} - \underset{(n - 1) terms}{\underset{︸}{(G_{i 1} + G_{i 2} + \dots + G_{i k} + \dots + G_{i n})}} \\ = (n - 1) F_{i} - (\underset{(n - 1) terms}{\underset{︸}{F_{i} + \dots + F_{i}}}) \\ = (n - 1) F_{i} - (n - 1) F_{i} = 0 \end{array}

Now, from (32), we have, if n = 3, for example

F_{1} = 3 G_{12}, F_{1} = 3 G_{13}, F_{2} = 3 G_{21}, F_{2} = 3 G_{23}, F_{3} = 3 G_{31} and F_{3} = 3 G_{32}

which imply that $G_{12} = G_{13}$ , $G_{21} = G_{23}$ , and $G_{31} = G_{32}$ . In general, (32) implies that

G_{i k} = G_{i j}, i, j, k \in ℕ, i \neq j, i \neq k

Equations (32) and (33), therefore, respectively provide us the following important relationships

\begin{array}{l} γ_{i} + \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j}}{Q_{i j}} = n \frac{2 β_{i j} R_{i}}{Q_{i j}^{2}} \\ \frac{β_{i k}}{Q_{i k}^{2}} = \frac{β_{i j}}{Q_{i j}^{2}}, \end{array}}

From (34), we can build a homogeneous system of linear equations with respect to the control parameters $γ_{i} > 0$ , $β_{i k} > 0$ , and $β_{i j} > 0$ , for all $i, j, k \in ℕ$ , $i \neq j$ , $i \neq k$

\begin{array}{l} γ_{i} + (\frac{1}{Q_{i k}} - \frac{2 n R_{i}}{Q_{i k}^{2}}) β_{i k} + \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{1}{Q_{i j}} β_{i j} = 0 \\ \frac{1}{Q_{i k}^{2}} β_{i k} - \frac{1}{Q_{i j}^{2}} β_{i j} = 0 \end{array}}

or, in matrix notation

A y = 0

Here, $A$ is the $n (n - 1) \times n^{2}$ coefficient matrix of system (35). The entries of $A$ consist of

1, (\frac{1}{Q_{i k}} - \frac{2 n R_{i}}{Q_{i k}^{2}}), \frac{1}{Q_{i j}}, \frac{1}{Q_{i k}^{2}} and \frac{1}{Q_{i j}^{2}}

where the $Q_{i j}$ and R_i are calculated at $x = x_{e}$ , that is, $A = A (x_{e})$ . The vector $y$ is an $n^{2} \times 1$ vector, the entries of which consist of the control parameters $(γ_{i}, β_{i j}, β_{i k})$ .

For the case $n = 2$ , since $i \neq j$ and $i \neq k$ , which means that $j \neq k$ , system (35) gives

γ_{1} + (\frac{1}{Q_{12}} - \frac{4 R_{1}}{Q_{12}^{2}}) β_{12} = 0 and γ_{2} + (\frac{1}{Q_{21}} - \frac{4 R_{2}}{Q_{21}^{2}}) β_{21} = 0

Consider the special situation where $ε_{1} = ε_{2}$ . Then, since $R_{1} = R_{2}$ and $Q_{12} = Q_{21}$ for any point $(x_{1}, y_{1}, x_{2}, y_{2}) \in D (L)$ , we have

q : = (\frac{1}{Q_{12}} - \frac{4 R_{1}}{Q_{12}^{2}}) = (\frac{1}{Q_{21}} - \frac{4 R_{2}}{Q_{21}^{2}})

Thus

A = [\begin{matrix} 1 & q & 0 & 0 \\ 0 & 0 & 1 & q \end{matrix}] and y = {[\begin{matrix} γ_{1} & β_{12} & γ_{2} & β_{21} \end{matrix}]}^{T}

Now, rank $A = 2 < 4$ , and nullity $A = 4 - 2 = 2$ . The former implies that for every point $x = (x_{1}, y_{1}, x_{2}, y_{2}) \in D (L)$ that generates q, there are nontrivial solutions $y$ . The latter implies there are two basis vectors for the null space of $A$ ; they are $(0, 0, - q,1)$ and $(- q,1,0,0)$ . Since we want the parameters to be positive, we can add the basis vectors to get $y = (γ_{1}, β_{12}, γ_{2}, β_{21}) = c (- q,1, - q,1)$ for some scalar $c \in ℝ$ . Hence, if we choose $c > 0$ , then the point $x = (x_{1}, y_{1}, x_{2}, y_{2})$ that makes $q < 0$ is an equilibrium point of system (4).

For the case $n = 3$ , equation (35) gives, for $i = 1$

\begin{array}{l} γ_{1} + (\frac{1}{Q_{12}} - \frac{6 R_{1}}{Q_{12}^{2}}) β_{12} + \frac{1}{Q_{13}} β_{13} = 0 \\ \frac{1}{Q_{12}^{2}} β_{12} - \frac{1}{Q_{13}^{2}} β_{13} = 0 \end{array}

for $i = 2$

\begin{array}{r} γ_{2} + (\frac{1}{Q_{21}} - \frac{6 R_{2}}{Q_{21}^{2}}) β_{21} + \frac{1}{Q_{23}} β_{23} = 0 \\ \frac{1}{Q_{21}^{2}} β_{21} - \frac{1}{Q_{23}^{2}} β_{23} = 0 \end{array}

and for $i = 3$

\begin{array}{l} γ_{3} + (\frac{1}{Q_{31}} - \frac{6 R_{3}}{Q_{31}^{2}}) β_{31} + \frac{1}{Q_{32}} β_{32} = 0 \\ \frac{1}{Q_{31}^{2}} β_{31} - \frac{1}{Q_{32}^{2}} β_{32} = 0 \end{array}

If we let

\begin{matrix} a_{12} : = (\frac{1}{Q_{12}} - \frac{6 R_{1}}{Q_{12}^{2}}), a_{13} : = \frac{1}{Q_{13}}, a_{22} : = \frac{1}{Q_{12}^{2}}, a_{23} : = - \frac{1}{Q_{13}^{2}} \\ a_{35} : = (\frac{1}{Q_{21}} - \frac{6 R_{2}}{Q_{21}^{2}}), a_{36} : = \frac{1}{Q_{23}}, a_{45} : = \frac{1}{Q_{21}^{2}}, a_{46} : = - \frac{1}{Q_{23}^{2}} \\ a_{58} : = (\frac{1}{Q_{31}} - \frac{6 R_{3}}{Q_{31}^{2}}), a_{59} : = \frac{1}{Q_{32}}, a_{68} : = \frac{1}{Q_{31}^{2}}, a_{69} : = - \frac{1}{Q_{32}^{2}} \end{matrix}

then in the form of system (36), we have

[\begin{matrix} 1 & a_{12} & a_{13} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & a_{22} & a_{23} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & a_{35} & a_{36} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & a_{45} & a_{46} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & a_{58} & a_{59} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & a_{68} & a_{69} \end{matrix}] [\begin{matrix} γ_{1} \\ β_{12} \\ β_{13} \\ γ_{2} \\ β_{21} \\ β_{23} \\ γ_{3} \\ β_{31} \\ β_{32} \end{matrix}] = [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}]

The rank and the nullity of $A$ are 6 and 3, respectively. Thus, we can conclude that for every point $(x_{1}, x_{2}, x_{3}) \in D (L)$ , we have nontrivial solutions $y$ of system (38). The three basis vectors for the nullspace of $A$ are

\begin{array}{l} (0,0,0,0,0,0, - ((a_{59} a_{68} - a_{58} a_{69}) / a_{68}), - (a_{69} / a_{68}),1) \\ (0, 0, 0, - ((a_{36} a_{45} - a_{35} a_{46}) / a_{45}), - (a_{46} / a_{45}),1,0,0,0) \\ (- ((a_{13} a_{22} - a_{12} a_{23}) / a_{22}), - (a_{23} / a_{22}),1,0,0,0,0,0,0) \end{array}

which can be added to obtain positive parameters. The points $(x_{1}, x_{2}, x_{3}) \in D (L)$ that produce the positive parameters constitute therefore the equilibrium point $x_{e} : = (x_{1}, x_{2}, x_{3})$ of system (4).

In a similar way, we can construct homogeneous systems of linear equations from (35) for higher values of n.

In summary, from equation (35), we can obtain the homogeneous system of linear equations (36), where matrix $A = A (x)$ is an $n (n - 1) \times n^{2}$ coefficient matrix whose entries consist of the values of $Q_{i j}$ and R_i at $x$ . The vector $y$ is an $n^{2} \times 1$ vector of control parameters $(γ_{i}, β_{i k}, β_{i j})$ , $i, j, k \in ℕ$ , $i \neq j$ , $i \neq k$ . Since rank $A = n (n - 1) < n^{2}$ , the homogeneous system (36) has infinitely many solutions $y$ . Since we want $y > 0$ , the n basis vectors of the null space of $A$ can be added to obtain all positive entries in $y$ . The point $x \in D (L)$ that generates the entries in $A$ and the positive entries in $y$ such that $A y = 0$ is the equilibrium point $x_{e}$ of system (4).

Parallel formation in the absence of equilibrium points

In the previous section, when we simultaneously solved $f_{i} (x) = 0$ and $g_{i} (x) = 0$ , we found a solution, namely, a set of equilibrium points. In this subsection, we show that a further analysis produces an unexpected solution—an emergent pattern that so far has only been numerically obtained by other researchers, namely, a highly parallel group, which arises due to the absence of equilibrium points.

Beginning with equations (29), which are

F_{i} : = γ_{i} + \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} \frac{β_{i j}}{Q_{i j}} and G_{i j} : = \frac{2 β_{i j} R_{i}}{Q_{i j}^{2}}

we want to solve $f_{i} (x) = 0$ and $g_{i} (x) = 0$ for $x$ , where

f_{i} (x) = F_{i} (x_{i} - x_{C}) - \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} G_{i j} (x_{i} - x_{j})

and

g_{i} (x) = F_{i} (y_{i} - y_{C}) - \sum_{\begin{array}{l} j = 1, \\ j \neq i \end{array}}^{n} G_{i j} (y_{i} - y_{j})

Now, (39) can be written in an expanded form as

\begin{array}{l} f_{i} (x) = F_{i} (x_{i} - x_{C}) - \underset{n - 1 terms}{\underset{︸}{G_{i 1} (x_{i} - x_{1}) - \dots - G_{i n} (x_{i} - x_{n})}} \\ = [\frac{F_{i}}{n} (x_{i} - x_{C}) - G_{i 1} (x_{i} - x_{1})] + \dots \\ + [\frac{F_{i}}{n} (x_{i} - x_{C}) - G_{i n} (x_{i} - x_{n})] \end{array}

Equation (40) can be written similarly. Thus

\begin{array}{l} {\overset{•}{L}}_{(4)} = - \sum_{i = 1}^{n} (μ_{i} f_{i}^{2} + φ_{i} g_{i}^{2}) \\ = - μ_{1} {\frac{F_{1}}{n} (x_{1} - x_{C}) + [\frac{F_{1}}{n} (x_{1} - x_{C}) - G_{12} (x_{1} - x_{2})] + \dots \\ {+ [\frac{F_{1}}{n} (x_{1} - x_{C}) - G_{1 n} (x_{1} - x_{n})]}}^{2} \\ - φ_{1} {\frac{F_{1}}{n} (y_{1} - y_{C}) + [\frac{F_{1}}{n} (y_{1} - y_{C}) - G_{12} (y_{1} - y_{2})] + \dots \\ {+ [\frac{F_{1}}{n} (y_{1} - y_{C}) - G_{1 n} (y_{1} - y_{n})]}}^{2} - \dots \\ - μ_{n} {\frac{F_{n}}{n} (x_{n} - x_{C}) + [\frac{F_{n}}{n} (x_{n} - x_{C}) - G_{n 2} (x_{n} - x_{2})] + \dots \\ {+ [\frac{F_{n}}{n} (x_{n} - x_{C}) - G_{n (n - 1)} (x_{n} - x_{n - 1})]}}^{2} \\ - φ_{n} {\frac{F_{n}}{n} (y_{n} - y_{C}) + [\frac{F_{n}}{n} (y_{n} - y_{C}) - G_{n 2} (y_{1} - y_{2})] + \dots \\ {+ [\frac{F_{n}}{n} (y_{n} - y_{C}) - G_{n (n - 1)} (y_{n} - y_{n - 1})]}}^{2} \end{array}

Let us now assume that for certain values of the control parameters $γ_{i} > 0$ and $β_{i j} > 0$ , we have

\begin{matrix} [\frac{F_{i}}{n} (x_{i} - x_{C}) - G_{i 1} (x_{i} - x_{1})] & = & 0 \\ ⋮ & ⋮ & ⋮ \\ [\frac{F_{i}}{n} (x_{i} - x_{C}) - G_{i n} (x_{i} - x_{n})] & = & 0 \end{matrix}}

and

\begin{matrix} [\frac{F_{i}}{n} (y_{i} - y_{C}) - G_{i 1} (y_{i} - y_{1})] & = & 0 \\ ⋮ & ⋮ & ⋮ \\ [\frac{F_{i}}{n} (y_{i} - y_{C}) - G_{i n} (y_{i} - y_{n})] & = & 0 \end{matrix}}

We can thus solve (41) and (42) simultaneously to get an equilibrium point $x_{e}$ . For the i th case, we need to simultaneously solve the four equations

\begin{array}{r} \frac{F_{i}}{n} (x_{i} - x_{C}) = 0 \\ \frac{F_{i}}{n} (x_{i} - x_{C}) - G_{i j} (x_{i} - x_{j}) = 0 \\ \frac{F_{i}}{n} (y_{i} - x_{C}) = 0 \\ \frac{F_{i}}{n} (y_{i} - y_{C}) - G_{i j} (y_{i} - y_{j}) = 0 \end{array}}

noting that the first and third equations come from the fact that $G_{i i} (x_{i} - x_{i}) = G_{i i} (y_{i} - y_{i}) = 0$ . From these equations, since $F_{i} \neq 0$ and $G_{i j} \neq 0$ in $D (L)$ , it must be that $(x_{i}, y_{i}) = (x_{C}, y_{C})$ and $(x_{i}, y_{i}) = (x_{j}, y_{j})$ , for all $i, j \in {1, \dots, n}$ , $i \neq j$ . This implies that an equilibrium point must be where all the individuals collapse onto each other. However, this is impossible in $D (L)$ . Hence, it must be that $(x_{i}, y_{i}) \neq (x_{C}, y_{C})$ and $(x_{i}, y_{i}) \neq (x_{j}, y_{j})$ , for all $i, j \in {1, \dots, n}$ , $i \neq j$ . Thus, we are left with only the second and forth equations to solve simultaneously

\begin{array}{l} \frac{F_{i}}{n} (x_{i} - x_{C}) - G_{i j} (x_{i} - x_{j}) = 0 \\ \frac{F_{i}}{n} (y_{i} - y_{C}) - G_{i j} (y_{i} - y_{j}) = 0 \end{array}}

This is solvable to give the set of lines

S : = {x \in D (L) : (x_{i} - x_{j}) (y_{i} - y_{C}) - (y_{i} - y_{j}) (x_{i} - x_{C}) = 0}

for all $i, j = 1, 2, \dots, n$ , $i \neq j$ . Consequently, in $D (L)$ , if (44) holds, then

{\overset{•}{L}}_{(4)} = - \sum_{i = 1}^{n} {μ_{i} {[\frac{F_{i}}{n} (x_{i} - x_{C})]}^{2} + φ_{i} {[\frac{F_{i}}{n} (y_{i} - x_{C})]}^{2}} < 0

which also tells us, since ${\overset{•}{L}}_{(4)} \neq 0$ , there is no equilibrium point in $D (L)$ in the special case where (44) holds. In conclusion, since a line in S can be written as

ℓ_{i C} : y_{i} - y_{C} = \frac{y_{i} - y_{j}}{x_{i} - x_{j}} (x_{i} - x_{C})

ℓ_{i j} : y_{i} - y_{j} = \frac{y_{i} - y_{C}}{x_{i} - x_{C}} (x_{i} - x_{j})

we can encounter two possible scenarios.

Line $ℓ_{i C}$ tells us that any point mass A_i can be on the same line that joins its position $(x_{i}, y_{i})$ to the position of the centroid $(x_{C}, y_{C})$ . Its slope is equal to $(y_{i} - y_{j}) / (x_{i} - x_{j})$ , the slope of a line that would have existed if A_i and A_j were on it. This simply means that at least one point mass will be on $ℓ_{i C}$ while the rest of the point masses will be on other lines parallel to $ℓ_{i C}$ .

Similarly, line $ℓ_{i j}$ tells us that at least two point masses A_i and A_j will be on a line parallel to a line whose slope is $(y_{i} - y_{C}) / (x_{i} - x_{C})$ and which would have existed if A_i and the centroid were on it. The other members of the group will be on lines parallel to $ℓ_{i j}$ .

Other researchers have reported this type of emergent behavior using their swarm model. For example, Couzin et al.²⁷ described this behavior as is an instance of highly parallel group, which is a group that self-organizes into a highly aligned arrangement with rectilinear motion. The same behavior is reported in Liu et al.²⁸ and Xue et al.²⁹ However, these papers only manage to numerically generate the pattern. Our result gives a first explicit formulation of the pattern.

Application to planar mobile car-like vehicles

In this section, we apply our method of developing the Lagrangian swarm model to design the velocity controllers of autonomous car-like robots. We reproduce the description of the robots from the authors’ work in Vanualailai et al.,³⁰ starting with Figure 5 which shows the i th car-like with front wheel steering and engine power applied to the rear wheels. For each car i, let $ξ > 0$ be the distance between the two axles and $ℓ > 0$ the length of each axle. Assuming that $ϕ_{i} = θ_{i}$ , the kinematic model of the car-like robot with respect to its center $(x_{i}, y_{i}) \in ℝ^{2}$ is, as shown in Pappas and Kyriakopoulos³¹

{\overset{•}{x}}_{i} = υ_{i} cos θ_{i} - \frac{ξ}{2} ω_{i} sin θ_{i}, {\overset{•}{y}}_{i} = υ_{i} sin θ_{i} + \frac{ξ}{2} ω_{i} cos θ_{i}, {\overset{•}{θ}}_{i} = ω_{i}

where the variable θ_i gives the robot’s orientation with respect to the $z_{1}$ -axis of the $z_{1}$ – $z_{2}$ coordinates, and υ_i and ω_i are the instantaneous translational and angular velocities, respectively. To ensure that the i th vehicle safely steers pass other vehicles, we enclose it by the smallest circle possible. As shown in Figure 5, if we let $ε_{1} > 0$ and $ε_{2} > 0$ be the clearance parameters, then we can enclose the vehicle by a protective circular region centered at $(x, y)$ , with radius $r_{V} : = \sqrt{{(2 ε_{1} + ξ)}^{2} + {(2 ε_{2} + ℓ)}^{2}} / 2$ . We can thus take equation (1) as the definition of our car-like robots. Accordingly, our system consists of the robots A_i as members of a swarm. The centroid of the swarm is given by (2). Our objective is to design the translational velocities υ_i and the angular velocities ω_i such that robots are attracted to the centroid as a cohesive and well-spaced swarm.

Figure 5.

The i th planar mobile robot which is car-like, with front wheel steering and steering angle ϕ_i.

Velocity controllers for the vehicles

Let us extend the definition of the independent variable from $x_{i} = (x_{i}, y_{i}) \in ℝ^{2}$ to $q_{i} : = (x_{i}, y_{i}, θ_{i}) \in ℝ^{3}$ , and $q : = (q_{1}, \dots, q_{n}) \in ℝ^{3 n}$ . Then (45) is the i th component of the system

\overset{•}{q} = H_{1} (q) v + H_{2} (q) w, q_{0} : = q (t_{0})

where $v : = (υ_{1}, \dots, υ_{n}) \in ℝ^{n}$ , $w : = (ω_{1}, \dots, ω_{n}) \in ℝ^{n}$ , and $H_{1}$ and $H_{2}$ are $3 n \times n$ matrices defined as

H_{1} = [\begin{matrix} cos θ_{1} & 0 & 0 & \dots & 0 & 0 \\ sin θ_{1} & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & \dots & 0 & 0 \\ 0 & cos θ_{2} & 0 & \dots & 0 & 0 \\ 0 & sin θ_{2} & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & \dots & 0 & 0 \\ ⋮ & ⋮ & ⋱ & ⋱ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & \dots & 0 & cos θ_{n} \\ 0 & 0 & 0 & \dots & 0 & sin θ_{n} \\ 0 & 0 & 0 & \dots & 0 & 0 \end{matrix}]

and

H_{2} = [\begin{matrix} - \frac{ξ}{2} sin θ_{1} & 0 & 0 & \dots & 0 & 0 \\ \frac{ξ}{2} cos θ_{1} & 0 & 0 & \dots & 0 & 0 \\ 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & - \frac{ξ}{2} sin θ_{2} & 0 & \dots & 0 & 0 \\ 0 & \frac{ξ}{2} sin θ_{2} & 0 & \dots & 0 & 0 \\ 0 & 1 & 0 & \dots & 0 & 0 \\ ⋮ & ⋮ & ⋱ & ⋱ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & 1 & 0 \\ 0 & 0 & 0 & \dots & 0 & - \frac{ξ}{2} sin θ_{n} \\ 0 & 0 & 0 & \dots & 0 & \frac{ξ}{2} cos θ_{n} \\ 0 & 0 & 0 & \dots & 0 & 1 \end{matrix}],

respectively. We can use $R_{i} = R_{i} (q)$ defined in (5) for the attraction to the centroid and $Q_{i j} = Q_{i j} (q)$ defined in (6) for interindividual collision avoidance. Then applying the Lyapunov-like function (7) to system (46) over the domain

\tilde{D} (L) : = {q \in ℝ^{3 n} : Q_{i j} (q) > 0 \forall i, j = 1, \dots, n, i \neq j}

we have, noting that $\partial L / \partial θ_{i} = 0$ since L does not contain a function of θ_i, and using $f_{i}$ and $g_{i}$ defined in (9) and (10), respectively

\begin{array}{l} {\overset{•}{L}}_{(46)} (q) = \sum_{i = 1}^{n} (f_{i} {x^{'}}_{i} + g_{i} {y^{'}}_{i}) \\ = \sum_{i = 1}^{n} [f_{i} (υ_{i} cos θ_{i} - \frac{ξ}{2} ω_{i} sin θ_{i}) + g_{i} (υ_{i} sin θ_{i} + \frac{ξ}{2} ω_{i} cos θ_{i})] \\ = \sum_{i = 1}^{n} [(f_{i} cos θ_{i} + g_{i} sin θ_{i}) υ_{i} - \frac{ξ}{2} (f_{i} sin θ_{i} - g_{i} cos θ_{i}) ω_{i}] \end{array}

Accordingly, we can define the steering control laws as

υ_{i} : = - k_{i} (f_{i} cos θ_{i} + g_{i} sin θ_{i}) and ω_{i} : = \frac{2 k_{i}}{ξ} (f_{i} sin θ_{i} - g_{i} cos θ_{i}),

where we want $k_{i}$ to be some arbitrary positive function of $x_{i}$ and $y_{i}$ only, and differentiable over $\tilde{D} (L)$ . With these control laws, we have, with respect to system (46)

{\overset{•}{L}}_{(46)} (q) = - \sum_{i = 1}^{n} \frac{1}{k_{i}} (υ_{i}^{2} + \frac{ξ^{2}}{4} ω_{i}^{2}) \leq 0

With (47), system (45) simplifies to

{\overset{•}{x}}_{i} = - k_{i} f_{i}, {\overset{•}{y}}_{i} = - k_{i} g_{i}, {\overset{•}{θ}}_{i} = \frac{2 k_{i}}{ξ} (f_{i} sin θ_{i} - g_{i} cos θ_{i})

The first two equations in (48) are independent of θ_i. That is, the positions $(x_{i}, y_{i})$ are determined by $k_{i} > 0$ , $f_{i}$ , and $g_{i}$ , which are functions of $x_{i}$ and $y_{i}$ only. Hence, it is sufficient to study the reduced system

{\overset{•}{x}}_{i} = - k_{i} f_{i}, {\overset{•}{y}}_{i} = - k_{i} g_{i}, x_{i 0} : = x_{i} (t_{0}), y_{i 0} : = y_{i} (t_{0}), t_{0} \geq 0

and let it the be the i th component of the system

\overset{•}{x} = F (x), x_{0} = x (t_{0})

where $F (x) : = (- k_{1} (x) f_{1} (x), - k_{1} (x) g_{1} (x), \dots, - k_{n} (x) f_{n} (x), - k_{n} (x) g_{n} (x)) \in ℝ^{2 n}$ . Since we are supposing that $k_{i} \in C^{1} [\hat{D} (L), ℝ_{+}]$ , $ℝ_{+} : = (0, \infty)$ , where

\hat{D} (L) : = {x \in ℝ^{2 n} : Q_{i j} (x) > 0 \forall i, j = 1, \dots, n, i \neq j}

system (50) has the same form and property as system (4). It is therefore well-spaced and cohesive in $\hat{D} (L)$ .

Restrictions on velocities and steering angles

A practical consideration is the mandatory restrictions on the velocities and the steering angle. In our case, the function $k_{i} = k_{i} (x) > 0$ plays an important role restricting the size of the steering angles φ_i. To see this, let $υ_{max} : = {max}_{i \in ℕ} | υ_{i} |$ and $ϕ_{max} : = {max}_{i \in ℕ} | ϕ_{i} |$ , with $0 < ϕ_{max} < π / 2$ . As shown in Pappas and Kyriakopoulos,³¹ the relationship between the translational velocities, υ_i, and the angular velocities, ω_i, is governed by

υ_{i}^{2} \geq η^{2} ω_{i}^{2} where η : = \frac{ξ}{tan ϕ_{max}}

From (51), we easily have

| ω_{i} | \leq \frac{| υ_{i} |}{| η |} \leq \frac{υ_{max}}{| η |}

Now, given any constant $ψ \geq 1$ , we have, from (47)

| υ_{i} | \leq k_{i} (ψ + | f_{i} | + | g_{i} |) and | ω_{i} | \leq \frac{2 k_{i}}{ξ} (ψ + | f_{i} | + | g_{i} |)

If we set $k_{i} : = υ_{max}$ , for instance, then the first inequality in (53) holds. Further, the second inequality in (53) and the inequality (52) are consistent if we let

\frac{2 k_{i}}{ξ} = \frac{2 v_{max}}{ξ} = \frac{υ_{max}}{| η |}

from which we get $| η | = ξ / 2$ . Thus, from (51), we have $tan ϕ_{max} = 2$ and $ϕ_{max} = {tan}^{- 1} 2$ . In other words, if we set $k_{i} = υ_{max}$ , then the maximum steering angle of every vehicle is set at $ϕ_{max} = {tan}^{- 1} 2$ .

In our simulations, we shall illustrate that an appropriately chosen $k_{i} = k_{i} (x)$ that is continuous on $\hat{D} (L)$ and satisfies (53) is sufficient to induce swarming with emergent patterns. If we choose, for example

k_{i} = k_{i} (x) : = \frac{υ_{max}}{ψ + | f_{i} | + | g_{i} |}

we can also show, along similar arguments as the above, that $ϕ_{max} = {tan}^{- 1} 2$ .

Simulations

For our simulations, we use the first two terms, ${\overset{•}{x}}_{i}$ and ${\overset{•}{y}}_{i}$ in (48) to obtain the positions $(x_{i} (t), y_{i} (t))$ of the i th vehicle, and the third term ${\overset{•}{θ}}_{i}$ to obtain its orientations, $θ_{i} (t)$ , at time $t > 0$ . At time $t = 0$ , the initial positions $(x_{i 0} (0), y_{i 0} (0))$ and orientations $θ_{i} (0)$ are randomly generated. The vehicles are drawn as arrows, with the arrowhead indicating the front of the vehicles. In each simulation, we use the following parameters:

Clearance parameters: $ε_{1} = ε_{2} = 0.1$ ;

Width and length of vehicle: $ℓ = 1$ , $ξ = 2$ ;

Radius of circular protective region: $r_{V} = 1.25$ ;

Maximum speeds and steering angle: $υ_{max} = ω_{max} = 2$ , $ϕ_{max} = {tan}^{- 1} 2$ ;

$ψ = 1$ in (53).

Additionally, since theoretically we require that $k_{i} \in C^{1} [\hat{D} (L), ℝ_{+}]$ , we can choose $k_{i} = k_{i} (x) = υ_{max}$ as suggested in the previous section. However, we shall use (54) to illustrate that it is sufficient that $k_{i}$ is continuous on $\hat{D} (L)$ to induce emergent patterns.

With the above parameters fixed, the remaining parameters are the cohesive parameters $γ_{i} > 0$ and the coupling parameters $β_{i j} > 0$ , for $i, j = 1, 2, \dots, n$ . As discussed in the “Roles of the parameters in the Lyapunov-like function” section, the cohesive parameters provide the strength of attraction between individuals and the coupling parameters provide the strength of repulsion between individuals.

We will consider two examples, each with only five vehicles to clearly illustrate the behavior of each vehicle. The first example illustrates the existence of an equilibrium point, while the second example illustrates the absence of one.

Example 9.1 (constant arrangement about a stationary centroid)

The parameters, for all $i, j = 1, 2, 3, 4, 5$ , are $γ_{i} = 1$ and $β_{i j} = 1$ . The emergent pattern is a stationary arrangement about the centroid (Figure 6).

Figure 6.

(a) Randomized initial positions and orientations of five vehicles. (b) At $t = 7$ , the vehicles are seen converging toward the centroid. We see that the top-most vehicle and the second vehicle from the left have to reverse to align correctly. (c) By $t = 20$ , the vehicles are stationary. Their trajectories are shown as lighter lines. (d) The instantaneous translational velocities eventually become zero, and, as expected, $| υ_{i} | \leq υ_{max} = 2$ for all $t \geq 0$ and $i = 1, \dots,5$ .

Example 9.2 (highly parallel formation)

In this example, the parameters, for all $i, j = 1, 2, 3, 4, 5$ , are γ_i randomized between and including 1 and 2, and $β_{i j} = 10$ . The emergent pattern is a parallel formation wherein the distances between the vehicles eventually stabilize over time (Figure 7).

Figure 7.

(a) Randomized initial positions and orientations of five vehicles. (b) By time $t = 40$ , the vehicles are seen in parallel formation. Their trajectories are shown in gray. (c) The instantaneous translational velocities converge to a common velocity, with $| υ_{i} | \leq υ_{max} = 2$ . (d) The angles θ_i of the vehicles stabilize with time.

Conclusion

In individual-based or Lagrangian swarm models governed by systems of first-order ordinary differential equations, the global existence and uniqueness of solutions, and the boundedness of solutions about the centroid of the swarm, are important properties. They ensure that the swarm model is cohesive and well-spaced.

This article developed a Lagrangian swarm model on the hypothesis that animal swarming is an interplay between long-range attraction and short-range repulsion between the individuals in the swarm. It treated both cohesive and well-spaced notions in a rigorous manner. The existence, uniqueness, and boundedness of solutions about the centroid were established via a Lyapunov-like function with attractive and repulsive components.

Extensive simulations suggested that the proposed artificial Lagrangian swarm model was sufficiently general to induce several stable patterns recognized as outcomes of collective behavior or self-organization. These are (a) constant arrangements about a stationary centroid, (b) parallel formations, (c) circular or oscillatory formations about a fixed point, and (d) random walks. To the author’s knowledge, such generality is not seen in other similar Lagrangian swarm models including the most recent one proposed in Li.¹⁸ The different types of emergent patterns arise by varying the system parameters.

This article, therefore, has provided a means to develop a generalized swarm model that could be used in engineering applications that seek to induce cooperation and pattern formation among multiple autonomous robotic agents.

Footnotes

Acknowledgements

The author would like to sincerely thank the editors and the anonymous reviewers for their suggestions that led to an improvement in the presentation of the article.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Jito Vanualailai

References

Park

Ahn

. A survey of multi-agent formation control. Automatica 2015; 53: 424–440.

Chen

Wang

. Formation control: a review and a new consideration. In: 2005 IEEE/RSJ international conference on intelligent robots and systems, Edmonton, Alta., Canada, 2–6 August 2005, pp. 3181–3186. IEEE.

Savkin

Wang

Baranzadeh

, et al. Distributed formation building algorithms for groups of wheeled mobile robots. Robot Auton Syst 2016; 75:463–474.

Soni

. Formation control for a fleet of autonomous ground vehicles: a survey. Robotics 2018; 7: 67.

Camazine

Deneubourg

Franks

, et al. Self-organization in biological systems. Princeton: Princeton University Press, 2003.

Gazi

Passino

. Stability analysis of social foraging swarms. IEEE Trans Syst Man Cybern B Cybern 2004; 34(1): 539–557.

Merrifield

. An investigation of mathematical models for animal group movement, using classical and statistical approaches. PhD Thesis, University of Sydney, NSW, Australia, August 2006.

Juanico

DEO

. Self-organized pattern formation in a diverse attraction-repulsive swarm. FPL 2009; 86: 48004.

Sozinova

Jiang

Alber

. A three-dimensional model of myxobacterial fruiting-body formation. Proc Natl Acad Sci 2006; 103(46): 17255–17259.

10.

Harvey

, et al. Interconnected cavernous structure of bacterial fruiting bodies. PLoS Comput Biol 2012; 8(12): e1002850.

11.

Couzin

Franks

. Self-organized lane formation and optimized traffic flow in army ants. Proc R Soc Lond B Biol Sci 2003; 270(1511): 139–146.

12.

Perna

Granovskiy

Garnier

, et al. Individual rules for trail pattern formation in Argentine ants (Linepithema humile). PLoS Comput Biol 2012; 8(7): e10052592.

13.

Tunstrøm

Katz

Ioannou

, et al. Collective states, multistability and transitional behaviour in schooling fish. PLoS Comput Biol 2013; 9(2): e1002915.

14.

Majkut

. Foraging fruit flies: Lagrangian and Eulerian descriptions of insect swarming. Master’s Thesis, Harvey Mudd College, Claremont, California, May 2006.

15.

Coppola

Guo

Gill

EKA

, et al. Provable emergent pattern formation by a swarm of anonymous, homogeneous, non-communicating, reactive robots with limited relative sensing and no global knowledge or positioning. CoRR 2018. arXiv/180.06827 [cs.RO].

16.

Mogilner

Edelstein-Keshet

Bent

, et al. Mutual interactions, potentials, and individual distance in a social aggregation. J Math Biol 2003; 47: 353–389.

17.

Carrillo

Fornasier

Toscani

, et al. Particle, kinetic, and hydrodynamic models of swarming. Mathematical modeling of collective behavior in socio-economic and life sciences. In: Naldi

Pareschi

Toscani

(eds) Modeling and simulation in science, engineering and technology. Boston: Birkhäuser, 2010, pp. 297–336.

18.

. Stability analysis of a swarm model with rooted leadership. Phys Lett A 2019; 33(1): 1–9.

19.

Czirók

Vicsek

. Collective motion of organisms in three dimensions. Phys A 1999; 264(1–2): 299–304.

20.

Sengupta

Basak

Peters

. Particle swarm optimization: a survey of historical and recent developments with hybridization perspectives. Machine Learning and Knowledge Extraction 2019; 1(1): 157–191.

21.

Kumar

Vanualailai

Sharma

. Lyapunov functions for a planar swarm model with application to nonholonomic planar vehicles. In: 2015 IEEE conference on control applications (CCA), Sydney, NSW, Australia, 21–23 September 2015, pp. 1919–1924. IEEE.

22.

Devi

Vanualailai

Kumar

, et al. A cohesive and well-spaced swarm with application to unmanned aerial vehicles. In: Proceedings of the 2017 international conference on unmanned aircraft systems, Miami, FL, USA, 13–16 June 2017, pp. 698–705. IEEE.

23.

Lemmon

Sun

. Cohesive swarming under consensus. In: 2006 45th IEEE conference on decision and control, San Diego, CA, USA, 13–15 December 2006, pp. 5091–5096. IEEE.

24.

Reynolds

. Flocks, herds, and schools: a distributed behavioral model. In: Proceedings of the 14th annual conference on computer graphics and interactive techniques, Anaheim, CA, July 1987, pp. 25–34. NY, USA: ACM.

25.

Weisstein

. Random walk. From MathWorld—a Wolfram Web Resource. Available at: http://mathworld.wolfram.com/RandomWalk.html.

26.

Yoshizawa

. Stability theory by Lyapunov’s second method. Tokyo: The Mathematical Society of Japan, 1966.

27.

Couzin

Krause

James

, et al. Collective memory and spatial sorting in animal groups. J Theor Biol 2002; 218: 1–11.

28.

Liu

Chu

Wang

. Collective motion in non-reciprocal swarms. J Control Theory Appl 2009; 7(2): 105–111.

29.

Xue

Zeng

Feng

, et al. Flocking motion, obstacle avoidance and formation control of range limit perceived groups based on swarm intelligence strategy. J Softw 2011; 6(8): 1594–1602.

30.

Vanualailai

Sharma

Nakagiri

. An asymptotically stable collision-avoidance system. International Journal of Non-Linear Mechanics 2008; 43: 925–932.

31.

Pappas

Kyriakopoulos

. Stabilization of non-holonomic vehicle under kinematic constraints. Int J Control 1995; 61(4): 933–947.