Escaping Local Minima

It is not broken. It is doing exactly what you told it to do. The goal pulls; the walls push; deep inside that pocket the pull and the push cancel out perfectly. The robot feels zero net force, concludes it has arrived, and parks. This dead end has a name, a local minimum, and learning to climb out of one is the difference between a swarm that finishes the job and a swarm that becomes lawn ornaments.

Watch them get stuck, then shake them loose

Below is a field of agents trying to reach a goal hidden behind a U-shaped wall. The slider controls noise: how much random jitter you let into each agent's motion. Start with the noise at zero, the way a pure, deterministic planner would run it.

Try this:

1. Leave noise at 0. Watch the agents stream into the U and pile up against the back wall, short of the goal. Every direction the gradient offers points back into the trap. They are not lost. They are convinced they're done.
2. Drag the noise up, a little. The agents start to jiggle. Watch one accidentally wander past the lip of the U, catch a downhill path, and escape. Then another. The trap leaks.
3. Crank the noise high. Now everyone escapes, but they stagger and waste motion getting there. Too little randomness and they stick; too much and they drift like drunks.

That tension is the whole lesson: pure determinism gets stuck; a little randomness explores. The art is dialing in just enough chaos.

Why the rational robot freezes

A potential field is a clever lie. You pretend the goal is a deep well and every obstacle is a hill, then let the robot roll downhill toward the goal. The force at any point is just the slope:

$$\vec{F}(\vec{x}) = -\nabla U(\vec{x}) = \underbrace{-\nabla U_{\text{att}}}_{\text{pull to goal}} \;+\; \underbrace{-\nabla U_{\text{rep}}}_{\text{push from walls}}$$

It works beautifully, until the pull and the push line up nose-to-nose and sum to zero somewhere that isn't the goal. The robot reads $\vec{F} \approx 0$, the universal signal for "you have arrived," and commits to the wrong place with total conviction. A U-shaped obstacle is the textbook offender: attraction and repulsion cancel, and the robot freezes in the dead end.

The fix is to stop being so reasonable

A perfectly deterministic robot is doomed inside a U, because every rule it follows points inward. The escape is to occasionally break the rules: add a random kick and see if it lands somewhere better.

This is the famous exploration-exploitation trade-off wearing a robotics costume. Exploit (follow the gradient) and you're efficient but you can get stuck. Explore (move randomly) and you're inefficient but you can find the way out. Noise buys you exploration, and exploration is what shakes a robot out of the trap.

Or follow the wall like a person in a dark room

Randomness isn't the only way out. The other classic trick is wall-following: when the robot detects it's stuck, it stops fighting the gradient and instead hugs the obstacle boundary, tracing along the wall until it clears the obstacle and the goal opens up again. It's deterministic, it's reliable, and it's exactly what you do groping for the light switch in an unfamiliar room. Real planners rarely trust the field alone; they bolt on wall-following or random walks precisely to escape minima.

First, notice you're stuck

You can't escape a trap you haven't noticed. The tell is a robot that wants to move but isn't: a large net force pushing on it, yet almost no actual velocity. Formally, agent $i$ is stuck when

$$\|\vec{v}_i\| < \epsilon_v \quad \text{and} \quad \|\vec{a}_i\| > \epsilon_a$$

high force, low motion. That contradiction ("I'm pushing hard and going nowhere") is the trigger that flips the robot out of polite gradient-following and into escape mode.

↘ The math: random-walk and wall-following escape

Once the stuck-detector fires, you inject an escape behavior. The simplest is a random-walk kick: with probability $p$ each step, add a draw from a zero-mean Gaussian to the acceleration:

$$\vec{a}_i \;\leftarrow\; \vec{a}_i + \begin{cases} \mathcal{N}(0,\, \sigma^2) & \text{with probability } p \\[2pt] 0 & \text{otherwise} \end{cases}$$

The variance $\sigma^2$ is the noise slider from the demo. Small $\sigma$ rarely clears the lip of the trap; large $\sigma$ clears it but wastes motion everywhere else, the same Goldilocks band you felt by hand.

The deterministic alternative is wall-following: nudge the robot along the tangent $\vec{t}_{\text{wall}}$ of the nearest obstacle boundary,

$$\vec{a}_i \;\leftarrow\; \vec{a}_i + k_{\text{wall}}\, \vec{t}_{\text{wall}}$$

so instead of grinding into the wall it slides along it until the obstacle is behind it. A hybrid controller is what production swarms actually run: follow the potential field by default, switch to a random walk (or wall-following) once the stuck-detector has fired for a beat, and switch back the moment velocity recovers. Deterministic when it can be, stochastic when it must be.

The field with no traps at all

Patching the field with random kicks and wall-following works, but it always feels like a bolt-on. So a natural question hangs in the air: could you build a potential field that simply has no false minima in the first place? One smooth surface, exactly one bottom, and that bottom sitting right on the goal? If such a field existed, gradient descent would never get stuck, because there would be nowhere to get stuck.

It exists. The catch, as usual, is that the math gets a lot harder.

↘ Navigation functions: a potential field that provably can't trap you

In the late 1980s and early 1990s, Daniel Koditschek and Elon Rimon proved you can construct a special potential function with a guarantee built in: a single minimum, at the goal, and no spurious minima anywhere else in the free space. They named it a navigation function. The promise is strong. From almost any starting point, plain gradient descent converges to the goal, full stop. No stuck-detector, no random kicks, no wall-following.

A navigation function $\varphi$ is engineered to be:

• $0$ at the goal and $1$ on every obstacle boundary,
• smooth (so the gradient is well defined everywhere), and
• Morse, the technical condition that pins down its critical points so the only minimum is the goal.

It is not magic. Their clean construction lives on a "sphere world," a space whose obstacles are all round and whose outer boundary is a big sphere. The recipe blends the squared distance to the goal with a term that vanishes at each obstacle boundary (pinning the value to $1$ there), then runs it through a sharpening exponent $\kappa$:

$$\varphi(\vec{x}) = \frac{\gamma(\vec{x})}{\bigl(\gamma(\vec{x})^{\kappa} + \beta(\vec{x})\bigr)^{1/\kappa}}$$

where $\gamma$ measures distance to the goal and $\beta$ measures distance to the obstacles. Crank $\kappa$ high enough and the unwanted saddle points get squeezed down to a measure-zero set, leaving the goal as the lone basin. For real, messily shaped worlds you first warp them into a sphere world with a smooth map, solve there, then warp back. That warping is the price of the guarantee, and it is why most swarms still reach for the cheap random kick instead.

What to carry away

• A local minimum is any spot where the net force is zero but the goal isn't. A U-shaped obstacle is the classic example, where attraction and repulsion cancel and the robot freezes in a dead end.
• Pure determinism gets stuck. A robot that only ever follows the gradient has no move that points out of the trap.
• A little randomness explores. Noise (random kicks) lets a robot rattle loose and stumble onto a path out. Too little and it sticks; too much and it staggers.
• Real planners hedge. They bolt on wall-following or random walks, and switch between deterministic and stochastic modes depending on whether they're making progress.