# On the nature of compact stars determined by gravitational waves, radio-
astronomy, x-ray emission and nuclear physics

H. Güven  Université Paris-Saclay, CNRS/IN2P3, IJCLab, 91405 Orsay, France
Physics Department, Yildiz Technical University, 34220 Esenler, Istanbul,
Turkey  J. Margueron  Univ Lyon, Univ Claude Bernard Lyon 1, CNRS/IN2P3, IP2I
Lyon, UMR 5822, F-69622, Villeurbanne, France  K. Bozkurt  Physics Department,
Yildiz Technical University, 34220 Esenler, Istanbul, Turkey  Université
Paris-Saclay, CNRS/IN2P3, IJCLab, 91405 Orsay, France  E. Khan  Université
Paris-Saclay, CNRS/IN2P3, IJCLab, 91405 Orsay, France  Institut Universitaire
de France (IUF)

###### Abstract

We investigate the question of the nature of compact stars, considering they
may be neutron stars or hybrid stars containing a quark core, within the
present constraints given by gravitational waves, radio-astronomy, X-ray
emissions from millisecond pulsars and nuclear physics. A Bayesian framework
is used to combine together all these constraints and to predict tidal
deformabilities and radii for a 1.4 M⊙ compact star. We find that present
gravitation wave and radio-astronomy data favors asy-stiff EoS compatible with
nuclear physics and that GW170817 waveform is best described for binary hybrid
stars. In addition, this data favors stiff quark matter, independently of the
nuclear EoS. Combining this result with constraints from X-ray observation
supports the existence of canonical $1.4$ M⊙ mass hybrid star, with a radius
predicted to be $R_{1.4}=12.02(8)$ km.

Neutron Stars (NSs), and most generally compact stars (CSs), are forefront
laboratories to explore the properties of extreme matter and consequently the
strong interaction. The guidance of experimental and observational data are of
prime importance, especially because the theory of the strong interaction, the
quantum chromo-dynamics (QCD), could not be simply applied in the regime
explored by CSs. One of the most important question in this field is to
understand how the strong interaction evolves as function of the density and
how quark matter emerges from hadrons Alford  _et al._ (2008); Anglani  _et
al._ (2014), if it ever does for densities relevant for stable CSs. Therefore,
one should consider two types of CS: NS, with no phase transition in the core,
and hybrid stars (HS), with phase transition, towards quark matter, in the
core. Note that the existence of strange quark stars is not considered in our
analysis since we assume that matter is ruled by a single equation of state.
In the present paper, we investigate the onset of a first order phase
transition (FOPT) producing the largest correction to the global properties of
CSs. It should be noted that CSs observations are also complementary to Earth
experiments, such as for instance heavy ion collision Collaboration (2019),
since they explore very isospin asymmetric and dense matter.

Figure 1: Mass-radius (left) and mass-tidal deformability (right)
representations for SLy5 Chabanat  _et al._ (1998) (top) and PKDD Long  _et
al._ (2004) (bottom). The observational contours are related to the analysis
of: J0348+0432 Antoniadis  _et al._ (2013), J0030+0451 Miller  _et al._
(2019), J0740+6620 Miller  _et al._ (2021), and GW170817 De  _et al._ (2018).
The lines represent predictions of a few selected EoS: purely nucleonic EoS
for NS (black and solid lines), and the others (color lines) show examples of
FOPT built upon nucleonic EoS considering the maximally stiff case ($c_{s}=c$)
for the quark phase. The FOPT parameters $p_{\mathrm{PT}}$ (MeV fm-3) and
$\mu^{*}$ (MeV) are given in the inset for HS.

Over the last decade, the observation of CSs has entered into the era of
precision measurements, which provides unprecedented possibilities for
constraining the EoS. Among these constraints, the most impactful ones are
shown in Fig. 1: The detection of massive NSs by radio astronomers has pushed
up the maximum mass limit, which is presently around 2M⊙ Demorest  _et al._
(2010); Arzoumanian  _et al._ (2018); Antoniadis  _et al._ (2013); Cromartie
_et al._ (2019); Linares  _et al._ (2018); Özel and Freire (2016). As a
typical example, the maximum mass limit from J0348+0432 Antoniadis  _et al._
(2013) is shown in Fig. 1. In addition to the masses, the radii of a few
millisecond pulsars (PSR J0030+0451 Miller  _et al._ (2019); Riley  _et al._
(2019) and PSR-J0740+6620 Miller  _et al._ (2021); Riley  _et al._ (2021))
have recently been extracted from X-rays observations, using NICER observatory
Gendreau and Arzoumanian (2017). Finally, the event GW170817 Abbott  _et al._
(2017, 2018, 2019), produced by the merger of two CSs, allowed the first
estimation of the effective tidal deformability $\tilde{\Lambda}$ for dense
matter Flanagan and Hinderer (2008); Hinderer (2008); Damour and Nagar (2009),
which is shown in the right panels in Fig. 1.

The link between the observation of CSs and the strong interaction is
performed through the equation of state (EoS), i.e., the pressure $p$ versus
the energy density $\varepsilon$. By solving the Tolman-Oppenheimer-Volkoff
(TOV) equations for spherical non-rotating and non-magnetized stellar objects
Tolman (1939); Oppenheimer and Volkoff (1939), the EoS can be transformed into
observational CS properties, e.g., a relation between masses and radii. For
such kind of direct comparison, it is important to accurately estimate
systematical uncertainties. This can be performed for instance by solving the
TOV equations for a large set of EoSs compatible with the current knowledge.
In this way, the model uncertainties in the EoS can be turned into a contour
in the macroscopic properties, e.g., masses, radii and tidal deformabilities,
shown in Fig. 1. The tidal deformability is well correlated to the compactness
($\beta=M/R$) of the compact star Abbott  _et al._ (2017), and together with
the measure of the mass extracted from the gravitational waveform, it allows
to infer the value of the radius Tews  _et al._ (2019); Abbott  _et al._
(2019). In some analyses, it is the radius prediction inferred from the tidal
deformability, assuming agnostic EoS modeling or universal relations, which is
directly used to select EoS models Xie and Li (2021).

A few examples of NS and HS EoSs are shown in Fig. 1, comparing predictions
based on the nucleonic SLy5 Chabanat  _et al._ (1998) (top panel) and PKDD
Long  _et al._ (2004) (bottom panel) EoSs. We employ in this study these two
typical nucleonic EoS which differ by the density dependence of the symmetry
energy: we consider an isospin soft model, hereafter called asy-soft,
represented by SLy5 Chabanat  _et al._ (1998) nuclear model and an isospin
stiff model, called asy-stiff, represented by PKDD Long  _et al._ (2004)
relativistic Lagrangian. The choice of reducing the nuclear EoS to only two
typical ones is also performed by other authors, see for instance Ref. Han and
Steiner (2019). The SLy5 model is compatible with recent chiral EFT
predictions with a low value of the slope of the symmetry energy
($L_{\textrm{sym}}=48.3$ MeV) Drischler  _et al._ (2019); Somasundaram  _et
al._ (2021), as well as with the analysis of the PREX-II experiment including
also binding energies, charge radii and dipole polarisabilities in a set of
finite nuclei Reinhard  _et al._ (2021). The asy-stiff PKDD model
($L_{\textrm{sym}}=79.5$ MeV) is compatible with another analysis of PREX-II
experiment Reed  _et al._ (2021).

Note that all the EoSs considered here satisfy the current experimental,
theoretical and observational constraints that we detail in this study. Twin
stars, i.e., two stars with same mass but different radii, may exist Li  _et
al._ (2023) but, in the present study, they are not considered since we impose
a one-to-one correspondence between masses and radii.

By showing models and observational contours, Fig. 1 illustrates that it is
difficult to find equations of state which reproduce equally well the contours
from NICER observatory (left panels) and from GW170817 (right panel). For
instance PKDD is out of the GW170817 contour but it is in very good agreement
with the two other contours from NICER observatory. The opposite is observed
for the other models which reproduce well GW170817. This tension has already
been observed in previous studies, see for instance Refs. Capano  _et al._
(2020); Güven  _et al._ (2020); Pang  _et al._ (2021); Dinh Thi  _et al._
(2021). Because of this tension in the data, we adopt the common strategy: we
employ GW170817 to select EoSs, by comparing different kind of binary systems:
binary neutron stars (BNS), binary hybrid stars (BHS) and neutron star hybrid
star (NSHS). This allows to determine whether one of these system is favored,
in a Bayesian framework, by the present data. In a second step, we combine the
prediction of these modelings together with NICER contour to infer the radius
$R_{1.4}$ of a $1.4$M⊙ compact star.

In order to describe hybrid stars, a first order phase transition is built on
top of nucleonic EoSs. The quark phase is described by the constant sound
speed approach inspired from the MIT bag model Chodos  _et al._ (1974). It
requires three quantities: the pressure $p_{\mathrm{PT}}$ at the entrance of
the phase transition, the shift in energy density, reflecting the latent heat
$\Delta\varepsilon_{\mathrm{PT}}$, and finally, the sound speed $c_{s}$ in
quark matter assumed to be constant. We have Zdunik, J. L. and Haensel, P.
(2013); Alford  _et al._ (2013); Chamel, N.  _et al._ (2013):

$\varepsilon(p)=\begin{cases}\varepsilon_{\mathrm{NM}}(p)&p<p_{\mathrm{PT}}\\\
\varepsilon_{\mathrm{NM}}(p_{\mathrm{PT}})+\Delta\varepsilon_{\mathrm{PT}}+(p-p_{\mathrm{PT}})/\alpha&p\geq
p_{\mathrm{PT}}\end{cases}$ (1)

where $\varepsilon_{\mathrm{NM}}$ is the nucleonic matter energy density, and
$\alpha$ is related to the sound speed as $\alpha=(c_{s}/c)^{2}$, where $c$ is
the speed of light in the vacuum. In the following, we use units where $c=1$.
A similar approach has recently been employed in Han and Steiner (2019); Xie
and Li (2021); Somasundaram and Margueron (2022); Somasundaram  _et al._
(2023), leading to the possible existence of a third branch of compact stars
Alford and Sedrakian (2017). In our study, we use these modeling to explore
the nature of CS favored by the present data.

Figure 2: Posterior PDF function of $\tilde{\Lambda}$ obtained for BNS, BHS
and NSHS configurations. The data shown in the graph is extracted from Ref. De
_et al._ (2018). The different line styles correspond to different sound
speeds $c_{s}^{2}=1/3$, $2/3$ and $1$. The two vertical bands represent the
tidal deformabilities obtained for the purely nucleonic EoSs, see the panel
associated to binary configurations. Figure 3: Same as Fig. 2 but as function
of the radius $R_{1.4}$. The data shown in the graphs are deduced from the
analysis of PSR J0030+0451 by Miller et al. Miller  _et al._ (2019) where the
PDF is sliced for masses between 1.35 and 1.45M⊙. The two vertical bands
represent the radii obtained from the purely nucleonic EoSs, see the panel
associated to binary configurations.

In practice we use the parameters $p_{\mathrm{PT}}$ and $\mu^{*}$, which
represents the chemical potential of quark matter at zero pressure, and from
which the latent heat $\Delta\varepsilon_{\mathrm{PT}}$ can be recovered as

$\Delta\varepsilon_{\mathrm{PT}}=\frac{p_{\mathrm{PT}}}{\alpha}\left[\frac{1+\alpha}{\left[\frac{\mu_{\mathrm{NM}}(p_{\mathrm{PT}})}{\mu^{*}}\right]^{\frac{1+\alpha}{\alpha}}-1}+1\right]-\varepsilon_{\mathrm{NM}}(p_{\mathrm{PT}})\,.$
(2)

We consider the following ranges for the model parameters (priors):
$\mu^{*}=925\pm 75$ MeV, suggested from color-superconducting quark matter
calculations Agrawal (2010); the sound speed parameter $\alpha$ is fixed to
three possible values: $\alpha=1/3$ (conformal limit), $2/3$ and $1$ (causal
limit); and finally, $p_{\mathrm{PT}}$ is an unconstrained parameter with
unknown boundaries. Here, we vary $p_{\mathrm{PT}}$ from 6 to 500 MeV fm-3,
guided by the vanishing of the posterior distribution.

It should be noted that in the present study, quark matter may appear already
around (and above) saturation density, since we explore a large space for the
sound speed, ranging between $1/\sqrt{3}$ and 1. While other analyses also
explore a large space (see for instance Ref. Xie and Li (2021)) which predict
quark matter to appear on the average for densities around
1.5$n_{\mathrm{sat}}$, some analyses of quark matter predict its appearance
above $3n_{\mathrm{sat}}$ Pfaff  _et al._ (2022) or above $1.6$M⊙ Parisi  _et
al._ (2021). These predictions may be related to the choice of the sound speed
prior in these analyses.

