JAIST Repository
https://dspace.jaist.ac.jp/

Title

Adaptive Navigation Control for Swarms ofAutonomous Mobile Robots

Author(s)Nishimura, Yasuhiro; Lee, Geunho; Chong, Nak
Young; Ji, Sang Hoon; Cho, Young‑Jo

Citation

Advances in Robot Navigation: 101‑118

Issue Date

2011‑07

Type

Book

Text version

publisher

URL

http://hdl.handle.net/10119/10288

RightsYasuhiro Nishimura, Geunho Lee, Nak Young Chong,Sang Hoon Ji and Young‑Jo Cho (2011). Adaptive
Navigation Control for Swarms of Autonomous
Mobile Robots, Advances in Robot Navigation,
Alejandra Barrera (Ed.), ISBN: 978‑953‑307‑346‑0,
InTech, Available from:http://www.intechopen.com/articles/show/title/ada
ptive‑navigation‑control‑for‑swarms‑of‑autonomous‑mobile‑robots

Description

Japan Advanced Institute of Science and Technology

5Adaptive Navigation Control for Swarms ofAutonomous Mobile Robots
Yasuhiro Nishimura1, Geunho Lee1, Nak Young Chong1, Sang Hoon Ji2 andYoung-Jo Cho3
1Japan Advanced Institute of Science and Technology,
2Korea Institute of Industrial Technology,

3Electronics and Telecommunications Research Institute1Japan2,3Korea

1. Introduction
Deploying a large number of resource-constrained mobile robots performing a common
group task may offer many advantages in efficiency, costs per system, and fault-tolerance(Sahin, 2005). Therefore, robot swarms are expected to perform missions in a wide variety of
applications such as environment and habitat monitoring, exploration, odor localization,
medical service, and search-and-rescue. In order to perform the above-mentioned tasks
successfully, one of the most important concerns is how to enable swarms of simple robots
to autonomously navigate toward a specified destination in the presence of obstacles anddead-end passageways as seen in Fig. 1. From the standpoint of the decentralized
coordination, the motions of individual robots need to be controlled to support coordinatedcollective behavior.
We address the coordinated navigation of a swarm of mobile robots through a clutteredenvironment without hitting obstacles and being trapped in dead-end passageways. Our
study is motivated by the observation that schools of fish exhibit emergent group behavior.
For instance, when schools of fish are faced with obstacles, they can split themselves into aplurality of smaller groups to avoid collision and then merge into a single group after
passing around the obstacles (Wilson, 1976). It is also worth noting that a group of fishfacing a dead end can get out of the area.
Based on the observation of schooling behavior in fish, this work aims to present a novel
adaptive group behavior, enabling large-scale robot swarms with limited sensing
capabilities to navigate toward a goal that is visible only to a limited number of robots. In
particular, the coordinated navigation is achieved without using any leader, identifiers,
common coordinate system, and explicit communication. Under such a minimal robot
model, the adaptive navigation scheme exploits the geometric local interaction which allows
three neighboring robots to form an equilateral triangle. Specifically, the proposed
algorithm allows robot swarms to 1) navigate while maintaining equilateral triangularlattices, 2) split themselves into multiple groups while maintaining a uniform distance ofeach other, 3) merge into a single group while maintaining a uniform distance of each other,

102

Advances in Robot Navigationand 4) escape from any dead-end passageways. During the adaptive navigation process, allrobots execute the same algorithm and act independently and asynchronously of each other.
Given any arbitrary initial positions, a large-scale swarm of robots is required to navigate
toward a goal position in an environment while locally interacting with other robots. The
basic necessities for the proposed solution are argued as follows. First, the robots can selfcontrol their travel direction according to environmental conditions, leading to enhancing
autonomy of their behavior. Secondly, by being split into multiple groups or re-united into asingle swarm, the robots can self-adjust its size and shape depending on the conditions. By
the capabilities above, robots have the emergent capability to maximize adaptability tooperate in uncertain environments. Thirdly, the coordinated navigation of multiple robots inan equilateral triangle formation reduces a potential traffic jam and stragglers.

