ECAI 02 Invited Plenary Talk - Sebastian Thrun

ECAI 02 Invited Plenary Talk - Sebastian Thrun

Particle Filters In Robotics or: How the World Became To Be One Big Bayes Network Sebastian Thrun Carnegie Mellon University University of Pittsburgh Acknowledgements Carnegie Mellon University UC Berkeley

Wolfram Burgard Frank Dellaert (now GA Tech) Dieter Fox (now U Washington) Geoff Gordon Michael Montemerlo Joelle Pineau Nicholas Roy Reid Simmons Stanford University

Dragomir Anguelov Rahul Biswas Daphne Koller Benson Limketkai Ben Wegbreit Kevin Murphy Andrew Ng University of Sydney Hugh Durrant-Whyte Eduardo Nebot Juan Nieto Funding

DARPA NSF Intel Robotics Research Today Particle Filters In Robotics 4 Open Problems Sebastian Thrun Carnegie Mellon University UAI

Aug 2, 2002 Robotics Yesterday Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Robotics Today Sebastian Thrun Carnegie Mellon University UAI

Aug 2, 2002 Robotics Tomorrow? Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Robotics Research Today Particle Filters In Robotics 4 Open Problems

Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Robotics @ CMU, 1997 with W. Burgard, A.B. Cremers, D. Fox, D. Hhnel, G. Lakemeyer, D. Schulz, W. Steiner Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002

Robotics @ CMU, 1998 with M. Beetz, M. Bennewitz, W. Burgard, A.B. Cremers, F. Dellaert, D. Fox, D. Hhnel, C. Rosenberg, N. Roy, J. Schulte, D. Schulz Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 The Localization Problem fast-moving ambiguous identity

non-stationary many objects static few objects one object uniquely identifiable local (tracking) Sebastian Thrun Objects Robots

Other Agents Carnegie Mellon University global kidnapped UAI Aug 2, 2002 Probabilistic Localization m map z1 observations x1

robot poses controls u2 laser data Sebastian Thrun Bayes filter HMMs z DBNs2 POMDPs Kalman filters x 2Particle filters x3 Condensation etc

z3 z3 ... u3 xt ut map m Carnegie Mellon University UAI Aug 2, 2002 Bayes Filter Localization

[Nourbakhsh et al 94] [Simmons/Koenig 95] [Kaelbling et al 96] Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 What is the Right Representation? Kalman filter [Schiele et al. 94], [Wei et al. 94], [Borenstein 96], [Gutmann et al. 96, 98], [Arras 98] Histograms

(metric, topological) [Nourbakhsh et al. 95], [Simmons et al. 95], [Kaelbling et al. 96], [Burgard et al. 96], [Konolige et al. 99] Sebastian Thrun Carnegie Mellon University Multi-hypothesis [Weckesser et al. 98], [Jensfelt et al. 99] Particles [Kanazawa et al 95] [de Freitas 98] [Isard/Blake 98] [Doucet 98] UAI Aug 2, 2002 Particle Filters For Localization

Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Monte Carlo Localization (MCL) With: Wolfram Burgard, Dieter Fox, Frank Dellaert Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002

Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Monte Carlo Localization With: Frank Dellaert Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002

Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Particle Filter in High Dimensions fast-moving ambiguous identity non-stationary many objects/features static

few objects one object uniquely identifiable local (tracking) Sebastian Thrun Carnegie Mellon University global kidnapped UAI

Aug 2, 2002 Learning Maps aka Simultaneous Localization and Mapping (SLAM) 70 m Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 The SLAM Problem Sebastian Thrun Carnegie Mellon University

with known data association UAI Aug 2, 2002 EKF Approach O(N2) [Smith, Self, Cheeseman, 1985] Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Kalman Filter Mapping: O(N2)

Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 EKS-SLAM for Underwater Mapping Courtesy of Stefan Williams and Hugh Durrant-Whyte, Univ of Sydney Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002

Particle Filtering in Low Dimensions! sample pose robot poses Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Particle Filtering in High Dimensions? sample map maps Sebastian Thrun

Carnegie Mellon University UAI Aug 2, 2002 Insight: Conditional Independence Landmark 1 1 z1 observations Robot poses x1 controls z3

x2 x3 ... u3 u2 xt ut z2 zt 2 Landmark 2

Factorization first developed by Murphy & Russell, 1999 Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Rao-Blackwellized Particle Filters robot poses landmark n=1 landmark n=N landmark n=2

