# Collision Avoidance Mechanism for Symmetric Circular Formations of Unitary Mass Autonomous Vehicles at Constant Speed

Authors: Vander L. S. Freitas; Elbert E. N. Macau
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Collective motion is a promising field that studies how local interactions lead groups of individuals to global behaviors. Biologists try to understand how those subjects interplay in nature, and engineers are concerned with the application of interaction strategies to mobile vehicles, satellites, robots, etc. There are several models in literature that employ strategies observed in groups of beings in nature. The aim is not to literally mimic them but to extract suitable strategies for the chosen application. These models, constituted of multiple mobile agents, can be used in tasks such as data collection, surveillance and monitoring. One approach is to use phase-coupled oscillators to design the mobile agents, in which each member is an oscillator and they are coupled according to an interconnection network. This design usually does not keep track and handle the possible collisions within the group, and real applications obviously must manage these situations to prevent the equipment from crashing. This paper introduces a collision avoidance mechanism to a model of particles with phase-coupled oscillators dynamics for symmetric circular formations.


---

## Body

## 1. Introduction

Phase-coupled oscillators may be employed to model several systems of interacting individuals, such as neurons in a brain, coupled pendulums, groups of living beings [1] and applications of collective motion [2, 3]. One of the most prominent paradigms of the field of phase-coupled oscillators is the Kuramoto model [4], in which the oscillators’ interactions are mediated via sinusoidal coupling. This model opened possibilities for the study of synchronization [5–9].Biologists try to identify local interaction rules that lead groups of agents to ordered collective motion such as flocks of birds [10, 11], schools of fish [12], and several other living beings [13]. Some models consider such knowledge, as in the case of the well-knownboids [14] which interact with each other according to three rules: attraction, repulsion and alignment.A well-known model for collective motion was proposed by Vicsek et al. [15] in which, depending on the density of the particles and the noise amplitude, the particles converge to an ordered motion. This motion is also known asflocking and is characterized by particles moving in parallel to the same direction.Sepulchre et al. [2, 16] developed a model to lead particles with coupled-oscillator dynamics to synchronized and balanced states, showing parallel and circular formations with symmetric patterns. Jain and Ghose [3] stabilized their models to formations whose centroid converges to a desired spatial coordinate. Besides, the radii of the circular formations may vary for each agent, with the same (or not) center of rotation, and is divided into synchronization subgroups.Circular formations are found in groups of fishes and bacteria [13]. Engineering applications of this kind of motion are related to tasks that require the agents to visit places periodically, like in surveillance, data collection, transport, etc.In this work we improve the control for symmetric circular formations proposed in Sepulchre et al. [2, 16] by adding a collision avoidance term, based on the balanced states of Kuramoto model. The purpose is to guarantee that the agents do not collide with the neighbors in their vicinity, so that the model can be applied to more general scenarios such as the ones founded in autonomous vehicles and satellite constellations.Moreover, we solve the inverse problem of optimization to find the optimal control parameters, using the Multiobjective Generalized Extremal Optimization (M-GEO) algorithm [17–19]. The aim is to establish a combination of parameters that leads the group to the symmetric circular formations and guarantees that the agents are not going to crash.The application of such model in real applications may require the usage of a data assimilation technique [20–22]. Its role is to incorporate the sensor readings into the model to correct the discrepancies between its state and the real state of the device. Still, the model may also be deployed along with a control strategy [23] whose role is to apply changes in the machine state, considering its inertia, limited speed, maximum angular velocity, etc.We consider here that the agents communicate according to three network schemes: (1) all-to-all, (2) a ring-like topology, and (3) a dynamic network. The first case was used in the optimization procedure and deals with agents that are able to communicate with neighbors at any distance. The ring-like topology is the circulant network topology with the fewer possible number of connections. It is applicable when the agents’ hardware is limited to the point of not being able to process all the data coming from the other agents. In this topology, each agent receives data from only two neighbors. Lastly, the agents communicate through a dynamic network whose connections are created or removed according to the Euclidean distance between agents. When a neighbor approaches the sensory region (radius) of an agent, one adds a connection between them. On the other hand, when the neighbor leaves this radius, the connection is broken.


## 2. Particles with Coupled-Oscillator Dynamics

