# Identification of V-Formations and Circular and Doughnut Formations in a Set of Moving Entities with Outliers

Authors: Francisco Javier Moreno Arboleda; Jaime Alberto Guzmán Luna; Sebastian Alonso Gomez Arias
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Diverse movement patterns may be identified when we study a set of moving entities. One of these patterns is known as a V-formation for it is shaped like the letter V. Informally, a set of entities shows a V-formation if the entities are located on one of their two characteristic lines. These lines meet in a position where there is just one entity considered the leader of the formation. Another movement pattern is known as a circular formation for it is shaped like a circle. Informally, circular formations present a set of entities grouped around a center in which the distance from these entities to the center is less than a given threshold. In this paper we present a model to identify V-formations and circular formations with outliers. An outlier is an entity which is part of a formation but is away from it. We also present a model to identify doughnut formations, which are an extension of circular formations. We present formal rules for our models and an algorithm for detecting outliers. The model was validated with NetLogo, a programming and modeling environment for the simulation of natural and social phenomena.


---

## Body

## 1. Introduction

Diverse movement patterns may be identified when we study a set of moving entities, for example, a flock of birds [1] and a school of fish [2]. One of these patterns is known as a V-formation for it is shaped like the letter V; see Figure 1. Another movement pattern is known as a circular formation for it is shaped like a circle; see Figure 2.Figure 1
V-formation in birds. Source: [9].Figure 2
Circular formation in a fish bank. Source: [21].Informally, a set of entities shows a V-formation if the entities are located on one of their two characteristic lines. The lines meet in a position where there is just one entity considered the leader of the formation [3]. Several authors have analyzed V-formations. In [4, 5], there is an attempt to explain from a physical point of view the reasons why certain species of birds, such as Canadian geese (Branta canadensis), red knots (Calidris canutus), and plovers (Calidris alpina), tend to fly this way.Other authors try to simulate V-formations at a computational level. For instance, Nathan and Barbosa [6] propose a model based on rules that allows us to generate V-formations depending on specific parameters. The authors validated their model using NetLogo [7], a programming and modeling environment to simulate natural and social phenomena.On the other hand, a circular formation is a set of entities grouped around a common center and where the entities’ distance to the center is less than a given threshold. Regarding related works with circular formations, we identified the following.In [8] the authors experimented with a set of data referring to the movement of different animal species. It was found that despite being in different ecosystems, species follow similar behavioral patterns. The authors also tried to model general grouping behaviors of fish, birds, insects, and even people. One of these behaviors is circular formation in which they identified physical forces: attraction, repulsion, alignment, and frontal interaction.On the other hand, researchers in the field of robotics and in control theory, inspired by social grouping phenomena and by the patterns of birds and fish, have developed applications to coordinate the movement of multivehicle systems. Among these patterns are circular [9] and V-formations; see Figure 3.Robots in circular formation and planes in V-formation. Sources: [11, 12].
(a)
(b)On the other hand, regardless of the type of formation, Reynolds [2, 10] proposes a computer model of coordinated animal motion for bird flocks and fish schools. His model considers three simple rules that act upon individuals: (i) separation: steer to avoid crowding local flockmates, (ii) alignment: steer towards the average heading of local flockmates, and (iii) cohesion: steer to move toward the average position of local flockmates.Although the previous works allow the simulation of a set of moving entities, they are not aimed at the explicit identification of V-formations and circular formations. The identification of these types of formations may be useful in fields as zoology, to analyze the movement of birds [3] and fish [11], and in the military and videogames where squadrons of combat planes, ships, and robots usually assume these types of formations [3, 12]. V-formations also usually appear in stock markets (stock prices) [13]. In this direction the model of Andersson et al. [14], although it is not aimed at the explicit identification of formations, identifies an entity leader in a set of moving entities. We use their model as the basis for identifying V-formations and circular formations, as we will show in our paper.This paper is organized as follows. In Section2, we present our models for V-formations and circular and doughnut formations, which are an extension of circular formations. In Section 3, we present support for outliers in our models. In Section 4, we present experiments. In Section 5, we conclude the paper and propose future works.


## 2. V-Formations and Circular and Doughnut Formations

### 2.1. Andersson’s Model

Next, we present the essential elements of Andersson’s model [14].Consider a setE of n entities {
e
1
,
e
2
,
…
,
e
n
} that move in a space, usually in a region during a time interval [
t
1
,
t
f
]. This space is represented by the Euclidian plane. Time is represented continuously. T
p denotes an infinite set of time-points: {
t
∣
t
∈
[
t
1
,
t
f
]
}. On the other hand, T
s denotes a finite set of discrete time-points {
t
1
,
t
2
,
…
,
t
f
}. Every t
i
∈
T
s represents a time-step and corresponds to a time-point in which the position of a moving entity (and perhaps other data) was recorded. A unit-time-interval is an open interval between two consecutive time-steps, that is, (
t
i
-
1
,
t
i
), for all t
i
∈
T
s, i
≠
1.The coordinates of an entity at a time-point are given by a pair of functionsx
p
o
s and y
p
o
s, both having the signature E
×
T
p
→ Real. Andersson assumes that between two consecutive time-steps an entity moves along a straight line with constant direction and constant velocity. This assumption has been adopted in other works (see [15–17] for a discussion). Therefore, in such a model in order to be practical enough, the recording frequency of the positions of moving objects should be adapted to the nature of each domain. For example, when detecting bird formations the elapsed time between two consecutive time-steps should not be longer than 30 seconds.Consider an entitye
i at a time-point t, where t
x
-
1
<
t
<
t
x, t
x
∈
T
s, x
≠
1; then the direction of e
i at t, denoted by d
(
e
i
,
t
), is the angle specified by the straight line segment that goes from (
x
p
o
s
(
e
i
,
t
x
-
1
), y
p
o
s
(
e
i
,
t
x
-
1
)
) to (
x
p
o
s
(
e
i
,
t
x
)
,
y
p
o
s
(
e
i
,
t
x
)
); see Figure 4. The angle d
(
e
i
,
t
) is between [
0
,
2
π
). Andersson declares the direction of an entity at a time-step t
x to beundefined, because at a time-step an entity might change its direction (for more details see [14]).Figure 4
d
(
e
i
,
t
): angle of entity e
i at a time-point t.The front region of an entitye
i is a region associated with e
i at a time-point t, where t
x
-
1
<
t
<
t
x, t
x
∈
T
s, x
≠
1, which represents the perception region of an entity, for example, a visual or an auditive range. The front region of e
i is defined as follows: consider three straight line segments s
0, s
1, and, s
2, each of length r. Each segment has an endpoint at (
x
p
o
s
(
e
i
,
t
)
,
y
p
o
s
(
e
i
,
t
)
). The direction of the segment s
0 is d
(
e
i
,
t
). Segments s
1 and s
2 form angles of α
/
2 and -
α
/
2
(
0
≤
α
<
2
π
) with regard to segment s
0, respectively. The circular sector (a wedge-shaped region) with a radius r
(
r
≥
0
), delimited by s
1 and s
2, makes up the front region of e
i at t and it is denoted byfront(e_i, t); see Figure 5.Figure 5
Front region of an entitye
i at a time-point t.An entitye
j is in front of an entity e
i, at a time-point t
(
t
∈
T
p
,
t
∉
T
s
), where t
x
-
1
<
t
<
t
x, t
x
∈
T
s, x
≠
1, if e
j is in the front region of e
i, that is, if (
x
p
o
s
(
e
j
,
t
)
,
y
p
o
s
(
e
j
,
t
)
) is inside front(e_i, t); this is denoted e
_
j
∈
f
r
o
n
t
(
e
_
i
,
t
) and we say that e
i follows e
j
(
e
i is a follower of e
j
) at t. We consider an additional restriction to establish that one entity follows another: let β
∈
[
0
,
π
]; then entity e
i follows entity e
j at t if (i)  e
_
j
∈
f
r
o
n
t
(
e
_
i
,
t
) and (ii) ∥
d
(
e
i
,
t
)
-
d
(
e
j
,
t
)
∥
≤
β; see Figure 6. An entity e
i is said to follow an entity e
j during a time interval [
t
a
,
t
b
], where t
a and t
b are time-points in T
p, if and only if e
i follows e
j at t, for all t
∈
[
t
a
,
t
b
], t
∉
T
s.Figure 6
Entitye
i follows entity e
j at a time-point t.An entitye
i is said to be aleader of a formation during a time interval I
=
[
t
a
,
t
b
], where t
a and t
b are time-points in T
p, if (i) e
i does not follow any entity during I and (ii) e
i is at least followed by m entities at each time-point t
∈
I, t
∉
T
s. It is said that there is aleadership pattern if e
i is a leader of at least m entities for at least k unit-time-intervals.