(a) adaptive navigation problem(b) escape function
Fig. 1. Concept of adaptive navigation by autonomous mobile robot swarms
Consequently, the proposed adaptive navigation provides a cost-effective way to allow for
an increase in efficiency and autonomy of group navigation in a highly clutteredenvironment. What is important from a practical standpoint is that the swarm flocking is
considered as a good ad hoc networking model whose connectivity must be maintained
while moving. In particular, maintaining the uniform distance enables the model tooptimize efficient energy consumption in routing protocols (Fowler, 2001)(Lyengar et al.,2005). This networking model can potentially be used in application examples such as
exploration and search-and-rescue. This navigation can be further applied to swarms of
unmanned vehicles and sensors performing autonomous operations such as capturing andtransporting toxic and hazardous substances. We describe our algorithm in detail, andperform extensive simulations to demonstrate that a swarm of robots can navigate toward a
specified destination while adapting to unknown environmental conditions in a scalable
manner.
The rest of this paper is organized as follows. Section 2 introduces a brief description ofresearch related to swarming and flocking and sheds light on our motivation. Section 3
presents the robot model and the formal definitions of the adaptive navigation problem.
Section 4 describes the fundamental motion control of each robot locally interacting with

Adaptive Navigation Control for Swarms of Autonomous Mobile Robots

103

their neighboring robots, leading to forming an equilateral triangle lattice. Section 5 gives
the solution scheme of the adaptive navigation. Section 6 demonstrates the validity andapplicability of the proposed scheme through extensive simulations. Section 7 draws
conclusions.

2. Background
Wireless network-enabled mobile robotic sensors have been increasingly popular over the
recent years (Yicka et al., 2008). Such robotic sensors dispersing themselves into an area canbe used for search-and-rescue and exploration applications by filling the area of interest
and/or establishing an ad hoc network. To achieve a desired level of self-deployment ofrobotic sensors, many prior studies have attempted to use decentralized approaches in selfconfiguration (Lee & Chong, 2009)(Shucker et al., 2008)(Spears et al., 2004), patterngeneration (Lee & Chong, 2009-b)(Ikemoto et al., 2005), and navigation (Gu & Hu, 2010)(Lee& Chong, 2008)(Olfati-Saber, 2006). In particular, we have witnessed a great interest in
distributed navigation control that enables a large number of robots to navigate from an
initial position toward a desired destination without human intervention.
Recently, many navigation control studies have been reported in the field of swarm robotics,
where the decentralized navigation controls are mainly based on interactions between
individual robots mostly inspired by evidence from biological systems (e.g., fish schools or
bird flocks) or natural phenomena (e.g., liquid diffusion). The navigation control can befurther divided into biological emergence (Folino & Spezzano, 2002)(Reynolds, 1987),
behavior-based (Lee & Chong, 2008)(Ogren & Leonard, 2005)(Balch & Hybinette, 2000), andvirtual physics-based (Esposito & Dunbar, 2006)(Zarzhitsky et al., 2005)(Spears et al., 2006)
approaches. Specifically, the behavior-based and virtual physics-based approaches are
related to the use of such physical phenomena as gravitational forces (Zarzhitsky et al.,2005)(Spears et al., 2006) and potential fields (Esposito & Dunbar, 2006). Those works mostly
use some sort of force balance between inter-individual interactions exerting an attractive or
repulsive force on each other. This is mainly because the force-based interaction rules are
considered simple yet effective, and provide an intuitive understanding on individual
behavior. However, the computation of relative velocities or accelerations between robots isneeded to obtain the magnitude of the interacting force.
Regarding the aspect of calculating the movement position of each robot, accuracy andcomputational efficiency issues have been attracted. In practice, many works on robot
swarms use sensor-rich information and explicit means of communication. Note that if
any means of communication would be employed, robots need to identify with each otheror use a global coordinate or positioning system (Correll et al., 2000)(Lam & Liu,
2006)(Nembrini et al., 2002). In this paper, we attempt to achieve adaptive navigation
without taking advantage of rich computational capabilities and communication. This willallow us to develop robot systems in simple, robust, and non-costly ways. A subset of thiswork was reported in (Lee & Chong, 2008) which provided mobile robot swarms withbasic navigation and adaptation capabilities. The main objective of this paper is to present
a completely new and general adaptive navigation coordination scheme assuming a more
complicated arena with dead-end passageways. Specifically, we highlight the simplicity
and intuition of the self-escape capability without incorporating a combination ofsophisticated algorithms.

104

Advances in Robot Navigation

3. Problem statement
3.1 Robot model and notations(a) ri ’s local coordinate(b) observation set O(c) triangular configuration T

Fig. 2. Illustration of definition and notation
In this work, we consider a swarm of mobile robots denoted by r1 ,⋯,rn . It is assumed that an
initial distribution of all robots is arbitrary and their positions are distinct. Each robot
autonomously moves on a two-dimensional plane. Robots have no leader and no identifiers.
They do not share any common coordinate system. Due to a limited observation range, eachrobot can detect the positions of other robots only within its line-of-sight. In addition, robots
are not allowed to communicate explicitly with each other.
Next, as illustrated in Fig. 2-(a), let’s consider a robot r with local coordinate
system r , and ry,i . The robot’s heading direction ry,i is defined as the vertical axis of ri ’s
coordinate system. It is straightforward to determine the horizontal axis rx,i by rotating ry,i 90
degrees clockwise. The position of ri is denoted by pi . Note that pi is (0, 0) with respect to ri ’s
local coordinate system. The line segment pi pj is defined as a straight line
between pi and pj occupied by another robot rj . The distance between pi and pj is defined as
dist pi ,pj . In particular, the desired inter-robot distance between ri and rj is denoted by du .
Moreover, ang mi ,ni denote the angle between two arbitrary vectors mi and ni .
As shown in Fig. 2-(b), r detects the positions pj , pk and pl of other robots located within its
sensing boundary SB, yielding a set of the positions Oi = pj ,pk ,pl with respect to its local
coordinate system. When ri selects two robots rn1 and rn2 within its SB, we call rn1 and rn2 theneighbors of ri , and their position set pn1 ,pn2 is denoted by Ni as illustrated in Fig. 2-(c).
Given pi and Ni , a set of three distinct positions pi ,pn1 ,pn2 with respect to ri is called thetriangular configuration i , namely pi ,pn1 ,pn2 . We further define the equilateral triangularconfiguration, denote by i , as the configuration that all distances between any two of pi ,pn1 and pn2 of i are equal to du .
3.2 Problem definition
It is known that the local geometric shape of schools of tuna represents a diamond shape(Stocker, 1999), whereby tuna exhibit their adaptive behavior while maintaining the local
shape. Similarly, the local interaction in this work is to generate i from i . Formally, thelocal interaction is to have ri maintain du with Ni at each time toward forming i . Now, we canAdaptive Navigation Control for Swarms of Autonomous Mobile Robots

105

address the coordination problem of adaptive navigation of robot swarms based on the local
interaction as follows:
Given r1 ,⋯,rn located at arbitrarily distinct positions, how to enable the robots to autonomously
travel through unknown territories using only local information in order to reach a destination?
It is assumed that the unknown environment to be navigated by a swarm of robots includes
obstacles and dead-end passageways. Next, we advocate that adaptive flocking can beachieved by solving the following four constituent sub-problems.
•
Problem-1(Maintenance): Given robots located at arbitrarily distinct positions, how to
enable them to navigate with i .
•Problem-2(Partition): Given that an obstacle is detected, how to enable a swarm to split
into multiple smaller swarms to avoid the obstacle.
•
Problem-3(Unification): Given that multiple swarms exist in close proximity, how to
enable them to merge into a single swarm.
•
Problem-4(Escape): Given some robots trapped in a dead-end passageway, how to
enable them to escape from the area.

4. Geometric local interaction scheme
This section explains the local interaction among three neighboring robots. As presented in
ALGORITHM-1, the algorithm consists of a function φinteraction whose arguments are pi and
Ni at each activation.

Algorithm 1. Local Interaction (code executed by the robot ri at point pi)

Fig. 3. Illustration of the local interaction algorithm
4.1 Local interaction algorithm
Let’s consider a robot ri and its two neighbors rn1 and rn2 located within ri ’s SB. As shown in
Fig. 3, three robots are configured into i whose vertices are pi , pn1 and pn2 , respectively.

106

Advances in Robot Navigation

