Page 456 - Automotive Engineering Powertrain Chassis System and Vehicle Body

Decisional architecture C HAPTER 14.2

expand this current node, i.e. we determine all its ðk þ 1Þs:ct ˛½0; sŠ and according to Equations 14.2.32
neighbours, then we select the neighbour which is the and 14.2.33, we have:
best according to a given criterion (a cost function) and it
becomes the current node. This process is repeated until _ sðks þ tÞ¼ _ sðksÞþ€ st (14.2.34)
the goal is reached or until the whole graph has been
1
explored. The time-optimal path is returned using sðks þ tÞ¼ sðksÞþ _ sðksÞt þ € st 2 (14.2.35)
back-pointers. In the next two sections, we detail two 2
key-points of the algorithm, namely the cost function Velocity constraint Using Equation 14.2.34,itis
assigned to each node and the node expansion. straightforward to check that a ð€ s; sÞ-bang does not vio-
Cost function A assigns a cost f(h) to every node h in late the velocity bonds of Equation 14.2.30 stated in
)
G. Since we are looking for a time-optimal path, we have Section 14.2.5.4.
chosen f(h) as being the estimate of the time-optimal Collision avoidance Recall that a ð€ s; sÞ-bang between
path in G connecting s to G and passing through h.f(h) ks and ðk þ 1Þs is collision-free if and only if:
)
)
is classically defined as the sum of two components g(h)
and h(h):
ct ˛½ks; ðk þ 1ÞsŠ; ci˛fl; .:; bg; AðsðtÞÞXB i ðtÞ¼ B
)
g(h) is the duration of the path between s and h, i.e.
the time component of h. Equation 14.2.35 provides the position of A at every
h(h) is the estimate of the time-optimal path time along the ð€ s; sÞ-bang and collision checking can
)
between h and an element of G , i.e. the amount efficiently be performed by computing the intersection
of time it would take A to reach g from its current between the two planar regions A(s(t)) and B i (t)
state with a ‘bang-coast-bang’ acceleration profile, i.e. It might be desirable to add a safety margin to the
maximum overall acceleration € s , null acceleration collision checking procedure so as to incorporate the
max
and minimum overall acceleration€ s min . When such an uncertainty on the motions of A and of the moving
6
acceleration profile does not exist, h(h) is set to þN. obstacles. In this case, the collision avoidance condition
becomes:
The heuristic function h(h) is trivially admissible, thus
A ) is guaranteed to generate the time-optimal path ct ˛½ks;ðk þ 1ÞsŠ;ci ˛f1;.;bg;
whenever it exists (Nilsson, 1980). Moreover the fact
that f(h) is locally consistent improves the efficiency of GðAðsðtÞÞ;smÞXB i ðtÞ¼ B
the algorithm.
Expansion of a node The neighbours of a given where G(X, sm) denotes the planar region X isotropically
node h ¼ðs; _ s; ksÞ are the nodes which can be grown of the safety margin sm. The safety margin can
integrate both a fixed and a velocity-dependent term, e.g.
reached from h by a ð€ s; sÞ-bang. As mentioned earlier,
€ s ˛fP€ s ks þ dR; 0; Q€ s ks þ dQg. € s ks and € s ks have to be sm ¼ c 0 þ c 1 _ sðtÞ with c 0 and c 1 ˛ R.
min
min
max
max
Complexity issues Expanding a node of the graph G
computed so as to ensure that the acceleration constraint can be done efficiently in constant time (recall that the
(Equation 14.2.29) is respected along the corresponding admissible state-time space AST is not computed, colli-
ð€ s; sÞ-bang. This computation is done in a conservative sion checking is performed directly in the two-
þ
way. First the farthest position, say s , that A can reach dimensional workspace W ). The heuristic function used
from its current state is determined. It is the position for the A search is both admissible and locally consistent
)
reached after ð€ s max ; sÞ- bang. Then the maximum curva- (see Section 14.2.5.5), the time complexity of the A )
þ
ture between s and s is determined and substituted into algorithm is therefore O(n) where n is the number of
(Equation 14.2.29) so as to yield the desired acceleration vertices in G (Farreny and Ghallab, 1987). n is defined
bounds€ s ks and€ s ks . Finally it remains to check that the
max
min
ð€ s; sÞ-bang associated with each of the candidate neigh- as:
bours does not violate the velocity and collision avoid-
2s max _ s max t max
ance constraints, i.e. that the ð€ s; sÞ-bang is included in n ¼ 2
AST. ds ds s
As we will see now, it is not necessary to compute AST The acceleration step and, to a greater extent, the
to check these two points. Velocity checking is done by time step are key factors as far as the running time of the
using the motion equation of A, while collision checking algorithm is concerned. Experimental running times and
is performed directly in W. Let us consider a ð€ s; sÞ-bang a discussion about the choice of the discretization steps
taking place between time instants ks and are given later in Section 14.2.5.5.
6
In this case, h is no longer reachable.

463