Mapping and Localization (SLAM) in Robotics, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 8.4 Free with a free account

Mapping and Localization (SLAM) in Robotics

Introduction to Artificial Intelligence · Chapter 8: Perception, Robotics, and Hands-On AISection 8.4 · lesson 60 of 6913 min · free with a free account

← Lisp: The Language That Shaped Early AINext lesson: Designing and Programming Advanced Robotic Platforms →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

How robots build a map while working out where they are.

  • Define pose, localization, mapping and SLAM, and explain why odometry drift makes SLAM necessary
  • Compare odometry, lidar and cameras as sensors for SLAM
  • Apply a Kalman filter update and contrast it with a particle filter's belief
  • Explain how occupancy grids are built and how loop closure corrects accumulated drift

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,897 words). Read along, or search it.

Opening Question

Map First or Position First

Put a robot vacuum in a house it has never seen. To clean efficiently, it needs a map. To draw the map, it has to know where it was standing each time it sensed a wall. And to know where it's standing, it would like to compare what it sees against a map. Each need depends on the other. So which comes first, the map, or the position?

Key Terms

Pose, Localization, Mapping and SLAM

Start with what a robot needs to know. Its pose is its position and the direction it faces. On a flat floor, that's three numbers: x, y, and a heading angle. Localization is given a map, and estimates the pose. Mapping is given the poses, and estimates the map. SLAM is given neither: only sensor readings and motion commands. It estimates both at once: simultaneous localization and mapping.

Dead Reckoning

Small Heading Errors Pile Up

The core difficulty is that every measurement is noisy, and the errors pile up. A robot can track its own motion by counting wheel turns. That's called dead reckoning. But each step carries a small error: a wheel slips, or one wheel is slightly larger than the other. A small heading error is the worst, because it points every later step a little wrong. In a simulation, a robot drives around a ten-meter square, eighty steps of half a meter. Its heading drifts by only a fraction of a degree per step. Yet by the end, its estimate is off by 3.3 meters, and the path no longer closes.

Why Pose Matters

Drifting Poses Smear the Map

That matters for the map, because every scan is placed using the robot's estimated pose. If the pose drifts, scans land in the wrong spots, and walls come out doubled or smeared. Even a perfect sensor can't rescue a map built from a drifting pose. SLAM works by tying the pose and the map together, so that seeing the same landmark again corrects both. A SLAM system has two halves. The front end turns raw readings into motion estimates and matches. The back end finds the path and map that fit them best.

Sensors

Odometry, Lidar and Cameras

No single sensor is enough, and each one fails in its own way, so SLAM systems combine them. Odometry, from wheel counters and inertial sensors, measures the robot's own motion. It's cheap, fast and always available, but its errors build up, and wheels slip on wet floors. Lidar times a reflected laser pulse to measure distance, scanning a full circle. It's accurate to centimeters, and works in the dark. But it costs more, glass and mirrors confuse it, and a flat unit sees only one slice of the world. A camera is cheap, light and rich in detail, and can recognize places by appearance. But depth must be worked out, and lighting, blur and blank walls all hurt it.

Camera Depth

Stereo, Depth Cameras and Unknown Scale

A camera can recover depth in three ways. Two cameras side by side, stereo, judge distance from how far each point shifts between the views. A depth camera projects its own light, and measures how it returns. A single camera can estimate depth from its own movement, but only up to an unknown scale. A small nearby scene, and a large faraway one, can look identical.

Filter Cycle

Predict Then Update

To combine noisy sources, SLAM uses filters. Both kinds repeat a two-beat cycle. Predict: the robot uses its odometry to guess its new pose, and its uncertainty grows, because motion is noisy. Update: it compares what its sensors see with what it expected, and its uncertainty shrinks. The two kinds of filter differ in how they hold the belief about where the robot is.

Kalman Predict Step

Variances Add When the Robot Moves

A Kalman filter holds its belief as one bell-shaped curve: a middle value, and a spread. Here's a full cycle, for a robot in a corridor. Before moving, it believes it's at 10.0 meters, with a spread, a standard deviation, of 0.5. The variance, the spread squared, is 0.25. Odometry reports a move of 2.0 meters, with motion noise of variance 0.09. So the prediction is 12.0 meters. And the variances add: 0.34, a spread of about 0.58.

