Nelson De Moura

Fawzi Nashashibi

Extraction of vehicle behaviors at intersections

Simulation of realistic urban environments is essential for the validation of decision-making algorithms in automated driving. To populate such spaces with independent agents that execute trajectories and that correctly interact with each other it is necessary to identify all possible behaviors that may arise from a set of real users trajectories. Using a twostep clustering process on trajectories with different duration, first on the position vector and then on the longitudinal velocity and acceleration, a number of behavior profiles can be identified per trajectory in intersections. To speed up the maneuver identification, the position clustering is executed on the dissimilarity matrix created using the dynamic time warp (DTW) measure between trajectories. As for the second clustering, the use of both longitudinal velocity and acceleration allows the representation of specific behaviors for each possible path. In both procedures the k-means clustering with DTW dissimilarity measure was used, combined with the Davies-Boudin score to define the optimal number of clusters. The final result provides the identification of behaviors in different geometric dispositions independently from map information and keeping the explainability property concerning each cluster.

I. INTRODUCTION

Despite all the hype in the late 2010s, automated vehicles (AV) are still in the research and development phase, with a few level 3 systems [START_REF] Sae | Taxonomy and definitions for terms related to driving automation systems for on-road motor vehicles[END_REF] starting to be deployed. The burning question on the minds of common folk concerns the behavior of AVs in dangerous/dilemma situations, which will determine its the social acceptability. Simulation is an important and valuable tool not only to develop and validate such systems but also to inform and demonstrate to the public the functioning of a hypothetical AV.

The majority of the research done on decision-making for AVs uses real data to represent real road users, which is ideal, but exactly as it was captured. It is impossible to be more realistic than that, but such rigid use does not expose the tested algorithms to the entire range of behaviors from other road users that the AV might face during its deployment, given that some behaviors might be rare but altogether essential to be considered. The idea presented in this article is then to extract the latent behavior of different road users in some scenarios, allowing in a latter time to be generalize over and to generate synthetic simulation actors that develop trajectories inspired by these latent behaviors and interact with each other in a manner that is compatible with reality.

This research has been funded by the plan "France relance", grant agreement number ANR-21-PRRD-0005-01; Nelson de Moura and F. Nashashibi are with INRIA, 75012 Paris, France. E-mail: {nelson.demoura; fawzi.nashashibi}@inria.fr.

Dataset [tr i ]

Man. 1 Man. 2

• • • Man. n Prof. 1 • • • Prof. m 1 Prof. 1 • • • Prof. m n • • • Cluster on ( s) j
Cluster on ( v 1,l , a 1,l ) j Cluster on ( v n,l , a n,l ) j

Fig. 1: Representation of the clustering process

This "extraction" from real data involves the clustering of different trajectories that should be captured from real situations. How to cluster time series of different sizes have been studied for many years, notably starting in the speech recognition domain [START_REF] Ruiz | Is the dtw "distance" really a metric? an algorithm reducing the number of dtw comparisons in isolated word recognition[END_REF], [START_REF] Vidal | On the verification of triangle inequality by dynamic time-warping dissimilarity measures[END_REF]. For example, some of the seminal works in the subject are [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]- [START_REF] Sakoe | Dynamic-programming approach to continuous speech recognition[END_REF], that laid the foundations of the dynamic time warp (DTW) distance measure and its simplification constraints, which are today one of the most efficient method to cluster time series of different sizes. One of the possible alternatives, to fit the available trajectories and then extract an equal size time series has been proven to not produce a difference in accuracy [START_REF] Ratanamahatana | Everything you know about dynamic time warping is wrong[END_REF], while two other possible approaches are to classify based on extracted features from the raw data (application specific) or to build some model from it [START_REF] Liao | Clustering of time series data-a survey[END_REF] (and risk losing the explainability property).

An example of a similar approach proposed here to treat trajectories raw data is [START_REF] Choong | Modeling of vehicle trajectory clustering based on lcss for traffic pattern extraction[END_REF], where two different clustering methods, the k-means algorithm and the fuzzy c-means (FCM) are used with the longest common sub-sequence (LCSS) measure combined with a Gaussian kernel to define the similarity matrix between trajectories. Using the raw data made available by [START_REF] Morris | Trajectory learning for activity understanding: Unsupervised, multilevel, and long-term adaptive approach[END_REF] both clustering methods produced similar results, but no method to determine the correct number of clusters were proposed since the rand index (RI) is used to determine the best result (which entails knowledge of some ground truth). Another example of the same type of approach is [START_REF] Ribeiro | Temporal gap statistic: A new internal index to validate time series clustering[END_REF], which uses the DTW as distance measure with a c-medoids algorithm to cluster time series. Since it uses the gap statistic to obtain the optimal number of clusters, it unfolds each time series into the frequency domain so as to correctly calculate the null distribution for the gap calculation (which compares a candidate distribution to one that does not have a separable structure). However, the approach was tested only with synthetic data.

A generative model can also be built based on the available raw data, as [START_REF] Choi | Trajgail: Generating urban vehicle trajectories using generative adversarial imitation learning[END_REF] did; it solves the problem of scarcity directly with a generative model trained with raw data. All the considered trajectories are fed into a partially observable Markov decision process that models an imitation learning task, which is trained using a generative adversarial framework. The entire framework is tested using two datasets: one synthetic, based on a microscopic road simulation and another created by the tachograph data from an entire fleet of taxis inside a district in Seoul. It can be clearly seen that the lack of some types of trajectories affects the accuracy of the generator under real condition, while if known a priori which are these rare trajectories they could be duplicated or have their importance increased.

The contribution of this paper can be surmised in two points: fast clustering for maneuver detection and behavior determination from maneuvers in an explainable way and independently from map information.

II. CLUSTERING THE TRAJECTORIES

Each trajectory can have different sizes, since it consists of a time series for the position, velocity and acceleration in a scenario like figure 2, for an agent i that has a trajectory of size j. The first piece of information necessary to be extracted from data is the expanded maneuver 1 being executed to then compare the long behaviors accordingly.

tr i = ( s, v, a) j , j ∈ N (1)
Let's assume that the working dataset contains a certain number of trajectories of vehicles in an intersection. To obtain the labeled data so as to interpret the behavior of each vehicle in the intersection, two different clustering operations are proposed: the first one to separate the different maneuvers that might be executed in an intersection, and the other one, to be executed in each defined class from the first one, to finally classify the range of behaviors displayed during an specific maneuver.

The first separation can be done using exclusively the position information in each trajectory. Given that each detected cluster now has the same lateral evolution, the second clustering operation can be done using the longitudinal velocity and acceleration information. This sequence of operation is illustrated by figure 1, where 'Man.' refers to maneuver, 'Prof.' to behavior profile and v ,l , a ,l refers to the longitudinal velocity and acceleration.

The dataset chosen to test the extraction of different driving profiles from real data was the InD dataset [START_REF] Bock | The ind dataset: A drone dataset of naturalistic road user trajectories at german intersections[END_REF], which is a bird-view urban dataset of intersection trajectories. All the trajectories are obtained from a video recording of 1 It represents the maneuvers executed by a single trajectory which may be more than one typical atomic maneuver.

the intersection (details about the trajectory calculation are in [START_REF] Bock | The ind dataset: A drone dataset of naturalistic road user trajectories at german intersections[END_REF]). Four different intersections were observed by a drone multiple times, defining the data-batches that hold the set of trajectories to be analyzed. Equation (2) describes more appropriately the data that compose each trajectory.

tr i = ( s x , s y , v x , v y , a x , a y ) j , j ∈ N (2)
Fig. 2: Example of an intersection from InD dataset (Obtained from [START_REF] Bock | The ind dataset: A drone dataset of naturalistic road user trajectories at german intersections[END_REF])

With the process and the information that needs to be extracted defined, the next step is to find a method to cluster the data correctly. K-Means is a fairly popular and robust method, with implementations available in multiple programming languages, so it was the chosen method. However, there is an important characteristic that needs to be accounted: the trajectories are time series with different sizes, which means that the Euclidean distance, the usual metric to calculate the proximity between data points in a cluster, cannot be used in a straightforward way.

To be able to compare two time series with different sizes one has to find a relation between the points of each series, which is done using an algorithm called dynamic time warping (DTW). With it, a similarity score (analogue to the Euclidean distance) can be calculated, and thus, the K-Means can be executed data points that have different sizes.

A. Dynamic time warp (DTW)

DTW was first introduced in the speech processing domain as a way to compare two time series that have different phases. Even though the trajectories studied here were sampled at the same frequency, they have different sizes and might correspond to the same maneuver in an intersection. Consider two discrete time series, represented by ( 3) and ( 4), with different sizes n and m, where K = {k 0 , k 1 , . . . , k n , . . . , k m , . . .} represents the sampled periods:

