Objectives - faculty.cs.tamu.edu

Objectives - faculty.cs.tamu.edu

15a Localization, Mapping, Exploration Why is this a problem- cant you just use GPS or some sort of RFID beacons? How can you simultaneously map the world and be sure where you are? How do you explore new areas efficiently or at least consistently? What about labeling the map with objects and features or terrain? Landing of Columbus boringmordheimforum.forumieren.com 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 1 15a Specific Learning Objectives Motivation Local -Markov --EKF Global -Grid -MCL Dynamic

Summary Define the pose of a mobile robot Describe the difference between iconic and feature-based localization Define each term in: bel(xt)=f(bel(xt-1), ut, zt, m) Describe the three types of localization problems Describe the difference between the EKF, Grid, and Monte Carlo Localization algorithms and which of the three types of localization problems they are best suited for. Be able to describe the difference between localization and simultaneous localization and mapping Describe frontier-based and GVG based exploration Describe the symbol-ground problem List the possible uses of terrain data by a robot and the impact of terrain on its functions Give examples of two types of methods for proprioceptive terrain identification and exteroceptive terrain identification and limitations of each nd 2019 Robin Murphy Introduction to AI Robotics 2 Edition (MIT Press 2019) 2 15a

Outline Localization: where I am? Mapping: where have I been? Exploration: where havent I been? Semantic World Knowledge: what am/did I see? Note: this section incorporates additional material beyond Chapter 11 in the textbook 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 3 Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary Navigation Cartographer

How am I going to get there? Mission Planner Behaviors Behaviors Behaviors Behaviors 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) deliberative Where am I going? Mission planning Whats the best way there? Path planning Where am I? Localization Where have I been? Map making reactive

15a 4 15a LOCALIZATION 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 5 15a Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary Localization (Position Estimation)

Mobile robot localization is the problem of determining the pose of a robot relative to a given map of the environment- Thrun, Burgard, Fox Mobile robot localization is often called position estimation Assumes that there is some sort of a priori map and the robot is localizing itself relative to it 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 6 15a Localization Problems Why localization should be easy Just coordinate transform Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary

What makes localization hard Requires model of the robot, sensors and response to the environment Sensor noise (proprioceptive and exteroceptive) Must infer position from series of uncertain sensor readings Computationally expensive May not know initial position Dynamic environments where objects move (did I move or did Object A move?) Path or task may not support localization E.g., would be better to hug the walls (active localization) but less optimal for path planning 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 7 15a Indoors: Why Odometry is Insufficient Motivation Local -Markov --EKF

Global -Grid -MCL Dynamic Summary Black Is ground Truth, Purple is Measured Using shaft Encoders for D 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 8 15a Outdoors: GPS isnt Perfect Motivation Local -Markov --EKF

Global -Grid -MCL Dynamic Summary 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 9 15a GPS Errors Errors relating to satellites: Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary Orbital error (location of satellite) Satellite clock error (satellite internal timekeeping)

Atmospheric error: Ionospheric error (proportional to electron content), tropospheric error (variable moisture content) Multipath errors: GPS signal bounce off local obstacles Receiver noise: noise in the receivers circuitry Satellite geometry: jumps occur as satellites are blocked and new fix is obtained from new satellite set 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 10 15a Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary 3 Types of Localization LOCAL

(initial xt) GLOBAL (no initial xt) SUSTAINED UPDATES INTERRUPTED UPDATES (kidnapped) 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 11 15a Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary

3 Types of Localization is not the same as localization algorithms LOCAL (initial xt) Key: Maintain position tracking GLOBAL (no initial xt) SUSTAINED UPDATES Key: Converge to right place quickly INTERRUPTED UPDATES (kidnapped) Key: Notice that world is different 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 12 15a

Two Approaches Feature-based: use features extracted from raw data Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary Label and match corners, walls, whatever Less features, so less computation Hard to extract features reliably Iconic: use raw (or near raw) sensor readings Match observations to what would expect to see at a location Computationally intensive 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 13

