Transcript Document

Thesis Presentation:
Cellular Automata for
Control and Interactions of
Large Formations of Robots
Ross Mead
Committee:
Dr. Jerry B. Weinberg
Dr. Stephen Blythe
Dr. Xudong Yu
Outline
 Introduction and Significance
 Comparison of Cellular Automata Approaches
 1-Dimensional Robot-Space Cellular Automata
Algorithm
Implementation
 2-Dimensional Robot-Space Cellular Automata
Algorithm Extension
Implementation
 Conclusions
 Future Work
 Q&A
2
Motivation
Space Solar Power (SSP)
How can a massive collection of robots
moving with no group organization
coordinate to form a global structure?
3
Problem
swarm
formation
4
Approach
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
complex emergent behavior from simplicity
5
“World-Space” Cellular Automata
Environment is represented topologically
as a 2- or 3-dimensional grid of cells…
a) robot between grid cells
b) boundary surrounds the
automaton
c) automaton wraps along
boundaries
d) two robots collide trying
to occupy same grid cell
6
“Robot-Space” Cellular Automata
Each robot is represented as a cell ci in a
1-dimensional automaton…
 ci = {H, s, F, S}
7
“Robot-Space” Cellular Automata
Each robot is represented as a cell ci in a
1-dimensional automaton…
 ci = {H, s, F, S}
neighborhood




 C ← automaton:
C = H1 U H2 U … U Hn
= {c1, c2, …, cn}
8
Hi = {ci-1, ci, ci+1}
ci-1 ← left neighbor
ci+1 ← right neighbor
cj ← some neighbor j
“Robot-Space” Cellular Automata
Each robot is represented as a cell ci in a
1-dimensional automaton…
 ci = {H, s, F, S}
state
 si = {p, rdes, ract, Γ, Θ , t}
 ( ... described later ... )
 C ← automaton:
C = H1 U H2 U … U Hn
= {c1, c2, …, cn}
9
“Robot-Space” Cellular Automata
Each robot is represented as a cell ci in a
1-dimensional automaton…
 ci = {H, s, F, S}
state transition




 C ← automaton:
C = H1 U H2 U … U Hn
= {c1, c2, …, cn}
10
si = {p, rdes, ract, Γ, Θ , t}
( ... described later ... )
sit = S(si-1t-1, sit-1, si+1t-1)
t ← time step (counter)
“Robot-Space” Cellular Automata
Each robot is represented as a cell ci in a
1-dimensional automaton…
 ci = {H, s, F, S}
formation





 C ← automaton:
C = H1 U H2 U … U Hn
= {c1, c2, …, cn}
11
F = {f(x), R, Φ, pseed}
f(x) ← description
R ← robot separation
Φ ← relative heading
pseed ← start position
Algorithm – Formation Definition
 F is sent to some robot, designating it as the seed cell cseed...
 cseed is not a leader, but rather an initiator of the coordination process
 For purposes of calculating desired relationships, each cell ci
considers itself to be at some formation-relative position pi:
pi = [ xi
f(xi) ]T
 In the case of cseed, this position pseed is given…
f(x) = a x2
cseed
pseed
12
Algorithm – Desired Relationships
 The desired relationship ri→j,des from ci to some neighbor
cj is determined by calculating a vector v from pi to the
intersection f(vx) and a circle centered at pi with radius R:
R2 = (vx – pi,x)2 + (f(vx) – pi,y)2
ri→j,des = [ vx
f(vx) ]T
 The relationship is rotated by –Φ to account for robot heading...
f(x) = a x2
R
desired relationship
with left neighbor ci-1
–v
ri→i-1,des
+v
pseed
13
ri→i+1,des
desired relationship
with right neighbor ci+1
Algorithm – Desired Relationships
 F and ri→j,des are communicated locally within the neighborhood.
 Each neighbor cj repeats the process, but considers itself to be at
different formation-relative position pj…
 determined by the desired relationship from the sending neighbor ci
pj = pi + ri→j,des
f(x) = a x2
Note:
rj→i,des = –ri→j,des
pi-1
pseed
14
pi+1
Algorithm – Desired Relationships
 Propagate changes in neighborhoods in succession.
 Calculated relationships generate a connected graph
that yields the shape of the formation.
f(x) = a x2
15
Algorithm – Actual Relationships
 Using sensor readings, robots calculate an
actual relationship ri→j,act with each neighbor cj.
 State of Hi governs robot movement:
rotational error Θi and translational error Γi
relationships based on individual coordinate systems
16
Algorithm – Formation Manipulation
17
Algorithm – Formation Manipulation
18
Algorithm – Formation Manipulation
19
Algorithm – Formation Manipulation
20
Algorithm – Formation Manipulation
21
Algorithm – Formation Manipulation
22
Implementation – Robot Platform
ZigBee module
-packet communication
-share state information
within neighborhood
Color-coding system
-visual identification
-neighbor localization
(actual relationships)
Scooterbot II base
-strong, but very light
-differential steering system
XBCv2 microcontroller
-Interactive C
-back-EMF PID motor control
-color camera
23
Implementation – Color-Coding System
Visual identification
the color of each robot is assigned based on ID:
orange for odd, green for even
Neighbor localization (actual relationships)
ri→j,act = [ di→j
αi→j ]T
24
Implementation – State Diagram
25
Implementation – Results
... and because embedding Windows’ own
media format is a too much for PowerPoint...
[ Click Here ]
26
Extending the Formation Definition
 Consider a set f' of M mathematical functions:
