Information Technology Reference
In-Depth Information
they let a CA to build a Voronoi Diagram. In this paper, we have used CA as
a formalism for merging a Grid Model of the world (Occupancy Grid) with the
Configuration Space (
C-Space
) of a robot and Numerical (Artificial) Potential
Field Methods, with the aim to give a simple and fast, even if sub-optimal, so-
lution for the path-planning problem for a non-holonomic mobile robot. This
method uses a directional (anisotropic) propagation of distance values between
neighbor automata to build a potential hypersurface embedded in 4D space. Us-
ing a constrained version of the descending gradient is possible to find out all the
admissible, equivalent and shortest (for a given metric of the space) trajectories
that connect two points of the robot
C-Space
.
2 Problem Statements
A wide variety of world models can be used to describe the interaction between
an autonomous agent and its environment. One of the most important is the
Configuration Space (
C−Space
) [6,8]. The
C−Space
of a rigid body is the set
of all its configurations. If the robot can translate and rotate on a 2D surface,
its
C−Space
is a 3D manifold R
2
×
SO
(2). It can be modelled as a 3D Bitmap
GC
(
C
-
Space Bitmap
), represented by the application
GC
:
W→{
0
,
1
}
, where
0s represent non admissible configurations. The
C−Potential
is a function
U
(
q
)
defined over the
C−Space
that ”drives” the robot through the sequence of con-
figuration points to reach the goal pose [2]. Let us introduce some other assump-
tions: 1) space topology is finite and planar; 2) the robot has a lower bound on
the steering radius (non-holonomic vehicle). The latter assumption introduces
important restrictions on the types of trajectories to be found.
Cellular Automata are automata defined on a Cellular Space Z
n
with tran-
sition functions invariant under translation [3]:
f
c
(
·
)=
f
(
·
)
, ∀c ∈
Z
n
,
f
(
·
):
Q
|A
0
|
→
Q
, where
c
is the coordinate vector identifying a cell,
Q
is the set of
states of an automaton and
A
0
is the set of arcs outgoing from a cell to the
neighbors. The mapping between the Robot Path-Planning Problem and CA is
quite simple: every cell of the
C−Space Bitmap GC
is an automaton of a CA.
The state of every cell contributes to build the
C−Potential
U
(
q
) through a
diffusion mechanism between neighbors. The way the diffusion is performed (in
this case with an anisotropic mechanism), contributes to respect the given con-
straints. The trajectories are found following the minimum valley of the surface
U
(
q
). In this work, we use a simple extension of the CA model: we associate a
vector of attributes (state vector) to every cell. Each state vector depends on the
state vectors of the cells in the neighborhood. There is a second point of view:
this is a Multilayered Cellular Automaton [1], where each layer corresponds to
a subset of the state vector components. Each subset is evaluated in a single
layer and depends on the same attribute of the neighbor cells in the same layer
and depends also on the states of the corresponding cell and its neighbors in
other layers. In the following section, we describe each layer and the transition
functions implemented in its cells.
