Chapter 9: Reactive Navigation — Potential Fields and Bug Algorithms

Reactive navigation produces motion directly from sensor readings, without building a map or planning a path. It is fast, computationally light, and naturally handles dynamic environments. Its weakness is that purely reactive methods can get stuck in local optima — a robot that only responds to immediate sensor readings may circle indefinitely or oscillate against a concave obstacle. This chapter covers two families of reactive methods: potential fields and Bug algorithms.

9.1 The Potential Field Concept

Imagine the robot exists in a scalar potential field $U(x, y)$. The goal attracts the robot (attractive potential); obstacles repel it (repulsive potential). The robot’s velocity is proportional to the negative gradient of the total potential — it always rolls downhill:

\[\mathbf{F} = -\nabla U = -\nabla U_{att} - \nabla U_{rep}\]

Attractive Potential

A quadratic well centred on the goal $\mathbf{q}_{goal}$:

\[U_{att} = \frac{1}{2} k_{att} \|\mathbf{q} - \mathbf{q}_{goal}\|^2\]

$\nabla U_{att} = k_{att} (\mathbf{q} - \mathbf{q}_{goal})$

This pulls the robot toward the goal with force proportional to distance.

Repulsive Potential

For each obstacle at $\mathbf{q}_{obs}$, active only within a radius $d_0$:

\[U_{rep} = \begin{cases} \frac{1}{2} k_{rep} \left(\frac{1}{d} - \frac{1}{d_0}\right)^2 & d < d_0 \\ 0 & d \geq d_0 \end{cases}\]

where $d = |\mathbf{q} - \mathbf{q}_{obs}|$.

$\nabla U_{rep} = k_{rep}\left(\frac{1}{d} - \frac{1}{d_0}\right)\frac{1}{d^2}\hat{\mathbf{d}}$

where $\hat{\mathbf{d}}$ is the unit vector from obstacle to robot.

Combined Velocity Command

\[\mathbf{v}_{cmd} = -\nabla U_{att} - \sum_{i} \nabla U_{rep,i}\]

The command is then clamped to the robot’s maximum speed and converted to $(v, \omega)$ using the robot’s heading.

def potential_field_command(robot_pos, goal_pos, obstacles,
                             k_att=1.0, k_rep=0.5, d0=0.5):
    f = k_att * (goal_pos - robot_pos)          # attractive
    for obs in obstacles:
        d = np.linalg.norm(robot_pos - obs)
        if d < d0:
            direction = (robot_pos - obs) / d
            magnitude = k_rep * (1/d - 1/d0) / d**2
            f += magnitude * direction           # repulsive
    return f

9.2 Converting Force to Robot Velocity

The force vector $\mathbf{F} = (F_x, F_y)$ in the world frame must be converted to $(v, \omega)$ in the robot frame:

def force_to_velocity(Fx, Fy, heading, v_max=0.3, omega_max=2.0):
    # Desired heading to the force direction
    desired_heading = math.atan2(Fy, Fx)
    heading_error   = desired_heading - heading
    heading_error   = math.atan2(math.sin(heading_error),
                                  math.cos(heading_error))
    v     = min(v_max,  math.hypot(Fx, Fy))
    omega = max(-omega_max, min(omega_max, 2.0 * heading_error))
    return v, omega

9.3 Local Minima Problem

The main failure mode of potential fields is local minima: points where $\nabla U = 0$ but which are not the goal. This typically occurs in concave obstacles (a U-shaped corridor) where the attractive and repulsive forces exactly cancel.

Remedies:

  1. Random perturbation: if the robot detects it has been stuck (low speed) for more than a threshold time, add a random velocity perturbation.
  2. Harmonic potentials: replace the simple quadratic with a solution to Laplace’s equation, which has no local minima in free space — but is more complex to compute.
  3. Bug algorithms: switch to a different strategy (wall-following) when stuck.

9.4 Bug Algorithms

Bug algorithms are simple, provably complete navigation strategies for unknown environments. They alternate between two behaviours: move toward goal and follow obstacle boundary.

Bug 0

  1. Head directly toward the goal.
  2. If an obstacle is hit, follow its boundary (wall-follow, keeping obstacle on the right) until the robot can again head directly to the goal without hitting the obstacle.
  3. Repeat.

Bug 0 is not complete: it can loop forever in adversarial environments. But it works well in practice for convex and mildly concave obstacles.

Bug 1

  1. Head directly toward the goal.
  2. When an obstacle is hit, circumnavigate it completely, recording the closest point to the goal.
  3. Return to that closest point and leave the obstacle in the direction of the goal.

Bug 1 is complete (always reaches the goal if a path exists) but may be inefficient.

Bug 2

  1. Maintain the straight line $M$ from start to goal.
  2. Head toward the goal.
  3. When an obstacle is hit, follow its boundary until hitting line $M$ at a point closer to the goal than the hit point.
  4. Continue toward goal.

Bug 2 is also complete and typically more efficient than Bug 1.

Implementation

The key sub-behaviour is wall following: the robot keeps the obstacle at a fixed distance $d_{wall}$ on one side. Using the ultrasound sensor panned to 90° (right side):

def wall_follow_command(right_dist, target_dist=0.25):
    error = target_dist - right_dist
    v     = 0.15           # slow forward
    omega = 1.5 * error    # proportional steering
    return v, omega

A more complete implementation uses a PID controller on the wall distance error.

9.5 Vector Field Histogram (VFH)

VFH is a reactive method that extends the sector-scan approach from Chapter 7. It builds a polar histogram of obstacle density around the robot (from the ultrasound scan), then identifies the valley (low-density sector) closest to the goal direction and steers into it.

VFH outperforms simple potential fields in dense, cluttered environments and does not suffer from local minima in the way that gradient descent does. The full VFH+ algorithm adds steering constraints to account for non-holonomic limitations.

9.6 When to Use Reactive Navigation

Reactive navigation is the right tool when:

It is insufficient when:

In these cases, the map-based planning methods of Chapters 10 and 11 are appropriate. In practice, most autonomous systems combine reactive and deliberative navigation in a hybrid architecture, as Chapter 15 demonstrates.

Navigation: