Influence diagrams for the optimization of a vehicle speed profile Václav Kratochvı́l and Jiřı́ Vomlel Institute of Information Theory and Automation Czech Academy of Sciences Pod vodárenskou věžı́ 4, Prague, 182 08, Czech Republic Abstract to compare the influence diagram solution with the analytic one. Both solutions have a close correspondence. Influence diagrams are decision theoretic exten- The proposed method allows applications of influence di- sions of Bayesian networks. They are applied to agrams to more complex scenarios of a speed profile op- diverse decision problems. In this paper we ap- timization. Speed constraints can be invoked not only by ply influence diagrams to the optimization of a path radii, but also by other causes like traffic regulations, vehicle speed profile. We present results of com- weather conditions, distance to other vehicles, etc. More- putational experiments in which an influence di- over, these conditions can be changing dynamically. Also, agram was used to optimize the speed profile of the criteria to be optimized need not be the total time only. a Formula 1 race car at the Silverstone F1 cir- We can consider also safety, fuel consumption, etc. We be- cuit. The computed lap time and speed profiles lieve that influence diagrams are very appropriate for these correspond well to those achieved by test pilots. situations since optimum policies are precomputed for any An extended version of our model that consid- speed the vehicle can attain. The optimal speed profile can ers a more complex optimization function and di- be quickly updated if the conditions change. verse traffic constraints is currently being tested There are two key properties that allow efficient computa- onboard a testing car by a major car manufac- tions. The first one is that the overall utility function is the turer. This paper opens doors for new applica- sum of local utilities in all considered segments of the ve- tions of influence diagrams. hicle path. This is the case not only when the goal is to minimize the total time, but also when we aim at the mini- mal total fuel consumption or a linear combination of these 1 INTRODUCTION two. The second key property is the Markov property. This allows to aggregate the whole future in one probability and Optimization of a vehicle speed profile is a well known one utility potential. These potentials are defined over the problem studied in literature. Some authors minimize the speed variable in the current path segment. energy consumption (Monastyrsky and Golownykh, 1993; The paper is organized as follows. In Section 2, we de- Chang and Morlok, 2005; Saboohi and Farzaneh, 2009; scribe the physical model of a vehicle and define the prob- Hellström et al., 2010; Mensing et al., 2011; Rakha et al., lem of the vehicle speed profile optimization. In Section 3, 2012) while others aim at minimizing the total time (Vele- we introduce influence diagrams and in Section 4 we apply nis and Tsiotras, 2008). them to the vehicle speed profile optimization. The results In this paper we describe an application of influence dia- of numerical experiments with real data are presented in grams to the problem of the optimization of a vehicle speed Section 5. Section 6 reviews the related work. In Section 7, profile. Speed profile specifies the vehicle speed at each we conclude the paper by a summary of our contribution point of the path. We illustrate the proposed method using and by a discussion of our future work. an example of the speed profile optimization of a Formula 1 race car at the Silverstone F1 circuit (Velenis and Tsiotras, 2008). The goal is to minimize the total lap time. This ex- 2 PHYSICAL MODEL OF THE VEHICLE ample will be used throughout the paper to explain the key concepts and for the final experimental evaluation of the First, we describe a simple physical model of a vehicle. proposed approach. An advantage is that the optimal solu- The content of this section is based on (Velenis and Tsio- tion is known (Velenis and Tsiotras, 2008). This allows us tras, 2008). Although this model is too simple to model the 44 complex behavior of a car-like vehicle, it is sufficient for where amax n is the maximum lateral acceleration. the optimization of a vehicle speed profile. Example 2. For a typical F1 race car amax = 30 m · s−2 . n This implies that √ i−1 i vimax = 30 · ri . (6) vi i+1 If ri = 30 m then the maximum speed is 108 km · h−1 . vi+1 Example 3. In Figure 2, we present the radius and maxi- mum speed profiles of the F1 Silverstone circuit (the bridge ri version). The radius larger than 500 meters is not de- picted1 . From the radius profile, we derive the maximum speed profile by use of formula (6). Figure 1: A point mass moving along a path. We model a vehicle as a point mass moving along a path, see Figure 1. We split the path into n ∈ N small seg- 100 200 300 400 ments of a specified length (e.g., 5 meters). Let s denote the length of each segment, i ∈ {0, . . . , n} be the path Radius [m] length coordinate, [i, i + 1] be the segment between path length coordinates i and i + 1. We assume that the accel- eration 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 0 acceleration ai : 0 1000 2000 3000 4000 5000 Lap distance[m] p vi+1 = vi+1 (vi , ai , s) = (vi )2 + 2 · s · ai . (1) Time ti+1 spent at the path segment [i, i + 1] is: 400 Maximum Speed [km/h]  −1 vi + vi+1 300 ti+1 = ti+1 (vi , vi+1 , s) = s · . (2) 2 200 The vehicle is controlled by a control variable ui , which is assumed to be constant at the segment [i, i+1]. The control 100 variable ui takes values from interval [−1, +1], where neg- ative values represent braking and positive values represent 0 accelerating. We use variable ui to control acceleration ai : 0 1000 2000 3000 4000 5000  max at · ui − cv · (vi )2 if ui ≥ 0 Lap distance [m] ai = (3) at · ui − cv · (vi )2 if ui < 0 , min where amax t and amin t are engine and brakes characteris- Figure 2: Radius and maximum speed profiles. tics, namely the maximum tangential acceleration and de- celeration, respectively. cv is the deceleration coefficient for aerodynamic drag. Other restrictions on maximal and minimal tangential ac- Example 1. For a F1 race car: celerations are due to friction forces at the tires, which re- stricts the control signals: ai = ai (ui , vi ) s 4 16 · ui − 0.0021 · (vi )2  if ui ≥ 0  vi = 18 · ui − 0.0021 · (vi )2 if ui < 0 . (4) |ui | ≤ umax i (v i ) = 1 − . (7) vimax The vehicle path is characterized by a radius profile, which Now, we can formally specify the problem. is defined as the radius ri of the circular arc which best Definition 1 (Vehicle speed profile optimization problem). approximates the path curve at each point i = 1, . . . , n The goal is to find a vehicle speed profile vi , i = 1, . . . , n (see Figure 1). The radius ri defines the maximum speed such that at point i as 1 Radius 500 meters allows maximum speed of 441 km · h−1 vi ≤ vimax = p amax n · ri , (5) – a speed never reached by an F1 race car. 45 • v0 is the actual speed of the vehicle at coordinate 0, We decided to use a method that employs a strong junction Pn tree (Jensen et al., 1994; Jensen and Nielsen, 2007), which • it minimizes the total time i=1 ti , is a refinement of methods of Shenoy (1992) and Shachter and Peot (1992). The utility nodes are eliminated first by • it satisfies the speed constraints specified by for- marrying all parents of each utility node and by including mula (5) for i = 0, 1, . . . , n and the corresponding utility potentials to cliques containing all • it satisfies the control constraints specified by for- parents of the utility node. It has been shown that an in- mula (7) for i = 0, 1, . . . , n. fluence diagram can be solved exactly by message passing performed on the strong junction tree. Remark. Please, note that an optimal speed profile can be also specified by values of control variable ui for i = To every clique C in the junction tree, we associate a prob- 0, . . . , n − 1, from which it is computed. ability potential ΦC and a utility potential ΨC . Let C1 and C2 be adjacent cliques with separator S. To pass a mes- sage from clique C2 to clique C1 potentials ΦC1 and ΨC1 3 INFLUENCE DIAGRAMS are updated as follows2 (Jensen et al., 1994): An influence diagram (Howard and Matheson, 1981) is a Φ0C1 = ΦC1 ∗ ΦS , (8) Bayesian network augmented with decision variables and ΨS utility functions. In graphs, random variables are depicted Ψ0C1 = ΨC1 + , (9) ΦS as circles, decision variables as squares, and utility func- tions as diamonds. As an example, see Figure 3. Random where and decision variables are denoted by capital letters, their states by respective lower-case ones. ΦS = M ΦC2 , ΨS = M (ΦC2 ∗ ΨC2 ) C2 \S C2 \S A solution to the decision problem described by an influ- and M is a generalized marginalization operation. The op- ence diagram consists of a series of decision policies for the erator M acts differently for a random variable A and a decision variables. Decision policy for decision variable U decision variable U of a (probability or utility) potential Ξ: defines for each configuration of parents of U a probabil- ity distribution over the states of U . Decision strategy is a X MΞ = Ξ, MΞ = max Ξ , sequence of decision policies, one for every decision vari- A A U U able. The goal is to find an optimal decision strategy that P maximizes the expected total utility. where A is a shorthand for summation over all states of A and maxU denotes maximum over all states of U . For a set 3.1 SOLVING INFLUENCE DIAGRAMS of variables C, we define MC Ξ as a sequence of single- variable marginalizations. The elimination order follows Several methods for solving influence diagrams were pro- the inverse order as determined by the relation ≺. In case of posed. A simple method was published already in (Howard discrete variables, the complexity of one message passing and Matheson, 1981) where influence diagrams were intro- operation is O(|C1 | + |C2 | + |S|), where |C| denotes the duced. They proposed to unfold respective influence dia- number of combinations of states of variables in C. gram into a decision tree and solve it using dynamic pro- Despite its similarity with the junction tree algorithm for gramming. Another algorithm was developed by (Shachter, Bayesian networks (Lauritzen and Spiegelhalter, 1988), 1986) and it foreshadowed the future graphical algorithms. only the collection phase of the strong junction tree is Basically, one can gradually simplify respective influence needed to solve an influence diagram. The maximum ex- diagram by successive removing nodes from its graph. pected utility value can be obtained by doing the remain- When a decision node is being removed (by maximizing ing marginalization in the root. Above that, we can easily expected utility), the maximizing alternative is recorded get the optimal decision policy for decision variables dur- as the optimal policy. Three operations to remove graph ing the message passing process. For every combination of nodes were introduced; at least one of them can be used parents of a decision variable (in our case the only parent at any given time. Another method is to reduce an influ- is the speed variable), it is the alternative with the maximal ence diagram into a Bayesian network by converting de- expected utility in the moment of message passing. cision variables into random variables – the solution of a specific inference problem in this Bayesian network then Note that this approach is highly dependent on the process corresponds to the optimal decision policy of the influence of building a junction tree from an influence diagram. The diagram (Cooper, 1988). One can also transform an in- 2 Given two potentials Φ and Ψ, their product Φ ∗ Ψ and the fluence diagram into a valuation network and solve it us- quotient Φ/Ψ are defined in the natural way, except that 0/0 is ing variable elimination in the valuation network (Shenoy, defined to be 0 and x/0 for x 6= 0 is undefined (Jensen et al., 1992). 1994). 46 size of cliques is determining the speed of the algorithm. Consequently, the junction tree algorithm is typically in- Table 1: The conditional probability table P (Ai |Vi = feasible for solving large influence diagrams. Fortunately, 131km/h, Ui = 25) ai ... -1 0 1 2 3 ... this is not the case for our application. P (ai |vi , ui ) 0 0 0 0.8 0.2 0 0 4 INFLUENCE DIAGRAMS FOR VEHICLE SPEED PROFILE In this paper we consider discrete random and discrete deci- OPTIMIZATION sion variables. For all i ∈ {0, . . . , n}, the variable Vi takes its values from V, which is a finite subset of interval [0, 400] In this section, we use the physical model of a vehicle from measured in km/h, the values of Ai are from A, which Section 2 to create an influence diagram for the speed pro- is a finite subset of interval [−34, 16] measured in ms−2 , file optimization. We split the vehicle path into n seg- and values of decision variable Ui are from U, which is a ments of the same length s. In each segment [i, i + 1], finite subset of interval [−100, +100], where value −100 i ∈ {0, . . . , n − 1} there are three random variables Vi , Ai , corresponds to the maximum braking (brakes 100%) while and Vi+1 , one decision variable Ui , and one utility poten- +100 corresponds to full acceleration (accelerator 100%). tial Ti . A part of influence diagram corresponding to one Sets V, A, and U are uniformly discretized with discretiza- path segment is depicted in Figure 3. The influence dia- tion steps dV , dA , and dU , respectively. Symbols |V|, |A|, gram used in the final experiments reported in Section 5 and |U| denote the cardinalities of the respective sets. consisted of 1010 parts, one for a segment 5 meters long. The probability and utility potentials are defined using for- mulas from Section 2. The conditional probability distribu- Ti+1 tions are “almost” deterministic. For each parent configu- ration 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 Vi Vi+1 by the corresponding formula of the physical model of the vehicle. The conditional probability distribution of the ac- celeration Ai is defined as: Ai P (Ai = a|Vi = vi , Ui = ui ) = ai −a  1 − dA if a = max{a ∈ A, a ≤ ai }  Ui a−ai (10) 1 − dA if a = min{a ∈ A, a > ai }  0 otherwise, Figure 3: A part of influence diagram corresponding to the path segment [i, i + 1]. where ai is defined by formula (3). Example 4. Consider P (Ai |Vi = 131km/h, Ui = 25) Variable Vi corresponds to the vehicle speed in the begin- and A = {−34, −33, . . . , −1, 0, 1, 2, . . . , 16}. Using (4) ning of the segment (at point i). Ai corresponds to the we compute the acceleration of an F1 race car ai = vehicle acceleration in the segment [i, i + 1] and it is as- 1.2 ms−2 . The conditional probability distribution is spec- sumed to be constant in this segment. Vi+1 is the vehicle ified in Table 1. speed at the end of the segment (at point i + 1). The de- cision variable Ui corresponds to the vehicle control signal Similarly, we define the conditional probability distribution whose positive values denote application of vehicle accel- P (Vi+1 |Vi , Ai ). More specifically, we combine the above erator and negative values ones an application of brakes. approximation and formula (1). Finally, the utility function Utility function Ti corresponds to time spent at segment is defined as [i, i + 1]. In our implementation the actual values of Ti are time savings achieved at segment [i, i + 1]. They are f (vi−1 , vi , s) = tmax − ti (vi−1 , vi , s) , (11) computed by subtracting time spent by the vehicle in the segment from a constant tmax – the maximum considered where function ti is defined by formula (2). time3 the vehicle may spend at a segment of length s. This After elimination of utility nodes, the graph of the influ- allows us to use maximization over non-negative utility po- ence diagram is transformed into a strong junction tree. See tentials, which is required when working with random vari- Figure 4 where we present the strong junction tree of in- ables having states of zero probability. fluence diagram from Figure 3. There are two cliques for 3 E.g., tmax is time for a minimal race speed 100 km/h, which path segment [i, i + 1], i ∈ {0, . . . , n − 1} in the strong is equal to 0.036 seconds if s = 1 meter. junction tree. We will denote them CiA and CiV and define 47 CiA = {Ai , Ui , Vi } and CiV = {Vi+1 , Ai , Vi }. Cliques are improve the quality of results. The coarser the discretiza- ordered reversely and the variable elimination is processed tion the larger the improvement. also in this order. Rectangular nodes correspond to junction tree separators. During the inference we include potential φ(Vi ) into a clique containing Vi that appears first in the computations. 4.1.2 Control constraints Vi The control constraints (7) are applied during marginaliza- CiA tion of the control variable Ui from a potential Ψ0C V (we Ai , Ui , Vi i will abbreviate it as Ξ) performed in the steps specified by formulas (8) and (9). Ai , Vi For each vi ∈ V we define a set of admissible control CiV U 0 (vi ) = {ui ∈ U, |ui | ≤ umax i (vi )} Vi+1 , Ai , Vi and compute an optimal admissible control value Vi+1 u∗i (vi ) = arg max Ξ(Ui = ui , Vi = vi ) . ui ∈U 0 (vi ) The optimal decision policy in Ui is for all vi ∈ V Figure 4: The strong junction tree for the part of influence 1 if u = u∗i (vi )  diagram from Figure 3. δi (u|vi ) = (13) 0 otherwise. The junction tree is initialized as follows. Each conditional The value of the new potential is probability distribution and each utility function is assigned to a clique containing all its variables. Thus Ξ(Vi = vi ) = Ξ(Ui = u∗i (vi ), Vi = vi ) . (14) ΦCiA = P (Ai |Ui , Vi ) , ΦCiV = P (Vi+1 |Ai , Vi ) , However, whenever u∗i (vi ) is the least or the largest value ΨCiA = 0 , ΨCiV = f (Ti+1 |Vi , Vi+1 ) . of U 0 (vi ) we can reduce the discretization error by consid- ering also the nearest value u∗∗ 0 i (vi ) outside Ui . The idea is 4.1 IMPLEMENTATION OF CONSTRAINTS similar to (12). If During the inference we have to consider the speed and Ξ(Ui = u∗∗ ∗ i (vi ), Vi = vi ) ≥ Ξ(Ui = ui (vi ), Vi = vi ) control constraints. Both, speed and control constraints are then we replace the deterministic policy (13) by a proba- inserted to corresponding cliques of the junction tree. bilistic policy 4.1.1 Speed constraints |u∗ (vi )−umax  (vi )|  1− i  i dU max if u = u∗i (vi ) ∗∗ δi (u|vi ) = |u (v )−u (vi )| Speed constraints are inserted in the form of likelihood evi-  1 − i i dU i if u = u∗∗ i (vi ) dence. Likelihood evidence is a vector that for each state of  0 otherwise. the corresponding variable takes values between zero and one (Jensen, 2001, Section 1.4.6). Likelihood evidence of Formula (14) is replaced by a speed constraint is a vector φ of length |V| such that Ξ(Vi = vi ) = φ(v) = δi (u∗i |vi ) · Ξ(Ui = u∗ (vi ), Vi = vi ) if v ≤ vimax +δi (u∗∗ ∗∗   1 i |vi ) · Ξ(Ui = ui (vi ), Vi = vi ) . v−v max 1 − dVi if v = min{v ∈ V, v > vimax } (12)  0 otherwise, 4.2 ZERO COMPRESSION where vimax is defined by (5). We solve the influence method using standard strong junc- Remark. The idea behind the formula (12) is that the closer tion tree method (Jensen et al., 1994) briefly described in the value of vimax is to the nearest speed value v ∈ V that Section 3.1. But the probability potentials we are working is greater than vimax the higher is the likelihood of v. In with are sparse, i.e., they contain many zeroes. This is a experiments, we observed that by giving a non-zero proba- consequence of conditional probability distributions being bility to the state v just above the maximum value vimax we “almost” deterministic. In Hugin (Andersen et al., 1990) a 48 procedure called zero compression is employed to improve ûi (vi ), which is computed as a weighted average of poli- efficiency of inference with sparse potentials. In this proce- cies for two values v i , v i from V that are the closest to vi : dure an efficient representation of the clique tables is used so that zeros need not be stored explicitly. The savings can v̂i+1 = vi+1 (v, s, ai (ûi (vi ), vi )) , (15) X X be large: in our case, we basically reduce the dimension of ûi (vi ) = w(v, vi ) · u · δi (u|v) , (16) each table by one. The compression does not affect the ac- v∈{v i ,v i } u∈U curacy of the inference process, as it introduces no approx- |v − vi | imations (Cowell et al., 1999), i.e., it is an exact inference w(v, vi ) = 1− . (17) method. dV Example 5. We can store the distribution from Example 4 All algorithms used in our experiments were implemented using two numbers only – value val and position pos of in the programming language R (R Core Team, 2014). the first non-zero number in the table. Note that the second non-zero number is positioned on pos+1 with value 1−val 5.1 ZERO COMPRESSION EXPERIMENTS and there are two non-zero numbers only. The same applies to P (Vi+1 |Vi , Ai ). We compared computational time of the zero compression and standard junction tree inference methods, see Table 2. In the standard inference method the complexity in one Recall that symbols |V|, |A|, and |U| denote the cardinali- path segment is O (|A| · |V| · (|V| + |U|)). In case of zero ties of the respective sets. The experiments were carried out compression the complexity drops to O(|V| · (|A| + |U|)). on an influence diagram consisting of 10 path segments. In Section 5.1 we evaluate the savings experimentally. We can see that zero compression brings large computa- tional savings for fine grained discretizations. 5 EXPERIMENTS Table 2: Comparisons of the CPU time for the zero com- We performed experiments with a model of a Formula 1 pression and the standard approach. race car at the Silverstone F1 circuit (the bridge version). The goal is to find a speed profile that minimizes the total |V| |A| |U| zero compr. [s] standard [s] lap time and satisfies speed and acceleration constraints as 50 50 50 0.08 0.73 specified by Definition 1. The speed constraints are derived 100 100 100 0.20 4.78 100 100 200 0.19 7.09 from radius of curves and the maximum allowed lateral ac- 100 200 100 0.25 9.17 celeration amax n – see formula (5). For a typical F1 race 200 100 100 0.39 13.01 −2 car amax n = 30 ms – see Example 2. The acceleration 200 200 100 0.49 24.30 constraints are defined by formula (7). 200 200 200 0.50 29.61 400 100 100 0.84 38.53 In our experiments we use the influence diagram described 400 400 100 1.26 142.92 in Section 3. The experiments were conducted in the fol- lowing way: 5.2 DISCRETIZATION EXPERIMENTS 1. Define the length of one segment s and sets of vari- We tested different variable discretizations and different ables’ states V, A, U. path segmentations. The goal was to find a combination of these parameters that represents a reasonable tradeoff 2. Initialize potentials ΦCiA , ΦCiV , ΨCiA , and ΨCiV and between precision and computational time. set up the junction tree. We performed experiments on a part of Silverstone F1 cir- 3. Insert speed and acceleration constraints to the junc- cuit 180 meters long. Results of some performed experi- tion tree. ments are presented in Figure 5. In the upper part of these figures, speed profiles are depicted while the control profile 4. Compute the optimal policies δi , i = 0, 1, . . . , n − 1. is plotted in their lower part. The shaded areas are forbid- den by the speed and control constraints, respectively. 5. Use the optimal policy and the initial speed4 v0 = 312 km/h to compute an optimal speed profile as It turned out that the number of states of the model vari- specified by formulas (15), (16), and (17). ables should be in accordance with the path segmentation. The finer is the path segmentation, the more variables’ val- The expected speed v̂i+1 at coordinate i + 1 is computed ues are required. Discretization that is not well balanced using formulas (1) and (4) from the expected control value with the path segmentation leads to oscillations of deci- sion (control) variables as it is illustrated for s = 1m, 4 Initial speed v0 is set as in (Velenis and Tsiotras, 2008). |V| = |A| = |U| = 100 in Figure 5. 49 Speed [km/h] Speed [km/h] 300 300 0 100 0 100 50 50 Control [%] Control [%] 0 0 −100 −100 750 800 850 750 800 850 Lap Distance [meters] Lap Distance [meters] Settings: s = 1m, |V| = |A| = |U| = 100 Settings: s = 5m, |V| = |A| = |U| = 100 Speed [km/h] Speed [km/h] 300 300 0 100 0 100 50 50 Control [%] Control [%] 0 0 −100 −100 750 800 850 750 800 850 Lap Distance [meters] Lap Distance [meters] Settings: s = 1m, |V| = 400, |A| = |U| = 100 Settings: s = 5m, |V| = 400, |A| = |U| = 100 Figure 5: Comparisons of various path segmentations and discretizations. In the experiments it turned out the oscillation depends The second reason is the inference algorithm itself. Infor- strongly on |V|. Basically, there are two reasons. First, mation passes through clique separators. In Figure 4 we the discretization has to be able to distinguish small speed can see that all separators contain Vi and every second sep- changes within one segment of the path. The reason can be arator consists of single Vi only. Hence, the size of V limits elucidated by the following example. the information flow between respective cliques. In other Example 6. Consider uniformly accelerated motion with words, |V| represents a bottleneck of the inference mecha- the initial speed v0 ∈ {200 km/h, 300 km/h}. In case nism. of full throttle, the acceleration computed by formula (4) Representative results for the whole Silverstone F1 circuit . . is a = 9.52 ms−2 and a = 1.42 ms−2 , respectively. are presented in Table 4. The expected lap time is quite Considering segments of various length s, we can compute stable with respect to different discretizations. For the final the speed at the end of the respective segment using for- experiments we selected the configuration printed in bold- mula (1). From Table 3 we can see that in case of s = 1 m face since from those that respect the speed and accelera- the discretization has to be fine grained in order to capture tion constraints well it is least computationally demanding. small speed changes within such a short segment. 5.3 INFLUENCE DIAGRAM SOLUTION Table 3: Speed [in km/h] in case of full acceleration We used the influence diagram to compute the speed pro- v0 v1 file for the Silverstone F1 circuit. It is plotted in the upper s=1m s=5m s = 20 m 200 200.6159 203.0606 211.9774 part of Figure 6 by a full line. The bridge version of Sil- 300 300.0612 300.3058 301.2215 verstone circuit is 5049 meters long, which corresponds to 1010 segments 5m long. In this figure we compare the 50 dynamic programming. In (Velenis and Tsiotras, 2008) the Table 4: CPU and lap time for diverse path segmentations problem was solved analytically by methods of the con- and discretizations. tinuous time control (Bertsekas, 2000) using the Pontrya- s |V| |A| |U| lap time CPU time gin’s maximum principle. We compared the influence di- [m] [s] [s] agram solution with the analytic solution in Section 5.4 – 10 400 200 100 83.92 20.61 the solutions were similar. However, analytical solutions 10 800 400 200 83.83 103.94 5 400 200 100 84.09 42.88 for considered extended versions of the problem with an 5 800 200 100 83.97 166.88 advanced optimization function and additional constraints 5 800 400 200 83.95 197.93 are not known and numerical methods have to be used. 5 800 800 800 83.94 473.16 5 1000 1000 1000 83.91 588.80 1 800 400 200 84.17 2110.68 7 CONCLUSIONS AND FUTURE WORK 1 1000 1000 1000 84.10 2850.66 1 1600 1000 1000 83.96 5544.99 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 computed speed profile with a test pilot performance at the learned: Silverstone F1 circuit (Oxford Technical Solutions, 2002). In the upper part of Figure 6 the test pilot speed profile is • We were able to find optimal solutions efficiently. plotted by a dotted line. Notice that the testing pilot vi- olates these restrictions several times. Also, the test pilot • We verified the solutions are in accordance with the acceleration is slower than expected. The speed constraints analytical solution of the considered problem. used in the model seem to be too cautious and the car ac- • An important advantage of influence diagrams is that celeration ability a bit exaggerated. once the policy is computed, it can be immediately It is interesting to compare the total lap time estimated by used to update the optimal speed profile under modi- the influence diagram model with results achieved by F1 pi- fied circumstances. For example, if the driver has to lots. While the model estimated time 83.95 seconds is little slow down because of an unexpected traffic situation, lower than time achieved by the test pilot – 85.51 seconds, the policy immediately provides the best new control it is higher than the fastest ever lap time – 78.12 seconds value and the speed profile is specified by following – attained by Sebastian Vettel with his Red Bull-Renault in the precomputed optimal policies. the qualification of the 2009 British Grand Prix. • Influence diagrams are especially handy in more com- plex real-life scenarios where the analytic solution is 5.4 ANALYTIC SOLUTION unknown. The analytic solution was presented in (Velenis and Tsio- • In applications, different optimality criteria come into tras, 2008). It is plotted in Figure 7 by a dotted line together play. We can do the computations efficiently as long with the influence diagram solution. The solutions are quite as they decompose additively along the path segments. similar but there are some differences. Apparently, the ana- lytical solution does not fully comply with the acceleration In future we plan to optimize speed profiles using influence constraints. This causes differences in the speed profiles, diagrams with continuous variables. Inspired by the work otherwise they would be equivalent. We were not able to of (Kveton et al., 2006) on MDPs we plan to study infer- explain this observation. In the lower part of Figure 7 we ence in influence diagrams based on mixtures of beta dis- present the control profile of the analytic solution recon- tributions. Other possibilities to be considered are approx- structed from the speed profile of the analytic solution5 . imations by mixtures of polynomials (Shenoy and West, 2011; Li and Shenoy, 2012) or by mixtures of truncated exponentials (Cobb and Shenoy, 2008; Moral et al., 2001). 6 RELATED WORK Currently, we are applying influence diagrams to a more complex scenario with a complex utility function, for The speed profile optimization problem can be also speci- which no analytical solution is known. Methods of the con- fied using Markov decision processes (MDPs) (Puterman, trol theory, if applied to this scenario, thus need to rely on 1994) with a finite horizon, a non-stationary policy and a approximate numerical methods. non-linear stationary reward function. The solution of such an MDP can be found by the approach presented in this pa- per since solution methods of both approaches are based on Acknowledgements 5 The little oscillations are caused by imprecision of the ana- This work was supported by the Czech Science Foundation lytic speed profile taken from (Velenis and Tsiotras, 2008). through project 13–20012S. 51 400 300 Speed [km/h] 200 100 Infl. diagram: 83.95 s Testing pilot: 85.81 s 0 100 50 Control [%] 0 −100 Infl. diagram 0 1000 2000 3000 4000 5000 Lap Distance [meters] Figure 6: A comparison of speed profiles: the influence diagram and a test pilot (Oxford Technical Solutions, 2002). The shaded areas are forbidden by the speed and control constraints, respectively. 400 300 Speed [km/h] 200 100 Infl. diagram: 83.95 s Analytic sol.: 82.70 s 0 100 50 Control [%] 0 −100 Analytic sol. 0 1000 2000 3000 4000 5000 Lap Distance [meters] Figure 7: A comparison of speed profiles: the influence diagram and analytic solution (Velenis and Tsiotras, 2008). The shaded areas are forbidden by the speed and control constraints, respectively. 52 References Mensing, F., Trigui, R., and Bideaux, E. (2011). Vehicle trajectory optimization for application in Eco-driving. Andersen, S. K., Olesen, K. G., Jensen, F. V., and Jensen, In Vehicle Power and Propulsion Conference (VPPC), F. (1990). HUGIN: a shell for building Bayesian belief IEEE, pages 1–6. universes for expert systems. In Shafer, G. and Pearl, J., editors, Readings in Uncertain Reasoning, pages 332– Monastyrsky, V. V. and Golownykh, I. M. (1993). Rapid 337. Kaufman. computation of optimal control for vehicles. Transporta- tion Research Part B: Methodological, 27(3):219 – 227. Bertsekas, D. P. (2000). Dynamic Programming and Opti- mal Control. Athena Scientific, 2nd edition. Moral, S., Rumi, R., and Salmerón, A. (2001). Mixtures Chang, D. J. and Morlok, E. K. (2005). Vehicle speed pro- of truncated exponentials in hybrid bayesian networks. files to minimize work and fuel consumption. Journal of In Benferhat, S. and Besnard, P., editors, Symbolic and Transportation Engineering, 131(3):173–182. Quantitative Approaches to Reasoning with Uncertainty, volume 2143 of Lecture Notes in Computer Science, Cobb, B. R. and Shenoy, P. P. (2008). Decision making pages 156–167. Springer Berlin Heidelberg. with hybrid influence diagrams using mixtures of trun- cated exponentials. European Journal of Operational Oxford Technical Solutions (2002). RT3000 inertial and Research, 186(1):261 – 275. GPS measurement system. Technical report, Oxford- shire, UK. Cooper, G. (1988). A method for using belief networks as influence diagrams. In Proceedings of the Fourth Con- Puterman, M. L. (1994). Markov Decision Processes: Dis- ference Annual Conference on Uncertainty in Artificial crete Stochastic Dynamic Programming. John Wiley & Intelligence (UAI-88), pages 55–63, Corvallis, Oregon. Sons, New York, NY. AUAI Press. R Core Team (2014). R: A Language and Environment Cowell, R. G., Dawid, A. P., Lauritzen, S. L., and Spiegel- for Statistical Computing. R Foundation for Statistical halter, D. J. (1999). Probabilistic Networks and Expert Computing, Vienna, Austria. Systems. Springer-Verlag, Berlin-Heidelberg-New York. Rakha, H. A., Kamalanathsharma, R. K., and Ahn, K. Hellström, E., Åslund, J., and Nielsen, L. (2010). Design of (2012). Aeris: Eco-vehicle speed control at signalized an efficient algorithm for fuel-optimal look-ahead con- intersections using i2v communication. Technical Re- trol. Control Engineering Practice, 18(11):1318–1327. port FHWA-JPO-12-063, Virginia Polytechnic Institute Howard, R. A. and Matheson, J. E. (1981). Influence dia- and State University and Virginia Tech Transportation grams. In Howard, R. A. and Matheson, J. E., editors, Institute. Readings on The Principles and Applications of Deci- Saboohi, Y. and Farzaneh, H. (2009). Model for devel- sion Analysis, volume II, pages 721–762. Strategic De- oping an eco-driving strategy of a passenger vehicle cisions Group. based on the least fuel consumption. Applied Energy, Jensen, F., Jensen, F. V., and Dittmer, S. L. (1994). From 86(10):1925–1932. influence diagrams to junction trees. In Proceedings of Shachter, R. D. (1986). Evaluating influence diagrams. Op- the Tenth Conference on Uncertainty in Artificial Intelli- erations Research, 34(6):871–882. gence, pages 367–373. Morgan Kaufmann. Shachter, R. D. and Peot, M. A. (1992). Decision making Jensen, F. V. (2001). Bayesian Networks and Decision using probabilistic inference methods. In Proceedings Graphs. Springer-Verlag, New York. of the Eighth Conference Annual Conference on Uncer- Jensen, F. V. and Nielsen, T. D. (2007). Bayesian Net- tainty in Artificial Intelligence (UAI-92), pages 276–283, works and Decision Graphs, 2nd ed. Springer-Verlag, San Mateo, CA. Morgan Kaufmann. New York. Shenoy, P. P. (1992). Valuation based systems for bayesian Kveton, B., Hauskrecht, M., and Guestrin, C. (2006). decision analysis. Operations Research, 40:463–484. Solving factored MDPs with hybrid state and action Shenoy, P. P. and West, J. C. (2011). Inference in hybrid variables. Journal of Artificial Intelligence Research, bayesian networks using mixtures of polynomials. Inter- 27:153–201. national Journal of Approximate Reasoning, 52(5):641– Lauritzen, S. L. and Spiegelhalter, D. J. (1988). Local 657. computations with probabilities on graphical structures Velenis, E. and Tsiotras, P. (2008). Minimum-time travel and their application to expert systems (with discus- for a vehicle with acceleration limits: Theoretical anal- sion). Journal of the Royal Statistical Society, Series B, ysis and receding-horizon implementation. Journal of 50:157–224. Optimization Theory and Applications, 138(2):275–296. Li, Y. and Shenoy, P. P. (2012). A framework for solving hybrid influence diagrams containing deterministic con- ditional distributions. Decision Analysis, 9(1):55–75. 53