ME5751�Robotics Motion Planning

Yizhe Chang chang@cpp.edu

Lecture Note Set #15-16

​

Outline

• Probability and Conditional Probability
• Bayes Rule
• Self-study: Gaussian Mixture Model
• Markov Chain
• Hidden Markov model
• Using HMM: Markov Localization

​

​

People

Andrey Andreyevich Markov (1856–1922)

Russian Mathematician

Professor, Saint Petersburg State University

Thomas Bayes (1701- 1761)

English statistician, philosopher and Presbyterian minister

One known mathematics publication

Bayes’ Theorem was presented after his death by Richard Price

Richard Price (1723-1791)

British moral philosopher, nonconformist preacher and mathematician

Formally described Bayes’ theorem Considered Bayes’ theorem helped prove the existence of God

Image from Wikipedia.org

Basic concept

Basic concept

Basic concept

Joint distribution

Conditional probability

Conditional probability: example

• In a group of 100 sports car buyers,
• 40 bought alarm systems,
• 30 purchased bucket seats,
• and 20 purchased an alarm system and bucket seats.
• If a car buyer chosen at random bought an alarm system, what is the probability they also bought bucket seats?

​

​

Conditional probability: example

• In a group of 100 sports car buyers,
• 40 bought alarm systems,
• 30 purchased bucket seats,
• and 20 purchased an alarm system and bucket seats.
• If a car buyer chosen at random bought an alarm system, what is the probability they also bought bucket seats?

​

​

example from: https://www.statisticshowto.datasciencecentral.com/what-is-conditional-probability/

Conditional probability

Conditional probability

• We throw two dices in a sequence
• probability of first throw P(A=5) to get 5?
• probability of second throw to get 5, given first throw is 5? P(B=5|A=5)
• Your intuition answer is?

​

Conditional probability

Theorem of total probability

Bayes rule

Bayes rule

• Bayes rule relate conditional probability p(x|y) to its inverse p(y|x)

​

Bayes rule example

• In brushfire prevention
• Dangerous fire is rare P(X=Fire)=0.01
• Smoke observation is common P(Y=Smoke)=0.1, (because people make barbecue…)
• Chance of smoke is timely observed when dangerous fire happen: P(Y=Smoke|X=Fire)=0.9
• What is the probability of having dangerous fire, when we observed observe smoke? P(X=Fire|Y=Smoke)?

​

Bayes rule example

Bayes rule example

• You are planning a picnic today, but the morning is cloudy
• We go to whether department, 50% rain starts with a cloudy moring: P(Cloudy|Rain) =0.5
• We ask our grandma: P(Cloudy) = 0.4
• We checked climate book, in this “dry” month: P(Rain) = 0.1
• What is the probability of rain today? P(Rain|Cloudy)

Bayes rule example: Evidence not clear

•  Suppose that we have two bags each containing black and white balls.
• Bag A contains three times as many white balls as blacks.
• Bag B contains three times as many black balls as white.
• Suppose we choose one of these bags at random.
• For this bag we draw five balls randomly; we put the ball back after drawing. The result is that we find 4 white balls and one black.
• What is the probability that we were using bag A (mainly white balls?)

​

Bayes rule example: Evidence not clear

Bayes rule example: Evidence not clear

Evidence not needed: normalization

Evidence not needed: normalization

Outline

• Probability and Conditional Probability
• Bayes Rule
• Self-study: Gaussian Mixture Model
• Markov Chain
• Hidden Markov model
• Using HMM: Markov Localization

​

​

Gaussian mixture model

μ = 3, σ = 2

μ = 4, σ = 3

??

Gaussian mixture model

Gaussian mixture model

μ = 3, σ = 2

μ = 4, σ = 3

??

Gaussian mixture model

Gaussian mixture model

• More resources at:
• https://www.geeksforgeeks.org/gaussian-mixture-model/

​

Outline

• Probability and Conditional Probability
• Bayes Rule
• Self-study: Gaussian Mixture Model
• Markov Chain
• Hidden Markov model
• Using HMM: Markov Localization

​

​

Bayes rule

• Bayes rule relate conditional probability p(x|y) to its inverse p(y|x)

​

Markov Chain 101

• Suppose the weather can be rainy and sunny, the following diagram depicts the transition from one day to another:
• A - Rainy
• B - Sunny

​

• What does this diagram mean??
• P(A|A) = 0.3
• P(B|A) = 0.7
• P(A|B) = 0.8
• P(B|B) = 0.2

Previous state

Next state

Markov Chain: forward propagation

​

​

​

​

​

​

​

• State transition: A-A-B, or A-B-B
• P(A|A) = 0.3
• P(B|A) = 0.7

A

B

A: Rainy 0.3

B: Sunny 0.7

Day 1- Rainy: 0.3*0.7

Day 1- Sunny: 0.7*0.2

Day 1

Day 2

Day 3

Markov Chain: forward propagation

• What is the probability the 3^rd day sunny?

​

​

​

​

​

