Albert Konijnenberg

Jinyu Li

Johny Habchi

Marion Dosnon

Giulia Rossetti

Rita Grandori

Sonia Longhi

Paolo Carloni

Frank Sobott

Conformational footprinting of proteins using a combination of top-down electron transfer dissociation and ion mobility

come   L'archive ouverte pluridisciplinaire

Introduction

In recent years native mass spectrometry is increasingly used to study proteins and protein complexes. Although traditionally largely employed as a supportive technique, more recently native MS has shown to be able to address structural questions that are difficult to tackle with traditional biophysical techniques [START_REF] Uetrecht | Interrogating viral capsid assembly with ion mobility-mass spectrometry[END_REF][START_REF] Zhou | Ion mobility-mass spectrometry of a rotary ATPase reveals AT-induced reduction in conformational flexibility[END_REF][START_REF] Konijnenberg | Global structural changes of an ion channel during its gating are followed by ion mobility mass spectrometry[END_REF][START_REF] Stengel | Dissecting Heterogeneous Molecular Chaperone Complexes Using a Mass Spectrum Deconvolution Approach[END_REF] . Such studies are based on the notion that proteins can be transferred natively into the gas-phase. Although for globular proteins a large body of evidence suggest that they can be transferred into the gas-phase whilst retaining their solution fold [START_REF] Hall | Do charge state signatures guarantee protein conformations?[END_REF][START_REF] Jurneczko | How useful is ion mobility mass spectrometry for structural biology? The relationship between protein crystal structures and their collision cross sections in the gas phase[END_REF] , such conclusions might be harder to justify for proteins that have little secondary or tertiary structure. As such a thorough understanding of the effect of the gasphase on protein structure is becoming increasingly important, but especially for structurally heterogeneous protein ensembles still remains difficult to obtain.

Two popular approaches to study protein structures in the gas-phase are ion-mobility mass spectrometry (IM-MS) and top-down radical-driven fragmentation experiments. Ion mobility adds the possibility to a mass spectrometry experiments to detect and separate different conformations and provide low resolution global structural information in the form of a collision cross section (CCS). These CCSs can then be compared to those obtained after calculations on structures obtained by X-ray crystallography or NMR spectroscopy [START_REF] Jurneczko | How useful is ion mobility mass spectrometry for structural biology? The relationship between protein crystal structures and their collision cross sections in the gas phase[END_REF] . Topdown experiments, on the other hand, are based on sequencing of intact proteins with non ergodic, radical-driven fragmentation methods combined with mass spectrometry detection, yielding information on the primary structure of a protein with amino acid resolution.

Several studies have indicated that analysis of intact proteins under native conditions can also yield structural information, for example on the backbone flexibility or the exposed surface area (solvent accessibility of residues) [START_REF] Zhang | Native electrospray and electron-capture dissociation in FTICR mass spectrometry provide top-down sequencing of a protein component in an intact protein assembly[END_REF][START_REF] Zhang | Native electrospray ionization and electron-capture dissociation for comparison of protein structure in solution and the gas phase[END_REF][START_REF] Li | Native top-down electrospray ionizationmass spectrometry of 158 kDa protein complex by high-resolution Fourier transform ion cyclotron resonance mass spectrometry[END_REF][START_REF] Lermyte | ETD allows for native surface mapping of a 150 kDa noncovalent complex on a commercial Q-TWIMS-TOF instrument[END_REF] . For example, it was shown that top-down electron transfer dissociation (ETD) enables surface mapping of the tetrameric protein alcohol dehydrogenase, by combining information from product ion spectra with solvent accessibility prediction of the amino acids in the protein structure [START_REF] Lermyte | ETD allows for native surface mapping of a 150 kDa noncovalent complex on a commercial Q-TWIMS-TOF instrument[END_REF] . Furthermore combining field asymmetric ion mobility spectrometry (FAIMS) separation with ECD revealed that the fragmentation patterns observed can be linked to the solution structure of a protein [START_REF] Robinson | The role of conformation on electron capture dissociation of ubiquitin[END_REF] . Here we provide evidence that top-down ETD can also be used to simultaneously characterize conformational differences based on their mobility arrival time-dependent ETD product ion spectra, when used in conjunction with ion mobility.

When ETD is coupled with IM (Fig S1 ), the data can be viewed as a 2D intensity heat map, i.e. mobility arrival time versus mass-to-charge ratio (m/z). Specific regions of interest can be selected using procedures within the software to extract ETD product ion spectra from the heat map (Fig S1B). Product ions originating from ETD, but released before the ion mobility cell, can be easily selected in this way, as they tend to lie on a diagonal line of increasing arrival time and m/z in the 2D intensity heat map. Alternatively, the ETD product ions may be liberated after ion mobility (following supplemental activation) when non-covalent interactions keep them together [START_REF] Lermyte | ETD allows for native surface mapping of a 150 kDa noncovalent complex on a commercial Q-TWIMS-TOF instrument[END_REF][START_REF] Zhang | Exploring salt bridge structures of gas-phase protein ions using multiple stages of electron transfer and collision induced dissociation[END_REF] . Since the supplemental activation is applied upon entry into the transfer cell, positioned after ion mobility separation, fragments that are released at this stage will retain the mobility arrival time of their precursor (Fig S1B). This allows assignment of product ions to a specific precursor conformation, based on their common mobility arrival time. Thus, combining ion mobility with ETD allows for differentiation of fragments from co-existing conformers within a single experiment.

Although (excessive) supplemental activation might cause conventional collision induced dissociation (CID), we observe that CID products (b and y-ions) are only a minority of the fragments observed, with the majority being c and z ions which can be easily distinguished from CID products based on their mass differences.

Results

To test the ability of native top-down ETD to probe structural differences we turned to the well-characterized protein Calmodulin. In absence of Ca 2+ Calmodulin has been shown to exist in equilibrium between a compact (globular) and an extended ("dumbbell") conformation [START_REF] Zhang | Molecular mechanisms of calmodulin's functional versatility[END_REF] (Fig. 1A). Our experiments yielded virtually similar results to previous IM-MS experiments on Calmodulin in the gas phase in terms of absolute collision cross sections and intensities of the conformations [START_REF] Wyttenbach | The effect of calcium ions and peptide ligands on the relative stabilities of the calmodulin dumbbell and compact structures[END_REF] , proving that the presence of radical anions does not interfere with ion mobility experiments. Using this approach we applied ETD fragmentation to the 7+ and 8+ charge states of CaM, which both display the two main CaM conformations. applying 40V of collisional activation after ETD/IM. Applying supplemental energy is crucial to release the fragments from the ETnoD products , most likely as non-covalent interactions are keeping the fragments in place [START_REF] Lermyte | ETD allows for native surface mapping of a 150 kDa noncovalent complex on a commercial Q-TWIMS-TOF instrument[END_REF][START_REF] Zhang | Exploring salt bridge structures of gas-phase protein ions using multiple stages of electron transfer and collision induced dissociation[END_REF] A distinct difference in both ETD fragmentation efficiency and fragment pattern is observed between the fragments originating from the compact and the extended precursor (Fig. 1A). A similar trend is observed for the fragment patterns from both conformations in the 7+ charge state. Assignment of the observed fragments from the compact and extended conformations provided two different product ion spectra . The compact conformation yields fragments that originate mainly from the termini of the protein, whereas fragments from the extended conformation essentially cover the complete protein sequence (Fig. 1). Mapping the observed fragments onto the known three-dimensional structures of calmodulin shows for the compact conformation that the fragments mainly stem from loops and helices that are located on the exposed surface of the protein. For the extended conformation of CaM we observe the fragments to be much more widespread over the protein structure and even located on the extended linker helix (ɑ4-ɑ5), which is buried in the compact structure. As such we show that the main structural differences between these structures are reflected in the respective fragmentation patterns, validating the conformational specificity of native top-down ETD fragment patterns.