### 2.2. V-Formations

Consider the formation in Figure7 where entities displayed a V-formation at a time-point t, and e
4 is the leader entity. Note that if we applied Andersson’s model [14] to this formation, we would observe that no entity contains e
4 in its front region. Therefore, this example shows that Andersson’s model [14] is inadequate to identify leadership patterns in these types of formations, unless we consider a wide front region for each entity, as shown in Figure 8. Thus, the entities on the extremes, e
1 and e
7, will require a wide front region to be able to contain the leader entity e
4; this is not a realistic assumption in V-formations since an entity’s visual field is not usually that wide [4].Figure 7
An example of a V-formation at a time-pointt.Figure 8
A V-formation: entitiese
1 and e
7 would require a wide front region in order to contain the entity leader e
4.In the following section, we extend Andersson’s model to identify leadership patterns in V-formations.


### 2.3. V-Formation Model

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t, card(
F
)
≥
3. F is a V-formation at t if the following hold.(i)
There exist nonempty subsetsA and B of F such that card
(
A
)
≥
2, card
(
B
)
≥
2, A
∪
B
=
F, and A
∩
B
=
{
e
k
}, where e
k is said to be the leader entity of the formation.
(ii)
Entities inA tend to form a straight line l
1 at t.
(iii)
Entities inB tend to form a straight line l
2 at t.
(iv)
Straight linesl
1 and l
2 meet at position (
x
p
o
s
(
e
k
,
t
), y
p
o
s
(
e
k
,
t
)
).
(v)
∠
a
p
t
>
0 (the smallest angle defined by straight lines l
1 and l
2 at t).Regarding conditions (ii) and (iii), to establish if a set of entities tend to form a straight line, we use Pearson’s correlation coefficient r [18]. Thus, given a set of points {
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
n
,
y
n
)
}, r indicates how much they adjust to a straight line (linearity degree). r
∈
(
-
1,1
); if |
r
|
≈
1, then points tend to form a straight line. r is calculated as shown in (1). A threshold μ
p may be specified by the user to indicate the linearity degree required for the lines of the formation; that is, |
r
|
≥
μ
p:
(1)
r
=
n
*
(
∑
i
=
1
n
x
i
*
y
i
)
-
∑
i
=
1
n
x
i
*
∑
i
=
1
n
y
i
[
n
*
∑
i
=
1
n
x
i
2
-
(
∑
i
=
1
n
x
i
)
2
]

*

[
n
*
∑
i
=
1
n
y
i
2
-
(
∑
i
=
1
n
y
i
)
2
]
.
To obtain the equation for each straight line (
y
=
m
x
+
b
) characteristic of the formation (l
1 and l
2) we may apply the equations that correspond to the straight line which most suits a set of points {
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
n
,
y
n
)
}; see (2). Table 1 presents the results for the formation in Figure 9:
(2)
m
=
n
*
(
∑
i
=
1
n
x
i
*
y
i
)
-
∑
i
=
1
n
x
i
*
∑
i
=
1
n
y
i
n
*
∑
i
=
1
n
x
i
2
-
(
∑
i
=
1
n
x
i
)
2
,
b
=
∑
i
=
1
n
y
i
-
m
*
∑
i
=
1
n
x
i
n
.
Regarding condition (v), ∠
a
p
t is calculated as follows: we get straight lines l
1 and l
2 from the formation and find the smallest angle between them as follows.a is the positive angle in [
0
,
2
π
) that is specified by the line segment that goes from p
k to p
i, where p
k is the position of e
k (leader entity) according to equation for l
1 and p
i is the position of e
i
∈
A, e
i
≠
e
k according to equation for l
1.
b is the positive angle in [
0,2
π
) that is specified by the line segment that goes from p
k to p
j, where p
k is the position of e
k (leader entity) according to equation for l
2 and p
j is the position of e
j
∈
B, e
j
≠
e
k, according to equation for l
2.Let w
=
|
a
-
b
|; then ∠
a
p
t
=
w if w
≤
π, and ∠
a
p
t
=
2
π
-
w, otherwise. For example, in the formation in Figure 9, a
=
0.7 rad (40.36°), b
=
5.14 rad (294.44°), and w
=
4.43 rad (254.08°); thus, ∠
a
p
t
=
1.84 rad (105.91°).Table 1
Applying our model to the formation in Figure9.
Characteristic line
Entities that make up the characteristic line
Characteristic line equation
Pearson’s coefficient
Entity coordinates: original and calculated using the characteristic line equation
l
1
A
=
{
e
1
,
e
2
,
e
3
,
e
4
}
y
=
2.1
+
0.85
x
0.99
e
1: (−4, −1) and (−4, −1.3)
e
2: (−2, −0) and (−2, 0.4)
e
3: (0, 2) and (0, 2.1)
e
4: (2, 4) and (2, 3.8)
l
2
B
=
{
e
4
,
e
5
,
e
6
,
e
7
}
y
=
8.7
-
2.2
x
0.97
e
4: (2, 4) and (2, 4.3)
e
5: (3, 2) and (3, 2.1)
e
6: (4, 1) and (4, 0.1)
e
7: (5, −3) and (5, −2.3)Figure 9
A formation of entities at a time-pointt.In an analogous way to leadership patterns, we say that there is a V-formation pattern if the set F of moving entities shows a V-formation for at least k unit-time-intervals.


### 2.4. Circular and Doughnut Formations

In this section, we present a formal model to identify circular formations. We also present doughnut formations, which are an extension of circular formations.


#### 2.4.1. Circular Formation Model

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t. Let C be theminimum circle that encloses the entities in F and let C
r be its radius and let (C
x
,
C
y) be its center (Welzl [19] and Megiddo [20] have showed that this circle can be found in linear time). F is a circular formation at t if(i)
C
r
≤
R (a user-given radius with center at (
C
x
,
C
y
)),
(ii)
the minimum number of members in the formation isN
min
⁡.In Figure 10, we show a circular formation with 9 members.Figure 10
A circular formation.


#### 2.4.2. Doughnut Formation Model

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t. Let C be the minimum circle that encloses the entities in F and let C
r be its radius and (
C
x
,
C
y
) its center. F is a doughnutformation at t if(i)
C
r
≤
R
ext (external radius, a user-given radius with center at (
C
x
,
C
y
)),
(ii)
for each entity of the formation its distanced regarding (
C
x
,
C
y
) is greater than R
int
⁡ (internal radius, a user-given radius with center at (
C
x
,
C
y
), R
int
⁡
≤
C
r),
(iii)
the minimum number of members in the formation isN
min
⁡.Note that a circular formation is a particular case of a doughnut formation, where R
int
⁡
=
0. In Figure 11, we show a doughnut formation with 8 members.Figure 11
A doughnut formation.Circular and doughnut patterns are also defined in an analogous way to a V-formation pattern.


