Lecture7 Localization

Lecture 7: 

Lecture 7 Localization 29 March, 2005

Quiz 4: 

Quiz 4 List two possible task requirements in designing a manipulator List two different kinematic manipulator configurations. What is the primary benefit of a 3-axis intersecting wrist? List two advantages of parallel manipulators over serial manipulators. List two advantages of serial manipulators over parallel manipulators.

Overview: 

Overview What is localization? Dead-reckoning Landmarks To localize or not to localize? Belief representation Case study

What is localization?: 

What is localization? Answers the question “where am I”. Localization Cognition Motion control Perception Real world Where am I? Do it. What do I know? Where am I going? How do I get there?

Dead reckoning: 

Dead reckoning Odometry: wheel sensors only Dead reckoning: also heading sensor Integrate robot motions to determine position Major sources of error: Limited resolution of time increments and measurements Wheel misalignment Unequal wheel diameter Variation in wheel contact to floor Unequal floor contact

Dead reckoning: 

Dead reckoning Integration errors Range error: integrated path length = sum of wheel movements Turn error: similar to range but for turns = difference of wheel motions Drift error: difference in error of the wheels leads to error in angular orientation Over time, turn and drift errors outweigh range errors (Fig 5.4) Typically use only over small distances

Landmarks: 

Landmarks A unique feature in the world Passive/active, natural/artificial Piloting = navigating with respect to external landmarks Landmark should be Visible from various positions and readily recognizable Support the task activity Stationary or of a known motion Examples: buildings, mountains, lakes brightness of sky, wind direction, sound from a direction

Landmarks in nature: biology’s perspective: 

Landmarks in nature: biology’s perspective Humans, ants, bees, birds All able to navigate reliably over long distances Can cope with modified, inconsistent environments Local or global landmarks Dead-reckoning Mixture

Nature’s navigation: local landmarks: 

Nature’s navigation: local landmarks Desert ants Use angular extent of local landmarks (diagram, pg 102) Honey bees Also use angular extent of local landmarks. Appear to remember what they saw when last at their destination. Introduction/removal of artificial landmarks stops foraging and they make orientation flights Similarly, make reconnaissance flights in unknown territory before foraging Sometimes use prominent landmarks, e.g. trees on dogleg route.

Nature’s navigation: global landmarks: 

Nature’s navigation: global landmarks Not always have local landmarks Desert ants with no landmarks Search pattern after ~10% overshoot on intended destination Purely dead-reckoning (no pheromone trail) Appear to use polarization pattern of blue sky, a relatively unchanging pattern over short time. Sky pattern gives rotation about vertical axis. Bees Use sun position and polarization pattern of sky (diagram pg105) Birds Experiments in planetariums show use stars for navigation In particular, apparent rotation of entire sky around celestial pole. Unaffected even if shown incorrect, artificial star constellations.

Nature’s navigation: dead-reckoning: 

Nature’s navigation: dead-reckoning Geese dead-reckon if can see where are going Do not retrace detoured route Apparently use optic flow Human maritime navigation “Sailing the parallels” to reduce turn error Polynesian’s steered canoes parallel to, or across, waves. Slight deviations cause easily detected roll.

Nature’s navigation: birds and humans: 

Nature’s navigation: birds and humans Bird can navigate long distances from unknown sites Magnetic compass: towards/away from equator Sun compass: learned, geographically dependent Hypotheses that use navigation maps for medium/long distance navigation, possibly landmarks close to home Polynesian navigators Capable of multi-thousand km journeys over open ocean Initially landmark based: stars, sun, and island landmarks Use wave and wind patterns to maintain accurate heading Clouds, birds, sky color for final destination vectoring Conclusion: multiple input sources

Landmarks: triangulation : 

Landmarks: triangulation Depends on whether get bearing or distance measurements Simple triangulation (Fig 7.1) Triangulation by bearings (Fig 7.2) Complicated by uncertainty (Fig 7.3) Landmark selection Typically prefer closer landmarks to more distant ones Want good angular separation May use knowledge of the type of error