Having showed that this method is able to yield different fragmentation patterns for different conformations, we aimed to apply it to a system where the gas-phase structure of the protein was unknown. Here we used native MS and top-down ETD to probe the unknown gas-phase structure of the three-helix bundle phosphoprotein X domain (P XD ) from measles virus (MeV) in the gas phase. P XD is required for MeV replication, via binding with the nucleoprotein C-terminal domain (N TAIL ) [START_REF] Habchi | Structural disorder within paramyxovirus nucleoproteins and phosphoproteins[END_REF] . P XD has been studied by X-ray crystallography and NMR, yielding a compact three α-helix bundle structure [START_REF] Johansson | Crystal structure of the measles virus phosphoprotein domain responsible for the induced folding of the C-terminal domain of the nucleoprotein[END_REF][START_REF] Gely | Solution structure of the C-terminal X domain of the measles virus phosphoprotein and interaction with the intrinsically disordered C-terminal domain of the nucleoprotein[END_REF] . In native mass spectrometry experiments P XD displays a broad charge state distribution indicative of a protein that is structurally heterogeneous [START_REF] Durzo | Molecular Basis for Structural Heterogeneity of an Intrinsically Disordered Protein Bound to a Partner by Combined ESI-IM-MS and Modeling[END_REF] , which is in line with recent work on the conformational landscape of P XD [START_REF] Bonetti | Identification and Structural Characterization of an Intermediate in the Folding of the Measles Virus X domain[END_REF] . Ion mobility experiments showed that the 3 lowest charge states (4 + -6 + ) all displayed multiple conformations (Fig. S2). Especially the 5 + charge state, with 5 distinct conformations, displays an astonishing degree of plasticity for a protein of only 55 amino acids (AA) (Fig. 2). Interestingly, these conformations appear to be stable in the gas phase over a 60 V range of ion acceleration voltages, in a collision-induced unfolding (CIU) study (Fig. S3).

We investigated the gas-phase structure of P XD using native top-down ETD on the 5 + -7 + charge states of P XD , combined with ion mobility to separate the different conformations. In order to release ETD fragments from the 5 + charge state, we required supplemental activation. The need for supplemental activation indicates that the higher-order structure is at least partially maintained in the gas phase, thus preventing the ETD fragments from being released. The requirement for supplemental activation was not observed for higher charge states. For both 6 + and 7 + , we observed fragments without supplemental activation. This suggests that the more unfolded states of the proteins, which are observed at higher charge states, undergo a loss of secondary and tertiary structure. Further evidence for structural heterogeneity is in the broad charge state series observed for P XD (4 + -9 + ). The fragment patterns obtained for 6 + and 7 + charge states show fragments between from amino acids 1-21 and 40-55, with the 7 + charge state additionally showing fragments from amino acids 30-40 (Fig. S4). This is remarkable as these fragments stem from parts of the protein that appear as α-helixes in the solution structure [START_REF] Johansson | Crystal structure of the measles virus phosphoprotein domain responsible for the induced folding of the C-terminal domain of the nucleoprotein[END_REF] ; α-helix 1 and α-helix 3 encompasses amino acids 4-12 and 33-47, respectively. The suggested loss of structure for higher charges states of P XD is supported by the ion mobility data which yields collision cross section (CCS) between 1169 and 1334 Å 2 for the 6 + and 1354 Å 2 for the 7 + charge state (Fig. S2).

Comparing these CCSs to the theoretical value of 960 Å 2 for the solution structure indeed points towards a less compact, more open conformation of P XD for those charge states.

We then focused on the 5 + charge state, which displayed a broad range of distinct conformations. We observed 5 conformers with CCSs of 938, 1032, 1112, 1171 and 1237 Å 2 , which are well separated by IM-MS (Fig. 2). By applying supplemental activation and correlating the product ions with the individual conformers via the mobility arrival time, we generated conformation-specific ETD fragment patterns. We ran a series of increasing supplemental activation (Fig. S5) to assess its effect on the release of fragments from P XD . At least 20V of supplemental activation was required in order to observe fragments. Increasing the supplemental activation further yielded a more extensive fragmentation pattern, although supplemental activation above 50V dramatically deteriorated the spectral quality.

We observed extensive sequence coverage for the two more extended conformations (Fig. 3). Interestingly, similar to the 6 + and 7 + we did not obtain fragments between AA 23-29 for any of the conformations, which are part of α-helix 2 in the solution structure (Fig. 3). The difficulty to sequence α-helices by top-down ETD has been reported before, with specific salt-bridges -on top of the already extensive hydrogen bonding between residues in the helix -apparently strengthening the α-helix to an extent that it resists fragmentation even with supplemental activation [START_REF] Breuker | Electrostatic stabilization of a native protein structure in the gas phase[END_REF] . For the third conformation we observed similar fragmentation patterns as for the two most extended conformations, with the exception of a large extent of α-helix 3, whereas the fragments continue to be observed from the loop between α-helix 2 and 3. For the two most compact structures we do not observe extensive fragmentation, but rather only some ETD fragments from the termini. Comparing these fragmentation patterns to the observed compact CCSs that these two species display, it is expected that significant higher-order structure is maintained for these conformations. As all conformations are activated under similar conditions, the differences in fragmentation patterns might point towards a loss of non-covalent interactions between or within the three-helix bundle in the gas-phase for the three most extended conformations, whereas the more compact conformations seem to retain enough interactions to keep the fragments together, even with supplemental activation applied. It should be noted that the P XD conformations of the 5 + charge state are stable up to 60 V collision energy, whereas a maximum of 50 V was used to release the fragments.

