Probabilistic Robotics.ppt

1、Probabilistic Robotics: A Tutorial,Juan Antonio Fernndez Madrigal October 2004 System Engineering and Automation Dpt. University of Mlaga (Spain),October 2004,Juan Antonio Fernndez Madrigal,Contents,Introduction 1.1 Probabilistic Robotics? 1.2 The Omnipresent Core: Bayes Rule 1.3 Lets Filter! (Bayes

2、 Filter) You Will Find Them Everywhere: Basic Mathematical Tools 2.1 A Visit to the Casino: MonteCarlo Methods 2.2 Partially Unknown Uncertainty: the EM Algorithm 2.3 Approximating Uncertainty Efficiently: Particle Filters The Foundations: The Common Bayesian Framework 3.1 Graphs plus Uncertainty: G

3、raphical Models 3.2 Arrows on Arcs: Bayesian Networks 3.3 Let it Move: Dynamic Bayesian Networks (DBNs) Forgetting the Past: Markovian Models 4.1 It is Easy if it is Gaussian: Kalman Filters 4.2 On the Line: Markov Chains 4.3 What to Do?: Markov Decision Processes (MDPs) 4.4 For Non-Omniscient Peopl

4、e: Hidden Markov Models (HMMs) 4.5 For People that Do Things: POMDPs,October 2004,Juan Antonio Fernndez Madrigal,1. Introduction,1.1 Probabilistic Robotics?,Why Probabilistic Robotics?,Whats Probabilistic Robotics?,Robotics that use probability calculus for modeling and / or reasoning about robot ac

5、tions and perceptions. -State-of-the-art Robotics,For coping with uncertainty on the robots environment.,For coping with uncertainty / noise on robots perceptions.,For coping with uncertainty / noise on robots actions.,October 2004,Juan Antonio Fernndez Madrigal,1. Introduction,1.2 The Omniscient Co

6、re: Bayes Rule (1750),P(R=r | e),Rule for updating your existing belief (probability of some variable) given new evidence (the occurrence of some event).,In spite of its simplicity, it is the basis for most probabilistic approaches in robotics and other sciences.,=,P(e | R=r),P(R=r),October 2004,Jua

7、n Antonio Fernndez Madrigal,Known evidence,1. Introduction,1.3 Lets Filter! (Bayes Filter),Bayes Rule can be iterated for improving estimate over time:,In general, there are the following possibilities:,October 2004,Juan Antonio Fernndez Madrigal,2. Youll Find Them Everywhere: Basic Mathematical Too

8、ls,2.1 A Visit to the Casino: MonteCarlo Methods (1946),A set of methods based on statistical sampling for approximating some value(s) (any quantitative data) when analytical methods are not available or computationally unsuitable.,In its general form, it is a way to approximate integrals:,Given the

9、 difficult integral (function “f” is known):,It can be approximated by the following steps:,1) Take a uniform distribution over the region of integration:,2) Calculate the expectation of f(U) by statistical sampling (m samples):,4) Since U is uniform, p(u)=1, so:,6) The error diminishes with many sa

10、mples, but maybe slowly.,There are techniques of “variance reduction” to reduce also sigma: -Antitethic variates -Control Variates -Importance Sampling -Stratified Sampling.,Error in aproximation does not depend on dimensionality of data.,October 2004,Juan Antonio Fernndez Madrigal,2. Youll Find The

11、m Everywhere: Basic Mathematical Tools,2.2 Partially Unknown Uncertainty: The EM Algorithm,-The Expectation-Maximization algorithm (1977) can be used in general for estimating any probability distribution from real measurements that can be incomplete.,-The algorithm works in two steps (E and M) that

12、 are iterated, improving the likelihood of the estimate over time. It can be demonstrated that the algorithm converges to a local optimum.,1. E-step (Expectation). Given the current estimate of the distribution, calculate the expectation of the measurements with respect to that estimate.,2. M-step (

13、Maximization). Produce a new estimate that improve (maximizes) that expectation.,October 2004,Juan Antonio Fernndez Madrigal,2. Youll Find Them Everywhere: Basic Mathematical Tools,2.2 Partially Unknown Uncertainty: The EM Algorithm,-Mathematical formulation (in the general case):,Z=(X,Y),All the da

