Research Mentor :
Dr. Sanza T. Kazadi
JRI
JRI Research Mentor
skazadi@jisan.org
Introduction
The creation of artificial swarms has become an interesting topic
of research in the last fifteen years. This research finds its roots in the
seminal work of Rodney Brooks (Brooks 1986) which advocated the creation of
simple robots with simple behaviors in the place of robots of complex abstract
models and interpreters for intelligent behavior. The method is called
behavior-based control and has become widely accepted, due to the
simplicity of the approach, the flexibility and potential for generalization to
learning and and the capability of researchers to create swarms of simple
behavior based robots capable of carrying out interesting behaviors. Several
researchers have proposed interesting methods of creating control algorithms for
such simple robots, including learning and evolutionary algorithms (Harvey 1994,
Mataric and Cliff 1996), and work continues on both of these general methods.
Artificial swarm design has thus far been largely along two different
lines of design. The first of these is the practical approach (Kelly
1996, 1998, 1998a, Mataric 1995, 1995a, 1997a), in which a particular
task is identified and a group of robots is built with the task in mind.
This work typically contains multiple iterations of design and redesign
of the physical robot and/or its controller to complete the task
(Goldberg and Mataric, 1997). The second of these is the theoretical
approach in which a task is examined theoretically, and a condition is
derived which will yield the global goal. The design of the robots is
then an exercise in obtaining robots whose real dynamics matches the
desired dynamics, which can take one iteration. The main difference
between these is that in the first approach, an understanding of the
underlying system dynamics is generated through the building and
improvement of various versions of the system, while the second attempts
to generate an understanding of these dynamics, and subsequently build
robotic systems based on this understanding. In this way, the second
approach is more similar to traditional methods in robotics, in which
the system dynamics are worked out before the generation of a robot. The
use of this approach in swarm robotics would seem to provide validation
of the swarm-based approach to system design, indicating that these
methods are not unrelated to work done on individual robots carrying out
sophisticated tasks with high precision. Rather, they may be seen as an
extension of those methods to tasks requiring a smaller degree of
individual precision.
Many studies have been undertaken using the practical approach to swarm
construction. Among these are studies investigating navigation and
exploration tasks, rudimentary construction tasks, task allocation
studies, and communication studies.
Cohen (Cohen 1996) reports on a mapping and navigation task in which a
swarm of robots spreads itself in a maze, and collectively maps the
terrain. The map is detailed enough to allow an agent to travel from a
point in the map to any other point in the map in a minimum amount of
time, while using minimal individual processing, and taking advantage of
an elegant communication scheme.
Mataric (Mataric 1995a, 1992a) describes a method for designing simple
orthogonal local behaviors which may be used to create diverse global
group-level behaviors. The design is a process of simultaneously
satisfying top-down (task-driven) and bottom-up (robot and
environment-driven) constraints of the problem. This work may be seen as
complementary to ours. Whereas our goal is the generation of conditions
which when satisfied will generate the desired behavior, this work
provides a set of techniques which may be used to satisfy the given
condition.
Gage (Gage 1995) details the design of a multiple robot system for mine
detection. This work focuses on illustrating the benefits in time and
correctness of coordinated and communicating multiple robot detection
schemes. The use of communication and coordination is found to be a
serious advantage over the lack of it, in terms both of detection speed,
correctness, and cost/success ratio.
Dorigo and Gamardella (Dorigo 1997) describe the creation of a swarm of
artificial virtual agents traveling on a graph made up of nodes and
links. This swarm is designed in such a way as to solve the traveling
salesman problem (TSP), which we discuss later in this Thesis. The
design is based on the behavior of ants, and is systematically improved
to produce a rather computationally quick method of solving the problem.
These four examples of swarm behavior illustrate the power of the method
in a concrete way.
The generation of real working models represents an important and
necessary step in the design and verification of a new technology.
However, the main weakness in these studies is their ability to be
generalized beyond closely related tasks, such as those investigated by
Dorigo and colleagues as extensions of the ant-based TSP work (Dorigo
1999). It is not clear how these studies might be used to design new,
very different swarms without significant additional effort.
In contrast, a method based on artificial physics and derived from
artificial life is gaining increasing support. This method purports to
create a dynamic set of equations capable of being followed by given
agents in a system which produce a desired behavior of the swarm. The
advantage of such an approach is that these equations may be completely
solved, yielding the stationary states of the system, and the modes of
evolution of the system. As long as the robots are capable of following
the dynamic equations of motion, the method will provide the desired
behavior (Spears 1999).
Spears and Gordon (Spears 1999) report work on an artificial
physics-based control algorithm intended to be employed on MAVs
(Micro-air vehicles). The central design condition is the creation of a
set of dynamic equations based on an attractive/repulsive force. This
force is of order r^-2 and reverses sign at a given distance between two
MAVs, switching from an attractive force to a repulsive force. A
modification of the system in which a sorting behavior is employed
allows the system to reliably create perfect hexagonal and square
lattices. This is the desired global outcome, and is accomplished using
only local actuators and sensors, making the possibility of porting the
algorithm to a MAV realistic. This work has only been carried out in
simulation thus far; future work may include the use of these methods.
Back to Top
Swarm Engineering Definition
Swarm engineering is complementary to both of the previous
approaches. It is important to be able to both create working robotic
platforms and simulations. However, it would seem to be desirable to be
able to express the work in a format that allows generalization and ease
of implementation. Thus, we propose the formal field of \emph{swarm
engineering} and use the remainder of this Thesis to illustrate it. We
define swarm engineering as a formal two-step process by that one
creates a swarm of agents which complete a predefined task. Swarm
engineering has two formal steps. The first step involves the generation
of a swarm condition. This is a condition which, when satisfied,
will guide the generation of a swarm of agents which is capable of
carrying out the desired action or actions. No specific method has yet
been formulated for this step, and it is largely problem-dependent. Many
methods may be employed to carry out this step including formal
mathematical analysis, a generation of understanding of the problem
domain through simulation or fabrication of working models, or any other
general method. What must be understood in this step is the behavior of
the swarm in the problem domain. Transfer of information about an odor
plume should occur only in the upstream direction, rather than the
downstream direction, as the latter may confuse the entire swarm.
This first step is extremely demanding in its requirements, however. It
requires that the problem be stated in such a way as to permit the
creation of swarm-based actions. This means that the statement of the
problem must be amenable to being satisfied by distributed agents,
rather than a single coordinated statement.
In general, care must be taken to avoid generating expressions of the
problem which focus on the macroscopic goal. Rather, the expression
should be centered around the microscopic goal, which may be satisfied
by the agents of possibly differing designs.
The second step in swarm engineering involves the fabrication of a
behavior or set of behaviors that satisfy the given swarm condition. If
the system is understood well enough to generate a veritable swarm
condition, the generation of a swarm behavior is often times
straightforward. For instance, if the swarm condition is that robots
must stay in close proximity, it is easy to generate sensors and
actuators to satisfy this.
The goal is to create one of any of a set of behaviors which provably
fulfills the swarm condition. Once this has been accomplished, questions
about the efficiency of such approaches may be asked. However, at this
point, the goal has been achieved and the new goal is to improve the
performance of the algorithm, not to generate the initial behaviors.
Swarm engineering is similar in its goals to behavior-based group
robotics (Mataric 1993). In both approaches, the goal is to generate a
predefined group behavior. However, in behavior based group robotics,
the approach is largely intuitive, and the process is complete when a
single working prototype system has been generated (Goldberg and Mataric,
1997). The goal of swarm engineering is to produce a general condition
or set of conditions which may be used to generate many different swarm
designs any of which can complete the global goal. Once this condition
or set of conditions is generated, specific behaviors which satisfy this
(these) condition(s) may be generated, with absolute certainty that
these will yield the desired global behavior.
Thus, swarm engineering consists of two related steps. The first step
is to propose an expression of the problem which leads to a set of
conditions on the individual agents which, when satisfied, will complete the task. The second step is to produce a behavior or set of behaviors
for one or many robots which accomplishes these requirements. We shall
investigate, in the next three Parts, three independent problems which
may be tackled using swarm-based techniques. In the first Part, no
general theory has been formulated, but a sufficient understanding of
the domains in which a swarm will be advantageous as well as the
condition for such a swarm to be effective is created. The second and
third Parts generate a succinctly stated theoretical swarm condition.
However, the swarm conditon of the third Part suffers from the effects
of random changes. We illustrate a method of circumventing this
difficulty.
Back to Top
Publications
Invited Book Chapter:
- S. Kazadi and J. Lee. Swarm Economicsi Advances in Computational Algorithms and Data Analysis Series: Lecture Notes in Electrical Engineering , Vol. 14 Ao, Sio-Iong; Rieger, Burghard; Chen, Su-Shing (Eds.) 2008,.
(postscript)PDF
Abstract
The Hamiltonian Method of Swarm Design is applied to the design
of an agent based economic system. The method allows the design of a system
from the global behaviors to the agent behaviors, with a guarantee that once
certain derived agent-level conditions are satisfied, the system behavior
becomes the desired behavior. Conditions which must be satisfied by consumer
agents in order to bring forth the ``invisible hand of the market"
are derived and demonstrated in simulation. A discussion of how this method
might be extended to other economic systems and non-economic systems is
presented.
Journal Papers:
- S. Kazadi, J. Wigglesworth, A. Grosz, A. Lim, D. Vitullo. Swarm-Mediated Cluster-Based Constuction. Complex Systems, 15(2), 157-181, 2004.
(postscript)
(PDF)
Abstract
We investigate the use of swarm clustering algorithms in the design
of simple robots capable of carrying out swarm-mediated construction.
Methods for generating multiple clusters of predetermined size are
developed. Relative cluster motion algorithms are also developed and
explored. All robotic algorithms are predicated on the use of only
robots utilizing no processing, gps, or explicit communication. Simple
stigmergic communication and minimal sensing capabilities are used
exclusively. We demonstrate swarms of minimal agents building equilateral
triangles, squares, and pentagons. Future use of these methods in
the design of more sophisticated construction techniques is discussed.
- S. Kazadi, M. Chung, B. Lee, and R. Cho. On the Dynamics of Puck Clusteri
ng Systems. Robotics and Autonomous Systems, 46(1), pp. 1-27, 2004.
(postscript)
(PDF)
Abstract
We examine the theoretical foundations for the dynamics of puck clustering
systems. Key in this investigation is the development of methods of
controlling variance in cluster size, an important precursor to swarm-mediated
clustering. We derive conditions under which clustering can take place
in a general framework, and demonstrate two different behavioral regimes
for clustering systems.
-
S. Kazadi, A. Abdul-Khaliq, and R. Goodman. On the Convergence of Puck Clustering Systems. Robotics and Autonomous Systems, 38 (2), 93-117,
2002. (postscript)
(PDF)
Theses:
Conference Papers:
-
Lihan Lai, Jeff Manning, Jeannie Su, and Sanza Kazadi
A Principled Approach to Swarm-Based Wall-Building
Proceedings, Third Australian Conference on Artificial Life 2007
, Gold Coast, Australia, December 4-6, p. 305-319,2007. (Postscript) (PDF)
Abstract
The Hamiltonian Method of Swarm Design is applied to the design
of an agent based economic system. The method allows the design of a system
from the global behaviors to the agent behaviors, with a guarantee that once
certain derived agent-level conditions are satisfied, the system behavior
becomes the desired behavior. Conditions which must be satisfied by consumer
agents in order to bring forth the "invisible hand of the market"
are derived and demonstrated in simulation. A discussion of how this method
might be extended to other economic systems and non-economic systems is
presented.
-
Sanza Kazadi, Paul Kim, John S. Lee, Joshua Lee
Swarm Economics
World Congress on Engineering and Computer Science 2007
, San Francisco, California, USA, October 24-26, p. 602-610,2007. (Postscript) (PDF)
Abstract
The Hamiltonian Method of Swarm Design is applied to the design
of an agent based economic system. The method allows the design of a system
from the global behaviors to the agent behaviors, with a guarantee that once
certain derived agent-level conditions are satisfied, the system behavior
becomes the desired behavior. Conditions which must be satisfied by consumer
agents in order to bring forth the "invisible hand of the market"
are derived and demonstrated in simulation. A discussion of how this method
might be extended to other economic systems and non-economic systems is
presented.
-
Sanza Kazadi, John R. Lee, Julie Lee
Artificial Physics, Swarm Engineering, and the Hamiltonian Method
World Congress on Engineering and Computer Science 2007
, San Francisco, California, USA, October 24-26, p. 623-632, 2007. (Postscript) (PDF)
Abstract
This paper describes the application of a swarm engineering methodology known
as the Hamiltonian method of swarm design to the artificial
physics problem. We demonstrate how to use this methodology to create swarms
of predefined global properties by applying it to the basic artificial physics
problem which creates locally hexagonal grids of agents, but fails to generate
global hexagons. A condition for global hexagonal structure is derived, and two
methods are described which accomplish this goal. Neither method requires
global information.
-
C. Lee, M. Kim, S. Kazadi
Robot Clustering
Proceedings of IEEE Conference on Systems, Man, and Cybernetics
, Waikoloa, Hawaii, USA, pp.1449-1454, October 2005. (Postscript) (PDF)
Abstract
Puck clustering systems are systems in which simple agents move building
material, or pucks, in a spatially limited area in a random or pseudo-random
way. While we adapt puck clustering theory to robot clustering systems
to generate a decentralized swarm of robots which coalesces using
only stigmergic information and local sensing into a single cluster,
this paper does not discuss puck clustering. Rather, its focus is
on aggregation. Robot clustering systems may be characterized by the
number of active robots in the system and the average variance of
the robots from a determined center. The number of active robots decreases
as cluster is formed, mirroring the analogous result of puck clustering.
There is a sharp decline in the average variance of the robots, indicating
a rapid coalescence of the robot swarm.
-
K. Chang, J. Hwang, E. Lee, S. Kazadi
The Application of Swarm Engineering Technique to Robust
Multi-chain Robot System.
Proceedings of IEEE Conference on Systems, Man, and Cybernetics
, Waikoloa, Hawaii, USA, pp.1429-1434, October 2005. (Postscript) (PDF)
Abstract
The swarm engineering technique construed in {[}1{]} attempts to develop
a general methodology that can be applied in creating swarm-mediated
systems. In this companion paper, we utilize the system established
in {[}2{]} to further explore the swarm engineering technique and
show how this methodology can be used to develop a robust multi-chain
robot system in a rigorous manner. In addition, we show the benefits
of building a multi-chain robot system using the swarm engineering
technique.
-
S. Kazadi
On the Development of a Swarm Engineering Methodology.
Proceedings of IEEE Conference on Systems, Man, and Cybernetics
, Waikoloa, Hawaii, USA, pp.1423-1428, October 2005. (Postscript) (PDF)
Abstract
This paper explores swarm engineering by revisiting popular concepts from
swarm intelligence and making them more rigorous by providing mathematical
definitions. The definitions form the basis for an examination of an
engineering methodology which starts by examining the desired state of a
global property of the system and then generates a requirement for a local
behavior that will generate the global property. This methodology allows a
local behavior to be tested theoretically before it is tested empirically.
-
S. Kazadi, E. Kondo, A. Cheng.
A Robust Centralized Linear Spatial Search Flock.
Proceedings of IASTED International Conference Robotics and
Applications, Honolulu, Hawaii, USA, pp.52-59, August 2004. (Postscript) (PDF)
Abstract
In this paper, we explore the development of a robust robot chain
designed to allow non-pheromone-mediated target localization and transportation
to a central location. The method is based on the development of a
lossless robot swarm capable of carrying out a search of a local area
in such a way that each individual robot is capable of determining
the direction along the chain that one might follow to the center
of search. We investigate some of the stability issues of the swarm,
examining the stability during the setup phase, after the setup phase,
and during catastrophic losses of individuals in the chain. We also
explore potential methods of using the mechanism to deal with obstacles
and multi-resource exploitation.
-
S. Kazadi, O. Koroleva.
Removing Degeneracy From Swarm Mediated Cluster-Based Construction.
Proceedings of IASTED International Conference Robotics and
Applications, Honolulu, Hawaii, USA, pp.60-66, August 2004. (Postscript) (PDF)
Abstract
In this paper we design swarm clustering algorithm to build, move
and place clusters of building materials on the desired place on
2D plane. Such algorithm consists of three phases: building
clusters, moving them radially and then orbitally. We present an
example that demonstrates desired cluster placement. In
particular, it is shown that with proposed algorithm capable of
building clusters, moving and placing them with respect to each
other in accordance with given requirements.
-
A. Zhang, M. Chung, B. Lee, R. Cho, S. Kazadi,
and R. Vishwanath. Variance in Converging Puck Cluster Sizes.
Proceedings of AAMAS'02, to appear, July 2002. (PDF Poster) (PDF -- full) (PS Poster) (PS -- full)
-
D. Lee, S. Kazadi, R. Goodman Swarm
Engineering for TSP ANTS'2000. (postscript) (PDF)
Back to Top
