Local vs. Global Planning

You've planned a perfect path from your desk to the kitchen. You start walking. Halfway there, your cat darts across the hallway. Do you:

1. Recompute the entire path from scratch?
2. Step around the cat and continue?

Obviously option 2. Your brain has a global plan ("go to kitchen") and local obstacle avoidance ("don't step on cat"). Robots work the same way.

The Two-Layer Architecture

Most autonomous robots split navigation into two layers:

The global planner uses A*, RRT, or similar to find a path on the map. It assumes the map is correct.

The local planner follows the global path while reacting to:

• Unmapped obstacles (people, chairs that moved)
• Sensor noise (map uncertainty)
• Dynamic objects (other robots, cars, pets)

Think of it like GPS navigation: the route is your global plan, but you still steer to stay in your lane and avoid potholes.

Global Planning Recap

We've covered this in previous lessons:

• Input: Current pose, goal pose, map
• Output: Sequence of waypoints (path)
• Frequency: Replan when goal changes, map updates, or stuck
• Algorithms: A* (2D), RRT (high-D), PRM (multi-query)

The global path is typically coarse — waypoints every 0.5-2 meters. It's a high-level guide, not a precise trajectory.

Local Planning: The Real Challenge

The local planner gets:

• The global path (as a "reference")
• Current robot pose and velocity
• Real-time sensor data (laser scan, camera, etc.)

Its job: Generate velocity commands (linear + angular) that follow the global path while avoiding obstacles.

This is harder than it sounds. The robot must balance:

• Progress: move toward the goal
• Safety: don't hit obstacles
• Dynamics: respect speed, acceleration, and turning limits
• Comfort: smooth motion, no sudden jerks

Two Popular Approaches

1. Dynamic Window Approach (DWA)

DWA simulates many possible velocity commands, scores each one, and picks the best.

How It Works

1. Sample candidate velocities (v, ω) within the robot's dynamic limits
   Example: v ∈ [0, 0.5 m/s], ω ∈ [-1, 1 rad/s]

2. For each candidate:
   a. Simulate the robot's trajectory over the next 1-2 seconds
   b. Check for collisions with obstacles
   c. Compute a score based on:
      - How close it gets to the global path (heading alignment)
      - How far it can go before hitting an obstacle (clearance)
      - How fast it's moving (speed preference)

3. Pick the velocity with the highest score
4. Send it to the motors

Scoring function example:

score = α * heading_score + β * clearance_score + γ * velocity_score

where:
  heading_score = how aligned with global path (0-1)
  clearance_score = distance to nearest obstacle (meters)
  velocity_score = current speed / max speed (0-1)
  α, β, γ = tunable weights

Example

Robot at X, goal direction →
Obstacles: ███

Candidate 1: Go straight    Candidate 2: Turn slightly left
  v=0.5, ω=0                  v=0.4, ω=0.3

  X →  collision!             X  ↗  safe, aligned

  Score: -∞ (collision)       Score: 0.8 (good!)

DWA picks Candidate 2: turn slightly left, avoid obstacle, keep moving.

DWA Pros/Cons

Pros:

• Fast (runs at 20-50 Hz easily)
• Smooth motion (considers dynamics)
• Handles dynamic obstacles well

Cons:

• Can get stuck in local minima (narrow passages)
• Requires careful tuning (α, β, γ weights)
• Doesn't look far ahead

2. Vector Field Histogram (VFH)

VFH builds a polar histogram of obstacle density around the robot, then picks the direction with the most free space aligned with the goal.

How It Works

1. Convert sensor data (laser scan) into a polar histogram
   Each angle bin (0°, 5°, 10°, ..., 355°) gets a density value

2. Identify "valleys" (low-density regions = free space)

3. Pick the valley closest to the goal direction

4. Steer toward that direction

Example

Polar histogram (top-down view):

       90°
        |
    ████|        ← obstacles ahead
180°────X────0°  ← robot at X, goal at 45°
        |
    free space
       270°

Valleys: 120°-180° (left), 270°-330° (back-right)
Goal direction: 45° (blocked!)
Best valley: 120° (turns left to go around)

VFH steers the robot smoothly around obstacles by always picking the "widest gap" that's still goal-aligned.

Pros:

• Very robust, hard to trap
• Works well in cluttered environments
• Simple concept

Cons:

• Discrete angular bins (can be jerky)
• Less smooth than DWA
• Doesn't directly consider robot dynamics

Putting It Together: The Navigation Stack

Here's how global + local planning work together:

Flow:

1. Global planner computes path to goal
2. Local planner follows the path, generates velocity commands
3. If local planner gets stuck, global planner replans
4. If goal changes, global planner updates, local planner follows new path

This two-layer approach is how most modern navigation stacks and commercial robots work.

What's Next?

You've planned a path (global) and avoided obstacles (local). Now the robot knows where to go. But how does it actually follow the path smoothly? Next, we'll explore path following — converting waypoints into steering commands.