Skip to the lesson
FixTheRobot Explore Robotics / Navigation / M1 Navigation Foundations / M1-T1

Navigation · Theory · M1

M1-T1 — What Is Robot Navigation?

Getting from here to there sounds like one problem. It is six, running at different speeds, and a failure in any of them looks like “the robot is stuck”.

  • Lesson 1 of 6
  • Module 1: Navigation Foundations
  • Theory
  • About 9 minutes to read

Navigation is what turns a goal such as “bring this to room 214” into wheel commands that arrive safely, again and again, in a world that keeps changing. The hard part is not any single algorithm. It is that several modules must agree with each other while a robot is moving, and that when they disagree the symptom is the same: the robot stops, weaves or gives up.

Learning objectives

After this lesson, you should be able to:

  • Describe navigation as a loop of sensing, localizing, mapping, planning, controlling and recovering.
  • State the navigation problem: reach a goal, avoid obstacles, respect the robot’s dynamics, and keep the cost low.
  • Explain why navigation needs a slow global planner and a fast local one.
  • Compute how far a robot travels during its sensing and computing delays, and use that to bound its safe speed.

The intuition

Imagine walking to a friend’s flat in an unfamiliar city. You do several things at once without naming them. You look around (sensing). You work out which street you are on (localization). You hold a picture of the streets and the cars (mapping). You pick a route (planning), and with each step you decide where to put your foot, dodging a pushchair as you go (control). If the road is closed you try another (recovery).

A robot has to do each of these explicitly, in software, and each one can fail on its own.

The navigation loopSix boxes in a loop: sense, localize, map, plan, control, act. A seventh box, recover, sits below and connects back to plan and control.SenseLiDAR, camera, IMU Localizewhere am I? Mapwhat is around? Planwhere, and how? Controlwhich command? Actwheels move the world changes, so the loop never stops Recoverstuck? lost? blocked? try something else
The navigation loop. The first three boxes answer “where am I and what is around me?”, the next two answer “where should I go and how?”, and recovery is what happens when the loop stops making progress.
StageThe question it answersWhat it hands onHow it typically fails
SenseWhat do my sensors say right now?Scans, images, wheel and inertial readingsNoise, dropouts, glass and dark surfaces, wrong timestamps
LocalizeWhere am I on the map?A pose with an uncertaintyDrift, jumps, being lost in a repetitive corridor
MapWhat is free, blocked or unknown?A costmap the planner can useStale obstacles, missing obstacles, wrong inflation
PlanWhich route reaches the goal?A path from here to the goalNo path found, a path through a gap that is too tight, a detour that is too long
ControlWhich command follows the path now?Wheel speeds or velocity commandsWeaving, corner cutting, oscillation, saturation
RecoverWhat do I do when I am stuck?A different action: wait, clear, back up, ask for helpRetrying the same thing forever

The mathematics

Stated precisely, the problem has a state, a goal set, forbidden regions, dynamics, limits and a cost.

find controls u(t), t in [0, T], such that

x˙=f(x, u)\dot{x}=f(x,\,u)
the robot obeys its dynamics
x(0)=xstartx(0)=x_{\text{start}}
x(T) in Xgoalx(T)\,\text{in}\,X_{\text{goal}}
it ends at the goal
x(t) not in Xobstacle for all tx(t)\,\text{not in}\,X_{\text{obstacle}}\,\text{for all}\,t
it never touches anything
∣v ∣≤vmax⁡, ∣a ∣≤amax⁡\lvert v\,\rvert \le v_{\max},\,\lvert a\,\rvert \le a_{\max}
speed and acceleration limits
and J=integral of cost⁡(x, u) dt is small\text{and}\,J=\text{integral of}\,\operatorname{cost}(x,\,u)\,\text{dt is small}
x
the robot’s state, for a mobile robot usually its pose (x, y, θ) and maybe its speed.
u
the control: forward speed and turn rate, or speed and steering angle.
f(x, u)
the dynamics: how the state changes under a control. Lesson M1-T3 gives the common models.
Xgoal, Xobstacle
the set of acceptable end states and the set of forbidden states.
J
the cost to minimize: usually some mix of time, distance, energy, closeness to obstacles and discomfort.

Two clocks: global and local

Solving this in one step is possible for toy problems and hopeless for a robot in a building. The map is large, the robot must decide in milliseconds, and the world is not what the map said. So navigation splits the problem in two.

  • Global planning looks at the whole known map, runs about once a second or only when needed, and produces a path that is long but approximate.
  • Local planning and control look a few metres ahead, run ten to fifty times a second, and turn the path into commands while reacting to what the sensors see now.

The two must agree. If the global planner sends the robot through a gap that the local costmap treats as blocked, the robot reaches the gap and stops. A great deal of practical navigation work is making the two layers see the same world.

Assumptions this track makes

  • A mobile robot on a mostly flat floor, described in 2D. Legged, aerial, marine and off-road robots are discussed in module 9.
  • A map exists or is being built (see the Localization and SLAM track). This track is about using it.
  • Obstacles are mostly static, and some move. Moving obstacles are the subject of module 6.

A worked example

Scout in a corridor. Scout drives at v = 1.0 m/s. Its LiDAR delivers a scan every 100 ms, perception and costmap update take 60 ms, the local planner takes 50 ms, and the motor controller adds 100 ms before the wheels respond. A person steps out of a doorway. How close can they be when Scout first sees them, if it is to stop without touching them?

