siu

A Platform for Local Interactions between Robots in Large Formations: 

A Platform for Local Interactions between Robots in Large Formations Ross Mead Jerry B. Weinberg Jeffrey R. Croxell

Motivation: 

Motivation Space Solar Power (SSP) large solar reflector panel in space diameter: ~16.5 km (~10mi) focus concentrated beam of solar energy diverted to an energy plant on Earth for harvesting

Motivation: 

Motivation One solution that received considerable attention was the use of robots to form a solar reflector. Imagine the space shuttle releasing thousands of robots, each with a piece of reflector attached to them. These robots then navigate themselves to form a large parabolic structure resembling a reflector, which is then used to harvest solar energy.

Motivation  Problem: 

Motivation  Problem How can a massive collection of robots… ~33,000 required for SSP (Landis 2004) … moving with no group organization… swarm … coordinate to form a global structure? formation

Problem: 

Problem swarm formation

Background: 

Background Fredslund & Mataric 2002 Balch & Arkin 1998 Reynolds 1987 Farritor & Goddard 2004

Background & Goals: 

Background & Goals In related work on formations, units know… where they belong in the formation who their neighbors are supposed to be Goals: generality – conforming to a variety of formations stability – maintaining the formation robustness – responding to changes in group size dynamic switching capability – responding to commands for changes in its organization

Background: 

Background This approach to the autonomous control of creating and maintaining multi-robot formations is similar to work done in coordinating formations of Earth-bound, mobile robots. Fredslund & Mataric 2002 Balch & Arkin 1998 This work has been inspired by biological or organizational systems, such as geese flying in formation.

Background: 

Background A variety of work has also been done to apply reactive control structures to create emergent group behaviors. Flocking algorithms have been used for both physical and simulated robots. Ando, et al 1995 A digital hormone model, inspired by biological cell interaction, has also been proposed for robotic organization Shen, et al 2004

Background: 

Background Robot formations have been applied to applications such as automated traffic cones. Farritor & Goddard 2004 Swarm behavior control has been applied to urban search-and-rescue robotics. Tejada, et al 2003

Formation Control: 

Formation Control Utilize reactive robot control strategies closely couple sensor input to actions Treat the formation as a cellular automaton lattice of computational units (cells) each cell is in one of a given set of states governed by a set of rules

Formation Control: 

Formation Control A command that indicates the geometric formation is sent to a seed robot The formation then transforms as robots… react to changes in their neighbors attain their calculated relationships based on the formation definition

Formation Control: 

Formation Control

Formation Control: 

A desired formation, F, is defined as a geometric description… i.e., mathematical function F ← y = ax2, where a is some constant Formation Control

Formation Control: 

A robot is chosen as the seed, or starting point, of the formation. Formation Control F ← y = ax2

Formation Control: 

Formation Control The desired location on the formation is determined by calculating a relationship vector from c,… where c is the formation-relative position (xi, yi) of the robot, … and the intersection of the function F and a circle centered at c with radius r, where r is the distance to maintain between neighbors in the formation. c ← (xi, yi) r2 ← (x-cx)2 + (y-cy)2 F ← y = ax2

Formation Control: 

Relationships and states are communicated locally to robots in the seed’s neighborhood, which propagates changes in each robot’s neighborhood in succession. Using sensor readings, robots attempt to acquire and maintain the calculated relationship with their neighbors. Formation Control c ← (xi, yi) r2 ← (x-cx)2 + (y-cy)2 F ← y = ax2 r r

Formation Control: 

c ← (xi, yi) r2 ← (x-cx)2 + (y-cy)2 Despite only local communication, the calculated relationships between neighbors results in the overall organization of the desired global structure. Formation Control F ← y = ax2

Formation Control: 

Thus, it follows that a movement command sent to a single robot would cause a chain reaction in neighboring robots, which then change states accordingly, resulting in a global transformation. Formation Control

Formation Control: 

Formation Control

Formation Control: 

Formation Control Likewise, to change a formation, a seed robot is simply given the new geometric description, and the process is repeated.

Results: 

Results A proof-of-concept of the formation control algorithm was successfully demonstrated in a simulated environment at AAAI-06. We have developed a robot platform to assess the algorithm in the physical world.

