State Estimation and Probabilistic Filtering in Robotics
Explore the concepts of state estimation, Bayesian filtering, and probabilistic approaches in robotics for estimating robot states using sensor data and actions. Discover the importance of handling uncertainty and incorporating probabilistic models in autonomous systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
State Estimation Probability, Bayes Filtering Arunkumar Byravan CSE 490R Lecture 3
Interaction loop Sense: Receive sensor data and estimate state Sense Plan Plan: Generate long-term plans based on state & goal Act: Apply actions to the robot Act
State Byron Boots Statistical Robotics at GaTech Markovian assumption: Future is independent of past given present
State Estimation Estimate state using sensor data & actions: Robot position and orientation Environment map Location of people, other robots etc. Indoor localization for mobile robots (given map) Fuse information from different sensors (LIDAR, Wheel encoders) Probabilistic filtering
Why a probabilistic approach? Why is building C-3PO Difficult? Uncertainty environmental dynamics approximate computation random action effects inaccurate models sensor limitations Explicitly represent uncertainty using the calculus of probability theory CS8803: STR Probability 8
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. = ( ) . 0 , 2 . 0 , 7 . 0 08 . 0 , 02 P Room
Continuous Random Variables X takes on values in the continuum. p(X = x), or p(x) is the probability density function. E.g.
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)
Law of Total Probability, Marginals Discrete case Continuous case ( ) 1 P x = ( ) p x dx = 1 x y = = ( ) ( , ) P x P x y ( ) ( , ) p x p x y dy y = ( ) ( | ) ( ) P x P x y P y = ( ) ( | ) ( ) p x p x y p y dy
Events P(+x, +y) ? X Y P P(+x) ? +x +x -x -x +y -y +y -y 0.2 0.3 0.4 0.1 P(-y OR +x) ? Independent?
Marginal Distributions X +x -x P X Y P +x +x -x -x +y -y +y -y 0.2 0.3 0.4 0.1 Y +y -y P
Conditional Probabilities P(+x | +y) ? X Y P +x +x -x -x +y -y +y -y 0.2 0.3 0.4 0.1 P(-x | +y) ? P(-y | +x) ?
Bayes Formula = = ( , ) ( | ) ( ) ( | ) ( ) P x y P x y P y P y x P x ( | ) y ( ) likelihood prior P y x P x = = ( ) P x y ( ) evidence P Often causal knowledge is easier to obtain than diagnostic knowledge. Bayes rule allows us to use causal knowledge.
Simple Example of State Estimation Suppose a robot obtains measurement z What is P(open|z)?
Example P(z|open)= 0.6 P(open)= P( open)= 0.5 P(z| open)= 0.3 ( | ) ( ) P z open P open = ( | ) P open z + ( | ) ( ) ( | ) ( ) P z open p open P z open p open 5 . 0 6 . 0 2 = = = ( | ) . 0 67 P open z 5 . 0 3 . 0 + 5 . 0 6 . 0 3 z raises the probability that the door is open.
Normalization ( | ) P y x P x P y ( ) = = ( | ) ( ) P y x P x ( ) P x y ( ) 1 = = 1 ( ) P y ( | ') ( ') P y x P x ' x Algorithm: = : aux ( | ) ( ) x P y x P x | x y 1 = aux | x y x = : ( | ) aux x P x y | x y
Conditioning Bayes rule and background knowledge: ( | , ) ( | ) P y x z P x z = ( | , ) P x y z ( | ) P y z ? = ( ) ( | , ) ( ) P x y P x y z P z dz ? = ( | , ) ( | ) P x y z P z y dz ? = ( | , ) ( | ) P x y z P y z dz
Conditioning Bayes rule and background knowledge: ( | , ) ( | ) P y x z P x z = ( | , ) P x y z ( | ) P y z = ( ) ( | , ) ( | ) P x y z P z y dz P x y
Conditional Independence = ( , ) ( | ) ( | ) P x y z P x z P y z Equivalent to and = ( ) ( | , ) P x z P x z y = ( ) ( | , ) P y z P y z x
Simple Example of State Estimation Suppose our robot obtains another observation z2. What is P(open|z1, z2)?
Recursive Bayesian Updating ( | , , P , ) ( z | , , ) P z x z z P x z z 1 1 1 1 n n z n = ( | , , ) P x z z 1 n ( | , , ) z 1 1 n n Markov assumption: znis conditionally independent of z1,...,zn-1 given x. P(x|z1, ,zn) =P(zn|x) P(x|z1, ,zn - 1) P(zn|z1, ,zn - 1) =h P(zn|x) P(x|z1, ,zn - 1) =h1...n P(zi|x) i=1...n P(x)
Example: Second Measurement P(z2|open)= 0.5 P(open|z1)= 2/3 P(z2| open)= 0.6 P( open|z1)=1/3 ( | ) P ( z | ) P z open P open z = ( | , ) 2 1 P open z z 2 1 + ( | ) ( | ) ( | ) ( | ) P z open P open z open P open z 2 1 2 1 1 2 5 2 3 = = = . 0 625 1 2 3 1 8 + 2 3 5 3 z2lowers the probability that the door is open.
Bayes Filters: Framework Given: Stream of observations z and action data u: = { , , , } d u z u z 1 2 1 t t t 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 = ( ) ( | , , , ) x P x u z u z 1 2 1 t t t t
z = observation u = action x = state Bayes Filters = ( ) ( | , , , ) Bel x P x u z u z 1 1 t t t t = ( | , , , , ) ( | , , , ) P z x u z u P x u z u Bayes 1 1 1 1 t t t t t = ( | ) ( | , , , ) P z x P x u z u Markov 1 1 t t t t Total prob. =h P(zt| xt) P(xt|u1,z1, ,ut,xt-1) P(xt-1|u1,z1, ,ut)dxt-1 = ( | ) ( | , ) ( | , , , ) P z x P x u x P x u z u dx Markov 1 1 1 1 1 t t t t t t t t = ( | ) ( | , ) ( ) P z x P x u x Bel x dx 1 1 1 t t t t t t t
Bayes Filter Algorithm ( ) ( = t z P x Bel | ) ( | , ) ( ) x P x u x Bel x dx 1 1 1 t t t t t t t Algorithm Bayes_filter ( Bel(x),d ): n=0 1. 2. 3. If d is a perceptual data item z then 4. 5. 6. 7. 8. For all x do For all x do = Bel ( ' ) ( | ) ) ( ) Bel x + P ( ' x z x Bel x = = 1 ( ' ) ( ' ) Bel x Bel x 9. Else if d is an action data item u then 10. 11. For all x do Bel'(x)= P(x|u,x') Bel(x')dx' 12. Return Bel (x)
Markov Assumption = ( | , , ) ( | ) p z x : 1 z u p z x : 0 1 : 1 t t t t t t = ( | , , ) ( | , ) p x x : 1 z u p x x u : 1 1 1 : 1 1 t t t t t t t Underlying Assumptions Static world Independent noise Perfect model, no approximation errors
Bayes Filters for Robot Localization
Bayes Filters are Familiar! = ( ) ( | ) ( | , ) ( ) Bel x P z x P x u x Bel x dx 1 1 1 t t t t t t t t Kalman filters Particle filters Hidden Markov models Dynamic Bayesian networks Partially Observable Markov Decision Processes (POMDPs)
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.