## 2.1. Andersson’s Model

Next, we present the essential elements of Andersson’s model [14].Consider a setE of n entities {
e
1
,
e
2
,
…
,
e
n
} that move in a space, usually in a region during a time interval [
t
1
,
t
f
]. This space is represented by the Euclidian plane. Time is represented continuously. T
p denotes an infinite set of time-points: {
t
∣
t
∈
[
t
1
,
t
f
]
}. On the other hand, T
s denotes a finite set of discrete time-points {
t
1
,
t
2
,
…
,
t
f
}. Every t
i
∈
T
s represents a time-step and corresponds to a time-point in which the position of a moving entity (and perhaps other data) was recorded. A unit-time-interval is an open interval between two consecutive time-steps, that is, (
t
i
-
1
,
t
i
), for all t
i
∈
T
s, i
≠
1.The coordinates of an entity at a time-point are given by a pair of functionsx
p
o
s and y
p
o
s, both having the signature E
×
T
p
→ Real. Andersson assumes that between two consecutive time-steps an entity moves along a straight line with constant direction and constant velocity. This assumption has been adopted in other works (see [15–17] for a discussion). Therefore, in such a model in order to be practical enough, the recording frequency of the positions of moving objects should be adapted to the nature of each domain. For example, when detecting bird formations the elapsed time between two consecutive time-steps should not be longer than 30 seconds.Consider an entitye
i at a time-point t, where t
x
-
1
<
t
<
t
x, t
x
∈
T
s, x
≠
1; then the direction of e
i at t, denoted by d
(
e
i
,
t
), is the angle specified by the straight line segment that goes from (
x
p
o
s
(
e
i
,
t
x
-
1
), y
p
o
s
(
e
i
,
t
x
-
1
)
) to (
x
p
o
s
(
e
i
,
t
x
)
,
y
p
o
s
(
e
i
,
t
x
)
); see Figure 4. The angle d
(
e
i
,
t
) is between [
0
,
2
π
). Andersson declares the direction of an entity at a time-step t
x to beundefined, because at a time-step an entity might change its direction (for more details see [14]).Figure 4
d
(
e
i
,
t
): angle of entity e
i at a time-point t.The front region of an entitye
i is a region associated with e
i at a time-point t, where t
x
-
1
<
t
<
t
x, t
x
∈
T
s, x
≠
1, which represents the perception region of an entity, for example, a visual or an auditive range. The front region of e
i is defined as follows: consider three straight line segments s
0, s
1, and, s
2, each of length r. Each segment has an endpoint at (
x
p
o
s
(
e
i
,
t
)
,
y
p
o
s
(
e
i
,
t
)
). The direction of the segment s
0 is d
(
e
i
,
t
). Segments s
1 and s
2 form angles of α
/
2 and -
α
/
2
(
0
≤
α
<
2
π
) with regard to segment s
0, respectively. The circular sector (a wedge-shaped region) with a radius r
(
r
≥
0
), delimited by s
1 and s
2, makes up the front region of e
i at t and it is denoted byfront(e_i, t); see Figure 5.Figure 5
Front region of an entitye
i at a time-point t.An entitye
j is in front of an entity e
i, at a time-point t
(
t
∈
T
p
,
t
∉
T
s
), where t
x
-
1
<
t
<
t
x, t
x
∈
T
s, x
≠
1, if e
j is in the front region of e
i, that is, if (
x
p
o
s
(
e
j
,
t
)
,
y
p
o
s
(
e
j
,
t
)
) is inside front(e_i, t); this is denoted e
_
j
∈
f
r
o
n
t
(
e
_
i
,
t
) and we say that e
i follows e
j
(
e
i is a follower of e
j
) at t. We consider an additional restriction to establish that one entity follows another: let β
∈
[
0
,
π
]; then entity e
i follows entity e
j at t if (i)  e
_
j
∈
f
r
o
n
t
(
e
_
i
,
t
) and (ii) ∥
d
(
e
i
,
t
)
-
d
(
e
j
,
t
)
∥
≤
β; see Figure 6. An entity e
i is said to follow an entity e
j during a time interval [
t
a
,
t
b
], where t
a and t
b are time-points in T
p, if and only if e
i follows e
j at t, for all t
∈
[
t
a
,
t
b
], t
∉
T
s.Figure 6
Entitye
i follows entity e
j at a time-point t.An entitye
i is said to be aleader of a formation during a time interval I
=
[
t
a
,
t
b
], where t
a and t
b are time-points in T
p, if (i) e
i does not follow any entity during I and (ii) e
i is at least followed by m entities at each time-point t
∈
I, t
∉
T
s. It is said that there is aleadership pattern if e
i is a leader of at least m entities for at least k unit-time-intervals.


## 2.2. V-Formations

Consider the formation in Figure7 where entities displayed a V-formation at a time-point t, and e
4 is the leader entity. Note that if we applied Andersson’s model [14] to this formation, we would observe that no entity contains e
4 in its front region. Therefore, this example shows that Andersson’s model [14] is inadequate to identify leadership patterns in these types of formations, unless we consider a wide front region for each entity, as shown in Figure 8. Thus, the entities on the extremes, e
1 and e
7, will require a wide front region to be able to contain the leader entity e
4; this is not a realistic assumption in V-formations since an entity’s visual field is not usually that wide [4].Figure 7
An example of a V-formation at a time-pointt.Figure 8
A V-formation: entitiese
1 and e
7 would require a wide front region in order to contain the entity leader e
4.In the following section, we extend Andersson’s model to identify leadership patterns in V-formations.


## 2.3. V-Formation Model

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t, card(
F
)
≥
3. F is a V-formation at t if the following hold.(i)
There exist nonempty subsetsA and B of F such that card
(
A
)
≥
2, card
(
B
)
≥
2, A
∪
B
=
F, and A
∩
B
=
{
e
k
}, where e
k is said to be the leader entity of the formation.
(ii)
Entities inA tend to form a straight line l
1 at t.
(iii)
Entities inB tend to form a straight line l
2 at t.
(iv)
Straight linesl
1 and l
2 meet at position (
x
p
o
s
(
e
k
,
t
), y
p
o
s
(
e
k
,
t
)
).
(v)
∠
a
p
t
>
0 (the smallest angle defined by straight lines l
1 and l
2 at t).Regarding conditions (ii) and (iii), to establish if a set of entities tend to form a straight line, we use Pearson’s correlation coefficient r [18]. Thus, given a set of points {
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
n
,
y
n
)
}, r indicates how much they adjust to a straight line (linearity degree). r
∈
(
-
1,1
); if |
r
|
≈
1, then points tend to form a straight line. r is calculated as shown in (1). A threshold μ
p may be specified by the user to indicate the linearity degree required for the lines of the formation; that is, |
r
|
≥
μ
p:
(1)
r
=
n
*
(
∑
i
=
1
n
x
i
*
y
i
)
-
∑
i
=
1
n
x
i
*
∑
i
=
1
n
y
i
[
n
*
∑
i
=
1
n
x
i
2
-
(
∑
i
=
1
n
x
i
)
2
]

*

