Skip to the lesson
FixTheRobot Explore Robotics / Navigation / M6 Local Planning and Obstacle Avoidance / M6-T3

Navigation · Theory · M6

M6-T3 — The Dynamic Window Approach

Instead of planning a path, choose a velocity: the best one among those the motors can reach now and the brakes can stop.

  • Lesson 3 of 7
  • Module 6: Local Planning and Obstacle Avoidance
  • Theory
  • About 8 minutes to read

A mobile robot is commanded by two numbers, speed and turn rate, and it can only change them so fast. The dynamic window approach takes that seriously: it samples the velocities reachable within one control period, throws away any that cannot be stopped before an obstacle, scores the rest, and sends the best. It is the engine behind many local planners, including the default one of Nav2’s predecessors.

Learning objectives

After this lesson, you should be able to:

  • Compute the dynamic window from acceleration limits and the robot’s absolute limits.
  • Predict the arc of a velocity pair and measure the free distance along it.
  • Apply the admissibility rule and explain what each term of the score does.
  • Recognise the usual failures: local minima, oscillation in narrow gaps, and coarse sampling.

The intuition

A driver does not choose a path in a car park, they choose how hard to press the pedal and how far to turn the wheel for the next moment. Each choice leads along a curve. The driver only considers choices that are possible now: the car cannot go from 1 m/s to 3 m/s in a blink. Of those, the ones that lead to a place the driver could still stop short of an obstacle are acceptable. Among the acceptable ones, the driver picks the curve that goes towards the goal, keeps clear of things, and is not painfully slow.

That is the whole method. The set of reachable velocities is the dynamic window. The curves are circular arcs, because a constant speed and turn rate give one. The rule that a curve must leave room to stop is called admissibility. The choice among acceptable curves is a weighted score.

Candidate arcs in the dynamic windowNine arcs start at the robot. The three fastest arcs, at 0.8 metres per second, run into a post and cannot be stopped in time and are drawn grey. The others are admissible and drawn green. The post is a dark disc with a dashed ring showing the robot radius added. goal (4, 1.0) m, off to the right post (r = 0.2 m) + robot radius 0.3 m Green: admissible (can stop before the post) Grey dashed: v = 0.8 m/s needs 0.64 m to stop,the post is 0.51 to 0.53 m away
Nine candidate arcs from the robot. Arcs at 0.8 m/s towards the post cannot be stopped in time and are rejected, even though they do not reach the post for another half metre.

The mathematics

The window

With current velocity (v, ω), accelerations av and aω, control period Δt, and the robot’s limits:

Reachable and allowed velocities
Vd={(v′, ω′): v′∈[v−av⋅Δt, v+av⋅Δt], ω′∈[ω−aω⋅Δt, ω+aω⋅Δt]}V_{d}=\{(v^{\prime},\,\omega ^{\prime}):\,v^{\prime}\in [v-a_{v}\cdot \Delta t,\,v+a_{v}\cdot \Delta t],\,\omega ^{\prime}\in [\omega -a_{\omega }\cdot \Delta t,\,\omega +a_{\omega }\cdot \Delta t]\}
Vs={v′∈[0, vmax⁡], ω′∈[−ωmax⁡, ωmax⁡]}V_{s}=\{v^{\prime}\in [0,\,v_{\max}],\,\omega ^{\prime}\in [-\omega _{\max},\,\omega _{\max}]\}

The search space is Vd ∩ Vs: both intervals clipped to the limits (lab M6-L2, stage 1).

Predicting an arc

For a constant (v, ω) the pose after time t is the unicycle arc of lesson M1-T3. The free distance d(v, ω) is the arc length at which the robot first touches an obstacle, or a cap D if none is met within D (lab M6-L2, stage 2).

Admissibility

Admissible velocities
v≤2⋅d(v, ω)⋅abrakev\le \sqrt{2\cdot d(v,\,\omega )\cdot a_{\text{brake}}}

A velocity is allowed only if the robot, braking at abrake, could stop before the first contact on its arc. The same idea for turning gives a rule for ω. The braking deceleration is a design number, not the motor’s peak.

The score

Objective (weights as in lab M6-L2: 0.6, 0.2, 0.2)
G(v, ω)=α⋅heading+β⋅clearance+γ⋅speedG(v,\,\omega )=\alpha \cdot \text{heading}+\beta \cdot \text{clearance}+\gamma \cdot \text{speed}
heading=1−∣angle from the robot′s heading to the goal direction at the end of the arc∣/π\text{heading}=1-\lvert \text{angle from the}\,\mathrm{robot}^{\prime}s\,\text{heading to the goal direction at the end of the arc}\rvert /\pi
clearance=min⁡(d, D)D\text{clearance}=\frac{\min (d,\,D)}{D}
speed=vvmax⁡\text{speed}=\frac{v}{v_{\max}}
TermWhat it rewardsIf its weight is too high
headingArcs that end up facing the goalCuts close to obstacles, and cannot turn away from a minimum
clearanceArcs that stay away from obstaclesHesitates in narrow gaps, drifts to the middle of free space
speedFaster arcsIgnores the goal direction and rushes past it

Fox, Burgard and Thrun normalise the terms and smooth the sum, and their clearance term is the distance to the nearest obstacle. The principle is the same.

A worked example

One decision. Scout is at the origin facing +x with v = 0.6 m/s and ω = 0.3 rad/s. Limits: vmax = 1.0 m/s, ωmax = 1.5 rad/s, av = 0.8 m/s², aω = 2.0 rad/s², Δt = 0.25 s, braking 0.5 m/s², robot radius 0.3 m. A post (radius 0.2 m) stands at (1.0, 0.1) and the goal is at (4, 1.0).

