1Dimensional RobotSpace Cellular Automata
In Mead et al. [19, 20], each robot is represented as a cell c_{i} in a 1dimensional robotspace cellular automaton, where i refers to the index within the automaton; note that an index is not necessarily the robot’s identification number or address that is used for communication—it is simply a reference. A cell consists of a neighborhood H, a state s, a formation definition F, and a step function S (each of these variable concepts will be described in detail throughout this chapter), written as:
c_{i} = {H, s, F, S}  (Eq. 1) 
Neighborhood
Each cell c_{i} is part of a neighborhood H_{i}, where:
H_{i} = {c_{i1}, c_{i}, c_{i+1}}  (Eq. 2) 
Cells c_{i1} and c_{i+1} refer to the left and right neighbors of c_{i} within the automaton, respectively. Likewise, a particular neighbor is denoted c_{j}, where j is the index of the cell representing a neighboring robot. It follows that, by combining the neighborhoods of all n cells, connectivity is enforced when defining the entire automaton C:
C = H_{1} ∪ H_{2} ∪ … H_{n}  (Eq. 3) 
State
The state s_{i} of a cell c_{i} consists of the following variables: p, the relative position of the cell within the formation (referred to as formationrelative position); r_{des}, the set of all desired relationships with neighboring cells; r_{act}, the set of all actual relationships with neighboring cells; Θ, the rotational error of the robot within the formation; Γ, the translational error of the robot within the formation; t, the time step of the cell (each of these variable concepts will be described in detail throughout this chapter). Formally:
s_{i} = {p, r_{des}, r_{act}, Θ, Γ, t}  (Eq. 4) 
In cellular automata, to determine the state s_{i}^{t} of c_{i} at time t, it must consider the state of all cells in H_{i} at the previous time step. A state transition step function—or step function—S (see State Transition for details on how this determines the state) can be written such that:
s_{i}^{t} = S(s_{i1}^{t1}, s_{i}^{t1}, s_{i+1}^{t1})  (Eq. 5) 
Formation Definition
A desired formation F is defined by: f(x), a geometric description (in this chapter, a single mathematical function); R, the desired distance to maintain between neighbors in the formation; Φ, the orientation of each robot relative to the formation on an x/ycoordinate system (referred to as formationrelative orientation); p_{seed}, a formationrelative position that serves as a starting point from which the formation and relationships will propagate.
F = {f(x), R, Φ, p_{seed}}  (Eq. 6) 
This definition is sent to some robot, designating it as the seed cell c_{seed} of the automaton. Note that c_{seed} is not a leader, but rather an initiator of the coordination process.
State Transition
For purposes of establishing neighborhood relationships, a cell considers itself to be at some formationrelative position p_{i} (in the case of c_{seed}, p_{seed} is given in F):
p_{i} = [ x_{i} f(x_{i}) ]^{T}  (Eq. 7) 
Relationships
Desired relationships
. Relationships are determined by calculating a vector v from p_{i} to the intersection of f(v_{x}) and a circle centered at p_{i} with radius R (given in F):R^{2} = (v_{x} – p_{i,x})^{2} + (f(v_{x}) – p_{i,y})^{2}  (Eq. 8)  
r_{i→j,des} = [ v_{x} f(v_{x}) ]^{T}  (Eq. 9) 
Solving for the desired relationship vector r_{i→j,des} to some neighbor c_{j} results in two intersections: one in the positive direction and one in the negative direction. These solutions define right and left neighbor relationships r_{i→i+1,des} and r_{i→i1,des}, respectively; these relationship vectors are then rotated by –Φ, the negation of the given formationrelative orientation, so that robot heading is consistent within the formation definition [Fig. 15].
The formation definition and relationship information are communicated locally within the H_{i}. Neighboring robots repeat the process, but consider themselves to be at different formationrelative positions as determined by the desired relationship from their neighbor. For a neighbor c_{j}:
Note that relationships r_{j→i,des} and r_{i→j,des} are equal in magnitude, but opposite in direction. This property of the algorithm is what guarantees convergence and stability between two robots attempting to establish and maintain relationships with one another. These calculated desired relationships generate a connected graph that yields the shape of the formation [Fig. 16].
Actual relationships
. Using only sensor readings, robots calculate an actual relationship r_{i→j,act} with a neighbor c_{j} (see Robot Platform for details on how this relationship is determined). The robot communicates locally (i.e., within the neighborhood) discrepancies in its desired and actual relationships to neighboring cells. Correcting for these discrepancies produces a robot movement action A_{i} (discussed below) for each c_{i}, resulting in the overall organization of the desired global structure.Motion control
By evaluating the state of the H_{i}, c_{i} is able to determine the translational error Γ_{i} and rotational error Θ_{i} (a difference from actual to desired) that will define its movement action A_{i} in the physical world:
A_{i} = [ Γ_{i} Θ_{i} ]^{T}  (Eq. 12) 
(For simplicity, A_{i} is assumed to be along a safe trajectory.)
To determine values for Γ_{i} and Θ_{i}, c_{i} must first seek a point of reference. Recall that the seed cell c_{seed} was given an initial formationrelative position p_{seed}, from which the formation and relationships propagate. As the distance from c_{seed} increases, the propagated error accumulates. It follows that the neighbor of c_{i} whose formationrelative position is closest to p_{seed} will have the least amount of propagated error within the system and, thus, will likely represent the most reliable robot to reference. This reference neighbor c_{k} is then the neighbor that yields the minimum distance p_{k}′ from p_{seed} to p_{k}:
k  p_{k}′ = min({p_{i1} – p_{seed}, p_{i+1} – p_{seed}})  (Eq. 13) 
Rotational error
. The rotational error Θ_{i} is a difference in robot orientation, which is propagated to each successive cell in the automaton. To determine Θ_{i}, c_{i} considers r_{k→i},act with respect to itself. Let θ_{i→k} represent the relative angle between the headings of c_{i} and c_{k}, and let θ_{i} and θ_{k} be the angles of the relationship vectors r_{i→k,act} and r_{k→i,act}, respectively. Then:θ_{i→k} = θ_{k} – θ_{i} + 180°; [180°, 180°]  (Eq. 14)  
Θ_{i} = Θ_{k} + θ_{i→k}; [180°, 180°]  (Eq. 15) 
Note that when θ_{i→k} = 0°, both i and k have the same global heading. The same holds true for every robot in the formation if Θ_{i} = 0° for all i. This property of the algorithm to yield an emergent global heading is essential for any subsequent teleoperation from an operator. If a translational movement command is given, the common heading of the robots allows for a smooth transition in the same direction.
Translational error
. The appropriate translational movement for each robot represented in the automaton is determined by an accumulation of error with both x and ycomponents. This error is determined by the difference in desired and actual relationships of reference cell c_{k}. One major consideration is that many of the robots are, themselves, correcting for translational and rotational errors while they are being referenced by other robots. Changes in the orientation of c_{k} can cause rather entropic behavior in c_{i}, which depends on it for motion control. To alleviate this problem, r_{k→i,des} must be rotated, accounting for the propagated rotational error Θ_{k} within the automaton. Let r_{k→i,des}′ denote r_{k→i,des} rotated by an angle –Θ_{k}; γ_{i} can be expressed as the translational error of c_{i} with respect to c_{k}:γ_{i} = Γ_{k} + r_{k→i,des}′ – r_{k→i,act}  (Eq. 16) 
The Γ_{k} term represents the accumulation of error from c_{k}. Recall that θ_{i→k} relates the headings of both of these robots, providing a conversion between the relative coordinate systems of c_{i} and c_{k}. Thus, rotating γ_{i} by –θ_{i→k} yields the translational error Γ_{i}.
Formation Manipulation
To show the dynamic switching capabilities of the algorithm, a human operator can send a variety of commands to the seed cell, thus, propagating changes in the automaton and causing a chain reaction in neighboring cells, which then change states accordingly, resulting in a global transformation of the formation.
Formation translation
A translation command Ψ (with both x and y components) moves the robots relative to the current formationrelative orientation Φ. [Fig 17]. This is done by “tricking” the cells and taking advantage of the motion control system as defined above; simply add Ψ to the current translational error of the seed, and the error will be propagated:
Γ_{seed} = Γ_{seed} + Ψ  (Eq. 17) 
Formation rotation
A formation rotation command Ω causes a change in the orientation of the formation as a whole, thus, requiring each robot to move in such a way as to maintain the shape as it is rotated [Fig. 18]. Taking advantage, again, of the motion control system, the rotational error of the seed Θ_{seed} is simply rotated by Ω:
Θ_{seed} = Θ_{seed} + Ω; [–180°, 180°]  (Eq. 18) 
Cell rotation
A cell rotation command φ modifies the orientation of each cell relative to the formation; this contrasts to the formation rotation command in that the position and orientation of the formation itself relative to an external frame of reference remain unchanged [Fig. 19]. To do this, the seed cell prepares to perform a rotation in a similar way to that of a formation rotation command; it rotates Θ_{seed} by φ. To prevent the entire formation from moving, it also rotates the formationrelative orientation Φ by this amount in the opposite direction and recalculates its desired relationships; this instigates a change in relationships through all cells in the automaton:
Formation scaling
A scaling command z stretches each of the desired relationships of c_{i} by the given scalar [Fig. 20]. For every neighbor c_{j}:
r_{i→j,des} = z × r_{i→j,des}  (Eq. 21) 
Formation resizing
A resizing command Z multiplies R (the distance that neighboring robots should stay apart) by this factor [Fig. 21]. This command is similar to the scaling command, but differs in that desired relationships must actually be recalculated using Equations 8 & 9 instead of being directly manipulated by some scalar:
R = Z × R  (Eq. 22) 
Formation change
To change a formation, a seed cell is chosen and given the new geometric description, and the process described above is repeated [Fig. 22].
Simulator
The control algorithm was initially implemented in a simulated environment [19; Simulator Code]. The simulator was written in C++ using OpenGL, and provides an easy means to visualize, manipulate, and test the algorithm; an operator may directly manipulate any cell, relocating or reorienting it to evaluate the stability of the system in the presence of error [Fig. 23].
As before, each robot is represented as a cell c_{i}, where i is the corresponding index within the automaton; in the simulator, the automaton is stored as a 1dimensional array of n cells, where n is given at runtime. Tenstothousands of cells have been tested against various formation definitions to demonstrate the scalability and generality of the algorithm [Table 1].
f(x) = 0  
f(x) = x  
f(x) = x  
f(x) = –½ x  
f(x) = –½ x  
f(x) = –x  
f(x) = x^{2}  
f(x) = x^{3}  
f(x) = {–√x, if x < 0  else, √x}  
f(x) = 0.05 sin(10 x)  
(Note that, for all formations shown here, R = 10.5", Φ = 90.0°, p_{seed} = [ 0.0 0.0 ]^{T}.) 
The simulator makes several simplifying assumptions. First, the array of cells is updated in discrete and synchronized time intervals; this alleviates any problems of inconsistency within the automaton. Second, each neighborhood has already been established; for a cell at index i, this neighborhood consists of the cells at the left and right indexes i1 and i+1, respectively. Finally, each cell is assumed to have perfect, continuous, and unlimited sensing; thus, a cell is able to get its distance and orientation to any other cell at any point in time.
The next section discusses the physical implementation of this algorithm and how these assumptions were overcome to prove that the approach is viable in the real world.
Robot Platform
A platform was developed to test the algorithm in the physical world [20; Fig. 24]. Each robot is built upon a Scooterbot II base [www.budgetrobotics.com]. The Scooterbot is 7 inches in diameter and is crafted from expanded PVC, making it durable and light. Two modified servo motors are employed for differential steering.
Controller
The formation control algorithm is implemented in Interactive C (IC) [www.botball.org/ic] and runs on an XBCv2 microcontroller [Fig. 25; www.botball.org]. The XBC utilizes backEMF PID for accurate motor control. It also features a camera, capable of multicolor, multiblob simultaneous tracking. Rotating the robot provides a 360° view of the environment and neighboring robots.
Neighbor localization
A neighboring robot represented by c_{j} is identified by either an orange or green color band; the color of each robot is assigned based on its ID: green for even; orange for odd. The alternating of color bands reduces the chances of overlapping color blobs and improves the accuracy of detecting a neighbor.
Relative distance
. To locate c_{j}, a robot represented by c_{i} rotates until the band of the appropriate color is within its view; it then centers on that band. The heading of c_{i} is always considered to be directed at the xaxis (0°); relative to the robot, left yields positive angles and right yields negative angles. The distance d_{i→j} between c_{i} and c_{j} is determined by recognizing that the perceived vertical displacement Δy between the top and bottom of a color band is proportional to the perceived vertical displacement ΔY at a known physical distance D [Fig. 26]:d_{i→j} = D × ΔY / Δy  (Eq. 23) 
Relative orientation
. The relative orientation α_{i→j} from c_{i} to c_{j} is simply the angular displacement from the initial location (i.e., prior to the search) of c_{i}. Thus, the actual relationship vector r_{i→j,act} is written in polar coordinates as:r_{i→j,act} = [ d_{i→j} α_{i→j} ]^{T}  (Eq. 24) 
Communication
Hardware
. A radio communication module is used to share formation and state information within a robot’s neighborhood. The Digi XBee (ZigBee/IEEE 802.15.4 compliant) was chosen for its rich feature set [www.digi.com]. The module does not require a host/slave configuration, allowing for mesh networking and packet rerouting. The XBee also scales well for large applications, using 16bit addressing to provide for over 65,000 nodes. The lowpower model offers a range of 100 meters, which is equivalent to class2 Bluetooth. The chip communicates using a TTLlevel UART, while the XBC uses RS232 levels. A PCB was designed by J.R. Croxell [20] to overcome level translation and to interface between the XBee and the XBC. All parts are surface mounted, with the exception of a 9pin DSub male plug. The result is a board smaller than the XBee itself that directly plugs into the XBC’s 9pin serial port [Fig. 27].Software
. Digi offers a wide range of functionality and extensive documentation for the XBee [29]; this eased the implementation and integration of a reliable packet communication system, supporting automatic retries and acknowledgments. The communication library developed allows values of different types to easily be “packed” (queued) into a buffer for sending and “unpacked” (dequeued) from a buffer when receiving (see Communication.ic in Robot Code for details). Packets can be addressed to a particular robot or broadcast. This allows each robot to communicate locally within its neighborhood, relaying and querying formation and state information.Behaviors
The simulator made the simplifying assumption of robots updating and moving in synchronous discrete time steps. However, in the real world, one must consider that each robot will be updating and moving in asynchronous continuous time. This problem is alleviated by using a finite state representation to safely transition between a series of behaviors, while maintaining an internal counter (time step independent of system clock) of events (state updates) that have occurred [Fig. 28]. This preserves the concept of discrete time in classic cellular automata.
WAITING FOR FORMATION
. This is the initial (entrypoint) behavior of the robot. The robot will wait indefinitely until it receives a formation definition from either the operator (designating it as the seed cell in the automaton) or from a neighboring robot (queried at robot startup and/or relayed upon receiving a formation definition itself).WAITING TO UPDATE
. The robot must make certain that its neighbors are not moving or preparing to move before it updates its state, as a moving robot would make determining an instantaneous actual relationship impossible. This behavior also functions as a checkpoint for synchronizing the current time step t of a cell within its neighborhood; the entire neighborhood is synchronized when all time steps are equal. To synchronize, the time step t_{i} of the cell c_{i} is set equal to the maximum of all neighborhood time steps:This is particularly useful when introducing a new robot into the formation. At startup, its neighborhood is queried for a formation definition and, subsequently, the time step. With this information, a cell can seamlessly enter into the automaton.
UPDATING
. During the update process, the robot determines its actual relationship to each neighbor within its neighborhood (see Neighbor localization above for how this relationship is determined). The robot then calculates its translational and rotational error, increments its time step t_{i}, and finally communicates its new state s_{i}^{t} locally within its neighborhood.WAITING TO MOVE
. This behavior is similar to the WAITING TO UPDATE behavior; the robot must wait until all neighbors are done updating before moving. Once all neighbors are done updating, their time steps should all be synchronized. If an inconsistency occurs, the robot reports an error and returns to the WAITING TO UPDATE state for synchronization.MOVING
. While executing this behavior, the robot actually attempts to correct for its calculated error, translating and rotating based on its movement action A_{i}. Upon completion, the translational and rotational error are approximately 0, and the state is updated to reflect this; the time step t_{i} is incremented for this state change, and the state s_{i}^{t} is communicated to the neighbors of the cell.Implementation Results
The algorithm was implemented on a variety of different formation using twelve of these robots (shown below in different numbers with different identification bands, as these pictures were taken during the process of this thesis; see Neighbor Identification in the next section for how these robots are identified).
f(x) = 0  
f(x) = x  
f(x) = x  
f(x) = –½ x  
f(x) = –½ x  
f(x) = –x  
f(x) = ^{1}/_{64} x^{2} (16.0" focus)  
f(x) = (0.1 x)^{3}  
f(x) = {–5 √x, if x < 0  else, 5 √x}  
f(x) = 8 sin(3 x)  
(Note that, for all formations shown here, R = 24.0", Φ = 90.0°, p_{seed} = [ 0.0 0.0 ]^{T}. Also, the perspective of the camera was changed to keep seven robots in the image.) 
2Dimensional RobotSpace Cellular Automata
Goals and Objectives
Extending the formation control algorithm to be applied to SSP, the global structure of the solar reflector array could be viewed as a 2dimensional lattice of robots. In [10, 11, 19, 20, 28], the formations were setup so each robot only needed to identify two neighbors. In the reflector formation, the definition of a neighborhood becomes more complex. There are various neighborhoods defined for cellular automata, such as the von Neumann Neighborhood (four surrounding cells), Moore Neighborhood (eight surrounding cells), and the Extended Moore Neighborhood (includes cells adjoining the immediate eight surrounding cells) [23]. Landis [15] provides insight into potential physical configurations of robots for SSP and this is considered in determining the appropriate number of neighbors for a given formation [Fig. 29]. The proper neighborhood definition for the automaton is crucial because it will directly affect how each robot cell reacts, how information gets propagated through the formation, and influences the overall performance of the formation by increasing or decreasing the communication and sensing overhead.
Extending the Formation Definition
Mead et al. [19] identified the potential for different categorizations of formations (see Formation classification in the Conclusions for a preliminary analysis), including those that are defined by multiple functions. To do so, the initial formation definition F must be extended to include more than one function. Let f' be a set of M mathematical functions used to define the shape of the formation, such that F in Equation 6 can be extended:
Each function is considered individually for purposes of calculating desired relationships and, thus, generates its own 1dimensional neighborhood as before; this results in M neighborhoods. To extend Equation 2, consider a neighborhood ^{m}h_{i} for a single function f_{m}(x), where 1 ≤ m ≤ M:
^{m}h_{i} = ^{m}{c_{i1}, c_{i}, c_{i+1}}  (Eq. 28) 
The combined neighborhood can then be represented as the union of all M neighborhoods:
H_{i} = ^{1}h_{i} ∪ ^{2}h_{i} ∪ … ∪ ^{M}h_{i}  (Eq. 29) 
Note that c_{i} is unique within the automaton as a whole and is a common intersection of each neighborhood for each function; to illustrate this, H_{i} can be expanded:
H_{i} = {^{M}c_{i1}, …, ^{2}c_{i1}, ^{1}c_{i1}, c_{i}, ^{1}c_{i+1}, ^{2}c_{i+1}, …, ^{M}c_{i+1}}  (Eq. 30) 
Similar to its previous definition, any particular neighbor can be written as ^{m}c_{j}, where m refers to the function upon which j is an index to a neighboring cell. It follows that the step function S must also consider the new neighborhood for purposes of calculating the state s_{i}^{t}:
s_{i}^{t} = (^{M}s_{i1}^{t1}, …, ^{2}s_{i1}^{t1}, ^{1}s_{i1}^{t1}, s_{i}^{t1}, ^{1}s_{i+1}^{t1}, ^{2}s_{i+1}^{t1}, …, ^{M}s_{i+1}^{t1})  (Eq. 31) 
This distinction is especially important f determining the aforementioned reference neighbor c_{k}; extending Equation 13 to consider all neighbors within a neighborhood defined by multiple functions, the identity of c_{k} can still be determined. The reference neighbor c_{k} can be defined, similar to before, as the neighbor that with the minimum distance p_{k}' from p_{seed} to ^{m}p_{k}, where m refers to the function upon which k is the index to the cell to be referenced:
k  p_{k}′ = min({^{M}p_{i1} – p_{seed}, ..., ^{2}p_{i1} – p_{seed}, ^{1}p_{i1} – p_{seed}, ^{1}p_{i+1} – p_{seed}, ^{2}p_{i+1} – p_{seed}, ..., ^{M}p_{i+1} – p_{seed}})  (Eq. 32) 
Formations Defined by Multiple Functions
As an example and for purposes of SSP [15], consider a hexagonal lattice structure by defining a formation F by three functions: f_{1}(x) = 0, f_{2}(x) = x √3, and f_{3}(x) = –x √3. For c_{seed}, solving for Equations 8 and 9 for each of these functions yields a total of six desired relationships [Fig. 30].
As before, the definition and relationships are propagated to neighboring cells, which repeat the process. However, using the standard implementation of the algorithm, the resulting formation would be a sort of “sixarmed structure” [Fig. 31].
The formation of this structure is the product of the p_{i} term in Equation 8, which considers the cell c_{i} to be at position pi on some function and, in turn, affects the calculation of desired relationships in Equation 9. While this may be desirable for some applications, it deviates from the goal of a lattice. By removing the p_{i} term from Equation 8, all cells will be considered at the origin when calculating their desired relationships on all M functions:
R^{2} = v_{x}^{2} + f_{m}(v_{x})^{2}  (Eq. 33) 
Note that the p_{i} term does not leave the algorithm completely—it is still propagated within the automaton for purposes of determining the reference neighbor in Equation 31. This seemingly minor change produces significant results: cells begin to develop common neighbors as neighborhoods intersect one another; an emergent hexagonal lattice structure results [Fig. 32].
Now, consider using the functions f_{1}(x) = x and f_{2}(x) = –x to define F in order to generate a square lattice [Fig. 33].
Similarly to that of the hexagonal lattice attempt, if the standard implementation is used, a “fourarmed structure” results that was not intended (but nonetheless interesting) [Fig. 34].
However, as before, by utilizing Equation 33 for purposes of determining desired relationships, the desired lattice forms from this multifunction definition [Fig. 35].
Neighbor Identification
For a robot to determine its state, it must be able to identify its neighbors. This is easier said than done, as each unit looks identical. The problem is analogous to being in a room of people that look and dress exactly alike; if one person speaks (i.e., sends a message) without further sensory input, such as auditory localization, it is impossible to determine who was speaking. A colored barcoding system is utilized to alleviate this problem; each robot features a unique “face”—a threecolor column, where the vertical locations of the green and magenta bands (in relation to the orange band) correspond to its identification number [Fig. 36].
Relative distances are calculated as in Equation 22 using only the orange color bar at the top. However, for an orange band in a camera frame to even be considered a neighboring robot, it now must also possess a green band and a magenta band at some nearby position beneath it; based on the proportions of the size of these bands in the physical world, it is simple to tell whether or not a perceived combination of bands in a frame is valid. The identification number of the robot is determined based on the following table (note that, when the green band is above the magenta band, this number is even and vice versa):
0  1  
2  3  
4  5  
6  7  
8  9  
10  11  
12  13  
14  15  
16  17  
18  19 
While a greater number of robots could have been identified using all permutations of color combinations, requiring that all three color bands be present and that one be in a fixed position simplifies vision processing, while still providing enough unique identifiers for the number of robots implemented.
Implementation Results
This extension of the algorithm was implemented and tested on 19 “facelifted” robots (shown below in different numbers) [Table 4]. Integration with the previous implementation was seamless, as relationships are calculated for any number of functions. A flag is set to specify whether Equation 8 or Equation 33 is to be used.
f_{1}(x) = 0
f_{2}(x) = x √3 f_{3}(x) = –x √3 R = 24.0" Φ = 90.0° p_{seed} = [ 0.0 0.0 ]^{T} 

f_{1}(x) = x
f_{2}(x) = –x R = 24.0" Φ = 45.0° p_{seed} = [ 0.0 0.0 ]^{T} 