Jisan
Research
Institute

" A pioneering research community "

 swarms

 

Research Mentor 

Dr. Sanza T. Kazadi
Jisan Research Institute 
JRI Research Mentor 
This email address is being protected from spambots. You need JavaScript enabled to view it.  

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.

Swarm Engineering

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.

Publications

Invited Book Chapters: 

  • S. Kazadi. Model Independent Economics Based on Swarm Engineering. Progress in Economics Research, Volume 18, New York: Nova Science Publishers, pp.233-247, 2011.
    (postscript) (PDF)

 

Abstract' 

In the classical approach to economics, conclusions about the way in which economic systems behave are drawn from the analysis of the consequences of assumptions about how the system constituents (individuals, firms, governments, etc.) will behave. Like other nonlinear dynamic systems, the analysis of such systems is difficult, and the detailed behaviors of the systems are highly dependent on the systems' initial conditions and specific design. Small changes in parameters can have very significant effects on the detailed function of the system. Careful scrutiny of the assumptions and initial conditions must be undertaken to ensure that the conclusions are relevant to the real world. Such an approach represents an if-then approach to economics, and has a specific weakness in that it is highly dependent on the creativity of the group generating the assumptions. 

We describe an alternative, only-if, approach to economics. Adapted from swarm engineering, this approach is a model-independent approach to economics. We demonstrate how, using a particularly simple model, the global economic goal can be described mathematically and used to determine a condition under which the global goal can be reached. We then provide several different types of vendor/consumer agent pairs which satisfy this goal. We also provide an example of a simple system and global goal that is impossible to achieve, demonstrating how this can be determined in a model-independent way. 

  • S. Kazadi and J. Lee. Swarm Economics. Advances in Computational Algorithms and Data Analysis Series: Lecture Notes in Electrical Engineering , Vol. 14 Ao, Sio-Iong; Rieger, Burghard; Chen, Su-Shing (Eds.), pp. 249-278, 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. Model Independence in Swarm Robotics. International Journal of Intelligent Computing and Cybernetics, Special Issue on Swarm Robotics, in press, 2009.
    (postscript) (PDF)

 

Abstract 

Purpose 

The development of a methodology for generating swarms is examined and illustrated using lossless flocking. 

Design / Methodology / Approach 

A general methodology for swarm design is described. Examples of this approach in the literature are examined. A general requirement for lossless flocking is developed. The requirement is used in developing two swarm behaviors. 

Findings 

It is possible to apply the approach to the lossless flocking and to use the swarm condition to develop two swarm behaviors which satisfy this condition in many situations. 

Research Limitations / Implications 

This research illustrates the general swarm engineering method and demonstrates how it can b e properly applied. 

Originality / Value 

 

The swarm engineering method is used to develop the "quark" model, a new physicomimetic model. 

  • 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 Clustering 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: 

  • S. Kazadi, S. Kazadi, J. Yang, J. Park. Orthogonality and optimality in non-pheromone mediated foraging. Proceedings IEEE Conference on Cybernetics and Intelligent Systems 2010. Singapore, June 28-30, 2010, pp. 212-217.
    (PDF)

 

Abstract 

We describe methods of reducing the variance in the outcomes of swarms. One method, based on predicting the attractors of the swarm system's phase space, is described and applied to two well-known swarm problems. A second method, based on implementing multiplicity or synchronous updating, is described and applied to two swarm problems. We describe conditions under which these two approaches may be used, illustrating them from the preceding examples. We also demonstrate that the second approach can be used to generate coupled differential equations that capture the behavior of the swarm, effectively giving a method of predicting the swarm's behavior and the phase space structure. 

  • S. Kazadi] and A. Lee Swarminess Proceedings, 11th IASTED International Conference on Intelligent Systems and Control 2008 , Orlando, Florida, USA, November 16-18, p. 220-227, 2008.
    (Postscript) (PDF

Abstract 

This paper examines the concept of swarminess, or the level of appropriateness of a swarm for a given task. We begin by defining the concept of a task and developing dependence maps including uni- and bidirectional dependences. We then define a vector swarminess measure. We examine two broad classes of tasks known as stigmergic and command tasks. We show that the swarminess of stigmergic tasks is infinite, while that of command tasks is finite. We use this to examine the swarm-based construction task and determine that this task, depending on available technology, may not be swarmy. 

  • S. Kazadi and J. Chang Hijacking Swarms Proceedings, 11th IASTED International Conference on Intelligent Systems and Control 2008 , Orlando, Florida, USA, November 16-18, p. 228-234, 2008.
    (Postscript) (PDF)

 

Abstract 

Swarms are defined by both their local and global behaviors. Swarm Engineering concerns itself with discovering classes of local behaviors based on local sensing and actuation which guarantee global properties of swarms emerge from any of the class of behaviors. One design requirement of swarm systems is that the swarm be capable of withstanding perturbations, deliberate or accidental, that occur in the behaviors of the individual agents. In the natural world, some swarms exploit the behaviors of other swarms in order to hijack the victim swarms, generally as a predatory behavior. In this paper, examine the cases under which a swarm can be hijacked. We demonstrate that a general set of conditions exist under which a swarm and some subset of its global properties may be hijacked. Swarms not satisfying this set of conditions may be hijacked only by overpowering them. 

  • 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. 

  • S. 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. 

  • S. Kazadi, John R. Lee, Julie Lee. Artificial Physics, Swarm Engineering, and the Hamiltonian Method, Proceedings of the 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)
The Jisan Research Institute · A California 501(c)3 Nonprofit Corporation · © Copyright 2009-2014 · All rights reserved