To analyze the broad range of P XD structures which we observed in the gas phase, we turned to computational modeling. First, we predicted the most probable protonation state of the protein with net charge state (5 + ) in the gas phase ([P XD ] 5+ , Fig. S6). To this aim, we used a hybrid Monte Carlo/molecular dynamics (MC/MD) in-house protocol. The latter reproduces the electrospray ionization (ESI)-MS derived main charge state for folded proteins in the free state and in complex with other proteins [START_REF] Marchese | A computational model for protein ionization by electrospray based on gas-phase basicity[END_REF][START_REF] Li | Molecular simulation-based structural prediction of protein complexes in mass spectrometry: the human insulin dimer[END_REF] . Our calculations are based on a structural model of P XD in solution (see Fig. S7), predicted from the NMR structure of the protein [START_REF] Bernard | Interaction between the C-terminal domains of N and P proteins of measles virus investigated by NMR[END_REF] . The resulting model is in good agreement with experimentally measured backbone N chemical shifts [START_REF] Johansson | Crystal structure of the measles virus phosphoprotein domain responsible for the induced folding of the C-terminal domain of the nucleoprotein[END_REF] (Fig. S7C). Next, we used steered MD (SMD) simulations to investigate the partial unfolding of [P XD ] 5+ in the gas-phase. SMD has been successfully used to study the unfolding of a variety of proteins in solution [START_REF] Hsin | Molecular origin of the hierarchical elasticity of titin: simulation, experiment, and theory[END_REF] . In our calculations, the gyration radius of the protein (see Fig. S8A) -and hence the CCS that correlates with it (Fig. S8B) -was mildly steered during the dynamics. The calculated CCS features several plateaus, corresponding to a folded state (different from the native state, though) along with four partially unfolded states (Fig. 4A and Table S1). Within the approximate error margin -estimated to be 2-3% [START_REF] Politis | A mass spectrometry-based hybrid method for structural modeling of protein complexes[END_REF][START_REF] Politis | Integrating ion mobility mass spectrometry with molecular modelling to determine the architecture of multiprotein complexes[END_REF] , our calculated CCS values correlate well with the experimentally derived CCS, except for the value of the folded state, which is underestimated by 11% (Fig. 4A). Interestingly the calculated CCS for the folded protein corresponds closely to the most compact experimental CCS for the 4 + charge state of P XD , which is smaller than the theoretical CCS of the solution structure of P XD (926 Å 2 ), thus suggesting a compaction of the structure upon entering the gas phase. The [P XD ] 5+ conformations associated with the calculated CCS values (I-V) are displayed in Fig. 4. Because of the match between calculated (stable plateaus, i.e. regions where the radius of gyration remained constant) and experimental CCS, visual inspection of these conformations may give insights into the partial unfolding of the protein in the ESI-MS experiment and explain its observed ETD fragmentation patterns (Fig. 3). In the folded state, the three α-helix bundle slightly opens up (I in Fig. 4). This leads to the ejection of α-helix 3 (II). For both conformations I and II, which are rather compact, we do not see much ETD fragmentation. This is consistent with the conformers' degree of secondary and tertiary structures. In III, α-helix 1 and α-helix 3 unravel. The latter is partially replaced by a new αhelix, closer to the C-terminus than α-helix 3. This replacement of helix 3 by one located closer to the C-terminus is consistent with the absence of fragments observed in the ETD experiments (Fig. 3 and4B): strong interactions are maintained in this region, preventing a release of the fragments. In IV and V, α-helix 2 progressively unravels. A "silent" area, which is not sequenced, is observed between amino acids 22 and 28 throughout all conformations and levels of applied supplemental activation (Fig S5). Although α-helix 2 slowly starts to unravel for the two most extended conformations, this region maintains a strong α-helical character (Fig. 4B), possibly preventing the release of any fragments. A similar effect is observed for the area encompassing the newly formed α-helix near the C-terminus. The formation of this new α-helix is interesting, as it is in this region that poor sequence coverage is obtained for the three largest conformations. This "silent" area, which is not sequenced, is followed by an unstructured region that is fully sequenced. This is again in agreement with the fragmentation patterns observed for conformations IV and V (Fig. 4).

These results validate that native top-down ETD combined with IM-MS provides significant structural information: the models for conformations I-V show to be consistent with experimental CCS data and furthermore provide a structural explanation for the ETD fragmentation patterns measured here.

The observation that even at 50V of supplemental activation after ETD, we do not observe fragments from certain regions is interesting. Ever since the first research using radical driven fragmentation was applied to proteins, it was observed that supplemental activation is required to release fragments from the remaining complex [START_REF] Horn | Activated ion electron capture dissociation for mass spectral sequencing of larger (42 kDa) proteins[END_REF][START_REF] Zubarev | Electron Capture Dissociation for Structural Characterization of Multiply Charged Protein Cations[END_REF][START_REF] Zubarev | Electron Capture Dissociation of Gaseous Multiply-Charged Proteins Is Favored at Disulfide Bonds and Other Sites of High Hydrogen Atom Affinity[END_REF] . However, as we go up stepwise in supplemental activation, we observe that after 30V the fragment pattern observed does not significantly change. This suggests that certain regions are simply not sequenced, or so stable that CID fragmentation occurs prior to release of these ETD fragments. As our results suggests that these regions maintain a high degree of secondary structure, a more systematic study on a well characterized protein structure should be performed to study the relation between gas-phase structure and the hierarchy of release of fragments with increasing supplemental activation.

To further validate our hypothesis that the behavior of P XD is caused by unraveling of the three-helix bundle, we added the protein N TAIL to P XD . The protein N TAIL is a binding partner of P XD and forms a 1:1 complex. Binding of the intrinsically disordered protein N TAIL to P XD is mediated by a disorder-to-order transition in the αMORE (molecular recognition elements) region of N TAIL , forming an α-helix that binds to the three-helix bundle motif of P XD with an affinity in the micro molar range [START_REF] Dosnon | Demonstration of a Folding after Binding Mechanism in the Recognition between the Measles Virus N TAIL and X Domains[END_REF] . The interactions between P XD and N TAIL have been studied

by IM-MS before, showing the formation of a 1:1 complex in the gas-phase [START_REF] Durzo | Molecular Basis for Structural Heterogeneity of an Intrinsically Disordered Protein Bound to a Partner by Combined ESI-IM-MS and Modeling[END_REF] . As the threehelix bundle is required for binding of P XD and N TAIL , we performed native top-down ETD on the N TAIL -P XD complex, to see if a difference in the fragmentation pattern for P XD can be observed. The fragile nature of the N TAIL -P XD interaction is reflected in the dissociation of the complex in the gas-phase upon supplemental activation after ETD (Fig. S9A). However, as the ETD reaction takes place before the transfer cell, where dissociation can be induced, fragments observed should still reflect the nature of the N TAIL -P XD complex. Top-down ETD of the native N TAIL -P XD complex shows exclusively fragmentation at the N-and C-termini of P XD (Fig. 5) over a broad range of collisional activation. These results are interesting as the much larger N TAIL protein show a more extensive fragmentation, suggesting that the absence of fragments for P XD is not caused by a low ETD fragmentation efficiency, but rather due to retention of the structure of P XD (Fig. 5 andS9B). The fragment patterns of P XD generated from its complex with N TAIL resemble these observed for the two compact conformations of P XD alone, where only fragments from the termini of P XD were observed due to the retention of higher order structure. Similar as for PXD alone, the fragment pattern is not changed with increasing collision energy, further reinforcing a possible relationship between higher order structure and the observed ETD fragments.

Discussion

Here we present data in which ETD fragment ions have been generated from distinct conformational states of multiply charged protein ions within the same experiment. This method was employed to generate simplified spectra, each containing the product ions originating from the different more compact or elongated conformations of structurally heterogeneous proteins. Extraction of the relevant product ion spectra from the 2D heat map allows linking of sequence-specific information with individual conformations of the protein.

In conclusion we show that the top-down ETD fragmentation process is conformationspecific and can thus differentiate individually coexisting conformations of a protein in a single experiment. By doing so we established native top-down electron transfer dissociation as a powerful addition to the toolbox of mass spectrometry techniques for structural biology. Paired with ion mobility, native top-down fragmentation approaches can provide essential structural restraints, both globally at low resolution (distinguish conformations by CCS (Å 2 )) and per residue (determine solvent accessibility or flexibility). These restraints in turn could be used to refine or validate models generated from homology modeling or molecular dynamics [START_REF] Webb | Modeling of proteins and their assemblies with the Integrative Modeling Platform[END_REF][START_REF] Politis | Integrative modelling coupled with ion mobility mass spectrometry reveals structural features of the clamp loader in complex with single stranded DNA binding protein[END_REF] , or serve as selection criteria for possible candidates from large ensembles of structures, as can e.g. be generated with software such as the Flexible Meccano package for intrinsically disordered proteins [START_REF] Ozenne | Flexible-meccano: a tool for the generation of explicit ensemble descriptions of intrinsically disordered proteins and their associated experimental observables[END_REF] .

Methods

Sample preparation:

The pDEST14 vector, allowing the expression of N-terminally hexahistidine tagged recombinant N TAIL under the control of the T7 promoter, and the pDEST14 construct encoding C-terminally hexahistidine tagged MeV XD were used for the expression of the recombinant proteins. Expression and purification of the protein was carried out as described previously [START_REF] Johansson | Crystal structure of the measles virus phosphoprotein domain responsible for the induced folding of the C-terminal domain of the nucleoprotein[END_REF][START_REF] Bernard | Interaction between the C-terminal domains of N and P proteins of measles virus investigated by NMR[END_REF] , except that the final gel filtration step was carried out using 10 mM ammonium acetate pH 6.5 as elution buffer. To obtain the PXD-NTAIL complex an equimolar concentration of NTAIL was added, incubated for 5 minutes and subsequently diluted to a final concentration of 10 µmolar. Calmodulin from bovine testes (ID: P1431) was obtained from Sigma Aldrich (St Louis MO, US) and dissolved in 100mM Ammonium Acetate (AmAc) pH 6.8 to a concentration of 100uM. Sample was subsequently aliquoted and stored at -20C for further use. CaM aliquots were diluted to a final concentration of 10uM in 100mM AmAc and buffer exchanged twice on a Biorad (Hercules CA, US) P6 spin column (ID: 732-6221) against 100mM AmAc to obtain calcium free calmodulin sample. Final samples were measured immediately after preparation Mass spectrometry: Multiply charged ions were generated using nano-electrospray ionization with in-house prepared gold-coated capillaries and a capillary voltage of +1.5 kV.

All experiments were performed on a Waters Synapt G2 HDMS with ETD option. Important Experimental collision cross sections (CCS) were determined by calibration against denatured proteins of known CCS (cytochrome C, ubiquitin and myoglobin) as reported elsewhere [START_REF] Bush | Collision cross sections of proteins and their complexes: A calibration framework and database for gas-phase structural biology[END_REF] . Denatured proteins were chosen as their charge and CCS increment reflects the unfolding of P XD in the gas-phase and the intrinsically disordered nature of N TAIL better than native globular proteins would.

Computational modeling: Based on the solution NMR structure of P XD (residues 462-505, PDB ID: 2K9D [START_REF] Bernard | Interaction between the C-terminal domains of N and P proteins of measles virus investigated by NMR[END_REF] ), 200 initial models of P XD (residues 459-507 with attached C-terminal hexahistidine tag) were generated using MODELLER 9v9 package [START_REF] Marti-Renom | Comparative protein structure modeling of genes and genomes[END_REF] . The lowest-DOPE (discrete optimized protein energy) score [START_REF] Shen | Statistical potential for assessment and prediction of protein structures[END_REF] model was selected as the starting structure for the following MD-based refinement in solution. The protonation states of residues in solution were assigned according to the corresponding pK a values calculated by using the H++ webserver [START_REF] Gordon | H++: a server for estimating pKas and adding missing hydrogens to macromolecules[END_REF] . P XD was inserted into a water box with edges of 505851 Å 3 containing ~4,420

water molecules and 5 Cl -ions to neutralize the system. The AMBER ff99SB-ILDN force field [START_REF] Lindorff-Larsen | Improved side-chain torsion potentials for the Amber ff99SB protein force field[END_REF][START_REF] Pavelites | A molecular mechanics force field for NAD+ NADH, and the pyrophosphate groups of nucleotides[END_REF][START_REF] Walker | Large and Fast Relaxations inside a Protein: Calculation and Measurement of Reorganization Energies in Alcohol Dehydrogenase[END_REF][START_REF] Craft | An AMBER/DYANA/MOLMOL phosphorylated amino acid library set and incorporation into NMR structure calculations[END_REF] and TIP3P force field [START_REF] Jorgensen | Comparison of simple potential functions for simulating liquid water[END_REF] were used for the protein and Cl -ions, and for water, respectively. Periodic boundary conditions were applied. Electrostatic interactions were calculated using the Particle Mesh Ewald (PME) method [START_REF] Darden | Particle mesh Ewald: An N-log(N) method for Ewald sums in large systems[END_REF] , and the cutoff for the real part of the PME and for the van der Waals interactions was set to 1.0 nm. All bond lengths were constrained using the LINCS algorithm [START_REF] Hess | LINCS: A linear constraint solver for molecular simulations[END_REF] . Constant temperature and pressure conditions were achieved by coupling the systems with a Nosé-Hoover thermostat [START_REF] Hoover | Canonical dynamics: Equilibrium phase-space distributions[END_REF][START_REF] Nose | A molecular dynamics method for simulations in the canonical ensemble[END_REF] and an Andersen-Parrinello-Rahman barostat [START_REF] Parrinello | Polymorphic transitions in single crystals: A new molecular dynamics method[END_REF] . A time-step of 2 fs was employed. The protein underwent 1000 steps of steepest-descent energy minimization with 1000 kJ mol -1 nm -2 harmonic position restraints on the protein complex, followed by 2500 steps of steepestdescent and 2500 steps of conjugate-gradient minimization without restraints. The system was then gradually heated from 0 K up to 300 K in 20 steps of 2 ns. 200 ns long MD simulation at 300 K and 1 atm pressure was carried out using GROMACS 4.5.5 [START_REF] Berendsen | GROMACS: A message-passing parallel molecular dynamics implementation[END_REF] . The structure closest to the average conformation of the protein in aqueous MD simulation, which is in good agreement with the experimentally measured chemical shifts [START_REF] Johansson | Crystal structure of the measles virus phosphoprotein domain responsible for the induced folding of the C-terminal domain of the nucleoprotein[END_REF] (Fig. S6), was employed as starting structure for the gas-phase simulations. The solvent and the Cl - counterions molecules were removed.

