Skip to content
ShilpBot

AI for Robotics · Lesson 2 of 2

Path Planning and SLAM: How Robots Navigate

Understand how mobile robots build maps, work out where they are (SLAM), and plan collision-free routes using algorithms like A*, Dijkstra and RRT.

By ShilpBot Team · 9 min read · Updated

To travel from A to B, a mobile robot must answer three questions: where am I, what does the world look like, and what route should I take? These correspond to localisation, mapping and planning, and navigation systems combine all three.

Localisation: where am I?

Wheel encoders give an estimate of movement called odometry, but small errors accumulate and the estimate drifts. To correct drift, robots compare what their sensors see with what they expect. Probabilistic methods such as the Kalman filter and the particle filter combine noisy motion and sensor data to maintain a best estimate of position with a measure of uncertainty.

Mapping: what is around me?

Robots commonly store the world as an occupancy grid, a grid of cells in which each cell is marked free, occupied or unknown, usually as a probability. Other representations include feature maps, which store landmarks, and 3D point clouds.

SLAM: doing both at once

Mapping needs a known position, and localisation needs a known map. SLAM, short for simultaneous localisation and mapping, solves both together when the robot starts in an unknown place. As the robot moves it:

  1. Predicts its new position from odometry.
  2. Observes the environment with LiDAR or cameras.
  3. Matches observations against the map built so far.
  4. Corrects both its position and the map.
  5. Performs loop closure when it recognises a place it has seen before, which removes accumulated drift.

Visual SLAM uses cameras and LiDAR SLAM uses laser scans. Each has different trade-offs in cost, accuracy and robustness to lighting.

Path planning: how do I get there?

With a map and a position, the robot searches for a collision-free route.

AlgorithmIdeaStrengthsLimitations
DijkstraExplores outward from the start by lowest costFinds the shortest pathSlow on large maps
A*Dijkstra guided by a heuristic estimate to the goalFast and optimal with a good heuristicNeeds a discrete grid or graph
RRTRandomly grows a tree through free spaceWorks in high dimensions, such as robot armsPaths are not optimal and can be jagged
Potential fieldsGoal attracts, obstacles repelSimple and fastCan get stuck in local minima

Global and local planning

Most systems use two layers. A global planner finds an overall route on the known map. A local planner runs many times per second, following that route while reacting to unexpected obstacles such as a person walking past.

Putting it together

On a typical mobile robot, a LiDAR feeds SLAM, which produces a map and a position. A global planner computes a route, a local planner converts it into velocity commands, and the control loops from Control Loops and PID execute those commands on the wheels.

Tools to explore

The Robot Operating System (ROS) provides ready-made navigation and SLAM packages, and simulators such as Gazebo allow you to test algorithms without risking hardware.

Key takeaways

  • Odometry drifts, so robots correct it using sensor observations.
  • SLAM builds a map and estimates position at the same time.
  • A* is the standard choice for grid maps, and sampling methods like RRT suit complex, high-dimensional spaces.

Frequently asked questions

What does SLAM stand for?

SLAM stands for simultaneous localisation and mapping. It lets a robot build a map of an unknown environment while tracking its own position within that map.

Is A* always the best path planning algorithm?

A* is excellent for grid or graph search with a good heuristic, but it is not ideal for every problem. High-dimensional problems such as planning for a robot arm often use sampling-based methods like RRT.

Can a robot navigate without a map?

Yes, simple reactive robots follow rules such as wall following or obstacle avoidance without any map. Maps become important when a robot must plan efficient routes or return to specific places.