We employ the Bayesian approach to compare our model predictions, represented
by a set of EoS parameters $\\{a_{i}\\}$ with the present data Steiner (2015).
The probability associated to a given model considering a set of data, the so-
called the posterior probability, is

$P(\\{a_{i}\\}|\textrm{data})\sim P(\textrm{data}|\\{a_{i}\\})\times
P(\\{a_{i}\\}),$ (3)

where $P(\textrm{data}|\\{a_{i}\\})$ is the likelihood function representing
the ability of the model to reproduce a set of measurements and
$P(\\{a_{i}\\})$ is the prior probability, which represents the a-priori
knowledge on the model parameters. We vary the parameters controlling the
FOPT, $\alpha$, $p_{\mathrm{PT}}$ and $\mu^{*}$, which are yet unconstrained
parameters. The likelihood probability entering Eq. (3) is defined as,

$P(\mathrm{data}|\\{a_{i}\\})=w_{\mathrm{filter}}(\\{a_{i}\\})\times
p_{\tilde{\Lambda}}\,,$ (4)

where $w_{\mathrm{filter}}(\\{a_{i}\\})$ is a pass-band type filter which
selects only the viable models with maximum mass larger than 2M⊙ and
$p_{\tilde{\Lambda}}$ expresses the ability of the model to reproduce the
observed probability density function (PDF) for $\tilde{\Lambda}$ deduced from
the GW signal, considering the wave-form analysis from Ref. De  _et al._
(2018). To do so, the effective tidal deformability $\tilde{\Lambda}(q)$ is
averaged over the mass ratio $q$ of the binary system in the range $[0.73,1]$,
see Ref. Güven  _et al._ (2020) for more details.

| EOS | $c_{s}^{2}$ | BHS | NSHS | BNS
---|---|---|---|---|---
asy-soft | SLy5 | 1/3 | $0.00$ | $0.00$ | $0.00$
SLy5 | 2/3 | $0.07$ | $0.04$ | $0.07$
SLy5 | 1 | $0.12$ | $0.08$ | $0.06$
asy-stiff | PKDD | 1/3 | $0.00$ | $0.00$ | $0.00$
PKDD | 2/3 | $\mathbf{0.28}$ | $0.00$ | $0.00$
PKDD | 1 | $\mathbf{0.65}$ | $0.00$ | $0.00$
Table 1: Overlap between the model prediction and the PDF associated to GW170817, as function of the nucleonic EoS, the sound speed in quark matter and the nature of the binary system. The largest overlaps are stressed in bold. | EOS | Configuration | $c_{s}^{2}$ |  $R_{1.4}$ Radius
---|---|---|---|---
|  |  | km |
asy-soft | SLy5 | NS | 2/3 | $12.00(0)$
SLy5 | NS | 1 | $12.00(0)$
SLy5 | HS | 2/3 | $11.86(6)$
SLy5 | HS | 1 | $11.83(6)$
SLy5 | HS or NS | 2/3 | $11.98(9)$
SLy5 | HS or NS | 1 | $11.96(1)$
Average |  |  | $11.94(2)$
asy-stiff | PKDD | HS | 2/3 | $\mathbf{12.06(12)}$
PKDD | HS | 1 | $\mathbf{11.98(11)}$
Average |  |  | $\mathbf{12.02(8)}$
Table 2: Predictions for the $R_{1.4}$ radius constrained by both GW170817 and
NICER observation of PSR J0030+0451, as function of the nature of the CS.

The posterior probability as a function of the effective tidal deformability
$\tilde{\Lambda}$, is shown in Fig. 2 for BNS, BHS and NSHS configurations.
For BNS systems, only asy-soft EoSs overlap the data since asy-stiff models
predict too large tidal deformabilities. NSHS systems are not favored by
either asy-soft or asy-stiff EoS. Finally, BHS systems are preferred by asy-
stiff models, overlapping at best the data, as shown in Tab. 1 where bold
values mark the best overlaps. In addition, it can be remarked that the
overlap is generally optimal for large sound speed, $c_{s}^{2}\gtrsim 2/3$,
implying a stiff quark matter phase. Considering Fig. 2 and Tab. 1, we
conclude that current GW and radio-astronomy observations favors asy-stiff
nucleonic EoS compatible with nuclear physics and a BHS configuration for
GW170817 event.

The same EoSs are employed to predict $R_{1.4}$, as shown in Fig. 3.
Independently of their ability to describe GW170817, the two nucleonic EoS
compatible with nuclear physics have a good overlap with the NICER data for
NSs: they predict radii from $12.00$ km (SLy5) to $13.50$ (PKDD). But when we
condition the model to reproduce GW170817 and radio-astronomy observations,
only PKDD survives in the case of HS. Tab. 2 subsumes the $R_{1.4}$
predictions conditioned by GW170817, radio-astronomy and nuclear physics. We
consider only the cases for which non-zero values are obtained in Tab. 1. The
centroids are weakly dependent on the nucleonic modelling, going from about
11.8 to about 12.1 km. We obtain however that the asy-stiff EoS, favoring the
HS configuration, predicts a radius $R_{1.4}=12.02(8)$ km, shown in bold in
Tab. 2. The asy-soft EoS, which is not favored in Tab. 1, predicts a radius
$R_{1.4}=11.94(2)$ km on average. These two predictions are quite close and
considering moreover their uncertainties, they are not significantly
different. We then find that the radius of a $1.4$M⊙ CS is weakly impacted by
the nucleonic EoS as well as by the nature of CS within the two nucleonic
scenarios that we have investigated. Considering the present observational
data, see Fig. 1 for instance, an uncertainty lower than 100 m in the
theoretical prediction for the CSs radius is yet impossible to resolve.

In conclusion, we have obtained that the cross-constraints from gravitational
wave, radio-astronomy, x-ray observations and nuclear physics favor binary
compact star systems with asy-stiff nucleonic EoS complemented with stiff
quark matter. The neutron star-hybrid star configuration is not favored for
GW170817 event. The present analysis supports the existence of canonical $1.4$
M⊙ mass hybrid star, and illustrates the complementary between nuclear physics
and astrophysics for the understanding of dense matter in CS. Future tight
constraints in the slope of the symmetry energy $L_{\mathrm{sym}}$ will
further constrain the nature of CSs in GW170817, as well as in the future
astrophysical observations, such as for instance binary CS mergers, radio-
astronomy or x-ray emission from millisecond pulsars.

This work is supported by the Scientific and Technological Research Council of
Turkey (TÜBİTAK) under project number MFAG-122F121 and the Yildiz Technical
University under project number FBA-2021-4229. J.M. and E. K. are both
supported by the CNRS/IN2P3 MAC project.

## References

  * Alford  _et al._ (2008) M. G. Alford, A. Schmitt, K. Rajagopal, and T. Schäfer, Rev. Mod. Phys. 80, 1455 (2008).
  * Anglani  _et al._ (2014) R. Anglani, R. Casalbuoni, M. Ciminale, N. Ippolito, R. Gatto, M. Mannarelli, and M. Ruggieri, Rev. Mod. Phys. 86, 509 (2014).
  * Collaboration (2019) T. H. Collaboration, Nat. Phys. 15, 1040 (2019).
  * Chabanat  _et al._ (1998) E. Chabanat, P. Bonche, P. Haensel, J. Meyer, and R. Schaeffer, Nucl. Phys. A 635, 231 (1998), [Erratum: Nucl.Phys.A 643, 441–441 (1998)].
  * Long  _et al._ (2004) W. Long, J. Meng, N. V. Giai, and S.-G. Zhou, Phys. Rev. C 69, 034319 (2004).
  * Antoniadis  _et al._ (2013) J. Antoniadis _et al._ , Science 340, 6131 (2013), arXiv:1304.6875 [astro-ph.HE] .
  * Miller  _et al._ (2019) M. C. Miller, F. K. Lamb, A. J. Dittmann, S. Bogdanov, Z. Arzoumanian, K. C. Gendreau, S. Guillot, A. K. Harding, W. C. G. Ho, J. M. Lattimer, R. M. Ludlam, S. Mahmoodifar, S. M. Morsink, P. S. Ray, T. E. Strohmayer, K. S. Wood, T. Enoto, R. Foster, T. Okajima, G. Prigozhin, and Y. Soong, The Astrophysical Journal Letters 887, L24 (2019).
  * Miller  _et al._ (2021) M. C. Miller, F. K. Lamb, A. J. Dittmann, S. Bogdanov, Z. Arzoumanian, K. C. Gendreau, S. Guillot, W. C. G. Ho, J. M. Lattimer, M. Loewenstein, S. M. Morsink, P. S. Ray, M. T. Wolff, C. L. Baker, T. Cazeau, S. Manthripragada, C. B. Markwardt, T. Okajima, S. Pollard, I. Cognard, H. T. Cromartie, E. Fonseca, L. Guillemot, M. Kerr, A. Parthasarathy, T. T. Pennucci, S. Ransom, and I. Stairs, The Astrophysical Journal Letters 918, L28 (2021).
  * De  _et al._ (2018) S. De, D. Finstad, J. M. Lattimer, D. A. Brown, E. Berger, and C. M. Biwer, Phys. Rev. Lett. 121, 091102 (2018).
  * Demorest  _et al._ (2010) P. Demorest, T. Pennucci, S. Ransom, M. Roberts, and J. Hessels, Nature 467, 1081 (2010), arXiv:1010.5788 [astro-ph.HE] .
  * Arzoumanian  _et al._ (2018) Z. Arzoumanian _et al._ (NANOGrav), Astrophys. J. Suppl. 235, 37 (2018), arXiv:1801.01837 [astro-ph.HE] .
  * Cromartie  _et al._ (2019) H. T. Cromartie _et al._ , Nature Astron. 4, 72 (2019), arXiv:1904.06759 [astro-ph.HE] .
  * Linares  _et al._ (2018) M. Linares, T. Shahbaz, and J. Casares, Astrophys. J. 859, 54 (2018), arXiv:1805.08799 [astro-ph.HE] .
  * Özel and Freire (2016) F. Özel and P. Freire, Annual Review of Astronomy and Astrophysics 54, 401 (2016), https://doi.org/10.1146/annurev-astro-081915-023322 .
  * Riley  _et al._ (2019) T. E. Riley _et al._ , Astrophys. J. Lett. 887, L21 (2019), arXiv:1912.05702 [astro-ph.HE] .
  * Riley  _et al._ (2021) T. E. Riley _et al._ , Astrophys. J. Lett. 918, L27 (2021), arXiv:2105.06980 [astro-ph.HE] .
  * Gendreau and Arzoumanian (2017) K. Gendreau and Z. Arzoumanian, Nature Astronomy 1, 895 (2017).
  * Abbott  _et al._ (2017) B. P. Abbott, R. Abbott, T. D. Abbott, _et al._ (LIGO Scientific Collaboration and Virgo Collaboration), Phys. Rev. Lett. 119, 161101 (2017), arXiv:1710.05832 [gr-qc] .
  * Abbott  _et al._ (2018) B. P. Abbott, R. Abbott, T. D. Abbott, _et al._ (LIGO Scientific Collaboration and Virgo Collaboration), Phys. Rev. Lett. 121, 161101 (2018).
  * Abbott  _et al._ (2019) B. P. Abbott, R. Abbott, T. D. Abbott, _et al._ (LIGO Scientific Collaboration and Virgo Collaboration), Phys. Rev. X 9, 011001 (2019).
  * Flanagan and Hinderer (2008) E. E. Flanagan and T. Hinderer, Physical Review D 77 (2008), 10.1103/PhysRevD.77.021502.
  * Hinderer (2008) T. Hinderer, The Astrophysical Journal 677, 1216 (2008).
  * Damour and Nagar (2009) T. Damour and A. Nagar, Physical Review D 80 (2009), 10.1103/PhysRevD.80.084035.
  * Tolman (1939) R. C. Tolman, Phys. Rev. 55, 364 (1939).
  * Oppenheimer and Volkoff (1939) J. R. Oppenheimer and G. M. Volkoff, Phys. Rev. 55, 374 (1939).
  * Tews  _et al._ (2019) I. Tews, J. Margueron, and S. Reddy, European Journal of Physics A 55, 97 (2019).
  * Xie and Li (2021) W.-J. Xie and B.-A. Li, Phys. Rev. C 103, 035802 (2021).
  * Han and Steiner (2019) S. Han and A. W. Steiner, Phys. Rev. D 99, 083014 (2019).
  * Drischler  _et al._ (2019) C. Drischler, K. Hebeler, and A. Schwenk, Phys. Rev. Lett. 122, 042501 (2019).
  * Somasundaram  _et al._ (2021) R. Somasundaram, C. Drischler, I. Tews, and J. Margueron, Phys. Rev. C 103, 045803 (2021).
  * Reinhard  _et al._ (2021) P.-G. Reinhard, X. Roca-Maza, and W. Nazarewicz, Phys. Rev. Lett. 127, 232501 (2021), arXiv:2105.15050 [nucl-th] .
  * Reed  _et al._ (2021) B. T. Reed, F. J. Fattoyev, C. J. Horowitz, and J. Piekarewicz, Phys. Rev. Lett. 126, 172503 (2021), arXiv:2101.03193 [nucl-th] .
  * Li  _et al._ (2023) J. J. Li, A. Sedrakian, and M. Alford, Phys. Rev. D 107, 023018 (2023).
  * Capano  _et al._ (2020) C. D. Capano, I. Tews, S. M. Brown, B. Margalit, S. De, S. Kumar, D. A. Brown, B. Krishnan, and S. Reddy, Nature Astron. 4, 625 (2020), arXiv:1908.10352 [astro-ph.HE] .
  * Güven  _et al._ (2020) H. Güven, K. Bozkurt, E. Khan, and J. Margueron, Phys. Rev. C 102, 015805 (2020), arXiv:2001.10259 [nucl-th] .
  * Pang  _et al._ (2021) P. T. H. Pang, I. Tews, M. W. Coughlin, M. Bulla, C. V. D. Broeck, and T. Dietrich, The Astrophysical Journal 922, 14 (2021).
  * Dinh Thi  _et al._ (2021) H. Dinh Thi, C. Mondal, and F. Gulminelli, Universe 7 (2021), 10.3390/universe7100373.
  * Chodos  _et al._ (1974) A. Chodos, R. L. Jaffe, K. Johnson, C. B. Thorn, and V. F. Weisskopf, Phys. Rev. D 9, 3471 (1974).
  * Zdunik, J. L. and Haensel, P. (2013) Zdunik, J. L. and Haensel, P., A&A 551, A61 (2013).
  * Alford  _et al._ (2013) M. G. Alford, S. Han, and M. Prakash, Phys. Rev. D 88, 083013 (2013), arXiv:1302.4732 [astro-ph.SR] .
  * Chamel, N.  _et al._ (2013) Chamel, N., Fantina, A. F., Pearson, J. M., and Goriely, S., A&A 553, A22 (2013).
  * Somasundaram and Margueron (2022) R. Somasundaram and J. Margueron, EPL 138, 14002 (2022), arXiv:2104.13612 [astro-ph.HE] .
  * Somasundaram  _et al._ (2023) R. Somasundaram, I. Tews, and J. Margueron, Phys. Rev. C 107, 025801 (2023), arXiv:2112.08157 [nucl-th] .
  * Alford and Sedrakian (2017) M. Alford and A. Sedrakian, Phys. Rev. Lett. 119, 161104 (2017).
  * Agrawal (2010) B. K. Agrawal, Phys. Rev. D 81, 023009 (2010).
  * Pfaff  _et al._ (2022) A. Pfaff, H. Hansen, and F. Gulminelli, Phys. Rev. C 105, 035802 (2022).
  * Parisi  _et al._ (2021) A. Parisi, C. V. Flores, C. H. Lenzi, C.-S. Chen, and G. Lugones, Journal of Cosmology and Astroparticle Physics 2021, 042 (2021).
  * Steiner (2015) A. W. Steiner, Journal of Physics G: Nuclear and Particle Physics 42, 034004 (2015).


# ADAPS: Autonomous Driving Via Principled Simulations

Weizi Li1, David Wolinski1, and Ming C. Lin1,2 1W. Li, D. Wolinski, M. Lin are
with the Department of Computer Science, University of North Carolina at
Chapel Hill, NC, USA<EMAIL_ADDRESS>Lin is now with the
Department of Computer Science, University of Maryland at College Park, MD,
USA<EMAIL_ADDRESS>
###### Abstract

Autonomous driving has gained significant advancements in recent years.
However, obtaining a robust control policy for driving remains challenging as
it requires training data from a variety of scenarios, including rare
situations (e.g., accidents), an effective policy architecture, and an
efficient learning mechanism. We propose ADAPS for producing robust control
policies for autonomous vehicles. ADAPS consists of two simulation platforms
in generating and analyzing accidents to automatically produce labeled
training data, and a memory-enabled hierarchical control policy. Additionally,
ADAPS offers a more efficient online learning mechanism that reduces the
number of iterations required in learning compared to existing methods such as
DAGGER [1]. We present both theoretical and experimental results. The latter
are produced in simulated environments, where qualitative and quantitative
results are generated to demonstrate the benefits of ADAPS.

##  I Introduction

Autonomous driving consists of many complex sub-tasks that consider the
dynamics of an environment and often lack accurate definitions of various
driving behaviors. These characteristics lead to conventional control methods
to suffer subpar performance on the task [2, 3]. However, driving and many
other tasks can be easily demonstrated by human experts. This observation
inspires imitation learning, which leverages expert demonstrations to
synthesize a controller.

While there are many advantages of using imitation learning, it also has
drawbacks. For autonomous driving, the most critical one is covariate shift,
meaning the training and test distributions are different. This could lead
autonomous vehicles (AVs) to accidents since a learned policy may fail to
respond to unseen scenarios including those dangerous situations that do not
occur often.

In order to mitigate this issue, the training dataset needs to be augmented
with more expert demonstrations covering a wide spectrum of driving
scenarios—especially ones of significant safety threats to the passengers—so
that a policy can learn how to recover from its own mistakes. This is
emphasized by Pomerleau [4], who synthesized a neural network based controller
for AVs: “the network must not solely be shown examples of accurate driving,
but also how to recover (i.e. return to the road center) once a mistake has
been made.”

Although critical, obtaining recovery data from accidents in the physical
world is impractical due to the high cost of a vehicle and potential injuries
to both passengers and pedestrians. In addition, even one managed to collect
accident data, human experts are usually needed to label them, which is
inefficient and may subject to judgmental errors [5].

These difficulties naturally lead us to the virtual world, where accidents can
be simulated and analyzed [6]. We have developed ADAPS (Autonomous Driving Via
Principled Simulations) to achieve this goal. ADAPS consists of two simulation
platforms and a memory-enabled hierarchical control policy based on deep
neural networks (DNNs). The first simulation platform, referred to as
SimLearner, runs in a 3D environment and is used to test a learned policy,
simulate accidents, and collect training data. The second simulation platform,
referred to as SimExpert, acts in a 2D environment and serves as the “expert”
to analyze and resolve an accident via principled simulations that can plan
alternative safe trajectories for a vehicle by taking its physical, kinematic,
and geometric constraints into account.

Furthermore, ADAPS represents a more efficient online learning mechanism than
existing methods such as DAGGER [1]. This is useful consider learning to drive
requires iterative testing and update of a control policy. Ideally, we want to
obtain a robust policy using minimal iterations since one iteration
corresponds to one incident. This would require the generation of training
data at each iteration to be accurate, efficient, and sufficient so that a
policy can gain a large improvement going into the next iteration. ADAPS can
assist to achieve this goal.

The main contributions of this research are specifically: (1) The accidents
generated in SimLearner will be analyzed by SimExpert to produce alternative
safe trajectories. (2) These trajectories will be automatically processed to
generate a large number of annotated and segmented training data. Because
SimExpert is parameterized and has taken the physical, kinematic, and
geometric constraints of a vehicle into account (i.e., principled), the
resulting training examples are more heterogeneous than data collected via
running a learned policy multiple times and are more effective than data
collected through random sampling. (3) We present both theoretical and
experimental results to demonstrate that ADAPS is an efficient online learning
mechanism.

The Appendix, which contains supporting material, can be found at
http://gamma.cs.unc.edu/ADAPS/.

##  II Related Work

We sample previous studies that are related to each aspect of our framework
and discuss the differences within.

Autonomous Driving. Among various methods to plan and control an AV [7], we
focus on end-to-end imitation learning as it can avoid manually designed
features and lead to a more compact policy compared to conventional mediation
perception approaches [8]. The early studies done by Pomerleau [4] and LeCun
et al. [9] have shown that neural networks can be used for an AV to achieve
lane-following and off-road obstacle avoidance. Due to the advancements of
deep neural networks (DNNs), a number of studies have emerged [10, 11, 12,
13]. While significant improvements have been made, these results mainly
inherit normal driving conditions and restrict a vehicle to the lane-following
behavior [13]. Our policy, in contrast, learns from accidents and enables a
vehicle to achieve on-road collision avoidance with both static and dynamic
obstacles.

Hierarchical Control Policy. There have been many efforts in constructing a
hierarchical policy to control an agent at different stages of a task [14].
Example studies include the options framework [15] and transferable motor
skills [16]. When combined with DNNs, the hierarchical approach has been
adopted for virtual characters to learn locomotion tasks [17]. In these
studies, the goal is to discover a hierarchical relationship from complex
sensorimotor behaviors. We apply a hierarchical and memory-enabled policy to
autonomous driving based on multiple DNNs. Our policy enables an AV to
continuously categorize the road condition as safe or dangerous, and execute
corresponding control commands to achieve accident-free driving.

Generative Policy Learning. Using principled simulations to assist learning is
essentially taking a generative model approach. Several studies have adopted
the same philosophy to learn (near-)optimal policy, examples including
function approximations [18], Sparse Sampling [19], and Fitted Value Iteration
[20]. These studies leverage a generative model to stochastically generate
training samples. The emphasize is to simulate the feedback from an
environment instead of the dynamics of an agent assuming the reward function
is known. Our system, on the other hand, does not assume any reward function
of a driving behavior but models the physical, kinematic, and geometric
constraints of a vehicle, and uses simulations to plan their trajectories
w.r.t. environment characteristics. In essence, our method learns from expert
demonstrations rather than self-exploration [21] as of the previous studies.

##  III Preliminaries

Autonomous driving is a sequential prediction and controlled (SPC) task, for
which a system must predict a sequence of control commands based on inputs
that depend on past predicted control commands. Because the control and
prediction processes are intertwined, SPC tasks often encounter covariate
shift, meaning the training and test distributions vary. In this section, we
will first introduce notation and definitions to formulate an SPC task and
then briefly discuss its existing solutions.

###  III-A Notation and Definitions

The problem we consider is a $T$-step control task. Given the observation
$\phi=\phi(s)$ of a state $s$ at each step $t\in[\\![1,T]\\!]$, the goal of a
learner is to find a policy $\pi\in\Pi$ such that its produced action
$a=\pi(\phi)$ will lead to the minimal cost:

$\hat{\pi}=\operatorname*{arg\,min}_{\pi\in\Pi}\sum_{t=1}^{T}C\left(s_{t},a_{t}\right),$
(1)

where $C\left(s,a\right)$ is the expected immediate cost of performing $a$ in
$s$. For many tasks such as driving, we may not know the true value of $C$.
So, we instead minimize the observed surrogate loss $l(\phi,\pi,a^{*})$, which
is assumed to upper bound $C$, based on the approximation of the learner’s
action $a=\pi(\phi)$ to the expert’s action $a^{*}=\pi^{*}(\phi)$. We denote
the distribution of observations at $t$ as $d_{\pi}^{t}$, which is the result
of executing $\pi$ from $1$ to $t-1$. Consequently,
$d_{\pi}=\frac{1}{T}\sum_{t=1}^{T}d_{\pi}^{t}$ is the average distribution of
observations by executing $\pi$ for $T$ steps. Our goal is to solve an SPC
task by obtaining $\hat{\pi}$ that minimizes the observed surrogate loss under
its own induced observations w.r.t. expert’s actions in those observations:

$\hat{\pi}=\operatorname*{arg\,min}_{\pi\in\Pi}\mathbb{E}_{\phi\sim
d_{\pi},a^{*}\sim\pi^{*}(\phi)}\left[l\left(\phi,\pi,a^{*}\right)\right].$ (2)

We further denote $\epsilon=\mathbb{E}_{\phi\sim
d_{\pi^{*}},a^{*}\sim\pi^{*}(\phi)}\left[l\left(\phi,\pi,a^{*}\right)\right]$
as the expected loss under the training distribution induced by the expert’s
policy $\pi^{*}$, and the cost-to-go over $T$ steps of $\hat{\pi}$ as
$J\left(\hat{\pi}\right)$ and of $\pi^{*}$ as $J\left(\pi^{*}\right)$. It has
been shown that by simply treating expert demonstrations as i.i.d. samples the
discrepancy between $J\left(\hat{\pi}\right)$ and $J\left(\pi^{*}\right)$ is
$\mathcal{O}(T^{2}\epsilon)$ [22, 1]. Given the error of a typical supervised
learning is $\mathcal{O}\left(T\epsilon\right)$, this demonstrates the
additional cost due to covariate shift when solving an SPC task via standard
supervised learning111The proofs regarding results
$\mathcal{O}(T^{2}\epsilon)$ and $\mathcal{O}(T\epsilon)$ can be found in
Appendix IX-A..

###  III-B Existing Techniques

Several approaches have been proposed to solve SPC tasks using supervised
learning while keeping the error growing linearly instead of quadratically
with $T$ [22, 1, 23]. Essentially, these methods reduce an SPC task to online
learning. By further leveraging interactions with experts and no-regret
algorithms that have strong guarantees on convex loss functions [24], at each
iteration, these methods train one or multiple policies using standard
supervised learning and improve the trained policies as the iteration
continues.

To illustrate, we denote the best policy at the $i$th iteration (trained using
all observations from the previous $i-1$ iterations) as $\pi_{i}$ and for any
policy $\pi\in\Pi$ we have its expected loss under the observation
distribution induced by $\pi_{i}$ as
$l_{i}\left(\pi\right)=\mathbb{E}_{\phi\sim
d_{\pi_{i}},a^{*}\sim\pi^{*}(\phi)}\left[l_{i}\left(\phi,\pi,a^{*}\right)\right],l_{i}\in\left[0,l_{max}\right]$222In
online learning, the surrogate loss $l$ can be seen as chosen by some
adversary which varies at each iteration.. In addition, we denote the minimal
loss in hindsight after $N\geq i$ iterations as
$\epsilon_{min}=\min_{\pi\in\Pi}\frac{1}{N}\sum_{i=1}^{N}l_{i}(\pi)$ (i.e.,
the training loss after using all observations from $N$ iterations). Then, we
can represent the average regret of this online learning program as
$\epsilon_{regret}=\frac{1}{N}\sum_{i=1}^{N}l_{i}(\pi_{i})-\epsilon_{min}$.
Using DAGGER [1] as an example method, the accumulated error difference
becomes the summation of three terms:

$J\left(\hat{\pi}\right)\leq
T\epsilon_{min}+T\epsilon_{regret}+\mathcal{O}(\frac{f\left(T,l_{max}\right)}{N}),$
(3)

where $f\left(\cdot\right)$ is the function of fixed $T$ and $l_{max}$. As
$N\rightarrow\infty$, the third term tends to $0$ so as the second term if a
no-regret algorithm such as the Follow-the-Leader [25] is used.

The aforementioned approach provides a practical way to solve SPC tasks.
However, it may require many iterations for obtaining a good policy. In
addition, usually human experts or pre-defined controllers are needed for
labeling the generated training data, which could be inefficient or difficult
to generalize. For autonomous driving, we want the iteration number to be
minimal since it directly corresponds to the number of accidents. This
requires the generation of training data being accurate, efficient, and
sufficient.

##  IV ADAPS

In the following, we present theoretical analysis of our framework and
introduce our framework pipeline.

###  IV-A Theoretical Analysis

We have evaluated our approach against existing learning mechanisms such as
DAGGER [1], with our method’s results proving to be more effective.
Specifically, DAGGER [1] assumes that an underlying learning algorithm has
access to a reset model. So, the training examples can be obtained only online
by putting an agent to its initial state distribution and executing a learned
policy, thus achieving “small changes” at each iteration [1, 23, 26, 27]. In
comparison, our method allows a learning algorithm to access a generative
model so that the training examples can be acquired offline by putting an
agent to arbitrary states during the analysis of an accident and letting a
generative model simulate its behavior. This approach results in massive
training data, thus achieving “large changes” of a policy at one iteration.

Additionally, existing techniques such as DAGGER [1] usually incorporate the
demonstrations of a few experts into training. Because of the reset model
assumption and the lack of a diversity requirement on experts, these
demonstrations can be homogeneous. In contrast, using our parameterized model
to retrace and analyze each accident, the number of recovery actions obtained
can be multiple orders of magnitude higher. Subsequently, we can treat the
generated trajectories and the additional data generated based on them
(described in Section VI-B) as running a learned policy to sample independent
expert trajectories at different states, since 1) a policy that is learned
using DNNs can achieve a small training error and 2) our model provides near-
exhaustive coverage of the configuration space of a vehicle. With these
assumptions, we derive the following theorem.

###### Theorem 1

If the surrogate loss $l$ upper bounds the true cost $C$, by collecting $K$
trajectories using ADAPS at each iteration, with probability at least $1-\mu$,
$\mu\in(0,1)$, we have the following guarantee:

$J\left(\hat{\pi}\right)\leq J\left(\bar{\pi}\right)\leq
T\hat{\epsilon}_{min}+T\hat{\epsilon}_{regret}+\mathcal{O}\left(Tl_{max}\sqrt{\frac{\log{\frac{1}{\mu}}}{KN}}\right).$

###### Proof:

See Appendix IX-A3. ∎

Theorem 1 provides a bound for the expected cost-to-go of the best learned
policy $\hat{\pi}$ based on the empirical error of the best policy in $\Pi$
(i.e., $\hat{\epsilon}_{min}$) and the empirical average regret of the learner
(i.e., $\hat{\epsilon}_{regret}$). The second term can be eliminated if a no-
regret algorithm such as Follow-the-Leader [25] is used and the third term
suggests that we need the number of training examples $KN$ to be
$\mathcal{O}\left(T^{2}l^{2}_{max}\log{\frac{1}{\mu}}\right)$ in order to have
a negligible generalization error, which is easily achievable using ADAPS.
Summarizing these changes, we derive the following Corollary.

###### Corollary 1

If $l$ is convex in $\pi$ for any $s$ and it upper bounds $C$, and Follow-the-
Leader is used to select the learned policy, then for any $\epsilon>0$, after
collecting
$\mathcal{O}\left(\frac{T^{2}l^{2}_{max}\log{\frac{1}{\mu}}}{\epsilon^{2}}\right)$
training examples, with probability at least $1-\mu$, $\mu\in(0,1)$, we have
the following guarantee:

$J\left(\hat{\pi}\right)\leq J\left(\bar{\pi}\right)\leq
T\hat{\epsilon}_{min}+\mathcal{O}\left(\epsilon\right).$

###### Proof:

Following Theorem 1 and the aforementioned deduction. ∎

Now we only need the best policy to have a small training error
$\hat{\epsilon}_{min}$. This can be achieved using DNNs since they have rich
representing capabilities.

###  IV-B Framework Pipeline

The pipeline of our framework is the following. First, in SimLearner, we test
a learned policy by letting it control an AV. During the testing, an accident
may occur, in which case the trajectory of the vehicle and the full
specifications of the situation (e.g., positions of obstacles, road
configuration, etc.) are known. Next, we switch to SimExpert and replicate the
specifications of the accident so that we can “solve” the accident (i.e., find
alternative safe trajectories and dangerous zones). After obtaining the
solutions, we then use them to generate additional training data in
SimLearner, which will be combined with previously generated data to update
the policy. Finally, we test the updated policy again.

##  V Policy Learning

In this section, we will detail our control policy by first explaining our
design rationale then formulating our problem and introducing the training
data collection.

Driving is a hierarchical decision process. In its simplest form, a driver
needs to constantly monitor the road condition, decide it is “safe” or
“dangerous”, and make corresponding maneuvers. When designing a control policy
for AVs, we need to consider this hierarchical aspect. In addition, driving is
a temporal behavior. Drivers need reaction time to respond to various road
situations [28, 29]. A Markovian-based control policy will not model this
aspect and instead likely to give a vehicle jerky motions. Consider these
factors, we propose a hierarchical and memory-enabled control policy.

The task we consider is autonomous driving via a single front-facing camera.
Our control policy consists of three modules: Detection, Following, and
Avoidance. The Detection module keeps monitoring road conditions and activates
either Following or Avoidance to produce a steering command. All these modules
are trained via end-to-end imitation learning and share a similar network
specification which is detailed in Appendix IX-B.

###  V-A End-to-end Imitation Learning

The objective of imitation learning is to train a model that behaves or makes
decisions like an expert through demonstrations. The model could be a
classifier or a regresser $\pi$ parameterized by $\mathbf{\theta}_{\pi}$:

$\hat{\theta}=\operatorname*{arg\,min}_{\theta_{\pi}}\sum_{t=1}^{T}\mathcal{F}\left(\pi\left(\phi_{t};\mathbf{\theta_{\pi}}\right),a^{*}_{t}\right),$
(4)

where $\mathcal{F}$ is a distance function.

The end-to-end aspect denotes the mapping from raw observations to
decision/control commands. For our policy, we need one decision module
$\pi_{Detection}$ and two control modules $\pi_{Following}$ and
$\pi_{Avoidance}$. The input for $\pi_{Detection}$ is a sequence of annotated
images while the outputs are binary labels indicating whether a road condition
is dangerous or safe. The inputs for $\pi_{Following}$ and $\pi_{Avoidance}$
are sequences of annotated images while the outputs are steering angles.
Together, these learned policies form a hierarchical control mechanism
enabling an AV to drive safely on roads and avoid obstacles when needed.

###  V-B Training Data Collection

For training Following, inspired by the technique used by Bojarski et al.
[10], we collect images from three front-facing cameras behind the main
windshield: one at the center, one at the left side, and one at the right
side. The image from the center camera is labeled with the exact steering
angle while the images from the other two cameras are labeled with adjusted
steering angles. However, once Following is learned, it only needs images from
the center camera to operate.

For training Avoidance, we rely on SimExpert, which can generate numerous
intermediate collision-free trajectories between the first moment and the last
moment of a potential accident (see Section VI-A). By positioning an AV on
these trajectories, we collect images from the center front-facing camera
along with corresponding steering angles. The training of Detection requires a
more sophisticated mechanism and is the subject of the next section.

##  VI Learning from Accidents

We explain how we analyze an accident in SimExpert and use the generated data
to train the Avoidance and Detection modules of our policy. SimExpert is built
based on the multi-agent simulator WarpDriver [30].

###  VI-A Solving Accidents

When an accident occurs, we know the trajectory of the tested vehicle for the
latest $K$ frames, which we note as a collection of states
$\mathcal{S}=\bigcup_{k\in[\\![1,K]\\!]}\mathbf{s}_{k}$, where each state
$\mathbf{s}_{k}\in\mathbb{R}^{4}$ contains the 2-dimensional position and
velocity vectors of the vehicle. Then, there are three notable states on this
trajectory that we need to track. The first is the earliest state where the
vehicle involved in an accident (is in a collision) $\mathbf{s}_{k_{a}}$ (at
frame $k_{a}$). The second is the last state $\mathbf{s}_{k_{l}}$ (at frame
$k_{l}$) where the expert algorithm can still avoid a collision. The final one
is the first state $\mathbf{s}_{k_{f}}$ (at frame $k_{f}$) where the expert
algorithm perceives the interaction leading to the accident with the other
involved agent, before that accident.

In order to compute these notable states, we briefly recall the high-level
components of WarpDriver [30]. This collision-avoidance algorithm consists of
two parts. The first is the function $p$, which given the current state of an
agent $\mathbf{s}_{k}$ and any prediction point $\mathbf{x}\in\mathbb{R}^{3}$
in 2-dimensional space and time (in this agent’s referential), gives the
probability of that agent’s colliding with any neighbor
$p(\mathbf{s}_{k},\mathbf{x})\in[0,\>1]$. The second part is the solver, which
based on this function, computes the agent’s probability of colliding with
neighbors along its future trajectory starting from a state $\mathbf{s}_{k}$
(i.e., computed for $\mathbf{x}$ spanning the future predicted trajectory of
the agent, we denote this probability $P\left(\mathbf{s}_{k}\right)$), and
then proposes a new velocity to lower this probability. Subsequently, we can
initialize an agent in this algorithm to any state
$\mathbf{s}_{k}\in\mathcal{S}$ and compute a new trajectory consisting of
$\hat{K}$ new states
$\mathcal{\hat{S}}_{k}=\bigcup_{\hat{k}\in[\\![1,\hat{K}]\\!]}\mathbf{\hat{s}}_{\hat{k}}$,
where $\mathbf{\hat{s}}_{1}=\mathbf{s}_{k}$.

Additionally, since $\mathbf{x}=(0,\>0,\>0)$ in space and time in an agent’s
referential represents the agent’s position at the current time (we can use
this point $\mathbf{x}$ with function $p$ to determine if the agent is
currently colliding with anyone), we find $\mathbf{s}_{k_{a}}$ where
$k_{a}=\min(k)$ subject to $k\in[\\![1,K]\\!]$ and
$p(\mathbf{s}_{k},(0,\>0,\>0))>0$. We note that a trajectory
$\mathcal{\hat{S}}_{k}$ produced by the expert algorithm could contain
collisions (accounting for vehicle dynamics) depending on the state
$\mathbf{s}_{k}$ that it was initialized from. We can denote the set of
colliding states along this trajectory as
$coll(\mathcal{\hat{S}}_{k})=\\{\mathbf{\hat{s}}_{\hat{k}}\in\mathcal{\hat{S}}_{k}\>|\>p(\mathbf{\hat{s}}_{\hat{k}},(0,\>0,\>0))>0\\}$.
Then, we can compute $\mathbf{s}_{k_{l}}$ where $k_{l}=max(k)$ subject to
$k\in[\\![1,k_{a}]\\!]$ and $coll(\mathcal{\hat{S}}_{k})=\emptyset$. Finally,
we can compute $\mathbf{s}_{k_{f}}$ with $k_{f}=1+max(k)$ subject to
$k\in[\\![1,k_{l}]\\!]$ and $P(\mathbf{s}_{k})=0$.

Knowing these notable states, we can solve the accident situation by computing
the set of collision-free trajectories
$solve(\mathcal{S})=\\{\mathcal{\hat{S}}_{k}\>|\>k\in[\\![k_{f},k_{l}]\\!]\\}$.
An example can be found in Appendix IX-C. These trajectories can then be used
to generate training examples in SimLearner in order to train the Avoidance
module.

###  VI-B Additional Data Coverage

Figure 1:  Illustration of important points and DANGER/SAFE labels from
Section VI for a vehicle traveling on the right lane of a straight road, with
an obstacle in front. Labels are shown for four points
$\\{\mathbf{l}_{u1},\mathbf{l}_{u2},\mathbf{l}_{u3},\mathbf{l}_{u4}\\}$
illustrating the four possible cases.

The previous step generated collision-free trajectories $solve(\mathcal{S})$
between $\mathbf{s}_{k_{f}}$ and $\mathbf{s}_{k_{l}}$. It is possible to build
on these trajectories if the tested steering algorithm has particular
data/training requirements. Here we detail the data we derive in order to
train the Detection module, where the task is to determine if a situation is
dangerous and tell Avoidance to address it.

To proceed, we essentially generate a number of trajectories parallel to
$\\{\mathbf{s}_{k_{f}},...,\mathbf{s}_{k_{a}}\\}$, and for each position on
them, generate several images for various orientations of the vehicle. These
images are then labeled based on under-steering/over-steering as compared to
the “ideal” trajectories in $solve(\mathcal{S})$. This way, we scan the region
of the road before the accident locus, generating several images (different
vehicle orientations) for each point in that region.

In summary (a thorough version can be found in Appendix IX-D), and as depicted
in Figure 1, at each state $\mathbf{s}_{k}$, we construct a line perpendicular
to the original trajectory. Then on this line, we define three points and a
margin $g=0.5~{}m$. The first point $\mathbf{l}_{i}$ is the furthest (from
$\mathbf{s}_{k}$) intersection between this line and the collision-free
trajectories $solve(\mathcal{S})$. The other two points
$\\{\mathbf{l}_{rl},\mathbf{l}_{rr}\\}$ are the intersections between the
constructed line and the left and right road borders, respectively. From these
points, a generated image at a position $\mathbf{l}_{u}$ along the constructed
line and with a given direction vector has either a DANGER or SAFE label (red
and green ranges in Figure 1) depending on the direction vector being on the
“left” or “right” of the vector resulting from the interpolation of the
velocity vectors of states belonging to nearby collision-free trajectories
(bilinear interpolation if $\mathbf{l}_{u}$ is between two collision-free
trajectories, linear otherwise).

If a point is on the same side of the original trajectory as the collision-
free trajectories ($\mathbf{l}_{u1}$ and $\mathbf{l}_{u2}$ in Figure 1,
$\mathbf{l}_{u1}$ is “outside” but within the margin $g$ of the collision-free
trajectories, $\mathbf{l}_{u2}$ is “inside” the collision-free trajectories),
the label is SAFE on the exterior of the avoidance maneuver, and DANGER
otherwise.

If a point is on the other side of the original trajectory as compared to the
collision-free trajectories ($\mathbf{l}_{u3}$ and $\mathbf{l}_{u4}$ in Figure
1)), inside the road ($\mathbf{l}_{u3}$) the label is always DANGER, while
outside but within the margin $g$ of the road ($\mathbf{l}_{u4}$), the label
is DANGER when directed towards the road, and SAFE otherwise.

##  VII Experiments

We test our framework in three scenarios: a straight road representing a
linear geometry, a curved road representing a non-linear geometry, and an open
ground. The first two scenarios demonstrate on-road situations with a static
obstacle while the last one demonstrates an off-road situation with a dynamic
obstacle. The specifications of our experiments are detailed in Appendix IX-E.

For evaluation, we compare our policy to the “flat policy” that essentially
consists of a single DNN [8, 11, 31, 13]. Usually, this type of policy
contains a few convolutional layers followed by a few dense layers. Although
the specifications may vary, without human intervention, they are mainly
limited to single-lane following [13]. In this work, we select Bojarski et al.
[10] as an example network, as it is one of the most tested control policies.
In the following, we will first demonstrate the effectiveness of our policy
and then qualitatively illustrate the efficiency of our framework.

###  VII-A Control Policy

Figure 2: LEFT and CENTER: the comparisons between our policy $O_{full}$ (TOP)
and Bojarski et al. [10], $B_{full}$ (BOTTOM). $O_{full}$ can steer the AV
away from the obstacle while $B_{full}$ causes collision. RIGHT: the accident
analysis results on the open ground. We show the accident caused by an
adversary vehicle (TOP); then we show after additional training the AV can now
avoid the adversary vehicle (BOTTOM).

####  VII-A1 On-road

We derive our training datasets from straight road with or without an obstacle
and curved road with or without an obstacle. This separation allows us to
train multiple policies and test the effect of learning from accidents using
our policy compared to Bojarski et al. [10]. By progressively increasing the
training datasets, we obtain six policies for evaluation:

  * •

Our own policy: trained with only lane-following data $O_{follow}$;
$O_{follow}$ additionally trained after analyzing one accident on the straight
road $O_{straight}$; and $O_{straight}$ additionally trained after producing
one accident on the curved road $O_{full}$.

  * •

Similarly, for the policy from Bojarski et al. [10]: $B_{follow}$,
$B_{straight}$, and $B_{full}$.

We first evaluate $B_{follow}$ and $O_{follow}$ using both the straight and
curved roads by counting how many laps (out of 50) the AV can finish. As a
result, both policies managed to finish all laps while keeping the vehicle in
the lane. We then test these two policies on the straight road with a static
obstacle added. Both policies result in the vehicle collides into the
obstacle, which is expected since no accident data were used during the
training.

Having the occurred accident, we can now use SimExpert to generate additional
training data to obtain $B_{straight}$333The accident data are only used to
perform a regression task as the policy by Bojarski et al. [10] does not have
a classification module. and $O_{straight}$. As a result, $B_{straight}$
continues to cause collision while $O_{straight}$ avoids the obstacle.
Nevertheless, when testing $O_{straight}$ on the curved road with an obstacle,
accident still occurs because of the corresponding accident data are not yet
included in training.

By further including the accident data from the curved road into training, we
obtain $B_{full}$ and $O_{full}$. $O_{full}$ manages to perform both lane-
following and collision avoidance in all runs. $B_{full}$, on the other hand,
leads the vehicle to drift away from the road.

For the studies involved an obstacle, we uniformly sampled 50 obstacle
positions on a $3~{}m$ line segment that is perpendicular to the direction of
a road and in the same lane as the vehicle. We compute the success rate as how
many times a policy can avoid the obstacle (while stay in the lane) and resume
lane-following afterwards. The results are shown in Table II and example
trajectories are shown in Figure 2 LEFT and CENTER.

| Training Module (Data) | Other Specs
---|---|---
Scenarios | Following (#Images) | Avoidance (#Images) | Detection (#Images) | Total | Data Augmentation | #Safe Trajectories | Road Type | Obstacle
Straight road | 33 642 | 34 516 | 32 538 | 97 854 |  $212$x | 74 | on-road | static
Curved road | 31 419 | 33 624 | 71 859 | 136 855 |  $98$x | 40 | on-road | static
Open ground | 30 000 | 33 741 | 67 102 | 130 843 |  $178$x | 46 | off-road | dynamic

TABLE I: Training Data Summary: Our method can achieve over 200 times more
training examples than DAGGER [1] at one iteration leading to large
improvements of a policy.

####  VII-A2 Off-road

We further test our method on an open ground which involves a dynamic
obstacle. The AV is trained heading towards a green sphere while an adversary
vehicle is scripted to collide with the AV on its default course. The result
showing our policy can steer the AV away from the adversary vehicle and resume
its direction to the sphere target. This can be seen in Figure 2 RIGHT.

| Test Policy and Success Rate (out of 50 runs)
---|---
Scenario | $B_{follow}$ | $O_{follow}$ | $B_{straight}$ | $O_{straight}$ | $B_{full}$ | $O_{full}$
Straight rd. / Curved rd. | 100% | 100% | 100% | 100% | 100% | 100%
Straight rd. + Obst. | 0% | 0% | 0% | 100% | 0% | 100%
Curved rd. + Obst. | 0% | 0% | 0% | 0% | 0% | 100%

TABLE II: Test Results of On-Road Scenarios: Our policies $O_{straight}$ &
$O_{full}$ can lead to robust collision avoidance and lane-following
behaviors.

###  VII-B Algorithm Efficiency

The key to rapid policy improvement is to generate training data accurately,
efficiently, and sufficiently. Using principled simulations covers the first
two criteria, now we demonstrate the third. Compared to the average number of
training data collected by DAGGER [1] at one iteration, our method can achieve
over 200 times more training examples for one iteration444The result is
computed via dividing the total number of training images via our method by
the average number of training data collected using the safe trajectories in
each scenario.. This is shown in Table I.

In Figure 3, we show the visualization results of images collected using our
method and DAGGER [1] within one iteration via progressively increasing the
number of sampled trajectories. Our method generates much more heterogeneous
training data, which when produced in a large quantity can greatly facilitate
the update of a control policy.

Figure 3: The visualization results of collected images using t-SNE [32]. Our
method can generate more heterogeneous training data compared to DAGGER [1] at
one iteration as the sampled trajectories progress.

##  VIII Conclusion

In this work, we have proposed ADAPS, a framework that consists of two
simulation platforms and a control policy. Using ADAPS, one can easily
simulate accidents. Then, ADAPS will automatically retrace each accident,
analyze it, and plan alternative safe trajectories. With the additional
training data generation technique, our method can produce a large number of
heterogeneous training examples compared to existing methods such as DAGGER
[1], thus representing a more efficient learning mechanism. Our hierarchical
and memory-enabled policy offers robust collision avoidance behaviors that
previous policies fail to achieve. We have evaluated our method using multiple
simulated scenarios, in which our method shows a variety of benefits.

There are many future directions. First of all, we would like to combine long-
range vision into ADAPS so that an AV can plan ahead in time. Secondly, the
generation of accidents can be parameterized using knowledge from traffic
engineering studies. Lastly, we would like to combine more sensors and fuse
their inputs so that an AV can navigate in more complicated traffic scenarios
[33].

## Acknowledgment

The authors would like to thank US Army Research Office and UNC Arts & Science
Foundation, and Dr. Feng “Bill” Shi for insightful discussions.

## References

  * [1] S. Ross, G. Gordon, and D. Bagnell, “A reduction of imitation learning and structured prediction to no-regret online learning,” in _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , 2011, pp. 627–635.
  * [2] N. Ratliff, “Learning to search: structured prediction techniques for imitation learning,” Ph.D. dissertation, Carnegie Mellon University, 2009.
  * [3] D. Silver, “Learning preference models for autonomous mobile robots in complex domains,” Ph.D. dissertation, 2010.
  * [4] D. Pomerleau, “ALVINN: An autonomous land vehicle in a neural network,” in _Advances in neural information processing systems_ , 1989, pp. 305–313.
  * [5] S. Ross, N. Melik-Barkhudarov, K. S. Shankar, A. Wendel, D. Dey, J. A. Bagnell, and M. Hebert, “Learning monocular reactive uav control in cluttered natural environments,” in _Robotics and Automation, 2013 IEEE International Conference on_. IEEE, 2013, pp. 1765–1772.
  * [6] Q. Chao, H. Bi, W. Li, T. Mao, Z. Wang, M. C. Lin, and Z. Deng, “A survey on visual traffic simulation: Models, evaluations, and applications in autonomous driving,” _Computer Graphics Fourm_ , 2019.
  * [7] W. Schwarting, J. Alonso-Mora, and D. Rus, “Planning and decision-making for autonomous vehicles,” _Annual Review of Control, Robotics, and Autonomous Systems_ , 2018.
  * [8] C. Chen, A. Seff, A. Kornhauser, and J. Xiao, “Deepdriving: Learning affordance for direct perception in autonomous driving,” in _Computer Vision, 2015 IEEE International Conference on_ , 2015, pp. 2722–2730.
  * [9] Y. LeCun, U. Muller, J. Ben, E. Cosatto, and B. Flepp, “Off-road obstacle avoidance through end-to-end learning,” in _Advances in neural information processing systems_ , 2005, pp. 739–746.
  * [10] M. Bojarski, D. Del Testa, D. Dworakowski, B. Firner, B. Flepp, P. Goyal, L. D. Jackel, M. Monfort, U. Muller, J. Zhang, _et al._ , “End to end learning for self-driving cars,” _arXiv preprint arXiv:1604.07316_ , 2016.
  * [11] H. Xu, Y. Gao, F. Yu, and T. Darrell, “End-to-end learning of driving models from large-scale video datasets,” in _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017, pp. 3530–3538.
  * [12] Y. Pan, C.-A. Cheng, K. Saigol, K. Lee, X. Yan, E. Theodorou, and B. Boots, “Agile off-road autonomous driving using end-to-end deep imitation learning,” in _Robotics: Science and Systems_ , 2018.
  * [13] F. Codevilla, M. Müller, A. Dosovitskiy, A. López, and V. Koltun, “End-to-end driving via conditional imitation learning,” in _Robotics and Automation (ICRA), 2017 IEEE International Conference on_. IEEE, 2017, pp. 746–753.
  * [14] A. G. Barto and S. Mahadevan, “Recent advances in hierarchical reinforcement learning,” _Discrete Event Dynamic Systems_ , vol. 13, no. 4, pp. 341–379, 2003.
  * [15] R. S. Sutton, D. Precup, and S. Singh, “Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning,” _Artificial intelligence_ , vol. 112, no. 1-2, pp. 181–211, 1999.
  * [16] G. Konidaris, S. Kuindersma, R. Grupen, and A. Barto, “Robot learning from demonstration by constructing skill trees,” _The International Journal of Robotics Research_ , vol. 31, no. 3, pp. 360–375, 2012.
  * [17] S. Levine and V. Koltun, “Guided policy search,” in _Proceedings of the 30th International Conference on Machine Learning (ICML)_ , 2013, pp. 1–9.
  * [18] G. J. Gordon, “Stable function approximation in dynamic programming,” in _Machine Learning Proceedings 1995_. Elsevier, 1995, pp. 261–268.
  * [19] M. Kearns, Y. Mansour, and A. Y. Ng, “A sparse sampling algorithm for near-optimal planning in large markov decision processes,” _Machine learning_ , vol. 49, no. 2-3, pp. 193–208, 2002.
  * [20] C. Szepesvári and R. Munos, “Finite time bounds for sampling based fitted value iteration,” in _Proceedings of the 22nd international conference on Machine learning_ , 2005, pp. 880–887.
  * [21] L.-J. Lin, “Self-improving reactive agents based on reinforcement learning, planning and teaching,” _Machine learning_ , vol. 8, no. 3-4, pp. 293–321, 1992.
  * [22] U. Syed and R. E. Schapire, “A reduction from apprenticeship learning to classification,” in _Advances in Neural Information Processing Systems_ , 2010, pp. 2253–2261.
  * [23] H. Daumé, J. Langford, and D. Marcu, “Search-based structured prediction,” _Machine learning_ , vol. 75, no. 3, pp. 297–325, 2009.
  * [24] S. M. Kakade and A. Tewari, “On the generalization ability of online strongly convex programming algorithms,” in _Advances in Neural Information Processing Systems_ , 2009, pp. 801–808.
  * [25] E. Hazan, A. Agarwal, and S. Kale, “Logarithmic regret algorithms for online convex optimization,” _Machine Learning_ , vol. 69, no. 2-3, pp. 169–192, 2007.
  * [26] S. Kakade and J. Langford, “Approximately optimal approximate reinforcement learning,” in _Proceedings of the 30th International Conference on Machine Learning (ICML)_ , vol. 2, 2002, pp. 267–274.
  * [27] J. A. Bagnell, S. M. Kakade, J. G. Schneider, and A. Y. Ng, “Policy search by dynamic programming,” in _Advances in neural information processing systems_ , 2004, pp. 831–838.
  * [28] G. Johansson and K. Rumar, “Drivers’ brake reaction times,” _Human factors_ , vol. 13, no. 1, pp. 23–27, 1971.
  * [29] D. V. McGehee, E. N. Mazzae, and G. S. Baldwin, “Driver reaction time in crash avoidance research: validation of a driving simulator study on a test track,” in _Proceedings of the human factors and ergonomics society annual meeting_ , vol. 44, no. 20, 2000.
  * [30] D. Wolinski, M. Lin, and J. Pettré, “Warpdriver: context-aware probabilistic motion prediction for crowd simulation,” _ACM Transactions on Graphics (TOG)_ , vol. 35, no. 6, 2016.
  * [31] J. Zhang and K. Cho, “Query-efficient imitation learning for end-to-end simulated driving,” in _AAAI_ , 2017, pp. 2891–2897.
  * [32] L. v. d. Maaten and G. Hinton, “Visualizing data using t-sne,” _Journal of machine learning research_ , vol. 9, no. Nov, pp. 2579–2605, 2008.
  * [33] W. Li, D. Wolinski, and M. C. Lin, “City-scale traffic animation using statistical learning and metamodel-based optimization,” _ACM Trans. Graph._ , vol. 36, no. 6, pp. 200:1–200:12, Nov. 2017.
  * [34] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural computation_ , vol. 9, no. 8, pp. 1735–1780, 1997.
  * [35] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” _nature_ , vol. 521, no. 7553, p. 436, 2015.
  * [36] D. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _ICLR_ , 2015.

##  IX Appendix

###  IX-A Solving An SPC Task

We show the proofs of solving an SPC task using standard supervised learning,
DAGGER [1], and ADAPS, respectively. We use “state” and ”observation”
interchangeably here as for these proofs we can always find a deterministic
function to map the two.

####  IX-A1 Supervised Learning

The following proof is adapted and simplified from Ross et al. [1]. We include
it here for completeness.

###### Theorem 2

Consider a $T$-step control task. Let $\epsilon=\mathbb{E}_{\phi\sim
d_{\pi^{*}},a^{*}\sim\pi^{*}(\phi)}\left[l\left(\phi,\pi,a^{*}\right)\right]$
be the observed surrogate loss under the training distribution induced by the
expert’s policy $\pi^{*}$. We assume $C\in\left[0,C_{max}\right]$ and $l$
upper bounds the 0-1 loss. $J\left(\pi\right)$ and $J\left(\pi^{*}\right)$
denote the cost-to-go over $T$ steps of executing $\pi$ and $\pi^{*}$,
respectively. Then, we have the following result:

$J\left(\pi\right)\leq J\left(\pi^{*}\right)+C_{max}T^{2}\epsilon.$

###### Proof:

In order to prove this theorem, we introduce the following notation and
definitions:

  * •

$d_{t,c}^{\pi}$: the state distribution at $t$ as a result of the following
event: $\pi$ is executed and has been choosing the same actions as $\pi^{*}$
from time $1$ to $t-1$.

  * •

$p_{t-1}\in\left[0,1\right]$: the probability that the above-mentioned event
holds true.

  * •

$d_{t,e}^{\pi}$: the state distribution at $t$ as a result of the following
event: $\pi$ is executed and has chosen at least one different action than
$\pi^{*}$ from time $1$ to $t-1$.

  * •

$(1-p_{t-1})\in\left[0,1\right]$: the probability that the above-mentioned
event holds true.

  * •

$d_{t}^{\pi}=p_{t-1}d_{t,c}^{\pi}+(1-p_{t-1})d_{t,e}^{\pi}$: the state
distribution at $t$.

  * •

$\epsilon_{t,c}$: the probability that $\pi$ chooses a different action than
$\pi^{*}$ in $d_{t,c}^{\pi}$.

  * •

$\epsilon_{t,e}$: the probability that $\pi$ chooses a different action than
$\pi^{*}$ in $d_{t,e}^{\pi}$.

  * •

$\epsilon_{t}=p_{t-1}\epsilon_{t,c}+(1-p_{t-1})\epsilon_{t,e}$: the
probability that $\pi$ chooses a different action than $\pi^{*}$ in
$d_{t}^{\pi}$.

  * •

$C_{t,c}$: the expected immediate cost of executing $\pi$ in $d_{t,c}^{\pi}$.

  * •

$C_{t,e}$: the expected immediate cost of executing $\pi$ in $d_{t,e}^{\pi}$.

  * •

$C_{t}=p_{t-1}C_{t,c}+(1-p_{t-1})C_{t,e}$: the expected immediate cost of
executing $\pi$ in $d_{t}^{\pi}$.

  * •

$C_{t,c}^{*}$: the expected immediate cost of executing $\pi^{*}$ in
$d_{t,c}^{\pi}$.

  * •

$C_{max}$: the upper bound of an expected immediate cost.

  * •

$J\left(\pi\right)=\sum_{t=1}^{T}C_{t}$: the cost-to-go of executing $\pi$ for
$T$ steps.

  * •

$J\left(\pi^{*}\right)=\sum_{t=1}^{T}C_{t,c}^{*}$: the cost-to-go of executing
$\pi^{*}$ for $T$ steps.

The probability that the learner chooses at least one different action than
the expert in the first $t$ steps is:

$\left(1-p_{t}\right)=\left(1-p_{t-1}\right)+p_{t-1}\epsilon_{t,c}.$

This gives us $\left(1-p_{t}\right)\leq(1-p_{t-1})+\epsilon_{t}$ since
$p_{t-1}\in\left[0,1\right]$. Solving this recurrence we arrive at:

$1-p_{t}\leq\sum_{i=1}^{t}\epsilon_{i}.$

Now consider in state distribution $d_{t,c}^{\pi}$, if $\pi$ chooses a
different action than $\pi^{*}$ with probability $\epsilon_{t,c}$, then $\pi$
will incur a cost at most $C_{max}$ more than $\pi^{*}$. This can be
represented as:

$C_{t,c}\leq C_{t,c}^{*}+\epsilon_{t,c}C_{max}.$

Thus, we have:

$\begin{split}C_{t}&=p_{t-1}C_{t,c}+(1-p_{t-1})C_{t,e}\\\ &\leq
p_{t-1}C_{t,c}^{*}+p_{t-1}\epsilon_{t,c}C_{max}+(1-p_{t-1})C_{max}\\\
&=p_{t-1}C_{t,c}^{*}+(1-p_{t})C_{max}\\\ &\leq C_{t,c}^{*}+(1-p_{t})C_{max}\\\
&\leq C_{t,c}^{*}+C_{max}\sum_{i=1}^{t}\epsilon_{i}.\end{split}$

We sum the above result over $T$ steps and use the fact
$\frac{1}{T}\sum_{t=1}^{T}\epsilon_{t}\leq\epsilon$:

$\begin{split}J\left(\pi\right)&\leq
J\left(\pi^{*}\right)+C_{max}\sum_{t=1}^{T}\sum_{i=1}^{t}\epsilon_{i}\\\
&=J\left(\pi^{*}\right)+C_{max}\sum_{t=1}^{T}(T+1-t)\epsilon_{t}\\\ &\leq
J\left(\pi^{*}\right)+C_{max}T\sum_{t=1}^{T}\epsilon_{t}\\\ &\leq
J\left(\pi^{*}\right)+C_{max}T^{2}\epsilon.\end{split}$

∎

####  IX-A2 DAGGER

The following proof is adapted from Ross et al. [1]. We include it here for
completeness. Note that for Theorem 5, we have arrived at the different third
term as of Ross et al. [1].

###### Lemma 1

[1] Let $P$ and $Q$ be any two distributions over elements $x\in\mathcal{X}$
and $f:\mathcal{X}\rightarrow\mathbb{R}$, any bounded function such that
$f(x)\in\left[a,b\right]$ for all $x\in\mathcal{X}$. Let the range $r=b-a$.
Then $|\mathbb{E}_{x\sim P}\left[f(x)\right]-\mathbb{E}_{x\sim
Q}\left[f(x)\right]|\leq\frac{r}{2}\lVert P-Q\rVert_{1}$.

###### Proof:

$\begin{split}&|\mathbb{E}_{x\sim P}\left[f(x)\right]-\mathbb{E}_{x\sim
Q}\left[f(x)\right]|\\\ &=|\int_{x}P(x)f(x)dx-\int_{x}Q(x)f(x)dx|\\\
&=|\int_{x}f(x)\left(P(x)-Q(x)\right)dx|\\\
&=|\int_{x}\left(f(x)-c\right)\left(P(x)-Q(x)\right)dx|,\forall
c\in\mathbb{R}\\\ &\leq\int_{x}|f(x)-c||P(x)-Q(x)|dx\\\
&\leq\max_{x}|f(x)-c|\int_{x}|P(x)-Q(x)|dx\\\ &=\max_{x}|f(x)-c|\lVert
P-Q\rVert_{1}.\end{split}$

Taking $c=a+\frac{r}{2}$ leads to $\max_{x}|f(x)-c|\leq\frac{r}{2}$ and proves
the lemma. ∎

###### Lemma 2

[1] Let $\hat{\pi}_{i}$ be the learned policy, $\pi^{*}$ be the expert’s
policy, and $\pi_{i}$ be the policy used to collect training data with
probability $\beta_{i}$ executing $\pi^{*}$ and probability $1-\beta_{i}$
executing $\hat{\pi}_{i}$ over $T$ steps. Then, we have $\lVert
d_{\pi_{i}}-d_{\hat{\pi}_{i}}\rVert_{1}\leq 2\min(1,T\beta_{i})$.

###### Proof:

In contrast to $d_{\hat{\pi}_{i}}$ which is the state distribution as the
result of solely executing $\hat{\pi}_{i}$, we denote $d$ as the state
distribution as the result of $\pi_{i}$ executing $\pi^{*}$ at least once over
$T$ steps. This gives us
$d_{\pi_{i}}=(1-\beta_{i})^{T}d_{\hat{\pi}_{i}}+\left(1-(1-\beta_{i})^{T}\right)d$.
We also have the facts that for any two distributions $P$ and $Q$, $\lVert
P-Q\rVert_{1}\leq 2$ and $(1-\beta)^{T}\geq 1-\beta
T,\forall\beta\in\left[0,1\right]$. Then, we have $\lVert
d_{\pi_{i}}-d_{\hat{\pi}_{i}}\rVert_{1}\leq 2$ and can further show:

$\begin{split}\lVert
d_{\pi_{i}}-d_{\hat{\pi}_{i}}\rVert_{1}&=\left(1-(1-\beta_{i})^{T}\right)\lVert
d-d_{\hat{\pi}_{i}}\rVert_{1}\\\ &\leq 2\left(1-(1-\beta_{i})^{T}\right)\\\
&\leq 2T\beta_{i}.\end{split}$

∎

###### Theorem 3

[1] If the surrogate loss $l\in\left[0,l_{max}\right]$ is the same as the cost
function $C$ or upper bounds it, then after $N$ iterations of DAGGER:

$J\left(\hat{\pi}\right)\leq J\left(\bar{\pi}\right)\leq
T\epsilon_{min}+T\epsilon_{regret}+\mathcal{O}(\frac{f(T,l_{max})}{N}).$ (5)

###### Proof:

Let $l_{i}\left(\pi\right)=\mathbb{E}_{\phi\sim
d_{\pi_{i}},a^{*}\sim\pi^{*}(\phi)}\left[l\left(\phi,\pi,a^{*}\right)\right]]$
be the expected loss of any policy $\pi\in\Pi$ under the state distribution
induced by the learned policy $\pi_{i}$ at the $i$th iteration and
$\epsilon_{min}=\min_{\pi\in\Pi}\frac{1}{N}\sum_{i=1}^{N}l_{i}(\pi)$ be the
minimal loss in hindsight after $N\geq i$ iterations. Then,
$\epsilon_{regret}=\frac{1}{N}\sum_{i=1}^{N}l_{i}(\pi_{i})-\epsilon_{min}$ is
the average regret of this online learning program. In addition, we denote the
expected loss of any policy $\pi\in\Pi$ under its own induced state
distribution as $L\left(\pi\right)=\mathbb{E}_{\phi\sim
d_{\pi},a^{*}\sim\pi^{*}(\phi)}\left[l\left(\phi,\pi,a^{*}\right)\right]]$ and
consider $\bar{\pi}$ as the mixed policy that samples the policies
$\\{\hat{\pi}_{i}\\}_{i=1}^{N}$ uniformly at the beginning of each trajectory.
Using Lemma 1 and Lemma 2, we can show:

