Transcript Document

Fault-Tolerant Formations
of Mobile Robots
Ross Mead
CS Dept., University of Southern California, USA
Rob Long
Jerry B. Weinberg
Dept. of CS, Southern Illinois University Edwardsville, USA
Outline
 Problem Statement
 Considerations
 Approach
 Algorithm
 Implementation
 Evaluation
 Conclusions
 Future Work
 Q&A
2
Problem Statement
 How can a large collection of robots moving with no
group organization coordinate to form a global structure?
swarm
formation
3
Considerations
 In related work on formations, robotic units know…
 where they belong in the formation
 who their neighbors are supposed to be
 Criteria of Fredslund & Matarić 2002:
 generality – conforming to a variety of formations
 stability – maintaining the formation
 dynamic switching capability – responding to commands for
changes in its organization
 robustness/scalability – responding to changes in group size
 obstacle avoidance – dealing with large and small obstructions
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
state transitions governed by a set of rules
complex emergent behavior from simplicity
5
“Robot-Space” Cellular Automata
Each robot in the formation is represented
as a cell ci in an n-dimensional automaton
of N cells…
 ci = {hi, si, F, S}
6
“Robot-Space” Cellular Automata
Each robot in the formation is represented
as a cell ci in an n-dimensional automaton
of N cells…
 ci = {hi, si, F, S}
neighborhood
 hi = ci U { n neighbors }
 n ≤ nmax
 C ← automaton:
C = h1 U h2 U … U hN
= {c1, c2, …, cN}
7
“Robot-Space” Cellular Automata
Each robot in the formation is represented
as a cell ci in an n-dimensional automaton
of N cells…
 ci = {hi, si, F, S}
state
 si = {pi, ri,des, ri,act, Γi, Θi, ti}
 (... described later ...)
 C ← automaton:
C = h1 U h2 U … U hN
= {c1, c2, …, cN}
8
“Robot-Space” Cellular Automata
Each robot in the formation is represented
as a cell ci in an n-dimensional automaton
of N cells…
 ci = {hi, si, F, S}
state transition




 C ← automaton:
C = h1 U h2 U … U hN
= {c1, c2, …, cN}
9
si = {pi, ri,des, ri,act, Γi, Θi, ti}
(... described later ...)
sit = S(... si-1t-1, sit-1, si+1t-1 ...)
t ← time step (counter)
“Robot-Space” Cellular Automata
Each robot in the formation is represented
as a cell ci in an n-dimensional automaton
of N cells…
 ci = {hi, si, F, S}
formation





 C ← automaton:
C = h1 U h2 U … U hN
= {c1, c2, …, cN}
10
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
11
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
 Relationships are rotated by –Φ to account for robot heading...
f(x) = a x2
R
–v
desired relationship
with left neighbor ci-1
+v
pseed
ri→i-1,des
ri→i+1,des
12
desired relationship
with right neighbor ci+1
Algorithm – Desired Relationships
 The desired relationship ri→j,des from ci to some neighbor
cj produces a unique formation-relative position pj:
rj→i,des = –ri→j,des
(for stability)
pj = pi + ri→j,des
f(x) = a x2
pi-1
pseed
ri→i-1,des
pi+1
ri→i+1,des
13
Algorithm – Desired Relationships
 ci announces an auction for pj–denoted A(pj)–iff:
||pi – pseed|| < ||pj – pseed||
(for densest packing)
Γi ≈ 0
(for stability)
f(x) = a x2
pi-1
pseed
14
pi+1
Algorithm – Desired Relationships
 A robot that receives an auction message for pj will
announce a bid B(pj) iff n = 0 (i.e., it has no neighborhood
and, thus, is not yet part of the automaton) or:
pj is closer to pseed
(for densest packing)
n < nmax
(for repair)
f(x) = a x2
pi-1
pseed
15
pi+1
Algorithm – Desired Relationships
 A robot that receives an auction message for pj will
announce a bid B(pj):
B(pj) = E d + X n
 d ← distance from robot to pj (weighted by energy cost modifier E)
 n ← number of existing neighbors (weighted by relation cost modifier X)
f(x) = a x2
pi-1
pseed
16
pi+1
Algorithm – Desired Relationships
 After a period of time, ci announces the winning bidder based on the
minimum bid B(pj)…
 F and ri→j,des are communicated locally within the neighborhood.
 Each neighbor cj repeats the process, but considers itself to be at its
own unique formation-relative position pj.
f(x) = a x2
pi-1
pseed
17
pi+1
Algorithm – Desired Relationships
 Propagate changes in neighborhoods in succession.
 Calculated relationships generate a connected graph
that produces the shape of the formation.
f(x) = a x2
18
Algorithm – Actual Relationships
 Using sensor readings, robots calculate an
actual relationship ri→j,act with each neighbor cj.
 State of all cells in hi governs robot movement:
rotational error Θi and translational error Γi
relationships based on relative coordinate systems
19
Algorithm – Extended Definition
20
Algorithm – Extended Definition
21
Implementation
22
Evaluation – Generality
The generality of a system refers to its
ability to conform to a variety of different
formations.
Analysis from various trials and
experiments has suggested a
classification of the formations that can
currently be produced…
23
Evaluation – Generality
I. Non-formation (swarm)
IV. Function-based formation
II. Explicit formation
V. Branching formation
III. Straight line formation
VI. Lattice formation
24
Evaluation – Stability
A system’s ability to maintain formation
(once established) dictates its stability.
To test the control algorithm against this
principle, we manipulated one or many
robots in a variety of different formations,
changing both position and orientation…
25
Evaluation – Dynamic Switching
 Dynamic switching capabilities refer to the ability of the
system to respond to an operator’s commands for
changes in formation organization.
 To manipulate the formation, a human operator sends
one of a variety of commands to any single robot…
 propagates changes in the automaton
 causes a chain reaction in neighbors
 results in a global transformation
26
Evaluation – Robustness/Scalability
 Evaluating robustness/scalability considers the ability of
a system to respond to changes in group size.
 Algorithm is independent of the number of robots.
 Robots can be reassigned to new tasks or exhibit failure.
 As numbers begin to dwindle or the task changes, other
robots may join the ranks to increase the numbers.
27
Evaluation – Robustness/Scalability
28
Conclusions
 Presented a distributed cellular automatabased formation control architecture capable
of controlling large numbers of robots.
 Discussed a distributed auctioning method to
allow robot formation to reconfigure
autonomously.
 Examined the architecture with respect to
necessary characteristics to handle realworld events.
29
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.
30