Information Technology Reference
In-Depth Information
Fig. 5.
3D and 2D Projection of Path Potentials
A second important property is related to the consistency of the solution found.
For a given environment (i.e. obstacles distribution) with a given starting and
goal cell, the solution found, if it exists, is the set of all optimal paths for the given
metric. The CA evolution can be seen as a motion from one point to another
point of the global state space until an optimal solution is reached. This is a
convergence point for the given problem or a steady global state. If we make some
perturbations, such as changing the environment (adding, deleting or moving one
or more obstacles) or changing the goal cell, then the point becomes unstable and
the CA starts to evolve again towards a new steady state, finding a new set of
optimal trajectories. We called this property as
Incremental Updating
. The CA
spontaneously evolves to a new steady state from the previous one, without
to be reset and re-initialized, therefore realizing a
Reactive Path-Planner
:a
path-planner that reacts to external (environmental) changes. The algorithm
complexity is strictly related to the obstacles distributions and it is impossible
to evaluate it because of the huge number of possible obstacles distributions.
We can only make a good estimate of the upper-bound. In the worst cases, the
number of free cells is approximatively
N/
2, where
N
is the total number of cells
of the
C
-
Space Bitmap
, therefore, the longest distance covered is nearly of
N/
2
cells. The longest paths (going farthest and then coming back) cover 2
2
cells
and require about N updating steps to be computed. Thus, the upper-bound
of the complexity is
O
(
N
2
). In cluttered environments, the result can be much
better because the number of free cells is lower.
5 Experimental Results
In this section, we illustrate only few experimental results (because of the limited
space) obtained with the algorithm previously described.
