Control of Agent Swarms Using Generalized Centroidal Cyclic Pursuit Laws

1 Introduction

Agents swarms are multi-agent systems or groups of autonomous mobile agents used for automated collaborative operations. The challenge in these applications is to design intelligent control laws such that the agents behave as desired without a centralized controller or global information. Linear cyclic pursuit is one such control law which is designed to mimic the behavior of biological organisms. Bruckstein et al. [Bruckstein et al., 1991] modelled this behavior with continuous and discrete pursuit laws and examined the evolution of global behavior. Convergence to a point in linear pursuit is the starting point to the analysis of achievable global formation among a group of autonomous mobile agents as discussed by Lin et al. [Lin et al., 2004] and Marshall et al. [Marshall et al., 2004a]. The stability of both linear and nonlinear pursuit has been studied in Marshall et al. [Marshall et al., 2004b].

The present work is a generalization of the cyclic pursuit problem discussed in the literature. Marshall et al. [Marshall et al., 2004b] studied the stability of linear system of n agents with equal and positive controller gains. Bruckstein et al. [Bruckstein et al., 1991] briefly mention a case where the controller gain may be inhomogeneous but positive. Sinha et al. [Sinha and Ghose, 2006a], [Sinha and Ghose, 2006b] further generalized it by considering negative gains also. The controller gains are considered to be decision variables to determine the global behavior of the system. In the present paper, we assume inhomogeneous gains that can take both positive and negative values. Further, the connection among the agents are generalized through a pursuit sequence that makes the agents follow the weighted centroid of the other agents.

We define a pursuit sequence as a set of weights used by an agent to find its leader. The range of values of the controller gain that stabilizes the system is obtained. Selecting from among the stabilizing controller gains appropriately, it is possible to control the point of convergence (reachable point) of the group of agents.

One of the behaviors that is important for various applications of such groups of autonomous agents is obtaining directed motion in a particular direction. We show that when the system is unstable, under certain conditions, all the agents' movement converge to a single asymptote. We obtain the condition on the unstable controller gains for which such motion is achievable. Finally, we show that generalized linear cyclic pursuit with heterogenous gains posses several interesting invariance properties with respect to the sequence of pursuit between agents. In particular, we show stability invariance, reachable point invariance and invariance of an asymptotic point in the directed motion case. We also prove these invariance properties for finite number of switching between different cyclic pursuit sequences.

2 Formulation of centroidal cyclic pursuit

Generalized linear cyclic pursuit is formulated using n agents numbered from 1 to n in a d dimensional space. The position of the agent i at any time t ≥ 0 is given by

Control of agent i is ui. The kinematics are given as

where ∑n-1 j=1 ηj = 1. Note that, each individual term, in the above expression, is of the form ηjZi+j mod n. Thus, agent i pursues a weighted centroid of the other agents and ηj is the weight given by agent i to the position of agent (i + j), modulo n, using which the centroidal pursuit is executed. The weight vector η = (η1, . . . , ηn-1) is called the pursuit sequence. One of the simplest pursuit sequences is η = {1, 0, . . . , 0}, where the first agent follows only the second, the second follows only the third and so on till the last agent follows only the first. Further, ki is the controller gain of agent i and ki need not be the same for all the agents. Using different values for the controller gains K = {ki}ni=1 , we analyze the behavior of the agents.

From the control law (2), we see that, for every agent i, each coordinate yδ i , δ = 1, · · · , d, of Zi, evolves independently in time. Hence, these equations can be decoupled into d identical linear system of equations represented as

where

and ∑ni=2 ηi = 1. Note that A is singular. Here, X = [x1, x2, · · · , xn], where each xi represents a yδ i for some δ = 1, · · · , d. We drop the superscript 'δ' since the equations are identical in all the d-directions (except for the initial conditions). Let η = {ηi}n-1 i=1 . The characteristic equation of A is

where Bi, i = 0, . . . , n - 1 are functions of η and K. The following properties can be shown to hold:

1. B0 = 0

We omit the proof of the above properties. These properties can also be easily verified using any mathematical (symbolic) toolbox like Mathematica. Since, B1 is not necessarily zero, there is one and only one root of A at the origin. The solution of (3) in the frequency domain is

Expanding the ith component of X(s), we get

where, biq(s) are functions of K and s. Let the non-zero roots of (5) be Rp = (σp + jωp), p = 1, · · · , ¯n - 1, where ¯n is the number of distinct roots of (5). Taking inverse Laplace transform

where, np is the algebraic multiplicity of the pth root and

Here, xf corresponds to the root s = 0.

