Transcript iasted2008 - Systems and Computer Engineering

A Practical Approach to Robotic
Swarms
IASTED Conference on Control and Applications
May 2008
Howard M. Schwartz and Sidney N. Givigi Jr.
Objectives
Develop a practical approach to robotic swarms.
Must be easy to implement and tractable.
Must appeal to the control engineer’s sense of performance.
Slide Name
Literature Review
 Olfati-Saber, R., “Flocking for Multi-Agent Dynamic Systems: Algorithms
and Theory”, IEEE Trans. Auto. Contr. 2006.
 Tanner, H.G., Jadbabaie, A., and Pappas G.J., “Stable Flocking of Mobile
Agents, Part I: Fixed Topology”, Proc. of CDC, 2003.
– These methods require one design an attraction and repulsive function. Designing this function
is not clear. Loss of control engineers intuition. Is the system working correctly?
Slide Name
Our Method
 We use an inertial model
xi  Fxi
yi  Fyi
• Define Connected and Unconnected Sets

G  j  V : q

 r , j  i
N i  j  V : q j  qi  r , j  i
i
Slide Name
j
 qi
Connected
Unconnected
The Forces on the Robots
 The force on unconnected robots is a type of gravity force.
g ij 
kg
rij
2
Where,
ij
 ij
is the unit vector from i to j
And rij is the distance from i to j
• The force on the connected robots is a type of spring damper force


f ij  k p rij  d 0 ij  kv (qi  q j ) ij ij
• The total force on a given robot is
Fi 
Slide Name
g   f
jGi
ij
jN i
ij
Simulation Results
 20 Robots, 100x100 grid, kp=4, kv=4, d0=10, kg=100, and r=12.
Slide Name
Swarming with obstacle avoidance
 Define a potential field.
e ( xi  x0 )
Pf  
 0
2
 ( yi  y 0 ) 2

 qi  p f  d f
otherwise
• Forces act along negative gradient of field
 fx  k f sgn xi  x0 Pf
 fy  k f sgn  yi  y0 Pf
• Then the complete force acting on each robot is
Fi 
Slide Name
g   f
jGi
ij
jN i
ij
 f
Simulation of robots swarming with obstacle avoidance
 kf = 200 all other terms are the same as before.
Slide Name
Swarm robots with constant motion and obstacle avoidance.
 Define specified velocity vxd = 1.0, then the force becomes,
Fix 
Slide Name
g
jGi
ijx
  f ijx   fx  kvd (vxd  xi )
jNi
Stability Analysis
 Why does this work.
~
x   0
  
 v1    k p
v2   k p
  
Substituting for kv = 4 and kp = 4, we get the
eigenvalues, λ1= -1.17, λ2 = -6.82, λ3 = 0.
Slide Name
1
 kv
kv
1  ~
x

kv   v1 
 kv  v2 
Stability of 3 Connected Robots
 Linearize for small motions about the equilibrium point.
r13   cos(600 )x1  sin( 600 )y1  cos(600 )x3  sin( 600 )y3
The force on robot 1 due to robot 3 due to small
motions is,



F13  k pr1313  kv (v13  13 )  13
The force in the x direction then becomes,
F13x  k p c 2x1  k p scy1  k p c 2x3  k p scy3
 kv c 2x1  kv scy1  kv c 2x3  kv scy 3
Slide Name
Stability of 3 robots
 The acceleration of robot i in the x direction is,
x 
F
jNi
ijx
In the case of 3 connected robots we have 12 states
and we can write the linearized equations in the form
x  Ax
0 I 
2 n4 n
where, A  
,
where
A

R
,
0

 A0 
the eigenvalue s of A are 6 rigid body zeros,
1,2  4.73, 3, 4  1.23, 5  10.9, 6  1.10
Slide Name
Stability of 20 Robots
Using a computer to evaluate the configuration and recognizing only
3 distinct relationships between robots, we get the following
maximum and minimum eigenvalues for the linearized system,
λmax = -19.86, λmin = -0.12±0.47j
Therefore the origin is asymptotically stable.
Slide Name
Experimental Results
 The robots are given positions over bluetooth link.
 The robots are controlled by a HC11 Handyboard.
 Web cameras installed in the ceiling track the robots.
Slide Name
Robots Following each other and doing obstacle avoidance
Slide Name
Conclusion
Practical approach to swarm robots
– Connected and unconnected sets, gravity and spring/damper forces
• Potential fields define obstacles
• The swarm is locally stable
• Experimental results validate the method.
Slide Name