Introduction
Definition
Potential fields solve the navigation problem by modeling
the robot as a particle responding to an attractive force from
its goal and repulsive forces from obstacles.
Potential fields are applicable even if the robot does not
know the obstacle locations ahead of time, as long as it has
sufficient sensing to detect the locations any obstacles that
are “nearby”.
Details about potential fields appear in Chapter 4 of the
Choset textbook.
Potential functions
A potential function is a function $U: X \to \mathbb{R}$.- Input: A state $x$.
- Output: The potential $U(x)$ at state $x$.
Moving in the potential field
The robot's motion follows the negative gradient of the potential function. \[ - \nabla U(x,y) = - \left( \begin{array}{cc} \partial U / \partial x \\ \partial U / \partial y \end{array} \right) \] Intuition: Always move in the steepest direction downhill.
This forms a vector field, in which each state is
associated with a vector showing the direction the robot should
move from that state.
Additive potential functions
The most common technique for constructing potential functions is to use an additive model: \[ \newcommand{\goal}{_{\rm goal}} \newcommand{\obst}{_{\rm obst}} U(x) = U\goal(x) + \sum_i U^{(i)}\obst(x) \]- $U\goal$ generates an attractive force toward the goal.
- $U\obst$ generates repulsive forces away from each obstacle.
Attractive potential
A simple choice for the attractive potential is based on a scaled squared distance to the goal: \[ U\goal(x) = \frac{1}{2} \zeta \left[d(x, x\goal) \right]^2 \]
Repulsive potential
We also need to define a repulsive potential for each obstacle. A common choice is \[ U^{(i)}\obst(x) = \begin{cases} \frac{1}{2} \eta \left( \frac{1}{d_i(x)} - \frac{1}{Q_i^*} \right)^2 & \text{if } d_i(x) \le Q_i^* \\ 0 & \text{if } d_i(x) > Q_i^* \\ \end{cases} \] In this setup:- $d_i(x)$ is the distance from state $x$ to the closest point on obstacle $i$.
- $Q_i^*$ is the maximum “range of influence” for obstacle $i$.
- $\eta$ is a scaling factor.
What could go wrong?
The main limitation of the potential field method is the
problem of local minima: points other than the goal (the
“global minimum”) at which the gradient is zero.
Avoiding local minima
How can a robot avoid becoming stuck in a local minimum of its potential field?- Find a better potential function that doesn't have
local minima. (A navigation function.)
For more about navigation functions, see Section 4.6
of the Choset textbook.
- Notice that we've reached a local minimum, and try to escape. (Short-term gradient ascent; random motions; etc)
Summary
We saw three classes of navigation algorithms.- Visibility graphs
- Bug algorithms
- Potential fields