LN 6 Localisation I

Localisation

How a robot can tell where it is on a map

Mapping

Creating a representation of the surrounding environment using a variety of onboard sensors

Localisation Navigation Types

• Behaviour-based

• Map-based

Map Representations

1. Occupancy Grid Map

2. Line-based Map

3. Topological Map

Occupancy Grid Map

• The environment is divided into a grid of cells each marked as free or occupied

• Intuition: Like using graph paper to represent a space

• Characteristics: Discrete metric representation. Can be detailed but computationally intensive

Line-based Map

• Represents features likes walls and doors as lines

• Characteristics: Geometric and continuous metric representation

Topological Map

• Represents the environment as a graph, with nodes representing places and edges representing connections between them.

• Intuition: Like a subway map, showing stations and connections, but not precise distances.

• Characteristics: Focuses on connectivity rather than precise geometry. Less computationally demanding.

Factors for Choosing a Map Representation

• Task precision

• Sensor compatibility

• Computational limits

Localisation Belief Representation

How a robot represents its uncertainty about its position

Belief representation types

• Single-Hypothesis belief

• Multiple-Hypothesis belief

Single-Hypothesis Belief

• Robot maintains only one estimate of its current position and orientation.

• Assumes only one possible state is true.

• Intuition: The robot makes a single best guess of where it is.

• Pros: Simple and computationally fast.

• Cons: Risky

• Can be represented by a single probability distribution, like a Gaussian.

Multiple-Hypothesis Belief

• The robot maintains several possible estimates (hypotheses) of its position and orientation, each with an associated probability

• Intuition: The robot considers multiple possibilities simultaneously, acknowledging its uncertainty

• Pros: More robust to uncertainty and sensor noise

• Cons: Computationally more expensive

Local Localisation

• Estimates the robot's position and orientation relative to its previous position.

• Intuition: "How far did I just step and in which direction?"

• Sensors: Typically uses odometry (wheel encoders), gyroscopes, accelerometers.

• Techniques: Dead Reckoning.

Global Localisation

• Estimates the robot's position and orientation relative to a fixed world frame or map.

• Intuition: "Where am I on this entire map?"

• Sensors: Can use landmarks, beacons, GPS (outdoors), or map matching techniques.

• Techniques: SLAM (Simultaneous Localization and Mapping), Kalman Filters, Particle Filters.

Dead Reckoning

• Method for local localisation

• Estimates a robot’s position by integrating its previous position with measurements of its motion over time

Dead Reckoning process

1. Start with known initial position

2. At each time step

   1. Read sensor data

   2. Update orientation

   3. Update position

3. New position is updated position

Dead Reckoning Advantages

• Simple

• Works without external sensors

• Always available

Dead Reckoning Limitations

• Error accumulation (Drift)

• Sensitivity to noise and slip

Error Accumulation (Drift)

Small inaccuracies in distance and heading measurements, as well as wheel slippage or uneven terrain, accumulate over time. This leads to a growing discrepancy between the estimated position and the actual position.

Key Challenges in Localisation

• Uncertainty: Sensor measurements are never perfect.

• Noise: Random errors in sensor readings.

• Drift: Errors that accumulate over time, especially in dead reckoning.

• Limited Sensors: Robots may not have access to all types of sensors or may have sensors with limited range or accuracy.

• Dynamic Environments: Moving objects or changes in the environment can make localisation harder.

Sensor Fusion

• Combining data from multiple sensors to obtain a more reliable and accurate estimate of the robot’s state

• To overcome the limitations of individual sensors and improve localisation accuracy