Figure 1. Regions defined for repulsion/attraction fields
by
Bradley Department of Electrical Engineering
Virginia Polytechnic Institute and State University
Blacksburg, VA 24061-0111
*unsal@vt.edu [unsal@ri.cmu.edu]
**bay@vt.edu
A homogeneous population of robots is to be realized for applications such as material transportation, hazardous material handling, planetary exploration, etc. Several algorithms for spatial self-organization of this swarm are given. Self-organizing agents can arrange themselves geometrically in two- and three-dimensional space using only local information. The method is a distributed one: each agent uses only information obtained by its own sensors. Algorithms are based on feasible assumptions on sensing capability. It is also shown possible to divide such a population into groups around goals by communicating minimal data. The self-organizing characteristic of the swarm provides a modular, adaptive and dynamic system. The approach is useful when a central controller is not feasible. Performance of the algorithms is shown with simulations.
There is an increasing interest in multiple autonomous mobile robot systems due to their applicability to material handling and operations in hazardous environments: mine sweeping, multi-satellite defense systems, maintenance work in nuclear plants [4], and planetary exploration [8]. Such systems involve both the problems of multiple robot coordination and autonomous navigation.
One approach for controlling multiple mobile robots is to use a hierarchical or central controller. However, the tasks mentioned above require many robots that are able to navigate autonomously. It is difficult to use a central controller or a hierarchical method due to dispersed spatial distributions in a system of unknown composition, as well as for the risks inherent with a single point of failure. The number of agents and the dynamic character of the system also make it impractical. The advantages of a decentralized system will be outlined below where we briefly introduce the army-ant scenario.
Our "army-ant" scenario [2, 12] envisages a large population of identical mobile robots that are able to find and carry a relatively small number of palletized payloads from place to place. The locations of pallets are defined by homing beacon signals. Using the beacon signals, robots are able to group around a pallet and self-organize to lift and carry it to its destination. The robots react to beacon signals -that can be visualized as environmental clues-, similar to insects reacting to pheromone fields [6]. The algorithms defined in this paper can also be used in applications mentioned above.
Army-ant robots will be relatively small, and individually incapable of carrying the load, but they will be able to act cooperatively as a transporter, similar to ant colonies in foraging activity. We treat the army-ant robots as a self-organizing system, because self-organization -an important characteristic of most insect societies- has many advantages [3,10].
Army-ant robots would also have the following characteristics:
A self-organizing system has several advantages over a hierarchical, "fixed" system. It consists of simple individuals that require little programming and can be coordinated into a collective system interacting with its environment.
Control and communication methods for multiple-robot systems have been investigated by various researchers [4,5,7,9]. In these papers, problems such as motion planning and coordination of multi-robot systems are approached with a distributed control system in mind. There are also several experimental works on multiple mobile robots [5,7,15]. However, some of these works include a central information processor, and are based on extensive communications between agents; some require map knowledge of the environment. On the other hand, there is extensive research carried out on individual autonomous mobile robots. Many solutions to problems including path planning and obstacle avoidance were proposed and tested [1,11]. Although these methods are applicable to multi-robot systems, they also require a map knowledge. However, army-ant robots need not build or possess maps of the environment; neither do they need to know beacon and robot positions in absolute coordinates. These characteristics provide instant adaptation to the environment.
Our approach to controlling multi-robot systems is to use simple behavioral rules for individual agents to achieve self-organization, instead of controlling them centrally. We avoid a central controller and/or hierarchical structure (and all the inconveniences of such methods). Our population of mobile robots form a large scale nonlinear system. Our aim is to incorporate multiple mobile robot control and reactive methods with self-organization in mind.
The main result will be little more than a binary decision tree, but one that results in robust, adaptive organizations in the group. Such a result achieved through central control would require a complex communications structure and would be computationally difficult.
Our scenario envisages beacons and robots signaling their position to the other robots. There are also several assumptions on the detection capabilities of the agents:
Part of our work on spatial self-organization in this paper is inspired by an interesting work by Sugihara and Suzuki [13]. They give a method for motion coordination of a group of mobile robots. Each robot plans its motion individually based upon a defined goal and detected position of other robots. Our method is also fully distributed in that sense.
Sugihara and Suzuki were able to create different geometric shapes by defining simple algorithms to be executed by a large number of agents: robots can form lines, circles, polygons and distribute themselves within a circle or convex polygon in the plane. Most of the algorithms defined in [13] are based on the assumption that each robot can detect the distance from the farthest teammate. Here, we use the advantage of a goal beacon and eliminate the need for the distance from the farthest agent. Consequently, we can introduce a method for forming separate teams around several beacons.
The first of many problems encountered in the army-ant scenario is the formation of a team around a "goal." It is necessary that the robots gather around a beacon (goal) to start the next phase (e.g., lifting). In this paper, we attempt to define several algorithms for organization of mobile semi-intelligent agents into 2-D and 3-D arrangements. Starting with a simple case, we demonstrate that robots can gather around goals and evenly distribute themselves in a defined region. We will also extend our algorithms to multi-goal situations.
The aim is to reach a stable and robust self-organizing system by using simple decision structures which may be implemented in a few lines of code.
A circle being the only rotation invariant shape in 2-D, we begin with an example on formation of a circle around a goal. The decision algorithm is very simple: a robot approaches the beacon up to certain (predefined) neighborhood d+e(psilon), its velocity being a function of its distance from the beacon. When a robot finds itself inside the circular region defined by d-e(psilon), it is "repelled" by the beacon. In the e(psilon)-region, each robot moves away from its closest mate. Our assumptions above guarantee the detection of the closest mate (Figure 1).
Figure 1. Regions defined for repulsion/attraction fields
All agents knowing the value of d and running the same algorithm, they form an almost perfect circle with radius d around the beacon. The use of a beacon enables us to find a new method for 2-D arrangement that uses only localized information.
Simulations running this algorithm gave very satisfactory results (Fig. 2): all agents are in the defined e(psilon)-region and they are distributed on the circle uniformly. As long as the value of the displacement per time step (velocity/force function) near the e-region is not much larger than the size of the e(psilon)-region, a satisfactory result is guaranteed.
We do not consider the problem of collision avoidance among agents. The performance of the algorithms should remain the same if this problem or existence of obstacles are considered. These issues can be handled with existing reactive behaviors.
The algorithm defined in the previous section can be altered to obtain an almost uniform distribution in a circle or can be directly applied to 3-D.
If we omit the variable e(psilon) (i.e., the e(psilon)-region) and force all agents inside the circle to move away from their closest teammate, agents approaching the beacon will fill the circular region defined by d almost uniformly. Assumptions for this algorithm are the same as before. Fig. 3 shows that the algorithm provides an almost uniform final arrangement. Robots inside the circular region simply move one unit farther from the closest mate at each time step.
Figure 3. Initial and final positions for tf =100 with d=100
Although our army-ant scenario requires 2-D spatial arrangements, self-organizing populations of large numbers of robotics agents can be applied to mine-sweeping, search & rescue missions, and space applications. The mobile agents could be small satellites, space or underwater vehicles instead of army-ant robots.
Our algorithm can be directly applied to 3-D without any alterations. Obviously, in 3-D, the same algorithm will result in the formation of a spherical shell with the beacon in the center. Although it may be hard to distinguish the spherical shape, views from different angles reveal that the mesh is quite exact. It is possible to form a sphere with the defined approximations by choosing suitable parameters such as velocity functions for different regions. With the same parameters as in 2-D, the algorithm is slower in 3-D because of the introduction of one additional dimension. Similarly, the algorithm used to distribute the agents uniformly inside a circular region can be applied to 3-D.
In this section, we will extend these trivial examples to the formation of a 3-D paraboloid by the same robotic agents as before. The same assumptions and algorithms used here can also be applied to 2-D. However, we prefer to simulate the case in 3-D, which is slightly more complicated and has possible applications to space: a team of robotic agents in orbit may cooperatively act as a large antenna that can be oriented as desired.
To form a paraboloid, one must define its focal and vertex points. The paraboloid (parabola) is a surface (plane curve) generated by a point moving so that its distance a from a fixed point, namely focus, is equal to its distance from a fixed plane (line). The orthogonal distance between the fixed plane and the vertex is equal to the distance between the focal point and the vertex (Fig. 4).
The variable a clearly defines the shape of the paraboloid and has to be fed to the agents. Since our aim is to create a parabolic antenna, not the whole paraboloid, another variable, say b, is needed to define the antenna size. The variable b can be the direct distance from vertex to the perimeter of the antenna (See Fig. 4).
Having variables a and b fed to the agents, we have to have a beacon at each the focus and vertex of the paraboloid, or we have to direct to agents to these points. Here we use two agents. Defining the agent (beacon) at the focus as F, the distance from it as df and the agent (beacon) at the vertex as V, distance as dv, and considering the regions shown in Figure 5, our algorithm for formation of paraboloid is defined in Figure 6.
As shown in the flowchart, this algorithm, based on the assumptions given above, simply compares functions of "sensed" distances to some predefined variables. The decision for regions A and B are straightforward: comparison between pairs (dv, b) and (dv, df). The decision for e(psilon), e(psilon)+, and e(psilon)- regions are slightly more complicated. Having values df, dv, and a, we imagine a coordinate system such that the origin is at V and F is on the z-axis. Thus, the distance dv can be written as:
(5.1) 
x, y, z being the coordinates of an agent in the defined (imaginary) coordinate system. And, the distance from the focal point is:
(5.2) 
By (5.1) and (5.2), we get:
and:
Figure 4. Definition of the imaginary coordinate axis
Figure 5. 2-D representation of the regions defined in the algorithm
Figure 6. Flowchart of the algorithm for formation of a paraboloid.
For any point on the paraboloid, the values z and x*x+y*y must satisfy the equation:
If z is less than (x2+y2)/4a, then the point is in the half-space including the positive z-axis; otherwise it is in the half-space including the negative z-axis. Again an e(psilon)-region is defined.
Therefore each agent, having "sensed" df and dv,
can decide which direction to go using this abstraction. "Attraction" and
"repulsion" vectors are defined as functions of the dv and/or df.
This algorithm ensures the formation of an almost uniform paraboloid mesh. Simulations
with random initial conditions give satisfactory final positions as seen in Figure 8, even though the rules defined above do not positively
contribute to the formation during the first steps of the simulation (since it takes time
for the "beacon" agents to attain their desired positions). Also the velocity
function inside the e(psilon)-region is quite simple. After (and during)
the formation, the shape and orientation of the parabolic mesh can be controlled by simply
changing the position of the agent/beacon at the focus. The rest of the team will adjust
according to the algorithms defined.
Figure 8. Initial (top) and final positions of 20 agents with tf =500.
Examples given in the previous sections included a single beacon/goal. However, simultaneous handling of multiple pallets is featured in the army-ant scenario. Therefore, it is necessary that teams of agents group around several goals simultaneously.
Assume that m goals and n agents (m is much less than n) are randomly distributed in an obstacle-free area. In the simplest case, agents can simply move toward the closest goal, assuming that they can distinguish between beacon signals. It is obvious that this straight-forward method may result in quite uneven distributions. (In the simulations defined hereafter, we will refer to this goal distribution as the "initial distribution," to have a performance criterion.) To obtain a more uniform distribution among goals/beacons, we introduce an additional variable ds that is assumed to be known by all agents.
Switching distance ds is a variable which changes with time. It represents the radius of the forbidden circular region around each goal. This value or the variables defining ds as a function of time, are known by each agent moving toward its own designated goal. When an agent finds itself in the forbidden region (i.e., if its distance to the goal is smaller than ds at any given time t), it randomly changes its goal. Again we are assuming that all the beacons are in the detection region of all agents. When an agent changes its destination, the forbidden region also "moves" to the new destination. It is now defined around the new goal.
For example, in the situation shown in Figure 9, an agent approaching beacon B finds itself inside the forbidden region at time t, and therefore, changes its destination randomly. Its goal at time t+1 becomes beacon A. Since the distance to the beacon A is greater than the distance to beacon B, the robot is now outside the forbidden region defined by ds(t), and continues to approach beacon A on the next step t+2. Although the interpretation of the distance ds changes, the function (variables) defining ds is the same.
Figure 9. Interpretation of forbidden region defined by ds
The most logical choice for the function ds = fds(t) seems to be a decreasing function of time. Advantages of the introduction of such a function are shown with simulations. The main simulation algorithm is given in Fig. 10. Switching distance ds is effective if it is greater than dn at a given time. dn is again a predefined constant to define the neighborhood and to stop the switching algorithm. The moment the value of the switching distance becomes less than dn, all agents stop switching goals, and eventually, circles will form around each goal (See flow-chart in Figure 10). The agents will again be distributed uniformly in the circle defined by dn around each goal.
Figure 10. Flowchart for use of switching distance ds
Figure 11. Definition of switching distance and, initial (x) and final positions of
agents.
Figure 12. Definition of switching distance and, initial (x) and final positions of
agents.
A particular choice of function for ds does not always give the best results for every initial condition (position of robots and goals). However, improvement in the final goal allocations is distinctive.
The result given in Figure 11 shows that goal allocation of robots can be changed from highly uneven initial distribution ([6 6 18] for 30 robots and 3 beacons) to an almost even distribution ([11 9 10]) by defining ds as shown. A very similar definition for switching distance (Fig. 12) again gives a satisfactory result (from [0 11 29] to [13 11 16]), close to best distribution ([13 13 14]) for different initial positions.
Although parameter definition of ds must be done by trial-and-error, the same function parameters work well for similar initial beacon/agent distributions.
The algorithm using the notion of switching distance is based on relatively simple assumptions on the communication capabilities of the robots. We may increase the number of essential assumptions, and therefore, communication capabilities of the robots, in order to devise more complex algorithms. By enabling agents to broadcast their assigned ID numbers and other parameters or by designing intelligent beacons that can "count" arriving agents, it is possible to separate them into teams with the desired number of agents [14]. Although additional assumptions on the robot capabilities increase the complexity (and thus the cost) of the system, the "swarm" will be more adaptive to the environmental conditions (such as the positions of beacons, obstacles).
We have outlined simple spatial self-organization methods for mobile agent/beacon systems. Based on feasible navigation and communication assumptions, algorithms defined here have many applications. These methods have obvious advantages over the central controller approach: Instead of communicating centrally computed coordinates to each agent, we use simple geometric properties of desired shapes to create repulsive/attractive force fields.
Since we use large time steps in simulations, there is no need for fast computation/communication, nor constant detection of teammate positions. The quality of the geometric shapes however will depend on the sensor accuracy.
The system of multiple mobile robots can also be visualized as a many-body problem [2]. Our advantage is that as we define attraction/repulsion functions acting on the agents, we actually create our own gravitation fields. Agents forming geometric shapes have only a partial knowledge of the environment, i.e., they cannot detect the form of the resulting geometric shape. Although none of them is aware of the fact, the resulting shape can be seen as a manifestation of collective behavior.
Furthermore, our self-organizing robots are an adaptive system. When an agent fails to operate, or beacon (or beacon robot in paraboloid formation) moves, the gravitation field definitions change, and, consequently, all agents move to their new position.
Here, we consider a bottom-up approach for spatial self-organization of multiple robots. On the other hand, the problem of transforming the final global task to individual behavior models (top-down approach) is yet to be resolved, if at all possible.
This material is based upon work supported by the National Science Foundation under Grant No. IRI-9202423 and , in part, by the Naval Research Laboratory under Grant No. N00014-99-1-G002. The content of this paper does not necessarily reflect the position or policy of the United States Government.
"mobile agents": Since not all agents will be doing the same thing at the same time, some degree of "heterogeneity" will emerge. This is desired and we will explicitly provide for and encourage "emergent functionality," but we will avoid assigning permanent roles.
quite exact: Simulations in Matlab display the agents that are not in the desired region by different colors. Also, it is possible to check the uniformity of the resulting mesh by simply comparing the average value of the distances between a robot and its teammates. different regions: Step size of velocity vector around e-region is relatively smaller than the value 2e(psilon), in order to form an almost perfect sphere. two agents: The choice of these agents can be automatic; either based on the initial distances, or by given identification numbers. simple: Each robot moves away from closest teammate by a one-unit at each time step. positions: In the given simulation examples, switching distance ds was chosen so that we are able to show the final goal allocations. Agents did not have sufficient time to fill uniformly the circular regions defined by dn. However, we know that the spatial distribution of agents inside the neighborhood would be (almost) uniform if we have chosen the final time to be larger than 300. each agent: Which may be impossible, for example, in planetary exploration missions.[1] Arkin, R.C., "Integrating Behavioral, perceptual, and World Knowledge in Reactive Navigation," in Designing Autonomous Agents, P. Maes, ed., Cambridge, Mass., 1990, pp. 105-122.
[2] Bay, J.S., and C. Ünsal, "Group Dynamics in Many-Robot Systems," submitted to IEEE Trans. on Robotics and Automation.
[3] Deneubourg J.L., S. Goss, J. Pasteels, D. Fresneau, and J.P. Lachaud, "Learning in Foraging and Division of Labor," in From Individual to Collective Behavior in Social Insects, J.M. Pasteels, and J.L. Deneuburg, eds., Experimentia Supplementum, vol. 54, B. Verlag, Basel, pp. 177-196. 4] Genovese, V., P. Dario, R. Magni, L. Odetti, "Self-Organizing Behavior and Swarm Intelligence in a Pack of Mobile Miniature Robots in Search of Pollutants," Proc. 1992 IEEE/RSJ Int. Conf. on Int. Rob. and Syst., Raleigh, NC, 1992, pp. 1575-1582. [5] Habib, M.K., H. Asama, M.K., I. Endo, A. Matsumoto, Y.Ishida, "Simulation Environment for An Autonomous Decen-tralized Multi-Agent Robotic system," Proc. 1992 IEEE/RSJ Int. Conf. on Int. Rob. and Syst., Raleigh, NC, 1992, pp. 1550-1557. [6] Kugler, P.N., and M.T. Turvey, Information, Natural Law, and Self-Assembly in Rhythmic Movement, Hillsdale, NJ: L. Erlbaum Assoc., 1987, pp. 69-84. [7] Mataric, M. J., "Kin Recognition, Similarity, and Group Behavior," in Proc. 15th Annual Cognitive Science Society Conference, Boulder, CO, June 1993. [8] Miller, D.P., "Multiple Behavior-Controlled Micro-Robots for planetary Surface Missions," Proc. 1990 IEEE Int. Conf. on Syst., Man, and Cybernetics, Los Angeles, Ca, Nov. 1990, pp. 281-292. [9] Parker, L.E., "Adaptive Action Selection for Cooperative Agent Teams," Proc. 2nd Int. Conf. on Simulation of Adap. Behavior, Dec. 1992. [10] Partridge, B.L., "The structure and Function of Fish Schools," Scientific American, 1982, pp. 114-123. [11] Rodin, E.Y., and S.M. Amin, "Intelligent Navigation For an Autonomous Mobile Robot," Proc. Int. Symp. on Int. Control, Arlington, VA, 1998, pp. 366-369. [12] Stilwell, D.J., and J.S. Bay, "Toward the Development of a Material Transport System using Swarms of Ant-like Robots," IEEE Conf. on Rob. and Auto., Atlanta, GA, 1993, pp. 766-771. [13] Sugihara, K., and I. Suzuki, "Distributed Motion Coordination of Multiple Mobile Robot," IEEE Int. Symp. on Int. Control, Philadelphia, PA, Sep. 1990, pp. 138-143. [14] Ünsal, C., "Self-organization in Large Populations of Mobile Robots," M.S. Thesis, VPI & SU, May 1993.Back to publications page.
Back to Cem Ünsal's home page.