The trajectory xi(t) of agent i depends on the eigenvalues Rp = (σp + jωp), p = 1, · · · , ¯n, of A which, in turn, are functions of the gains ki, i = 1, · · · , n. If all the eigenvalues of A have negative real parts, then the system (3) is stable. In the next section, we will find the combination of the gains for which system (3) is stable.

3 Stability analysis

If the system (3) is stable, as t → ∞, ˙xi(t) = 0, ∀i. This implies that eventually all the agents will converge to a point. Thus, we have the following result.

Theorem 1 The system of n agents, given by (3), will converge to a point if and only if the following conditions hold

• (a) At most one ki is negative or zero, that is, at most for one i, ki ≤ 0 and kj > 0, ∀j, j ̸= i.

Proof. The "if" part is proved using Gershgorin's Disc Theorem [Horn and Johnson, 1987]. We consider three cases:

Case 1: All gains are positive.

Here, ki > 0, ∀i. Therefore, condition (b) is automatically satisfied. The Gershgorin's discs are shown in Figure 3(a). Since one and only one root of (5) is at the origin, the remaining ¯n1 roots of (5) must be on the LHS of the s-plane and have negative real parts. It remains to be shown that the root at the origin does not contribute to the dynamics of the system.

Consider a subspace S = {x ∈ Rn∣∣∣[ϕ/k1 ϕ/k2 · · ·

ϕ/kn]x = 0; ϕ ̸= 0; ϕ = constant}. We can show that S is A-invariant and there exists a linear transformation using a non-singular matrix P , given by,

such that the new coordinate system is ˆX = PX and (3) transforms to,

where the elements of A are functions of K. Here, ˙ˆxn = 0. Thus, we can disregard exactly one zero eigenvalue and determine stability based on the remaining n - 1 eigenvalues of A. Hence, the system is stable when ki > 0, ∀i.

Case 2: One gain is zero and other gains are positive.

Here, for some i, ki = 0 and kj > 0, ∀j, j ̸= i. Gershgorin's discs is the same as in Case 1 (Fig 3(a)). Following similar arguments as in Case 1, we can show that the system is stable. Case 3: One gain is negative and other gains are positive.

The Gershgorin discs, when ki < 0 and kj > 0, ∀j, j ̸= i, are as shown in Figure 3(c). When the system becomes unstable, from the continuity of the root locus, the roots have to pass through the origin to move from LHS to RHS of the s-plane. We can find the point at which the first root crosses the origin by equating the coefficient of s in (5) to zero, i.e.,

Since (1 - B1) > 0, from property 2 of (5), therefore, if condition (b) is satisfied, the system is stable.

The "only if" part is proved by contradiction, assuming the system is stable but any one or both the conditions do not hold. We omit details. □

Corollary 1: Consider n mobile agents with kinematics given by (3). The agents will converge to a point if and only if not more than one of the agents (say agent p) has negative or zero controller gain bounded below by ¯ kp, i.e., kp > ¯ kp and all other agents have ki > 0, ∀ i, i ̸= p where ¯ kp is given by

Proof. The proof follows directly from Theorem 1. □

4 Rendezvous

Theorem 2 (Reachable Point) If a system of n-agents have their initial positions at Zi0 and gains K = {ki}ni=1 , ∀i, that satisfy Theorem 1, then they converge to Zf given by,

where Zf is a reachable point for this system of n agents.

Proof. Since system (3) is stable, all non-zero eigenvalues of A have negative real parts. Therefore, as t → ∞, the second term of (8) goes to zero and limt→∞ xi(t) = xf . This means that eventually the agent i converges to the point xf , given by (10), in the corresponding δth direction. Thus, the rendezvous point in Rd is obtained by replacing xf by the vector [y1 f , · · · , yd f ]T in the corresponding d dimensions. □

Now, let us denote Zf(Zi0,K) as the reachable point obtained from the initial point Zi0 and gain K that satisfies Theorem 1. Then the set of reachable points (called the reachable set), at which rendezvous occurs starting from the initial point Zi0, is denoted as Zf (Zi0) and is defined as,

The agents can be made to converge to any desirable point within this reachable set by suitably selecting the gains. Some examples of Zf (Zi0) is given in Figure 2 for d = 2.

5 Directed motion

When the system (3) is not stable, we can obtain directed motion of the agents under certain condition.

Definition: The most positive eigenvalue of a linear system is the eigenvalue with the largest real part.

Theorem 3 Consider a system of n-agents with kinematics given by (3). The trajectory of all the agents converge to a straight line as t →∞ if and only if the most positive eigenvalue of (3) is real and positive.