14、ta (both missing and measured),Measured data,Missing or hidden data (not measured),p(Z | M) = p(X,Y | M),Complete-data likelihood given a model M (we will maximize the expectation of this),-E-step:,-M-step:,M(i) = argmax(on M) E log p(X,Y | M) | X,M(i-1) ,Variation: M(i) = any M that makes expectati

15、on greater than M(i-1),Generalized EM (GEM), also converges,October 2004,Juan Antonio Fernndez Madrigal,2. Youll Find Them Everywhere: Basic Mathematical Tools,2.3 Approximating Uncertainty Efficiently: Particle Filters,-MonteCarlo Filter (i.e.: iterated over time).,-It is useful due to its efficien

16、cy.,-Represent probability distributions by samples with associated weights, and yield information from the distributions by computing on those samples.,-As the number of samples increases, the accuracy of the estimate increases.,-There are a diversity of particle filter algorithms depending on how

17、to select the samples.,October 2004,Juan Antonio Fernndez Madrigal,3. The Foundations: The Common Bayesian Framework,3.1 Graphs plus Uncertainty: Graphical Models,A common formalism that copes with both uncertainty and complexity, two problems commonly found in applied mathematics and engineering.,A

18、 graphical model is a graph with associated probabilities. Nodes represent random variables. An arc between two nodes indicates a statistical dependence between two variables.,Many specific derivations: mixture models, factor analysis, hidden Markov models, Kalman filters, etc.,Three basic types:,A)

19、 Undirected graphs (=Markov Random Fields): in Physics, Computer Vision, .,B) Directed (=Bayesian Networks): in Artificial Intelligence, Statistics, .,C) Mixed (=Chain Graphs).,October 2004,Juan Antonio Fernndez Madrigal,3. The Foundations: The Common Bayesian Framework,3.2 Arrows on Graphs: Bayesia

20、n Networks,Nodes (variables) can hold discrete or continuous values. Arcs represent causality (and conditional probability),The model is completely defined by its graph structure, the values of its nodes (variables) and the conditional probabilities of the arcs,P(C=true)=0.5 P(C=false)=0.5,P(S=true

21、| C=true)=0.1 P(S=true | C=false)=0.5 P(S=false | C=true)=0.9 P(S=false | C=false)=0.5,P(R=true | C=true)=0.8 P(R=true | C=false)=0.2 P(R=false | C=true)=0.2 P(R=false | C=false)=0.8,October 2004,Juan Antonio Fernndez Madrigal,3. The Foundations: The Common Bayesian Framework,3.2 Arrows on Graphs: B

22、ayesian Networks - Inference,1) Bottom-up Reasoning or Diagnostic: from effects to causes,-For example: given that the grass is wet (W=true), which is more likely, the sprinklet being on (S=true) or the rain (R=true)?,-We seek P(S=true | W=true) and P(R=true | W=true),-Using the definition of condit

23、ional probability:,-In general, using the chain rule:,P(C,S,R,W) = P(C) P(S|C) P(R|S,C) P(W|S,R,C),-But by the graph structure:,P(C,S,R,W) = P(C) P(S|C) P(R|C) P(W|S,R),October 2004,Juan Antonio Fernndez Madrigal,3. The Foundations: The Common Bayesian Framework,3.2 Arrows on Graphs: Bayesian Networ

24、ks - Inference,1) Bottom-up Reasoning or Diagnostic: from effects to causes,-For example: given that the grass is wet (W=true), which is more likely, the sprinklet being on (S=true) or the rain (R=true)?,-We seek P(S=true | W=true) and P(R=true | W=true),-Using the definition of conditional probabil

25、ity:,-By marginalization:,October 2004,Juan Antonio Fernndez Madrigal,3. The Foundations: The Common Bayesian Framework,3.2 Arrows on Graphs: Bayesian Networks - Inference,2) Top-down Reasoning or Causal / Generative Reasoning: from causes to effects,-For example: given that it is cloudy (C=true), w

26、hich is the probability that the grass is wet (W=true)?,-We seek P(W=true | C=true),-The inference is similar.,October 2004,Juan Antonio Fernndez Madrigal,3. The Foundations: The Common Bayesian Framework,3.2 Arrows on Graphs: Bayesian Networks - Causality,-It is possible to formalise if a variable