[
n
*
∑
i
=
1
n
y
i
2
-
(
∑
i
=
1
n
y
i
)
2
]
.
To obtain the equation for each straight line (
y
=
m
x
+
b
) characteristic of the formation (l
1 and l
2) we may apply the equations that correspond to the straight line which most suits a set of points {
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
n
,
y
n
)
}; see (2). Table 1 presents the results for the formation in Figure 9:
(2)
m
=
n
*
(
∑
i
=
1
n
x
i
*
y
i
)
-
∑
i
=
1
n
x
i
*
∑
i
=
1
n
y
i
n
*
∑
i
=
1
n
x
i
2
-
(
∑
i
=
1
n
x
i
)
2
,
b
=
∑
i
=
1
n
y
i
-
m
*
∑
i
=
1
n
x
i
n
.
Regarding condition (v), ∠
a
p
t is calculated as follows: we get straight lines l
1 and l
2 from the formation and find the smallest angle between them as follows.a is the positive angle in [
0
,
2
π
) that is specified by the line segment that goes from p
k to p
i, where p
k is the position of e
k (leader entity) according to equation for l
1 and p
i is the position of e
i
∈
A, e
i
≠
e
k according to equation for l
1.
b is the positive angle in [
0,2
π
) that is specified by the line segment that goes from p
k to p
j, where p
k is the position of e
k (leader entity) according to equation for l
2 and p
j is the position of e
j
∈
B, e
j
≠
e
k, according to equation for l
2.Let w
=
|
a
-
b
|; then ∠
a
p
t
=
w if w
≤
π, and ∠
a
p
t
=
2
π
-
w, otherwise. For example, in the formation in Figure 9, a
=
0.7 rad (40.36°), b
=
5.14 rad (294.44°), and w
=
4.43 rad (254.08°); thus, ∠
a
p
t
=
1.84 rad (105.91°).Table 1
Applying our model to the formation in Figure9.
Characteristic line
Entities that make up the characteristic line
Characteristic line equation
Pearson’s coefficient
Entity coordinates: original and calculated using the characteristic line equation
l
1
A
=
{
e
1
,
e
2
,
e
3
,
e
4
}
y
=
2.1
+
0.85
x
0.99
e
1: (−4, −1) and (−4, −1.3)
e
2: (−2, −0) and (−2, 0.4)
e
3: (0, 2) and (0, 2.1)
e
4: (2, 4) and (2, 3.8)
l
2
B
=
{
e
4
,
e
5
,
e
6
,
e
7
}
y
=
8.7
-
2.2
x
0.97
e
4: (2, 4) and (2, 4.3)
e
5: (3, 2) and (3, 2.1)
e
6: (4, 1) and (4, 0.1)
e
7: (5, −3) and (5, −2.3)Figure 9
A formation of entities at a time-pointt.In an analogous way to leadership patterns, we say that there is a V-formation pattern if the set F of moving entities shows a V-formation for at least k unit-time-intervals.


## 2.4. Circular and Doughnut Formations

In this section, we present a formal model to identify circular formations. We also present doughnut formations, which are an extension of circular formations.


### 2.4.1. Circular Formation Model

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t. Let C be theminimum circle that encloses the entities in F and let C
r be its radius and let (C
x
,
C
y) be its center (Welzl [19] and Megiddo [20] have showed that this circle can be found in linear time). F is a circular formation at t if(i)
C
r
≤
R (a user-given radius with center at (
C
x
,
C
y
)),
(ii)
the minimum number of members in the formation isN
min
⁡.In Figure 10, we show a circular formation with 9 members.Figure 10
A circular formation.


### 2.4.2. Doughnut Formation Model

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t. Let C be the minimum circle that encloses the entities in F and let C
r be its radius and (
C
x
,
C
y
) its center. F is a doughnutformation at t if(i)
C
r
≤
R
ext (external radius, a user-given radius with center at (
C
x
,
C
y
)),
(ii)
for each entity of the formation its distanced regarding (
C
x
,
C
y
) is greater than R
int
⁡ (internal radius, a user-given radius with center at (
C
x
,
C
y
), R
int
⁡
≤
C
r),
(iii)
the minimum number of members in the formation isN
min
⁡.Note that a circular formation is a particular case of a doughnut formation, where R
int
⁡
=
0. In Figure 11, we show a doughnut formation with 8 members.Figure 11
A doughnut formation.Circular and doughnut patterns are also defined in an analogous way to a V-formation pattern.


## 2.4.1. Circular Formation Model

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t. Let C be theminimum circle that encloses the entities in F and let C
r be its radius and let (C
x
,
C
y) be its center (Welzl [19] and Megiddo [20] have showed that this circle can be found in linear time). F is a circular formation at t if(i)
C
r
≤
R (a user-given radius with center at (
C
x
,
C
y
)),
(ii)
the minimum number of members in the formation isN
min
⁡.In Figure 10, we show a circular formation with 9 members.Figure 10
A circular formation.


## 2.4.2. Doughnut Formation Model

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t. Let C be the minimum circle that encloses the entities in F and let C
r be its radius and (
C
x
,
C
y
) its center. F is a doughnutformation at t if(i)
C
r
≤
R
ext (external radius, a user-given radius with center at (
C
x
,
C
y
)),
(ii)
for each entity of the formation its distanced regarding (
C
x
,
C
y
) is greater than R
int
⁡ (internal radius, a user-given radius with center at (
C
x
,
C
y
), R
int
⁡
≤
C
r),
(iii)
the minimum number of members in the formation isN
min
⁡.Note that a circular formation is a particular case of a doughnut formation, where R
int
⁡
=
0. In Figure 11, we show a doughnut formation with 8 members.Figure 11
A doughnut formation.Circular and doughnut patterns are also defined in an analogous way to a V-formation pattern.


## 3. Outliers

Informally, for V-formations an outlier is an entity which is away from its characteristic lines, and for circular formations it is an entity found beyond the radius of the formation(
R
).


### 3.1. Outliers in V-Formations

There are sets of entities which tend to display a V-formation; they may have at a time-pointt entities which are away from their characteristic lines and which, therefore, affect Pearson’s coefficient. These entities are called outliers [22, 23].There are numerous methods to detect outliers in different domains [24]. Listing 1 presents an algorithm that receives an array of m entities (lineMembers) which form a characteristic line of a formation at a time-point t. The algorithm determines if, after removing a maximum number of entities on the given array, the Pearson’s coefficient surpasses a given threshold μ
p. For example, if it is permitted to remove a maximum of two entities from a characteristic line of the formation, it is considered that the entities in Figure 12 display a V-formation having two outliers on each characteristic line. Then, the algorithm receives the minimum value of Pearson’s coefficient μ
p which should be met and a maximum percentage of entities (percentageOutliers) which are permitted to be removed from the array of entities. This percentage is calculated with regard to the total number of entities m.Listing 1:Outlier detection algorithm.
ALGORITHM: Outlier detection on a characteristic line
INPUT:  lineMembers = [
e
1
,
e
2
,
…
,
e
m
] //Array of m entities
μ
p //Threshold for Pearson’s coefficient
percentageOutliers //Maximum percentage of outliers permitted on lineMembers
OUTPUT:  outliers = [
] // Array of outliers
BEGIN
(1) Obtain the equation of the linel which most suits the positions (x
,
y) of the entities in lineMembers, see (2).
(2) Get the maximum number of outliers permitted onlineMembers: nbrOutliers = ⌈
m
*
p
e
r
c
e
n
t
a
g
e
O
u
t
l
i
e
r
s
/
100
⌉.
(3) Find thenbrOutliers entities in lineMembers which have the maximum distance to l.
(4) Remove fromlineMembers the entities found in Step  3.
(5) Calculate Pearson’s coefficient using positions (x
,
y) of each entity in lineMembers:
Pearson = PearsonCoefficient(lineMembers).
(6) IfPearson
≥
μ
p then return in outliers the entities found in Step  3.
ENDFigure 12
A V-formation with two outliers.Example 1.
Consider the set of entities in Figure13 which would form a straight line if entities e
2 and e
4 were not considered; that is, e
2 and e
3 are outliers.Figure 13
Characteristic line of a V-formation with two outliers.Input algorithm parameters:l
i
n
e
M
e
m
b
e
r
s
=
[
e
1
,
e
2
,
…
,
e
8
], μ
p
=
0.99 andpercentageOutliers = 20%.Step 1.
Equation ofl: y
=
-
0.754
x
+
2.01.Step 2.
nbrOutliers = ⌈
8
*
0.2
⌉
=
2.Step 3.
e
2 and e
4.Step 4.
lineMembers
=
[
e
1
,
e
3
,
e
5
,
e
6
,
e
7
,
e
8
].Step 5.
Pearson = PearsonCoefficient (lineMembers) = 1.Step 6.
1
≥
0.99; then returnoutliers = [e
2
,
e
4].The algorithm determines that entitiese
2 and e
4 are outliers. Then, we conclude that entities e
1
,
e
3
,
e
5
,
e
6
,
e
7, and e
8 tend to form a straight line with Pearson’s coefficient greater than 0.99.