A hybrid Monte Carlo (MC)/MD protocol [START_REF] Marchese | A computational model for protein ionization by electrospray based on gas-phase basicity[END_REF][START_REF] Li | Molecular simulation-based structural prediction of protein complexes in mass spectrometry: the human insulin dimer[END_REF] was used to identify the most probable protonation states of P XD at 5 + ([P XD ] 5+ ) in the gas phase. The protocol is based on OPLS/AA [START_REF] Jorgensen | Potential energy functions for atomic-level simulations of water and organic and biomolecular systems[END_REF] force field energy augmented by additional energy terms associated with the gas-phase basicity (GB) of ionizable residues 21 (see ref. [START_REF] Li | Molecular simulation-based structural prediction of protein complexes in mass spectrometry: the human insulin dimer[END_REF] for detailed description). After the MC/MD calculation reached convergence (Fig. S5), the selected aqueous structure with the identified lowest energy protonation state for the [P XD ] 5+ underwent steered molecular dynamics (SMD) simulation at 300 K for 72 ns in the gas phase to enforce the protein to extended conformation by pulling the gyration radius (R g ) of the protein (see Fig. S8). The SMD spring constant was set as 500 kJ•mol -1 •nm -2 , the velocity is 0.0001 nm per 1000 steps and the target R g value is 4.5 nm. These values are similar to those applied in ref. [START_REF] Bonomi | PLUMED: A portable plugin for free-energy calculations with molecular dynamics[END_REF] . The SMD was carried out using GROMACS 4.5.5 [START_REF] Berendsen | GROMACS: A message-passing parallel molecular dynamics implementation[END_REF] and PLUMED plug-in [START_REF] Bonomi | PLUMED: A portable plugin for free-energy calculations with molecular dynamics[END_REF] with the same setup as the one described for the aqueous MD simulation, except that the time step was 1.5 fs and the force field was OPLS/AA [START_REF] Jorgensen | Potential energy functions for atomic-level simulations of water and organic and biomolecular systems[END_REF] . Theoretical CCS values were calculated for structures every 15 ps using the projection approximation (PA) method implemented in the MOBCAL code [START_REF] Shvartsburg | Optimization of algorithms for ion mobility calculations[END_REF][START_REF] Mesleh | Structural Information from Ion Mobility Measurements: Effects of the Long-Range Potential[END_REF] spectroscopy [START_REF] Breuker | Electrostatic stabilization of a native protein structure in the gas phase[END_REF] , revealing it to be a stable three-helix bundle in solution. Solution model of the N TAIL -P XD complex as calculated previously [START_REF] Durzo | Molecular Basis for Structural Heterogeneity of an Intrinsically Disordered Protein Bound to a Partner by Combined ESI-IM-MS and Modeling[END_REF] The structures of P XD and N TAIL are depicted in grey, with the observed ETD fragments mapped in red, whereas observed fragments for the intrinsically disordered protein N TAIL are colored orange.

Figure 1

 1 Figure 1 shows the fragments observed for the 8+ charge state extracted from the arrival times of the compact conformation (Fig 1B) and extended conformation (Fig 1C) upon

  voltages were: sampling cone 25-40 V, extraction cone 1 V, trap collision energy 4 V, transfer collision energy 70 V for CaM and 50 V for P XD (unless indicated otherwise) and trap DC bias 30 V. Selected charge states for CaM, P XD and N TAIL -P XD were mass-selected using the 32 k quadrupole and underwent an ion-ion ETD reaction with reagent 1,4 dicyanobenzene in the trap T-wave (at ~510 -2 mbar He) of the instrument. These ETD ions then pass through the T-wave ion mobility stage (at ~1.5 mbar N 2 ) and are subjected to CID in the transfer Twave (at ~210 -2 mbar Ar) and then analyzed using TOF-MS. Ion mobility separation was performed at a wave velocity of 300 m/s and a wave height of 13 V. ETD settings used were a scan time interval of 1 s and a reagent refill time of 0.1 s. The wave velocity in the trap cell, where the ETD fragmentation takes place, was 300 m/s with a wave height of 0.25 V. Data acquisition and processing were carried out using MassLynx4.1. Peak assignment was performed by manually comparing the observed fragment masses with an in-silico generated fragment list from the protein sequence. A cutoff of 3 times signal-to-noise or greater was used to determine which fragments were considered to be observed. Relative intensities of fragments were obtained by normalizing the fragment intensities against the most intense fragment observed. For spectra with multiple conformations another normalization round was performed, which scaled each intensity relative to the area under the drift time curve of the conformation it was found in.

Figure 1

 1 Figure 1 Conformational footprinting of the two conformations of Calmodulin. A conformational specific fragmentation spectra of each of the two conformations of Calmodulin, with their respective structures depicted on the right side. Fragments are shown on the structure of the structure in their respective colors. Fragmentation patterns for the 8+ and 7+ of B the compact, globular conformation and C the extended, dumbbell structure of CaM. Black bars indicate the location of the 8 alpha-helices that make up the structure of CaM.

Figure 2

 2 Figure 2 Mass spectra of P XD reveal a broad charge state distribution indicative for an unfolded protein, as is reinforced by the multiple conformations observed for the 5 + charge state of P XD (red inset). The blue inset shows the solution structure of P XD as solved by NMR

Figure 3

 3 Figure 3 ETD fragments observed for the different conformations of the 5 + charge state of P XD . The mobility arrival time distribution (ATD) on the right shows the different conformations obtained from which the individual fragment patterns were extracted. Cfragments are colored red, with z-fragments in grey. Highlighted orange areas indicate alpha-helices in the solution structure of P XD .

Figure 4

 4 Figure 4 SMD simulations of [P XD ] 5+ . A Calculated CCS values plotted as a function of simulated time. The experimental CCS values for conformations I-V are indicated by dashed lines and the calculated CCS value of the protein in aqueous solution is indicated by the solid line. B Most representative structural models of the different conformations of the 5 + charge states of P XD based on the steered molecular dynamics simulations after cluster analysis of the structures present in the plateau areas, with the observed ETD fragments observed mapped in red for each ion-mobility separated conformation.

Figure 5

 5 Figure 5 Fragment patterns for A P XD and B N TAIL generated by top-down ETD of the 10 + N TAIL -P XD complex at various levels of supplemental activation reveal only terminal fragments, indicative of a stable three-helix bundle structure of P XD within the complex. C-fragments are colored in red (P XD ) or orange (N TAIL ), whilst z-fragments are colored grey in both figures. C

  . Since the PA CCS (CCS PA ) typically underestimates experimental CCS measured in nitrogen buffer gas by ∼14% 53 , the scaled values (CCS exp =1.14×CCS PA ) were used for comparison with experimental results.

	Corresponding Author

* Frank Sobott, Department of Chemistry, University of Antwerp, Groenenborgerlaan 171, B-2020 Antwerpen, Belgium. Email: frank.sobott@uantwerpen.be. Telephone: +32 32653388

Acknowledgements

The authors would like to thank the Hercules foundation for funding the Synapt G2 instrument.

Author contributions

A.K. and F.S conceptually conceived the research. J.H. and M.D. produced and purified the proteins. A.K. performed the mass spectrometry experiments. J.L. and G.R. performed the SMD calculations. All authors contributed to interpreting the data and writing the paper.


Philippe Ledent

Anshul Paigwar

Alessandro Renzaglia

Radu Mateescu

Christian Laugier

Formal Validation of Probabilistic Collision Risk Estimation for Autonomous Driving

published or not. The documents may come

Formal Validation of Probabilistic Collision Risk Estimation for Autonomous Driving

Philippe Ledent, Anshul Paigwar, Alessandro Renzaglia, Radu Mateescu and Christian Laugier

Abstract-Autonomous driving technology is rapidly advancing towards level 5 autonomy along with claims of increasing safety on roads. However, a proper validation of such safetycritical, complex systems and of their reliability still needs to be addressed adequately. To this end, standard exhaustive methods are inappropriate to validate the probabilistic algorithms widely used in this field and new solutions need to be adopted. In this work, we present a new approach where formal verification is employed to validate systems with probabilistic predictions.

In particular, we focus on the risk assessment generated by a probabilistic perception system, the Conditional Monte Carlo Dense Occupancy Tracker (CMCDOT). This framework provides an environment representation through Bayesian probabilistic occupancy grids and estimates Time-to-Collision probabilities for every static and dynamic part of the grid in near future. Focusing on the validation of the probabilistic collision risk estimation, we adopt the CARLA simulator to generate a large number of realistic intersection crossing scenarios with two vehicles. The formal verification is then performed using the XTL model checker of the CADP toolbox, based on the definition of appropriate Key Performance Indicators (KPIs). Finally, a quantitative analysis that goes beyond classical temporal logic verification is provided.