The window
v window=[0.6−0.8⋅0.25, 0.6+0.8⋅0.25]=[0.4, 0.8]v\,\text{window}=[0.6-0.8\cdot 0.25,\,0.6+0.8\cdot 0.25]=[0.4,\,0.8]
ω window=[0.3−2.0⋅0.25, 0.3+2.0⋅0.25]=[−0.2, 0.8]\omega \,\text{window}=[0.3-2.0\cdot 0.25,\,0.3+2.0\cdot 0.25]=[-0.2,\,0.8]

Three speeds and three turn rates give nine candidates. “Free” is the distance to the post along the arc (3.00 means clear to the cap), “stop” is v²/(2 · 0.5), and the score uses the weights 0.6, 0.2, 0.2 with the heading measured after 1 s:

vωfree (m)stop (m)admissiblescore
0.4−0.20.540.16yes0.624
0.40.30.520.16yes0.706
0.40.83.000.16yes0.771
0.6−0.20.530.36yes0.659
0.60.30.510.36yes0.747
0.60.80.570.36yes0.647
0.8−0.20.520.64no0.694
0.80.30.510.64no0.788
0.80.80.530.64no0.682

Without admissibility the winner is (0.8, 0.3) with score 0.788: fast, pointed at the goal, and heading at a post 0.51 m away, with a stopping distance of 0.64 m. With admissibility the three fast arcs are removed and the winner is (0.4, 0.8) with 0.771: it turns away from the post, whose clearance term is a full 1.0, and keeps moving. The difference between the two is 0.017 in score and the difference between a collision and a clean pass in practice. This is lab M6-L2, stage 3.

Engineering implications and limitations

Cost and resolution

The work is samples × prediction steps × obstacle checks per cycle. With 20 speeds, 40 turn rates and 30 steps there are 24 000 pose evaluations each cycle, 480 000 per second at 20 Hz, before any obstacle lookup. A costmap lookup per pose is cheap; a per-obstacle loop is not. Use grid lookups with the footprint, and keep the samples as few as the manoeuvres need.

Weights are behaviour

Tune one weight at a time on a fixed set of scenes and watch the arcs, not only the trajectory. Nav2’s DWB controller exposes the same idea as a list of “critics”, each a cost with a scale, for example path alignment, goal alignment and obstacle proximity.

Known failure modes

  • Local minima: the score is local, so a dead end looks as good as a corridor until the robot is in it (lab M6-L1).
  • Oscillation: alternate cycles prefer left and right when two arcs score alike; add a penalty for changing the turn rate, or a forward preference.
  • Narrow gaps: the best arcs may be a curve that needs a larger turn than the window gives; the robot slows and stops. Allow rotation in place as a candidate.
  • Coarse arcs: a prediction step larger than a post can skip it (lab M6-L2, stage 2).
  • Circular arcs are an assumption: a car-like robot with limited steering rate needs its own kinematics.

Common misconceptions

“The dynamic window approach plans a path.”

It chooses one velocity per cycle. Any path is the result of repeating that choice.

“Collision-free for the next second is safe.”

Safe means that a stop is still possible. That is the admissibility rule, and it often removes the fastest arcs.

“More samples always improve the result.”

They improve the best score, but the weights decide what “best” means, and more samples cost cycle time.

“The window is the same as the speed limit.”

The speed limit is part of it, but the window also moves with the current velocity, which is why it is called dynamic.

Engineering takeaways

  1. The dynamic window is the set of velocities reachable in one control period, clipped to the robot’s limits.
  2. Each candidate is a circular arc; its free distance is the arc length to the first contact.
  3. Admissible means v² ≤ 2·abrake·free distance, so a stop is always possible.
  4. The score combines heading, clearance and speed; the weights define the behaviour.
  5. It is local: it needs a global path and recovery for minima and narrow gaps.

References and further reading

The original paper and its global extension.

  • D. Fox, W. Burgard and S. Thrun, “The Dynamic Window Approach to Collision Avoidance”, IEEE Robotics & Automation Magazine 4(1), 1997.
  • O. Brock and O. Khatib, “High-Speed Navigation Using the Global Dynamic Window Approach”, IEEE ICRA, 1999.
  • Nav2 documentation, “DWB Controller”, docs.nav2.org.

Knowledge check

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

Question 1

A robot at v = 0.9 m/s with av = 1.0 m/s², Δt = 0.2 s and vmax = 1.0 m/s. What is the speed window?

Explanation

[0.9 − 0.2, 0.9 + 0.2] = [0.7, 1.1], clipped to [0.7, 1.0].

Question 2

An arc has a free distance of 0.7 m. The robot brakes at 0.5 m/s². What is the highest admissible speed?

Explanation

v ≤ √(2 × 0.5 × 0.7) = √0.7 = 0.837 m/s.

Question 3

An obstacle is 0.8 m along an arc. Is the arc admissible at 1.0 m/s with braking 0.5 m/s²?

Explanation

No. Stopping from 1.0 m/s takes 1.0² / (2 × 0.5) = 1.0 m, more than the 0.8 m available. The arc is collision-free for now, but the robot could no longer avoid contact.

What’s next

Next: obstacles that move, and how to predict whether and when they will cross your path.

Practice this lesson

Implement the Dynamic Window

Pick the best safe velocity every tick to reach the goal without touching the shelving.

Next lesson

M6-T4 — Time to Collision and Predicting Moving Obstacles

Compute time to collision under constant velocity and say when that prediction is wrong.

Nothing below is required to finish this lesson.