Chapter 5: Mobile Robot Localization

Question 1

4 Building blocks of navigation

Answer 1

• perception
• localization
• cognition
• motion control

Question 2

4 Building blocks of navigation

Perception

Answer 2

The robot must interpret its sensors to extract meaningful data.

Question 3

4 Building blocks of navigation

Localization

Answer 3

The robot must determine its position in the environment.

Question 4

4 Building blocks of navigation

Cognition

Answer 4

The robot must decide how to act to achieve its goals.

Question 5

4 Building blocks of navigation

Motion control

Answer 5

The robot must modulate its motor outputs to achieve the desired trajectory.

Question 6

5 Sources of odometric error

Answer 6

• Limited resolution during integration (time increments, measurement resolution, etc.)
• Misalignment of the wheels (deterministic)
• Uncertainty in the wheel diameter and in particular unequal wheel diameter (deterministic).
• Variation in the contact point of the wheel.
• Unequal floor contact (slipping, nonplanar surface, etc.)

Question 7

Key advantage of the multiple-hypothesis representation regarding position

Answer 7

The robot can explicitly maintain uncertainty regarding its position.

If the robot only acquires partial information regarding position from its sensors and effectors, that information can be conceptually incorporated in an updated belief.

Question 8

Robot Localization

2 Update steps

Answer 8

• Prediction (or action) update
• Perception (or measurement, or correction) update.

Question 9

Prediction update

Answer 9

The robot uses its prioprioceptive sensorts to estimate its configuration.

E.g. the robot estimates its motion using the encoders.

Question 10

Perception update

Answer 10

The robot uses information from its exteroceptive sensors to correct the position estimated during the prediction phase.

E.g. the robot uses a rangefinder to measure its current distance from a wall and corrects accordingly the position estimated during the prediction phase.

Question 11

Robot localization

Belief

Answer 11

A robot cannot measure its true pose. It can only know the best estimate of its pose.

The best guess about the robot state (pose) is called belief.

Denote the belief over a state variable xₜ by bel(xₜ):

bel(xₜ) = p(xₜ | z₁→ₜ , u₁→ₜ)

represents the probability of the robot being at xₜ given all its past observations z₁→ₜ and all its past control inputs u₁→ₜ.

Question 12

5 Ingredients of probabilistic map-based localization

Answer 12

• Initial probability distribution
• Map of the environment
• Data
• Probabilistic motion model
• Probabilistic measurement model

Question 13

5 Ingredients of probabilistic map-based localization

Initial probability distribution

Answer 13

bel(x₀)

In the case where the initial robot location is unknown, the initial belief bel(x₀) is a uniform distribution over all poses.

Conversely, if the location is perfectly known, the initial belief is a Dirac delta function.

Question 14

5 Ingredients of probabilistic map-based localization

Map of the environment

Answer 14

The environment map M = {m₀, m₁, ..., mₘ} must be known.

If the map is not known a priori, then the robot needs to build a map of the environment.

Question 15

5 Ingredients of probabilistic map-based localization

Data

Answer 15

For localizing, the robot needs to use data from its prioprioceptive and exteroceptive sensors.

Denote with zₜ the current reading from the exteroceptive sensor.

Denote with uₜ the reading from the prioprioceptive sensor or the control input.

Question 16

5 Ingredients of probabilistic map-based localization

Probabilistic motion model

Answer 16

The probabilistic motion model is derived from the kinematics of the robot.

In the noise-free case, the robot current location xₜ can be conputed as a function f of the previous location xₜ₋₁ and the encoder readings uₜ.

xₜ = f( xₜ₋₁, uₜ)

Question 17

5 Ingredients of probabilistic map-based localization

Probabilistic measurement model

Answer 17

This is derived directly from the exteroceptive sensor model. E.g. the error model of the laser, the sonar, or the camera.

The measurement function depends on the map M and the robot location xₜ.

zₜ = h(xₜ , M)

The measurement function h is typically a change of coordinates from the world frame to the sensor reference frame attached to the robot.

Question 18

3 types of localization problems

Answer 18

• Position tracking
• Global localization
• Kidnapped robot problem

Question 19

3 types of localization problems

Position tracking

Answer 19

The robot current location is updated based on the knowledge of its previous position (tracking).

This implies that the robot initial location is supposed to be known.

Additionally, the uncertainty on the robot pose has to be small. If the uncertainty is too large, position tracking might fail to localize the robot.

Question 20

3 types of localization problems

Global localization

Answer 20

Global localization assumes that the robot initial location is unknown.

This means that the robot can be placed anywhere in the environment - without knowledge about it - and is able to localize globally within it.

In global localization, the robot belief is usually a uniform distribution.