27、(node) is a cause for another or if they are merely correlated.,-It would be useful, for example, for a robot to learn the effects of its actions.,October 2004,Juan Antonio Fernndez Madrigal,3. The Foundations: The Common Bayesian Framework,3.3 Let it Move: Dynamic Bayesian Networks (DBNs),-Bayesian

28、 Networks with time, not dynamical in the sense that the graph structure or parameters vary.,-(Very) simplified taxonomy of Bayesian Networks:,Graphical Models,Undirected = Markov Random Fields,Directed = Bayesian Networks,Non-temporal,Temporal = Dynamic Bayesian Networks,Hidden Markov Models (HMM),

29、Markov Decision Processes,Partially Observable Markov Decision Processes (POMDP),Markov Chains,Kalman Filters,Totally Observable,Partially Observable,No actions,Actions,Gaussian Models,Markov Processes (independence of future w.r.t. all past),October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting

30、 the Past: Markovian Models,4.1 It is Easy if it is Gaussian: Kalman Filters (1960),-They model dynamic systems, with partial observability, and gaussian probability distributions.,-It is of interest:,-Applications: any in which it is needed to estimate the state of a known dynamical system under ga

31、ussian uncertainty / noise: computer vision (tracking), robot SLAM (if the map is considered part of the state), .,-To estimate the current state. Thus, the EM algorithm can be thought as an alternative not subjected to gaussians.,-Extensions: to reduce computational cost (e.g.: when the state has a

32、 large description), to cope with more than one hypothesis (e.g.: when two indistinguishable landmarks yield a two-modal distribution for the pose of a robot), to cope with non-linear systems (through linearization: EKF), .,October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting the Past: Markovia

33、n Models,4.1 It is Easy if it is Gaussian: Kalman Filters (1960),-Mathematical formulation:,P(x | u,x) = Ax + Bu + ec,current state of the system,actions performed by the system,last state,known linear model of the system,gaussian noise in system actions,P(z | x) = Cx + em,current observations of th

34、e system,current state of the system,known linear model of the observations,gaussian noise in observations,White Noise,October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models,4.1 It is Easy if it is Gaussian: Kalman Filters (1960),-Through a Bayes Filter:,state estimate,

35、October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models,4.2 On the Line: Markov Chains,-Nodes of the network represent a random variable X in a given instant of time (unknown except for the first node).,-Arc from node Xn to node Xn+1 represent the conditional probability

36、 that the random variable X takes a probability distribution Xn+1 given that it exhibited distribution Xn at the last instant (no other past instant is considered since the model is markovian).,-Instants of time are discrete. All conditionals are known.,-It is of interest: a) causal reasoning: to ob

37、tain Xn from all its past, and b) whether the probability distribution converges over time: assured if the chain is ergodic (any node is reachable in one step from any other node) .,-Applications:,-Direct: physics, computer networks, .,-Indirect: as part of more sophisticated models.,October 2004,Ju

38、an Antonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models,4.3 What to Do?: Markov Decision Processes,-Markov Processes with actions (output arcs) that can be carried out at each node (state), with some reward as a result of a given action on a given state.,-It is of interest: to obtain t

39、he best sequence of actions (markov chain) that optimize the reward. Any sequence of actions (chain) is called a policy.,-In every MDP, it can be demonstrated that there always exists an optimal policy (the one that optimizes the reward).,-Obtaining the optimal policy is expensive (polynomial). Ther

40、e are several algorithms for solving it, some of them reducing that cost (by hierarchies, etc.). The most classical one: value iteration.,-Applications: decision making in general, robot path planning, travel route planning, elevator scheduling, bank customer retention, autonomous aircraft navigatio

41、n, manufacturing processes, network switching and routing, .,A Case of Reinforcement Learning (RL),October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models,4.4 For Non-Omniscient People: Hidden Markov Models,(1960-70) Markov Processes without actions and with partial obse

42、rvability.,States of the network are not directly accessable, except through some stochastic measurement. That is, observations are a probabilistic function of the state,-It is of interest:,-Applications: speech processing, robot SLAM, bioinformatics (gene finding, protein modeling, etc.), image pro

43、cessing, finance, traffic, .,a) which is the probability of the sequence of observations, given the network?,b) which states have we visited more likely, given observations and network parameters?,c) which are the network parameters that maximize the probability of having obtained those observations