$\begin{split}L(\hat{\pi}_{i})&=\mathbb{E}_{\phi\sim
d_{\hat{\pi}_{i}},a^{*}\sim\pi^{*}(\phi)}\left[l\left(\phi,\hat{\pi}_{i},a^{*}\right)\right]\\\
&\leq\mathbb{E}_{\phi\sim
d_{\pi_{i}},a^{*}\sim\pi^{*}(\phi)}\left[l\left(\phi,\hat{\pi}_{i},a^{*}\right)\right]+\frac{l_{max}}{2}\lVert
d_{\pi_{i}}-d_{\hat{\pi}_{i}}\rVert_{1}\\\ &\leq\mathbb{E}_{\phi\sim
d_{\pi_{i}},a^{*}\sim\pi^{*}(\phi)}\left[l\left(\phi,\hat{\pi}_{i},a^{*}\right)\right]+l_{max}\min\left(1,T\beta_{i}\right)\\\
&=l_{i}\left(\hat{\pi}_{i}\right)+l_{max}\min\left(1,T\beta_{i}\right).\end{split}$

By further assuming $\beta_{i}$ is monotonically decreasing and
$n_{\beta}=\operatorname*{arg\,max}_{n}(\beta_{n}>\frac{1}{T}),n\leq N$, we
have the following:

$\begin{split}\min_{i\in 1:N}L(\hat{\pi}_{i})&\leq L(\bar{\pi})\\\
&=\frac{1}{N}\sum_{i=1}^{N}L(\hat{\pi}_{i})\\\
&\leq\frac{1}{N}\sum_{i=1}^{N}l_{i}(\hat{\pi}_{i})+\frac{l_{max}}{N}\sum_{i=1}^{N}\min\left(1,T\beta_{i}\right)\\\
&=\epsilon_{min}+\epsilon_{regret}+\frac{l_{max}}{N}\left[n_{\beta}+T\sum_{i=n_{\beta}+1}^{N}\beta_{i}\right].\end{split}$

Summing over $T$ gives us:

$J(\bar{\pi})\leq
T\epsilon_{min}+T\epsilon_{regret}+\frac{Tl_{max}}{N}\left[n_{\beta}+T\sum_{i=n_{\beta}+1}^{N}\beta_{i}\right].$

Define $\beta_{i}=(1-\alpha)^{i-1}$, in order to have
$\beta_{i}\leq\frac{1}{T}$, we need $(1-\alpha)^{i-1}\leq\frac{1}{T}$ which
gives us $i\leq 1+\frac{\log{\frac{1}{T}}}{\log{(1-\alpha)}}$. In addition,
note now $i=n_{\beta}$ and
$\sum_{i=n_{\beta}+1}^{N}\beta_{i}=\frac{(1-\alpha)^{n\beta}-(1-\alpha)^{N}}{\alpha}\leq\frac{1}{T\alpha}$,
continuing the above derivation, we have:

$J\left(\bar{\pi}\right)\leq
T\epsilon_{min}+T\epsilon_{regret}+\frac{Tl_{max}}{N}\left(1+\frac{\log{\frac{1}{T}}}{\log{(1-\alpha)}}+\frac{1}{\alpha}\right).$

Given the fact $J\left(\hat{\pi}\right)=\min_{i\in 1:N}J(\hat{\pi}_{i})\leq
J(\bar{\pi})$ and representing the third term as
$\mathcal{O}(\frac{f(T,l_{max})}{N})$, we have proved the theorem.

∎

####  IX-A3 ADAPS

With the assumption that we can treat the generated trajectories from our
model and the additional data generated based on them as running a learned
policy to sample independent expert trajectories at different states while
performing policy roll-out, we have the following guarantee of ADAPS. To
better understand the following theorem and proof, we recommend interested
readers to read the proofs of Theorem 2 and 5 first.

###### Theorem 4

If the surrogate loss $l$ upper bounds the true cost $C$, by collecting $K$
trajectories using ADAPS at each iteration, with probability at least $1-\mu$,
$\mu\in(0,1)$, we have the following guarantee:

$J\left(\hat{\pi}\right)\leq J\left(\bar{\pi}\right)\leq
T\hat{\epsilon}_{min}+T\hat{\epsilon}_{regret}+\mathcal{O}\left(Tl_{max}\sqrt{\frac{\log{\frac{1}{\mu}}}{KN}}\right).$

###### Proof:

Assuming at the $i$th iteration, our model generates $K$ trajectories. These
trajectories are independent from each other since they are generated using
different parameters and at different states during the analysis of an
accident. For the $k$th trajectory, $k\in[\\![1,K]\\!]$, we can construct an
estimate
$\hat{l}_{ik}(\hat{\pi}_{i})=\frac{1}{T}\sum_{t=1}^{T}l_{i}\left(\phi_{ikt},\hat{\pi}_{i},a^{*}_{ikt}\right)$,
where $\hat{\pi}_{i}$ is the learned policy from data gathered in previous
$i-1$ iterations. Then, the approximated expected loss $\hat{l}_{i}$ is the
average of these $K$ estimates:
$\hat{l}_{i}(\hat{\pi}_{i})=\frac{1}{K}\sum_{k=1}^{K}\hat{l}_{ik}(\hat{\pi}_{i})$.
We denote
$\hat{\epsilon}_{min}=\min_{\pi\in\Pi}\frac{1}{N}\sum_{i=1}^{N}\hat{l}_{i}(\pi)$
as the approximated minimal loss in hindsight after $N$ iterations, then
$\hat{\epsilon}_{regret}=\frac{1}{N}\sum_{i=1}^{N}\hat{l}_{i}(\hat{\pi}_{i})-\hat{\epsilon}_{min}$
is the approximated average regret.

Let $Y_{i,k}=l_{i}(\hat{\pi}_{i})-\hat{l}_{ik}(\hat{\pi}_{i})$ and define
random variables
$X_{nK+m}=\sum_{i=1}^{n}\sum_{k=1}^{K}Y_{i,k}+\sum_{k=1}^{m}Y_{n+1,k}$, for
$n\in[\\![0,N-1]\\!]$ and $m\in[\\![1,K]\\!]$. Consequently,
$\\{X_{i}\\}_{i=1}^{NK}$ form a martingale and $|X_{i+1}-X_{i}|\leq l_{max}$.
By Azuma-Hoeffding’s inequality, with probability at least $1-\mu$, we have
$\frac{1}{KN}X_{KN}\leq l_{max}\sqrt{\frac{2\log{\frac{1}{\mu}}}{KN}}$.

Next, we denote the expected loss of any policy $\pi\in\Pi$ under its own
induced state distribution as $L\left(\pi\right)=\mathbb{E}_{\phi\sim
d_{\pi},a^{*}\sim\pi^{*}(\phi)}\left[l\left(\phi,\pi,a^{*}\right)\right]]$ and
consider $\bar{\pi}$ as the mixed policy that samples the policies
$\\{\hat{\pi}_{i}\\}_{i=1}^{N}$ uniformly at the beginning of each trajectory.
At each iteration, during the data collection, we only execute the learned
policy instead of mix it with the expert’s policy, which leads to
$L(\hat{\pi}_{i})=l(\hat{\pi}_{i})$. Finally, we can show:

$\begin{split}\min_{i\in 1:N}L(\hat{\pi}_{i})&\leq L(\bar{\pi})\\\
&=\frac{1}{N}\sum_{i=1}^{N}L(\hat{\pi}_{i})\\\
&=\frac{1}{N}\sum_{i=1}^{N}l_{i}(\hat{\pi}_{i})\\\
&=\frac{1}{KN}\sum_{i=1}^{N}\sum_{k=1}^{K}\left(\hat{l}_{ik}(\hat{\pi}_{i})+Y_{i,k}\right)\\\
&=\frac{1}{KN}\sum_{i=1}^{N}\sum_{k=1}^{K}\hat{l}_{ik}(\hat{\pi}_{i})+\frac{1}{KN}X_{KN}\\\
&=\frac{1}{N}\sum_{i=1}^{N}\hat{l}(\hat{\pi}_{i})+\frac{1}{KN}X_{KN}\\\
&\leq\frac{1}{N}\sum_{i=1}^{N}\hat{l}(\hat{\pi}_{i})+l_{max}\sqrt{\frac{2\log{\frac{1}{\mu}}}{KN}}\\\
&=\hat{\epsilon}_{min}+\hat{\epsilon}_{regret}+l_{max}\sqrt{\frac{2\log{\frac{1}{\mu}}}{KN}}.\end{split}$

