AI Notes
Master navigation. Localization, mapping, SLAM. Robotics 2024.
What is Robot Navigation?
Robot navigation is the capability of a mobile robot to determine its position in the environment and plan a path to reach a desired destination. It answers three fundamental questions: "Where am I?" (localization), "Where am I going?" (goal specification), and "How do I get there?" (path planning and execution). Navigation integrates sensing, mapping, localization, planning, and control into a coherent system that enables autonomous movement.
The Navigation Stack
Localization: Where Am I?
Odometry (Dead Reckoning)
Monte Carlo Localization (Particle Filter)
Represent position belief as set of particles
Each particle = (x, y, θ, weight)
1000-5000 particles spread across possible positions
Algorithm
1. PREDICT: Move all particles according to motion model + noise
2. UPDATE: Weight particles by sensor likelihood
particle near wall + sensor sees wall → high weight
particle in open space + sensor sees wall → low weight
3. RESAMPLE: Duplicate high-weight particles, remove low-weight
Over time: particles converge to true position
Even handles "kidnapped robot" problem (global localization)
SLAM (Simultaneous Localization and Mapping)
Chicken-and-egg problem
Need map to localize → but need location to build map!
SLAM solves both simultaneously
- EKF-SLAM: Extended Kalman Filter (landmarks)
- GraphSLAM: Optimize pose graph (loop closures)
- ORB-SLAM: Visual features from camera
- LiDAR SLAM: Point cloud matching (most accurate)
Loop closure: Recognizing previously visited location
Corrects accumulated drift in one step
Critical for consistent maps
Mapping
Occupancy Grid Maps
| Each cell | probability of being occupied P(occupied) |
| Laser hits cell | increase P(occupied) |
| Laser passes through cell | decrease P(occupied) |
| Result | 2D map with clear/occupied/unknown cells |
| Used by | Roomba, warehouse robots, most mobile robots |
Topological Maps
Advantages
- Graph of distinctive places (nodes) and paths (edges):
- Kitchen ←→ Hallway ←→ Bedroom ←→ Bathroom
- Advantages: Compact, enables high-level planning
- "Go from kitchen to bedroom" → [kitchen, hallway, bedroom]
- Combine with metric maps for best results
Disadvantages
Obstacle Avoidance
Dynamic Window Approach (DWA)
| 4. Score remaining by | heading toward goal + speed + clearance |
| Works for | differential drive robots, holonomic bases |
| Handles | moving obstacles (replans each cycle) |
Vector Field Histogram (VFH)
Worked Example: Complete Navigation Task
| Task | Robot in office, navigate from Room A to Room C |
| Phase 1 | Localization |
| Start | Robot uncertain about position |
| Scans room with LiDAR | matches features against map |
| Particle filter converges | position: (3.2, 7.1, 45°) |
| Phase 2 | Global Planning |
| Goal | Room C entrance at (15.4, 2.3) |
| A* on occupancy grid | path through hallway |
| Waypoints | [(3.2,7.1), (3.2,5.0), (8.0,5.0), (15.0,5.0), (15.4,2.3)] |
| Phase 3 | Local Execution |
| At waypoint 3 | unexpected person in hallway |
| Person passes | resume planned path |
| Phase 4 | Goal Reached |
| Final approach | slow down, align with door |
| Localization confirms: within 0.1m of goal | SUCCESS |
Navigation in Different Environments
| Environment | Challenge | Solution |
|---|---|---|
| Indoor (office) | Narrow doors, furniture | 2D LiDAR SLAM + occupancy grid |
| Outdoor (sidewalk) | GPS, uneven terrain | GPS + visual odometry + 3D map |
| Underground | No GPS, dark | LiDAR SLAM + IMU fusion |
| Dynamic (crowd) | Moving obstacles | Prediction + reactive planning |
| Multi-floor | Elevators, stairs | Topological map + floor detection |
ROS Navigation Stack
| - Costmap (local + global) | environment representation |
| - Global planner | Dijkstra/A* on global costmap |
| - Local planner | DWA on local costmap |
| - Recovery behaviors | rotate, backup if stuck |
| amcl node | Adaptive Monte Carlo Localization |
| map_server | Loads pre-built map (from SLAM) |
| sensor drivers | LiDAR, camera, IMU data |
Interview Questions
Q: How does a robot navigate without GPS (indoor)? A: Through SLAM (build map + localize simultaneously using LiDAR/cameras), or localization against a pre-built map using sensor matching. The robot compares current sensor readings against stored map features to determine position, then plans paths through known free space. Odometry provides short-term position tracking between sensor updates.
Q: What is the difference between global and local planning? A: Global planning uses the full map to find a path from start to goal (Dijkstra/A*—runs infrequently, produces waypoints). Local planning handles immediate obstacles and dynamics (DWA—runs at 10-20Hz, generates motor commands). Global planning says "go through the hallway"; local planning says "steer left to avoid that person."
Q: How does a robot handle dynamic environments? A: Through constant replanning. The local planner runs at high frequency (10-20Hz), incorporating latest sensor data. If an obstacle appears, the next planning cycle automatically avoids it. For predictable moving objects (people walking), prediction models estimate future positions and plan proactively around predicted paths.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Robot Navigation - Autonomous Movement.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.
Search Terms
artificial-intelligence, artificial intelligence, artificial, intelligence, robotics, robot, navigation, robot navigation - autonomous movement
Related Artificial Intelligence Topics