15a Feature-Based Algorithms Markov Localization covers all three problems, though usually used for local Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary bel(xt)=f(bel(xt-1), ut, zt, m), where bel(x) : belief that the robot is at pose x Remember pose for 2D is: x=(x y q)T ut : control actions or what you told the robot to do zt : measurements or what the robot observed m 2019 Robin :Murphy map Introduction to AI Robotics 2nd Edition (MIT Press 2019)

14 15a Starts out equally unsure Senses door: could be any door Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary New bel of where are in world: 3 major possibilities As move forward, estimate of where is moves but gets wider Senses door Belief is mostly that at second door due to match to map

As move forward, estimate of where is moves but gets wider 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 15 15a How Would You Compute This? Extended Kalman Filter is most common Main idea: Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary z is the set of observations about the features (aka landmarks) Need an additional vector to represent which feature in z corresponds to what feature in the map m correspondence variables Try to minimize the first and second moments, covariance to get the correct pose and then use those statistics about how the robot is moving to predict result of next control action

EKF steps Prediction: where the robot will be, given the control action Correction: predict what it will measure at that location, take the difference, update the estimation for the next cycle 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 16 15a Impact of Errors on Prediction Small translation, rotational error Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary High rotation error High translation

error Large translation, rotational error 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 17 15a Can find distances to EKF Example corresponding landmarks Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary Less accurate 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 18

15a 2 Iconic Methods Grid-based localization Uses a grid as a tesselation of convex polygon Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary (Other algorithms use regular grid as way to store data) Computes the likelihood of all possible poses within that polygon given the observation and puts in a histogram In practice, use just a local sub-map which restricts applicability to local localization 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 19

15a Motivation Local -Markov --EKF Global -Grid -MCL Dynamic Summary 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 20 15a 2 Iconic Methods Grid-based localization Motivation Local -Markov --EKF Global -Grid

-MCL Dynamic Summary Monte Carlo Localization (MCL) Technically it is not restricted to raw sensor observations, but is typically used this way Scatters particles throughout space, then computes probability given the observation Adds more particles at the next update, while some particles die Fun fact: noise actually helps this method! 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 21 15a Starts out equally unsure Senses door: could be any door Motivation Local -Markov --EKF Global

-Grid -MCL Dynamic Summary New bel of where are in world: 3 major possibilities Generate new particles, delete others- more dense around most likely spots Senses door Assign importance to particles As move forward, estimate of where is moves but gets wider 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 22 15a Static v. Dynamic Environments People, changes introduce a hidden state in the model, therefore the algorithms break Motivation Local -Markov --EKF

Global -Grid -MCL Dynamic Summary Two fundamental techniques State augmentation: try to make the hidden state unhidden Have to estimate impact of people on observations Outlier rejection Depends on sensors, environment Ex. Eliminate surprisingly short readings 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 23 15a Motivation Local -Markov --EKF Global -Grid -MCL

Dynamic Summary Summary Mobile robot localization is the problem of determining the pose of a robot relative to a given map of the environment Localization algorithms are variants of Bayes Filter algorithms, where the belief in a pose is a function of the last pose and a motion model Motion model must contain at a minimum pose, control actions, map Iconic localization is more common than feature-based due to problems in reliably extracting features Feature-based localization historically has used EKF

Need correspondence variables to link observations to map In practice, Monte Carlo methods (MCL) dominate localization, both for iconic and feature-based Localization works very well for static environments with good models, but dynamic environments are difficult. State augmentation is incomplete and outlier detection hard to quantify 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) The results rely heavily on the ability to accurately sense the environment 24 15a MAPPING 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019)

25 Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary Navigation Cartographer How am I going to get there? Mission Planner Behaviors

Behaviors Behaviors Behaviors 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) deliberative Where am I going? Mission planning Whats the best way there? Path planning Where am I? Localization Where have I been? Map making reactive 15a 26 15a

