Information Technology Reference
In-Depth Information
maximum curvature constraint. From a configuration (
c,d
), the robot can achieve
a set of configurations (
γ,δ
)
, ∀γ ∈ I
c
(
d
)
, ∀δ ∈ D
(
γ,d
), where
I
c
(
d
)
⊆ I
c
is the
subset of neighbor cells reachable from the configuration (
c,d
), and
D
(
γ,d
)
⊆ D
is the subset of admissible orientations at the destination cell
γ
compatible with
the leaving direction
d
. The transition function is defined as follows:
1
ifc
=
goal cell ∧ d
=
final direction
minAttr
c
(
d, t
)
if ¬Obst
c
(
d, t
)
∧ Attr
c
(
d, t
)
=
minAttr
c
(
d, t
)
Attr
c
(
d, t
)
Attr
c
(
d, t
+1)=
otherwise
∀t>
0
, ∀c ∈GC, ∀d ∈ D
where:
minAttr
c
(
d,t
) = min
∀γ∈I
c
(
d
)
∀δ∈D
(
γ,d
)
{Attr
γ
(
δ, t
)+
Cost
(
c,d,γ,δ
)
}
and
Cost
(
·, ·, ·, ·
) is the length/cost of the move from the current configuration (
c,d
)
to the configuration (
γ,δ
), and
Obst
c
(
d,t
) is the admissibility value of the same
move evaluated in the Obstacle Layer. If we change the movement costs, we can
consider robots with different types of kinematics. For example, the kinematics
(2
,
3
,
1
,
0
, High, High, High
) emulates a car-like kinematics moving only forward
(Dubin's car), while the kinematics (2
,
3
,
1
,
0
, High,
2
,
3) emulates a common car-
like kinematics moving also backward (Reed's and Shepp's car). Two main prop-
erties can be demonstrated: the termination of the propagation and the absence
of local minima (refer to [9]). The later property is very important for our aims:
it ensures to achieve the goal (the global minimum) just following the negated
gradient vector without stalling in a local minimum. The graphical represen-
tation of the potential surface is quite di
*
cult. To be able to infer its aspect,
we must reduce the number of dimensions projecting it from the 4D space to a
3D space, and obtaining a skeleton laying on the hypersurface which gives an
approximate idea of its topology. This skeleton is a tree (the root is in the goal)
composed of the admissible robot movements that connect one cell to another.
In Fig. 4 are shown some evolution steps of the growing of the skeleton tree.
3.4 Paths Extraction Layer
This layer determines all the shortest paths that connect the starting point
to the goal point on the base of potential hypersurface
U
(
q
) computed in the
previous layer. The method extends the descent gradient methods described in
[4,12]. Because of the steering constraint, we have to use a constrained negated
gradient, i.e. the gradient vector is evaluated only for the admissible directions.
The resulting trajectories (Fig. 5.a) are subsets of the attraction skeleton of
Fig. 4.f, i.e. only those parts of the skeleton which connect the starting cell to
the goal cell belong to the final trajectories.
4Algorithm Properties
This algorithm has the advantage of being computable in an asynchronous way:
there is no specific evaluation order of the cells in each layer, and every layer can
be updated without waiting that the other layers have reached a stationary point.