R[K] = r[k 0 ], r[k 1 ], . . . , r[k n ] (3) S[K] = s[k 0 ], s[k 1 ], . . . , s[k m ] (4)
The goal of the DTW is to calculate the optimal sequence of pairs of point indexes, one from each time series. This is done by minimizing the euclidean distance between the points pointed by the index pair, from (r

[k 0 ], s[k 0 ]) to (r[k n ], s[k m ]
), using a certain set of increments to walk from the former to the latter. In the standard implementation (equation 6) three steps are tested: advance one for the index 1, advance one for index 2 or advance one in both. Equation ( 5) defines the DTW from R and S as the calculated sum of distances, which are determined by the recursion in equation ( 6), for 0

≤ i ≤ k n and 0 ≤ j ≤ k m . DT W (R, S) = γ(k n , k m ) (5)
γ(i, j) = d(r[k i ], s[k j ])+ min [γ(i -1, j), γ(i, j -1), γ(i -1, j -1)] (6)
There are multiple DTW variants, some changing the walk used in the recursion (6) (constraint DTW [START_REF] Müller | Information retrieval for music and motion[END_REF]) or adopting restriction on the elements to be considered by equation ( 6) (Sakoe-Chiba band [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF]; Itakura parallelogram [START_REF] Itakura | Minimum prediction residual principle applied to speech recognition[END_REF]). In [START_REF] Morel | Timeseries averaging using constrained dynamic time warping with tolerance[END_REF], the DTW implementation is constrained to avoid a degenerate comparison between two series (when the path moves in using the vector (i -1, j) or (i, j -1) multiple times) that have very different sizes while [START_REF] Cuturi | Soft-dtw: A differentiable loss function for time-series[END_REF] implements a differentiable measure to be used as kernel for machine learning methods. A continuous DTW version was implemented by [START_REF] Brankovic | k, l)-medians clustering of trajectories using continuous dynamic time warping[END_REF]. During the clustering operations discussed here the DTW version used will be the one displayed by equation ( 5) since continuity and differentiability is not important for the task.

Usually, when the Euclidean metric is used, the centroid of a set of series can be calculated simply by summing all the elements and dividing by the number of series in the set. To do so with series of different lengths the Dynamic Barycenter Averaging (DBA) can be used, producing an average inspired series that minimizes the sum of squared DTW distances to each element of the set [START_REF] Petitjean | A global averaging method for dynamic time warping, with applications to clustering[END_REF]. In [START_REF] Forestier | Generating synthetic time series to augment sparse datasets[END_REF] the same procedure was expanded to calculate a weighted average of a set of time series.

B. K-Means clustering

The K-Means clustering is an unsupervised learning method that tries to separate a set of data into k pre-defined clusters given a measure of similarity. It is fairly well known today for its versatility and simplicity. In the instances where the k-means clustering is used in this work, the Euclidean metric, popularly used to determine the dissimilarity between elements inside a cluster will be replaced by the DTW distance measure. There are some possible problems with this substitution given that the DTW is not a metric (it does not assure the triangular inequality property [START_REF] Ribeiro | Temporal gap statistic: A new internal index to validate time series clustering[END_REF]), but the conclusion of [START_REF] Vidal | On the verification of triangle inequality by dynamic time-warping dissimilarity measures[END_REF] guarantees that, if equation ( 6) is solved according to the Bellman's optimal principle, the triangle inequality is loosely satisfied, thus avoiding the necessity to change from the K-Means to C-Medoids [START_REF] Ribeiro | Temporal gap statistic: A new internal index to validate time series clustering[END_REF]. The algorithm initialization is done using the k-means++ algorithm [START_REF] Arthur | K-means++ the advantages of careful seeding[END_REF] except when said otherwise.

III. FINDING THE OPTIMAL NUMBER OF CLUSTERS

Throughout the years many different methods have been used to measure the validity and quality of a cluster classification [START_REF] Halkidi | On clustering validation techniques[END_REF]. Some of them are: the Davies-Bouldin (DB) index [START_REF] Davies | A cluster separation measure[END_REF], which calculates a score that measures the biggest similarity between two clusters (from the idea that it is desirable that each cluster be as different as possible from the others); the rand index, which measures the changes in classification for pairs of elements according to the number of clusters used [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF]; and the gap statistic, that compares the within-cluster dispersion from a certain clustering operation with what would be expected from a null reference distribution [START_REF] Tibshirani | Estimating the number of clusters in a data set via the gap statistic[END_REF].

To determine the optimal number of behaviors observed in the clustering of the longitudinal information, the Davies-Boudin index was chosen mostly because it takes into account the distances between elements inside a cluster and the inter-cluster distances as well, without the need of any further information. The gap statistic needs a null distribution to compare to and the rand index needs the ground truth for its calculation (which for the maneuver detection is possible but not the case for the longitudinal detection).

A. Davies-Boudin score

The DB index is defined based on the dispersion of a cluster C i , indicated as s i , and the dissimilarity between two different clusters, namely d ij [START_REF] Halkidi | On clustering validation techniques[END_REF]. The calculation is displayed in equation [START_REF] Ratanamahatana | Everything you know about dynamic time warping is wrong[END_REF], where n c refers to the number of clusters being used.

DB nc = 1 n c nc i=0 max j=1,...,nc,i =j R ij (7)
R ij = (s i + s j ) d ij (8)
In this case, the dispersion s i within each cluster is calculated by the sum of the DTW distances between the DBA centroid and each element, divided by the number of pairs detected. The distance between clusters is obtained by the DTW distance from the respective DBA centroids.

IV. CLUSTERING PROCEDURE

The procedure is based on three steps: first, executing the clustering using the trajectory position coordinates, for each data-batch in each scenario present in the dataset; second, each obtained cluster previously, which represents an expanded maneuver, are unified into a single cluster for each expanded maneuver; and third, the clustering using the longitudinal velocity and acceleration is done on the respective clusters from step two.

A. Position clustering

The K-means clustering can be executed on the trajectories directly, which is costly in computational terms. One way to speed up the calculation is to execute the clustering operation using a row from the dissimilarity matrix, defined by 9, where n indicates the number of trajectories being considered and the d DT W i,j represents the DTW distance between the elements indexed as i ad j.

D DT W =      d DT W 0,0 = 0 • • • d DT W 0,n d DT W 1,0 • • • d DT W 1,n . . . . . . . . . d DT W n,0 • • • d DT W n,n = 0      (9)
Executing the K-Means onto one dimension instead with having to recalculate distances to the current centroid in an iteration vastly decreases the computational time in comparison with the alternative. Algorithm 1 shows the entire procedure. Considering that each line (row or column) from D DT W represent the comparison of one trajectory with all the others, line 2 establishes the index array of all trajectories. For each element still being considered, the respective line of the dissimilarity matrix is clustered (line 6) to obtain the labels (which allocates each element of the row to a cluster) and the centers of each cluster (which will be the average difference between elements on the cluster). Then, using the classification with the smallest center possible (line 8) all the elements of the same cluster are grouped in the final structure (line 16) and removed from consideration on the next round (line 17). The same procedure could be done sequentially according to the order of the matrix D DT W , which would be faster. However, iterating over all elements results in a more robust result, avoiding any initialization problems. Finally, the last cluster receives the remaining data still in c idx.

The operation in algorithm 1 is repeated for different numbers of cores, and the optimal choice is determined by the minimal DB index calculated from all those clustering operations. One of the possible problems of this method is the calculation of the dissimilarity matrix, which is O(N 2 ). This can be mitigated by splitting a bigger dataset in smaller ones and then using the next method to unify all the results.

B. Unifying the maneuvers from each data-batch

This process actually allows all data-batches from a single scenario to be bundle together while it also mitigates the O(N 2 ) problem of calculating the dissimilarity matrix. In consequence, one can cluster using small sets of data during the position clustering and then bring them together in clusters without repetition. Having all the data batches clustered, their centroids can be compared with each other using the DTW distance. Defining a simple difference threshold is enough in the following case to add data to its analogue cluster or to establish a new one, if none are similar.

C. Longitudinal clustering

Now having all the trajectories classified into maneuvers, the longitudinal set of data from each maneuver can be recovered and clustered into different behavioral profiles. This is done by recovering the longitudinal velocity and acceleration for each element on the cluster: for a determined number of cores, execute the clustering and determine the optimal cluster number by minimizing the DB index calculated.

Algorithm 2: Longitudinal maneuver clustering

Input : long data, nx2 matrix Output: lab opt , µ opt , optimal labels and centers The method of clustering the dissimilarity matrix was tested with the longitudinal data as well, but it did not produce adequate results because the differences between each element can be too small to be significant in the final distance. The longitudinal velocity is contained around a positive finite range in this case between 20m/s and 0 and acceleration fluctuates around zero, differently to the position that usually do not have a common baseline. Hence, the DTW distances calculated for the position of different trajectories are clearly different, but not so much for the longitudinal data of the same expanded maneuver.

V. RESULTS AND DISCUSSION

A. Methodology

All data-batches and scenarios from the InD dataset [START_REF] Bock | The ind dataset: A drone dataset of naturalistic road user trajectories at german intersections[END_REF] (7 for scenario 1, 10 for scenario 2, 12 for scenario 3 and 3 for scenario 4) were used to obtain the results displayed in the figures 5, 6 and 7 and table II. The only alteration done was to remove the following trajectories: first filter all those related to pedestrians, cyclists or trucks-buses; second, to eliminate incomplete traces, notably if they had already started before the beginning of the data recording or if they did not end before its end. Also, there was some trajectories inside the dataset that suffered a tracking loss during their calculation and were incomplete. All those trajectories were not used in the clustering presented in V-B.