Summing over $T$ proves the theorem. ∎

###  IX-B Network Specification

All modules within our control mechanism share a similar network architecture
that combines Long Short-Term Memory (LSTM) [34] and Convolutional Neural
Networks (CNN) [35]. Each image will first go through a CNN and then be
combined with other images to form a training sample to go through a LSTM. The
number of images of a training sample is empirically set to 5. We use the
many-to-many mode of LSTM and set the number of hidden units of the LSTM to
100. The output is the average value of the output sequence.

The CNN consists of eight layers. The first five are convolutional layers and
the last three are dense layers. The kernel size is $5\times 5$ in the first
three convolutional layers and $3\times 3$ in the other two convolutional
layers. The first three convolutional layers have a stride of two while the
last two convolutional layers are non-strided. The filters for the five
convolutional layers are 24, 36, 48, 64, 64, respectively. All convolutional
layers use VALID padding. The three dense layers have 100, 50, and 10 units,
respectively. We use ELU as the activation function and $\mathcal{L}2$ as the
kernel regularizer set to 0.001 for all layers.

We train our model using Adam [36] with initial learning rate set to 0.0001.
The batch size is 128 and the number of epochs is 500. For training Detection
(a classification task), we use Softmax for generating the output and
categorical cross entropy as the loss function. For training Following and
Avoidance (regression tasks), we use mean squared error (MSE) as the loss
function. We have also adopted cross-validation with 90/10 split. The input
image data have $220\times 66$ resolution in RGB channels.

###  IX-C Example Expert Trajectories

Figure 4 shows a set of generated trajectories for a situation where the
vehicle had collided with a static obstacle in front of it after driving on a
straight road. As expected, the trajectories feature sharper turns (red
trajectories) as the starting state tends towards the last moment that the
vehicle can still avoid the obstacle.

Figure 4:  Plotted collision-free trajectories generated by the expert
algorithm for a vehicle traveling on the right lane of a straight road, with
an obstacle in front. Spans 74 trajectories from the first moment the vehicle
perceives the obstacle (green, progressive avoidance) to the last moment the
collision can be avoided (red, sharp avoidance).

###  IX-D Learning From Accidents

Figure 5:  (This figure is copied from the main text to here for
completeness.) Illustration of important points and DANGER/SAFE labels from
Section VI for a vehicle traveling on the right lane of a straight road, with
an obstacle in front. Labels are shown for four points
$\\{\mathbf{l}_{u1},\mathbf{l}_{u2},\mathbf{l}_{u3},\mathbf{l}_{u4}\\}$
illustrating the four possible cases.

For the following paragraph, we abusively note $\mathbf{s}_{k}.x$,
$\mathbf{s}_{k}.y$ the position coordinates at state $\mathbf{s}_{k}$, and
$\mathbf{s}_{k}.vx$, $\mathbf{s}_{k}.vy$ the velocity vector coordinates at
state $\mathbf{s}_{k}$. Then, for any state
$\mathbf{s}_{k}\in\\{\mathbf{s}_{k_{f}},...,\mathbf{s}_{k_{a}}\\}$ we can
define a line
$L(\mathbf{s}_{k})=\\{\mathbf{l}_{u}=(\mathbf{s}_{k}.x,\>\mathbf{s}_{k}.y)+u\times(-\mathbf{s}_{k}.vy,\>\mathbf{s}_{k}.vx)\>|\>u\in\mathbb{R}\\}$.
On this line, we note $\mathbf{l}_{i}$ the furthest point on
$L(\mathbf{s}_{k})$ from $(\mathbf{s}_{k}.x,\>\mathbf{s}_{k}.y)$ which is at
an intersection between $L(\mathbf{s}_{k})$ and a collision-free trajectory
from $solve(\mathcal{S})$. This point determines how far the vehicle can be
expected to stray from the original trajectory $\mathcal{S}$ before the
accident, if it followed an arbitrary trajectory from $solve(\mathcal{S})$. We
also note $\mathbf{l}_{rl}$ and $\mathbf{l}_{rr}$ the two intersections
between $L(\mathbf{s}_{k})$ and the road edges ($\mathbf{l}_{rl}$ is on the
“left” with $rl>0$, and $\mathbf{l}_{rr}$ is on the “right” with $rr<0$).
These two points delimit how far from the original trajectory the vehicle
could be. Finally, we define a user-set margin $g$ as outlined below (we set
$g=0.5~{}m$).

Altogether, these points and margin are the limits of the region along the
original trajectory wherein we generate images for training: a point
$\mathbf{l}_{u}\in L(\mathbf{s}_{k})$ is inside the region if it is between
the original trajectory and the furthest collision-free trajectory plus a
margin $g$ (if $\mathbf{l}_{u}$ and $\mathbf{l}_{i}$ are on the same side,
i.e. $sign(u)=sign(i)$), or if it is between the original trajectory and
either road boundary plus a margin $g$ (if $\mathbf{l}_{u}$ and
$\mathbf{l}_{i}$ are not on the same side, i.e. $sign(u)\neq sign(i)$).

In addition, if a point $\mathbf{l}_{u}\in L(\mathbf{s}_{k})$ is positioned
between two collision-free trajectories
$\mathcal{\hat{S}}_{k_{1}},\mathcal{\hat{S}}_{k_{2}}\in solve(\mathcal{S})$,
we consider the two closest states on $\mathcal{\hat{S}}_{k_{1}}$, and the two
closest states from $\mathcal{\hat{S}}_{k_{1}}$, and bi-linearly interpolate
these four states’ velocity vectors, resulting in an approximate velocity
vector $\mathbf{v}_{bilin}(\mathbf{l}_{u})$ at $\mathbf{l}_{u}$. Similarly, if
a point $\mathbf{l}_{u}\in L(\mathbf{s}_{k})$ is not positioned between two
collision-free trajectories, we consider the two closest states on the single
closest collision-free trajectory $\mathcal{\hat{S}}_{k_{1}}\in
solve(\mathcal{S})$, and linearly interpolate their velocity vectors,
resulting in an approximate velocity vector $\mathbf{v}_{lin}(\mathbf{l}_{u})$
at $\mathbf{l}_{u}$.

From here, we can construct images at various points $\mathbf{l}_{u}$ along
$L(\mathbf{s}_{k})$ (increasing $u$ by steps of $0.1~{}m$), with various
orientation vectors (noted $\mathbf{v}_{u}$ and within 2.5 degrees of
$(\mathbf{s}_{k}.vx,\>\mathbf{s}_{k}.vy)$), and label them using the following
scheme (also illustrated in Figure 5). If the expert algorithm made the
vehicle avoid obstacles by steering left ($\mathbf{l}_{i}$ with $i>0$), there
are four cases to consider when building a point $\mathbf{l}_{u}$:

  * •

$u<i+g$ and $u>i$: $\mathbf{l}_{u}$ is outside of the computed collision-free
trajectories $solve(\mathcal{S})$, on the outside of the steering computed by
the expert algorithm. The label is SAFE if
$det(\mathbf{v}_{lin}(\mathbf{l}_{u}),\mathbf{v}_{u})\geq 0$, and DANGER
otherwise.

  * •

$u<i$ and $u>0$: $\mathbf{l}_{u}$ is inside the computed collision-free
trajectories $solve(\mathcal{S})$. The label is SAFE if
$det(\mathbf{v}_{bilin}(\mathbf{l}_{u}),\mathbf{v}_{u})\geq 0$ (over-
steering), and DANGER otherwise (under-steering).

  * •

$u<0$ and $u>rr$: $\mathbf{l}_{u}$ is outside the computed collision-free
trajectories $solve(\mathcal{S})$ on the inside of the steering computed by
the expert algorithm. The label is always DANGER.

  * •

$u<rr$ and $u>rr-g$: $\mathbf{l}_{u}$ is in an unattainable region, but we
include it to prevent false reactions to similar (but safe) future situations.
The label is DANGER if
$det(\mathbf{v}_{lin}(\mathbf{l}_{u}),\mathbf{v}_{u})>0$, SAFE otherwise.

Here, the function $det(\cdot,\cdot)$ computes the determinant of two vectors
from $\mathbb{R}^{2}$.

Conversely, if the expert algorithm made the vehicle avoid obstacles by
steering right ($\mathbf{l}_{i}$ with $i<0$), there are four cases to consider
when building a point $\mathbf{l}_{u}$:

  * •

$u>i-g$ and $u<i$: the label is SAFE if
$det(\mathbf{v}_{lin}(\mathbf{l}_{u}),\mathbf{v}_{u})\leq 0$, and DANGER
otherwise.

  * •

$u>i$ and $u<0$: the label is SAFE if
$det(\mathbf{v}_{bilin}(\mathbf{l}_{u}),\mathbf{v}_{u})\leq 0$, and DANGER
otherwise.

  * •

$u>0$ and $u<rl$: the label is always DANGER.

  * •

$u>rl$ and $u<rl+g$: the label is DANGER if
$det(\mathbf{v}_{lin}(\mathbf{l}_{u}),\mathbf{v}_{u})<0$, SAFE otherwise.

We then generate images from these (position, orientation, label) triplets
which are used to further train the Detection module of our policy.

###  IX-E Experiment Setup

####  IX-E1 Scenarios

We have tested our method in three scenarios. The first is a straight road
which represents a linear geometry, the second is a curved road which
represents a non-linear geometry, and the third is an open ground. The first
two represent on-road situations while the last represents an off-road
situation.

Both the straight and curved roads consist of two lanes. The width of each
lane is $3.75~{}m$ and there is a $3~{}m$ shoulder on each side of the road.
The curved road is half circular with radius at $50~{}m$ and is attached to
two straight roads at each end. The open scenario is a $1000~{}m$ $\times$
$1000~{}m$ ground, which has a green sphere treated as the target for the
Following module to steer the AV.

####  IX-E2 Vehicle Specs

The vehicle’s speed is set to $20~{}m/s$, which value is used to compute the
throttle value in the simulator. Due to factors such as the rendering
complexity and the delay of the communication module, the actual running speed
is in the range of $20\pm 1~{}m/s$. The length and width of the vehicle are
$4.5~{}m$ and $2.5~{}m$, respectively. The distance between the rear axis and
the rear of the vehicle is $0.75~{}m$. The front wheels can turn up to 25
degrees in either direction. We have three front-facing cameras set behind the
main windshield, which are at $1.2~{}m$ height and $1~{}m$ front to the center
of the vehicle. The two side cameras (one at left and one at right) are set to
be $0.8~{}m$ away from the vehicle’s center axis. These two cameras are only
used to capture data for training Following. During runtime, our control
policy only requires images from the center camera to operate.

####  IX-E3 Obstacles

For the on-road scenarios, we use a scaled version of a virtual traffic cone
as the obstacle on both the straight and curved roads. This scaling operation
is meant to preserve the obstacle’s visibility, since at distances greater
than $30~{}m$ a normal-sized obstacle is quickly reduced to just a few pixels.
This is an intrinsic limitation of the single-camera setup (and its
resolution), but in reality we can emulate this “scaling” using the camera’s
zoom function for instance. For the off-road scenario, we use a vehicle with
the same specifications as of the AV as the dynamic obstacle. This vehicle is
scripted to collide into the AV on its default course when no avoidance
behavior is applied by the AV.

####  IX-E4 Training Data

In order to train Following, we have built a waypoint system on the straight
road and curved road for the AV to follow, respectively. By running the
vehicle for roughly equal distances on both roads, we have gathered in total
65 061 images (33 642 images for the straight road and 31 419 images for the
curved road). On the open ground, we have sampled 30 000 positions and
computed the angle difference between the direction towards the sphere target
and the forward direction. This gives us 30 000 training examples.

In order to train Avoidance, on the straight road, we rewind the accident by
74 frames starting from the frame that the accident takes place, which gives
us 74 safe trajectories. On the curved road, we rewind the accident by 40
frames resulting in 40 safe trajectories. On the open ground, we rewind the
accident by 46 frames resulting in 46 safe trajectories. By positioning the
vehicle on these trajectories and capturing the image from the front-facing
camera, we have collected 34 516 images for the straight road, 33 624 images
for the curved road, and 33 741 images for the open ground.

For the training of Detection, using the mechanism explained in Subsection
VI-B, we have collected 32 538 images for the straight road, 71 859 for the
curved road, and 67 102 images for the open ground.