I. INTRODUCTION

The use of formal methods for verification and certification of algorithms and mathematical logic of software is a long standing research [START_REF] Mccarthy | Towards a Mathematical Science of Computation[END_REF]. While our software are continuously evolving, becoming more capable and complex, the methods to verify software need to evolve simultaneously. Physical and software components are getting deeply intertwined, each operating on different spatial and temporal scales. Verification of such automated cyber-physical systems (ACPS) is still an open research challenge.

Autonomous vehicles represent a critical ACPS that require meticulous attention in validation. Moreover, there are increasing demands on regulating and validating intelligent vehicle systems to build public trust in their use. Formal methods have already had several successful deployments in fields like aerospace and railways [START_REF] Garavel | Formal Methods for Safe and Secure Computer Systems -BSI Study 875[END_REF], but autonomous driving remains a challenging field because of the complexity of its key components, such as: perception of the environment, scene interpretation, decision making and undertaking actions. Considering the fact that intelligent vehicles are supposed to be driven on existing roads, along with other vehicles with human drivers, a higher level of uncertainties need to be taken into account [START_REF] Urmson | Autonomous driving in urban environments: Boss and the urban challenge[END_REF]. In these scenarios, the use of probabilistic approaches for perception and prediction become essential to Univ. Grenoble Alpes, Inria, 38000, Grenoble, France; e-mail: firstname.lastname@inria.fr accurately confront the uncertainties in the environment [START_REF] Leonard | A perceptiondriven autonomous urban vehicle[END_REF]. The stochasticity of these algorithms, involving multiple states and complex transitions between them, makes the validation through standard approaches often unviable.

Most of the existing literature revolves around the formal verification of decision algorithms [START_REF] Kamali | Formal verification of autonomous vehicle platooning[END_REF], [START_REF] Barbier | Validation of Perception and Decision-Making Systems for Autonomous Driving via Statistical Model Checking[END_REF]. Researchers are exploring formal verification techniques for Probabilistic Model Checking [START_REF] Zhao | Probabilistic model checking of robots deployed in extreme environments[END_REF]. Compared to conventional systems (e.g., discrete-time Markov models), where the formal model accurately reflects the actual behaviour of the real-world system [START_REF] Calinescu | Formal verification with confidence intervals to establish quality of service properties of software systems[END_REF], verification through formal model is fairly accurate but it becomes more challenging for autonomous systems in dynamic environments. In the context of intelligent vehicle systems, where states (e.g., estimation of collisions) change and evolve at every time step, exhaustively checking such properties is usually not affordable in many scenarios because of time, complexity and costs constraints.

The main contribution of this paper is a methodology to validate perception systems based on a combination of simulation, formal verification, and statistical analysis. The simulation framework must comprise a realistic description of the dynamic physical environment (e.g., urban landscape and vehicles), the perception system under study, and a set of relevant scenarios (e.g., leading to collisions). We consider here the validation of the Conditional Monte Carlo Dense Occupancy Tracker (CMCDOT) [START_REF] Rummelhard | Conditional monte carlo dense occupancy tracker[END_REF], in particular its collision risk estimation functionality. Executing the simulation scenarios yields traces of events containing the suitable data for validation (timestamp, estimated probabilities of collision, position and velocities of the vehicles, etc.). Then, on each trace obtained, a number of typical temporal properties (invariants, safety, liveness) are verified using the XTL [START_REF] Mateescu | XTL: A Meta-Language and Tool for Temporal Logic Model-Checking[END_REF] model checker of the CADP toolbox [START_REF] Garavel | CADP 2011: A Toolbox for the Construction and Analysis of Distributed Processes[END_REF], producing quantitative verdicts (sets of events violating the properties, with their diagnostic information). Finally, a statistical analysis of the verdicts is carried out, by defining an appropriate Key Performance Indicator (KPI) for each property, using it to compute a grade for each trace, and aggregating the results in analysis reports using R-studio. The whole methodology has been automated and can be instantiated in other contexts as well.

The rest of the paper is organized as follows. Section II briefly introduces the main properties of CMCDOT, with a particular focus on the collision risk estimation. Section III discusses the principles of formal validation and how it is employed on the considering problem. In Section IV the results obtained with the analysis of intersection crossing scenarios are finally presented and discussed.

II. COLLISION RISK ESTIMATION

The CMCDOT framework [START_REF] Rummelhard | Conditional monte carlo dense occupancy tracker[END_REF] is a perception system which provides a dense and generic representation of the environment [START_REF] Elfes | Using occupancy grids for mobile robot perception and navigation[END_REF], [START_REF] Moravec | Sensor fusion in certainty grids for mobile robots[END_REF] as a probabilistic occupancy grid (see Fig. 1), based on Bayesian fusion, filtering of sensor data and Bayesian inference [START_REF] Bessière | Bayesian Programming[END_REF]. By exploiting specific sensor models, the gathered data are converted in probabilistic estimations which represent the environments as static and dynamic occupied regions, free spaces and unknown areas (Fig. 2). This differentiation enables the use of state-specific models, such as classic occupancy grids for static components and sets of moving particles for dynamic occupancy, as well as confidence estimation and management of areas with no information.

The resulting approach is particularly suitable in situations where incomplete or even contradictory data come from different sensors (camera, lidars, radars, etc.). The estimation for each cell over time can be obtained from various sensors data, whose specific uncertainty (noise, measurement errors) is taken into consideration. Filtered cell estimations are thus much more robust, leading to a more reliable global occupancy of the environment, reducing false detection.

Additionally, an important feature of the CMCDOT, and the main subject of study of this paper, is the estimation of the collision risk for each cell of the grid. Most of the existing risk estimation methods consist in detecting and tracking dynamic objects in the scene [START_REF] Fortmann | Multi-target tracking using joint probabilistic data association[END_REF], [START_REF] Khan | An mcmc-based particle filter for tracking multiple interacting targets[END_REF]. The simplest solution is then to estimate a Time to Collision (TTC) by projecting the egovehicle and the trajectories of other moving object in the future [START_REF] Kaempchen | Situation assessment of an autonomous emergency brake for arbitrary vehicle-to-vehicle collision scenarios[END_REF]. Detection of moving objects requires to pre-define shape of objects and involves fitting of object models in pointcloud to find the location of objects in environment. As the number and types of objects increase, the detection and tracking becomes difficult and costly problem to solve.

The grid-based approach used in the CMCDOT framework, instead of detecting objects, directly computes estimations of the position of every static and dynamic cell of the grid by linearly projecting them in near future based upon their estimated velocity as well as the trajectory of the ego-vehicle. These estimations are iteratively computed over short-time periods, until a potential collision is detected. In this case a TTC is associated to the cell from which the colliding element came from (Fig. 3). The probabilistic estimation for different TTCs (e.g, 1, 2 and 3 seconds) are then associated to every cell to obtain a collision risk profile. This strategy, originally presented in [START_REF] Rummelhard | Probabilistic grid-based collision risk prediction for driving application[END_REF], presents the advantage of being model free, avoids solving the complex problem of multi-object detection and tracking, while integrating the totality of the available information and providing a probabilistic estimation of the risk associated to each part of the scene. The result of this estimation can then be used as the starting point for any control and decision-making system.

A. Simulation for perception

