Influence diagrams are decision theoretic extensions of Bayesian networks. They are applied to diverse decision problems. In this paper we apply influence diagrams to the optimization of a vehicle speed profile. We present results of computational experiments in which an influence diagram was used to optimize the speed profile of a Formula 1 race car at the Silverstone F1 circuit. The computed lap time and speed profiles correspond well to those achieved by test pilots. An extended version of our model that considers a more complex optimization function and diverse traffic constraints is currently being tested onboard a testing car by a major car manufacturer. This paper opens doors for new applications of influence diagrams.
Optimization of a vehicle speed profile is a well known
problem studied in literature. Some authors minimize the
energy consumption
In this paper we describe an application of influence
diagrams to the problem of the optimization of a vehicle speed
profile. Speed profile specifies the vehicle speed at each
point of the path. We illustrate the proposed method using
an example of the speed profile optimization of a Formula 1
race car at the Silverstone F1 circuit
There are two key properties that allow efficient computations. The first one is that the overall utility function is the sum of local utilities in all considered segments of the vehicle path. This is the case not only when the goal is to minimize the total time, but also when we aim at the minimal total fuel consumption or a linear combination of these two. The second key property is the Markov property. This allows to aggregate the whole future in one probability and one utility potential. These potentials are defined over the speed variable in the current path segment.
The paper is organized as follows. In Section 2, we describe the physical model of a vehicle and define the problem of the vehicle speed profile optimization. In Section 3, we introduce influence diagrams and in Section 4 we apply them to the vehicle speed profile optimization. The results of numerical experiments with real data are presented in Section 5. Section 6 reviews the related work. In Section 7, we conclude the paper by a summary of our contribution and by a discussion of our future work. 2
First, we describe a simple physical model of a vehicle.
The content of this section is based on
We model a vehicle as a point mass moving along a path, see Figure 1. We split the path into n 2 N small segments of a specified length (e.g., 5 meters). Let s denote the length of each segment, i 2 f0; : : : ; ng be the path length coordinate, [i; i + 1] be the segment between path length coordinates i and i + 1. We assume that the acceleration is constant at each segment. Let vi be the velocity at i, and ai the acceleration at the segment [i; i + 1]. The velocity vi+1 at i + 1 is a function of the velocity vi and acceleration ai: vi+1 Time ti+1 spent at the path segment [i; i + 1] is: ti+1 The vehicle is controlled by a control variable ui, which is assumed to be constant at the segment [i; i+1]. The control variable ui takes values from interval [ 1; +1], where negative values represent braking and positive values represent accelerating. We use variable ui to control acceleration ai: ai where atmax and atmin are engine and brakes characteristics, namely the maximum tangential acceleration and deceleration, respectively. cv is the deceleration coefficient for aerodynamic drag.
Example 1. For a F1 race car: ai = ai(ui; vi)
The vehicle path is characterized by a radius profile, which is defined as the radius ri of the circular arc which best approximates the path curve at each point i = 1; : : : ; n (see Figure 1). The radius ri defines the maximum speed at point i as vi vimax = pamax ri ; n (3) (4) (5)
Lap distance[m] where anmax is the maximum lateral acceleration. Example 2. For a typical F1 race car anmax = 30 m s 2. This implies that vimax = p30 ri : (6) If ri = 30 m then the maximum speed is 108 km h 1. Example 3. In Figure 2, we present the radius and maximum speed profiles of the F1 Silverstone circuit (the bridge version). The radius larger than 500 meters is not depicted1. From the radius profile, we derive the maximum speed profile by use of formula (6).
0 1000 2000 3000 4000
5000
Lap distance [m]
Other restrictions on maximal and minimal tangential accelerations are due to friction forces at the tires, which restricts the control signals: juij uimax(vi) = s 1
vi vimax 4 : (7) Now, we can formally specify the problem.
Definition 1 (Vehicle speed profile optimization problem). The goal is to find a vehicle speed profile vi; i = 1; : : : ; n such that
1Radius 500 meters allows maximum speed of 441 km h 1 – a speed never reached by an F1 race car. v0 is the actual speed of the vehicle at coordinate 0, it minimizes the total time Pn i=1 ti, it satisfies the speed constraints specified by formula (5) for i = 0; 1; : : : ; n and it satisfies the control constraints specified by formula (7) for i = 0; 1; : : : ; n.
Remark. Please, note that an optimal speed profile can be also specified by values of control variable ui for i = 0; : : : ; n 1, from which it is computed.
An influence diagram
A solution to the decision problem described by an influence diagram consists of a series of decision policies for the decision variables. Decision policy for decision variable U defines for each configuration of parents of U a probability distribution over the states of U . Decision strategy is a sequence of decision policies, one for every decision variable. The goal is to find an optimal decision strategy that maximizes the expected total utility. 3.1
Several methods for solving influence diagrams were
proposed. A simple method was published already in
We decided to use a method that employs a strong junction
tree
To every clique C in the junction tree, we associate a
probability potential C and a utility potential C . Let C1 and
C2 be adjacent cliques with separator S. To pass a
message from clique C2 to clique C1 potentials C1 and C1
are updated as follows2
C1 C1 +
S ;
S ; S (8) (9) where
S =
M C2nS
S =
M ( C2 C2nS
C2 ) and M is a generalized marginalization operation. The operator M acts differently for a random variable A and a decision variable U of a (probability or utility) potential : M = X ; A
A
M U = max
U
;
where PA is a shorthand for summation over all states of A
and maxU denotes maximum over all states of U . For a set
of variables C, we define MC as a sequence of
singlevariable marginalizations. The elimination order follows
the inverse order as determined by the relation . In case of
discrete variables, the complexity of one message passing
operation is O(jC1j + jC2j + jSj), where jCj denotes the
number of combinations of states of variables in C.
Despite its similarity with the junction tree algorithm for
Bayesian networks
In this section, we use the physical model of a vehicle from Section 2 to create an influence diagram for the speed profile optimization. We split the vehicle path into n segments of the same length s. In each segment [i; i + 1], i 2 f0; : : : ; n 1g there are three random variables Vi; Ai; and Vi+1, one decision variable Ui, and one utility potential Ti. A part of influence diagram corresponding to one path segment is depicted in Figure 3. The influence diagram used in the final experiments reported in Section 5 consisted of 1010 parts, one for a segment 5 meters long.
Vi Ui
Ai
Ti+1 Vi+1
Variable Vi corresponds to the vehicle speed in the beginning of the segment (at point i). Ai corresponds to the vehicle acceleration in the segment [i; i + 1] and it is assumed to be constant in this segment. Vi+1 is the vehicle speed at the end of the segment (at point i + 1). The decision variable Ui corresponds to the vehicle control signal whose positive values denote application of vehicle accelerator and negative values ones an application of brakes. Utility function Ti corresponds to time spent at segment [i; i + 1]. In our implementation the actual values of Ti are time savings achieved at segment [i; i + 1]. They are computed by subtracting time spent by the vehicle in the segment from a constant tmax – the maximum considered time3 the vehicle may spend at a segment of length s. This allows us to use maximization over non-negative utility potentials, which is required when working with random variables having states of zero probability.
3E.g., tmax is time for a minimal race speed 100 km=h, which is equal to 0:036 seconds if s = 1 meter. In this paper we consider discrete random and discrete decision variables. For all i 2 f0; : : : ; ng, the variable Vi takes its values from V, which is a finite subset of interval [0; 400] measured in km=h, the values of Ai are from A, which is a finite subset of interval [ 34; 16] measured in ms 2, and values of decision variable Ui are from U , which is a finite subset of interval [ 100; +100], where value 100 corresponds to the maximum braking (brakes 100%) while +100 corresponds to full acceleration (accelerator 100%). Sets V, A, and U are uniformly discretized with discretization steps dV , dA, and dU , respectively. Symbols jVj, jAj, and jU j denote the cardinalities of the respective sets. The probability and utility potentials are defined using formulas from Section 2. The conditional probability distributions are “almost” deterministic. For each parent configuration of a variable there are only two states from the finite domain of that variable with a non-zero probability. These two values are those that are closest to the value computed by the corresponding formula of the physical model of the vehicle. The conditional probability distribution of the acceleration Ai is defined as:
P (Ai = ajVi = vi; Ui = ui) = 8< 1 adiAa if a = maxfa 2 A; a aig
1 adAai if a = minfa 2 A; a > aig : 0 otherwise, (10) where ai is defined by formula (3).
Example 4. Consider P (AijVi = 131km=h; Ui = 25) and A = f 34; 33; : : : ; 1; 0; 1; 2; : : : ; 16g. Using (4) we compute the acceleration of an F1 race car ai = 1:2 ms 2. The conditional probability distribution is specified in Table 1.
Similarly, we define the conditional probability distribution P (Vi+1jVi; Ai). More specifically, we combine the above approximation and formula (1). Finally, the utility function is defined as f (vi 1; vi; s) = tmax ti(vi 1; vi; s) ; (11) where function ti is defined by formula (2).
After elimination of utility nodes, the graph of the influence diagram is transformed into a strong junction tree. See Figure 4 where we present the strong junction tree of influence diagram from Figure 3. There are two cliques for path segment [i; i + 1], i 2 f0; : : : ; n 1g in the strong junction tree. We will denote them CiA and CiV and define CiA = fAi; Ui; Vig and CV = fVi+1; Ai; Vig. Cliques are i ordered reversely and the variable elimination is processed also in this order. Rectangular nodes correspond to junction tree separators.
CiA CiV
Vi Ai; Ui; Vi
Ai; Vi Vi+1; Ai; Vi
Vi+1
The junction tree is initialized as follows. Each conditional probability distribution and each utility function is assigned to a clique containing all its variables. Thus
CiA = P (AijUi; Vi) ; CiA = 0 ;
CiV = P (Vi+1jAi; Vi) ; CiV = f (Ti+1jVi; Vi+1) :
During the inference we have to consider the speed and control constraints. Both, speed and control constraints are inserted to corresponding cliques of the junction tree. 4.1.1
Speed constraints are inserted in the form of likelihood
evidence. Likelihood evidence is a vector that for each state of
the corresponding variable takes values between zero and
one
1 : 0 v vimax dV if v vimax if v = minfv 2 V; v > vimaxg (12) otherwise, where vimax is defined by (5).
Remark. The idea behind the formula (12) is that the closer the value of vimax is to the nearest speed value v 2 V that is greater than vimax the higher is the likelihood of v. In experiments, we observed that by giving a non-zero probability to the state v just above the maximum value vimax we improve the quality of results. The coarser the discretization the larger the improvement.
During the inference we include potential (Vi) into a clique containing Vi that appears first in the computations. 4.1.2
The control constraints (7) are applied during marginalization of the control variable Ui from a potential 0CV (we i will abbreviate it as ) performed in the steps specified by formulas (8) and (9).
For each vi 2 V we define a set of admissible control U 0(vi) = fui 2 U ; juij uimax(vi)g and compute an optimal admissible control value ui (vi) = arg
max ui2U0(vi) (Ui = ui; Vi = vi) : The optimal decision policy in Ui is for all vi 2 V i(ujvi) = 1 if u = ui (vi) 0 otherwise.
(13) The value of the new potential is (Vi = vi) =
(Ui = ui (vi); Vi = vi) : (14) However, whenever ui (vi) is the least or the largest value of U 0(vi) we can reduce the discretization error by considering also the nearest value ui (vi) outside Ui0. The idea is similar to (12). If (Ui = ui (vi); Vi = vi) (Ui = ui (vi); Vi = vi) then we replace the deterministic policy (13) by a probabilistic policy i(ujvi) 8 > 1 < = 1 >: 0 jui (vi) uimax(vi)j
if u = ui (vi) jui (vi)ddUUuimax(vi)j if u = ui (vi) otherwise.
Formula (14) is replaced by (Vi = vi) = i(ui jvi) + i(ui jvi) (Ui = u (vi); Vi = vi)
(Ui = ui (vi); Vi = vi) : 4.2
We solve the influence method using standard strong
junction tree method
Example 5. We can store the distribution from Example 4 using two numbers only – value val and position pos of the first non-zero number in the table. Note that the second non-zero number is positioned on pos+1 with value 1 val and there are two non-zero numbers only. The same applies to P (Vi+1jVi; Ai).
In the standard inference method the complexity in one path segment is O (jAj jVj (jVj + jU j)). In case of zero compression the complexity drops to O(jVj (jAj + jU j)). In Section 5.1 we evaluate the savings experimentally. 5
We performed experiments with a model of a Formula 1 race car at the Silverstone F1 circuit (the bridge version). The goal is to find a speed profile that minimizes the total lap time and satisfies speed and acceleration constraints as specified by Definition 1. The speed constraints are derived from radius of curves and the maximum allowed lateral acceleration amax – see formula (5). For a typical F1 race n car amax = 30 ms 2 – see Example 2. The acceleration n constraints are defined by formula (7).
In our experiments we use the influence diagram described in Section 3. The experiments were conducted in the following way: 1. Define the length of one segment s and sets of variables’ states V; A; U . 2. sInetituiaplitzhee pjuontecntitoianlstreeC.iA ; CiV ; CiA ; and CiV and 3. Insert speed and acceleration constraints to the junction tree. 4. Compute the optimal policies i; i = 0; 1; : : : ; n 1. 5. Use the optimal policy and the initial speed4 v0 = 312 km=h to compute an optimal speed profile as specified by formulas (15), (16), and (17).
The expected speed v^i+1 at coordinate i + 1 is computed
using formulas (1) and (4) from the expected control value
4Initial speed v0 is set as in
X
w(v; vi) w(v; vi) = 1 v2fvi;vig jv dV vij :
X u
u2U
i(ujv) ; (16)
(15)
(17)
All algorithms used in our experiments were implemented
in the programming language R
We compared computational time of the zero compression and standard junction tree inference methods, see Table 2. Recall that symbols jVj, jAj, and jU j denote the cardinalities of the respective sets. The experiments were carried out on an influence diagram consisting of 10 path segments. We can see that zero compression brings large computational savings for fine grained discretizations. It turned out that the number of states of the model variables should be in accordance with the path segmentation. The finer is the path segmentation, the more variables’ values are required. Discretization that is not well balanced with the path segmentation leads to oscillations of decision (control) variables as it is illustrated for s = 1m, jVj = jAj = jU j = 100 in Figure 5. 750
800 Lap Distance [meters] 850 750
800 Lap Distance [meters] 850 Settings: s = 1m, jVj = jAj = jU j = 100
Settings: s = 5m, jVj = jAj = jU j = 100 0 0 1 − lt[]ron% 050 o C In the experiments it turned out the oscillation depends strongly on jVj. Basically, there are two reasons. First, the discretization has to be able to distinguish small speed changes within one segment of the path. The reason can be elucidated by the following example.
Example 6. Consider uniformly accelerated motion with the initial speed v0 2 f200 km=h; 300 km=hg. In case of full throttle, the acceleration computed by formula (4) is a =: 9:52 ms 2 and a =: 1:42 ms 2, respectively. Considering segments of various length s, we can compute the speed at the end of the respective segment using formula (1). From Table 3 we can see that in case of s = 1 m the discretization has to be fine grained in order to capture small speed changes within such a short segment.
The second reason is the inference algorithm itself. Information passes through clique separators. In Figure 4 we can see that all separators contain Vi and every second separator consists of single Vi only. Hence, the size of V limits the information flow between respective cliques. In other words, jVj represents a bottleneck of the inference mechanism.
Representative results for the whole Silverstone F1 circuit are presented in Table 4. The expected lap time is quite stable with respect to different discretizations. For the final experiments we selected the configuration printed in boldface since from those that respect the speed and acceleration constraints well it is least computationally demanding.
We used the influence diagram to compute the speed
profile for the Silverstone F1 circuit. It is plotted in the upper
part of Figure 6 by a full line. The bridge version of
Silverstone circuit is 5049 meters long, which corresponds to
1010 segments 5m long. In this figure we compare the
computed speed profile with a test pilot performance at the
Silverstone F1 circuit
It is interesting to compare the total lap time estimated by the influence diagram model with results achieved by F1 pilots. While the model estimated time 83:95 seconds is little lower than time achieved by the test pilot – 85:51 seconds, it is higher than the fastest ever lap time – 78:12 seconds – attained by Sebastian Vettel with his Red Bull-Renault in the qualification of the 2009 British Grand Prix. 5.4
The analytic solution was presented in
The speed profile optimization problem can be also
specified using Markov decision processes (MDPs)
We proposed an application of influence diagrams to speed profile optimization and tested it in a real-life scenario. We summarize what we have achieved and what we have learned:
We were able to find optimal solutions efficiently. We verified the solutions are in accordance with the analytical solution of the considered problem.
An important advantage of influence diagrams is that once the policy is computed, it can be immediately used to update the optimal speed profile under modified circumstances. For example, if the driver has to slow down because of an unexpected traffic situation, the policy immediately provides the best new control value and the speed profile is specified by following the precomputed optimal policies.
Influence diagrams are especially handy in more complex real-life scenarios where the analytic solution is unknown.
In applications, different optimality criteria come into
play. We can do the computations efficiently as long
as they decompose additively along the path segments.
In future we plan to optimize speed profiles using influence
diagrams with continuous variables. Inspired by the work
of
This work was supported by the Czech Science Foundation through project 13–20012S.
Infl. diagram 4000
5000 Infl. diagram: 83.95 s Analytic sol.: 82.70 s
Analytic sol. 0 1000
2000 3000 Lap Distance [meters]