Potential fields

The goal pulls, the obstacles push, and the robot slides downhill into a local minimum.

U9.5PlanningUniversity35 min

Do this lesson in the simulator

Every planner so far builds a complete route before the robot moves. A potential field does not plan at all. It puts the robot on an imaginary hillside and lets it roll.

  • The goal is a valley, pulling the robot towards it from anywhere.
  • Every obstacle is a hill, pushing the robot away, steeply when it is close and not at all beyond some reach.
  • The robot's velocity is the sum of the two, every tick.

The appeal is real. There is no map to build, no search, nothing to store, and it handles obstacles that appear while the robot is already moving. It runs in a few lines at any rate the robot can manage. For a while in the 1980s it looked like the answer.

The two terms

Attraction. A constant-size pull towards the goal is the simplest, easing off near the target so the robot does not overshoot:

strength = min(TOP, FLOOR + 0.3 * gap)
ax, ay = strength * dx / gap, strength * dy / gap

That eased version is a conical well far away and a parabolic one close in, which is the standard construction and gives a controller that arrives rather than orbiting. The FLOOR matters on a real machine: below about 15 percent of full command the motors do not turn at all, so a pull that eases smoothly to zero leaves the robot parked a few centimetres short, commanding a speed it cannot produce. Keep the pull above the dead band and stop on distance instead.

Repulsion. The textbook form, from the nearest point of the obstacle, with a reach d0 beyond which it is exactly zero:

if d < d0:
    m = K * (1.0 / d - 1.0 / d0) / (d * d)

The 1/d - 1/d0 factor makes the push fall smoothly to nothing at the edge of its reach rather than switching off with a jolt, and the 1/d^2 makes it blow up close in. It does blow up, so cap it, or one tick very near a wall commands a wild velocity.

For a rectangle, the nearest point is easy and worth knowing:

nearest = (min(max(x, ox), ox + ow), min(max(y, oy), oy + oh))

Clamp the robot's position into the rectangle on each axis independently. Inside, it returns the point itself and the distance is zero, so the cap earns its keep there too.

The local minimum

Now the problem, and it is fatal.

The sum of a pull and several pushes can be zero somewhere that is not the goal. The robot stops, or worse, oscillates across the flat spot for ever. This is not a bug in the arithmetic. It is a property of adding fields together, and it cannot be tuned away.

Three shapes cause it constantly:

  • A wall square across the line to the goal. The push is exactly opposite the pull, they cancel, and the robot sits there.
  • A U shape, or any concave obstacle. The robot drives into the mouth and is pushed back by both sides. This is the classic, and it is why potential fields never drive a real robot through a room with furniture in it.
  • Two obstacles with a gap between them. The pushes from both sides add up across the gap and close it, so the robot refuses a passage it could easily fit through. Narrow corridors also produce fast oscillation, bouncing off alternate walls.

The deep statement: a potential field is a local method, and no local method can be complete. It only ever sees the gradient where it is standing. A planner that searches the graph knows the whole free space and will tell you truthfully when there is no route. A field will simply stop, and it cannot tell you why.

What people do about it

  • Random walk on stalling. Detect that the robot has stopped moving while not at the goal, drive somewhere random for a second, and resume. Sometimes works. No guarantee.
  • Wall following on stalling. The bug algorithms of U5: follow the boundary until the direct line to the goal is clear again. This is complete in two dimensions, and it is the honest fix.
  • Navigation functions. Build a potential with exactly one minimum, at the goal, by construction. A distance transform over an occupancy grid, run backwards from the goal, is one, and it is genuinely free of local minima. Note what that costs: a global computation over the whole map, which is exactly what the field was meant to avoid.
  • Use it as a local layer only. This is the real answer, and it is what modern stacks do. A global planner (A* on a grid) produces the route; a local reactive layer (a field, or dynamic window, or a lattice of short trajectories) follows it while dodging whatever has wandered into the way. Each does the job it is good at.

The scene here

One block, and a goal up and to the right of it. The pull and the push are not opposite, so the robot slides along the face of the block and round its top. Move the goal to be directly behind the block and the same program sits still for ever, which is worth doing once.

from bugbot import *
import math
connect()

BLOCK = (80.0, 10.0, 30.0, 90.0)
GOAL = (170.0, 160.0)
REACH, K_PUSH = 45.0, 120000.0

def field(x, y):
    dx, dy = GOAL[0] - x, GOAL[1] - y
    gap = math.hypot(dx, dy)
    strength = min(13.0, 4.0 + 0.3 * gap)
    vx, vy = strength * dx / gap, strength * dy / gap
    ox, oy, ow, oh = BLOCK
    cx, cy = min(max(x, ox), ox + ow), min(max(y, oy), oy + oh)
    ex, ey = x - cx, y - cy
    d = math.hypot(ex, ey)
    if 1e-6 < d < REACH:
        m = min(60.0, K_PUSH * (1.0 / d - 1.0 / REACH) / (d * d))
        vx, vy = vx + m * ex / d, vy + m * ey / d
    return vx, vy

# the field along the robot's row, as it walks into the block
for x in range(30, 80, 5):
    vx, vy = field(float(x), 40.0)
    print("at x =", x, "velocity", round(vx, 1), round(vy, 1))

Run this in the simulator

Watch the y component grow as the robot closes on the block: that is the push turning a head-on approach into a slide.

Task: slide round the block

Drive to the green corner at (170, 160) using a potential field and nothing else: no route, no grid, just a velocity worked out fresh each tick from the pull and the push. Plot pull and push, the size of each part, and do not touch the block or the mat edges.

from bugbot import *
import math
connect()

DT = 0.1
V_MAX, V_LAT = 20.0, 15.0
START = (30.0, 40.0)
GOAL = (170.0, 160.0)
BLOCK = (80.0, 10.0, 30.0, 90.0)

Challenges

  1. Move the goal to (170, 40), directly behind the block, and run the same program. Describe precisely what the robot does and why.
  2. Add stall detection: if the robot has moved less than 2 cm in two seconds and is not at the goal, drive in a random direction for a second. Does it escape the case above reliably?
  3. Put a second block 40 cm from the first and try to drive between them. At what separation does the gap close?