Our underlying system consists ofN identical individuals with unitary mass and velocity. They maneuver at constant speed according to steering controls. Each particle position is given by rk=xk+iyk∈C, the direction of the velocity vector by eiθk=cos⁡θk+isin⁡θk, and phase θk∈R for k=1,…,N. The phase represents the heading angle of the particle, pointing out the direction of motion.Letr=(r1,…,rN)T∈CN be the vector of particles’ positions, θ=(θ1,…,θN)T∈TN the velocity vector, and uk(r,θ) the maneuver control (feedback control).The particle model is the following:(1a)rk˙=eiθk(1b)θk˙=ukr,θ.Whenuk=0 the particles move in a straight line towards their initial phase (heading angle) θk(0). Still, when uk=ω0, i.e., if not coupled with others, particle k moves in circular trajectories centered at ck with radius ρ=ω0-1, as shown in the following:(2)ck=rk+ω0-1ieiθk.The center of mass of the group is(3)R=1N∑j=1Nrj.Whenθk=θj for all pairs j and k, particles are synchronized. On the other hand, if the phases are spread in such a way that they cancel each other with opposite values, they are said to be balanced. These two extreme states are measured with the Kuramoto order parameter [24], given by the following equation:(4)pθ=1N∑j=1Neiθjwith eiθj=cos⁡θj+isin⁡θj, and 0≤|pθ|≤1. The order parameter corresponds to the velocity of the particles center of mass, since R˙=pθ. When pθ=0, they are in a balanced state with the center of mass in a steady position, and |pθ|=1 stands for the synchronized state, in which the center of mass moves at unitary velocity.The order parameter represents the centroid of the first harmonic of the particle headings and is used to define the potential (5) [2]:(5)U1θ=N2pθ2whose maximum and minimum are characterized by synchronized and balanced phases, respectively. This potential is a direct candidate to be a Lyapunov function, because it is strictly positive, and it is zero only in the equilibrium point, that is, when the phases are balanced, and therefore pθ=0. It reaches its unique minimum (balancing) when pθ=0, and its unique maximum (synchronization) when all phases are identical. All other critical points of U1 are saddle points [2]. Its gradient, with relation to phase θk, is described by the following:(6)∂U1∂θk=ieiθk,pθ,k=1,⋯,N.This inner product is defined byz1,z2=Re{z1∗z2}, for z1,z2∈C, and z1∗ is the conjugate of the complex number z1 [2]. Thus,(7)uk=-K∂U1∂θk=KN∑j=1Nsin⁡θk-θjwith K≠0 a gain.Sepulchre et al. [2] showed that all solutions of this system are asymptotically stable for the described case, with all-to-all coupling.


### 2.1. Circular Formations