Landmark example: QualNav: 

Landmark example: QualNav DARPA Autonomous Land Vehicle (late ‘80s) Use landmarks to localize to an ‘orientation region’ (a patch of the world) Orientation region bounded by ‘landmark pair boundaries’ Within an orientation region, landmarks appear in fixed order (Fig 9.9) Vehicle can directly perceive landmark pair boundaries when landmark pair transitions from being in front, to on the side, to behind What happens if a landmark disappears?

Perceptual aliasing: 

Perceptual aliasing Perceptual aliasing = many locations look alike Can not assume unique perceptual signatures Combat by Use more sensor information from more sensor modalities Limited amount of additional information can add Increased acuity implies increased sensitivity to fluctuations Use history of sensor readings One freak input may affect many following inputs Must visit identical history Requires large amounts of storage Combine dead-reckoning with landmarks Only useful if know roughly where are at start

To localize or not to localize?: 

To localize or not to localize? How to get between two locations Navigate without hitting anything Reliably detect goal location Follow left wall???

Behavior based navigation: 

Behavior based navigation Use procedural solutions Quick and easy to develop Disadvantages Does not scale to new or larger environments The left-wall-follow behavior must be very accurate Requires much fine-tuning between multiply active behaviors

Model based navigation: 

Model based navigation Use position relative to map of environment Easily transparent to human operators Map is communication medium between humans and robot Disadvantages Robot implicitly trusts map Requires much more up-front development effort

Belief representation: 

Belief representation Robot has to represent its belief in where it thinks it is Single unique position (Fig 5.9) No position ambiguity eases decision making Challenge is to always generate a single position hypothesis Multiple positions Provides explicit representation of position uncertainty Can allow robot to reason about its future belief state Can be hard to decide where to go next Computationally very expensive

Case study: FIDO rover: 

Case study: FIDO rover NASA’s technology development rover Support for MER rovers Numerous field trials 6 wheel rocker-bogie suspension Sensors Numerous cameras (hazard, panoramic, navigation) Sun sensor Inertial measurement unit

FIDO: 

FIDO Driving consists of Arc turns based on Ackerman steering Straight drives Turn-in-place motions Rover state = planar position and heading State equations Have to deal with estimated wheel travel, based on estimated wheel slippage on the left and right sides Utilizes velocity synchronization algorithm to minimize power draw, minimize wheel slippage, and reduce side-slip tendency

FIDO localization: 

FIDO localization Estimates inertial unit bias with regular Kalman filter (while stationary) Integrates state equations to give dead-reckoned position estimate Fuses dead reckoning from wheel odometry and inertial unit output, using extended Kalman filter (while moving) Regularly updates rover heading using sun sensor

FIDO algorithm: 

FIDO algorithm

FIDO: localization results: 

FIDO: localization results JPL’s indoor rover pit (all except sun sensor) Rover commanded to follow a 1m box Individual runs, 2-3 cm error in X and Y (0.84% error over entire 4m distance) Accumulated error over all runs, 13.5 cm in X and -5.0 cm in Y (0.72% error over entire 20m distance) Science accuracy for manipulator placement is +/- 10cm in position and +/- 2 degrees in orientation For extended runs, would be 100m: close to 1m (approximately rover size) 1 km: close to 10m

Summary: 

Summary Localization is attempting to determine position Typically use multiple input sources Dead-reckoning Landmarks Must deal with sensor noise, perception ambiguity Have to represent belief in where robot thinks it is, either as single or multiple positions

References: 

References “Introduction to Autonomous Mobile Robots”, R Siegwart and I Nourbaksh, Bradford “Mobile Robotics: A Practical Introduction”, U Nehmzow, Springer “Computational Principles of Mobile Robotics”, G Dudek, M Jenkin, Cambridge University Press “Introduction to AI Robotics”, R Murphy, Bradford “Rover Localizaton Results for the FIDO Rover”, E Baumgartner, H Aghazarian, A Trebi-Ollennu, SPIE Photinics East Conference, October, 2001.