### 3.2. Outliers in Circular Formations

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t. Consider an entity e
i
∈
F such that F
-
{
e
i
} is a circular formation and the distance from e
i to (C
x
,
C
y) (center of the minimum circle that encloses the entities in F
-
{
e
i
}) is greater than R at t. This entity may be considered as a member of the formation which is temporally away from it; that is, e
i is an outlier. To identify this type of entities, we introduce a parameter R
m
a
x
O
u
t
l
i
e
r, where R
m
a
x
O
u
t
l
i
e
r
>
R. An entity is considered an outlier at a time-point t if its distance d to (C
x, C
y) is greater than R and less than R
m
a
x
O
u
t
l
i
e
r; see Figure 14.Figure 14
A circular formation with two outliers.Since the distancing of the outlier entity from the formation is temporal, an analyst may introduce a second parameterT
m
a
x
T
i
m
e
S
e
p
a
r
a
t
i
o
n to control the maximum continuous time of permitted distancing. That is, if an entity separates from a circular formation at a time-point t, then, to be considered an outlier, it will have to reincorporate (d
≤
R) to the formation before t
+
T
m
a
x
T
i
m
e
S
e
p
a
r
a
t
i
o
n. This same aspect can also be considered for outliers in V-formations.An analyst can also specify a maximum permitted number of outliersmaxNumberOutliers in the formation. This value can be calculated from a percentage (percentageOutliers) with regard to the total number of entities in the formation.


### 3.3. Outliers in Doughnut Formations

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t. Consider an entity e
i
∈
F such that F
-
{
e
i
} is a doughnut formation. For doughnut formations we consider two types of outliers: external and internal. An entity e
i is considered an external outlier at t if its distance d to (C
x
,
C
y) (center of the minimum circle that encloses the entities in F
-
{
e
i
}) is greater than R
ext and less than R
m
a
x
O
u
t
l
i
e
r, where R
m
a
x
O
u
t
l
i
e
r
>
R
ext. On the other hand, e
i is considered an internal outlier at t if d is less than R
int
⁡; see Figure 15.Figure 15
Outliers in doughnut formations.Analogously to circular formations,T
m
a
x
T
i
m
e
S
e
p
a
r
a
t
i
o
n andmaxNumberOutliers values may be specified, not only for external outliers but also for internal outliers.


## 3.1. Outliers in V-Formations

There are sets of entities which tend to display a V-formation; they may have at a time-pointt entities which are away from their characteristic lines and which, therefore, affect Pearson’s coefficient. These entities are called outliers [22, 23].There are numerous methods to detect outliers in different domains [24]. Listing 1 presents an algorithm that receives an array of m entities (lineMembers) which form a characteristic line of a formation at a time-point t. The algorithm determines if, after removing a maximum number of entities on the given array, the Pearson’s coefficient surpasses a given threshold μ
p. For example, if it is permitted to remove a maximum of two entities from a characteristic line of the formation, it is considered that the entities in Figure 12 display a V-formation having two outliers on each characteristic line. Then, the algorithm receives the minimum value of Pearson’s coefficient μ
p which should be met and a maximum percentage of entities (percentageOutliers) which are permitted to be removed from the array of entities. This percentage is calculated with regard to the total number of entities m.Listing 1:Outlier detection algorithm.
ALGORITHM: Outlier detection on a characteristic line
INPUT:  lineMembers = [
e
1
,
e
2
,
…
,
e
m
] //Array of m entities
μ
p //Threshold for Pearson’s coefficient
percentageOutliers //Maximum percentage of outliers permitted on lineMembers
OUTPUT:  outliers = [
] // Array of outliers
BEGIN
(1) Obtain the equation of the linel which most suits the positions (x
,
y) of the entities in lineMembers, see (2).
(2) Get the maximum number of outliers permitted onlineMembers: nbrOutliers = ⌈
m
*
p
e
r
c
e
n
t
a
g
e
O
u
t
l
i
e
r
s
/
100
⌉.
(3) Find thenbrOutliers entities in lineMembers which have the maximum distance to l.
(4) Remove fromlineMembers the entities found in Step  3.
(5) Calculate Pearson’s coefficient using positions (x
,
y) of each entity in lineMembers:
Pearson = PearsonCoefficient(lineMembers).
(6) IfPearson
≥
μ
p then return in outliers the entities found in Step  3.
ENDFigure 12
A V-formation with two outliers.Example 1.
Consider the set of entities in Figure13 which would form a straight line if entities e
2 and e
4 were not considered; that is, e
2 and e
3 are outliers.Figure 13
Characteristic line of a V-formation with two outliers.Input algorithm parameters:l
i
n
e
M
e
m
b
e
r
s
=
[
e
1
,
e
2
,
…
,
e
8
], μ
p
=
0.99 andpercentageOutliers = 20%.Step 1.
Equation ofl: y
=
-
0.754
x
+
2.01.Step 2.
nbrOutliers = ⌈
8
*
0.2
⌉
=
2.Step 3.
e
2 and e
4.Step 4.
lineMembers
=
[
e
1
,
e
3
,
e
5
,
e
6
,
e
7
,
e
8
].Step 5.
Pearson = PearsonCoefficient (lineMembers) = 1.Step 6.
1
≥
0.99; then returnoutliers = [e
2
,
e
4].The algorithm determines that entitiese
2 and e
4 are outliers. Then, we conclude that entities e
1
,
e
3
,
e
5
,
e
6
,
e
7, and e
8 tend to form a straight line with Pearson’s coefficient greater than 0.99.


## 3.2. Outliers in Circular Formations

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t. Consider an entity e
i
∈
F such that F
-
{
e
i
} is a circular formation and the distance from e
i to (C
x
,
C
y) (center of the minimum circle that encloses the entities in F
-
{
e
i
}) is greater than R at t. This entity may be considered as a member of the formation which is temporally away from it; that is, e
i is an outlier. To identify this type of entities, we introduce a parameter R
m
a
x
O
u
t
l
i
e
r, where R
m
a
x
O
u
t
l
i
e
r
>
R. An entity is considered an outlier at a time-point t if its distance d to (C
x, C
y) is greater than R and less than R
m
a
x
O
u
t
l
i
e
r; see Figure 14.Figure 14
A circular formation with two outliers.Since the distancing of the outlier entity from the formation is temporal, an analyst may introduce a second parameterT
m
a
x
T
i
m
e
S
e
p
a
r
a
t
i
o
n to control the maximum continuous time of permitted distancing. That is, if an entity separates from a circular formation at a time-point t, then, to be considered an outlier, it will have to reincorporate (d
≤
R) to the formation before t
+
T
m
a
x
T
i
m
e
S
e
p
a
r
a
t
i
o
n. This same aspect can also be considered for outliers in V-formations.An analyst can also specify a maximum permitted number of outliersmaxNumberOutliers in the formation. This value can be calculated from a percentage (percentageOutliers) with regard to the total number of entities in the formation.