• State transition: A-A-B, or A-B-B
• P(x₃=B, x₂=A, x₁=A) = 0.3*0.7= 0.21
• P(x₃=B, x₂=B, x₁=A) = 0.7*0.2 = 0.14
• P(x₃=B) = 0.21+0.14= 0.35

A

B

A: Rainy 0.3

B: Sunny 0.7

Day 1- Rainy: 0.3*0.3

Day 1- Sunny: 0.7*0.2

Day 1

Day 2

Day 3

Markov Chain: forward propagation

• What if we ask the probability the third day is raining? (A)

​

​

​

​

​

• State transition: A-A-B, or A-B-B
• P(x₃=A, x₂=A, x₁=A) = 0.3*0.3= 0.09
• P(x₃=A, x₂=B, x₁=A) = 0.7*0.8 = 0.56
• P(x₃=A) =0.09+0.56= 0.65

P(x₃=B) + P(x₃=A) =1

A

A

A: Rainy 0.3

B: Sunny 0.7

Day 1- Rainy: 0.3*0.3

Day 1- Sunny: 0.7*0.8

Day 1

Day 2

Day 3

A 1^st order Markov Chain

• The state at X_t+1 is only related to the state at X_t
• That is:
• P(X_t+1|X_t) = P(X_t+1|X_t,X_t-1, X_t-2, … X₀)

E.g. Student Markov chain

Student Markov Chain

Student Markov Chain

• n-step transition

pⁿ = p*p*p…

​

Every element represent

the chance after n^th transition

​

More classical transitions for Markov chain

• Drunkard’s walk: 5 bars on a street, 50% go next, 50% go previous. If the drunkard starts in bar 2, what is the chance he ends up in bar 0 in
• 2 steps?
• 3 steps?
• 4 steps?

​

​

More classical transitions for Markov chain

• Land of Oz
• This strange place will never have 2 consecutive good nice whether day

Outline

• Probability and Conditional Probability
• Bayes Rule
• Self-study: Gaussian Mixture Model
• Markov Chain
• Hidden Markov model
• Using HMM: Markov Localization

​

​

Hidden Markov model

• What if
• The state a transition:

​

​

​

​

​

​

​

​

• We cannot directly observe the state x
• We know the transition depends on previous input u, and previous state x
• We can observe an output/observance z
• Can we infer the next state? P(x_t+1)?

X₀

X₁

X₂

u₀

u₁

z₀

z₁

z₂

Hidden Markov model

• What if we have a model:

​

​

​

​

​

• We know:

​

X₀

X₁

X₂

u₀

u₁

z₀

z₁

z₂

Hidden Markov Model

• Question
• We know
• we know day 0 it is x₀ = rain
• we “prayed” at day 0 u₀ = rain, day 2 u₁ = rain

​

• We also observed:
• Cat sleeps at day 1 z₁ = L, sleeps at day 2 z₂= L
• What is the chance that at day 2 it is rainy? sunny?

​

Hidden Markov Model

Hidden Markov Model

X₀

X₁

X₂

u₀

u₁

z₀

z₁

z₂

Hidden Markov Model

X₀

X₁

X₂

u₀

u₁

z₀

z₁

z₂

Posterior for day 1 being rainy and sunny

HMM: update after a new observation

X₀

X₁

X₂

u₀

u₁

z₀

z₁

z₂

Probability for day 2, given cat sleeps on day 1

Posterior from previous day!

HMM: new state prior from previous update

X₀

X₁

X₂

u₀

u₁

z₀

z₁

z₂

Posterior for day 2 being rainy

HMM: update after a new observation

X₀

X₁

X₂

u₀

u₁

z₀

z₁

z₂

What happened just now?

• We update the posterior P(X_n|Z_n) by:
• Update Day1 Prior -> Posterior

​

​

​

​

• Day 2 Prior -> Posterior

​

Outline

• Probability and Conditional Probability
• Bayes Rule
• Self-study: Gaussian Mixture Model
• Markov Chain
• Hidden Markov model
• Using HMM: Markov Localization

​

​

A simple 2D localization story

• Our robot is approaching a wall
• We have a wheel encoder, we know the update of position for each interval follows a distribution h(x_t|x_t-1,u_t-1) (State transition table)
• We have a lidar, every time gap, we are sensing the distance to the wall (thus we know the position of the robot). We know the error of lidar follow a distribution P(z_t|x_t) (output table)
• Can we know where are we? (i.e. calculate bel(x_t|z_t))?

​

x_t

A simple 2D localization story

• In this configuration, how many column and rows we expect for state transition diagram?
• Or it is a distribution h(x_t|x_t-1,u_t-1)

A simple 2D localization story

• How about output (emission?)
• By your intuition, what should be the biggest value for x=0?
• Or it is continuous o(z_t|x_t)

​

x_t

Change of story for robotics

Change of predict belief

Change of correction belief

Markov localization

• A tutorial: https://www.youtube.com/watch?v=4gmQHvCDKzM