SLAM Simultaneous localization and mapping Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary Recall that localization requires an a priori map Mapping is when you dont have a map, but you probably dont have localization either 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 27 15a Rao-Blackwellized Filtering

Dominant method in SLAM Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary If you know the path that the robot has taken, computing the maximum likelihood map is easy Its the map where the observations are consistent But you dont know the path, because that would be localization Let each particle contain a path and a local map (instead of only one version of the map) After each observation, update only the sensed area of the maps Use a tree to save all the particles forming the history of the current particles Each particle is computed independently of the others Will get pretty good map as go along, though probably several

possible paths When close the loop will get a better path estimate (closure will propagate backwards) 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 28 15a Rao-Blackwellized Filtering (Fox) Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 29 15a EXPLORATION

2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 30 15a Exploration Where HAVENT I been? Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary Can explore reactively (move to open area as per Donath), but wed like to create maps and be purposeful about it Two major methods Frontier-based

GVG 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 31 15a Frontier Based Exploration Robot senses environment Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary Borders of low certainty form frontiers Rate the frontiers Centroid

Utility of exploring (big? Close?) Move robot to the centroid and repeat (continuously localize and map as you go) 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 32 15a GVG Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary

2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 33 15a Keeps moving, ignores areas hard to get to Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 34 15a

Reaches deadend at 9, backtracks Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 35 15a Goes back and catches missing areas Motivation SLAM Exploration

-Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 36 15a Discussion of Exploration Both methods work OK indoors, not so clear on utility outdoors Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps

- Impact - Sensing Summary GVG Susceptible to noise, hard to recover nodes Frontier Have to rate the frontiers so dont trash 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 37 15a SEMANTIC WORLD KNOWLEDGE 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 38 15a Saphira Architecture Motivation SLAM Exploration -Frontier

-GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary Developed at SRI by Konolige, Myers, Saffioti Comes with Pioneer robots Behaviors produce fuzzy outputs, fuzzy logic combines them Has a global rep called a Local Perceptual Structure to filter noise Instead of RAPs, uses PRS-Lite 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 39 15a

Saphira and LPS Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 40 15a Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain

- Maps - Impact - Sensing Summary 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 41 15a Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary Symbol-Grounding Problem Computers (and AI) reasons using symbols Ex. room, box, corner, door

Robots perceive raw data How to convert sensor readings to these labels? 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 42 15a Spatial World Knowledge What do you see? Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary How could a robot reliably extract the

same labels? 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 43 15a Terrain What does terrain mapping mean? Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary Terrain Maps Types Elevation-oriented Imagery Mostly manual interpretation

Usually terrain mapping means getting elevation data But in robotics, elevation maps are available so its more about mapping things that arent elevation 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 44 Components of a Terrain Map 15a US Army Field Manual FM5-33 Terrain Analysis Natural terrain Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary

Surface configuration: landforms, relief, slope or gradient Vegetation features Soil features Water features Man-made features Urban areas Transportation: highways, railroads, bridges, culverts, tunnels, ferries, fords, shipyards, naval bases, landings, airfields 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 45 15a DTED Maps Digital Terrain Elevation Data (DTED)

Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary Produced by NIMA (National Imagery and Mapping Agency) Shuttle created at least level 1, 2 Levels 3-5 are classified by US But <10m data sets are commercially available DTED Level Post Spacing 1 100m 2 30m 3 10m 4 3m 5 1m 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 46 15a

Redux: Navigation Mission A priori knowledge Cartographer & World model Mission Planner Navigator Pilot deliberative reactive behavior behavior behavior behavior behavior SENSORS ACTUATORS 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019)

47 15a NHC Navigation Planning Reasons about goals, ROE Path Planning, any navigational constraints Instantiates behaviors & monitors progress 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 48 15a Summary SLAM works well for indoors, especially if range scans and multiple loops through an area