First, ri finds the centroid of the triangle △pi pn1 pn2 , denoted by pct , with respect to its local
coordinate system, and measures the angle ϕ between the line pn1 pn2 connecting theneighbors and rx,i (r ’s horizontal axis). Using pct and ϕ, ri calculates the next movement
point pti . Each robot computes pti by its current observation of neighboring robots.
Intuitively, under ALGORITHM-1, ri may maintain du with its two neighbors at each time.
In other words, each robot attempts to form an isosceles triangle for Ni at each time, andby repeatedly running ALGORITHM-1, three robots configure themselves into i (Lee &Chong, 2009).
4.2 Motion control
As illustrated in Fig. 4-(b), let’s consider the circumscribed circle of an equilateral triangle
whose center is pct of △pi pn1 pn2 and radius dr is du ⁄√3. Under the local interaction, thepositions of each robot are determined by controlling the distance di from pct and theinternal angle αi (see Fig. 4-(a)). First, the distance is controlled by the following equation
di t =-a di t -dr ,(1)

Where a is a positive constant. Indeed, the solution of (1) is di t =|di 0 |e-at +dr thatconverges exponentially to dr as t approaches infinity. Secondly, the internal angle iscontrolled by the following equation
αi t =k βi t -γi t -2αi t ,(a) control parameters range d and bearing α(2)(b) desired equilateral triangle

Fig. 4. Two control parameter of local interaction
where k is a positive number. Because the total internal angle of a triangle is 180˚ , (2) can be
rewritten as
αi t =k' 60˚-αi t ,(3)+ 60˚ that converges
where k' is 3k. Likewise, the solution of (3) is α t = |α 0 |eexponentially to 60˚ as t approaches infinity.
Note that (1) and (3) imply that the trajectory of ri converges to dr and 60˚, an equilibrium
state as termed dr 60˚ T shown in Fig. 4-(b). This also implies that three robots eventuallyAdaptive Navigation Control for Swarms of Autonomous Mobile Robots

107

form i . In order to prove the convergence of the local interaction, we apply Lyapunov’s
stability theory (Slotine & Li, 1991). Lyapunov’s stability theorem states that if there exists a
scalar function v x of the state x with continuous first order derivatives such that v x is
positive definite, v' x is negative definite, and v x →∞ as ‖x‖→∞, then the equilibrium atthe origin is asymptotically stable. Now, the desired configuration can be regarded as one
that minimizes the energy level of a Lyapunov function.
Consider the following scalar function of the state x = di t αi t T with continuous firstorder derivatives:
f, =

1
d −d
2

+

1
60˚ − α2.

(4)This scalar function is always positive definite except di ≠dr and αi ≠60. The derivative of thescalar function is given byf, =− d −d

− 60˚ − α,(5)which is obtained by differentiating fl,i to substitute for di and α . It is evident that (5) is
negative definite and the scalar function fl,i is radially unbounded since it tends to infinity
as ‖x‖→∞. Therefore, the equilibrium state is asymptotically stable, implyingthat ri reaches a vertex of i . Further details on the convergence proof are given in (Lee &Chong, 2009).

Fig. 5. Adaptive navigation algorithm flowchart

5. Adaptive navigation algorithm
As illustrated in Fig. 5, the input to the adaptive navigation algorithm at each time is Oi andthe arena border detected with respect to ri ’s local coordinate system, and the output is ri ’s
next movement position. When ri observes the arena within its SB, depending on whether or
not it can move forward, it either executes the partition function to avoid the obstacle or theescape function to break a stalemate. When ri faces no arena border but observes other108

Advances in Robot Navigation

swarms, it executes the unification function. Otherwise, it basically performs themaintenance function to navigate toward a goal.