## 3.3. Outliers in Doughnut Formations

LetF
=
{
e
1
,
e
2
,
…
,
e
n
} be a set of moving entities at a time-point t. Consider an entity e
i
∈
F such that F
-
{
e
i
} is a doughnut formation. For doughnut formations we consider two types of outliers: external and internal. An entity e
i is considered an external outlier at t if its distance d to (C
x
,
C
y) (center of the minimum circle that encloses the entities in F
-
{
e
i
}) is greater than R
ext and less than R
m
a
x
O
u
t
l
i
e
r, where R
m
a
x
O
u
t
l
i
e
r
>
R
ext. On the other hand, e
i is considered an internal outlier at t if d is less than R
int
⁡; see Figure 15.Figure 15
Outliers in doughnut formations.Analogously to circular formations,T
m
a
x
T
i
m
e
S
e
p
a
r
a
t
i
o
n andmaxNumberOutliers values may be specified, not only for external outliers but also for internal outliers.


## 4. Experiments and Discussion

### 4.1. Experiment for V-Formations

For our experiment, we used Nathan’s model [6] implemented in NetLogo in order to generate V-formations. NetLogo is a programmable modeling environment for simulating natural and social phenomena that have been used in previous works [14, 25].We worked with a population of 15 entities. The dimensions of the Euclidian plane where the entities move werex
∈
[
-
35,35
] and y
∈
[
-
35
,
35
], where the unit of measure for distance in NetLogo is apatch. To generate V-formations, we used the parameters in Table 2. These parameters allow us to define aspects related to vision and movement of the entities in Nathan’s model.Table 2
Parameters to generate V-formations in NetLogo using Nathan’s model.
Number of entities
15
Vision parameters
Vision distance
9 patches
Vision cone
1.79 rad (103°)
Obstruction cone
0.75 rad (43°)
Movement parameters
Base speed
0.2
Speed change factor
0.15
Updraft distance
9 patches
Too close
3.1
Max. turn
0.14 rad (8°)For outlier detection, we considered for our model the following parameters:μ
p
=
0.90 andpercentageOutliers = 20%. Our experiment began from tick 40199 and ended at tick 40400, because in Nathan’s model the generation of V-formations requires a stabilization time (tick 40199 in our experiment, atick is the unit of measure for time in NetLogo). Time-steps were taken in intervals of 20 ticks, for if we consider a smaller step, a change in the position and direction of an entity would be practically imperceptible. Thus, the total number of steps was 10. Figure 16 shows the position of entities at ticks 40200, 40220, 40380, and 40400 and Table 3 summarizes our results.Table 3
V-formations: results of the experiment in NetLogo.
Tick
Formations identified by our model (leader bolded, outliers in brackets)
Pearson’s coefficient straight line 1
Pearson’s coefficient straight line 2
Opening angle
V-formation
Formations identified by Andersson’s model (leader bolded)
40200
{
1,2
,
3
,
5,13,14
}
{
1,2
,
3
}→0.99
{
3,5
,
13,14
}→0.99
1.5 rad (86.49°)
Yes
{
2
,
3
,
5
}
{
13
,
14
}
{
7
,
9
,
12
}
{
7,9
}→1
{
9,12
}→1
1.33 rad (75.92°)
Yes
{
7
,
9
,
12
}
{
0,4
,
6
,
8
}
{
0,4
,
6
}→0.98
{
6,8
}→1
0.52 rad (29.97°)
Yes
{
0
,
4
}
{
6
,
8
}
{
10,11
}
NA
{
10,11
}→1
NA
No
{
10
,
11
}
40220
{
1,2
,
3
,
5,13,14
}
{
1,2
,
3
}→0.99
{
3,5
,
13,14
}→0.99
1.51 rad (86.49°)
Yes
{
2
,
3
,
5
}
{
13
,
14
}
{
7
,
9
,
12
}
{
7,9
}→1
{
9,12
}→1
1.33 rad (75.92°)
Yes
{
7
,
9
,
12
}
{
0,4
,
6
,
8
}
{
0,4
,
6
}→0.98
{
6,8
}→1
0.52 rad (29.97°)
Yes
{
0
,
4
}
{
6
,
8
}
{
10,11
}
NA
{
10,11
}→1
NA
No
{
10
,
11
}
⋮
40380
{
2
,
[
3
]
,
13
,
1
,
5,14
}
{
2,13,1
}→1
{
1,5
,
14
}→0.95
0.79 rad (45.13°)
Yes
{
1
,
5
}
{
7
,
9
,
12
}
{
7,9
}→1
{
9,12
}→1
1.33 rad (75.92°)
Yes
{
7
,
9
,
12
}
{
0
,
4
,
8
}
{
0,4
}→1
{
4,8
}→1
2.68 rad (153.74°)
Yes
No
{
10,11
}
NA
{
10,11
}→1
NA
No
{
10
,
11
}
{
6
}
NA
NA
NA
NA
NA
40400
{
[
1
]
,
5
,
3
,
2,13
,
[
15
]
}
{
5,3
}→0.93
{
3,2
,
13
}→0.98
0.86 rad (49.5°)
Yes
{
2
,
3
}
{
1
,
5
}
{
7
,
9
,
12
}
{
7,9
}→1
{
9,12
}→1
1.33 rad (75.92°)
Yes
{
7
,
9
,
12
}
{
0,4
}
NA
{
0,4
}→1
NA
No
No
{
10,11
}
NA
{
10,11
}→1
NA
No
{
10
,
11
}
{
6,8
}
NA
{
6,8
}→1
NA
No
NoV-formations. Position of entities at ticks (a) 40200, (b) 40220, (c) 40380, and (d) 40400.
(a)
(b)
(c)
(d)


#### 4.1.1. Analysis of V-Formation Results

According to the results shown in Table3, our model classified several sets of entities as V-formations. These results agree with what was expected since Nathan’s model had already stabilized and V-formations were being generated effectively for those times. Moreover, it was necessary to apply the outlier detection algorithm just in two ticks (at ticks 40380 and 40400, see entities in brackets in Table 3, second column). On the other hand, we found that formations showed a high linearity degree since Pearson’s coefficients in all cases were greater than 0.92.We also applied Andersson’s model. We consideredm
=
2 and for the front region of each entity the parameters in Table 2; that is, s
0
=
9 patches (vision distance) and α
=
1.79 rad (103°) (vision cone). Andersson’s model only identified formations of two and three entities. This is reasonable as explained in Section 2.2 (see Figure 8). In addition, his model does not give information about the shape of the formation that it identifies; even if we considered a wider front region, his model would not indicate that a formation is, for example, V-shaped.


### 4.2. Experiments for Circular and Doughnut Formations

For experiments with circular and doughnut formations, we also worked in NetLogo and used Wilensky’s model [26] (a model inspired in Reynolds’ work [10]), which generates randomized formations of entities in NetLogo.We worked with a population of 102 entities. The dimensions of the Euclidian plane where the entities move werex
∈
[
-
35
,
35
] and y
∈
[
-
35
,
35
]. To generate formations, we used the parameters in Table 4.Table 4
Parameters to generate formations in NetLogo using Wilensky’s model.
Number of entities
102
Vision parameters
Vision distance
3 patches
Minimum Separation
1 patch
Movement parameters
Maximum angle of rotation
0.08 rad (4.75°)
Maximum following angle
0.04 rad (2.50°)
Maximum angle of separation
0.06 rad (3.5°)The model was executed on 1200 consecutive ticks (one run) and we conducted an analysis of circular formations and doughnut formations every 400 ticks. We considered that a set of entities showed a circular/doughnut pattern if the set showed a circular/doughnut formation during all the run (1200 ticks). A total of 100 runs were conducted. The parameters used to detect circular and doughnut formations are shown in Tables5 and 6. Table 7 summarizes our results for the 100 runs. Figure 17 shows the results for one of the runs.Table 5
Parameters for circular formation detection in NetLogo.
Minimum number of entities (N
min
⁡)
5
Maximum distance (R) from the center of the minimum enclosing circle to the entities
15 patches
Maximum percentage of outliers permitted (percentageOutliers)
30%
R
m
a
x
O
u
t
l
i
e
r
30 patches
T
m
a
x
T
i
m
e
S
e
p
a
r
a
t
i
o
n
400 ticksTable 6
Parameters for doughnut formation detection in NetLogo.
Minimum number of entities (N
min
⁡)
5
Maximum distance (R
ext) from the center of the minimum enclosing circle to the entities
30 patches
Maximum distance (R
int
⁡) from the center of the minimum enclosing circle to the entities
10 patches
Maximum percentage of outliers permitted
30%
R
m
a
x
O
u
t
l
i
e
r
50 patches
T
m
a
x
T
i
m
e
S
e
p
a
r
a
t
i
o
n
400 ticksTable 7
Circular and doughnut formations: results of the experiments in NetLogo.
Circular
Doughnut
Andersson’s model
Total number of patterns identified during the 100 runs
332
198
752
Average number of patterns identified in each run (1200 ticks)
3
2
8
Average number of entities in each pattern
13
22
4
Average number of outliers
2
Internal: 3External: 2
NACircular and doughnut formations. Position of entities at ticks (a) 0, (b) 400, (c) 800, and (d) 1200.
(a)
(b)
(c)
(d)


#### 4.2.1. Analysis of Experiments for Circular and Doughnut Formations

According to the results shown in Table7, the model classified several sets of entities as circular formations and around three remained throughout the 1200 ticks of a run. Regarding doughnut formations, the model detected around two formations that remained during the 1200 ticks of a run. These results agree with what was expected since Wilensky’s model had already stabilized in NetLogo.With respect to Andersson’s model, we consideredm
=
3 and the parameters in Table 2. His model identified 752 formations during the 100 runs, a value that is greater than the total number of circular and doughnutformations identified during the 100 runs. This is reasonable because with m
=
3 (note that the average number of entities in his formations was four) it is expected that any set of at least three entities that are close to each other (considering s
0
=
9 patches) will be identified as a formation. However, as our previous experiments with V-formations, his model is unable to indicate the shape of a formation that it identifies.


## 4.1. Experiment for V-Formations

For our experiment, we used Nathan’s model [6] implemented in NetLogo in order to generate V-formations. NetLogo is a programmable modeling environment for simulating natural and social phenomena that have been used in previous works [14, 25].We worked with a population of 15 entities. The dimensions of the Euclidian plane where the entities move werex
∈
[
-
35,35
] and y
∈
[
-
35
,
35
], where the unit of measure for distance in NetLogo is apatch. To generate V-formations, we used the parameters in Table 2. These parameters allow us to define aspects related to vision and movement of the entities in Nathan’s model.Table 2
Parameters to generate V-formations in NetLogo using Nathan’s model.
Number of entities
15
Vision parameters
Vision distance
9 patches
Vision cone
1.79 rad (103°)
Obstruction cone
0.75 rad (43°)
Movement parameters
Base speed
0.2
Speed change factor
0.15
Updraft distance
9 patches
Too close
3.1
Max. turn
0.14 rad (8°)For outlier detection, we considered for our model the following parameters:μ
p
=
0.90 andpercentageOutliers = 20%. Our experiment began from tick 40199 and ended at tick 40400, because in Nathan’s model the generation of V-formations requires a stabilization time (tick 40199 in our experiment, atick is the unit of measure for time in NetLogo). Time-steps were taken in intervals of 20 ticks, for if we consider a smaller step, a change in the position and direction of an entity would be practically imperceptible. Thus, the total number of steps was 10. Figure 16 shows the position of entities at ticks 40200, 40220, 40380, and 40400 and Table 3 summarizes our results.Table 3
V-formations: results of the experiment in NetLogo.
Tick
Formations identified by our model (leader bolded, outliers in brackets)
Pearson’s coefficient straight line 1
Pearson’s coefficient straight line 2
Opening angle
V-formation
Formations identified by Andersson’s model (leader bolded)
40200
{
1,2
,
3
,
5,13,14
}
{
1,2
,
3
}→0.99
{
3,5
,
13,14
}→0.99
1.5 rad (86.49°)
Yes
{
2
,
3
,
5
}
{
13
,
14
}
{
7
,
9
,
12
}
{
7,9
}→1
{
9,12
}→1
1.33 rad (75.92°)
Yes
{
7
,
9
,
12
}
{
0,4
,
6
,
8
}
{
0,4
,
6
}→0.98
{
6,8
}→1
0.52 rad (29.97°)
Yes
{
0
,
4
}
{
6
,
8
}
{
10,11
}
NA
{
10,11
}→1
NA
No
{
10
,
11
}
40220
{
1,2
,
3
,
5,13,14
}
{
1,2
,
3
}→0.99
{
3,5
,
13,14
}→0.99
1.51 rad (86.49°)
Yes
{
2
,
3
,
5
}
{
13
,
14
}
{
7
,
9
,
12
}
{
7,9
}→1
{
9,12
}→1
1.33 rad (75.92°)
Yes
{
7
,
9
,
12
}
{
0,4
,
6
,
8
}
{
0,4
,
6
}→0.98
{
6,8
}→1
0.52 rad (29.97°)
Yes
{
0
,
4
}
{
6
,
8
}
{
10,11
}
NA
{
10,11
}→1
NA
No
{
10
,
11
}
⋮
40380
{
2
,
[
3
]
,
13
,
1
,
5,14
}
{
2,13,1
}→1
{
1,5
,
14
}→0.95
0.79 rad (45.13°)
Yes
{
1
,
5
}
{
7
,
9
,
12
}
{
7,9
}→1
{
9,12
}→1
1.33 rad (75.92°)
Yes
{
7
,
9
,
12
}
{
0
,
4
,
8
}
{
0,4
}→1
{
4,8
}→1
2.68 rad (153.74°)
Yes
No
{
10,11
}
NA
{
10,11
}→1
NA
No
{
10
,
11
}
{
6
}
NA
NA
NA
NA
NA
40400
{
[
1
]
,
5
,
3
,
2,13
,
[
15
]
}
{
5,3
}→0.93
{
3,2
,
13
}→0.98
0.86 rad (49.5°)
Yes
{
2
,
3
}
{
1
,
5
}
{
7
,
9
,
12
}
{
7,9
}→1
{
9,12
}→1
1.33 rad (75.92°)
Yes
{
7
,
9
,
12
}
{
0,4
}
NA
{
0,4
}→1
NA
No
No
{
10,11
}
NA
{
10,11
}→1
NA
No
{
10
,
11
}
{
6,8
}
NA
{
6,8
}→1
NA
No
NoV-formations. Position of entities at ticks (a) 40200, (b) 40220, (c) 40380, and (d) 40400.
(a)
(b)
(c)
(d)