44、?,How good is a given model? (not really interesting for us),Where are we in the model? (little use: model known),Which is the model? (robot mapping/localisation),October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models,4.4 For Non-Omniscient People: Hidden Markov Models,

45、-Elements in a HMM:,N = n of states in the network (i-th state=si).,M = n of different possible observations (k-th observation=ok).,A = matrix (N x N) of state transition probabilities: axy=P(qt+1=sy | qt=sx),B = matrix (N x M) of observation probabilities: bx(ok)=P(ot=ok | qt=sx),P = matrix (1 x N)

46、 of initial state probabilities: Px=P(q0=sx),l = HMM model = (A,B, P),October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models,4.4 For Non-Omniscient People: Hidden Markov Models,-Solution to Problem a): which is the probability of a sequence of observations (of length T)

47、, given the network?,-Direct approach: enumerate all the possible sequences of states (paths) of length T in the network, and calculate for each one the probability that the given sequence of observations is obtained if the path is followed. Then, calculate the probability of that path, and thus the

48、 joint probability of the path and of the observations for that path. Finally, sum up for all the possible paths In the network.,It depends on the number of paths of length T: O(2TNT ), unfeasible for T long enough.,October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models

49、,4.4 For Non-Omniscient People: Hidden Markov Models,-Efficient approach: the forward-backward procedure.,-A forward variable is defined at(i)=P(O1,O2,.,Ot,qt=si | l) as the probability of the observation sequence O1,O2,.,Ot followed by reaching state si.,1. a1(i)=Pibi(O1), for all states i from 1 t

50、o N,-It is calculated recursively:,-This calculation is O(N2T ).,October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models,4.4 For Non-Omniscient People: Hidden Markov Models,-Efficient approach: the forward-backward procedure.,-Alternativelty, a backward variable can be d

51、efined bt(i)=P(Ot+1,Ot+2,.,OT,qt=si | l) as the probability of the observation sequence Ot+1,Ot+2,.,OT preceded by having reached state si.,1. b1(i)=1, for all states i from 1 to N,-It is calculated recursively:,October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models,4.4

52、 For Non-Omniscient People: Hidden Markov Models,-Solution to Problem b): which states have we visited more likely, given a sequence of observations of length T and the network?,-There is not a unique solution (as in problem a): it depends on the optimality criteria chosen. But when one is chosen, a

53、 solution can be found analitycally.,-The Viterbi Algorithm: it finds the best single-state sequence of states (the one that maximizes the probability of each single state of the sequence, independently on the other states, at each step).,-The following two variables are defined:,(It calculates all

54、the sequences of states that reach state si at the end and produce the given observations; Then it returns the maximum probability found),(traces the state that maximizes the expression, that is, that maximizes the likelihood of passing through single state sj),October 2004,Juan Antonio Fernndez Mad

55、rigal,4. Forgetting the Past: Markovian Models,4.4 For Non-Omniscient People: Hidden Markov Models,-The algorithm works as follows:,1. d1(i)=Pibi(O1), for all states i from 1 to N y1(i)=0, for all states i,4. qt*= yt+1(qt+1*) (for retrieving all the other states in the sequence),October 2004,Juan An

56、tonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models,4.4 For Non-Omniscient People: Hidden Markov Models,-Solution to Problem c): which are the network parameters that maximize the probability of having obtained the observations?,-Not only there is no one unique solution (as in problem b

57、), but there are not any analitycal procedure to obtain it: only approximations are available.,-Approximation algorithms that obtain locally optimal models exist. Most popular: EM (Expectation-Maximization), which is called Baum-Welch when adapted to HMMs:,-The sequence of observations are considere

58、d the measured data. -The sequence of states that yield those observations, the missing or hidden data. -The matrices A, B, P are the parameters to approximate. -The number of states is known a priori.,October 2004,Juan Antonio Fernndez Madrigal,4. Forgetting the Past: Markovian Models,4.5 For Peopl

59、e that Do Things: POMDPs,-Markov Processes with both actions and partial observability.,-It is of interest:,-Applications: any in which it is needed both to model some real process (or environment) and to act optimally with that model. Only recently applied to robotics (1996),-The three problems of HMMs: likelihood of the mode