CS 188: Artificial Intelligence Fall 2008AnnouncementsRecap: Some Simple CasesHidden Markov ModelsBattleship HMMPassage of TimeExample: Passage of TimeObservationExample: ObservationExample HMMSlide 11The Forward AlgorithmBelief UpdatesParticle FilteringParticle Filtering: TimeParticle Filtering: ObservationParticle Filtering: ResamplingRobot LocalizationSLAMCS 188: Artificial IntelligenceFall 2008Lecture 19: HMMs II11/6/2008Dan Klein – UC Berkeley1AnnouncementsMidterm solutions up, regrade requests by 11/13Midterm evaluation up, please fill out!P5 up, due 11/19No section next week2Recap: Some Simple CasesE1X1X2X1QueriesModelsX2X1Hidden Markov ModelsAn HMM isInitial distribution:Transitions:Emissions:X5X2E1X1X3X4E2E3E4E5Battleship HMMP(X1) = uniformP(X|X’) = usually move according to fixed, known patrol policy (e.g. clockwise), sometimes move in a random direction or stay in placeP(Rij|X) = as before: depends on distance from ships in x to (i,j) (really this is just one of many independent evidence variables that might be sensed)1/9 1/91/9 1/91/91/91/9 1/9 1/9P(X1)P(X|X’=<1,2>)1/6 1/60 1/61/200 0 0X5X2Ri,jX1X3X4Ri,jRi,jRi,jE5Passage of TimeAssume we have current belief P(X | evidence to date)Then, after one time step passes:Or, compactly:Basic idea: beliefs get “pushed” through the transitionsWith the “B” notation, we have to be careful about what time step t the belief is about, and what evidence it includesX2X1Example: Passage of TimeAs time passes, uncertainty “accumulates”T = 1 T = 2 T = 5Transition model: ships usually go clockwiseObservationAssume we have current belief P(X | previous evidence):Then:Or:Basic idea: beliefs reweighted by likelihood of evidenceUnlike passage of time, we have to renormalizeE1X1Example: ObservationAs we get observations, beliefs get reweighted, uncertainty “decreases”Before observation After observationExample HMMExample HMMS SESEThe Forward AlgorithmWe are given evidence at each time and want to knowWe can derive the following updatesWe can normalize as we go if we want to have P(x|e) at each time step, or just once at the end…Belief UpdatesEvery time step, we start with current P(X | evidence)We update for time:We update for evidence:The forward algorithm does both at once (and doesn’t normalize)Problem: space is |X| and time is |X|2 per time stepX2E1X1X2E1X1E2Particle FilteringSometimes |X| is too big to use exact inference|X| may be too big to even store B(X)E.g. X is continuous|X|2 may be too big to do updatesSolution: approximate inferenceTrack samples of X, not all valuesTime per step is linear in the number of samplesBut: number needed may be largeThis is how robot localization works in practice0.0 0.10.0 0.00.00.20.0 0.2 0.5Particle Filtering: TimeEach particle is moved by sampling its next position from the transition modelThis is like prior sampling – samples’ frequencies reflect the transition probsHere, most samples move clockwise, but some move in another direction or stay in placeThis captures the passage of timeIf we have enough samples, close to the exact values before and after (consistent)Particle Filtering: ObservationSlightly trickier:We don’t sample the observation, we fix itThis is similar to likelihood weighting, so we downweight our samples based on the evidenceNote that, as before, the probabilities don’t sum to one, since most have been downweighted (in fact they sum to an approximation of P(e))Particle Filtering: ResamplingRather than tracking weighted samples, we resampleN times, we choose from our weighted sample distribution (i.e. draw with replacement)This is equivalent to renormalizing the distributionNow the update is complete for this time step, continue with the next oneRobot LocalizationIn robot localization:We know the map, but not the robot’s positionObservations may be vectors of range finder readingsState space and readings are typically continuous (works basically like a very fine grid) and so we cannot store B(X)Particle filtering is a main technique[DEMOS]SLAMSLAM = Simultaneous Localization And MappingWe do not know the map or our locationOur belief state is over maps and positions!Main techniques: Kalman filtering (Gaussian HMMs) and particle methods[DEMOS]DP-SLAM, Ron
View Full Document
Unlocking...