Algorithm 2. Neighbor Selection -1 (code executed by the robot ri at point pi)
The four functions above should determine two positions pn1 and pn2 occupied by twoneighbors rn1 and rn2 . These positions are the input arguments of ALGORITHM-1. Before
explaining the four functions as individual solutions of each sub-problem, we introduce theneighbor selection algorithm commonly used in the four functions, enabling ri to select its
neighbor robots. To form i , the first neighbor rn1 is selected as the one located the shortest
distance away from ri as shown in Fig. 6-(a). When there exist two or more candidates rn1m
and rn1n for rn1 , ri arranges their positions pn1m = xn1m ,yn1m and pn1n = xn1n ,yn1n with respect
to ri ’s local coordinate system. Then, ri uniquely determines its rs1 by sorting their positionsin the following increasing order with respect to its local coordinate system:
where the logic symbols ∨ and ∧if pn1m <pn1n ⇔ yn1m <yn1n ∨ yn1m =yn1n ∧ xn1m <xn1nindicate the logical conjunction and the logical disjunction, respectively. As presented in Fig.
6-(b), the second neighbor rn2 is selected such that the length of i ’s perimeter is minimized
as follows: min dist pn1 ,pn2 +dist pn2 ,pi . In particular, when both ri and the neighbors are
all aligned, if there are three or more robots in Oi , rn2 is re-selected such that ri is not
located on the same line. Under ALGORITHM-2, ri is able to select its neighbors and thenform i . Notice that the currently selected neighbors do not coincide with ones at the nexttime due to the assumption of anonymity. Using the current Oi by ri , i is newly formed ateach time.

(a) rn1 selection(b) rn2 selection

Fig. 6. Illustration of the neighbour selection algorithm
5.1 Maintenance function
The first problem is how to maintain i with neighboring robots while navigating. As shownin Fig. 7-(a), ri adjusts its traveling direction Ti with respect to its local coordinate system andAdaptive Navigation Control for Swarms of Autonomous Mobile Robots

109

computes Oi at the time t. By rotating Ti 90 degrees clockwise and counterclockwise,
respectively, two vectors Ti,c and Ti,a are defined. Within ri ’s SB, an area of traveling direction
A Ti is defined as the area between Ti,c and Ti,a as illustrated in Fig. 7-(b). Under
ALGORITHM-2, ri checks whether there exists a neighbor in A Ti . If any robots exist
within A Ti , ri selects the first neighbor rn1 and defines its position pn1 . Otherwise, ri spots avirtual point pv located some distance dv away from pi along A Ti , which gives pn1 . After
determining pn1 , rn2 is selected and its position pn2 is defined.

(a) traveling direction Ti(b) maintenance area A Ti

Fig. 7. Illustration of the maintenance function
5.2 Partition function(a) favorite vector fj(b) partition area A fjmax

Fig. 8. Illustration of the partition function
When ri detects an obstacle that blocks its way to the destination, it is required to modify the
direction toward the destination avoiding the obstacle. In this work, ri determines its
direction by using the relative degree of attraction of individual passageways sj , termed thefavorite vector fj , whose magnitude is given:

110

Advances in Robot Navigation

f =

w

(6)

d

where wj and dj denote the width of sj and the distance between the center of wj and pi ,respectively. Note that if ri can not exactly measure wj beyond its SB, wj may be shortened.
Now, sj can be represented by a set of favorite vectors fj 1≤j≤m , and then ri selects the
maximum magnitude of fj , denoted as fj

max. Similar to defining A Ti above, ri defines a

maximum favorite area A fjmax based on the direction of fj

maxwithin its SB. If neighbors

are found in A fjmax , ri selects rn1 to define pn1 . Otherwise, ri spots a virtual point pv locatedat dv in the direction of fj
ALGORITHM-2.

max

to define pn1 . Finally, rn2 and its rn2 are determined under

5.3 Unification function
In order to enable multiple swarms in close proximity to merge into a single swarm, ri
adjusts Ti with respect to its local coordinate system and defines the position set of robots Du
located within the range of du . r computes ang Ti ,pi pu , where pi pu is the vector startingfrom pi to a neighboring point pu in Du , and defines a neighbor point pref that gives theminimum ang Ti ,pi pu between Ti and pi pu . If there exists pul , ri finds another neighborpoint pum using the same method starting from pi pul . Unless pul exists, ri defines pref as prn .
Similarly, ri can decide a specific neighbor point pln while rotating 60 degrees
counterclockwise from pi pref . The two points, denoted as prn and pln , are located at thefarthest point in the right-hand or left-hand direction of pi pu , respectively. Next, a
unification area A Ui is defined as the common area between A Ti in SB and the rest of thearea in SB, where no element of Du exists. Then, ri defines a set of robots in A Ui and selects
the first neighbor rn1 . In particular, the second neighbor position pn2 is defined such that the
total distance from pn1 to pi can be minimized only through either prn or pln .