Robot Platform: 

Robot Platform Each robot features: a Scooterbot II base differential steering system an XBC v2 microcontroller executes formation control algorithm a color-coding system and color camera visual identification and tracking of neighbors an XBee radio communication module sharing information within a robot’s neighborhood

Robot Platform: 

Robot Platform Scooterbot II base precision cut double-decker base rigid expanded PVC strong, but very light 2" risers for additional decks differential steering system http://www.budgetrobotics.com/

Robot Platform: 

Robot Platform Differential steering two modified R/C servo motors with 2 1/2" diameter rubber wheels if motors are operated at same speed, the robot goes straight if motors are operated at different speeds, the robot turns or spins

Robot Platform: 

Robot Platform XBC v2 microcontroller executes formation algorithm back-EMF PID motor control fast charging ~1 hour to fully charge http://www.botball.org/

Robot Platform: 

Robot Platform Color-coding system visual identification and tracking of neighbors Color camera multi-color, multi-blob simultaneous color tracking

Robot Platform: 

Robot Platform Color camera multi-color, multi-blob simultaneous color tracking Color-coding system visual identification and tracking of neighbors

Robot Platform: 

Robot Platform XBee radio communication module sharing state information within a robot’s neighborhood ZigBee/IEEE 802.15.4 specification up to 65,535 nodes on a network support for multiple network topologies low duty cycle  long battery life collision avoidance retries and acknowledgements link quality indication 128-bit AES encryption http://www.maxstream.net/

Robot Platform: 

Robot Platform XBee radio communication module share information within a robot’s neighborhood ZigBee/IEEE 802.15.4 specification 300’ (100m) line-of-sight range peer-to-peer, point-to-point, point-to-multipoint and mesh network topologies retries & acknowledgements for error handling 65,535 network addresses for each channel http://www.maxstream.net/

Robot Platform: 

Robot Platform Simple, light, and inexpensive… reproduction of each unit is easy and affordable A successful implementation of the algorithm on a modest number of physical robots will prove that the approach is viable in the real world.

Future Work – Formation Management: 

Future Work – Formation Management Develop a graphical user interface to provide a human operator with… a visualization of the formation information on each individual robot unit

Future Work – Dynamic Neighborhoods: 

Future Work – Dynamic Neighborhoods Implement an auction-based method to determine neighborhoods dynamically… a robot is chosen to be a neighbor based on its distance to the desired location in the formation

Future Work – Formation Classification: 

Future Work – Formation Classification Classify different types of formations… those defined by multiple functions those that generate erroneous neighbors

Future Work – Formation Classification: 

Future Work – Formation Classification

Future Work – Formation Classification: 

Future Work – Formation Classification

Future Work – Formation Classification: 

Future Work – Formation Classification

References: 

References Balch, T. & Arkin R. 1998. “Behavior-based Formation Control for Multi-robot Teams” IEEE Transactions on Robotics and Automation, 14(6), pp. 926-939. Bekey G., Bekey, I., Criswell D., Friedman G., Greenwood D., Miller D., & Will P. 2000. “Final Report of the NSF-NASA Workshop on Autonomous Construction and Manufacturing for Space Electrical Power Systems”, 4-7 April, Arlington, Virginia. Farritor, S.M., & Goddard, S. 2004. “Intelligent Highway Safety Markers”, IEEE Intelligent Systems, 19(6), pp. 8-11. Fredslund J., & Mataric, M.J. 2002. “Robots in Formation Using Local Information”, The 7th International Conference on Intelligent Autonomous Systems, Marina del Rey, California. Reynolds, C.W. 1987. “Flocks, Herds, and Schools: A Distributed Behavioral Model, in Computer Graphics”, 21(4) SIGGRAPH ’87 Conference Proceedings, pages 25-34. Tejada S., Cristina A., Goodwyne P., Normand E., O’Hara R., & Tarapore, S. 2003. “Virtual Synergy: A Human-Robot Interface for Urban Search and Rescue”. In the Proceedings of the AAAI 2003 Robot Competition, Acapulco, Mexico.

Questions?: 

Questions? For more information, visit the exhibition or http://roboti.cs.siue.edu/projects/formations/