Table I shows the number of clusters explored during the position and longitudinal clustering to determine the best number of clusters. These ranges were determined by visual inspection for the position clustering, according to the possible maneuvers in the map and defined empirically for the longitudinal clustering. Since there was no indication as to how many clusters might exist for the longitudinal clustering, a wider search range was used. All the calculations were done in a Dell Inspiron 5570 notebook with a Intel Core i9-12900H containing an NVidia Quadro A2000 and using the functions available from the Python library TSlearn [START_REF] Tavenard | Tslearn, a machine learning toolkit for time series data[END_REF].

B. Results

1) Position clustering:

Applying the algorithm 1 for each data-batch available the dataset results into clusters similar to figures 3 and 4, which are clusters for scenario 0 (not using the same color code as in figure 5; the cluster numbers are not related to the maneuvers defined in the next subsection). All the modifications discussed in the methodology section allow the algorithm 1 to be robust enough to cluster all the trajectories in the dataset without mistakes. Table II shows the difference in execution time between the default clustering method and the dissimilarity method usage proposed in algorithm 1. The timings were calculated as the average time for the clustering of all cores displayed in table I and all data-batches for each scenario, in one pass only. The Given the performance difference by calculation time, the dissimilarity matrix method is superior. However, the error rate was negative because the direct K-Means approach missclassified some trajectories while the dissimilarity method did not. This happens due to the initialization of the direct method, which might start with the wrong trajectories in a cluster and throughout the clustering might not be able to shift to the correct ones (being stuck in a local minima). As it can be seen there is a real gain using the dissimilarity method, even if it is necessary to calculate the dissimilarity matrix before the clustering and the clusters' centers afterwards (which is included in the calculated times). As said before, this method works as well as the direct k-means method, if not better, because all the maneuvers are distinct enough for the DTW distance to have a clear difference between clusters. This is not the case for the longitudinal velocity and acceleration, for example, where the division between maneuvers was already done, thus the differences are rather subtle and difficult to cluster.

2) Unifying data-batches: Following the details given in subsection IV-B, figures 5, 6, 7 and 8 represent all the trajectories detected for the first three intersections present in the InD dataset. The union of clusters determined earlier represents the maneuvers discovered in each scenario.

The only drawback of the unifying method presented earlier is that a threshold needs to be established based on the DTW distance score between two cluster centers. In the implementation a single value could be used for all scenario but there is no guarantee that one can be found every time. The ease of finding the correct threshold value depends on how different are the clusters being considered, which is the same characteristic that allows the dissimilarity matrix 3) Longitudinal clustering: Given that some maneuvers have a small number of samples, a minimal threshold of 10 trajectories was adopted to execute the clustering (in red on table III). Also, a restriction of the number of clusters tested according to the number of trajectories was used: min(20, n traj /2).

As initialization, the algorithm 1 was used to select the cluster seeds instead of the usual k-means++ in the follow-Fig. 8: Maneuvers for scenario 3 from InD dataset ing way: from the clusters obtained with the dissimilarity matrix calculated with the longitudinal data, one sample was randomly selected from each cluster to serve as initial seed. Table III gives a complete overview concerning the number of samples per trajectory in each of the scenarios available. To explain the results obtained from the clustering of the longitudinal data, figure 9 displays the average velocities and 10 shows the average acceleration for the maneuver 1 of scenario 0 (which are the data from the maneuvers in figure 3). In this case the optimal number of clusters, hence behavior profiles, detected was 12. It can be seen that there is a stratification of velocity between cluster centers, with two of them reaching the velocity equal to zero in the middle of the maneuver (clusters 1 and 2), represented by figures 11a and 11c respectively and other two others that did not interact with anyone (clusters 3 and 4), represented by figures 11b and 11d. Comparing the four plots in figure 11, it can be said that some clusters represent the vehicles that interacted with other road users and some represent those that did not. Moreover, the difference between 11a and 11c and between 11b and 11d can be explained by the starting velocity (from 20 to 15 m/s for the former and 15 to 10 m/s for the latter), since the turning velocity (at the middle of the trajectory) is almost equivalent (around 10m/s).

The other clusters, not shown here, represent velocity profiles that indicate different levels on interaction with other road users, some with higher starting velocities and/or with higher decelerations, to wait other road users or just to execute the turn more lowly. The results from all the scenarios point to the conclusion that two of the most determinant factors to explain the behavior profiles obtained are the aggressiveness of the driver (accounts for deceleration and the starting velocity) and if and how it interacted with other road users during the trajectory. Therefore, classifying each behavior profile with these two parameters can represent the entire range of behavior profiles for an intersection.

However, there is no right answer about the number of clusters, differently from the position clustering case. Figure 12 shows the DB score curve, and if one uses the minimal approach suggested in algorithm 2 the optimal number of clusters should be 18, not the 12 shown in figures 9 and 10. This is because for higher number of clusters the DB score reach the realm of diminished returns, where only a few trajectories might get relegated to one cluster, decreasing the dispersion and thus the score itself. Fig. 12: DB scores for the test number of clusters Using the k-means++ algorithm to seed the initial clusters (not the usual dissimilarity matrix method) and 5 repeated calculations per cluster (to avoid any initialization local minima) results in even lower DB scores, with a cost due to the calculation time (10 times higher than with the dissimilarity method as seed initialization). But, in this case, the optimal number of clusters is two, simply separating the trajectories that do interact and those that do not. The use of k-means++ selects two dissimilar seeds for initialization which, connected to the fact that the average calculated by the DBA is equal in extension to the biggest series, reduces the DB score in comparison with higher number of clusters. In the dispersion calculation for equation [START_REF] Ratanamahatana | Everything you know about dynamic time warping is wrong[END_REF] the value is normalized using the number of pairing between each element and the average (the number of times equation ( 6) is executed), therefore artificially reducing the score.

Another problem with the DTW calculation for longitudinal data happens in the comparison of large periods where the velocity is equal to zero. In this case a big part of the trajectory might produce a distance equal to zero, thus keeping together trajectories that should form different clusters. It is what happens in figure 11a and11c where curves that spent different amounts of time in zero should have been in different clusters.

Ideally, for the proposed use as input to train a simulation agent, it should exist a separation on the range of velocities displayed by the trajectories representing a maneuver as well. Thus, considering all these elements, the results displayed in table IV comes from the manual selection of the DB scores, taking into account still the local minima on the DB curve, but trying to obtain profiles that separate on the longitudinal velocity as well. The results in red represent an insufficient number of trajectories to apply the longitudinal clustering.

VI. CONCLUSION AND NEXT STEPS

It is essential for realistic simulations to have independent agents that behave and interact with each other in a natural way. The main goal of this article is to extract behavior profiles from real trajectories to, first, understand which kind of behaviors might arise from different maneuvers, and second, to be able to, in a later iteration, generalize over

Algorithm 1 :

 1 Clustering the DTW dissimilarity matrix Input : D DT W ; nk, number of clusters Output: clust, set of clusters 1 counter = 0; 2 c arr = [from 0 to length(D DT W )]; 3 for counter < n cores -1 do 4 best idx = -1, min inert = 0; 5 for each c idx in c array do 6 labels, centers = kmeans(D(c idx, :), nk); 7 min idx = argmin(µ idx ); 8 if centers[min idx] ≤ min inert then 9 best idx = min idx; 10 min labels = labels; 11 min inert = centers[min idx]; in min labels do 15 if elem == best idx & idx ∈ cand idx then 16 clust[counter] ← idx; 17 cand idx.pop(elem);

Fig. 3 :

 3 Fig. 3: Cluster 0 from data batch 2 of scenario 0

Fig. 4 :

 4 Fig. 4: Cluster 2 from data batch 2 of scenario 0

Fig. 5 :Fig. 6 :

 56 Fig. 5: Maneuvers for scenario 0 from InD dataset

Fig. 7 :

 7 Fig. 7: Maneuvers for scenario 2 from InD dataset

Fig. 9 :Fig. 10 : 4 Fig. 11 :

 910411 Fig. 9: Average velocities for maneuver 1 of scenario 0

  DB(lab nk , µ nk , long data); 4 end 5 best idx = argmin(db result); 6 lab opt , µ opt ← lab best idx , µ best idx

1 for nk < n cores do 2 lab nk , µ nk = kmeans(long data, nk); 3 db result ←

TABLE I :

 I Number of clusters explored

	Clust. type	Sce. 0	Sce. 1	Sce. 2	Sce. 3
	Position	7 ± 2	10 ± 3	10 ± 3	8 ± 3
	Longitudinal		11 ± 9

TABLE II :

 II Average position clustering time per data-batch

	Scenario	Dissi. method	Direct Kmeans	Error rate
	0	31.48s ± 13.69s	831.16s ± 572.19s	0%
	1	26.85s ± 14.45s	267.34s ± 167.08s	-1.7%
	2	32.72s ± 09.88s	257.28s ± 098.87s	-0.53%
	3	57.08s ± 19.54s	682.91s ± 290.26s	-0.37%

TABLE III :

 III Number of trajectories per maneuver Man. Sce. 0 Sce. 1 Sce. 2 Sce. 3 Traj. Sce. 0 Sce. 1 Sce. 2 Sce. 3

	0	199	712	245	405	8	1	21	15	-
	1	146	231	162	37	9	1	13	19	-
	2	21	118	724	452	10	-	12	7	-
	3	609	9	357	85	11	-	20	14	-
	4	803	216	324	47	12	-	-	2	-
	5	21	257	133	44	13	-	-	4	-
	6	2	662	21	-	14	-	-	4	-
	7	2	19	20	-	Total 1805 2290 2051 1070

The extraction of behaviors was done in a sequence of two clustering operations. First, the position coordinates of each trajectory as clustered to determine the existing maneuvers in one data-batch. This clustering operation was accelerated by using DTW dissimilarity matrix itself (algorithm 1) rather than the entire trajectories. Second, the detected maneuvers for all the data-batches in one scenario were fused together and clustered as a maneuver using the longitudinal velocity and acceleration, to determine the behavior profiles that might exist.

The next steps can be divided in three tasks: to test the algorithm with the pedestrian and cyclist data, not used here, and also to explore new datasets; test different dissimilarity measures and optimal cluster selection criteria for the longitudinal case; and finally to train the aforementioned agents in a simulation environment based on the profiles obtained.


Comparing imputation completeness and accuracy (and precision)

Completeness: how much missing data is imputed? (pipe length imputed / unknown) Accuracy: is the imputed data close to the truth? (pipe length correctly imputed / unknown) Precision: how much do results change when repeated many times? 20

SWDE in a few words Walloon Water Company (SWDE)

Major water utility in Wallonia (Belgium) :

• 67 % of connection points, > 1 million user water meters, > 2.5 million users supplied Matching tables using identifiers merge(x,y,all.x=T/F,all.y=T/F,by=…)

Matching tables using coordinates st_nearest_feature(x,y)

Advantages: automate and make everything reproducible ex: interpolate water consumption daily over 6 years for > 1 million water meters -> few min (rolling join). Drawbacks: code is not very visual, code syntax is package-specific Take-home messages:

• Archive regularly (more than yearly) an image of the whole network or a history of changes • Make sure the link between pipes in service and out of service is kept Imputation of "simple" pipe attributes that should already be available:

• Pipe materials, diameters: sometimes missing (few %), not always required

• Pipe installation dates: often missing (>10-20%), almost always required (pipe age)

Imputation of more complex data not necessarily available:

• Average static service pressure for the pipe (complex R algorithm)

• Number of connection points and number of users for the pipe (geomatics)

• Type of soil, position under the road, azimuth…

Comparing imputation completeness and accuracy (and precision)

Completeness: how much missing data is imputed? (pipe length imputed / unknown) Accuracy: is the imputed data close to the truth? (pipe length correctly imputed / unknown) Precision: how much do results change when repeated many times?