(a) traveling direction Ti
Fig. 9. Illustration of the unification function(b) unification area A Ui

Adaptive Navigation Control for Swarms of Autonomous Mobile Robots

111

5.4 Escape control
When ri detects an arena border within its SB as shown in Fig. 10-(a), it checks whether i isequal to i . Neighboring robots should always be kept du distance from ri . Moreover, ri ’s
current position pi and its next movement position pti remain unchanged for several time
steps, ri will find itself trapped in a dead-end passageway. ri then attempts to find newneighbors within the area A Ei to break the stalemate. Similar to the unification function, ri
adjusts Ti with respect to its local coordinate system and defines the position set of robots De
located within SB. As shown in Fig. 10-(b), ri computes ang Ti ,pi pe , where pi pu is the vector
starting from pi to a neighboring point pe in De , and defines a neighbor point rref that gives
the minimum ang Ti ,pi pe between Ti and pi pu . While rotating 60 degrees clockwise andcounterclockwise from pi pref , respectively, ri can decide the specific neighbor points pln andprn . Employing pln and prn , the escape area A Ei is defined. Then, ri adjusts a set of robots in
A Ei and selects the first neighbor rn1 . In particular, the second neighbor position pn2 isdetermined under ALGORITHM-2.

(a) encountered dead-end passageway(b) merging with another adjacent swarm

Fig. 10. Illustration of the escape function

6. Simulation results and discussion
This section describes simulation results that tested the validity of our proposed adaptive
navigation scheme. We consider that a swarm of robots attempts to navigate toward astationary goal while exploring and adapting to unknown environmental conditions. In
such an application scenario, the goal is assumed to be either a light or odor source that can
only be detected by a limited number of robots. As mentioned in Section 3, the coordinatednavigation is achieved without using any leader, identifiers, global coordinate system, andexplicit communication. We set the range of SB to 2.5 times longer than du .
The first simulation demonstrates how a swarm of robots adaptively navigates in anenvironment populated with obstacles and dead-end passageway. In Fig. 11, the swarm
navigates toward the goal located on the right hand side. On the way to the goal, some of
the robots detect a triangular obstacle that forces the swarm split into two groups from 7 sec(Fig. 11-(c)). The rest of the robots that could not identify the obstacle just follow theirneighbors moving ahead. After being split into two groups at 14 sec (Fig. 11-(d)), each group
maintains their local geometric configuration while navigating. At 18 sec (Fig. 11-(e)), some112

Advances in Robot Navigation

robots happen to enter a dead-end passageway. After they find themselves trapped, theyattempt to escape from the passageway by just merging themselves into a neighboringgroup from 22 sec to 32 sec (from Figs. 11-(f)) to (k)). After 32 sec (Fig. 11-(k)), simulation
result shows that two groups merge again completely. At 38 sec (Fig. 11-(l)), the robots
successfully pass through the obstacles.

Fig. 11. Simulation results of adaptive flocking toward a stationary goal ((a)0 sec,(b)4 sec,(c)7 sec,(d)14 sec,(e)18 sec,(f)22 sec,(g)23 sec,(h)24 sec,(i)28 sec,(j)29 sec,(k)32 sec,(l)38sec)

Adaptive Navigation Control for Swarms of Autonomous Mobile Robots

113

Fig. 12 shows the trajectories of individual robots in Fig. 11. We could confirm that theswarm was split into two groups due to the triangular obstacle located at coordinates (0,0).
If we take a close look at Figs. 11-(f) through (j) (from 22 sec to 29 sec), the trapped ones
escaped from the dead-end passageway located at coordinates (x, 200). More important,
after passing through the obstacles, all robots position themselves from each other at thedesired interval du .

Fig. 12. Robot trajectory results for the simulation in Fig.11
Next, the proposed adaptive navigation is evaluated in a more complicated environmental
condition as presented in Fig. 13. On the way to the goal, some of the robots detect a
rectangular obstacle that forces the swarm split into two groups in Fig. 13-(b). After passing
through the obstacle in Fig. 13-(d), the lower group encounters another obstacle in Fig. 13(e), and split again into two smaller groups in Fig. 13-(g). Although several robots aretrapped in a dead-end passageway, their local motions can enable them to escape from thedead-end passageway in Fig. 13-(i). This self-escape capability is expected to be usefully
exploited for autonomous search and exploration tasks in disaster areas where robots haveto remain connected to their ad hoc network. Finally, for a comparison of the adaptive
navigation characteristics, three kinds of simulations are performed as shown in Figs. 14
through 16. All the simulation conditions are kept the same such as du, the number ofrobots, and initial distribution. Fig. 14 shows the behavior of mobile robot swarms without
the partition and escape functions. Here, a considerable number of robots are trapped in thedead-end passageway and other robots pass through an opening between the obstacle andthe passageway by chance. As compared with Fig. 14, Fig. 15 shows more robots passthrough the obstacles using the partition function. However, a certain number of robots
remain trapped in the dead-end passageway because they have no self-escape function. Fig.

114

Advances in Robot Navigation

16 shows that all robots successfully pass through the obstacles using the proposed adaptive
navigation scheme. It is evident that the partition and escape functions will provide swarmsof robots with a simple yet efficient navigation method. In particular, self-escape is one of
the most essential capabilities to complete tasks in obstacle-cluttered environments that
require a sufficient number of simple robots.

Fig. 13. Simulation results of adaptive flocking toward a stationary goal ((a)0 sec,(b)8 sec,(c)10 sec,(d)14 sec,(e)18 sec,(f)22 sec,(g)25 sec,(h)27 sec,(i)31 sec,(j)36)

Adaptive Navigation Control for Swarms of Autonomous Mobile Robots

Fig. 14. Simulation results for flocking without partition and escape functions

Fig. 15. Simulation results for flocking with only partition function

115

116

Advances in Robot Navigation

Fig. 16. Simulation results for flocking with the partition and escape functions

7. Conclusions
This paper was devoted to developing a new and general coordinated adaptive
navigation scheme for large-scale mobile robot swarms adapting to geographicallyconstrained environments. Our distributed solution approach was built on the following
assumptions: anonymity, disagreement on common coordinate systems, no pre-selectedleader, and no direct communication. The proposed adaptive navigation was largely
composed of four functions, commonly relying on dynamic neighbor selection and local
interaction. When each robot found itself what situation it was in, individual appropriate
ranges for neighbor selection were defined within its limited sensing boundary and therobots properly selected their neighbors in the limited range. Through local interactions
with the neighbors, each robot could maintain a uniform distance to its neighbors, andadapt their direction of heading and geometric shape. More specifically, under the
proposed adaptive navigation, a group of robots could be trapped in a dead-end passage,
but they merge with an adjacent group to emergently escape from the dead-end passage.
Furthermore, we verified the effectiveness of the proposed strategy using our in-house
simulator. The simulation results clearly demonstrated that the proposed algorithm is a
simple yet robust approach to autonomous navigation of robot swarms in highlycluttered environments. Since our algorithm is local and completely scalable to any size, itis easily implementable on a wide variety of resource-constrained mobile robots andplatforms. Our adaptive navigation control for mobile robot swarms is expected to be
used in many applications ranging from examination and assessment of hazardous
environments to domestic applications.

Adaptive Navigation Control for Swarms of Autonomous Mobile Robots

117

8. References
Balch, T. & Hybinette, M. (2000). Social potentials for scalable multi-robot formations, Proc.
IEEE Int. Conf. Robotics and Automation, pp. 73-80, IEEE
Correll, N., Bachrach, J., Vickery, D., & Rus, D. (2009). Ad-hoc wireless network coveragewith networked robots that cannot localize, Proc. IEEE Int. Conf. Robotics andAutomation, pp. 3878 - 3885, IEEE
Esposito, J. M. & Dunbar, T. W. (2006). Maintaining wireless connectivity constraints forswarms in the presence of obstacles, Proc. IEEE Int. Conf. Robotics and Automation,
pp. 946-951, IEEE
Folino, G. & Spezzano, G. (2002). An adaptive flocking algorithm for spatial clustering, In:
Parallel Problem Solving from Nature (LNCS), Yao, X., Burke, E., Lozano, J. A., Smith,J., Merelo-Guervos, J. J., Bullinaria, J. A., Rowe, J., Tino, P., Kaban, A., & Schwefel,
H.-P. (Ed.), Vol. 2439, 924-933, Springer Berlin, ISBN: 978-3-540-23092-2
Fowler, T. (2001). Mesh networks for broadband access, IEE Review, Vol. 47, No. 1, 17-22
Gu, D. & Hu, H. (2010). Distributed minmax filter for tracking and flocking, Proc. IEEE/RSJ
Int. Conf. Intelligent Robots and Systems, pp. 3562-3567, IEEE
Ikemoto, Y., Hasegawa, Y., Fukuda, T., & Matsuda, K. (2005). Graduated spatial patternformation of robot group, Information Science, Vol. 171, No. 4, 431-445
Lam, M. & Liu, Y. (2006). ISOGIRD: an efficient algorithm for coverage enhancement in
mobile sensor networks, Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, pp.
1458-1463, IEEE
Lee, G. & Chong, N. Y. (2009). A geometric approach to deploying robot swarms, Annals of
Mathematics and Artificial Intelligence, Vol. 52, No. 2 − 4, 257-280
Lee, G. & Chong, N. Y. (2009-b). Decentralized formation control for small-scale robot teams
with anonymity, Mechatronics, Vol. 19, No. 1, 85-105
Lee, G. & Chong, N. Y. (2008). Adaptive flocking of robot swarms: algorithms andproperties, IEICE Trans. Communications, Vol. E91 − B, No. 9, 2848-2855
Lyengar, R., Kar, K., & Banerjee, S. (2005). Low-coordination topologies for redundancy insensor networks, Proc. 3rd Acm Int. Sym. Mobile Ad Hoc Networking and Computing,pp. 332-342, ACM
Nembrini, J., Winfield, A., & Melhuish, C. (2002). Minimalist coherent swarming of wirelessnetworked autonomous mobile robots, Proc. 7th Int. Conf. Simulation of Adaptive
Behavior, pp. 373-382, IEEE
Olfati-Saber, R. (2006). Flocking for mult-agnet dynamic systems: algorithms and theory,
IEEE Trans. Automatic Control, Vol. 51, No. 3, 401-420
Ogren, P. & Leonard, N. E. (2005). A convergent dynamic window approach to obstacle
avoidance, IEEE Trans. Robotics and Automation, Vol. 21, No. 2, 188-195
Stocker, C. W. (1987). Flocks, herds, and schools: a distributed behavioral model, Computer
Graphics, Vol. 21, No. 4, 25-34
Sahin, E. (2005). Swarm robotics: from sources of inspiration to domains of application, In:
Swarm Robotics (LNCS), Sahin, E & Spears, W. M., (Ed.), Vol. 3342, 10-20, Springer
Berlin, ISBN: 978-3-540-24296-3
Shucker, B., Murphey, T. D., & Bennett, J. K. (2008). Convergence-preserving switching for
topology-dependent decentralized systems, IEEE Trans. Robotics, Vol. 24, No. 6,1405-1415

118

Advances in Robot Navigation

Slotine, J. E. & Li,W. (1991). Applied nonlinear control, Prentice-Hall, ISBN: 0-13-040890-5
Spears, D., Kerr, W., & Spears, W. M. (2006). Physics-based robot swarms for coverage
problems, Int. Jour.Intelligent Control and Systems, Vol. 11, No. 3, 124-140
Spears, W. M., Spears, D., Hamann, J., & Heil, R. (2004). Distributed, physics-based controlof swarms of vehicles, Autonomous Robots, Vol. 17, No. 2 − 3, 137-162
Stocker, S. (1999). Models for tuna school formation, Mathematical Biosciences, Vol. 156, No.
1−2, 167-190
Wilson, E. O. (1976). Sociobiology: the new synthesis, Harvard University Press, ISBN: 0674-00089-7
Yicka, J., Mukherjeea, B., & Ghosal, D. (2008). Wireless sensor network survey, Computer
Networks, Vol. 52, No. 12, 2292-2330
Zarzhitsky, D., Spears, D., & Spears, W. M. (2005). Distributed robotics approach to chemical
plume tracing, Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, pp. 4034-4039,
IEEE