Kalman Update Step

Weighing the Lidar Reading by Confidence

Now the lidar sees a wall, known to sit at 20 meters, at a distance of 7.8. That puts the robot at 12.2 meters. But the reading has its own variance, 0.16. The filter weighs each source by its confidence. The gain K is the prediction's variance, over the total: 0.34 over 0.50, which is 0.68. The new estimate moves 0.68 of the way toward the reading: 12.0 plus 0.68 times 0.2, which is 12.14 meters. And the new variance is one minus 0.68, times 0.34: about 0.109, a spread of 0.33 meters.

Lessons and Limits

Combined Sources Sharpen the Belief

Two things stand out. The estimate lands between the prediction and the reading, closer to the one we trust more: the lidar. And the new spread, 0.33, is smaller than either source alone. Combining two independent sources always sharpens the belief. The limits: a Kalman filter assumes one bell-shaped peak, and it needs to know which landmark it's looking at. And in EKF-SLAM, which keeps every landmark in its state along with the robot's pose, the cost grows quickly as landmarks are added.

Quick Check

Fusing 5.0 and 5.6 Meters

Quick check. A different robot predicts it's at 5.0 meters, with variance 0.30. A sensor reading says 5.6 meters, with variance 0.10. Where does the Kalman filter put it? Pause, and work it out. At 5.45 meters. The gain is 0.30 over 0.40, or 0.75. So the estimate moves three quarters of the way toward the sensor: 5.0 plus 0.75 times 0.6. 5.30 is a plain average, which ignores confidence. 5.15 flips the weights, and leans toward the less trusted prediction.

Particle Filter

Move, Weigh and Resample

A particle filter holds its belief differently: as a cloud of many guesses, called particles. Each particle is one possible pose. Its cycle has three steps. Move every particle by the odometry reading, plus a little random noise. Weigh each particle by how well the sensor reading matches what that pose would see. Then resample: copy the heavy particles, and drop the light ones. Because the cloud can form several clumps, it can hold several different ideas of where the robot is.

Worked Example

Three Doors in a Corridor

Picture a corridor with three doors, at 3, 7 and 14 meters. The robot knows nothing at first, so its 300 particles are spread evenly. It sees a door. Particles near any of the three doors gain weight, and the cloud gathers into three clumps. Then it drives 4 meters. Particles from the doors at 7 and 14 now stand where there's no door. Particles from the door at 3 arrive at the door at 7. It sees a second door. That one clump keeps its weight, and the others shrink to a few stragglers. The share of particles near the truth grows from 8 percent, to 27, to 78.

Comparison

FastSLAM and the Two Filters

The same idea scales to full SLAM. In FastSLAM, each particle carries its own map. The cost: you need enough particles, and the work grows with their number, and with the size of the map. So: a Kalman filter keeps one efficient bell curve, with clear uncertainty, but it can't hold two guesses. A particle filter handles odd-shaped, many-peaked beliefs, but needs many particles.

Map Types

Grids, Landmarks, Graphs and 3D Maps

The map itself can take several forms. An occupancy grid marks each cell free, occupied, or unknown, or gives it a probability. It's the usual output of lidar, and great for planning paths, but its memory grows with the area. A landmark map lists landmark positions, each with its uncertainty. It's compact, and the natural partner of EKF-SLAM, but it says nothing about empty space. A topological map is a graph of places joined by paths, good for routes across large areas. And 3D maps, point clouds or meshes, suit drones and outdoor vehicles, but they're heavy to store.

Occupancy Grid

Free, Occupied and Unknown Cells

Here's how an occupancy grid is built from lidar rays. For each ray, the cells it passes through become more likely to be free. The cell where the ray ends becomes more likely to be occupied: something stopped it there. And the cells beyond stay unknown, because the ray never reached them. In one simulated scan from a single spot, that gave 93 free cells and 41 occupied ones, and left 42 unknown, in the shadows behind obstacles. They stay unknown until the robot moves.

Loop Closure

Pose Graphs Spread the Error Back