Question 21

3 types of localization problems

Kidnapped robot problem

Answer 21

The case where the robot gets kidnapped and moved to another location.

The kidnapped robot problem is similar to the global localization problem only if the robot realizes having been kidnapped.

The difficulty arises when the robot does not know it has been moved to another location and it believes it knows where it is but in fact does not.

The ability to recover from kidnapping is a necessary condition for the operation of any autonomous robouts and even more for commercial robots.

Question 22

Markov localization

Answer 22

Markov localization tracks the robot’s belief state using an arbitrary probability density function to represent the robot’s position.

In practice, all known Markov localization systems implement this generic belief representation by first tessellating the robot configuration space (x, y, θ) into a finite, discrete number of possible robot poses in the map.

Question 23

3 Key Assumptions of Markov localization

Answer 23

1. If an object in the map is detected, the measurement error can be described with a distribution that has a mean at the correct reading.
2. There should always be a nonzero chance that a range sensor will ready any measurement value.
3. In contrast to the above, there is a specific failure mode in ranging sensors whereby the signal is absorbed or coherently reflected, causing the sensor’s range measurement to be maximal. I.e. there is a local peak in the probability density distribution at the maximal reading of a range sensor.

Question 24

Markov assumption

Answer 24

The output xₜ is a function only of the previous state xₜ₋₁ and its most recent actions (odometry) uₜ and perception zₜ.

Question 25

Kalman filter localization

Answer 25

A special case of Markov localization.

Instead of using an arbitrary density function, the Kalman filter uses Gaussians to represent the robot belief bel(xₜ), the motion model, and the measurement model.

Question 26

Kalman filter shortcoming

Answer 26

The assumptions made by the Kalman filter to limit the choice of initial belief to a Gaussian, means that the robot initial location must be known with a certain approximation.

The robot cannot recover its position if it gets lost (in contrast with Markov).

Kalman filter addresses the position-tracking problem, but not the global localization or the kidnapped robot problem.

Question 27

Localisation problem

Answer 27

Tries to answer the question of how a mobile robot can know where it is in any given environment.

Question 28

Define

Pose

Answer 28

The location and rotation for the robot.

Question 29

Define

Dead Reckoning

A.k.a. odometry

Answer 29

The process the robot uses to calculate its current position, using a previously determined position and estimated speeds over an elapsed time.

Question 30

Sensor Aliasing

Answer 30

Uncertainty when different robot poses result in the same sensor values.

(e.g. when a robot moves parallel to the surface of an object).

Question 31

4 Main sources of uncertainty for a robot’s location

Answer 31

• Initial pose uncertainty as it’s not easy to know a robot’s start pose in an environment.
• Effector noise, a.k.a motion noise, motion uncertainty and actuator uncertainty.
• Sensor noise - the actual errors made by the sensor.
• Sensor aliasing when the environment looks similar from different positions.

Question 32

4 Steps of a Kalman Filter measurement update

Answer 32

1. Observation step. The robot collects actual sensor data and extracts appropriate features.
2. Measurement prediction. Based on its predicted position on the map. Consists in the features that the robot expects to observe from the position where it is.
3. Matching step. The robot computes the best matching between the features extracted during observation and the expected features selected during the measurement prediction.
4. Estimation step. The Kalman filter uses the information provided to update the robot belief state.

Question 33

Landmark-based navigation

Answer 33

Landmarks are generally defined as passive objects in the environment that provide a high degree of localization accuracy when they are within the robot’s field of view.

This navigation generally makes use of artificial markers that have been placed by the robot’s designers to make localization easy.

Question 34

2 phases for a landmark-based navigator

Answer 34

When a landmark is in view, the robot localizes frequently and accurately, using action update and perception update to track its position without cumulative error.

When the robot is in a no-landmark “zone”, then only action update occurs, and the robot accumulates position uncertainty until the next landmark enters the robot’s field of view.

The robot is effectively dead-reckoning from landmark zone to landmark zone.

Question 35

SLAM

Answer 35

Simultaneous localization and mapping problem

The aim of SLAM is to recover both the robot path and the environment map using only the data gathered by a robot’s prioprioceptive and exteroceptive sensors.

These data are typically the robot displacement estimated from the odometry and features (e.g. corners, lines, planes) extracted from laser, ultrasonic, or camera images.

Question 36

3 Types of errors that remain from a geometric pov

Answer 36

1. Range error
2. Turn error
3. Drift error

Question 37

Range error

Answer 37

Error in the Integrated path length (distance) of the robot’s movement (sum of the wheel movements)

Question 38

Drift error

Answer 38

Difference in the error of the wheels leads to an error in the robot’s angular orientation.