Circular formations are achieved with a composed potential which contains an orientation control and a spacing control. Their aim is to stabilize both the relative orientations of the velocity vectors and the positions relative to the center of mass of the group, respectively [25].Let the rotation centroids of particles be represented by the vectorc=(c1,⋯,cN)∈C.Definition 1 (circular formations).
A circular formation is a relative equilibrium regime in which all particles travel around the same centroid, i.e.,ck=cj for every pair j and k.Consider the following potential:(8)Sr,θ=12Nc,Lcso that L=[lij]∈R2 is the Laplacian matrix, with(9)lij=Ninetifi=j-1ifj∈Ninet0otherwiseand Ninet being the set of neighbors of i in the interconnection network. For an all-to-all coupling, |Ninet|=N-1.The control for thek-th particle associated with this potential is shown in the following [26]:(10)ukspac=ω0KNeiθk,Lkcin which Lk is the k-th row of the Laplacian matrix. It is able to stabilize the particles rotation centers ck to the same position.The circular formations can be used in systems of multiple agents to perform tasks like area monitoring or data collection, since the particles visit the same places periodically. Hereafter, we show how to form clusters of particles inside the circular formation.Consider the following rewritten order parameter [2]:(11)pmθ=1mN∑j=1Neimθjrepresenting the m-th harmonic of the particle phases, with 0≤|pmθ|≤1/m. m|pmθ|=1 corresponds to the synchronization of the m-th phase harmonic, and pmθ=0 is its antisynchronized state. The centroid of the m=1 phase harmonic is pθ=p1θ [25].The synchronized state|pθ|=1 is characterized by θ1=θ2=⋯=θN. Note that |pθ|=1 implies m|pmθ|=1 for m>1. The splay state is given by θk=2πk/N, k=1,⋯,N; i.e., the phases are evenly distributed around the unit circle.Now consider a natural generalization of the potential (5):(12)Umθ=N2pmθ2.Theorem 2.
Letm∈N. The potential Um reaches its minimum when pmθ=0 (balancing modulo (2π/m)) and its unique maximum when the phase difference between any two phases is an integer multiple of 2π/m (synchronization modulo (2π/m)). All other critical points of Um are saddle points of Um (proof in [2]).The idea is to use linear combinations of this potential to achieve arrangements of particles inside the formation. For this purpose, considerM a positive integer, divisor of N. A (M,N) pattern is a symmetric arrangement of N phases divided into M clusters. M=1 corresponds to the synchronized state, in which all particles have the same phase, and the pattern (N,N) relates to the splay state, when the phases are uniformly distributed around the unitary circle (balanced state).An arrangement ofN particles, with M clusters is a pattern (M,N). For example, if there are 12 particles in the system and they form two clusters, of 6 particles each, this arrangement represents a (2,12) pattern.Consider the potential formed with the linear combinations ofUm:(13)UM,Nθ=∑m=1MKmUm.An arrangement(M,N) is formed if and only if the set of phases θ leads UM,N to its global minimum, with Km>0, for m=1,⋯,M-1 and KM<0 (proof in [2]).The resulting control to achieve symmetric circular formations with all-to-all interaction is the composition of controls (10) and (16), as follows:(14)uk=ω01+Keiθk,Pkc-∂UM,N∂θkfor ω0∈R is the natural frequency, K>0 a gain, c is the set of particles’ centers, and Pk is the projection matrix k-th row, defined as P=[pij]∈R2,(15)pij=N-1Nifi=j-1Notherwiseand potential gradient(16)∂UM,N∂θk=-1N∑m=1M∑j=1NKmmsin⁡mθk-θj.Figure1 shows simulations with N=6 particles with random initial conditions and control (14) for all-to-all interaction.Figure 1
Symmetric circular formation with control (14) for all-to-all interaction. Configuration: N=6, K=0.1, and ω0=0.5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
M = 1 (b)
M = 2 (c)
M = 3 (d)
M = 6The corresponding control to more general undirected interconnection networks is the following:(17)uk=ω01+Keiθk,Lkc-∂WLM,N∂θk,K>0with gradient(18)∂WLM,N∂θk=-∑m=1MKmmieimθk,Lkeimθ.The stability of (18) is guaranteed under the condition that the communication network is circulant [3, 16]. A circulant network is completely defined by its first row and each subsequent row is the previous row shifted one position to the right with the first entry of the row equal to the last entry of the previous row.


## 2.1. Circular Formations