••

  190/262 cities in Wallonia supplied • Nearly 40 000 km of pipes • Over 162 million m 3 of water introduced every year into the pipe network • Over 150 M€ invested every year for infrastructure maintenance (2020-2023) applied research project between INRAE (ETTIS research unit) and SWDE INRAE: French public research institute (Agriculture, Food & Water Supply, Environment) ETTIS: Research unit among which engineers and researchers work on the Asset Management of Water Infrastructures GePaME : multi-scale asset management of drinking water networks Aim: help SWDE improve its asset management from the pipe to the whole network scale, from the short-term to the long-term 3 Task 01: dealing with data Dealing with data -More than 50% of project time Why do we need to manipulate the data? Data has been (historically) gathered and structured to answer daily business needs Asset Management requires large records of data specifically formatted (e.g., models, statistical analyses) What are the 3 main problems to deal with? 1. Detecting the underlying DB structure in the various files (GIS, CMMS, CSV) 2. Detecting and correcting data which are not consistent 3. Imputing missing data Tools used and why : R, Excel, QGIS Unlike analysts employed at SWDE, we did not have access to online (up to date) databases Statistical analyses and models are easily made with R code How much data are we talking about? • 500k GIS pipe segments • 2 500 DMAs with 1 to >5 water meters, 1 measurement/15 min since ~2016 • 100 000 repairs on the pipe network since 2011 • 90 000 leak inspections since 2016 • Over 1 million user water meters with yearly readings • Millions of address points for users • Thousands of streets represented as Not all data from SWDE is used • 3 main sources (SAP, Elyx Aqua, Perf'O) • Many separate files • Keys linking the files sometimes complex CMMS: Computerized Maintenance Management System GIS: geographic information system CSV: comma separated values SPW (Service Public de Wallonie) NGI (National Geographic Institute) What does the data used in the project look like? (internally) SAP: enterprise resource planning software GIS: geographic information system CSV: comma separated values SPW (Service Public de Wallonie) NGI (National Geographic Institute) X, Y: geographic coordinates MO: Maintenance Order (SAP concept) ID: (d=DMA, p=pipe, r=repair part, s=street) t: time DIA: pipe diameter MAT: pipe material Task Functions used Finding the identifiers Removing duplicates unique() ; duplicated() ; is.na() Creating new identifiers setkey() ; DT[,id:=…,by=.(name,date)]

• Record and store the history of changes in the DMA structure

	Problem n°2:	5
	Challenge: the
	network changes
	everyday, identifiers
	change…

detecting and correcting data errors Typical errors to correct: text data

Manually input text can be inconsistent with the "constraints" (data type, null values forbidden, list of authorized values, upper/lower cases, local characters…) ->

ideally, avoid manual text! 15 Task Solution Function used Raw data Output data Matched with

	Problem n°3: imputing missing data Data imputation: automatized	6
	• Extract street	Regular	str_detect()	fg 50	FONTE GRISE 50
	names,	expressions		fonte 1960 dn50	FONTE GRISE 50
	material
	names,			Rue du bidule 80b	rue, du bidule, 80b
	diameters…			Avenue_machin face 52 a	avenue, machin, 52a
	• Regroup
	similar values
	Associate similar	String	stringdist()	London, Baker st.	London, Baker
	names	distance	amatch()	London, Bqker str	street
		Fuzzy	toupper()	FLENU CELL 1	FLENU CEL 01
		matching	stri_trans_gener	Flénu CEL 01
			al(,"Latin-ASCII")

Exemple de pied de page ( A modifier sous l'onglet "Insertion" / "En-tête/pied" ) Exemple de pied de page ( A modifier sous l'onglet "Insertion" / "En-tête/pied" )

Exemple de pied de page ( A modifier sous l'onglet "Insertion" / "En-tête/pied" )

We thank all the members of the GePaME project from INRAE-ETTIS and from SWDE!

Accuracy: is the imputed data close to the truth? (pipe length correctly imputed / unknown) Precision: how much do results change when repeated many times? Comparing imputation completeness and accuracy (and precision)

Random omission Omission by street

No data is sometimes better than bad data!

Conclusions

These are the take-home messages:

01

Requires large amounts of formatted, interoperable data.

AS S E T M AN AG E M E N T 02

Best done with ETL tools with online databases but powerful "offline" alternatives exist (R and its packages).


Janette Webb

Margaret Tingey

Sociology, Faye Wade

Edward Elgar

Thomas Reverdy
email: thomas.reverdy@grenoble-inp.fr

Frederic Marty
email: frederic.marty@gredeg.cnrs.fr

Frédéric Marty

Ronan Bolton
email: ronan.bolton@ed.ac.uk

Chapter 7: The redesign of electricity markets under EU influence: The capacity mechanism in France and Britain

Keywords: Electricity Market, Capacity Mechanism, State Aid, Market Failures, Security of Supply, Sociology of Market, Energy Only Market

Ronan Bolton is an interdisciplinary energy researcher with a background in mechanical engineering and environmental social science. His work examines the interconnected policy, market and regulatory challenges of transforming carbon based energy systems.

<a> Introduction

Since the late 1990s, European Directives covering the energy markets have gradually been transposed into legislation by Member States, contributing to the consolidation of electricity sector organisation around a liberalised market model across EU nations. It was thought that this new organisational model was flexible enough to take into account the specifities of each country's electricity system and the inherent 'market failures' associated with electricity supply, notably the natural monopoly of the networks and the need for instantaneous balancing between supply and demand.

However, the introduction of variable renewables (wind and solar) into power systems has prompted some governments, industry groups, and economic experts to highlight an additional failure of the market: to produce adequate incentives for investments to secure capacities for peak load. In order to address this 'failure', a number of EU countries have introduced a capacity mechanisma means of valuing capacity (MW)alongside the conventional energy-only wholesale markets where buyers and sellers transact power (MWh). Capacity mechanisms are highly controversial and their rationales, merits and designs are continually being debated by economic and regulatory experts [START_REF] Roques | Market design for generation adequacy: Healing causes rather than symptoms[END_REF][START_REF] Fabra | A primer on capacity mechanisms[END_REF].

The chapter does not engage directly in these substantive technical debates about market designs and capacity mechanisms. Instead we draw on perspectives from science and technology studies (STS), in particular contributions to the social study of electricity markets [START_REF] Silvast | Energy, economics, and performativity: Reviewing theoretical advances in social studies of markets and energy[END_REF][START_REF] Breslau | What Do Market Designers Do When They Design Markets? Social Knowledge in the Making[END_REF][START_REF] Karnøe | Material disruptions in electricity systems: can wind power fit in the existing electricity system? Débordements[END_REF], to cast light on the articulation of technical concerns, economic tools, and political issues in the work of economists, regulators and other technical experts who shape these markets. Our aim is to use the debate about capacity mechanisms to analyse the evolving relationship between politics and economics in the construction of liberalised electricity markets.

Our empirical focus is on the cases of France and Britain i , where market design and regulatory processes have followed very different paths. The question of whether to introduce a capacity mechanism and its optimal design appeared in both cases just after the 2008 financial crisis, with the issue being resolved much more quickly in the UK than in France. We discuss how the processes and outcomes in each case can be partially explained by the history of liberalisation in each country, different technical and economic framings of the security of supply issue, national practices of energy market regulation, and relations between these countries and the European institutions ii .

With the Third Energy Package in 2009, the European Commission initiated a clarification of its electricity market legislation, putting forward the energy-only market model (without a capacity mechanism) as the norm for the European electricity sector, from which any deviation needed to be justified. Within this frame, electricity market design involves a procedure of validation whereby the technical expertise and political objectives of both the national governments and the European Commission enter into a dialogue. Market interventions wich signal a deviation from the preffered model need to be justified in relation to this wider framecomposed of European electricity liberalisation Directives, EU competition policy and State Aid guidelinesbut there is a necessary degree of flexibility and ambiguity in place to accommodate diversity [START_REF] Bolton | Ambiguous interventions: Capacity remuneration mechanisms and the politics of energy transition in Britain and Germany[END_REF].

Following [START_REF] Nik-Khah | On going the market one better: economic market design and the contradictions of building markets for public purposes[END_REF], we observe that by delimiting the economic arguments considered to be legitimate, this evolving institutional framework exerts a strong influence over the market shaping process. This alignment involves integrating, ex-ante, political concerns about common European objectives into the technical specificities of each market intervention, as shown in the French case, and one of retrospectively justifying deviations from the market norm, in the form of state-aid evaluation, as in the UK case.

The chapter begins with a comparison of the background to electricity market liberalisation in France and the UK, and then charts the introduction and design of their capacity mechanisms.

Following this, we examine the influence of the EU institutions over the design of capacity mechanisms in each case, and in the final part of the chapter we reflect on the nature of the dynamic between the EU and national level in the market shaping process.

<a> Trajectories of electricity liberalisation

In a liberalised energy sector, electricity generation capacity is in principle the result of suppliers' autonomous investment decisions. Given the specific characteristics of electricity, in particular its non-storable nature, the ability of decentralised decisions to guarantee sufficient production capacity has been an important concern in all cases of electricity liberalisation, initially in the UK, and more recently in France, reflecting the technical and institutional inertia of the French sector.

The difference in maturity and experience of liberalisation between France and the UK has influenced their approaches to market redesign and led to different evaluation procedures by the European authorities.

<b> Britain

Britain was a pioneer in introducing competition to its electricity market in the early 1990s.

Following the Electricity Act of 1989, the monopoly electricity generator and transmission company in England and Wales, the Central Electricity Generating Board (CEGB), was split into two competing private electricity generating companies -National Power and PowerGenand a separate transmission company, National Grid, which was initially owned by the twelve Regional Electricity Companies (RECs)also privatisedand later sold as a stand-alone entity.

What became known as the 'British Model' of electricity liberalisation had three distinctive features: Firstly, retail markets were opened up to competition and the distribution companies no longer held regional supply monopolies. This saw the progressive phasing out of regulated tariffs over the course of the 1990s and eventually, by 1998/1999, all electricity customers had the option of switching away from their regional supplier. Secondly, an independent electricity regulator (now called OFGEM) was established and its Director, Prof Stephen Littlechild, was given significant powers under the Act to interpret and enforce the licencing terms in the legislation.

A third significant feature of the model was the Electricity Pool, the wholesale market where National Power and PowerGen, along with new entrant generators, would compete. Generators above a certain threshold were subject to the Pooling and Settlement Agreement, requiring them to submit price bids into the market if they wanted their plant to be dispatched, i.e. called upon to generate and to sell their output.

National Grid was responsible for collecting the price bids for each half hourly trading period; and based on this information, it would calculate the economic dispatch and schedule plant. The overall aim was to maximise the output of the generating units with lowest marginal costs whilst meeting demand, but due consideration was given to the physical constraints of the transmission grid and other technical parameters. These were factored in as part of National Grid's overall system optimisation, not dissimilar to the procedure used by its predessor, the nationalised CEGB.

Generators selling into 'the Pool', along with receiving the system marginal price (SMP) if dispatched, also received a capacity payment to ensure that there was adequate generation on the system to meet demand and to incentivise investment in new plant. The capacity payment was based on National Grid's rolling half-hourly calculation of the Loss of Load Probability (LOLP) and an administratively determined Value of Lost Load (VOLL).

During its years in operation from 1990 to 2001, the Pool was the subject of much debate and criticism, in particular a claim that the legacy incumbents which continued to dominate the market, National Power and PowerGen, could manipulate the pool price, for example by holding back generation at certain peak demand periods, thus increasing the LOLP and their capacity payments.

The Pool was replaced in 2001 by an alternative trading platform, the New Electricity Trading Arrangements (NETA), and this was later expanded to Scotland in 2005 iii , creating the British Electricity Trading and Transmission Arrangements (BETTA).

The philosophy behind NETA/BETTA is quite different, more closely resembling gas markets than traditional power pools. Unlike the Electricity Pool, which was a 'gross' market, requiring all trades for physical power to be routed through it, BETTA is a decentralised market where buyers and sellers of power are free to enter into bilateral contracts, or transact via an organised power exchange. They simply need to notify National Grid of their positions one hour prior to 'gate closure'; based on the costs of balancing the system close to real time, system prices are then calculated and used as a basis to charge licensed generators and suppliers (the balancing responsible parties) for their role in creating deviations between trading positions and actual physical exchanges. So alongside its decentralised structure, BETTA is characterised as a 'net' pool; where system pricing is based on the final positions of the traders rather than the overall, or gross, economic dispatch.

In the transition away from the Pool, the capacity payment was dropped: BETTA was originally designed an energy-only market. This was partly due to an underlying commitment to a particular economic logic; that market-based pricing would send clear signals to investors that new capacity is needed and that this would lead to a more efficient outcome than a centralised approach. There was also a practical element as, throughout the 1990s, there had been significant levels of investment in new gas-fired power plant capacity, resulting in the UK having a comfortable capacity margin (approximately 17% in 2010).

<b> France

Unlike the UK, the liberalisation of the French electricity sector has never been a political project supported at the national level. The French senior administration and political class have always considered that EDF's monopoly on electricity production was not contradictory to the objective of efficiency. The existence of scale effects, thanks to the standardisation of the nuclear production system and its control by a single company, was hardly compatible with a horizontal de-integration of EDF iv . Only French industrial customers were in favour of liberalisation. The French government's acceptance of the European directives has been mainly the result of a desire not to obstruct a wider European integration project, and to contribute to the political cohesion of the European Union.

The reluctant adherence to liberalisation largely explains the lack of sectoral structural reform. The French government has accepted only a limited number of transfers of EDF's generation assets to its competitors, seeking in this way to respond to European injunctions in favor of reciprocity, since EDF was acquiring generation assets in other European countries. Then, in 2003, EDF sold its shares in Compagnie Nationale du Rhône to the Suez group, which eventually merged with Gaz de France to form ENGIE. The liberalisation led to the creation of a decentralised wholesale market, organised around an auction market, EPEX Spot, promoting market price as a reference for the value of electricity and the decision to invest. The interconnections with other European countries developed and led to similar prices.

At the end of the first ten years of liberalisation, due to the particularly low marginal cost of nucleargenerated electricity, France's regulated tariff was maintained. However, competition in the supply business was developed in 2010 thanks to a law (loi NOME: Nouvelle Organisation du Marché de l'Electricité) that has obliged EDF to resell nuclear-generated electricity to EDF's competing suppliers, which, with the exception of ENGIE, have little generation capacity [START_REF] Reverdy | Making an exception: market design and the politics of reregulation in the French electricity sector[END_REF]. The European wholesale market price has now partly replaced a valuation of electricity previously based on its average generation cost.

Despite such specificities compared to the ideal-type of perfect competition, France has implemented EU Directives concerning the European electricity market, although somewhat reluctantly. The French electricity market is highly interconnected with the markets of other continental European countries and EDF is one of the major operators across this market. However, such integration has not become fully effective, due to political choices to maintain a regulated tariff for residential customers, and the tariff for reselling nuclear-generated electricity to competing suppliers. This situation, which constitutes a significant exemption from the market model promoted by the European institutions, is reflected in the European institutions' suspicion of successive French Governments' adherence to the European liberalisation project, and their willingness to encourage the development of competition at the expense of incumbent interests [START_REF] Reverdy | Making an exception: market design and the politics of reregulation in the French electricity sector[END_REF]. This suspicion has led the French legislator to apply a 'precautionary principle' to any new regulatory change to avoid the risk of its compliance with EU rules being challenged by the European Commission.

<a> Design and introduction of the capacity mechanisms

The design of the capacity mechanism within each country is indicative of how the issue of security of supply has been debated in the public arena, and the type of economic argument used to justify the mechanism.

<b> Britain's capacity market

Since privatisation the British energy system as a whole became increasingly reliant on natural gas, and by 2010 gas accounted for 43 per cent of the country's primary energy consumption, up from 25 per cent in 1990 [START_REF] Fevre | The Role of Gas in UK Energy Policy[END_REF]. Perceptions of the threats to energy security resulting from this shift to gas in the energy system began to change during the 2000s as North Sea production reached its peak and the UK became a net importer of the fuel. Whereas during the 1990s the issue of energy security was not high up on the political agenda and was predominantly left to the market, in the 2004 Energy Act a statutory obligation was placed on the responsible Secretary of State for to 'publish a report dealing, as regards both the short term and the long term, with the availability of electricity and gas for meeting the reasonable demands of consumers in Great Britain' v .

In 2009, a highly influential report was published by the energy regulator, OFGEM, following a review of the UK's energy security situation (Project Discovery). One of the key risks raised by OFGEM during this time was that the deteriorating economic situation could result in power plant closures, in particular accelerating the shut down of the country's ageing coal plants. Between 2012 and 2013 the total capacity on the system reduced by almost 5 per cent.

Subsequently, OFGEM published an Electricity Capacity Assessment in 2013, an important justification for government intervention to increase the capacity margin at this time. This indicated that on current trends the loss of load expectation (LOLE, or the number of hours per year that electricity demand on the system would not be met), a key indicator of electricity system security, could rise to 9hrs/year in 2015/16, above the government's maximum target of 3hrs/year. At the outset, DECC signaled a preference for a limited strategic reserve, with a number of plants held back from the market and dispatched only if the energy-only market could not meet demand.

DECC predicted that such a targeted mechanism would offer greater flexibility in the type of resource supported and, given the uncertainty surrounding future market developments, it would provide an additional option value. This was based on a market analysis which found that a revenue stream from a capacity market, involving an auction open to all plants operating in the market, would benefit existing old and inefficient plants who would otherwise face closure due to the costs of compliance with European environmental legislation, in particular the Industrial Emissions Directive.

However, following a consultation in late 2010, DECC changed its view and instead opted for a capacity market. The key economic argument for this was that Britain's electricity market had a missing money problem, based on a structural flaw in liberalised electricity markets with regards to long-term system adequacy. The conceptual argument with missing money is that prices in the energy-only market are unlikely to be allowed to rise to the extremely high levels required to motivate private investment in new capacity, due to both political interference in price setting and intervention by the system operator to dispatch its emergency reserves. As a result, there is a fundamental market failure with respect to investment in peaking plant, and the energy-only market will fail to deliver the level of energy security required by society.

Although barely mentioned in the initial 2010 government consultation on options for the capacity intervention, missing money emerged as a key argument in the consultation submissions and the subsequent follow-up analysis conducted by DECC. DECC began to incorporate missing money as a new variable into their cost-benefit calculations. They conducted a sensitivity analysis with a 'stress test' scenario, which included a £5,000/MWh price cap, representing the missing money, and found that under certain assumptions the capacity market would be economically efficient vi .

The argument that such structural reform was necessary gained credibility as updated modelling projections, based on OFGEM's Electricity Capacity Assessment, indicated that the capacity margin could drop below 5% in the near futuren and in a number of the scenarios analysed, the LOLE would be greater than 3 hours/year. This analysis incorporated the effects of plant closures and increasing amounts of low carbon generation, and on the back of it, it was decided to introduce a centralised auction for capcity contracts of varying lengths to provide an additional layer of electricity system security.

<c> Too much energy security?

Following the commencement of capacity auctions in 2014, the most notable outcome of the market so far has been the low clearing prices vii : The price in the main auction viii peaked in 2016, at £22.50 per kW/year. This was well below the cost of new entry (CONE), a key parameter in the auction design which represents the government's view of the likely cost of constructing a new plant to serve peak demand, a combined-cycle gas turbine plant (CCGT) in this case. If the market was undersupplied to a level which threatened security of supply, one would expect the market clearing price to reach these levels and for new power plants to be constructed. As a result, the amount of capacity purchased in the auctions has seen the loss of load expectation (LOLE) security standard set by government (no more than 3hrs/year) being greatly exceeded ix . This has occurred to the extent that some are questioning whether the capacity market is providing too much energy security, such that the electricity customer does not benefit. Key reasons cited by government for this outcome are 'plants without capacity agreements staying open for longer than was expected, with additional procurement through the capacity auctions making a minor contribution' x . In the UK government's view, this capacity mechanism is considered to be the most cost-effective outcome for the consumer. In their recent appraisal of the market, they stated that they 'do not intend or expect to maintain such low levels of LOLE into the future, as the reliability standard represents the most cost-effective amount of LOLE for consumers. Therefore, we expect LOLE to rise over the coming years (but remain below three hours), as plant without capacity agreements close' (ibid, p.10).

<b> The French capacity market <c> Political demand for security of supply

Before the liberalisation of the French electricity sector, EDF's planning of generation resources, which was based on their long term demand forecasts, incorporated the risk of shortage at peak load. Following liberalisation, the security of supply issue was first raised with the publication of the 20 September 2006 decree on forecast balances. This decree defined a criterion for matching supply and demand: like the UK, the loss of load must remain below three hours per year. The French electricity producers (through the French Electricity Union), underlined the contradiction: how to set an objective for available production capacity, given that the sector is liberalised? In the context of liberalising the sector, EDF is no longer in a monopoly position and no longer wishes to assume this responsibility alone, using its own generation resources. The French electricity producers also highlighted the specificities of electricity consumption in France, where the large share of electric heating leads to consumption peaks associated with low temperatures in winter.

<c> A political coalition in support of demand side response

As soon as this subject of generation failure emerged in France, it was formalised as a political demand external to the functioning of the market. This differs from many other cases where a capacity mechanism has been set up by the sector-specific regulator and internalised within the functioning of the market. This reflects the fact that, in underlying economic doctrine, the need for a capacity mechanism is contested; it is seen as a complement to the current market design, and regarded by some as a political demand for additional assurance of security of supply, hence reflecting a social (not an economic) choice. Political requirements were clearly expressed at this stage, despite the absence of any demonstration of the market's inability to meet security of supply requirements, or of a 'market failure'.

A parliamentary committee, under the responsibility of Senator Bruno Sido and Deputy Serge Poignant tackled the subject. The Directorate General for Energy and Climate, from the Ministry of Energy, provided the secretariat. This committee chose a capacity obligation covering all suppliers as the preffered mechanism to achieve the politically mandated security of supply target:

The proposal was to distribute the liability for the risk of generation failure amongst the various suppliers. This distributed obligation had to be set sufficiently in advance to give visibility to investors. The parliamentary committee gave priority to demand side response, a technical strategy very favourable to electro-intensive industrial customers who were able to enhance their loadshifting potential and revenues from this practice. The creation of a pool of industrialists able to contribute to demand flexibility was been supported during a transitional period, in advance of the establishment of an enduring mechanism.

At this first stage, the solution aimed to reduce the effects of market distortion on customers or competitors. The projected mechanism, a decentralised capacity obligation placed on suppliers, satisfied both the dominant supplier, EDF, which was no longer solely responsible for the security of supply, and the electro-intensive industrialists, who could increase their load-shifting capacity. Thus, it reflected the political compromise reached by parliament.

<c> Learning processes throughout stakeholder consultations

The proposals of Sido and Poignant's report were incorporated into the law on New Organisation of the Electricity Market (NOME) in 2010. The Minister delegated to Réseau de Transport de l'Electricité (RTE) , the French electricity network operator, the design of the capacity mechanism, which was then considered a purely technical matter. The official independent regulator of energy (Commission de Régulation de l'Energie) was not in charge of the design of the instrument. But RTE's leeway was limited, since there was no consensus at the EU level on the need for a capacity mechanism. RTE had to anticipate the risks of a judicial dispute initiated by consumers or suppliers which could be referred to the Court of Justice of the European Union. RTE's arbitration was, then, mainly guided by the concern to make the mechanism acceptable to the European Commission.

The consultations with interested parties organised by RTE had however revealed significant controversies. These consultations required the reopening of the debate on the nature of the mechanism, in particular whether it should be decentralised or not. According to independent electricity suppliers, the law did not require the use of a decentralised mechanism. Indeed, EDF's competitors considered that the decentralised mechanism was excessively fragile, too opaque, did not offer a sufficiently accurate price signal, did not offer a real guarantee of remuneration for suppliers and risked deterring them from investing in adequate capacities to meet security of supply targets. Conversely, they argued, a centralised auction mechanism, as was implemented in the UK, which would directly remunerate the market participants proposing investment projects, would be much more effective in creating the necessary capacity, and would also be much more transparent. RTE based its argument on a calculation of the financial transfers from consumers to suppliers induced by the mechanism. RTE, supported by electro-intensive industrial consumers, argued that the centralised mechanism was likely to be costlier, as it would encourage an overestimation of capacity needs and additional production investments.

In spring 2012, the independent authorities that supervise the electricity sector, the sector-specific regulator, the Energy Regulation Commission (CRE), and the French Competition Authority (AdlC), expressed strong scepticism about the need for the capacity mechanism, and the effect of a decentralised mechanism on financial transfers between consumers and producers. This scepticism led to a delay in the publication of the ministerial order to implement the mechanism. The CRE's scepticism was based on the fact that France already had a significant production overcapacity and its concern about the coherence of the French mechanism vis-à-vis the rules of the European internal market. The development of interconnectors with European neighbours was highlighted a more efficient strategy for developing security of supply.

Circumstances of the French power market added to these concerns. In 2015 and 2016, large imports via interconnectos, combined with French overcapacity, resulted in significant price reductions on the wholesale market, thus affecting EDF's revenues, margins and ability to finance new investments. As the French State is EDF's largest shareholder, the Government saw in the capacity mechanism a way to raise the price of electricity in order to restore EDF's financial position. Emmanuel Macron, then Minister of Economy and Finance, explained the issue of the low price of electricity: 'The Government is working on the regulatory side. This includes capacity mechanisms (…), the introduction of a price floor for CO2 (…). The adoption of such a measure would be decisive because, by increasing the "spot price", it will create in fact a price floor for a megawatt hour of electricity' xi . The Government therefore wished to speed up the regulatory process and the validation of the capacity mechanism by the European institutions.

At this stage of the design, the mechanism was based on obligations on suppliers to hold certificates for an adequate amount of generation and/or demand side response related to their customer portfolio. Certificates are allocated initially via an administrative procedure of certifying existing capacities of production or demand response, and then, certificates may be traded over-the-counter or on an organised market as suppliers seek to cover their obligations xii . The incumbent benefits from the implementation of this mechanism because it contributes to the covering of costs of its installed base (the cost of operation and maintenance of existing installations). Also, the decentralised mechanism has the advantage of remunerating all capacities and not only those utilised at peak periods. It is thus suited to the particular needs of EDF, as all of its nuclear production capacities are weakened by a very low market price for electricity.

<a> Evaluation by European Authorities

The trajectory of the development of national capacity mechanisms reveals the strengthening of the role of the EU's Directorate-General for Competition in the validation of national regulations, through the procedure for control of State Aid. This procedure evaluates the justification of national-level electricity market interventions, and their effect on competition in the European integrated market.

<b> Britain

From an EU perspective, a key issue was whether and how non-British capacity (e.g. from France, Netherlands, or Ireland) could participate in the capacity auctions. When the European Directorate General (DG) for Competition appraised the UK application for state-aid approval in 2014, one point of note was the UK government commitment to allow foreign capacity to benefit from contracts. This was not to be the case in the first capacity auction as interconnector flows were not permitted to bid into the auction; rather they were valued implicitly, i.e. incorporated into the demand curve for the capacity auction based on historical trends and statistical analysis of flows under different scenarios.

The Commission raised this as a point of concern, which was discussed at length during the prenotification stage of the state-aid assessment. DECC asked for more time to assess the technical feasibility of opening up the market, given uncertainty about interconnector flows under different operational scenarios; for example, how the obligation to provide energy at certain times might distort neighbouring markets. They committed to ensuring that subsequent auctions would value non-British capacity explicitly i.e. it could bid into the auction if judged to be capable of physical delivery and subject to the same penalties as domestic providers if obligations are not met.

From Jan 2020, all EU capacity mechanisms must be open to direct cross-border participation by capacity providers located in another Member State. This is to be achieved through cooperation agreements with the transmission system operators in the neighbouring countries, in order to avoid bidders receiving double payments from two national mechanisms xiii . A new EU requirement, following the updating of the Electricity Regulation in 2019, is that any new capacity with a carbon intensity of more than 550g/Kw will be prohibited from participating in any auction. Depending on the extent to which the UK aligns with EU Electricity Regulations in the future, it is likely that the British Capacity Market will accept bids from non-British capacity providers directly.

Aside from the question of foreign participation in the auctions, a recent, and surprising, development at the EU level saw the capacity market being suspended in late 2018 due to controversy about the eligibility of demand-side response (DSR) providers to access auctions for long term (15 year) capacity contracts. Under the original market rules approved by the Commission, DSR was part of 'Transitional Arrangements' under which they had a choice to either bid into a DSR-specific auction or the main auction, and compete against conventional capacity. DSR at the outset was only permitted to be awarded one-year capacity market contracts, not 3 or 15 year contracts as available to conventional generators, interconnectors and storage operators. This was on the basis that unlike generators or interconnectors, DSR does not incur significant fixed costs and, as such, does not suffer from the missing money problem.

A small-scale DSR provider challenged this rule, taking a case to the European Court of Justice (ECJ); and, following a protracted legal case, the court ruled in November 2018 that the market should be suspended, pending a review by the Commission xiv . The UK Department for Business, Energy and Industrial Strategy (BEIS)responsible for energy policy following the dissolution of DECC in 2016made a statement to the effect that this is a matter of providing clarification to the ECJ, rather than a fundamental rethinking of the scheme xv . The UK Government's view regarding DSR contract length, which the Commission eventually agreed with, was that 'no quantitative evidence was presented … that could be used to inform a policy decision on whether multi-year agreements for DSR are necessary' (ibid). The UK's capacity market has now received retrospective approval from the Commission following its more in-depth investigation.

<b> France

Unlike the UK case where approval was gained retrospectively, the compatibility of the French mechanism with European competition rules was a key consideration in the design process. This was prompted by a controversy which emeged in 2015 when electricity retailers claimed that they may be constrained from acquiring certificates from EDF, the dominant player in the generation market, and hence exposed to an unjustifiable level of risk. Faced with a technical controversy about the effects of the mechnism, the EU Court of Justice was sollicitated by the French State Council in 9 October 2015 to ensure that the planned French mechanism was compatible with European competition rules.

In the same period, the EU Commission was more active following its decision to perform a sector specific inquiry on capacity mechanisms across a number of EU states. Acknowledging the usefulness of these mechanisms, but also encouraging heterogeneity between Member States, the EU Commission sectoral inquiry recommended specific measures which aimed to provide a framework for national initiatives, even if European rules recognised the autonomy of the latter in energy policy [START_REF] Marty | L'Europe de l'énergie : de la concurrence à la solidarité ?[END_REF]. The Commission's objective was to avoid distortions to competition, particularly benefiting incumbents, and to strengthen the harmonisation of mechanisms. The Commission's 8 May 2012 communication on State aid modernisation set as a key condition for validating State Aid the identification of a "situation where aid can bring about a material improvement that the market alone cannot deliver, for example by remedying a well-defined market failure".

The European Commission introduced a significant change in the French mechanism, adding a centralised tendering mechanism for new generation capacity. Within the centralised mechanism, the public authority decides on the eligible technologies and the required capacities, and implements a competition four years before the date on which the capacities must become available. This centralised mechanism has been introduced to strengthen the bankability of new investments by guaranteeing them a minimum remuneration. Functioning like a contract-for difference, the price is guaranteed for seven years; if the market price is below this amount, the investor receives the difference. This mechanism addresses the demands of alternative suppliers other than EDF who have highlighted the fact that the decentralised mechanism may not sufficiently encourage investment in new facilities.

The work of validation not only concerned the design of the mechanism, but also its economic justifications. However, the economic literature provided diverse justifications; the Member State, France in this case, had to select the one most easily accepted by the European Commission. RTE quickly eliminated the main justification associated with the capacity mechanism in energy economics, namely the missing money issue resulting from price caps. Mobilising this argument would require an intrusive investigation into price formation in the French power market and assessment of the level of this missing money, which, given the dominance of EDF, would most likely turn out to be an adversarial procedure. According to RTE experts, this calculation was very complicated, because the counterfactual would be difficult to appraise and the results of such a procedure would be highly challengeable. According to the French Government and RTE, the mechanism was a justifiable response to a structural problem of its electricity market, its particular configuration and France's reliance on nuclear power. Unless a very rapid technological breakthrough could increase production flexibility (storage), and make consumption responsive to price signals, the capacity mechanism was accepted by the European Commission as a necessary market adaptation xvi .

<a> Conclusion

The difference between the British and French cases of introducing capacity remuneration mechanisms illustrates the European dimension of electricity market governance and transformation. In Britain, before circa. 2010, the security of supply issue was considered to be an outcome of the functioning of the free market, largely outside the political realm. While the UK has since changed its position, the EU has come to the view that the energy-only market should be the standard bearer, the legitimate market norm from which national regulations and political interventions became framed as deviations. But beneath the surface there remains significant scope for agency at the national level, with deviations from the preferred market model being authorised on condition that they are successfully framed as addressing market failures and that their economic scope is within certain limits.

Through this procedure of articulating a high-level market norm for Member States to follow, and the scope for deviation from it, the European Commission is conditioning how political objectives can be integrated into the market design process. However, as we have discussed earlier in this chapter, this 'normalisation' does not reflect a consensus in the academic literature on electricity market design where there are different views on the need for seperate capacity mechanisms.

Rather, the promotion of the energy-only market model in Europe reflects a political projectof European market integrationand a sensitivity of European regulators, who seek to limit deviations from a version of the market which most closely resembles a Walrasian ideal of market equilibrium.

Due to its limited powers to directly impose its preferred market design, and the need to maintain political legitimacy, it tolerates exceptions and deviations from the standard [START_REF] Reverdy | Making an exception: market design and the politics of reregulation in the French electricity sector[END_REF], that is if they are justified as the expression of a national political will that cannot be delivered by the market. The Member State must demonstrate, and articulate, an economically framed argument that the market is unable to achieve a political objective due to the existence of a 'market failure' [START_REF] Davies | When is a market not a market?:"Exemption","externality" and "exception" in the case of European state aid rules[END_REF][START_REF] Davies | The limits of neoliberalism: Authority, sovereignty and the logic of competition[END_REF]. It must also be demonstrated that the remedy is no worse than the failure, that it is appropriate to the objectives and proportionate. Political objectives must be translated into the frame of economic expertise in order to justify an exception to the standard.

Through this control of exception, the DG Competition tries to make progress towards greater integration through progressive alignment. Aware of the diversity of national policy issues and priorities, it seeks harmonisation.

As this chapter has shown, the process of negotiating these derogations can differ between cases.

For the UK, European influence over the design of the capacity market was largely carried out expost, as the country was a first mover in introducing a capacity mechanism and had already gained initial EU approval. For France, the organisation in charge of the design of the mechanism, RTE, anticipated the requirements and the justification that could be expected by the European Commission. The influence of EU institutions was therefore most significant through implicit channels [START_REF] Töller | Measuring and Comparing the Europeanization of National Legislation: A Research Note[END_REF]. RTE, in a situation of legal uncertainty about the assessment of its mechanism by the DG Competition, had strong incentives to negotiate before a formal examination of its proposal. The Europeanisation of the French capacity mechanism reflects the influence of the EU 'beyond compliance' [START_REF] Schmidt | Beyond Compliance: The Europeanization of Member States through Negative Integration and Legal Uncertainty[END_REF].

The other differences among Member States in terms of market design and economic justification can be explained by national and temporal contingencies. Their designs are path-dependent and also related to economic issues other than security of supply, and both of the mechanisms had been introduced in a context of a drop of electricity prices after 2008. The British mechanism was suited to the protection of privately owned thermal generators, while the French mechanism was a strategy to avoid a huge loss for the predominantly publically owned EdF and its fleet of nuclear plants.

Even if the regulation could be technically justified whatever the economic context, the political mobilisation in favour of the implementation of capacity mechanisms was accelerated in this specific economic circumstance.

Along with ensuring security of supply, in each country the executive authorities were concerned by the difficulties faced by the market players in coping with an increasingly volatile and uncertain electricity price trend, and most likely had an interest in protecting the companies themselves. Of course, this motivation was never written or proclaimed officially, being contradictory with State Aid doctrine. This willingness to override the market and the trend in political commitments to free markets, varying with the economic cycle, has also been observed by [START_REF] Borenstein | The US Electricity Industry after 20 Years of Restructuring[END_REF].

The implementation of capacity mechanisms reflects an ongoing search for a balance between the European Commission's desire to standardise and integrate the electricity market, by adopting a market model supported by some experts and academics, and the desire of countries to adapt this model to address local issues. Some of these can be legitimised in economic terms, such as the framing of security of supply as a market failure, while others are less explicit, such as financial support for domestic energy companies during an economic crisis. The European state aid control procedure has been evolved to accommodate these competing agendas. Behind the mainly technical discussions are ongoing debates about the ability of the market to achieve political objectives of common interest.

<a> Acknowledgements

This research received funding from the program CNRS-NEEDS (Nucléaire : Energie, Environnement, Déchets, Société) <a> Endnotes i The British electricity market covers England, Wales and Scotland and is under the jurisdiction of the UK government ii The material in this paper covers a period when the UK remained a member of the EU and the transition period which, at the time of writing, is due to conclude at the end of 2020. Brexit will of course fundamentally change the energy relationship between the EU and the United Kingdom. The nature of this future alignment is not something we cover in this chapter.

iii There are two transmission owners in Scotland; Scottish Power Transmission in the South and Scottish Hydro Electric Trnamsission covering the Highlands and Islands. Prior to their privatisation in 1991, these were part of vertically integrated electricity companies, the South of Scotland Electricity Board (SSEB) and the North of Scotland Hydro Electricity Board (NSHEB). Until the full integration of the electricity systems of England/Wales and Scotland, the Scottish companies had been selling into the Electricity Pool on the basis of a long term contract.

iv With the liberalisation of the sector, privatisation of EDF was initiated but was stopped immediatly, when politicians realised that they needed to retain control of the company in a context of uncertainty about electricity prices. The French State still retains 80% of the company's shares. vii Following the example of capacity market auctions already implemented in the USA, the UK capacity market has been designed as a "descending clock auction". Capacity providers place bids into the auction over multiple rounds indicating the amount of capacity they would be willing to make available at a particular price level. After successive rounds, when the supply curve coincides with the demand curve, a clearing price (£/kW/year) is determined which is paid to all bidders still in the auction at this point (known as "pay as clear").

  <c> The rise of the missing money argument In the lead up to the 2013 Energy Act, which introduced the capacity market and other elements of the UK's Electricity Market Reform (EMR), a number of options for a capacity intervention were considered in a consultation document published in December 2010 by the Department of Energy and Climate Change (DECC) (DECC, 2010b).

v

  Energy Act 2004 vi DECC. Consultation on Possible Models for a Capacity Mechanism: Impact Assessment, Department of Energy and Climate Change, London (2011)

viii

  In the capacity market there are two types of auctions: T-4, the main auction for delivery of capacity where the obligation would commence in four year's time, and T-1, a top up auction for delivery in one year's time which is used to top-up the T-4 auction if required. ix Falling to 0.001 hours in 2018/19 for example. In 2014/15, when the market commenced, it was 1.6 hours x BEIS (2019) Capacity Market Five Year Review (2014-2019) xi Minister Macron Tuesday, March 22, 2016, Commission for Economic Affairs of the National Assembly. xii Traded are published on the EPEX Spot website. The average price, given by the 2019 Electricity Balance established by RTE in January 2020, was characterised by a strong upward trend, from 10 K€/MW in 2017 to 16 K€/MW in 2020. In 2019 the mechanism contributed to an increase of 3.2 €/MWh for an average tariff including taxes of 176 €/MWh xiii Article 26 of Regulation (EU) 2019/943 xiv ECJ ruling in favor of Tempus energy: Judgment in Case T-793/14 xv https://www.gov.uk/government/collections/electricity-market-reform-capacity-market (accessed on 19.2.19) xvi State aid: Commission approves revised French market-wide capacity mechanism, 8 November 2016


Denilson Barbosa

Ioana Manolescu

Jeffrey Yu Xu

Application Benchmark

published or not. The documents may come

Comp. by: bvijayalakshmiGalleys0000885341 Date:20/12/08 Time:12:18:28 Stage:First Proof File Path://ppdys1108/Womat3/Production/PRODENV/0000000005/0000008302/0000000016/ 0000885341.3D Proof by: QC by: A Application Benchmark

Definition

An application benchmark is a suite of tasks that are representative of typical workloads in an application domain.

Main Text

Unlike a MICROBENCHMARK, an application benchmark specifies broader tasks that are aimed at exercising most components of a system or tool. Each individual task in the benchmark is assigned a relative weight, usually reflecting its frequency or importance in the application being modeled. A meaningful interpretation of the benchmark results has to take these weights into account.

The Transaction Processing Performance Council (TPC) is a body with a long history of defining and published benchmarks for database systems. For instance, it has defined benchmarks for Online Transaction Processing applications (TPC-C and TPC-E), Decision Support applications (TPC-H), and for an Application Server setting (TPC-App).

Other examples of application benchmarks are: the OO1 and OO7 benchmarks, developed for object-oriented databases, and XMark, XBench and TPoX, developed for XML applications.

Cross-references

▶ Micro-Benchmarks ▶ XML Application Recommended Reading

Author manuscript, published in "Encyclopedia of Database Systems Springer (Ed.) (2009) 99-100"