|
|
|
|
|
Directed Search
Constraint Tracking (page
3) |
|
←
Figure 2. shows the hypercube for a robot with three degrees of redundancy. There are 2n points on the faces
of the cube, ~ points at the vertices, and 3’~ points in all. Respectively, we call these the simple,
factorial, and exhaustive exploration patterns. For more than four or five degrees of redundancy, the
computational expense associated with current computing hardware prohibits the exhaustive pattern in real-
time applications.
Annealing describes a process of heating a material to an elevated temperature and then cooling it very
slowly. The slow cooling allows the material to reach a low energy state in which it is relatively ductile.
With no intelligence or systematic strategy, some materials minimize energy state during the slow cooling.
Simulated annealing is an approximation of this natural process carried out on a computer and is based on
the Boltzmann probability distribution.
In this equation, E is the energy of the system, k is Boltzmann’s constant, and T is the temperature.
Essentially, the Boltzmann probability distribution states that a system’s energy is probabilistically
distributed depending upon the temperature. As the temperature increases, the probability of the system
assuming a higher energy state increases. As the temperature is lowered, the odds of the system leaving a lower energy state decrease. Each configuration option corresponds to an energy state. Because simulated annealing algorithms sometimes leave lower energy states for higher ones, they can escape from
local minima.
Simulated annealing algorithms typically include a method of generating random changes in the
system’s
configuration. The random changes represent trial configurations evaluated using the Boltzmann
probability
distribution. If the distribution indicates, the system assumes the trial configuration; otherwise it is
discarded. →
|
|
|
|
|
|