Introduction to Mobile Robotics PDF

Introduction to Mobile Robotics Probabilistic Robotics 1 Probabilistic Robotics Key idea: Explicit representation of uncertainty (using the calculus of probability theory) ▪ Perception = state estimation ▪ Action = utility optimization...

Introduction to Mobile Robotics Probabilistic Robotics 1 Probabilistic Robotics Key idea: Explicit representation of uncertainty (using the calculus of probability theory) ▪ Perception = state estimation ▪ Action = utility optimization 2 Axioms of Probability Theory P(A) denotes probability that proposition A is true. ▪ 0  P(A)  1 ▪ P(True) = 1 P(False) = 0 ▪ P(A B) = P(A) + P(B) − P(A  B) 3 A Closer Look at Axiom 3 P(A B) = P(A) + P(B) − P(A B) True A A B B B 4 Using the Axioms P(A A) = P(A) + P(A) − P(A A) P(True) = P(A) + P(A) − P(False) 1 = P(A) + P(A) − 0 P(A) = 1− P(A) 5 Discrete Random Variables ▪ X denotes a random variable ▪ X can take on a countable number of values in {x1, x2, …, xn} ▪ P(X=xi) or P(xi) is the probability that the random variable X takes on value xi ▪ P(.) is called probability mass function ▪ E.g. P(Room) = 0.7, 0.2, 0.08, 0.02 6 Continuous Random Variables ▪ X takes on values in the continuum. ▪ p(X=x) or p(x) is a probability density function b P(x  [a, b]) =  p(x)dx a ▪ E.g. p(x) x 7 “Probability Sums up to One” Discrete case Continuous case  P(x) = 1  p(x) dx = 1 x 8 Joint and Conditional Probability ▪ P(X=x and Y=y) = P(x,y) ▪ If X and Y are independent then P(x,y) = P(x) P(y) ▪ P(x | y) is the probability of x given y P(x | y) = P(x,y) / P(y) P(x,y) = P(x | y) P(y) ▪ If X and Y are independent then P(x | y) = P(x) 9 Law of Total Probability Discrete case Continuous case P(x) =  P(x | y)P(y) p(x) =  p(x | y)p(y) dy y 10 Marginalization Discrete case Continuous case P(x) =  P(x, y) p(x) =  p(x, y) dy y 11 Bayes Formula P(x, y) = P(x | y)P(y) = P(y | x)P(x)  P(y | x) P(x) likelihood  prior P(x y) = = P(y) evidence 12 Normalization P ( x y) = P ( y | x ) P ( x ) =  P(y | x) P(x) P ( y) 1  = P(y) = −1  P ( y | x)P(x) x 13 Bayes Rule with Background Knowledge P(x | y, z) = P(y | x, z) P(x | z) P(y | z) 14 Conditional Independence P(x, y z) = P(x | z)P( y | z) ▪ Equivalent to P(x z) = P(x | z, y) and P( y z) = P( y | z, x) ▪ But this does not necessarily mean P(x, y ) = P(x)P( y) (independence/marginal independence) 15 Simple Example of State Estimation ▪ Suppose a robot obtains measurement z ▪ What is P(open | z)? 16 Causal vs. Diagnostic Reasoning ▪ P(open|z) is diagnostic ▪ P(z|open) is causal ▪ In some situations, causal knowledge is easier to obtain count frequencies! ▪ Bayes rule allows us to use causal knowledge: P(open | z) = P(z | open)P(open) P(z) 17 Example ▪ P(z|open) = 0.6 P(z|open) = 0.3 ▪ P(open) = P(open) = 0.5 P(z | open)P(open) P(open | z) = P(z | open) p(open) + P(z | open) p(open) 0.6  0.5 0.3 P(open | z) = = = 0.67 0.6  0.5 + 0.3 0.5 0.3 + 0.15 ▪ z raises the probability that the door is open 18 Combining Evidence ▪ Suppose our robot obtains another observation z2 ▪ How can we integrate this new information? ▪ More generally, how can we estimate P(x | z1,..., zn )? 19 Recursive Bayesian Updating P(zn | x, z1,…, zn − 1) P(x | z1,…, zn − 1) P(x | z1,…, zn ) = P(zn | z1,…, zn − 1) Markov assumption: zn is independent of z1,...,zn-1 if we know x P(zn | x) P(x | z1,…, zn − 1) P(x | z1,…, zn ) = P(zn | z1,…, zn − 1) =  P(zn | x) P(x | z1,…, zn − 1)   = 1...n  P(zi | x)P(x) i=1...n  20 Example: Second Measurement ▪ P(z2|open) = 0.25 P(z2|open) = 0.3 ▪ P(open|z1)=2/3 P(z2 | open) P(open | z1 ) P(open | z2, z1 ) = P(z2 | open) P(open | z1 ) + P(z2 |open) P(open | z1 ) 1 2 1 1  = 4 3 = 6 = 6 = 5 = 0.625 1 2 3 1 1 1 4 8  +  + 4 3 10 3 6 10 15 z2 lowers the probability that the door is open 21 Actions ▪ Often the world is dynamic since ▪ actions carried out by the robot, ▪ actions carried out by other agents, ▪or just the time passing by change the world ▪ How can we incorporate such actions? 23 Typical Actions ▪ The robot turns its wheels to move ▪ The robot uses its manipulator to grasp an object ▪ Plants grow over time … ▪ Actions are never carried out with absolute certainty ▪ In contrast to measurements, actions generally increase the uncertainty 24 Modeling Actions ▪ To incorporate the outcome of an action u into the current “belief”, we use the conditional pdf P(x | u, x’) ▪ This term specifies the pdf that executing u changes the state from x’ to x. 25 Example: Closing the door 26 State Transitions P(x | u, x’) for u = “close door”: 0.9 0.1 open closed 1 0 If the door is open, the action “close door” succeeds in 90% of all cases 27 Integrating the Outcome of Actions Continuous case: P(x | u) =  P(x | u, x ')P(x ' | u)dx ' Discrete case: P(x | u) =  P(x | u, x ')P(x ' | u) We will make an independence assumption to get rid of the u in the second factor in the sum. 28 Example: The Resulting Belief P(closed | u) =  P(closed | u, x ')P(x ') = P(closed | u, open)P(open) + P(closed | u, closed)P(closed) 9 5 1 3 15 =  +  = 10 8 1 8 16 P(open | u) = P(open | u, x ')P(x ') = P(open | u, open)P(open) + P(open | u, closed)P(closed) 1 5 0 3 1 =  +  = 10 8 1 8 16 = 1− P(closed | u) 29 Bayes Filters: Framework ▪ Given: ▪ Stream of observations z and action data u: dt = {u1, z1, …, ut , zt } ▪ Sensor model P(z | x) ▪ Action model P(x | u, x’) ▪ Prior probability of the system state P(x) ▪ Wanted: ▪ Estimate of the state X of a dynamical system ▪ The posterior of the state is also called Belief: Bel(xt ) = P(xt | u1, z1, …, ut , zt ) 30 Markov Assumption P(z t | x0:t , z1:t−1, u1:t ) = P(z t | xt ) P(xt | x1:t−1, z1:t−1, u1:t ) = P(xt | xt−1, ut ) Underlying Assumptions ▪ Static world ▪ Independent noise ▪ Perfect model, no approximation errors 31  z = observation u = action Bayes Filters x = state Bel(xt ) = P(xt | u1, z1 …, ut , zt ) Bayes =  P(zt | xt , u1, z1, …, ut ) P(xt | u1, z1, …, ut ) Markov =  P(zt | xt ) P(xt | u1, z1, …, ut ) Total prob. =  P(zt | xt )  P(x t | u1, z1, …,ut , xt−1 ) P(xt−1 | u1, z1, …, ut ) dxt−1 Markov =  P(zt | xt )  P(x | u , x t t t−1 ) P(xt−1 | u1, z1, …,ut ) dxt−1 Markov = P(zt | x )  P(x | u , x t t t t−1 ) P(xt−1 | u1, z1, …, zt−1 ) dxt−1 = P(zt | xt )  P(x t | ut , xt−1 ) Bel(xt−1 ) dxt−1 32 Bayes P(z t | xt ) Algorithm Bel(xt ) = Filter P(xt | ut , xt −1 )Bel(xt −1 )dxt −1 1. Algorithm Bayes_filter(Bel(x), d): 2. =0 3. If d is a perceptual data item z then 4. For all x do 5. Bel '(x) = P(z | x)Bel(x) 6.  =  + Bel '(x) 7. For all x do 8. Bel '(x) =  −1Bel '(x) 9. Else if d is an action data item u then 10. For all x do 11. Bel '(x) =  P(x | u, x ') Bel(x ') dx ' 12. Return Bel’(x) 33 Bayes Filters are Familiar! Bel(xt ) =  P(z t | xt )  P(xt | ut , xt −1 )Bel(xt −1 )dxt −1 ▪ Kalman filters ▪ Particle filters ▪ Hidden Markov models ▪ Dynamic Bayesian networks ▪ Partially Observable Markov Decision Processes (POMDPs) 34 Probabilistic Localization Probabilistic Localization Summary ▪ Bayes rule allows us to compute probabilities that are hard to assess otherwise. ▪ Under the Markov assumption, recursive Bayesian updating can be used to efficiently combine evidence. ▪ Bayes filters are a probabilistic tool for estimating the state of dynamic systems. 37