Motivation SLAM Exploration -Frontier -GVG Sym-Grnd Terrain - Maps - Impact - Sensing Summary Frontier-based and GVG are two types of exploration, but not necessarily as intuitively efficient as might be expected Symbol-ground problem remains a general challenge for AI and existing solutions are limited, highly domain specific Terrain maps are available at low resolutions which are good for planning but terrible for execution Outdoor navigation requires being able to sense terrain, but no reliable proprioceptive or exteroceptive methods, though proprioception appears more promising in the short term 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 49 15a

SLAM Why is this a problem- cant you just use GPS or some sort of RFID beacons? GPS is only for outdoors, RFID beacons for indoor encounter transmission problems How can you simultaneously map the world and be sure where you are? You can use probabilistic methods to be reasonably certain where you are How do you explore new areas efficiently or at least consistently? Generally use some type of frontier-based exploration method What about labeling the map with objects and features or terrain? Adding semantics to a map is part of the symbol-ground problem or general recognition problem Some work has been done in terrain labeling but not a lot. 2019 Robin Murphy Introduction to AI Robotics 2 nd Edition (MIT Press 2019) 50

Recently Viewed Presentations

  • Safe Schools/Healthy Students Grant Initiative Teen ...

    Safe Schools/Healthy Students Grant Initiative Teen ...

    Title: Safe Schools/Healthy Students Grant Initiative Teen Leadership Experience New Hanover County, North Carolina Year One Report UNCW Evaluation Team
  • Research and Education on Lighting Laboratory D.Sc. Eino

    Research and Education on Lighting Laboratory D.Sc. Eino

    Research and Education on Lighting Laboratory D.Sc. Eino Tetri [email protected] Lighting Laboratory Helsinki University of Technology Department of Electrical and Communications Engineering Staff: 23 people working in education and national and international research projects Research and education include areas related...
  • E/L/G 0300: Intermediate Incident Command System for ...

    E/L/G 0300: Intermediate Incident Command System for ...

    An after-action review answers the following questions: What did we set out to do? What actually happened? Why did it happen? What are we going to do differently next time? Are there lessons learned that should be shared? What follow-up...
  • World History - Jenks Public Schools

    World History - Jenks Public Schools

    World History The Early Beginnings of Mankind ... Know Prehistory Anthropology Archaeology Paleontology Artifacts Hominid Radiocarbon Dating Used to determine the age of artifacts and fossils "Lucy" was unearthed in 1974 by Donald Johanson Radiocarbon dated to 3.2 million years...
  • Where we started

    Where we started

    Also, my presentation is on the Web, and the URL is on the handout. CIMTech - lab, faculty development center 8 computers, mixed platform, and lots of development toys Had paid printing, but it had to be a special card...
  • Presentazione standard di PowerPoint

    Presentazione standard di PowerPoint

    45% reduction in age-adjusted prostate cancermortality. Similartrends in World HealthOrganization data wherePSA screening ispracticed. Sicuramente l'uso del PSA ha permesso di raggiungere una riduzione pari all'80% dei casi presentatesi con un disseminazione metastatica ed un'altrettanta riduzione della mortalità.
  • MILLER/SPOOLMAN LIVING IN THE ENVIRONMENT Chapter 8 Aquatic

    MILLER/SPOOLMAN LIVING IN THE ENVIRONMENT Chapter 8 Aquatic

    Major Life Zones and Vertical Zones in an Ocean. Figure 8.6: This diagram illustrates the major life zones and vertical zones (not drawn to scale) in an ocean. Actual depths of zones may vary. Available light determines the euphotic, bathyal,...
  • MEKANİK VENTİLASYON MODLARI - WordPress.com

    MEKANİK VENTİLASYON MODLARI - WordPress.com

    Airway Pressure Release Ventilation (APRV) Uygulayıcı iki farklı düzeyde basınç ve bu basınçlarda kalma süresini belirler. (Phigh-Plow/t high-t low) Her iki seviyede hasta spontan soluyabilir. ALI/ARDS hastalarında, massif atelektazisi olan hastalarda kullanılır.