T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Mobile Robot
Probabilistic Robotics
Lecture 4
Jeong-Yean Yang
2020/10/22
1
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Question
Why Probabilistic Approach is
Different?
Change your Thinking Styles
from Examples
1
2
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Optimization
Convex hull should be exist
• Convex hull means that it is one of the local minima.
• Think that Y=x^2 has the minimum value at x=0
• In 2D problem. A = x^2 +y^2 has the minimum at x=0
and y=0
3
Local minimum
Local minimum
Review
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Gradient Descent follows
• Gradient Descent stops at minimum.
4
( )
( , )
f x y
f(x,y) = x^2+y^2
( )
( , )
f x y
Repeat
-
( )
if
then stops.
old
X
guess
X
X
f X
X
X
Review
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Gradient Descent Method, GDM
• You should learn GDM.
• Neural network is one of the example based on GDM.
• Over 80% of engineering method uses GDM.
• However, before use GDM, you should think about the
convex hull problem.
• If there is no convex hull, GDM will be diverged.
5
Review
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Differentiation-based Optimization
for Complex Function
• Local Minimum can be obtained by GDM.
• Back to 2D problem.
6
y=x(x-10)^2
x0
y=f’(x0)(x-x0)+f(x0)
0=f’(x0)(x-x0)+f(x0)
x1 - f(x0)/f’(x0)+x0
x1
y=f’(x1)(x-x1)+f(x1)
x2- f(x1)/f’(x1)+x1
….
f’(x)0
0
5
10
15
0
50
100
150
200
250
300
350
400
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Case 1) y=x(x-10)^2
• Y’ = (x-10)^2 + 2x(x-10)
• X 10
7
0
5
10
15
0
50
100
150
200
250
300
350
400
Test1.m
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Case 2) sinX + 0.5sqrt(X)
• Result
8
0
5
10
15
0
0.5
1
1.5
2
2.5
3
0
5
10
15
20
25
30
3
4
5
6
7
8
9
10
11
12
turns,k
x
x
X suddenly shifts to 11.
WHY?
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Iterative Method often OSCILLATE!
• Sin (x) is symmetric.
• Symmetric curves often generate oscillation, which
does not converge to solutions.
9
0
5
10
15
0
0.5
1
1.5
2
2.5
3
sinX + 0.5sqrt(X)
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Differentiation-based Method
is Too fast to Find a Solution
• Diff.-based Method is fast, but it becomes unstable.
• Gradient Descent Method is used alpha value,
to control convergence rate
10
x0
x1
x2
Diff-
based
Method
x0
x1
x2
Diff-
based
Method
-
( )
X
X
f X
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
How to Avoid Oscillation and
how to find global minimum?
• Hmm.. Trial and error
– Many trials with different initial guess, Xo.
– Xo = 6 fails. Xo =5 fails. Xo=2 fails.
• Fortunately, a good guess can solve problem.
11
0
5
10
15
0
0.5
1
1.5
2
2.5
3
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Random Guess can solve it?
• If there are many local minima,
– Random guess + GDM can solve problem.
• Random guess takes a lot of time.
– It is inefficient in general.
– But, random process (or perturbation) GUIDES to optimal
solution
12
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Differentiation
• Differentiation or Gradient Descent Method
– Requires Differentiation but it becomes very Large value
– Ex) dy/dx = 1/0.00001 infinite.
– Iterative method becomes UNSTABLE.
13
0=f’(x0)(x-x0)+f(x0)
x1 - f(x0)/f’(x0)+x0
1
(
)
'(
)
k
k
k
k
f x
x
x
f x
Small f’(x) generates large noise.
X becomes unstable…
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
On behalf of Differentiation,
Stochastic Searching is Stable in Every time
• Genetic algorithm.
• Think Gene for optimal agents in our environment.
• X= [x1,x2,x3,…]
• F = F(X)
• Good = sort(F)
– Crossover = average of some Good.
– Mutation = random value
• X [ Crossover, mutation]
14
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Genetic Algorithm
• Ten x is used as initials.
• Find the best one
• 4 best X is averaged.
(best1+best2)/2,
(best3+best4)/2.
Crossover
• 8 new X are randomly
chosen Mutation
15
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Human-like motion?
• We are experience in computer program.
• Everything is designed and there is no ERROR.
•
Think different!
• Which one is better?
16
Case 1
Case 2
P control
P control
+
W(noise)
Bad
For Large Noise
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Probabilistic Robotics
2
17
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Every Sense and Action are
NOT Determined.
• Senses from Sensors
• Actions with actuators
• Everything is under Probabilistic Distribution(Modeling)
18
ADC
(Analog to
Digital)
PWM
+
Driver
sense
Distance
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Gaussian Distribution
• X has Gaussian distribution with mean and deviation
19
0
10
20
30
40
50
60
70
80
90
100
-2.5
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
2.5
-2.5
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
2.5
0
5
10
15
20
25
Matlab
X=normrnd(0,1,100,1)
Plot(x)
Hist(x)
~
( , )
x
N
2
2
1
(
)
~
exp
2
2
: mean
: standard deviation
Probabilistic Density Function (PDF)
x
x
N
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
With More Samples,
• 10000 samples,
20
-4
-3
-2
-1
0
1
2
3
4
0
50
100
150
200
250
300
350
400
Test1.m
See the changes of mean and
deviation.
-4
-3
-2
-1
0
1
2
3
4
0
500
1000
1500
2000
2500
3000
3500
Mean value
Higher
deviation
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Stochastic Process in Robotics
• 1. Noise is unavoidable phenomenon
– Random process should be under consideration
– Our world is filled with Noise, but nothing in mathematics and
simulation world
Noise modeling is required
• 2. Thus, Random process is favorable in many cases.
– Random process (or perturbation) increases the possibility of
finding solution.
• 3. Random Process is bad for mathematic modeling?
– No, Prob. Modeling is possible.
– Yes, because you CANNOT use “If – then” method.
– Therefore, OPTIMIZATION is required for stochastic process 21
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Deterministic Model Vs. Stochastic Model.
• In control or some methods,
– Modeling is required.
– Something beyond modeling is curse for designers.
• Random property could be GOOD, but it is NOT
accurate.
– Optimization is required as in the case of GA problem.
• When GA is proposed, some peoples said that,
– It is NOT good method. We cannot estimate when GA will be
over.
– But, think different…….
22
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Robotics Trend is Rapidly
Shifting from Deterministic to Stochastic
• We cannot determine when GA will stop.
• Even we cannot say that it is an optimal value.
• GA has been perished.
• But,
23
solution
Deterministic
approach
Stochastic
approach
the SOLUTION lies around probabilistic condition
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
What is Stochastic Method?
• Rule 1. Stochastic or Probabilistic method does NOT
follow the exact solution.
– Maybe there will be a solution…I think so.
• Rule 2. Stochastic or Probabilistic method has some
kinds of random values.
– Thus, Stochastic method requires Optimization.
• AI has been based on deterministic method.
• Nowadays, Learning is based on Stochastic Method.
24
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Stochastic Approach
Simple Example with Case Study
3
25
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Example: Cleaning Robot
26
Why it Do Wall-Following?
1. Clean near walls
2. No sensor for map building
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Example: Cleaning Robot
27
0
1
2
Three distance
sensors 0~2
cos
cos
ˆ
sin
sin
2
1 /
1 /
L
R
x
w
r
x
y
w
a
a
Only two inputs
Random
Noise
For an actual
Environment
Strategy
How to move it
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Deterministic Strategy
• X = [x,y,q]
• Xd=[xd,yd,qd] desired value.
• Case 0) No avoidance.
– wL=wR= w0
• Case 1) Center Sensor < threshold
– Frontal obstacles.
– New target = qd = 90.
• Case 2) Right Sensor < threshold
– Right obstacles.
– New target = qd = 15.
28
90
turn
15
turn
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
“Curling” with Deterministic Method
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Slip and Wall Obstacles are
Not Determined
• Why it fails to do wall following?
• 1.Wheel slip is Not determined
– Small Errors from Wheel slips generates Bigger Errors
– Rotation with two wheel Encoders CANNOT be accurate.
• 2. Wall is the sources of Uncertainties(Noises)
– Wall is not fixed.
– Even in fixed walls, measurement errors occur
• Result: Environment is a Stochastic World
30
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Stochastic Environment for Cleaning Robots:
What We Have to Change?
• Stochastic Environment
– Everything is probabilistically determined.
– Think the distribution : X~N(mean, sigma)
• Simple rules from Deterministic ways
– 1. Go straight
– 2. If no obstacles then jump to 1.
– 3. Turn to left.
– 4. Jump to step 2.
• Even with Noise on Wheels..
– Speed of Left, Right wheel ~ N(0,1)*5
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Wheel Dynamics
32
I,
m,a
=
T
w
N
f
2
2
1)
2)
0
1
3)
2
1
2
x
y
c
ma
f
ma
W
N
I
mr
T
rf
mr
T
rf
o
2
2
2
4)
1
2
2
3
x
a
r
mr
f
mr
T
mr
T
mr
When T=const., if r then but w
𝛼
vs
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Probabilistic Process is required for
Mobile Robot rather than any other Robotics fields.
• Mobile robot depends on wheel movement.
33
I,
m,a
=
T
w
N
f
o
2
2
2
1
2
3
2
x
c
ma
mr
f
I
mr
T
rf
T
mr
mr
T
Rolling condition
In case of slip
2
2
1
2
1
2
x
c
x
x
ma
f
I
mr
T
rf
T
rma
T
mr
rma
x
a
r
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Rolling Vs. Slip
• Slip: Wheel cannot move forward
even though is NOT zero.
• Assume that
34
2
3
2
x
a
r
mr
T
Rolling condition
Slip Condition
2
1
2
x
x
ma
f
T
mr
rma
(
)
x
a
r
2
2
3
2
2
3
Roll
Roll
mr
T
T
mr
2
2
1
0
2
2
slip
slip
T
mr
T
mr
Roll
Slip
0
x
a
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Slip is one of the STRONG Noises
• Slip depends on road status, which is hardly observed
in general.
• Mobile robot moves with two wheels
– Jacobian
determines the movement in X-Y-q space.
– This assumption is also from Non-Slip(Rolling) condition.
• Therefore, mobile robot is always being biased by Slip
noise.
• How can we solve this?
– Localization(SLAM) is an alternative way.
– On the other hand, is there a good approach?....
Stochastic approach.
35
dX
Jd
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Moving in a straight line is IMPOSSIBLE
in a Stochastic World
• Is it possible?
– Actually, 0.2* N(0,1) noise is applied
36
W=(wl,wr)=(1,1)
W=(wl,wr)=(5,5)
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Example: Roomba
Question 1
Why does it do spiral
motion?
Question 2
After bumping, why it
starts to turn to left?
It does not look so
useful.
Spiral motion has been known that
It is efficient way for a cleaning robot can cover larger area.
Yes, it is. However, I think that a Roomba took a very Tactical method in a stochastic
world.
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Mobile Robot CANNOT follow
Straight line without SLAM.
• iRobot takes excellent strategy from my observation.
• If it surely cannot move on straight line,
– Take the strategy of rotation Turn to Right (Spiral motion)
– Also, Spiral motion can find a space.
: Answer to 1st question.
• How to search walls or avoid obstacles?
– Turn to Right will find a space.
– Then, turn to left will avoid obstacles.
– Walls will be on right side.
: Answer to 2nd question.
• Basically, two approaches are thought in stochastic
thinking.
38
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Modeling for Two Approaches
in Stochastic World.
• 1.Go Straight Turning Right for Spiral motion
• 2.Turn Left Look for empty space
for wall following
Left
Right
Deterministic
Left
Right
Stochastic
VL~N(m+e,1), VR~N(m,1)
Left
Right
Deterministic
Left
Right
Stochastic
0
0
+
+
Proportional to
Error
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Stochastic Strategy for Cleaning Robot
• 1. Easy to Programming
– Everything is considered under Distribution
– Mean, Variance is the Parameter for everything.
• 2. Keeping a robot in Desired Margin
– In the case of Trajectories, a robot should tracks within a
specified marginal area
Margins
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
• Strategy
– WL > WR
– It will turn to right direction
• Environment has
probabilistic noises, too.
• WL~N( m+offset, s)
• WR~N(m,s)
41
Moving in a Straight Line is Not Possible.
Then, Do a Circular Motion
Left
Right
Stochastic
VL~N(m+e,1), VR~N(m,1)
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Example: Circular or Spiral Motion
• Left: WL > WR failed for spiral motion
• Right: We need another parameterization for spiral motion
•
Exponential function is added
42
Only VL > VR for circular motion
VL = v0 + exp(-at)
VR = v0 – exp(-at)
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Parameterization:
Generally, complex problem is simplified
with some parameters.
• New strategy
• t increases, WL =WR
• So, a mobile robot starts to “go forward” motion as
in the case of Roomba
• Thus, 1st generation Roomba set the room size.
– Think that room size is proportional to
• Parameter, can control spiral trajectory
43
0
0
exp(
)
exp(
)
L
R
w
w
t
w
w
t
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Wall following
• 1. Spiral motion should be Wall Detection
– Movement for a Right Open Space
• 2. If a robot detect a wall, make a Left Open Space
– A.First, Left Backward moving
– B.Then, a robot find a Left Open Space (by Backward + Left turn)
– C. Do Spiral motion.
44
Only Rotation?
It often fails.
1
1
2
2A
2B
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Wall Following
-150
-100
-50
0
50
100
150
-150
-100
-50
0
50
100
150
x
y
Only Unbalanced
Perturbations
error
wall
1. Go straight with R=V0, L = V0+e
2. If no obstacles then jump to 1.
3. Turn to left with Perturbation
4. Jump to step 2.
if Distance of Right > e then
R = V0, L = Vo+e*K. ( K>>1)
Following Walls
-150
-100
-50
0
50
100
150
-150
-100
-50
0
50
100
150
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Over Bumping …
Double Threshold Instead of Steering Control
• Steering Control for Keeping Distance Error
– Sensor Noise is too High and Expensive method.
• Double Threshold
– if Distance of Right > e then
–
R = V0, L = Vo+e*K. ( K>>1)
– if Distance of Right < e2 then
–
R = V0+e’ , L = V0
error
wall
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Double Threshold Strategy
Following Walls
: Much bumping
Double Threshold
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Experimental Results
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Can you Feel the Difference
between
Deterministic and Stochastic
Approaches?
49
• Deterministic method tries to design a model
– World will work as we thought
– If World does not work as you think, you have to change
your model
• Stochastic method think a world as non deterministic
– A world will work PROBABLY.
– A world will work as one of my thinking, which depends on
probabilistic distribution.