Latency budget
latency=100+60+50+100 ms=310 ms=0.31 s\text{latency}=100+60+50+100\,\mathrm{ms}=310\,\mathrm{ms}=0.31\,\mathrm{s}
distance during latency=v×latency=1.0×0.31=0.31 m\text{distance during latency}=v\times \text{latency}=1.0\times 0.31=0.31\,\mathrm{m}
braking distance(a=1.0 m/s2)=v22a=1.02.0=0.50 m\text{braking distance}(a=1.0\,\mathrm{m}/\mathrm{s}^{2})=\frac{v^{2}}{2a}=\frac{1.0}{2.0}=0.50\,\mathrm{m}
minimum detection distance=0.31+0.50=0.81 m\text{minimum detection distance}=0.31+0.50=0.81\,\mathrm{m}

Scout must be able to see an obstacle at least 0.81 m ahead to stop in time at 1.0 m/s. The numbers also show how to improve things. Halving the speed to 0.5 m/s cuts the latency distance to 0.155 m and the braking distance to 0.125 m, a total of 0.28 m, nearly three times less. Speed enters the stopping distance twice, once through latency and once squared through braking. Module 7 turns this into a full safety margin.

The same arithmetic shows why the global planner can be slow. At 1.0 m/s and one replan per second, the robot has moved 1.0 m between plans, which is fine for a route but far too coarse for dodging a person.

Engineering implications and limitations

Observe each stage separately

A navigation failure rarely says which part failed. The robot is stopped in a corridor whether the cause is a stale obstacle in the map, a localization jump, or a controller that cannot follow the path. The first engineering habit is to make each stage observable: log the pose and its covariance, publish the costmaps, record the path and the commands, and keep timestamps on all of them. Lab M1-L1 practises reading such a record.

Interfaces are where bugs live

Each stage trusts the one before it. The planner trusts the costmap, the controller trusts the path, the costmap trusts the pose. When a stage is wrong, every stage after it inherits the error and may amplify it. This is why modules in this track keep returning to consistency: the same footprint, the same frames, the same costmap, the same units.

Limits of this view

The loop is a useful model, not the only architecture. Some systems plan and control together (model predictive control over a costmap), and learned systems may skip the map entirely. Even then, the same questions have to be answered somewhere, and the failures look similar.

Common misconceptions

“Navigation is path planning.”

Planning is one stage of six. Plenty of failed runs have a perfect plan and fail in localization, the costmap or the controller.

“If the plan is correct the robot will arrive.”

A path is a suggestion. The robot has to localize against it, follow it with limited acceleration, and react to things the plan did not know about.

“A faster algorithm makes the robot faster.”

Speed is usually limited by how far the robot can see and how quickly it can stop, not by how fast the planner runs.

“More sensors fix navigation.”

More data that disagrees makes the localization and costmap problems harder. Sensors help when each one covers a failure of another.

Engineering takeaways

  1. Navigation is a loop of sensing, localizing, mapping, planning, controlling and recovering. Learn where each can fail.
  2. The problem is to reach a goal while avoiding obstacles, obeying dynamics and limits, and keeping a cost low.
  3. A slow global planner and a fast local planner work together, and must see the same world.
  4. Sensing and computing delays turn into distance. Safe speed follows from detection distance, latency and braking.
  5. Make every stage observable, because a failure looks the same whichever stage caused it.

References and further reading

Textbooks and the paper behind the Nav2 navigation system.

  • R. Siegwart, I. Nourbakhsh and D. Scaramuzza, Introduction to Autonomous Mobile Robots, 2nd ed., MIT Press, 2011.
  • S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, MIT Press, 2005.
  • S. LaValle, Planning Algorithms, Cambridge University Press, 2006 (free online).
  • S. Macenski, F. Martín, R. White and J. Ginés Clavero, “The Marathon 2: A Navigation System”, IEEE/RSJ IROS, 2020.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

A robot drives smoothly down a corridor and then stops 1 m short of a doorway, although the planner reports a valid path through it. Name two stages that could be responsible and what you would look at first.

Explanation

The planner and the local costmap or controller may disagree about the doorway, for example because the local costmap inflates the walls so the gap looks blocked. Look at the global path and the local costmap side by side in the same frame, and at the controller’s log for “no valid command”. Localization is a third suspect: if the pose is off by 1 m the doorway is in the wrong place relative to the robot.

Question 2

At 2.0 m/s the same robot has 0.31 s of latency and can brake at 1.0 m/s². By how much does the minimum detection distance grow compared with 1.0 m/s, and why is it more than double?

Explanation

Latency distance doubles (0.31 to 0.62 m) but braking distance quadruples (0.5 to 2.0 m) because it grows with the square of speed. The total goes from 0.81 m to 2.62 m, about 3.2 times as much.

Question 3

Why can a navigation system not simply run its global planner at the control rate?

Explanation

The global planner searches a large map, so each run takes far longer than a control period, and the control loop has hard deadlines. Splitting the work lets the global layer be slow and thorough while the local layer stays fast and reactive.

What’s next

Next: the parts of a navigation stack and what each one hands to the next.

Practice this lesson

Read a Failed Run

Scout stopped in a corridor and never arrived: read the logs and the trace, and decide which part of the stack failed.

Next lesson

M1-T2 — The Navigation Stack at a Glance

Name the parts of a navigation stack (costmaps, global planner, local planner, controller, recovery) and the information each hands to the next.

Nothing below is required to finish this lesson.

  • Lab
    M1-L1: Read a Failed Run

    Scout stopped in a corridor and never arrived: read the logs and the trace, and decide which part of the stack failed.