Circular formations are achieved with a composed potential which contains an orientation control and a spacing control. Their aim is to stabilize both the relative orientations of the velocity vectors and the positions relative to the center of mass of the group, respectively [25].Let the rotation centroids of particles be represented by the vectorc=(c1,⋯,cN)∈C.Definition 1 (circular formations).
A circular formation is a relative equilibrium regime in which all particles travel around the same centroid, i.e.,ck=cj for every pair j and k.Consider the following potential:(8)Sr,θ=12Nc,Lcso that L=[lij]∈R2 is the Laplacian matrix, with(9)lij=Ninetifi=j-1ifj∈Ninet0otherwiseand Ninet being the set of neighbors of i in the interconnection network. For an all-to-all coupling, |Ninet|=N-1.The control for thek-th particle associated with this potential is shown in the following [26]:(10)ukspac=ω0KNeiθk,Lkcin which Lk is the k-th row of the Laplacian matrix. It is able to stabilize the particles rotation centers ck to the same position.The circular formations can be used in systems of multiple agents to perform tasks like area monitoring or data collection, since the particles visit the same places periodically. Hereafter, we show how to form clusters of particles inside the circular formation.Consider the following rewritten order parameter [2]:(11)pmθ=1mN∑j=1Neimθjrepresenting the m-th harmonic of the particle phases, with 0≤|pmθ|≤1/m. m|pmθ|=1 corresponds to the synchronization of the m-th phase harmonic, and pmθ=0 is its antisynchronized state. The centroid of the m=1 phase harmonic is pθ=p1θ [25].The synchronized state|pθ|=1 is characterized by θ1=θ2=⋯=θN. Note that |pθ|=1 implies m|pmθ|=1 for m>1. The splay state is given by θk=2πk/N, k=1,⋯,N; i.e., the phases are evenly distributed around the unit circle.Now consider a natural generalization of the potential (5):(12)Umθ=N2pmθ2.Theorem 2.
Letm∈N. The potential Um reaches its minimum when pmθ=0 (balancing modulo (2π/m)) and its unique maximum when the phase difference between any two phases is an integer multiple of 2π/m (synchronization modulo (2π/m)). All other critical points of Um are saddle points of Um (proof in [2]).The idea is to use linear combinations of this potential to achieve arrangements of particles inside the formation. For this purpose, considerM a positive integer, divisor of N. A (M,N) pattern is a symmetric arrangement of N phases divided into M clusters. M=1 corresponds to the synchronized state, in which all particles have the same phase, and the pattern (N,N) relates to the splay state, when the phases are uniformly distributed around the unitary circle (balanced state).An arrangement ofN particles, with M clusters is a pattern (M,N). For example, if there are 12 particles in the system and they form two clusters, of 6 particles each, this arrangement represents a (2,12) pattern.Consider the potential formed with the linear combinations ofUm:(13)UM,Nθ=∑m=1MKmUm.An arrangement(M,N) is formed if and only if the set of phases θ leads UM,N to its global minimum, with Km>0, for m=1,⋯,M-1 and KM<0 (proof in [2]).The resulting control to achieve symmetric circular formations with all-to-all interaction is the composition of controls (10) and (16), as follows:(14)uk=ω01+Keiθk,Pkc-∂UM,N∂θkfor ω0∈R is the natural frequency, K>0 a gain, c is the set of particles’ centers, and Pk is the projection matrix k-th row, defined as P=[pij]∈R2,(15)pij=N-1Nifi=j-1Notherwiseand potential gradient(16)∂UM,N∂θk=-1N∑m=1M∑j=1NKmmsin⁡mθk-θj.Figure1 shows simulations with N=6 particles with random initial conditions and control (14) for all-to-all interaction.Figure 1
Symmetric circular formation with control (14) for all-to-all interaction. Configuration: N=6, K=0.1, and ω0=0.5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
M = 1 (b)
M = 2 (c)
M = 3 (d)
M = 6The corresponding control to more general undirected interconnection networks is the following:(17)uk=ω01+Keiθk,Lkc-∂WLM,N∂θk,K>0with gradient(18)∂WLM,N∂θk=-∑m=1MKmmieimθk,Lkeimθ.The stability of (18) is guaranteed under the condition that the communication network is circulant [3, 16]. A circulant network is completely defined by its first row and each subsequent row is the previous row shifted one position to the right with the first entry of the row equal to the last entry of the previous row.


## 3. Collision Avoidance Mechanism

Considering the control of (7), when K>0 the particles achieve a balanced state, with the phases well distributed around the unitary circle such that the order parameter tends to zero. Motivated by this behavior, we propose the introduction of a repulsion termrep in (14) and (17), so that the phases of close range particles are adjusted to avoid collision, by moving apart.The repulsion term comes from a generalization of the potentialU1 from (5), for limited communication:(19)U1θ=N2pθ,pθ=12Neiθ,1N11Teiθ.Substituting the term(11T)/N=diag{1}-P by L, so that P and L are the Projection and Laplacian matrices, respectively, results in(20)WLθ=12eiθ,Leiθ.Equation (20) is also called Laplacian phase potential [26]. Its correspondent gradient is given by(21)∂WL∂θk=1Nieiθk,Lkeiθwhich corresponds to(22)1Nrk∑j∈Nrksin⁡θk-θjfor N(rk)={j∈N∣rk-rj<d} is the set of neighbors of agent k and |N(rk)| is the number of neighbors in the set N(rk). This gradient leads the solutions to the stationary points when the Laplacian matrix is circulant. We employ the gradient of the Laplacian phase potential as a repulsion term:(23)rep=KrNrk∑j∈Nrksin⁡θk-θjwith Kr>0 being the strength of the repulsion. An agent belongs to N(rk) if it is within a predefined radius d, centered at rk.The idea behind the repulsion term of (23) is that the agent k tries to balance its heading angle with its closest neighbors N(rk). This results in an adjustment of agent’s k heading angle to the opposite direction in relation to N(rk).One drawback of this approach is that it is not possible to guarantee that the matrix is circulant, sinceL is time-varying. However, the neighbors indeed repel the agent as desired.The new controls for symmetric circular formation with therep term are shown in (24) and (25) for all-to-all and limited coupling networks, respectively:(24)uk=ω01+Keiθk,Pkc-∂UM,N∂θk+rep(25)uk=ω01+Keiθk,Lkc-∂WLM,N∂θk+repwith K>0.


## 4. Optimization Problem

The gainK is related to the circular formations and the Kr to the collisions control. One has to deal with the trade-off between the gains K and Kr, since the possible combinations lead the system to numerous behaviors. When K is much higher than Kr, the particles achieve a circular formation but are susceptible to crash. The opposite (Kr≫K) is also problematic, since the clusters may never emerge due to the excessive repulsion.This trade-off betweenK and Kr characterizes a multiobjective problem, in which one wishes the agents not to collide and to keep the balanced formation. Thus, there can exist more than one optimum, and these values constitute the so-called Pareto frontier, whose number of dimensions correspond to the number of objective functions. Finding optimal values of K and Kr is the objective of this section.The basic structure of evolutionary algorithms consists of the selection of an initial population, application of random modifications and evolutionary operations into the individuals, evaluation according to a fitness criterion, and selection of the next generation [27]. In this section, we use the term “population” to the solutions of the optimization problem and not to the particles of the model.The chosen algorithm is the Multiobjective Generalized Extremal Optimization (M-GEO). The main advantage of this algorithm over others is that it has only two parameters, the number of bits to represent the design variables and an exponentτ that controls the rate of mutation of the design variables, in order to avoid local minima.In the M-GEO, each individual of the population is a bit of a sequence of bits that represents a solution. This sequence is converted into real values for the design variablesK and Kr and is then used to calculate the objective functions. This solution evolves according to operations of bit flip, following a probability distribution that generates different values of K and Kr. This mechanism guarantees that the solution is not stuck at local minima (or maxima). The algorithm heuristic guides the solution to the direction of minimization (or maximization) of the chosen objective functions. The aim is to seek for the most adapted solutions for the problem.The minimum numbern of bits necessary to represent a design variable in order to obtain a desired precision p is calculated as follows:(26)2n≥xj′′-xj′p+1such that xj′ and xj′′ are the lower and upper bounds, respectively, of variable j, with j∈{1,2,⋯,D}. We use here D=2 project variables, namely, K,Kr∈[0,1], with boundaries xj′=0 and xj′′=1. We chose our precision to be p=0.01, which results in n=7 bits for each variable, since(27)27≥1-00.01+1128≥101,from (26). A solution of the M-GEO in our problem has then 14 bits, corresponding to the two design variables.We used two objective functions:(i)
|pθ|: In (4), when |pθ|→0, we say the agents are in a balanced state. As aforementioned, these symmetric formations are indeed balanced formations. Thus, we want to minimize this parameter.(ii)
fncoll: it is the number of imminent collisions per second. When two particles i and j are too close to each other, with ∥ri-rj∥<d, for d is a threshold distance, we say the agents are in a situation of imminent collision. Each time it happens, we accumulate a score, by adding 1 unit for each second an agent is in this state. At the end of the simulation, there is a number of imminent collisions, which we want to minimize as much as possible.We model this multiobjective minimization problem as follows:(28)minpθ,fncollSubjected  to  design  variables:K,Kr∈0,1so that |pθ|∈[0,1], fncoll∈[0,tf] and tf is the maximum simulation time of the model 1.The M-GEO configurations are the following (for more details about the algorithm, see [18, 19]):(i)
τ={0.5,1.0,1.5,2.0,2.5}. This range was used in the simulations performed by [28] with monobjective problems. Reference [18] also used it in the multiobjective case, finding best results in the interval τ∈[0.5,2].(ii)
Number of bits per design variable is7, corresponding to a precision of 0.01.(iii)
Number of runs for eachτ is 50.(iv)
Total number of objective function evaluations is100000. It means that the algorithm evaluates the objective functions 2000 times for each τ.The initial conditions and parameters for the model of phase-coupled oscillators are as follows:(i)
N=6 agents randomly positioned inside a rectangle of dimensions l×l, for l=N∗π∗20(ii)
Control of (24), for all-to-all coupling.(iii)
ω0=0.05(iv)
d=5, the collision radius(v)
K,Kr∈[0,1](vi)
tf=1000s being the total time of each simulation.As we are dealing with a multiobjective optimization problem, there is not only one optimal result. Instead, we have the so-called Pareto frontier that contains the set of trade-off solutions. Every solution in this set is considered optimal. Our results are depicted in Figure2. If we run the M-GEO with a more accurate precision p and a higher number of evaluations of the objective function NFE, other optimal values may appear. It means that the values found so far are possibly suboptimal solutions.Figure 2
Pareto frontier of the multiobjective optimization problem (minimization), with objective functionspθ and fncoll and design variables K and Kr.


## 5. Simulation Results

In this section, we present three simulation scenarios of network coupling: (1) all-to-all, (2) ring-like topology, and (3) dynamic network.The choice of which solution one should use in the simulations is possible. One approach is to choose the one whose distance until the utopian solution is minimum. The utopian solution would be composed of the best possible values for each objective function. In our case, this point is(|pθ|,fncoll)=(0,0). The closest solution to this point is generated by K=0.00787402 and Kr=0.0866142. In fact the scales for fncoll and |pθ| are completely different and the distance is dictated pretty much by fncoll. Nevertheless, we would choose this solution anyways, since the symmetric circular formations are guaranteed and the number of collision is minimum when compared to the others.The optimization process did not impose any hierarchy relation between the objective functions|pθ| and fncoll. Indeed, we seek for combinations of K and Kr that achieve the symmetric circular formations and avoid collisions. If the optimization procedures were applied considering only the objective function fncoll, the particles would probably not collide at the cost of never achieving the circular shapes.The following simulations are then performed with control gainsK=0.00787402 and Kr=0.0866142.


### 5.1. All-to-All

The simulations for the all-to-all communication topology, with the optimal control parameters, are presented in Figure3, with N=6, ω0=0.05, and d=5. Particles seem to establish the formation and the clusters, accordingly. Figure 4 shows simulations with not optimal parameters, for comparison purposes. One may observe that the balancing between collision avoidance and the clusters does not hold in this last setup.Figure 3
All-to-all: symmetric circular formation with control (24). Configuration: N=6, K=0.00787402, Kr=0.0866142, ω0=0.05, ρ=20, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
M = 1 (b)
M = 2 (c)
M = 3 (d)
M = 6Figure 4
All-to-all (not optimal): Symmetric circular formation with control (24). Configuration: N=6, K=0.1, Kr=0.1, ω0=0.05, ρ=20, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
M = 1 (b)
M = 2 (c)
M = 3 (d)
M = 6We take into account the fact that each agent has a repulsion region of radiusd=5. The neighbors inside this region are used to calculate the repulsion term rep for each agent. Here, we consider the agents are particles, without a real size. However, in real applications, the bigger the agents are the higher the radius d and/or the gain Kr must be, as they have to start to avoid the neighbors before they reach a critical distance. The parameters d and Kr state the initial distance considered for the usage of rep and also the maneuver intensity.


### 5.2. Ring-like Topology

Now, consider the case in which the agents are able to communicate to each other at any distance, but they have limited processing capacity. This scenario is challenging, but possible to handle if we impose a fixed network topology for the agents’ communication, with fewer connections than the all-to-all topology. One good option is the ring-like topology, since it is circulant and has the minimum possible number of edges (connections). It allows the agents to have only two fixed neighbors and therefore do not overload their processing capacity.Figure5 exhibits simulation results for a ring-like coupling topology, using control (25), and Figure 6 presents results for simulations with not optimal control parameters, for comparison purposes. The control (25), for network-based coupling, is an approximation of the control (24), for the all-to-all case. It means that the results are not completely equivalent.Figure 5
Ring-like network topology: Symmetric circular formation with control (25). Configuration: N=6, K=0.00787402, Kr=0.0866142, ω0=0.05, ρ=20, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
M = 1 (b)
M = 2 (c)
M = 3 (d)
M = 6Figure 6
Ring-like network topology (not optimal): symmetric circular formation with control (25). Configuration: N=6, K=0.1, Kr=0.1, ω0=0.05, ρ=20, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
M = 1 (b)
M = 2 (c)
M = 3 (d)
M = 6The(N,N) pattern (splay state), that is when the phases are all uniformly distributed around the unitary circle, seemed to not have been achieved with this setup. The same problem is also observed in Figure 3. It is probably related to the rotation radius ρ of the particles. The bigger it is, the more distributed inside the formation the particles look like.


### 5.3. Dynamic Network

We now show simulation results using dynamic network topologies. Each agent has a vision radius, simulating a limited sensory region. This region has a radiusγ, indicating that if an agent j is at a distance less than or equal to γ from agent i, then j is said to be neighbor of i. This γ must be larger than d.There are no guarantees that the network is circulant, for any sensory region radiusγ. Perhaps, an alternative to real applications is to establish a natural frequency ω0 so that the rotation radius ρ is equivalent to the sensory region of the agents. It allows the agents to see nearly all the others. If γ=2ρ+δ, we can make sure all the agents will see each other, for certain δ>0, depending on the initial conditions.The aforementioned scheme is applicable if the agents’ hardware is able to sense all the agents inside the radiusγ. It is suitable when considering dynamic setups with agents being introduced, removed, or replaced online.Figure7 presents simulation results for symmetric circular formations of M=3 clusters, for different γ values. When γ<2ρ+δ, for δ>0, the circular formations rarely occur, due to the fact that the resulting networks are not circulant (Figure 7(a)). Figure 8 illustrates results of simulations with non-optimal control parameters K and Kr.Figure 7
Dynamic networks: symmetric circular formation with control (25). Configuration: N=6, K=0.00787402, Kr=0.0866142, ω0=0.05, ρ=20, M=3, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
γ = 40 (b)
γ = 50 (c)
γ = 60Figure 8
Dynamic networks (not optimal): symmetric circular formation with control (25). Configuration: N=6, K=0.1, Kr=0.1, ω0=0.05, ρ=20, M=3, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
γ = 40 (b)
γ = 50 (c)
γ = 60Figure8 shows that results are better for the nonoptimal configuration, when γ=40. The optimal control parameters found for all-to-all coupling seem not suitable for the dynamic case, which suggests the employment of a specific optimization procedure.The presented strategy for collision avoidance seemed to be effective in safely maintaining the agents close to each other without crashing. The better scenario is the all-to-all communication, because of its simplicity. However, it is possible that the agents’ hardware is not able: to process all the information coming from the neighbors or to send (receive) data to (from) long distances. These two cases are managed with the control for limited communication, which is an approximation of the all-to-all scenario.


## 5.1. All-to-All

The simulations for the all-to-all communication topology, with the optimal control parameters, are presented in Figure3, with N=6, ω0=0.05, and d=5. Particles seem to establish the formation and the clusters, accordingly. Figure 4 shows simulations with not optimal parameters, for comparison purposes. One may observe that the balancing between collision avoidance and the clusters does not hold in this last setup.Figure 3
All-to-all: symmetric circular formation with control (24). Configuration: N=6, K=0.00787402, Kr=0.0866142, ω0=0.05, ρ=20, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
M = 1 (b)
M = 2 (c)
M = 3 (d)
M = 6Figure 4
All-to-all (not optimal): Symmetric circular formation with control (24). Configuration: N=6, K=0.1, Kr=0.1, ω0=0.05, ρ=20, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
M = 1 (b)
M = 2 (c)
M = 3 (d)
M = 6We take into account the fact that each agent has a repulsion region of radiusd=5. The neighbors inside this region are used to calculate the repulsion term rep for each agent. Here, we consider the agents are particles, without a real size. However, in real applications, the bigger the agents are the higher the radius d and/or the gain Kr must be, as they have to start to avoid the neighbors before they reach a critical distance. The parameters d and Kr state the initial distance considered for the usage of rep and also the maneuver intensity.


## 5.2. Ring-like Topology

Now, consider the case in which the agents are able to communicate to each other at any distance, but they have limited processing capacity. This scenario is challenging, but possible to handle if we impose a fixed network topology for the agents’ communication, with fewer connections than the all-to-all topology. One good option is the ring-like topology, since it is circulant and has the minimum possible number of edges (connections). It allows the agents to have only two fixed neighbors and therefore do not overload their processing capacity.Figure5 exhibits simulation results for a ring-like coupling topology, using control (25), and Figure 6 presents results for simulations with not optimal control parameters, for comparison purposes. The control (25), for network-based coupling, is an approximation of the control (24), for the all-to-all case. It means that the results are not completely equivalent.Figure 5
Ring-like network topology: Symmetric circular formation with control (25). Configuration: N=6, K=0.00787402, Kr=0.0866142, ω0=0.05, ρ=20, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
M = 1 (b)
M = 2 (c)
M = 3 (d)
M = 6Figure 6
Ring-like network topology (not optimal): symmetric circular formation with control (25). Configuration: N=6, K=0.1, Kr=0.1, ω0=0.05, ρ=20, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
M = 1 (b)
M = 2 (c)
M = 3 (d)
M = 6The(N,N) pattern (splay state), that is when the phases are all uniformly distributed around the unitary circle, seemed to not have been achieved with this setup. The same problem is also observed in Figure 3. It is probably related to the rotation radius ρ of the particles. The bigger it is, the more distributed inside the formation the particles look like.