Proof. If the most positive eigenvalue is positive, then (3) is unstable. Hence, the agents will not converge to a point. Let the unit vector along the velocity vector of agent i at time t be -→vi (t) = (¯ vi (t))-1 [v1 i (t) v2 i (t) · · · vd j (t)]T where, vδ i (t) = ˙yδ i (t), ∀δ and ¯ vi(t) = √{ ˙y1 i (t)}2 + · · · + { ˙yd i (t)}2 . If all the agents have to converge to a straight line as t →∞, then

The above equation can be rewritten for all i, j ∈ {1, . . . , n} and for all δ, γ ∈ {1, . . . , d} as t →∞, as follows

where, θγδ is a constant independent of time and the agent identity. Thus, to prove that the agents move in a straight line, we have to show that (18) is true. Considering any one of the d-dimensions and differentiating (8), we get ˙xi(t) as

Thus, V has the same dynamics as (3) but with different initial conditions. The time response of the speed of the ith agent, vi(t) can be obtained similar to (8) as

Comparing (19) and (21) and matching the coefficients, we get

whereMpq(K, η,Rp) is independent of the agent identity i.

Now, the instantaneous slope of the trajectory of the agent i in the (γ, δ) plane as t → ∞ can be simplified if ωm = 0 σm ≥ σp, ∀p is given by

Let σm > σp, ∀p, p ̸= m. As t → ∞, it can be seen that with simple mathematical manipulations all the terms go to zero as except for p = m. Now, if ωm = 0 (which implies that the most positive eigenvalue is real), the above equation simplifies to

where, θγδ is independent of time and the agent identity i. It is a constant and a function of ki, i = 1, · · · , n, and the initial positions of the agents Zi0, ∀i. Now, following a similar procedure, we have

Therefore, as t →∞, ˙yδ i / ˙yγ i = (yδ i -yδ f )/(yγ i - yγ f ). Hence, (yγ f , yδ f ) is on the straight line along which the agents motion converges as t → ∞.

Now, to prove the converse, let ωm ̸= 0, then

From the above, we see that if ωm ̸= 0, the agents will not converge to a straight line. □

Remark 1: The straight line asymptote of the trajectories (after sufficiently large time) passes through Zf = [y1 f , y2 f · · · , yd f ]T ∈ Rd which is called the asymptote point. Remark 2: When ωm ̸= 0, the agents do not converge to a straight line. However, the direction in which the ith agent moves, after a sufficiently large t, can be calculated from (25). Remark 3: Even though the agents converge to a straight line, the direction of motion of the agents need not be the same. In fact, if the gain of only one agent is negative, all the agents move in the same direction, otherwise they move in two opposite directions along the straight line. The direction in which an agent i will move is determined from the sign of the coefficient, aiprq with p = m, q = 1, r = np of xi(t) in (8).

6 General pursuit sequence and switching invariance results

In the problem formulation, we have assumed a particular sequence in which an agent pursues another. We now show that even where the connection (or more generally, the pursuit sequence) among the agents is changed, certain properties of the system remain unchanged. This is important in certain applications where the connectivity or the trajectory have to be changed during the process due to some constraints, without changing the goal.

Definition: Let the set of all pursuit sequences be Q and ηi , ηj ∈ Q be two pursuit sequences. When there is a change in the pursuit sequence of the agents fromηi to ηj , it is called switching. If switching occurs a finite number of times during the process, then we call it a finite switching case.

Theorem 4 The stability of the linear cyclic pursuit is pursuit sequence invariant.

Proof. The stability of (3) depends on the roots of ρ(s) = 0. As long as there is a cyclic pursuit among the agents, ρ(S) remains unchanged even when the pursuit sequence is different. Thus, stability of the system is pursuit sequence invariant. □

Theorem 5 The reachable point of a stable linear cyclic pursuit is pursuit sequence invariant.

Proof. Consider (15), which gives the coordinates of the rendezvous point. This equation is independent of the sequence of connection among the agents. Hence, the rendezvous point is independent of the connectivity of the agents. □

Theorem 6 The asymptote point of an unstable linear cyclic pursuit system, satisfying Theorem 3, is pursuit sequence invariant.

Proof. For the agent i, as t →∞, the unit velocity vector can be written using (23) as

Since θγδ, ∀γ, δ; γ ̸= δ depends on the connection of the agents, the unit velocity vector changes as the connection is changed. This implies that for different connections, the asymptote to which the agents converge is different. However, from (24), it can be seen that all the asymptotes pass through the point Zf (the asymptote point), which is independent of the connection. In other words, all the asymptotes radiate from Zf , but their direction depends on the connection between the agents. □

The pursuit sequence invariance property discussed so far is based on the assumption that the pursuit sequence between the agents remained constant throughout time. Now, we show that even if the pursuit sequence between the agents change during the process, some of the properties remain unchanged.

Corollaries given below follows directly from the above Theorems.