F = {f', R, Φ, pseed}
f' = {f1(x), f2(x), ..., fM(x)}
f3(x) = –x √3
f2(x) = x √3
R
f1(x) = 0
1h
i
2h
i
= 2{ci-1, ci, ci+1}
3h
i
= 1{ci-1, ci, ci+1}
= 3{ci-1, ci, ci+1}
 For desired relationships, each fm(x) is considered individually...
 yielding its own 1-dimensional neighborhood mhi
 resulting in M neighborhoods and a 2-dimensional cellular automaton (M > 1)
Hi = 1hi U 2hi U ... U Mhi = {Mc1-1, …, 2c1-1, 1c1-1, c1, 1c1+1, 2c1+1, …, Mc1+1}
27
How can this be applied to SSP?
 Reflector viewed as 2-dimensional lattice of robots
and, thus, a 2-dimensional cellular automaton...
28
Multi-Function Formations
29
Multi-Function Formations
 Desired relationship: ri→j,des = [ vx
What
happened?
f(vx) ]T
 Original: R2 = (vx – pi,x)2 + (f(vx) – pi,y)2
30
Multi-Function Formations
 Desired relationship: ri→j,des = [ vx
What
happened?
f(vx) ]T
 Original: R2 = (vx – pi,x)2 + (f(vx) – pi,y)2
 Alternative: R2 = vx2 + f(vx)2
31
Multi-Function Formations
 Desired relationship: ri→j,des = [ vx
Similarly...
f(vx) ]T
 Original: R2 = (vx – pi,x)2 + (f(vx) – pi,y)2
32
Multi-Function Formations
Similarly...
 Alternative: R2 = vx2 + f(vx)2
33
Implementation – Robot Platform
34
Implementation – Robot “Faces”
Visual identification
each robot has a unique three-color column...
vertical locations of color bands correspond to ID
green on top for even, magenta on top for odd
5 locations × 4 locations = 20 unique faces
35
Implementation – Robot “Faces”
“All around me are familiar faces... ”
36
Implementation – Results
[ Click Here ]
37
Conclusions – Algorithm
 Designed and implemented a general
distributed robot formations algorithm...
able to conform to a wide variety of formations
 Robots represented as cells in multidimensional cellular automata...
simple rule sets produce complex group behavior
 Distinguishes itself as leaderless algorithm...
only communication is to instigate coordination
38
Conclusions – Robot Platform
Hardware 
Software 
 19 robots developed.
 Extensive and reusable
collection of libraries.
 Accurate motion control.
 Greatest implementation
hurdle—Interactive C...
 Reasonable execution time.






 Reliable communication.
 Robot faces were excellent!
39
most time spent debugging
workarounds—not fixes
serial library deadlock
bug list is... amusing...
imposes harsh program size
... stay away!
Conclusions – Formation Classification
I. Non-formation (swarm)
IV. Function-based formation
II. Explicit formation
V. Branching formation
III. Straight line formation
VI. Lattice formation
40
Future Work
 Dynamic neighborhoods
 3-dimensional formations
 Seed election
 Disconnected formations
 Formation repair
 Formation classification
 Obstacle avoidance
 Analysis [ Click here ]
 Global positioning
 Formation management
42
Questions?
For more information, please visit
http://roboti.cs.siue.edu/projects/formations/
or see the following papers:

Mead, R. & Weinberg, J.B. (2008). A
Distributed Control Algorithm for Robots in
Grid Formations. To appear in the
Proceedings of the Robot Competition and
Exhibition of The 23rd National Conference
on Artificial Intelligence (AAAI-08), Chicago,
Illinois.

Mead, R., Weinberg, J.B., & Croxell, J.R.
(2007). A Demonstration of a Robot
Formation Control Algorithm and Platform.
To appear in the Proceedings of the Robot
Competition and Exhibition of The 22nd
National Conference on Artificial Intelligence
(AAAI-07), Vancouver, British Columbia.

Mead, R. & Weinberg, J.B. (2008). 2Dimensional Cellular Automata Approach for
Robot Grid Formations. To appear in
Student Abstracts and Poster Program of
The 23rd National Conference on Artificial
Intelligence (AAAI-08). Chicago, Illinois.

Mead, R., Weinberg, J.B., & Croxell, J.R.
(2007). An Implementation of Robot
Formations using Local Interactions. In the
Proceedings of The 22nd National
Conference on Artificial Intelligence (AAAI07), 1889-1890. Vancouver, British
Columbia.
43