Information Technology Reference
In-Depth Information
a)
b)
Fig. 3.
An example of a) a world map (Occupancy Grid), b) the result of the evolution
of the Obstacles Layer for the ”L-Robot” of Fig. 2.a
The latter is the set of all the admissible movements as defined by the specific
kinematics of the robot. The admissibility of a move is also influenced by the
vicinity of the obstacles: an obstacle too close to the robot has the effect to
inhibit some of its movements. The attribute evaluated in this layer (
Obstacles
Attribute
) is a boolean:
Obst
c
(
θ,µ
)
∈{True,False}
, and represents the admis-
sibility of each move in each robot pose, on the base of the obstacles distribution
also. Therefore, this is a 4D CA and its transition function is the application:
R
2
×
SO
(2)
×{Move}→{True,False}
.
False if ∃a ∈ A
0
:
isObstacle
(
c
+
a
)
∧
(
c
+
a
)
∈GC
Obst
c
(
θ, µ, t
)
otherwise
Obst
c
(
θ, µ, t
+1)=
∀t>
0
, ∀c ∈GC, ∀θ ∈D, ∀µ ∈{Move}
As a matter of fact, this layer is composed with sublayers, one for each robot
orientation and move: it is itself a Multilayered CA on a 2D domain (the space
R
2
of positions). It is a particular CA also for another reason: each sublayer has
a non-standard fixed architecture [10], i.e. the neighborhood does not have the
standard square shape. The neighborhood shape reflects the motion silhouette
of the robot during a movement (sweeping) as in the example of Fig. 2.d. In fact,
the above transition function simply realizes a collision test: given a robot pose
(
x,y,θ
) and an admissible (just for the kinematics) move
µ
, it will test if, during
the movement, the silhouette overlaps an obstacle. In this case, the cell (
x,y,θ,µ
)
is marked
False
, with the meaning that the move
µ
, normally admissible, is not
admissible for that particular pose because of the presence of the obstacle. In
other words, the presence of an obstacle cell inhibits a number of movements
in the surrounding cells. The test is implemented very easily: each automaton
searches in its (non-standard) neighborhood if there is an obstacle cell. If there is,
the robot cannot execute the move without to collide with an obstacle. The test
is very fast because all the neighborhood shapes are automatically precalculated
off-line starting from the basic robot silhouette. In Fig. 3.b is shown the result of
the evolution of the layer for a ”L-Robot” from the Occupancy Map (Fig. 3.a).
