First problem encountered in our Army-ant scenario is the formation of a team around a "goal" (marshaling). It is necessary that robots gather around a beacon (goal) to start the next phase (e.g., lifting). In this chapter, we attempt to define several algorithms for organization of mobile semi-intelligent agents into 2-D and 3-D arrangements. We also extend our algorithms to multigoal situations and try to find relatively better solutions by increasing the number of assumptions on the "intelligence" of agents. We will try to explain our approach while giving some examples of spatial self-organization.
We want the Army-ant "swarm" to be a self-organizing system because of the nonlinear characteristics such as the significant changes in the overall behavior of the system due to small changes in the individual behaviors. On the other hand, it is highly difficult (if not impossible) to obtain analytical results for a large-scale nonlinear system. Because of the analytical difficulties in large-scale nonlinear interactions, our work has an "algorithmic" characteristic.
The approach taken in this thesis for formation of a circle around a goal by a group of robots is a distributed one. This method does not require a central controller. This is an important characteristic of a self-organizing system.
Our scenario envisages a beacon signaling to the robots the position of the pallet/goal. There are also several assumptions on the detection capabilities of the agents:
However, Army-ant robots have navigation characteristics different from
other autonomous mobile robots discussed in Chapter 2; our
scenario does not require the robots to build or possess maps of the environment. The
robots do not need to know beacon and robot positions in absolute coordinates. The
algorithm we used to form a circle is very simple: A robot approaches the beacon up to
certain (predefined) neighborhood d, its velocity being a function of its distance
from the beacon (Figures 3.1.1 and 3.1.2). For
different regions, a different function is defined:
Note that both vi and di are vectors. When a robot finds itself inside the
circular region defined by d, it is "repelled" by the beacon. In the
epsilon-region, each robot moves away from its closest mate. Our assumptions above
guarantee the detection of the closest mate.
Figure 3.1.1 Plot of the speed toward the goal as a function of distance to the
goal
Figure 3.1.2 Plot of the regions defined for velocity/force vector functions.
All agents knowing the value of d and running the same algorithm, they form an
almost perfect circle with radius d around the beacon. This algorithm, with the
advantage of using a beacon signal, does not require that the robots know the distance
from the farthest teammate, as in [35]. 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 (Figure 3.1.3)
gave very satisfactory results. Some of the results are shown in figures 3.1.4-3.1.8. As seen in figures 3.1.5, 3.1.7
and 3.1.8, all agents are in the defined epsilon-region and they are
distributed on the circle uniformly. As long as the value of the displacement per time
step (velocity/force function) is not much larger than the size of the epsilon-region, a
satisfactory result is guaranteed.
Figure 3.1.3 Algorithm for formation of a circle around a goal
Figure 3.1.4 Initial(x) and final positions of the agents for tf=50 with d=80.
Figure 3.1.5 Positions after 100 more time steps with the same parameter
values.
Figure 3.1.6 Initial(x) and final positions of the agents for tf=50 with d=80.
Figure 3.1.7 Positions after 100 more time steps with the same parameter
values.
Figure 3.1.8 Initial(x) and final positions of the agents for tf=50 with d=80.
None of the algorithms we define in this chapter take into consideration the problem of
collision avoidance among robots. The performance of the algorithms defined here should
remain basically the same if this problem is considered. We also cannot give a performance
analysis in terms of the quality of the resulting arrangements. The quality of the
approximation in the implementation will depend on the accuracy of sensors and response
time of actuators of the agents. These questions are to be addressed when actual mobile
robots are built and tested.
The algorithm defined in previous section can be altered to obtain an almost uniform distribution in a circle or can be directly applied to 3-D.
If the algorithm used for circle formation around a goal is changed as
in Figure 3.2.1, agents approaching the beacon will fill the circular
region defined by d almost uniformly. The algorithm is simpler than before. Each
agent entering the circular region starts to move away from the closest mate. Assumptions
for this algorithm are the same as before, and there is no need to use a variable
(epsilon) to define a desired region.
Figure 3.2.1 Algorithm for distributing agent uniformly inside a circle.
As sample simulation results show (Figures 3.2.2-3.2.5),
the algorithm provides a uniform final arrangement for relatively small number of robots .
As the number of robots increases, final distribution inside the circle may become less
uniform depending on the number of robots and their order of entering the region. Robots
inside the circular region simply move one unit farther from the closest mate at each time
step. A more complex definition for the velocity vector, perhaps by using two closest
teammates, can provide faster and more satisfactory results.
Figure 3.2.2 Initial(x) and final positions for tf=50 with d=100.
Figure 3.2.3 Positions after 50 more time steps with same parameter values.
Figure 3.2.4 Initial(x) and final positions for tf=200 with d=100.
Figure 3.2.5 Initial(x) and final positions of the agents for tf=200 with
d=100.
Although our Army-ant scenario requires 2-D spatial arrangements, self-organizing populations of large number of robotics agents can be applied to space applications. The mobile agents could be small satellites, space or underwater vehicles instead of Army-ant robots.
The algorithm defined in section 3.1 can be directly applied to 3-D without any alterations. In 3-D, the same algorithm will result formation of a sphere with the beacon in the center. As shown in figures 3.2.6-3.2.7, final positions resulting from randomly distributed initial conditions are again satisfactory. Although it may be hard to distinguish the spherical shape, views from different angles reveal that the mesh is quite exact. Simulations on 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. After several runs, we found that it is possible to form a sphere with the defined approximations, by suitably choosing parameters, such as velocity functions for different regions. For example, these functions must be defined so that the step size of velocity vector around epsilon-region is relatively smaller than the value 2*epsilon, in order to form an almost perfect circle. With the same parameters as in 2-D, the algorithm works 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. However, we do not give such examples since it is
visually and algebraically difficult to obtain a performance criterion for the final
positions of the agents inside the sphere.
Figure 3.2.6 Final positions of 30 agents around the beacon with tf=300 and
d=150.
Figure 3.2.7 Final positions of 30 agents around the beacon with tf=150 and
d=100.
As we demonstrated in the previous section, it is possible to generalize our assumptions and algorithms to 3-D. Here we will demonstrate the formation of a paraboloid by robotic agents based on the same assumption as before. Namely, (i) each agent can detect signals from beacons and/or agents and (ii) each agent is able to determine the direction and distance of these signals' sources. 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 obviously equal the distance between the focal point and the vertex.
The variable a clearly defines the shape of the paraboloid and
has to be fed to the agents forming it. Since our aim here is to create a parabolic
antenna, not the whole paraboloid, another variable, say b, is needed in order to
define the radius of the antenna. b can be the direct distance from vertex to the
perimeter of the antenna (See Figure 3.3.1).
Figure 3.3.1 Definition of the imaginay coordinate axes.
Having variables a and b fed to the agents, we have to have two beacons at
the focus and vertex of the paraboloid, or we have to direct to agents to these points.
Here we use two agents, chosen based on their distance to those target points, as beacons
and direct them accordingly. Agents have to be able to distinguish between signals emitted
by beacons or by the chosen 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 3.3.2, our algorithm for
formation of paraboloid is defined in Figure 3.3.3. The resulting
velocity vector field is shown in Figure 3.3.4.
Figure 3.3.2 2-D Representation of the regions defined in the algorithm
Figure 3.3.3 Flowchart of the algorithm for formation of a paraboloid
Figure 3.3.4 Force fields defined in the algorithm (Velocity functions are constant
in all regions).
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 epsilon regions are slightly more
complicated. Having values df, dv, and a, we define a coordinate
system such that the origin is at V and F is on the z-axis (See Figure 3.3.1).
Thus, the distance dv can be written as:
x, y, z being the coordinates of an agent in the defined (imaginary) coordinate system.
On the other hand, the distance from the focal point is:
From above equations, we get:
and:
For any point on the paraboloid, the values z and x2+y2 must satisfy the equation:
If z>(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 epsilon-region, shown in Figure 3.3.2, 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. Matlab simulations with random initial conditions gave satisfactory final positions as seen in figures 3.3.5 and 3.3.6, 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 epsilon- region is quite simple: Each robot moves away from closest teammate by a one unit at each time step. Again, choice of a more complex algorithm may provide a more uniform result in shorter time intervals. After (and also 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 3.3.5 Initial (top row) and final positions of 30 agents forming a
paraboloid with tf=600.
Figure 3.3.6 Initial (top row) and final positions of 20 agents forming a
paraboloid with tf=600.
Examples given in the previous sections included a single beacon/goal. However, simultaneous handling of multiple pallets is featured in Army-ant scenario. Therefore, it is necessary that teams of agents group around several goals simultaneously. The methods described here will be explained in order of increasing assumptions (and, therefore, communications).
Assume that m goals and n agents 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, as seen in Figure 3.4.1, where each one of the 40 robots moves toward the closest of
four goals. (In the simulations defined hereafter, we will refer to this goal distribution
as the "initial distribution," in order 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.
Figure 3.4.1 Initial (x) and final positions fot tf=150: All agents moved
toward closest beacon.
Switching distance ds is a variable that 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 3.4.2,
an agent approaching beacon B finds itself inside the forbidden region at time t
(distance to goal di(t) is less than switching distance ds(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 interpretation of the distance ds changes,
the function (variables) defining ds stays the same.
Figure 3.4.2 Interpretation of forbidden region defined by ds
Figure 3.4.3 Switching distance ds is decreasing with time (dn:
radius of the predefined neigborhood)
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 figure 3.4.4.
Figure 3.4.4 Flowchart for use of switching distance ds
As flowchart in Figure 3.4.4 shows, 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 algorithm is devised in such a
way that the agents will be distributed uniformly in the circle defined by dn around each
goal.
Simulation performed in Matlab enables us to define different time functions for ds. We can also define parameters other than ds, such as velocity as a function of distance, neighborhood dn around each goal, simulation time, as well as the number of agents and beacons.
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. Effects of the parameters on the final allocation can be determined by experiments, but only for specific initial positions.
The result given in Figure 3.4.5 shows that goal
allocation of robots can be changed from highly uneven ([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 (Figure 3.4.6) again gives a
satisfactory result (from [0 11 29] to [13 11 16]), close to best distribution ([13 13
14]) for different initial positions. A third example (Figure 3.4.7)
shows quite different choice of function. Again, this constant ds provides
distinctive improvement in the goal allocation. In simulation examples given in figures 3.4.5-3.4.7, switching distance ds was chosen
so that we are able to show the final goal allocations, and therefore 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 uniform or
almost uniform if we have chosen the final time to be larger than 300.
Figure 3.4.5 Definition of switching distance and resulting final positions at
tf=300 (Initial positions defined by x's).
Figure 3.4.6 Definition of switching distance and resulting final positions at
tf=300 (Similar function of ds, different initial positions).
Figure 3.4.7 Definition of a piecewise constant switching distance and
resulting final positions at tf=300.
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 here (and therefore communication capabilities of the agents) to devise a new algorithm.
Assume that, in addition to assumptions we made in section 3.1, all robots are able to broadcast two values (namely, "ID number" and "family value"), and detect values signaled by others.
We use these two values to create teams of robots associated with each goal. Each robot, again, initially moves toward the closest detected beacon. When a robot finds itself inside the neighborhood (region defined by dn), it checks if it is the first robot arriving. If it is the first one arriving into the neighborhood, the robot becomes a first, and starts running a different algorithm while trying to move away from the closest teammate (as they arrive). If there is already a first robot in the neighborhood, all other arriving robots compare their ID numbers with the ID number of the first agent. If the difference between two ID numbers is larger than family value fv, then the robot randomly switches goal. Otherwise, it stays in the neighborhood and tries to move away from the closest mate, including the first (See flowchart in figure 3.4.8). Family value fv is the maximum possible difference between ID numbers of a team (family). Calculations are done in modulo N, where N is the total number of robots.
For example, if robot number 45 in a population of 50 robots enters a neighborhood with a first robot with current ID number of 2 and family value of 10, it stays in the neighborhood since |45-2|mod(50)=7 is less than 10. fv is a predefined value computed and transmitted by firsts. For our simulations, we choose the number to be:
Therefore, receiving this value from the first, arriving robots can "compute" whether they are allowed in this particular neighborhood or not. This definition requires another assumption. Each agent (not each first, since any agent may become a first) must know the total number of robots.
This definition of fv does not guarantee an even distribution by
itself. The first robots run another algorithm to improve goal allocation. Each first
agent changes its ID number according to ID numbers of other firsts.
A first shifts its ID number so that the (modular) difference between its ID number and closest
first ID number increases (See Figure 3.4.9 for an example).
Figure 3.4.8 Flowchart of the fv algorithm
Figure 3.4.9 Three first agents shifting their ID numbers
Sample simulation results are given below. Results shown in figures 3.4.10
and 3.4.11 have the same initial conditions and parameters (e.g.,
velocity/force functions for different regions, neighborhood size, infinite detection
region) as the simulation examples given in figures 3.4.6 and 3.4.7, respectively. Comparison of the results shows a better final
distribution in both cases. When even allocation of robots is important, this method may
be used -although the number of assumptions on communication abilities of the agents is
larger. In both examples, one robot continuously switches its goal. This is due to
behavior of the first agents. Since we do not have any control over the ID number of the
robots that become first, the number of robots allowed in each family/team may not be the
same (even if all the first agents can detect each other) due to the ID number shifting
process. However, the probability that one or two robots are not allowed in any team is
relatively small, and in a large population of robots it is insignificant.
Figure 3.4.10 Initial (x) and final positions for tf=200, and goal allocation of robots. (Initial positions and other parameters are the same as the example given in Figure 3.4.6).
Figure 3.4.11 Initial (x) and final positions for tf=100, and goal allocation of robots. (Initial positions and other parameters are the same as the example given in Figure 3.4.6).
Figures 3.4.12 and 3.4.13 show two simulation results having the same initial conditions and parameter values. Only ID numbers of the robots are changed so that the ID numbers of the first agents would be different in each simulation run. Since these numbers are different, goal allocation versus time plot shows different characteristics (it takes more time to reach steady-state, and goal allocations change drastically in the first example), and in the second example one robot is again not allowed to any of the teams. However, the steady-state distributions are quite similar and almost even.
Figure 3.4.12 Initial (x) and final positions for tf=100, and goal allocation of robots.
Figure 3.4.13 Initial (x) and final positions for tf=100, and goal allocation of robots. (Initial positions and other parameters are the same as in Figure 3.4.12; only ID numbers of the robots are changed).
It is also possible to see the change in the ID numbers of the firsts and family sizes during the simulation. Simulations created in the Matlab 4.0 environment for this algorithm also show the detection map of the firsts.
As seen in the flowchart, we also assume that the total number of robots is known by all agents. This assumption decreases the versatility of the swarm. Instead of defining fv as a function of total number of agents, we can simply choose it as a constant value fed to all agents. Another approach is to design beacons capable of signaling required family size to agents. This method also enables us to form teams with different sizes if the size and/or weight differ from payload to payload.
It is also possible that the distances between the neighborhoods of beacons prevent the first agents from detecting each other. Since fv is defined as a function of the number of detected firsts, this may create a problem. However, if firsts robots cannot detect each other, that means not every robot can detect all beacons (assuming beacons have the same or lesser communication capabilities as robots). Again, the steady-state distribution is much better than initial distribution (See Figure 3.4.14).
Figure 3.4.14 Initial and final positions of the robots for tf=150, and goal allocation versus time. (Detection region of the agents are 700 units while the beacons and robots are distributed on a 1000x1000 space.)
The methods explained in this chapter are listed in increasing complexity in communication and assumptions. One can observe that we are slowly crossing the line to behavioral self-organization. In this section, we will outline a method that we call the "ideal case," without simulations. This method requires very explicit communications.
We can design robot receivers in a way that they would be able to change their reception bandwidth, i.e. detection-band limits. They must also be able to send signals at the same frequency as the beacon they are moving toward. Therefore, the robots could be programmed, for example, to double their detection limit and signal their arrival if they arrive into the defined neighborhood (We are still assuming that robots can detect the distance to signal sources).
Let us assume that the beacons defining the position of the pallets can also receive signals from agents in the neighborhood, can change their signal frequency, and are able to run simple algorithms such as counting. If agents entering the region can signal (using the same frequency so that no other beacon detect the signal) that they are now in the neighborhood, the beacon will be able to count the number of agents assigned to the pallet at a given time.
When the count reaches the predefined number of robots (which is programmed into the beacon), the beacon becomes invisible to robots outside by shifting its broadcasting frequency beyond the detection limits of agents which are not in the neighborhood. Since robots in the neighborhood have their detection band doubled, this change in the frequency can be used to start another phase.
This scenario brings another problem besides increased complexity in communications and beacon characteristics: Two or more robots arriving into the neighborhood at the same or in a very short interval, may create miscount. Although the solution to this problem lies in the concept of
semaphores, realizing a system which eliminates the problem, as in on-line reservation systems, means more complexity in the design of robots and beacons.Most of the algorithms defined in this section are based on the assumptions that agents can compute directions and distances to beacons and other agents. The displacements at each time step (i.e., velocities) of the agents are functions of these distance vectors. On the other hand, the last algorithm, which requires more explicit communications, uses ID numbers assigned to agents (along with the distance vectors) to compute the velocity vectors.
Since the velocity vectors computed at each time step are functions of distance vectors and/or ID numbers associated with agents, we can think of this model as a many-body physics model. Our many-body model in Army-ant scenario has an advantage: we can define our laws of gravitation as we want.
As simulations show, an increase in the amount and type of transferred data between agents leads to an increase in the "intelligence" of the swarm. On the other hand, each new assumption on the communication abilities of the agents (and beacons) will probably increase the cost and complexity of the "system." For example, the scenario defined as "ideal case" in section 3.4.3, based on more assumptions, requires very explicit communication capabilities. Problems such as two or more robots arriving into the neighborhood at the same time, can be solved given that each robot is equipped with devices able to solve the "source sharing problem."
Also, there may be cases that beacons are situated outside the detection region of the agents. Possible solutions of such a problem again require that robot detect not only the distance and direction, but also the "status" of other agents. Status can be another broadcast signal telling others that a particular robot is going toward a beacon. Using this signal along with detected distance value, robots can "school" together to find beacons, as do predator fishes.
The simulations in this chapter did not include any obstacles. However, Army-ant robots working in a warehouse encounter many problems that we did not consider here. As we explain in the next chapter, a status signal can be very useful when there are many obstacles creating "alleys."
Back
to Thesis Main PageTo Chapter 2
To Chapter 4