Potential Field Navigation

Give the robot an invisible landscape with a valley at the goal and a hill around every obstacle. Then let it roll downhill by following the negative gradient.

Driving downhill

Drag the flag, the start ring or any obstacle

How it works

Gradients of scalar fields

In one sentence

The robot moves along $-\nabla U$ , where $U$ adds an attractive bowl centered on the goal and, for each obstacle closer than $\rho_0$ , a repulsive term that blows up at the obstacle.

General formula

\begin{aligned} {\htmlData{sym=0}{U}}({\htmlData{sym=2}{\mathbf{q}}}) &= \tfrac12 {\htmlData{sym=3}{k_a}}\lVert{\htmlData{sym=2}{\mathbf{q}}}-{\htmlData{sym=1}{\mathbf{q}_g}}\rVert^2 \\ &\quad + \sum_i \tfrac12 {\htmlData{sym=4}{k_r}}\left(\tfrac{1}{{\htmlData{sym=5}{\rho_i}}} - \tfrac{1}{{\htmlData{sym=6}{\rho_0}}}\right)^2 \end{aligned}

The first term pulls toward the goal like a spring of strength $k_a$ . Each obstacle adds a steep hill of strength $k_r$ , but only within distance $\rho_0$ .

What the symbols mean

$U$
Potential
A height map the robot rolls downhill on, toward the goal and away from obstacles.
$\mathbf{q}_g$
Goal
Where the robot wants to go.
$\mathbf{q}$
Robot position
Where the robot is now.
$k_a$
Attraction strength
How strongly the goal pulls the robot in.
$k_r$
Repulsion strength
How strongly obstacles push the robot away.
$\rho_i$
Distance to obstacle i
How close the robot is to obstacle number i.
$\rho_0$
Influence radius
Obstacles farther than this have no effect.

The attractive term is a bowl centered on the goal, and its gradient pulls the robot in.
Each obstacle adds a repulsive term that grows near it and vanishes beyond distance $\rho_0$ .
The robot moves by $\mathbf{q} \leftarrow \mathbf{q} - \eta\,\nabla U$ , the same update as gradient descent.
Where pushes and pulls cancel, the robot can stall in a local minimum that is not the goal.

Learn the math

Directional Derivatives and the GradientCalc III · Lesson 24, Partial Derivatives Vector FieldsCalc III · Lesson 39, Line Integrals Field from Potential: E = −∇VE&M · Lesson 10, Electric Potential