### 4.1.1. Analysis of V-Formation Results

According to the results shown in Table3, our model classified several sets of entities as V-formations. These results agree with what was expected since Nathan’s model had already stabilized and V-formations were being generated effectively for those times. Moreover, it was necessary to apply the outlier detection algorithm just in two ticks (at ticks 40380 and 40400, see entities in brackets in Table 3, second column). On the other hand, we found that formations showed a high linearity degree since Pearson’s coefficients in all cases were greater than 0.92.We also applied Andersson’s model. We consideredm
=
2 and for the front region of each entity the parameters in Table 2; that is, s
0
=
9 patches (vision distance) and α
=
1.79 rad (103°) (vision cone). Andersson’s model only identified formations of two and three entities. This is reasonable as explained in Section 2.2 (see Figure 8). In addition, his model does not give information about the shape of the formation that it identifies; even if we considered a wider front region, his model would not indicate that a formation is, for example, V-shaped.


## 4.1.1. Analysis of V-Formation Results

According to the results shown in Table3, our model classified several sets of entities as V-formations. These results agree with what was expected since Nathan’s model had already stabilized and V-formations were being generated effectively for those times. Moreover, it was necessary to apply the outlier detection algorithm just in two ticks (at ticks 40380 and 40400, see entities in brackets in Table 3, second column). On the other hand, we found that formations showed a high linearity degree since Pearson’s coefficients in all cases were greater than 0.92.We also applied Andersson’s model. We consideredm
=
2 and for the front region of each entity the parameters in Table 2; that is, s
0
=
9 patches (vision distance) and α
=
1.79 rad (103°) (vision cone). Andersson’s model only identified formations of two and three entities. This is reasonable as explained in Section 2.2 (see Figure 8). In addition, his model does not give information about the shape of the formation that it identifies; even if we considered a wider front region, his model would not indicate that a formation is, for example, V-shaped.


## 4.2. Experiments for Circular and Doughnut Formations

For experiments with circular and doughnut formations, we also worked in NetLogo and used Wilensky’s model [26] (a model inspired in Reynolds’ work [10]), which generates randomized formations of entities in NetLogo.We worked with a population of 102 entities. The dimensions of the Euclidian plane where the entities move werex
∈
[
-
35
,
35
] and y
∈
[
-
35
,
35
]. To generate formations, we used the parameters in Table 4.Table 4
Parameters to generate formations in NetLogo using Wilensky’s model.
Number of entities
102
Vision parameters
Vision distance
3 patches
Minimum Separation
1 patch
Movement parameters
Maximum angle of rotation
0.08 rad (4.75°)
Maximum following angle
0.04 rad (2.50°)
Maximum angle of separation
0.06 rad (3.5°)The model was executed on 1200 consecutive ticks (one run) and we conducted an analysis of circular formations and doughnut formations every 400 ticks. We considered that a set of entities showed a circular/doughnut pattern if the set showed a circular/doughnut formation during all the run (1200 ticks). A total of 100 runs were conducted. The parameters used to detect circular and doughnut formations are shown in Tables5 and 6. Table 7 summarizes our results for the 100 runs. Figure 17 shows the results for one of the runs.Table 5
Parameters for circular formation detection in NetLogo.
Minimum number of entities (N
min
⁡)
5
Maximum distance (R) from the center of the minimum enclosing circle to the entities
15 patches
Maximum percentage of outliers permitted (percentageOutliers)
30%
R
m
a
x
O
u
t
l
i
e
r
30 patches
T
m
a
x
T
i
m
e
S
e
p
a
r
a
t
i
o
n
400 ticksTable 6
Parameters for doughnut formation detection in NetLogo.
Minimum number of entities (N
min
⁡)
5
Maximum distance (R
ext) from the center of the minimum enclosing circle to the entities
30 patches
Maximum distance (R
int
⁡) from the center of the minimum enclosing circle to the entities
10 patches
Maximum percentage of outliers permitted
30%
R
m
a
x
O
u
t
l
i
e
r
50 patches
T
m
a
x
T
i
m
e
S
e
p
a
r
a
t
i
o
n
400 ticksTable 7
Circular and doughnut formations: results of the experiments in NetLogo.
Circular
Doughnut
Andersson’s model
Total number of patterns identified during the 100 runs
332
198
752
Average number of patterns identified in each run (1200 ticks)
3
2
8
Average number of entities in each pattern
13
22
4
Average number of outliers
2
Internal: 3External: 2
NACircular and doughnut formations. Position of entities at ticks (a) 0, (b) 400, (c) 800, and (d) 1200.
(a)
(b)
(c)
(d)


### 4.2.1. Analysis of Experiments for Circular and Doughnut Formations

According to the results shown in Table7, the model classified several sets of entities as circular formations and around three remained throughout the 1200 ticks of a run. Regarding doughnut formations, the model detected around two formations that remained during the 1200 ticks of a run. These results agree with what was expected since Wilensky’s model had already stabilized in NetLogo.With respect to Andersson’s model, we consideredm
=
3 and the parameters in Table 2. His model identified 752 formations during the 100 runs, a value that is greater than the total number of circular and doughnutformations identified during the 100 runs. This is reasonable because with m
=
3 (note that the average number of entities in his formations was four) it is expected that any set of at least three entities that are close to each other (considering s
0
=
9 patches) will be identified as a formation. However, as our previous experiments with V-formations, his model is unable to indicate the shape of a formation that it identifies.


## 4.2.1. Analysis of Experiments for Circular and Doughnut Formations

According to the results shown in Table7, the model classified several sets of entities as circular formations and around three remained throughout the 1200 ticks of a run. Regarding doughnut formations, the model detected around two formations that remained during the 1200 ticks of a run. These results agree with what was expected since Wilensky’s model had already stabilized in NetLogo.With respect to Andersson’s model, we consideredm
=
3 and the parameters in Table 2. His model identified 752 formations during the 100 runs, a value that is greater than the total number of circular and doughnutformations identified during the 100 runs. This is reasonable because with m
=
3 (note that the average number of entities in his formations was four) it is expected that any set of at least three entities that are close to each other (considering s
0
=
9 patches) will be identified as a formation. However, as our previous experiments with V-formations, his model is unable to indicate the shape of a formation that it identifies.


## 5. Conclusions and Future Work

In this paper, we propose two models:(I)
a model to identify V-formations with outliers. The model considers the location of entities to determine if they form this type of formation during a time interval;
(II)
a model to identify circular formations with outliers. The model considers the location of entities to determine if they form this type of formation during a time interval. In addition, we proposed an extension to identify doughnut formations with outliers.The rules for model (I) are flexible since they allow V-formations which are not necessarily perfectly aligned, in accordance with the real world. Furthermore, we consider outliers in V-, circular, and doughnut formations, that is, members of the formation that could be temporarily away from it. Our experimental results in NetLogo showed that our models identified these types of formations in such simulation environment where they were generated. We also showed that when we applied Andersson’s model, his model did not give information about the shape of the formation that it identified; that is, his model suffers from lack of semantic information about shape formations.Regarding future work, we plan to conduct a series of experiments in the stock market where V-formations usually appear [13]. Moreover, we plan to extend our models to identifyisolated entities, that is, entities that even if they are considered members of a formation, they follow their own path and do not influence the path of other entities [27]. We also plan to propose models to identify patterns such asconvergence, that is, a set of entities that converge or approach a place;divergence, that is, a set of entities that disperse or move away from a place [28], andself-organization, that is, a set of entities that move as a formation without there being a leader or an entity guiding the rest [29] or that this leader is unknown to the members [30–32].



---

*Source: 241684-2014-04-10.xml*