Corollary 2: (Stability) The stability of the linear cyclic pursuit is invariant under finite pursuit sequence switching.

Corollary 3:(Reachability with switching) The reachable point of a stable linear cyclic pursuit system is invariant with finite pursuit sequence switching.

Corollary 4:(Directed motion with switching) The asymptote point of an unstable linear cyclic pursuit system, satisfying Theorem 3, is invariant with finite pursuit sequence switching.

Note that the trajectory of the agents may change due to switching but the stability, reachable point and the asymptote point are not changed.

7 Simulation results

A system of 5 agents are considered in R3 . The initial positions of the agents are S = [(2, 1, 1), (4, 9, 4), (6, 7, 7), (8, 3, 9), (10, 2, 2)]. The pursuit sequences considered in these simulations are η0 = (0.4, 0.3, 0.2, 0.1), η1 = (0.1, 0.1, 0.1, 0.7) and η2 = (0, 0, 0, 1). Different sets of gains are selected arbitrarily for simulation to illustrate the results obtained in this paper. We assume that the agents know the gains and pursuit sequences.

Case 1: The pursuit sequence of the agents is η0 and K = [4, 6, 8, 10, 12] which satisfies Theorem1. The trajectories of agents are shown in Figure 3. The system is stable. The agents converge to Zf = [4.9, 4.3, 3.9]T which satisfies (15). Case 2: Pursuit sequence is η0 and K = [4, 6, 8, 10, 0]. This set of gains satisfy Theorem 1. The agents converge at Z5(0) = [10, 2, 2]T as shown in Fig. 4.

Case 3: The pursuit sequence is η0 andK = [4, 6, 8, 10, - 1]. Here, ¯ k5 = -1.56 and according to Theorem 1, this system is stable (Fig. 5). The agents converge at Zf = [20.3256,-2.5814,-1.9302]T and satisfies (15). Case 4: Pursuit sequence is η0 . andK = [4, 6, -2, 10, -5]

are considered, keeping the same pursuit sequence η0 . This y 1

y 1

Figure 5: The trajectories of a stable system of 5 agents with one gain negative and the other gains positive.

system is unstable as it violates Theorem 1. The eigenvalues of this system are {4.9245, 0, - 0.6796, - 6.3871, - 10.8578} . It can be seen that the most positive eigenvalue is positive satisfying Theorem 3 and the agents converge to a straight line as can be seen in Figure 6. Moreover, we can see that some agents move in one direction while the others in the opposite direction.

Case 5: The pursuit sequence is η0 and K = [4, 6,-2,-3,-3] and . The gains do not satisfy Theorem 1. The eigenvalues are {3.3729 ± j0.1070, 0,-2.3447,-6.4010}. Since the most positive eigenvalue is not real, the agents will not converge to a straight line. This can be seen in Figure 7, where we can see that the direction of motion of the agents varies with time.

Case 6: The switching invariance of the reachable point is shown in Figure 8 for the system with gains K = [4, 6, 8, 10, 12] and the pursuit sequence of η1 , η0 and η2 , in this sequence. The dotted line shows the trajectory if there was no switching. It can be seen from the figure that the reachable point is remains unchange for finite number of switching.

Case 7: Here, we show the switching invariance of

y 1

Figure 6: The trajectories of an unstable system of 5 agents with two gains negative and the other gains positive.

y 1

Figure 8: Switching invariance of reachable point. Solid line: switching between η1 , η0 and η2 and Dotted line: no switching (pursuit sequence η1 )

the asymptote point. The gains considered are K = [4, 6, 8, 10, - 5], which satisfy Theorem 3. The pursuit sequence switches from η1 to η0 to η2 . The trajectories are shown in Figure 9. We see that even with switching, the asymptote point remains the same.

Case 8: A swarm of 20 agents are considered to show the scalability of generalized centroidal cyclic pursuit. The initial positions of the agents are chosen randomly. The gains of the agents are positive and the pursuit sequence is selected arbitrarily. Fig 10 shows the rendezvous of the swarm of agents.

8 Conclusions

Cyclic pursuit strategies have recently been of much interest among researchers in swarm intelligence. In this paper, we generalize the concept of cyclic pursuit in which an agent pursues a weighted average of the remaining agents. The system of agents using generalized centroidal cyclic pursuit is analyzed. The set of controller gains are determined for which the system will remain stable. If the system is stable, all the agents converge to a point. The rendezvous point is

y 1

Figure 10: The trajectories of a swarm of 20 agents

obtained as a function of the gains and the initial positions. If the system is unstable, we found the condition under which the agents demonstrate directed linear motion. An interesting result shown here is that the stability, rendezvous point and the asymptote of the directed motion are all invariant to pursuit sequence and switching.