Particle Filters in Robotics, Sebastian Thrun

Particle Filters in Robotics, Sebastian Thrun

************************************************************************************

1) Introduction

1970's

model based approaches

doesn't account for uncertainty

assumes model is perfect

1980's

reactive techniques

i.e. behaviour based (Brooks)

generate control from sensor measurements

assumes sensors are perfect

mid 1990's

techniques that assume imperfect models and sensors

probabilistic robotics

integrates imperrfect models and sensors thru prob laws

such as Bayes rule

at all levels of perception and decision making

particle filters

easy: robot localization

harder problems

SLAM

variable number of dimensions

FastSLAM

can handle > 100,000 dimensions in real time

tracking

people moving near a robot

caveats

will always be wrong

false independence assumptions

lack state variables that systematically affect

sensor and actuator noise

? want state to affect noise?

must work in real time - pf's computationally expensiv

vanialla (exponential-time) pf's

2) Particle filters

approximate techniqes for calculationg posteriors

in partially observable (?) controllable (?) Markov chains (?)

with discrete time

state is not observable - measure with zt

zt = stochastic (?) projection of true state xt

Bayes filters compute posterior recursively

if states, control, measurements all discrete

Markov chain = hidden Markov models (HMM)

then Bayes equation (1) can be implemented exactly

pf's are applied to continuous state spaces

closed form solns for (1) are usually unknown

if p(x0) is gaussian, and motion/measurement models are linear

then (1) = Kalman filter

if nonlinear, can use linearize with 1st order taylor -> ekf

unscented filters

better linear model thru non-random sampling

still rely on gaussian-linear approximation

advantages to pf's

can be applied to any model

that can be formulated using a Markov chain

anytime

comp time can be changed w number of particles,

depending on resources

easy to implement

don't have to linearize

don't need closed form soln's of conditional p(xt|ut,xt-1)

disadvantage

d-dim state space --> exponentially many particles in d

best in low-dim spaces

conditional independences allow for higher dim apps (?)

3) Particle Filters in Low Dimensional Spaces

classical example: robot localization

state = x,y,theta

position tracking - if error is small at all times (?)

more general: global localization

localizing robot under global uncertainty

fig 1a - distribution over entire world

robot could be anywhere

kidnapped robot problem

well-localized robot is tele-ported to other location wo being told

i.e. - robo-cup - judge picking up and moving robot

multi-robot localization (observing each other)

fig 1 - global localization

a) global uncertainty

b) bimodal uncertainty - after going down symmetric corridor

c) unimodal uncertanity - after going into unique room

three figures represent successive posteriors (1)

each particle = x,y,theta

pf's for localization ==> Monte Carlo localization (MCL)

motivated by condensation aglorithm - popular in computer vision

more successful than parametric techniques such as KF's

aibo soccer robot - only 50 particles - limited computation

recent research

problem: next-state probability p(xt|ut,xt-1) sometimes insufficient

kidnapped robot

sensor accuracy much better than control accuracy (?)

hybrid sampling

subset of samples generated according to measurement model

? how different from general pf?

figure 3: compares standard and mixture MCL's

unmodeled environmental state

- artificially inflate unc to accomodate systematic noise

- filters for preprocessing sensor data

ex: range sensors corrupted by people

clustering particles

diff resampling rates for diff clusters

empirically increases robustness to errs in map used in loc

stratified (?) sampling techniqes

to increase variance in sampling step (?)

multi-robot

? are all these methods addressing problem with next-state

probability?

4) Particle Filters in High Dimensional Spaces

number of particles scales exponentially with state dimension

similar problem with vanilla HMM's

? aren't plain pf's = vanilla HMM's?

SLAM

errors in robot localization

-> systematic errors in feature localization

absence of initial map makes it impossible

to localize robot during mapping

using MCL algorithms

? more possible with KF?

data association problem:

if two features observed at diff times are same feature

space of all maps (?) is hundreds of thousdands dimensional

dimension of map unknown at beginning

ekf's address all of these problems except data association

assume statice environment - features not moving

time-invariant feature locations

time-variant robot pose

(2) integral only involves robot pose, not map

main problems

1) complexity = O(N^2) -even wo data assoc problem

scaling issues:

can't manage > 1000 features in rt

research into:

heirarchical map representations

maps decomposed recursively

into submaps

still O(N^2), but constant smaller

2) cannot incorporate negative information

false negatives

when failing to see a feature

that was expected

neg info leads to non-gaussian posteriors

3) no soln to data assoc problem

max likelihood estimator

thresholding outliers

new features placed on provisional list

problem: false positives

-> catastrophic erros

Rao-Blackwellized pf's

significantly more efficient than ekf for slam

1) O(MlogN)

M can be constant in case of bounded uncertaintly

SLAM ekf's only work with bounded uncertainty anyway

2) can deal with neg info

3) exp results, not proven, say better at data assoc

assume, first, no data assoc problem

independence property ( ?)

(not exploited by EKF soln's)

knowledge of robot path

-> feature locations cond indep (3)

fig 4 - shaded region is robot path

leads to (4) - more efficient version of (2)

estimates post on robot paths x^t

rather than xt

p(x^t|z^t,u^t)

each particle = posterior over entire path

p(yn|x^t,z^t)

feature posteriors

in FastSLAM

one EKF for each feature, dim = 2

pf's for robot paths

as in MCL for localization

feature ekfs exact, robot pose pfs approximate

O(NM)

N = number of features, M = num particles

because of (3), conditional independence

in FastSLAM, exploit fact that robot can only

observe finite number of features at any

point in time

features in tree structures (?)

becomes O(MlogN)

data assoc

since FastSLAM has an EKF for each feature,

can keep multiple hypotheses,

instead of just keeping best one

can incorporate neg information

by modifying importance factors

of indiv particles (?)

ekf more computationally expensive

question: (?) for FastSLAM, why can't you just use 3d ekf

for robot pose, and have no pf's?

fig 5 - FastSLAM with outdoor tree detection w lasers

fig 6 - lazy version of FastSLAM

each particle uses max likelihood data assoc

? particle for robot pose or feature?

feature locations calculated in a lazy way

for the mose likely particle only

? again, particles for robot pose

or feature?

point estimates for features (no variance)

similar to FastSLAM

pf's for estimates over robot paths

very good for indoor mapping

tracking

moving features

tracking people, service robotics

1) factored pf

features associated with indep pfs

using maximum likelihood

2) maps to detect people

differences between previous map

similar to SLAM

simultaneous localization of robots and people

similar to FastSLAM - exploits indep property

5) Discussion

tradicionally, pfs mostly used for low-dim localization problems

recently, higher dim problems

hybrid representations that exploit structure

conditional independences

further research: control

above only looks at perception

robot needs to do the right thing