landmark n=1 landmark n=N landmark n=2 [Murphy 99, Montemerlo 02] Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 The FastSLAM Algorithm .2

.7 Sebastian Thrun Carnegie Mellon University .1 UAI Aug 2, 2002 FastSLAM - O(MN) Update robot particles based on O(M) control ut Constant time per particle

Incorporate observation zt into Kalman filters O(M) Constant time per particle O(MN) Resample particle set Linear time per particle M = Number of particles N = Number of map features Sebastian Thrun

Carnegie Mellon University UAI Aug 2, 2002 Ben Wegbreits Log-Trick n4? T new particle F n2? F T

n3? T F 3,3 [i] [i] n k4? T old particle F

n k2? T n k1? T 1[i],1[i] Sebastian Thrun F 2[i],2[i] n k6? F

T n k3? T 3[i],3[i] Carnegie Mellon University F n k1 5? T 4[i],4[i] 5[i],5[i] F

6[i],6[i] F n k3 7? T 7[i],7[i] UAI F 8[i],8[i] Aug 2, 2002

FastSLAM - O(M logN) Update robot particles based on control ut O(M) Constant time per particle Incorporate observation zt into Kalman filters Log time per particle Resample particle set

O(M logN) O(M logN) Log time per particle M = Number of particles N = Number of map features Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Advantage of Structured PF Solution Kalman: O(N2)

500 features FastSLAM: O(MlogN) Moores Theorem: logN 30 M: discussed later + global uncertainty, multi-modal + non-linear systems + sampling over data associations Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 3 Examples

Particles + Kalman filters Particles + Point Estimators Particles + Particles Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Outdoor Mapping (no GPS) 4 km excursion

With Juan Nieto, Eduardo Nebot, Univ of Sydney Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 With Juan Nieto, Eduardo Nebot, Univ of Sydney Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 3 Examples

Particles + Kalman filters Particles + Point Estimators Particles + Particles Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Indoor Mapping

Map: point estimators (no uncertainty) Lazy Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Importance of Particle Filters Non-probabilistic Sebastian Thrun Carnegie Mellon University

Probabilistic, with samples UAI Aug 2, 2002 Multi-Robot Mapping Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Multi-Robot Exploration DARPA TMR Texas

DARPA TMR Maryland With: Reid Simmons and Dieter Fox Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 3 Examples Particles + Kalman filters Particles + Point Estimators Particles +

Particles Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Tracking Moving Features With: Michael Montemerlo Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002

Tracking Moving Entities Through Map Differencing Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Map-Based People Tracking With: Michael Montemerlo Sebastian Thrun Carnegie Mellon University UAI

Aug 2, 2002 Autonomous People Following With: Michael Montemerlo Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Advantage of Structured PF Solution Kalman: O(N2) 500 features FastSLAM: O(MlogN)

Moores Theorem: logN 30 M: discussed now! + global uncertainty, multi-modal + non-linear systems + sampling over data associations Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Worst-Case Environment ? N landmarks

robot path Kalman filters: Maps (relative information) converges for linear-Gaussian case Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Relative Map Error (Simulation) Kalman Filter 250 particles

error steps Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Relative Map Error (Simulation) Kalman Filter 250 particles 100 particles error 2 particles

steps Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Robot-To-Map Error (Simulation) error Kalman Filter 250 particles 100 particles 2 particles steps

Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Summary Results O(N2) O(MN) O(M logN) O(logN) O(N2) O(logN) Scalable(?) solution to data association problem Sebastian Thrun

Carnegie Mellon University UAI Aug 2, 2002 Robotics Research Today Particle Filters In Robotics 4 Open Problems Sebastian Thrun Carnegie Mellon University UAI

Aug 2, 2002 Can We Factorize Better? Static Factorization Dynamic Factorization Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Example: Multi-Robot Localization [Fox et al, 99]

Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Example: Multi-Robot Localization Robot 1 poses x1 x1 x2 x2 xt

z2 x3 xt z1 observations map Sebastian Thrun ... x3 z2 x1 xt

z3 observations Robot 3 poses x3 z1 observations Robot 2 poses x2 m Carnegie Mellon University [Fox et al, 99] UAI

Aug 2, 2002 Dynamic Factorization ?? Task: calculate E[y|x] from samples error Robot y always use joint always factorize factorize dynamically optimal # samples Robot x Sebastian Thrun

Carnegie Mellon University UAI Aug 2, 2002 Can We Learn Control? : p ( xt | z 0..t , u 0..t ) u t 1 Not an MDP Not discrete or low-dimensional Not knowledge-free Only thing that matters in robotics Sondik 71,Littman/Kaelbling/Cassandra 96,

Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Implications for Planning & Control MDP Planner POMDP Planner N. Roy et al Sebastian Thrun Carnegie Mellon University UAI

Aug 2, 2002 Can we Exploit Procedural Knowledge? Programming Learning prob See DavidxAndres = {{10, 0.2}, and Stuart {11, 0.8}}; Russells AAAI paper prob y =this {{20, year!

0.5}, {21, 0.5}}; prob z = x + y; prob f = neuroNet(y); with Frank Pfenning, CMU Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 And Can We Actually Do Something Useful? See poster by Anguelov et al. Sebastian Thrun Carnegie Mellon University

UAI Aug 2, 2002 The Nursebot Project University of Pittsburgh School of Nursing Prof. Jackie Dunbar-Jacob Prof. Sandy Engberg Prof. Margo Holm Prof. Deb Lewis Prof. Judy Matthews Prof. Barbara Spier School of Medicine Prof. Neil Resnick Prof. Joan Rogers Intelligent Systems

Prof. Don Chiarulli University of Pittsburgh Computer Science Prof. Martha Pollack Carnegie Mellon University Computer Science, Robotics Prof. Sebastian Thrun Prof. Geoff Gordon Human Computer Interaction Prof. Sara Kiesler Financial Support National Science Foundation $1.4M ITR Grant $3.2M ITR Grant Sebastian Thrun

Carnegie Mellon University UAI Aug 2, 2002 The Nursebot Project Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002 Haptic Interface (In Development) Sebastian Thrun

Carnegie Mellon University UAI Aug 2, 2002 Wizard of Oz Studies By Sara Kiesler, Jenn Goetz Sebastian Thrun Carnegie Mellon University UAI Aug 2, 2002

Recently Viewed Presentations

  • Lesson 3-1: Area, Squares, and Square Roots

    Lesson 3-1: Area, Squares, and Square Roots

    Explore how the scale factor affects two-dimensional figures on a coordinate plane. TEK(S): I can use algebraic representations to represent dilations on a coordinate plane. (8.3C) I know which transformations remain congruent and which do not. (8.10B) I can model...
  • TwO- Column Proof - Dunkerton High School

    TwO- Column Proof - Dunkerton High School

    Continuing a two-Column proof. Begin by creating two columns; a statement column and a proof column. The first statement will ALWAYS be your given statement with the reasoning being given. The continuing statements will be from your reasoning from postulates,...
  • Year 09 - Mathematics - Unit 2 - Answers

    Year 09 - Mathematics - Unit 2 - Answers

    2.5 - Linear Sequences. Page 629. a. n. th term = 3. n + 2. The solution to the equation 3. n + 2 = 596 is . n = 198; which is a whole number. Therefore 596 is a...
  • Feeding Relationships - MR JEFF'S SECONDARY SCIENCE 1

    Feeding Relationships - MR JEFF'S SECONDARY SCIENCE 1

    What would the food web for these food chains look like? plants owl aphid blue tit ladybird plants moth owl blue tit plants vole stoat plants vole owl bluetit owl chiffchaff stoat vole plant aphid ladybird moth spider 1. Name...
  • Linear Regression Using MS Excel - University of Waterloo

    Linear Regression Using MS Excel - University of Waterloo

    Linear Regression Analysis Using MS Excel Tutorial for Assignment 2 Civ E 342 The Regression Analysis Procedure Step 1: Import Data to Excel Objective: Import original data to Excel.
  • SDG&E CARE and ESA

    SDG&E CARE and ESA

    For ESA-only campaigns (targeted marketing to CARE customers not yet served by ESA), SDG&E averaged a 34.8% open rate and a 4.8% click-through rate. Utility industry average is 25.9% open rate and 3.5% click-through rate.
  • violence - AP Psychology

    violence - AP Psychology

    OPERANT CONDITIONING. A form of associative learning in which the consequences of a behavior change the probability of a behavior's occurrence.. Also called instrumental learning. Active process; behaviors occur spontaneously; the learner decides whether or not to repeat behavior based...
  • Transnationalist - UC San Diego Social Sciences

    Transnationalist - UC San Diego Social Sciences

    Political Transnationalism between Ecuador Spain Cristina Fernández Gutiérrez