1

Dispersion and Line Formation in Artificial Swarm
Intelligence
DONGHWA JEONG and KIJU LEE, Case Western Reserve University

1.

INTRODUCTION

One of the major motifs in collective or swarm intelligence is that, even though individuals follow
simple rules, the resulting global behavior can be complex and intelligent. In artificial swarm systems,
such as swarm robots, the goal is to use systems that are as simple and cheap as possible, deploy
many of them, and coordinate them to conduct complex tasks that each individual cannot accomplish
[Cao 1995; Simmons 2000; Sahin 2005]. The system may involve a group of artificially intelligent
agents with limited sensing, communication, and computing capabilities and can achieve a higher
level task by the agents locally or globally collaborating with each other. Local collaboration can be
established among the neighbors within a certain communication range or physical/social distance.
Global collaboration can be realized by centralized control possibly with a designated leader.
Global shape formation is one of the challenging problems in artificial swarm intelligence. In nature,
it is performed for various purposes, such as engergy saving and path optimization. For instance, a
flock of large birds fly together while forming a V shape in order to reduce the air resistance and
fatigue for physically weak birds [Weimerskirch 2001]. Ants form a line to optimize the path to a food
source by laying a trail of pheromone and regulate foraging activities without any central control or
spatial information [Prabhakar 2012; Gordon 2013]. This trail enables the ant colony find the shortest
path to the food source [Bonabeau 2000]. Shape formation in artificial intelligence systems is usually
required for specific task-oriented performance, including 1) forming sensing grids [Spears 2004], 2)
exploring and mapping in space, underwater, or hazardous environments [Nawaz 2010; Wang 2011],
and 3) forming a barricade for surveillance or protecting an area/person [Cheng 2005]. This paper
presents a dynamic model of an artificial swarm system based on a virtual spring damper model and
algorithms for dispersion without a leader and line formation with an interim leader using only the
distance estimation among the neighbors.
2.

DYNAMIC MODEL OF COLLECTIVE SYSTEMS

Our dynamic model of swarm systems involving multiple agents is based on a virtual spring damper
model. To realize attractive and repulsive forces in a stable manner, virtual damper is added to the
spring system to depress the oscillatory motion of the agents. Modeling dynamic multi-agent systems
frequently requires global optimization by designing objective functions. As the number of agents increases, the computational cost for optimization increases exponentially. To address this problem, we
used geometric conditions that guarantee global shape formation from geometric primitives based on
the attractive and repulsive forces between the agents as shown in Fig. 1. Each node and edge represent an agent and a communication/sensing/social connection respectively where the spring constant
and damping ratio may be differently defined depending on each application. The mass of each node
may indicate the weight or relative importance of that agent within the group.
Let A1 , A2 , · · · , An be the agents in two-dimensional space. For the ith agent, the two-dimensional
th
th
Cartesian coordinate is denoted by ~xi = [xi , yi ]T . Likewise,
p the vector from the i agent to the j
T
2
2
agent is given by ~xij = [xi − xj , yi − yj ] where ||~xij || = (xi − xj ) + (yi − yj ) Assuming that the
Collective Intelligence 2014.

1:2

•

D. Jeong and K. Lee

Fig. 1. Attractive and repulsive forces between the nodes are modeled with a spring and a damper.

ith agent has a mass, mi . Then it follows the Newton’s second law: f~im = mi ~x¨i where f~im is the force
at the ith node and ~xi is its position. The force exerted by the spring and damper is described by
f~ik = −kij d~ij and f~ib = −bij ~x˙ ij where kij is the spring constant, bij is the damping coefficient between
agent i and neighboring agent j, and d~ij is a displacement vector between the two. In this model, each
agent knows the distances to its neighbors only. However, d~ij is expressed as a vector since the sum
of multiple interactions to an agent will force the agent to a certain direction in the global coordinate
system. The net force acting on the ith agent in the global coordinate can be derived as
X
f~im = f~ik + f~ib = −
(kij d~ij + bij ~x˙ ij )
j∈Mi
th
where M
Pi is the ~number˙ of neighboring agents of the i agent. The acceleration is calculated as
¨
~xi = − j∈Mi (kij dij + bij ~xij )/mi . In practical control with a microprocessor, the above equation can
be rewritten in discrete time representation given by
X
~x˙ i [t + 1] − ~x˙ i [t] = −
(kij d~ij + bij ~x˙ ij [t])/mi .
j∈Mi

In case of mi = 1 for all i = 1, · · · , n, the anticipated velocity and position at t + 1 and t + 2 are given by
X
X
~x˙ i [t + 1] = ~x˙ [t] −
(kij d~ij + bij ~x˙ ij [t]); ~xi [t + 2] = 2~xi [t + 1] − ~xi [t] −
(kij d~ij + bij ~x˙ ij [t]).
j∈Mi

3.

j∈Mi

DISPERSION AND LINE FORMATION

Algorithms
Two algorithms are introduced here: 1) dispersion based on trigonal plannar elements without a leader
and 2) line formation using paired line elements using an interim leader.

Fig. 2. Elementary geometric shapes: (a) trigonal planar and (b) paired line.

Collective Intelligence 2014.

Dispersion and Line Formation in Artificial Swarm Intelligence

•

1:3

Dispersion using trigonal planar elements. Let N be a set of dynamic agents. For every O ∈ N , label
the closest three neighbor agents as A, B, and C. By using the proposed attractive and repulsive forces,
let LOA = LOB = LOC = Ld where Ld is the desired distance between the agents.
Lining using paired line elements. Let N be a set of dynamic agents. For every O ∈ N , label the
closest agent as A. Let LOA =  and form a pair, (O, A). Find the nearest pair and label as (B, C). Let
LOB = LOC = LAB = LAC . Note that LOB = LOC for LOA = LBC =  as  → 0. When all rectangulars
are connected each other, two ends are designated as interim leaders of the connected chains in order
to stretch the line to opposite directions.
Simulation Results
MATLAB simulation is performed with 50 agents randomly spread in two-dimensional space. The
simple trigonal elements guarantee dispersion of the agents and paired line elements guarantees line
shape while maintaining connectivity as shown in Fig. 3 and 4. If each agent has a limited sensing/communication range, the system may result in multiple disc formation or outliers. Fig. 5 shows
the simulation results for two different communication ranges.

Fig. 3. Dispersion based on trigonal planar elements

Fig. 4. Line formation using paired line elements

Fig. 5. Separated discs and connected disc with different sensing range: (a) 40 inch, (b) 60 inch with 100 agents

Collective Intelligence 2014.

1:4

•

D. Jeong and K. Lee

REFERENCES
Y U. Cao, A S. Fukunaga, A B. Kahng, and, F. Meng. 1995. Cooperative mobile robotics: antecedents and directions. IEEE/RSJ
International Conference on Intelligent Robots and Systems 1, 226–234.
R. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, S. Thrun, and, H. Younes. 2000. Coordination for Multi-Robot
Exploration and Mapping. AAAI/IAAI .
E. Sahin. 2005. Swarm Robotics: From Sources of Inspiration to Domains of Application. Swarm Robotics, Lecture Notes in
Computer Science ,3342, 10–20.
H. Weimerskirch, J. Martin, Y. Clerquin, P. Alexandre, and, S. Jiraskova. 2001. Energy saving in flight formation. Nature ,413,
697–698.
S. Shen, N. Michael, Y. Mulgaonkar, and, V. Kumar. 2013. Vision-based State Estimation for Autonomous Rotorcraft MAVs in
Complex Environments. IEEE International conference on Robotics and Automation .
R. W. Beard, J. Lawton, and, F. Y Hadaegh. 2001. A coordination architecture for spacecraft formation control. IEEE Transactions on control Systems Technology ,9, 777–790.
E. Bonabeau, and, G. Theraulaz. 2000. Swarm Smarts. Scientific American ,282(3).
B. Prabhakar, N. Dektar. Katherine, and, D. Y. Gordon. 2012. The Regulation of Ant Colony Foraging Activity without Spatial
Information. PLoS Comput Biol ,8(8).
D. Y. Gordon. 2013. The rewards of restraint in the collective regulation of foraging by harvester ant colonies. Nature ,498.91–93
X. Li, and, X. Liang. 2011. A 3D Local Interaction Strategy for Swarm Robot. Journal of computers ,6(10).2237–2242.
C. M Breder. 1954. Equations descriptive of fish schools and other animal aggregations. Ecology ,35.361–370.
S. Sakai. 1973. A model for group structure and its behavior. Biophysics Japan ,13. 82–90.
H. S Niwa. 1994. Self-organizing dynamic model of fish schooling. J. Theor. Biol. ,171.123–136.
J. A Beecham, and, K. D Farnsworth. 1999. Animal group forces resulting from predator avoidance and competition minimization. J. Theor. Biol. ,198.533–548.
K. Warburton, and, J. Lazarus. 1991. Tendency-distance models of social cohesion in animal groups. J. Theor. Biol. ,150.473–488.
W. M Spears, D. F Spears, J. C Hamann, and, R. Heil. 2004. Distributed, Physics-Based Control of Swarms of Vehicles.
Autonomous Robots ,17.137–162.
S. Nawaz, M. Hussain, S. Watson, N. Trigoni, and, P. N Green. 2010. An Underwater Robotic Network for Monitoring Nuclear
Waste Storage Pools. Sensor Systems and Software ,24.236–255.
Y. Wang, A. Liang, and, H. Guan. 2011. Frontier-based multi-robot map exploration using Particle Swarm Optimization. Swarm
Intelligence , 1–6.
J. Cheng, W. Cheng, and, R. Nagpal. 2005. Robust and self-repairing formation control for swarms of mobile agents. AAAI ,
59–64.

Collective Intelligence 2014.