## 5.3. Dynamic Network

We now show simulation results using dynamic network topologies. Each agent has a vision radius, simulating a limited sensory region. This region has a radiusγ, indicating that if an agent j is at a distance less than or equal to γ from agent i, then j is said to be neighbor of i. This γ must be larger than d.There are no guarantees that the network is circulant, for any sensory region radiusγ. Perhaps, an alternative to real applications is to establish a natural frequency ω0 so that the rotation radius ρ is equivalent to the sensory region of the agents. It allows the agents to see nearly all the others. If γ=2ρ+δ, we can make sure all the agents will see each other, for certain δ>0, depending on the initial conditions.The aforementioned scheme is applicable if the agents’ hardware is able to sense all the agents inside the radiusγ. It is suitable when considering dynamic setups with agents being introduced, removed, or replaced online.Figure7 presents simulation results for symmetric circular formations of M=3 clusters, for different γ values. When γ<2ρ+δ, for δ>0, the circular formations rarely occur, due to the fact that the resulting networks are not circulant (Figure 7(a)). Figure 8 illustrates results of simulations with non-optimal control parameters K and Kr.Figure 7
Dynamic networks: symmetric circular formation with control (25). Configuration: N=6, K=0.00787402, Kr=0.0866142, ω0=0.05, ρ=20, M=3, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
γ = 40 (b)
γ = 50 (c)
γ = 60Figure 8
Dynamic networks (not optimal): symmetric circular formation with control (25). Configuration: N=6, K=0.1, Kr=0.1, ω0=0.05, ρ=20, M=3, and d=5. The red circles correspond to the agents, and the blue circle is their center of mass.
(a)
γ = 40 (b)
γ = 50 (c)
γ = 60Figure8 shows that results are better for the nonoptimal configuration, when γ=40. The optimal control parameters found for all-to-all coupling seem not suitable for the dynamic case, which suggests the employment of a specific optimization procedure.The presented strategy for collision avoidance seemed to be effective in safely maintaining the agents close to each other without crashing. The better scenario is the all-to-all communication, because of its simplicity. However, it is possible that the agents’ hardware is not able: to process all the information coming from the neighbors or to send (receive) data to (from) long distances. These two cases are managed with the control for limited communication, which is an approximation of the all-to-all scenario.


## 6. Conclusions

For real applications involving vehicle in formation movement, namely, mobile robots, unmanned aerial vehicles, and others, one needs to define a collision avoidance mechanism. For this purpose, based on the Kuramoto model, in a model of phase-coupled oscillators for symmetric circular formations, a specific extra term was added. When an agent has neighbors in its vicinity, this term tries to balance its phase with them in such a way that it goes to their opposite direction.The concept of vicinity is defined by a radius around the agent and its size depends also on the agents size, because of the reaction time before an imminent collision. The bigger the agents are the higher the radius must be, as they have to start maneuvering before they reach a critical distance.We solved the inverse problem of optimization to find the proper parameters for the model, in order to both reach the symmetric circular formations and prevent the agents from colliding. This characterizes a multiobjective problem, which we solved with the evolutionary algorithm M-GEO.To depict the results, we conducted simulations with the resulting parameters for all-to-all coupling, ring-like network topology and dynamic networks. The all-to-all coupling is useful when the agents do not have hardware limitations to both send (receive) data to (from) long distances and to process all the information received from the neighbors. However, when any of these two problems is present, the ring-like and dynamic topologies may be useful.The results with the collision avoidance mechanism showed to be effective for its purpose. The next step of this research is to deploy this model into real applications and to also consider communication delays among agents.



---

*Source: 6291082-2018-06-07.xml*