In this work, the simulation relies on the use of two frameworks: CARLA, an open urban driving simulator [START_REF] Dosovitskiy | CARLA: An open urban driving simulator[END_REF], and Robot Operating System (ROS). CARLA simulation environment consists of complex urban layouts, buildings and vehicles rendered in high quality, allowing for a realistic representation of real-world scenarios. The ego-vehicle and its sensors, as well as other moving vehicles, as depicted in Figure 4, can be configured in the simulation to match with the actual system. The provided CARLA-ROS bridge enables data acquisition from the simulation in native ROS message formats, where the data can be recorded, stored, and processed by the same code running on the actual vehicle.

In order to establish the ground truth, a grid indicating the position of all simulated objects is needed. This grid must reflect CMCDOT's occupation grid in the following aspects: origin position, grid direction, cell size and velocities. The bounding box and velocity information provided by CARLA simulator is translated into occupancy grid at each time step to generate the ground truth.

Currently, each lidar is simulated with the appropriate position on the ego vehicle, the same sampling frequency and the same data format as the physical sensor. To match the sensing uncertainty, a Gaussian noise can be added.

In order to be able to efficiently generate a large number of simulated environments, we have perfected a parameterbased approach which streamlines the process through which the dimensions and initial position and velocity of non-ego vehicles are specified.

III. FORMAL VALIDATION

One of the main assets of CMCDOT is the possibility to estimate the probability of collision for each cell in the grid.

The validation focuses on checking the reliability of this risk estimation by performing a rigorous formal verification on execution traces, and then by analyzing the output of the verification using well defined KPI in order to obtain a quantitative evaluation of CMCDOT as grades. Three properties will be checked: coherence, safe prediction (safety), and prediction progress (reactivity).

These properties are defined on execution traces where each line in the trace file is called an event. Each event has a timestamp, the speeds of both vehicles, the probability of collision within 1, 2, and 3 seconds, the positions of both vehicles, and a collision indication. All data are real numbers except the collision indication which is Boolean. We denote P i col (e) where i ∈ {1, 2, 3} the probability of collision within i seconds read on event e. We denote P col (e) = (P 1 col (e), P 2 col (e), P 3 col (e)) the triple that contains all three probabilities of collision for e.

The verification consists in checking that for every trace T , the set of events e in T that violate each property P is empty:

∀T, T P ⇐⇒ {e ∈ T | e P } = ∅
Each trace receives a verdict file indicating for each property if the property holds. When it does not, the verdict contains for each property the list of violating events along with evidence of why the event is a violation of P .

The verification is carried out using the XTL [START_REF] Mateescu | XTL: A Meta-Language and Tool for Temporal Logic Model-Checking[END_REF] model checker of the CADP toolbox [START_REF] Garavel | CADP 2011: A Toolbox for the Construction and Analysis of Distributed Processes[END_REF] dedicated to the formal modelling and analysis of asynchronous concurrent systems. The underlying behavioural models used within CADP are state spaces, i.e., state-transition graphs in which transitions are labeled by events (channel names and data values exchanged) executed by communicating concurrent processes. XTL is both a language and a tool for querying state spaces. It enables the expression of temporal logic operators, observer automata, and to perform more general computations over (sets of) states and transitions, also involving the data values carried by the events. To apply these tools for CMCDOT, we consider the execution traces as particular cases of state spaces consisting of a single finite sequence of transitions, each one being labeled by an event of the trace.

At time t CMCDOT's risk grid indicates for each cell c the probability for c to collide with the ego-vehicle within t + 1, t + 2, and t + 3 seconds. To proceed with our analysis, the probabilities are abstracted into three interpretation classes: low, transitioning and high. For simplicity's sake, these classes are represented by 0, 0.5, and 1 respectively. The thresholds that separate the three classes have been fixed at 0.1 and 0.9.

A. Coherence of the risk probabilities

The three probabilities give overlapping information. In particular, for some event e, P col (e) = (0, 0.5, 1) indicates that no collision should occur during the first second following e but one must occur before the end of the third second following e. This collision may occur during the second second or the third second. However certian configurations like P col (e) = (1, 0.5, 0) are incoherent because they give Interpretation of P col (e) Meaning in English (0, 0, 0) Not before 3 (0, 0, 0.5)

Not before 2 (0, 0, 1)

Between 2 and 3 (0, 0.5, 1)

Between 1 and 3 (0, 1, 1)

Between 1 and 2 (0.5, 1, 1)

Before 2 (1, 1, 1)

Before 1 (0, 0.5, 0.5)

Not before 1 (0.5, 0.5, 1)

Before 3 (0.5, 0.5, 0.5) Uncertain

TABLE I: Table of coherent combinations of P col (e) (left)

and their meaning in English (right) given in terms of the predicted collision. For example, "Between 2 and 3" means that the collision should occur between two and three seconds.

contradictory indications, i.e., there should be no collision within the next three seconds and there must be one within the first second. Altogether there are 3 3 = 27 combinations for P col (e) where seventeen are incoherent and ten are coherent.

In fact, the coherent combinations are only those where the probabilities follow an order relation. Table I lists the ten coherent configurations along with their interpretations. The seven first are good configurations while the three last are coherent but not very useful. In particular the last one does not give any meaningful information for decision.

The coherence property consists in asserting for every event e in a trace T , that the triple P col (e) has one of the ten coherent configurations. This is an invariant assertion that can be checked on every event individually regardless of the information on other events.

B. Safe Prediction

In Table I, the interpretations (left) show that the triple P col (e) is a prediction of where a collision should occur or not during the three seconds following e. Safety properties specify intuitively that "something bad will never happen" [START_REF] Manna | A hierarchy of temporal properties[END_REF]. A bad prediction is when P col (e) predicts no collision yet one occurs or when P col (e) does not predict a collision yet one occurs. Safety properties are classic in temporal logic. They will be evaluated with an observer automaton [START_REF] Alpern | Verifying temporal properties without temporal logic[END_REF], illustrated on Figure 5. For every event e in a trace T , the observer is synchronized with the trace taking as parameter the prediction P col (e). It parses the trace during three seconds following e observing whether a collision occurs or not as predicted. If the automaton decides that all events of T are safe predictions (always ending in the accepting state 4 and never in the rejecting state 5) then T satisfies the safe prediction property because "nothing bad happened". This automaton, encoded in XTL and executed on each event of T , computes the set of events that violate this property and produces a verdict for each of them.

C. Prediction Progress

The prediction of collision should progress in two ways as a collision approaches. First, each one of the P i col (e) (i ∈ {1, 2, 3}) should follow the class progression 0, then 0.5, then Fig. 5: Safety automaton checking for each event if it is a good or bad prediction. It is a mix between a deciding automaton and a timed automaton. State 1 is the initial state, state 4 is the accepting state, and state 5 is the rejecting state. For a given event e in the trace, the automaton parses the events covering the next three seconds. In state 1 it checks that the collision indication during the first second corresponds to P 1 col (e). If so, it moves to state 2, if not it moves to state 5.

1. Second, considering the triple P col (e) altogether, P 1 col (e) should reach the value 1 first, then P 2 col (e), and then P 3 col (e). A collision should only happen after this progression. However this progression can be interrupted by a change of velocity of one of the vehicles. If no collision is ever predicted, P col (e) should remain at (0, 0, 0) for all events.