Even with good filters, small errors keep accumulating. The most powerful correction is loop closure: recognizing that the robot has returned to a place it visited before. Many systems store their estimate as a pose graph. Each node is a pose, and each link is a measured movement between two poses. A loop closure adds one more link, saying: this pose and that earlier pose are the same place. Then an optimizer adjusts all the poses at once, to satisfy as many links as possible. In the square-path simulation, the average error was 1.32 meters before loop closure, and the worst 3.26. After spreading the error back along the loop, the average was 0.05 meters, and the worst 0.11. That simulation is idealized. Its drift grows steadily, which makes it easy to remove. Real errors are messier.

Quick Check

A False Match Between Look-Alike Corridors

Quick check. A delivery robot works in a building with two corridors that look exactly alike, on different floors. On the second floor, it wrongly decides it's back at a spot on the first floor, and accepts the loop closure. Predict: what happens to its map? The whole map bends out of shape. The optimizer treats two different places as one, and bends every pose it can to satisfy that false link. It doesn't stop at the current pose, and it can't ignore the link, because it trusts it. That's why good systems check candidate matches carefully before accepting them.

Visual SLAM

Features, Matching and Place Recognition

Visual SLAM uses cameras as the main sensor, in four parts. First, find distinctive features in each image, corners and blobs that are easy to spot again. Second, match those features from one frame to the next. Third, work out how the camera moved, and where each feature sits in 3D, which gives a sparse map of landmark points. Fourth, recognize returning places by the overall look of an image, which supplies the loop closures. Well-known systems such as ORB-SLAM follow this pattern. Lidar SLAM gives accurate distances in the dark. Visual SLAM is cheap, and strong at recognizing places. So many robots fuse a camera, a lidar and an inertial sensor. If a dark room blinds the camera, the system keeps going.

Back to the Vacuum

Predict, Correct and Close Loops

Back to the robot vacuum in its new house. It doesn't choose between the map and the position. It predicts with its wheels, corrects with its sensors, and every time it recognizes a room it's seen before, a loop closure pulls the whole map back into shape.

Key Takeaways

SLAM in Summary

To sum up. SLAM estimates the robot's pose and the map together, because each is needed to find the other. Odometry is fast but drifts, lidar gives accurate distances, and cameras give rich detail but must work out depth and scale. A Kalman filter keeps one bell-shaped belief and sharpens it with each measurement. A particle filter keeps many guesses, and can hold several possibilities. And loop closure recognizes a return to a known place, and corrects drift across the whole path, as long as the match is real.

Think About It

Every Wall Drawn Twice

Here's something to think about. A robot's map shows every wall twice, slightly offset, as if two maps were laid on top of each other. Which part of the system would you suspect first, and what would you change?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Mapping and Localization (SLAM) in Robotics

What is SLAM in robotics?
SLAM, or simultaneous localization and mapping, is the problem of estimating a robot's pose and a map of its surroundings at the same time, using only sensor readings and motion commands. Localization assumes a map and estimates the pose, while mapping assumes known poses and builds the map. SLAM needs both at once, because scans placed with a drifting pose produce a smeared map, and a poor map makes the pose hard to find.
Why does odometry drift over time?
Odometry drifts because every step of dead reckoning carries a small error, and those errors accumulate. Wheels slip, or one wheel is slightly larger than the other, so the counted motion differs from the true motion. A small heading error is especially harmful because it points every later step a little wrong. In one simulation, a fraction of a degree per step left a robot 3.3 meters off after an 80-step square path.
What is the difference between a Kalman filter and a particle filter for robot localization?
A Kalman filter holds the robot's belief as one bell-shaped curve with a mean and a spread, while a particle filter holds it as a cloud of possible poses. The Kalman filter is efficient and gives a clear uncertainty, but it cannot hold two guesses at once. A particle filter can form several clumps, which helps when look-alike landmarks such as identical doors leave the position ambiguous, but it needs many particles.
What is loop closure in SLAM?
Loop closure is recognizing that a robot has returned to a place it visited before, and using that match to correct accumulated drift. In a pose graph, each node is a pose and each link is a measured movement. A loop closure adds a link saying two poses are the same place, and an optimizer adjusts every pose to satisfy the links. A false match, such as two identical corridors, can bend the whole map.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →