![](bg6.png)
all path cost results in a combination of robot met-
ric, environment metric and surface gradient (a kind
of ”path-planner metric”). Two main properties can
be demonstrated: the termination of the propagation
of the potential values through the C-Space and the
absence of local minima. The later property ensures
to achieve the goal (in the global minimum) just fol-
lowing the negated gradient vector of the C-Potential
function without stalling in any local minima.
4 EXPERIMENTS AND RESULTS
We have generated some synthetic elevation maps and
introduced an obstacle distribution to observe the al-
gorithm behavior. An interesting property of this al-
gorithm is the simultaneous computation of trajecto-
ries from more than one starting position. We exploit
this property to show multiple problems in the same
environment. In the example of Fig. 9, the terrain has
a group of three ”hills” in the middle, and we con-
sider five different starting points of the robot and one
goal (bottom-left). From any position, the robot tries
to move around the hills, unless the shortest path is
to pass over them (in any case, at the minimum ele-
vation). The performance tests, carried out with an
Intel Pentium IV 2.26 GHz PC, gave the following
result (mean times over 500 repetitions ): 182 ms
(Fig. 9), 26.7 ms (Fig. 8). The complexity of a path-
planning algorithm is always strictly related to the ob-
stacles distribution. A good upper-bound estimate, in
the worst cases without obstacles enlargements, can
be done. Considering that the longest paths cover ap-
proximatively 1/2 of the total number of cells N of
the 2D Workspace Bitmap, and require nearly 2
N
2
N
cells updates to be computed, a realistic upper-bound
of the complexity is O(N
2
). If we take also into ac-
count of the obstacles enlargements, the result is even
better since the number of free cells is much lower,
especially in a cluttered world.
5 CONCLUSION
In this paper we have described an architecture solu-
tion for the Path-Planning Problem for mobile robots
with generic shapes (user defined) and with generic
kinematics on variable (regular) terrains based on
(Multilayered) Cellular Automata. Another impor-
tant property of this algorithm is related to the con-
sistency of the solution found. For a given terrain sur-
face, the solution found (if it exists) is the set of all
shortest paths (for the given metric) that connect the
starting cell to the goal cell. The CA evolution can be
seen as a motion from one point to another point of a
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 (e.g. adding, delet-
ing or moving one or more obstacles), then the point
becomes unstable and the CA starts to evolve again
towards a new steady state, finding a new set of opti-
mal trajectories (Incremental Updating).
REFERENCES
Barraquand, J., Langlois, B., and Latombe, J. C. (1992).
Numerical potential field techniques for robot path
planning. IEEE Trans. on Systems, Man and Cyber-
netics, 22(2):224–241.
Jahanbin, M. R. and Fallside, F. (1988). Path planning us-
ing a wave simulation technique in the configuration
space. In Artificial Intelligence in Engineering: Ro-
botics and Processes (J. S. Gero ed.), Southampton.
Computational Mechanics Publications.
Kathib, O. (1985). Real-time obstacle avoidance for ma-
nipulator and mobile robots. In Int. Conf. on Robotics
and Automation.
Kobilarov, M. and Sukhatme, G. S. (2004). Time optimal
path planning on outdoor terrain for mobile robots un-
der dynamic constraints. In IEEE/RSJ Int. Conf. on
Intelligent Robots and Systems.
Lozano-P
´
erez, T. (1983). Spatial planning: A configura-
tion space approach. IEEE Trans. on Computers, C-
32(2):108–120.
Lozano-P
´
erez, T. and Wesley, M. A. (1979). An algo-
rithm for planning collision-free paths among polyhe-
dral obstacles. Comm. of the ACM, 22(10):560–570.
Pai, D. K. and Reissell, L. M. (1998). Multiresolution rough
terrain motion planning. IEEE Trans. on Robotics and
Automation, 14(1):19–33.
Sipper, M., editor (1997). Evolution of Parallel Cellular
Machines - The Cellular Programming Approach, vol-
ume 1194 of LNCS. Springer-Verlag.
Tzionas, P. G., Thanailakis, A., and Tsalides, P. G. (1997).
Collision-free path planning for a diamond-shaped ro-
bot using two-dimensional cellular automata. IEEE
Trans. on Robotics and Automation, 13(2):237–250.
Zelinsky, A. (1994). Using path transforms to guide the
search for findpath in 2d. Int. J. of Robotics Research,
13(4):315–325.
A REACTIVE MOTION PLANNER ARCHITECTURE FOR GENERIC MOBILE ROBOTS BASED ON
MULTILAYERED CELLULAR AUTOMATA
87