In 2000, NSF and NASA met to discuss harvesting solar power in space to help meet future energy needs. One solution that received considerable attention was the use of robots to form a solar reflector. Imagine a space shuttle arriving in orbit, its bay doors opening, and a collection of thousands of individual robots, each with a piece of the reflector attached to them, float out into space. These robots then navigate themselves to form a large parabolic structure, which is then used to harvest solar energy. How can this swarm, or massive collection that moves with no group organization, coordinate to form an organized, global structure, or formation? Once organized, how can this formation be effectively controlled?

In previous work, I treated robots as cells in a 1-dimensional cellular automaton. Each robot “cell state” consists of its distance and orientation in 2-dimensional space in relation to neighboring robots. Using a reactive control architecture, these robots are able to establish and maintain formations defined by a single mathematical function. The viability of this approach was demonstrated in simulation with thousands of robots and on a physical platform with twelve custom robots. In order to attain formations necessary for applications such as the solar reflector, the algorithm must be generalized to 2- and 3-dimensional cellular automata. I now extend the algorithm to show how it can be generalized to 2-dimensional grid formations defined by multiple functions in order for form grid structures.

Site Map


List of Figures

  1. An Illustration of Space Solar Power.
  2. The Suntower (Left) and the SolarDisc (Right).
  3. Robotic Highway Safety Markers.
  4. The “Sense-Plan-Act” Paradigm.
  5. The “Sense-Act” Paradigm.
  6. Flock of Birds Demonstrating Swarm-Like Behavior. Note the Lack of Organization.
  7. Flock of Geese in Formation.
  8. Marching Band Formation, Demonstrating and Maintaining Well-Defined Organization.
  9. Three SPHERES Satellites Maintain Formation by Keeping their Tethers Taut.
  10. Independent “Swarm-Bots” (Indicated by Blue Lights; Left) Connect with Others (Indicated by Red Lights; Right).
  11. An Overhead View of 4 Mobile Robots Traveling in a Diamond Formation.
  12. Illustrates Various Limitations of 2-dimensional World-Space Cellular Automata: (a) Robot is between Grid Cells; (b) Boundary Surrounds the Automaton; (c) Automaton Wraps along Boundaries; (d) Two Robots Collide while Trying to Occupy the Same Grid Cell.
  13. Robots as Cells in a 1-Dimensional Robot-Space Cellular Automaton.
  14. Eleven Robots in a Parabolic Formation.
  15. ci Calculates the Desired Relationships to its Neighbors.
  16. Calculated Relationships between Robots Generate a Parabolic Formation.
  17. Translation Command Sent to a Seed Cell Moves Formation Forward.
  18. Formation Rotation Command Sent to a Seed Cell Rotates Entire Formation.
  19. Cell Rotation Command Sent to a Seed Cell Rotates Cells Individually; Formation Itself Appears Fixed in Place.
  20. Scaling Command Sent to a Seed Cell Stretches Desired Relationships of Cells.
  21. Resizing Command Sent to a Seed Cell Changes Cell Interval in the Formation.
  22. Formation Change Command Sent to a Seed Cell Causes a Global Transformation; Pictured Here Transforming from f(x) = a x2 (Parabola) to f(x) = 0 (Line).
  23. Simulated Robots Change Formation from f(x) = x2 (Parabola) to f(x) = 0.05 sin(10 x) (Sine Curve); Pictured at Four Time Steps.
  24. The Robot Platform.
  25. XBC Microcontroller.
  26. ci Identifies and Determines its Distance to cj.
  27. XBee Wireless Communication Module.
  28. Finite State Diagram of Robot Operation.
  29. Potential Arrangement of Robotic Units to Form a Tight Lattice Structure.
  30. A Formation Defined by Three Functions Yields Six Relationships.
  31. A Three-Function Formation Definition Generates a Sort of “Six-Armed Structure”.
  32. A Three-Function Formation Definition Produces a Hexagonal Lattice Structure.
  33. A Formation Defined by Two Functions Yields Four Relationships.
  34. A Two-Function Formation Definition Generates a Sort of “Four-Armed Structure”.
  35. A Two-Function Formation Definition Produces a Hexagonal Lattice Structure.
  36. ci Identifies the “Face” of cj and Determines its Relative Distance.
  37. A Formation Definition Yields Erroneous Relationships.
  38. Demonstrates Ability to Create and Maintain Different Formations: (a) Line, (b) Wedge, (c) Column, and (d) Diamond.
  39. An Operator Sketches Movement Commands to a Formation of Three Robots to Move Forward (Left) and Strafe Right (Right).

List of Tables

  1. Simulated Function-Based Formations (33 Cells)
  2. Implemented Function-Based Formations (7 Robots)
  3. Robot Faces
  4. Implemented Lattice Formations