麻省理工学院：《自制决策制造原则》英文版 Robot Localization using SIR

oo Robot Localization using SIR Sample x' from(x, y, 8) Iterate oI-n-model according to action af, to get proposal distribution mportance 3)Resample i epent

Robot Localization using SIR i I. Sample {x t} from (x, y, θ) II. Iterate: 1) Sample from motion model according to action a Prediction t, to get proposal distribution q(x) 2) Add importance weights 3) Resample Measurement

●。● Robot Localization using SIR Take sample set ( Xt11 Iterate For each sample x 1) Sample from p(X,1 Xt-1, a,-1 2) Attach importance weights p(x1)p(1|x1)p(x1|x+1,a12) WIx Z,x t x (x|x1=1,a1) ll. Resample from W(Xy

Robot Localization using SIR i I. Take sample set {x t-1} II. Iterate: i For each sample x t-1 1) Sample from p(xt-1| xit-1,at-1) 2) Attach importance weights = t x w it ) = x p it ) z p | x t ) x p t | xit −1, a ) = z p | xi ( t ) ( ( t i ( i t −1 ( ( ( i x q it ) x p t | xit −1, a ) t −1 II i I. Resample from w(x ) t

●。● Motion model as Proposal distribution o Importance sampling efficiency o difference between g(x and p(x) o Motion model and posterior are often close o Motion model is gaussian

Motion model as Proposal distribution | Importance sampling efficiency ∝ difference between q(x) and p(x) | Motion model and posterior are (often) close | Motion model is Gaussian

Motion model as proposal ●。● distribution o Motion model is gaussian about translation and rotation Start location 10 meters

Motion model as Proposal distribution | Motion model is Gaussian about translation and rotation

oo Sampling from Motion Model o a common motion model Decompose motion into rotation translation rotation Rotation 卩=△1,02e=a△d+Q2△ Translation:p=△d,o2△d=a3△d+a4△1+△2) Rotation: =△91022=a△d+a2△2 o Compute rotation translation rotation from odometry o For each particle, sample a new motion triplet by from gaussians described above o Use geometry to generate posterior particle position

Sampling from Motion Model | A common motion model: • Decompose motion into rotation, translation, rotation • Rotation: µ = ∆θ1, σ2 ∆θ1 = α1∆d+ α 2∆θ1 • Translation: µ = ∆d, σ 2 = α 3 ∆d+ α 4(∆θ1+ ∆θ 2) ∆d • Rotation: µ = ∆θ1,σ2 ∆θ 2 = α1∆d+ α 2∆θ2 | Compute rotation, translation, rotation from odometry | For each particle, sample a new motion triplet by from Gaussians described above | Use geometry to generate posterior particle position

●。。 Sensor model 0L3 Approximated F1 Measured Expected distance 73 g 0 4om Measured distance y [cm]

Sensor Model Measured distance y [cm] Expected distance Probability p(y,x) Approximated Measured

●。。 Sensor model prabang 县3 asreddstanee圆l distance Laser model built from collected data Laser model fitted to measured data using approximate geometric distribution

Sensor Model Laser model built from collected data Laser model fitted to measured data, using approximate geometric distribution

● Problem o How to compute expected distance for any given(x, y, 8? Ray-tracing Cached expected distances for all(X, y, 8) o Approximation Assume a symmetric sensor model depending only on Ad: absolute difference between expected and measured ranges Compute expected distance only for(x, y) Much faster to compute this sensor model Only useful for highly-accurate range sensors ( e.g., laser range sensors, but not sonar)

Problem | How to compute expected distance for any given (x, y, θ)? • Ray-tracing • Cached expected distances for all (x, y, θ). | Approximation: • Assume a symmetric sensor model depending only on ∆d: absolute difference between expected and measured ranges • Compute expected distance only for (x, y) • Much faster to compute this sensor model • Only useful for highly-accurate range sensors (e.g., laser range sensors, but not sonar)

●。● Computing Importance Weights (Approximate Method) o Off-line for each empty grid-cell(x, y) Compute d(x, y the distance to nearest filled cell from(x, y) Store this"expected distance"map o At run-time, for a particle( x, y) and observation z=(r, 8) Compute end-point (x,y)= X+rcos(0), y+rsin (e)) Retrieve d(x, y and compute Ad from △d=r-d(x,y) Compute p( Ad x) from Gaussian sensor model of specITIc o

Computing Importance Weights (Approximate Method) | Off-line, for each empty grid-cell (x, y) • Compute d(x, y) the distance to nearest filled cell from (x, y) • Store this “expected distance” map | At run-time, for a particle (x, y) and i observation z =(r, θ) • Compute end-point (x’, y’) = (x+rcos(θ),y+rsin(θ)) • Retrieve d(x’, y’) and compute ∆d from ∆d = r - d(x’, y’) • Compute p(∆d |x) from Gaussian sensor model of specific σ2

●。。 Another prob|em o An observation Is several range measurements o Assume range measurements are independent p(21)=∏p2 o What happens when map is wrong?

Another problem | An observation is several range measurements: • Zt={z1,z 2,…,z n} | Assume range measurements are independent: ( i ( Z p ) = ∏ z p t ) t Z | What happens when map is wrong?