The prediction progress can be stated "once a collision starts being predicted, the prediction will eventually progress until a collision or a change of velocity occur". This is a response property, in which if no collision is predicted, P col (e) should remain at (0, 0, 0) as default behavior, however it adopts a progressing behavior in reaction to a collision starting to be predicted. This property expresses that the only valid reason for the prediction not to progress once it started, is a change of velocity. This property is the intersection of a safety property in that it waits for the collision to be predicted, and a liveness property in that is ensures the order of the progression up to a collision or a change of velocity.

Once again this temporal property is verified using an observer automaton, which will reveal every evolution of the prediction that goes against the expected progression and no change of velocity was observed.

IV. EXPERIMENTS & RESULTS

A. Scenario description and trace details

Our simulation scenario aims at checking the behavior of cars at a four-way crossroad and validating the Time-to-Collision (TTC) estimated by CMCDOT. For simplification, we bound our simulation with a rule stating that at any given moment in time, a maximum of one simulated non-ego vehicle is present on the crossroad. As shown in Figure 6, the egovehicle (white) and non-ego vehicle (red) both start at the same time from a given location in the Carla environment. A PID controller maintains constant velocity for both vehicles and the steering angle is fixed. For simplicity, we only consider the case when both vehicles collide at a 90-degree angle. A scenario ends when the cars collide or the egovehicle completes its track, passing the intersection without any collision. For our study, a total of 800 traces have been considered to generate the results reported here.

To simulate different cases, we rely on the random generation of parameters defining: the non-ego vehicle class (cars or motorcycles), initial positions and initial speeds of the ego and non-ego vehicles. The test cases are then run, and their results (perception output of CMCDOT, as in Fig. 4) are stored with a frequency of 10 Hz alongside the parameter sets. The analysis of these datasets allows us to accurately measure the efficiency of our perception and estimation solution.

The strong advantage of this approach is the ease with which a large number of simulated scenarios can be generated, ran, and analyzed.

B. Validation Results

To assess the validity of CMCDOT's collision prediction, the verification verdicts are analyzed using KPI in order to produce grades as quantitative results. The KPI need metrics, ideal grades, and evaluation functions to give grades to traces w.r.t the metrics and the ideal values. For every property P , each event e in a trace T receives a grade G P (e) ∈ [0, 1]. The ideal grade is 1 and G P (e) = 1 if e satisfies P . Each property is given metrics to determine the severity of the violations. Upon violation, G P (e) is reduced by a penalty factor. The grade of a trace is the average of the grades of all its events.

The coherence property verifies the order relation within the P col (e) triple for every event e in a trace. When the order is violated (P i col (e) > P j col (e)), the penalty for coherence is P i col (e) -P j col (e) with i, j ∈ {1, 2, 3} and i < j. Figure 7 shows the grades for the coherence property. 95% of the traces have only coherent predictions. In the remaining traces, none have contradicting predictions. The incoherences that are identified by this property are events similar to a situation with P 1 col (e) = 1 and P 2 col (e) = 0.99. Though the order relation is violated, the impact is minimal. Globally CMCDOT is coherent in its predictions.

For the safe prediction property, a bad prediction occurring on an event three seconds before a collision has time to be corrected on the following events but a bad prediction occurring during the last second is dangerous for driving. The metrics take this severity scale into account. When an event e violates the safe prediction property, the safe prediction grade Figure 8 shows the corresponding grades. The high grades represent 85% of traces. The grades that are in [0.9, 1) come from executions where the predictions are accurate but one or two events late. The other grades are due to the fact that we are stressing CMCDOT with situations where the vehicles nearly miss or barely touch. The traces with low grades correspond to cases where the collision is predicted but the trace did not indicate a collision, thus giving a bad grade to all the events within three seconds of a collision. This revealed that the bounding boxes that are used in the simulator to determine collisions did not completely fit the vehicle. There were also some very particular scenarios where the vehicles were so close that CMCDOT took longer than usual to predict collisions. In these situations, a human driver would never let vehicles be so close.

Based on these results, we can conclude that CMCDOT satisfies or almost satisfies the safe prediction property 85% of the time when confronted to corner cases.

The verdict of the prediction progress property lists all the events where the prediction evolved against the intended progression. The penalty for this property is proportional to Fig. 9: Prediction progress results: The prediction evolved as expected in 80% of the traces. In some traces CMCDOT hesitated on the progression of the predictions. how severe the reverse progression is.

Figure 9 shows that for 80% of the traces the predictions progress as intended. In the scenarios there are no changes in the velocities, so the expected behavior is for the predictions to always progress towards a collision. In 80% of the traces, the prediction progresses as expected. The worst grade begins at 0.9, indicating that the traces where the prediction evolves in the reverse order contain punctual fluctuations where CM-CDOT hesitates on some predictions. The impact of these hesitations is not significant in the overall evolution of the progression when a collision approaches.

V. CONCLUSIONS

We presented a methodology for validating perception systems based on a combination of simulation, formal verification on simulation traces, and statistical analysis of the verification results according to KPIs associated to each property of interest. We instantiated this methodology for validating the collision risk prediction feature of CMCDOT for a set of relevant scenarios involving collisions between vehicles, but also corner cases (near misses or bare touches). Our validation framework, which integrates the CARLA simulator, the CADP verification toolbox, and the RStudio statistical computing environment, enabled us to assess the accurate behaviour of CMCDOT w.r.t. collision risk prediction.

As future work, we plan to take into account the changes of vehicle velocities (variable speeds and changes in direction). Our methodology can be readily leveraged to achieve this, by first pre-cutting the traces into intervals of constant/transient velocities, and then applying the analysis as discussed in Section III. We also plan to consider some more frequent and realistic urban situations, such as stopping behind another vehicle at a stop light or driving for hours to see if CMCDOT still performs well after long executions.

Fig. 1 :

 1 Fig. 1: (Top) Real environment around the car and as observed using a 64 layered lidar. (Bottom) Representation of the environment as dense probabilistic occupancy grid output from CMCDOT framework. Colors represents different state of each cell in the grid: occupied static (blue), occupied dynamic (green), empty (black), unknown area (red).

Fig. 2 :

 2 Fig.2:The CMCDOT represents the environment as a grid, to whose cells are associated static, dynamic, empty and unknown coefficients. Weighted particles, which sample the velocity space, are then associated to the dynamic part.

Fig. 3 :

 3 Fig. 3: Collision risk estimation of a specific cell. Both the future cell and the ego-vehicle positions are predicted according to their estimated velocity. The risk of every cell is used to integrate over time the total collision risk.

Fig. 4 :

 4 Fig. 4: Simulated scenario in Carla (top) and output of CMCDOT (bottom).

Fig. 6 :

 6 Fig. 6: Intersection Crossing scenario and CMCDOT grid.

Fig. 7 :

 7 Fig. 7: Coherence results: 95% of the traces have only coherent predictions. 5% of the traces are slightly less coherent. The minimal grade is 0.95.

Fig. 8 :

 8 Fig. 8: Safe prediction results: 40% of the traces have safe predictions, 45% generally have safe predictions with the exception of a few events, 15% of the traces have low grades.

ACKNOWLEDGMENT

This work has also been conducted within the ENABLE-S3 project of the ECSEL joint undertaking under grant agreement NO 692455. This joint undertaking receives support from the European Union's Horizon 2020 research and innovation program and Austria, Denmark, Germany, Finland, Czech Republic, Italy, Spain, Portugal, Poland, Ireland, Belgium, France, Netherlands, United Kingdom, Slovakia, Norway.