# Solvable subgroup theorem, length function and topological entropy

Shengkui Ye

###### Abstract

We prove a general solvable subgroup theorem in terms of length functions. As
applications, we obtain a solvable subgroup theorem in dynamical systems: any
solvable group of finite Hirsch length acting on a smooth manifold with
uniformly positive topological entropies must be virtually $\mathbb{Z}^{n}.$

###  0.1 Introduction

The solvable subgroup theorems were established in many contexts of
mathematics, eg. Gromoll-Wolf , Lawson-Yau for smooth manifolds, Bridson-
Haefliger [3] for CAT(0) spaces, Gersten-Short [7] for biautomatic groups,
Conner [5] for stable norms coming from left-invariant metrics, Prytuła [15]
for systolic complexes, and so on. Basically, the theorems say that solvable
groups acting nicely on nice spaces are special (eg. virtually abelian or
virtually abelian-by-abelian). In the theory of dynamic systems, Hu-Shi-Wang
[10] proved that a Heisenberg group acting on smooth Riemannian manifolds are
restrictive, in the sense that the central elements must have vanishing
Lyapunov exponents and topological entropy. In this note, we obtain a general
Solvable Subgroup Theorem in dynamic systems theory. Recall that a group
virtually has a property $P$ if some finite-index subgroup has the property
$P.$

###### Theorem 0.1

Let $G$ be a group consisting of $C^{\infty}$-diffeomorphisms of a closed
Riemannian manifold $M$ such that each non-identity element has a positive
topological entropy (resp. a positive minimal Lyapunov exponent). Then each
solvable subgroup $H<G$ of finite virtual cohomological dimension (eg. having
finite Hirsch length) is virtually abelian-by-abelian. Furthermore, if the
topological entropies (resp. Lyapunov exponents) have a uniform positive lower
bound, then $H$ is virtually a finitely generated abelian group
$\mathbb{Z}^{n}.$

The proof is based on a study of length functions defined by the author in
[18]. Let $G$ be a group. A real-valued function $l:G\rightarrow[0,\infty)$ is
called a length function if

(1) $l(g^{n})=|n|l(g)$ for any $g\in G$ and $n\in\mathbb{Z};$

(2) $l(hgh^{-1})=l(g)$ for any $h,g\in G;$ and

(3) $l(ab)\leq l(a)+l(b)$ for _commuting_ elements $a,b.$

Length functions exist in many branches of mathematics, eg. stable word
lengths, stable norms, smooth measure-theoretic entropy, translation lengths
on $\mathrm{CAT}(0)$ spaces and Gromov $\delta$-hyperbolic spaces, stable
norms of quasi-cocycles, rotation numbers of circle homeomorphisms, dynamical
degrees of birational maps, absolute values of Margulis invariants (cf. [18],
Section 2) and filling volumes (cf. [2]). A length function $l$ is called
purely positive if $l(g)>0$ for each torsion-free element $g.$ If there is a
constant $c>0$ such that $l(g)>c$ for any nonzero $l(g),$ the length function
$l$ is called discrete. A group $G$ is called purely positive or discrete if
there exists a length function $l$ on $G$ with the corresponding properties.

###### Theorem 0.2

Let $G$ be a finitely generated solvable group with a purely positively length
function. Suppose that $G$ is virtually torsion-free and any abelian subgroup
$A$ has finite
$\dim_{\mathbb{Q}}(A\bigotimes_{\mathbb{Z}}\mathbb{Q})<+\infty$. Then $G$ is
virtually either abelian or a non-nilpotent $\mathbb{C}$-linear subgroup of
$H\rtimes\mathbb{Z}^{n}$ for some integer $n$ and a finitely generated
$\mathbb{Z}[\mathbb{Z}^{n}]$-module $H.$

###### Theorem 0.3

Every solvable subgroup of finite virtual cohomological dimension in a
discretely purely positive group is a finite extension of $\mathbb{Z}^{n}.$

The following question was asked by Hu-Shi-Wang [10] (Question 1.3).

###### Question 0.4

Let $H=\langle f,g,h\mid fh=hf,gh=hg,[f,g]=h\rangle$ be the Heisenberg group,
acting on a compact $C^{\infty}$-Riemannian manifold $M$ preserving a Borel
probability measure $\mu.$ Is the norm $\|Dh_{x}^{n}\|$ bounded by
$e^{\sqrt{n}\varepsilon}$ for some $\varepsilon>0,$ or even by a polynomial in
$n$ for $\mu$-a.e. $x\in M$?

We give a positive answer to this question in the case of exponential
function.

###### Theorem 0.5

There exist constants $K,C>0$ such that

$\log\|Dh_{x}^{n}\|\leq K\sqrt{n}+C$

for any $x\in M.$

##  1 Semi-direct product

Let $A\in\mathrm{GL}_{n}(\mathbb{Z})$ be a matrix and
$G=\mathbb{Z}^{n}\rtimes_{A}\mathbb{Z}$ the semi-direct product.

###### Lemma 1.1

Any length function $l:G\rightarrow\mathbb{R}_{\geq 0}$ can be extended to be
a continuous length function $l:\mathbb{R}^{n}\mathbb{\rightarrow R}_{\geq 0}$
satisying the following properties:

1) (subadditive) $l(r_{1}+r_{2})\leq l(r_{1})+l(r_{2})$ for any
$r_{1},r_{2}\in\mathbb{R}^{n}.$

2) (homogenuous) $l(ar)=|a|l(r)$ for any $a\in\mathbb{R}$ and
$r\in\mathbb{R}^{n}.$

3) (conjugation invariant) $l(r)=l(Ar)$ for any $r\in\mathbb{R}^{n}.$

Proof. For any $q=(x_{1},\cdots,x_{n})^{T}\in\mathbb{Q}^{n}$, let $d$ be the
least common multiple of the denominators of $x_{i}.$ Define
$l(q)=\frac{1}{d}l(dq).$ For any integer $k>0,$ we have
$l(kq)=\frac{1}{|k|d}l(dkq)$ and $l(q)=\frac{1}{k}l(kq).$ Therefore,
$l(rq)=|r|l(q)$ for any rational number $r$ and any element
$q\in\mathbb{Q}^{n}.$ Suppose that $\\{q_{i}\\}\subset\mathbb{Q}^{n}$ is a
Cauchy sequence. For any $\varepsilon>0,$ there exists $N$ such that when
$k,m>N,$ we have

$\|q_{k}-q_{m}\parallel<\varepsilon.$

Suppose that the $i$-th component $(q_{k})_{i}=\frac{r_{ki}}{s_{ki}}$ for
coprime integers $r_{ki},s_{ki}.$ Denote by $\\{e_{1},...,e_{n}\\}$ the
standard basis of $\mathbb{Z}^{n}.$ Then

$\displaystyle|l(q_{k})-l(q_{m})|$ $\displaystyle=$
$\displaystyle|\frac{1}{\mathop{\mathrm{l}cm}(s_{k1},s_{k2},...,s_{kn})}l(\mathop{\mathrm{l}cm}(s_{k1},s_{k2},...,s_{kn})(\frac{r_{k1}}{s_{k1}},\frac{r_{k2}}{s_{k2}},...,\frac{r_{kn}}{s_{kn}}))-l(q_{m})|$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n}l((\frac{r_{ki}}{s_{ki}}-\frac{r_{mi}}{s_{mi}})e_{i})$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n}|\frac{r_{ki}}{s_{ki}}-\frac{r_{mi}}{s_{mi}}|l(e_{i})$
$\displaystyle<$ $\displaystyle n\varepsilon Max\\{l(e_{1}),...,l(e_{n})\\}.$

This proves that $\\{l(q_{i})\\}$ is a Cauchy sequence. For any
$r\in\mathbb{R}^{n},$ choose a rational sequence $q_{i}\rightarrow r$ and
define $l(r)=\lim l(q_{i}).$ For any $r_{1},r_{2}\in\mathbb{R}^{n},$ let
rational sequences $q_{1i}=\frac{r_{1i}}{s_{1i}}\rightarrow
r_{1},q_{2i}=\frac{r_{2i}}{s_{2i}}\rightarrow r_{2}$ (here
$r_{1i},r_{2i}\in\mathbb{Z}^{n},s_{1i},s_{2i}\in\mathbb{Z}$). We have that

$\displaystyle l(q_{1i}+q_{2i})$ $\displaystyle=$ $\displaystyle
l(\frac{r_{1i}}{s_{1i}}+\frac{r_{2i}}{s_{2i}})$ $\displaystyle=$
$\displaystyle
l(\frac{r_{1i}s_{2i}+r_{2i}s_{1i}}{s_{1i}s_{2i}})=\frac{1}{s_{1i}s_{2i}}l(r_{1i}s_{2i}+r_{2i}s_{1i})$
$\displaystyle\leq$
$\displaystyle\frac{1}{s_{1i}s_{2i}}(l(r_{1i}s_{2i})+l(r_{2i}s_{1i}))$
$\displaystyle=$ $\displaystyle
l(\frac{r_{1i}}{s_{1i}})+l(\frac{r_{2i}}{s_{2i}})=l(q_{1i})+l(q_{2i}).$

Therefore,

$\displaystyle l(r_{1}+r_{2})$ $\displaystyle=$ $\displaystyle\lim
l(q_{1i}+q_{2i})$ $\displaystyle\leq$ $\displaystyle\lim l(q_{1i})+\lim
l(q_{2i})=l(r_{1})+l(r_{2}).$

This proves the subadditivity of $l$ on $\mathbb{R}^{n}.$ From the definition,
we obviously have 2). Since the action of $A$ on $\mathbb{Z}^{n}$ is linear,
the action extends obviously to $\mathbb{R}^{n},$ which gives 3).

A similar proof shows the following.

###### Lemma 1.2

Any length function $l:\mathbb{Z}^{n}\rightarrow\mathbb{R}_{>0}$ can be
extended to be a unique continuous length function
$l^{\prime}:\mathbb{R}^{n}\rightarrow\mathbb{R}_{>0}.$

Proof. The existence is the same as in the proof of Lemma 1.1. In other words,
for any $q=(x_{1},\cdots,x_{n})^{T}\in\mathbb{Q}^{n}$, let $d$ be the least
common multiple of the denominators of $x_{i}.$ Define
$l(q)=\frac{1}{d}l(dq).$ For any $r\in\mathbb{R}^{n},$ choose a rational
sequence $q_{i}\rightarrow r$ and define $l(r)=\lim l(q_{i}).$ The uniqueness
of $l^{\prime}$ comes from the fact that a continuous function on
$\mathbb{R}^{n}$ depends only on its image on $\mathbb{Q}^{n}.$

###### Lemma 1.3

Let $A\in\mathrm{GL}_{n}(\mathbb{Z})$ be a ($\mathbb{C}$-)diagonalizable
matrix without eigenvalues of norm $1.$ Then any length function $l$ of
$G=\mathbb{Z}^{n}\rtimes_{A}\mathbb{Z}$ vanishes on $\mathbb{Z}^{n}.$

Proof. Consider the real Jordan form

$\begin{bmatrix}A_{1}&&&\\\ &A_{2}&&\\\ &&\ddots&\\\ &&&A_{r}\end{bmatrix}$

of $A,$ where $A_{i}$ is either a real Jordan block or

$a\begin{bmatrix}\cos\phi&-\sin\phi\\\ \sin\phi&\cos\phi\end{bmatrix},$

where $a\neq 1$ is a positive real number. Choose the corresponding basis
$\\{v_{1},..,v_{n}\\}$ from corresponding $A_{i}$-invariant subspaces for
$\mathbb{R}^{n}.$ If $Av_{i}=\lambda_{i}v_{i}$ for $|\lambda_{i}|\neq 1,$ then
$l(v_{i})=\lambda_{i}l(v_{i})$ implies $l(v_{i})=0.$ Otherwise,

$l(v_{i})=l(A^{k}v_{i})=a^{k}l((\frac{1}{a}A_{i})^{k}v_{i})$

for any integer $k.$ Since $\frac{1}{a}A_{i}$ is an rotation matrix and $l$ (a
continuous function by Lemma 1.1) is bounded on compact set, we get that
$l(v_{i})=0$ when $a\neq 1.$ This shows that the length function $l$ vanishes
on a basis of $\mathbb{R}^{n}$ and thus vanishes on the whole $\mathbb{R}^{n}$
by Lemma 1.1.

###### Lemma 1.4

Let $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a length function. If the
restriction $l|_{\mathbb{Z}^{n}}$ is discretely purely positive, then $l$ is
purely positive.

Proof. By Tao ect. [6], there is a Banach space $(B,\parallel\parallel)$ and
an additive group homomorphism $f:\mathbb{R}^{n}\rightarrow B$ such that
$l(x)=\parallel f(x)\parallel$ for any $x\in\mathbb{R}^{n}.$ If $l(x)=0$ for
some $x\neq 0,$ the kernel $\ker f$ is non-trivial and
$\mathop{\mathrm{I}m}f=\mathbb{R}^{m},m<n.$ Since $l|_{\mathbb{Z}^{n}}$ is
discretely purely positive, the group $\mathbb{Z}^{n}$ acts freely and
properly discontinuously on $\mathop{\mathrm{I}m}f=\mathbb{R}^{m}.$ This
implies $m=n,$ a contradiction. Therefore, $l$ is purely positive.

###### Remark 1.5

Without the condition that $l|_{\mathbb{Z}^{n}}$ is discrete, Lemma 1.4 is not
true. For example, let
$v_{1}=(1,\sqrt{2}),v_{2}=(-\sqrt{2},1)\in\mathbb{R}^{2}.$ For the
decomposition $\mathbb{R}^{2}=\mathbb{R}v_{1}\bigoplus\mathbb{R}v_{2},$ let
$f:\mathbb{R}^{2}\rightarrow\mathbb{R}$ be the projection onto the first
component. The length function $l$ defined by $l(x)=|f(x)|$ is purely positive
on $\mathbb{Z}^{2},$ since the line $\mathbb{R}v_{1}$ has irrational slope.

###### Lemma 1.6

Let $A\in\mathrm{GL}_{n}(\mathbb{Z}).$ If the group
$G=\mathbb{Z}^{n}\rtimes_{A}\mathbb{Z}$ admits a discrete purely positive
length function function $l,$ then $G$ is virtually abelian.

Proof. By Lemma 1.1, we have a length function
$l:\mathbb{R}^{n}\mathbb{\rightarrow R}_{\geq 0}$ extending
$\mathbb{Z}^{n}\mathbb{\rightarrow R}_{\geq 0}.$ Suppose that
$l|_{\mathbb{Z}^{n}}$ is discretely purely positive. Lemma 1.4 implies that
$l|_{\mathbb{R}^{n}}$ is purely positive. Consider the real Jordan form

$\begin{bmatrix}A_{1}&&&\\\ &A_{2}&&\\\ &&\ddots&\\\ &&&A_{r}\end{bmatrix}$

of $A,$ where $A_{i}$ is either a real Jordan block or

$a\begin{bmatrix}\cos\phi&-\sin\phi\\\ \sin\phi&\cos\phi\end{bmatrix},$

for some real number $a>0.$ If $Av=\lambda v$ for a unit eigenvector $v$ and
an eigenvalue $\lambda$ with $|\lambda|\neq 1,$ then $l(v)=l(Av)=\lambda l(v)$
implying $l(v)=0.$ Therefore, all the eigenvalues have norm 1. Suppose that
there is a non-trivial Jordan block

$J=\begin{bmatrix}1&1&0&\\\ &1&\ddots&0\\\ &&\ddots&1\\\
&&&1\end{bmatrix}_{k\times k}$

with $k\geq 2.$ Let $\\{e_{1},...,e_{k}\\}$ be the basis of the eigenspace
$\mathbb{R}^{k}$ under which the representation matrix of the restriction of
$A$ is of the form $J.$ For any positive integer $m,$ we have

$J^{m}e_{2}=me_{1}+e_{2}$

and

$ml(e_{1})\leq l(J^{m}e_{2})+l(e_{2})=2l(e_{2}).$

Since $m$ is arbitrary, we get $l(e_{1})=0.$ Therefore, all the real Jordan
blocks are $A$ are diagonal. Suppose that $a\neq 1.$ For any $v_{i}$ in the
subspace corresponding to $A_{i},$ we have

$l(v_{i})=l(A^{k}v_{i})=a^{k}l((\frac{1}{a}A_{i})^{k}v_{i})$

for any integer $k.$ Since $\frac{1}{a}A_{i}$ is a rotation matrix and $l$ is
bounded on compact set, we get that $l(v_{i})=0.$ Therefore, $a=1$ and $A$ is
conjugate to a block sum of rotation matrices and $1s$. Since $A$ is an
integer matrix, all the rotation matrices are of finite orders. This proves
that $A$ is of finite order and $G$ is virtually abelian.

On the other hand, Conner [5] (Example 7.1) gave an example
$\mathbb{Z}^{n}\rtimes_{A}\mathbb{Z}$ with purely positive word length, where

$A=\begin{bmatrix}0&0&0&-1\\\ 1&0&0&2\\\ 0&1&0&-1\\\ 0&0&1&2\end{bmatrix}$

is an irreductible matrix with an eigenvalue of norm 1. Recall that an
integral matrix $A_{n\times n}$ is irreducible if it has no proper non-trivial
invariant subgroup in $\mathbb{Z}^{n}.$ Using the same idea as Conner [5], we
can prove the following result.

###### Lemma 1.7

Let $A\in\mathrm{GL}_{n}(\mathbb{Z})$ be an irreducible matrix with a norm-one
eigenvalue. Then the stable word length on the semi-direct product
$\mathbb{Z}^{n}\rtimes_{A}\mathbb{Z}$ is purely positive.

Proof. Let $\mathbb{C}^{n}>\mathbb{Z}^{n}$ be a normed vector space, given by

$\|a_{1}e_{1}+a_{2}e_{2}+\cdots+a_{n}e_{n}\|=a_{1}\bar{a}_{1}+a_{2}\bar{a}_{2}+\cdots+a_{n}\bar{a}_{n},$

where each $a_{i}\in\mathbb{C}$ and $\\{e_{1},e_{2},...,e_{n}\\}$ is the
standard basis. For each

$g=(z,t^{i})\in\mathbb{C}^{n}\rtimes_{A}\mathbb{Z},$

where $t$ is a generator of $\mathbb{Z}$, let

$L(g)=\inf\\{\sum_{j=1}^{k}(\|z_{j}\|+|i_{j}|):g=(z_{1},t^{0})(0,t^{i_{1}})(z_{2},t^{0})(0,t^{i_{2}})\cdots(z_{k},t^{0})(0,t^{i_{k}})\\}$

for some $z_{1},z_{2},...,z_{k}\in\mathbb{C}^{n}$ and integers
$i_{1},i_{2},...,i_{k}\\}.$ From the definition, we have

$L(gh)\leq L(g)+L(h)$

and $L(g)=L(g^{-1})$ for any $g,h\in\mathbb{C}^{n}\rtimes_{A}\mathbb{Z}$.
Define $l(g)=\lim_{n\rightarrow\infty}\frac{L(g^{n})}{n}.$ Note that $l(g)$ is
the stable word length when $g\in\mathbb{Z}^{n}\rtimes_{A}\mathbb{Z}.$ Since
$A$ is irreducible, $A$ is diagonalizable over $\mathbb{C}.$ Let $v$ be a unit
eigenvector such that $Av=v.$ Since $A$ is diagonalizable over $\mathbb{C}$,
the complement $(\mathbb{C}v)^{\perp}$ is $A$-invariant as well. We have an
inclusion $\mathbb{C}v\times\mathbb{Z\rightarrow C}^{n}\rtimes_{A}\mathbb{Z}$.
For each $g=(z,t^{i})\in\mathbb{C}^{n}\rtimes_{A}\mathbb{Z}$, write
$z=z_{v}+z_{v}^{\prime}$ with $z_{v}\in\mathbb{C}v$ and
$z_{v}^{\prime}\in(\mathbb{C}v)^{\perp}.$ For arbitrary $z\in\mathbb{C}v$ with
$(z,1)=(z_{1},t^{i_{1}})(z_{2},t^{i_{2}})\cdots(z_{k},t^{i_{k}}),$ we have

$\displaystyle z$ $\displaystyle=$
$\displaystyle(z,1)=(z_{1},t^{i_{1}})(z_{2},t^{i_{2}})\cdots(z_{k},t^{i_{k}})$
$\displaystyle=$
$\displaystyle(z_{1v},t^{i_{1}})(z_{2v},t^{i_{2}})\cdots(z_{kv},t^{i_{k}})=z_{1v}+z_{2v}+\cdots+z_{kv}$

with the decomposition of each $z_{i}=z_{iv}+z_{iv}^{\prime}.$ This means that
$L(z)=\|z\|.$

Let

$I=\\{g\in\mathbb{Z}^{n}\rtimes_{A}\mathbb{Z}:l(g)=0\\}.$

For any $g=(z,t^{i}),$ we have $L(g)\geq|i|.$ This implies that
$I<\mathbb{Z}^{n}.$ Since $l$ is conjugate invariant and homogenuous, $I$ is
an $A$-invariant direct summand of $\mathbb{Z}^{n}$. Since $A$ is irreducible,
we have either $I=\mathbb{Z}^{n}$ or $I=0.$ But if $I=\mathbb{Z}^{n},$ we will
have that $l$ vanishes on $\mathbb{C}^{n}$ by noting that
$\\{x\in\mathbb{C}^{n}\rtimes_{A}\mathbb{Z}:l(g)=0\\}$ is a
$\mathbb{C}$-vector subspace of $\mathbb{C}^{n}.$ This implies that $I=0$ and
$l$ is purely positive.

Combining Lemma 1.3 and Lemma 1.7, we have the following.

###### Corollary 1.8

Let $A\in\mathrm{GL}_{n}(\mathbb{Z})$ be an irreducible matrix. The semi-
direct product $\mathbb{Z}^{n}\rtimes_{A}\mathbb{Z}$ is purely positive if and
only if there is a norm-one eigenvalue of $A.$

##  2 Proofs of theorems

###### Lemma 2.1

([18], Corollary 4.7) A purely positive finitely generated nilpotent group is
virtually abelian.

###### Remark 2.2

Without the condition of finite generation, Lemma 2.1 is not true. For each
integer $n\geq 2,$ let $H_{n}$ the group consisting of all $3\times 3$
strictly upper triangular matrices with entries in $\mathbb{Z}/n.$ Let
$G=(\bigoplus_{n\geq 2}H_{n})\times\mathbb{Z}$. The group $G$ is nilpotent,
with a purely positive length function coming from the projection
$G\rightarrow\mathbb{Z}$. However, $G$ is not virtually abelian.

###### Lemma 2.3

Let $G$ be a solvable group equipped with a purely positive lenghth function
$l.$ Let $A$ be a maximal abelian normal subgroup of $G$. Assume that $A$ is
torsion-free. Then $C_{G}(A)=A$, where $C_{G}(A)$ is the centralizer of $A$ in
$G.$

Proof. Note that $C_{G}(A)$ is a normal subgroup of $G$. Actually, for any
$x\in C_{G}(A),t\in G,a\in A,$ we have
$txt^{-1}a=txt^{-1}t(t^{-1}at)t^{-1}=tx(t^{-1}at)t^{-1}=t(t^{-1}at)xt^{-1}=atxt^{-1}.$
Suppose that $C_{G}(A)\neq A.$ Let $B/A$ be a maximal abelian characteristic
subgroup of the solvable group $C_{G}(A)/A$. Note that $B/A$ is non-trivial,
as it can contain the last non-trivial term in the derived series of
$C_{G}(A)/A.$ Since $C_{G}(A)/A$ is normal in $G/A,$ the group $B/A$ is normal
in $G/A.$ Let $B<G$ be the normal subgroup corresponding to $B/A.$ Since the
commutator subgroup $1\neq[B,B]<A,$ there exist elements $b_{1},b_{2}\in B$
such that the commutator $1\neq[b_{1},b_{2}]\in A.$ But the subgroup $\langle
b_{1},b_{2}\rangle<B$ is a Heisenberg group. Lemma 2.1 implies that any length
function of $\langle b_{1},b_{2}\rangle$ vanishes on the center
$[b_{1},b_{2}]$, which is a contradiction.

###### Theorem 2.4

Let $G$ be a solvable group with a purely positive length function $l.$
Suppose that $G$ has a finite virtually cohomological dimension. There exists
a finite-index subgroup $K<G$ such that

1) either $K$ is abelian, or

2) there exits abelian groups $A,B$ fitting into an exact sequence

$1\rightarrow A\rightarrow K\rightarrow B\rightarrow 1$

satisfying that the action of $B$ on $A\bigotimes_{\mathbb{Z}}\mathbb{Q}$ is
effective and each non-identity element of $B$ is non-unipotent in
$\mathrm{Aut}(A\bigotimes_{\mathbb{Z}}\mathbb{Q)\hookrightarrow}\mathrm{GL}_{n}(\mathbb{C}).$
In particular, $G$ is either virtually abelian or virtually non-nilpotent
abelian-by-abelian.

Proof. Let $H<G$ be a finite-index subgroup of finite cohomological dimension.
Let $A$ be a maximal abelian normal subgroup of $H.$ Since $H$ is torsion-
free, $A$ is torsion-free. The quotient group $H/A$ acts on $A$ by
conjugation. By Lemma 2.3, the action is effective. Note that $A$ embeds into
$A\bigotimes_{\mathbb{Z}}\mathbb{Q\cong Q}^{n}$ for some integer $n.$ The
group $H/A$ is isomorphic to a subgroup of
$\mathrm{GL}_{n}(\mathbb{Q})\hookrightarrow\mathrm{GL}_{n}(\mathbb{C}),$ by
considering its conjugate action on $A.$ Therefore, $H/A$ has a finite-index
subgroup $K/A$ (for some $K<G)$, which is conjugate to a subgroup of the upper
triangular matrices in $\mathrm{GL}_{n}(\mathbb{C}).$ For each unipotent $g\in
K/A$ (eg. $g\in[K/A,K/A],$ the commutator subgroup), the subgroup $\langle
A,g\rangle$ is isomorphic to the nilpotent group $A\rtimes_{g}\mathbb{Z}.$ For
any finite subset $S\subset A,$ the subgroup $\langle S,g\rangle$ generated by
$S,g$ is still nilpotent. Lemma 2.1 implies that $\langle S,g\rangle$ is
virtually abelian. Therefore, $g=1.$ This proves that $K/A$ (isomorphic to a
subgroup of $(\mathbb{C}^{\ast})^{n})$ is abelian. If $K/A$ is finite, then
$H$ is virtually abelian. If $K/A$ is infinite, and $H$ is virtually abelian-
by-abelian. In the latter case, take $B=K/A$ to finish the proof.

Proof of Theorem 0.2. Let $K$ be a finite-index torsion-free subgroup of $G.$
Let $A$ be a maximal normal abelian group of $K.$ Since $K/A$ acts effectively
on $A,$ we know that $K/A$ is isomorphic to a subgroup of
$\mathrm{GL}_{n}(\mathbb{Q})\hookrightarrow\mathrm{GL}_{n}(\mathbb{C}).$ There
is a finite-index subgroup $K_{1}/A$ of $K/A,$ which is upper triangulizable.
Any unipotent element $\gamma\in K_{1}/A$ (eg. $\gamma\in[K_{1}/A,K_{1}/A]$
the commutator subgroup) will give a nilpotent subgroup $\langle
A,\gamma\rangle=A\rtimes_{\gamma}\mathbb{Z}$, which is impossible since any
length function will vanish on the center of the nilpotent group (see [18],
Lemma 5.2). Therefore, $K_{1}/A$ is abelian and the finite-index subgroup
$K_{1}<G$ is metabelian. A classical theorem (cf. [14], 11.3.3, page 252)
implies that $K_{1}$ embeds into $H\rtimes(K_{1})_{\mathrm{ab}}$ for some
finitely generated $\mathbb{Z}[(K_{1})_{\mathrm{ab}}]$-module $H$ over the
integral group ring of the abelianization of $K_{1}.$ Since $K_{1}$ is
finitely generated, the abelianization $(K_{1})_{\mathrm{ab}}$ contains a
subgroup $\mathbb{Z}^{n}$ of finite index. Note that $H$ is finitely generated
$\mathbb{Z}[\mathbb{Z}^{n}]$-module as well. The group $K_{1}$ is a finitely
generated torsion-free metabelian. Therefore, it is $\mathbb{C}$-linear by
Levič [13] and Remeslennikov [16].

###### Theorem 2.5

Let $G$ be a solvable group with a purely positive length function. Suppose
that $G$ is virtually torsion-free and any abelian subgroup $A$ is finitely
generated. Then $G$ is virtually either $\mathbb{Z}^{n}$ or a non-nilpotent
group $B$ of the form

$1\rightarrow\mathbb{Z}^{m}\rightarrow B\rightarrow\mathbb{Z}^{k}\rightarrow
1$

for some integers $n,m,k.$ Here $\mathbb{Z}^{k}$ acts on $\mathbb{Z}^{m}$
effectively by non-unipotent matrices.

Proof of Theorem 2.5. We use the notation as in the proof of Theorem 0.2. By
the assumption, $A=\mathbb{Z}^{m}$ for some $n.$ Since the group
$K_{1}/A<\mathrm{GL}_{n}(\mathbb{Z})$ is solvable, it is poly-cyclic. In
particular, $K_{1}/A$ is finitely generated abelian group and there is a
finite-index subgroup $\mathbb{Z}^{k}$ for some $k.$ Let $B<K_{1}$ be the
preimage of $\mathbb{Z}^{k}<K_{1}/A$ to finish the proof. If $B$ is virtually
abelian, this is the first case. If $B$ is not virtually abelian, it is cannot
be nilpotent by Lemma 2.1. This means that each non-identity element in
$\mathbb{Z}^{k}$ acts by a non-unipotent invertible matrix.

Proof of Theorem 0.3. Let $G$ be such a discretely purely positive solvable
group of finite virtual cohomological dimension. Since $G$ is of finite
virtual cohomological dimension, we assume that $G$ itself is torsion-free.
Let $A$ be a maximal normal abelian subgroup. Since $G$ has a discrete length
function, $A$ is not divisible. Since $A$ has a finite cohomological
dimension, we know $A$ is isomorphic to $\mathbb{Z}^{n}.$ By Lemma 2.3, the
quotient group $G/A$ acts effectively on $A.$ This means that $G/A$ is
isomorphic to a subgroup of $\mathrm{GL}_{n}(\mathbb{Z}).$ Lemma 1.6 implies
that $G/A$ is a torsion group. However, every solvable subgroup of
$\mathrm{GL}_{n}(\mathbb{Z})$ is polycyclic (cf. [17], Cor 1, page 26).
Therefore, $G/A$ is a polycyclic torsion group and thus is finite.

Proof of Theorem 0.1. Let $\mathrm{Diff}^{\infty}(M)$ be the group of
diffeomorphisms of $M.$ For any $f,g\in\mathrm{Diff}^{\infty}(M)$ and integer
$n,$ it is well-known that the topological entropy satisfies
$h_{\mathrm{top}}(f^{n})=|n|h_{\mathrm{top}}(f)$ and
$h_{\mathrm{top}}(f)=h_{\mathrm{top}}(gfg^{-1})$ (cf. [11], Cor. 3.14 and
Prop. 3.1.7, page 111). Hu [9] (Theorem C) proves that
$h_{\mathrm{top}}(fg)\leq h_{\mathrm{top}}(f)+h_{\mathrm{top}}(g)$ when
$fg=gf.$ This shows that the topological entropy $h_{\mathrm{top}}$ is a
length function on the group $\mathrm{Diff}^{\infty}(M).$ By Theorem 2.4, the
group $H$ is virtually either abelian or meta-abelian. In any case, $H$ is
virtually abelian-by-abelian. If there is a uniform lower bound of the
topological entropies, the length function is discrete. Theorem 0.3 implies
that $H$ is virtually a finitely generated abelian group $\mathbb{Z}^{n}.$

In the case of Lyapunov exponents, note that for any $x\in M,u\in
T_{x}M,f\in\mathrm{Diff}^{\infty}(M)$ the Lyapunov exponent

$\chi(x,u,f)=\lim_{n\rightarrow\infty}\frac{\log\|D_{x}f^{n}u\|}{n}\leq\sup_{x\in
M}\lim_{n\rightarrow\infty}\frac{\log\|D_{x}f^{n}\|}{n}.$

Actually,

$l(f):=\max\\{\sup_{x\in
M}\lim_{n\rightarrow\infty}\frac{\log\|D_{x}f^{n}\|}{n},\sup_{x\in
M}\lim_{n\rightarrow-\infty}\frac{\log\|D_{x}f^{n}\|}{n}\\}$

is a length function on $\mathrm{Diff}^{\infty}(M)$ (see [18], Lemma 2.5). A
similar argument finishes the proof.

###### Theorem 2.6

Let $G$ be a solvable group with a purely positive length function. Suppose
that $G$ has virtual cohomological dimension $vcd(G)\leq 3$ and any abelian
subgroup $A$ is finitely generated. Then $G$ is a finite extension of
$\mathbb{Z}^{n}$ for some integer $n\leq 3.$

Proof of Theorem 2.6. By Theorem 2.5, the group $G$ is virtually either
$\mathbb{Z}^{n}$ or a non-nilpotent group $B$ of the form

$1\rightarrow\mathbb{Z}^{m}\rightarrow B\rightarrow\mathbb{Z}^{k}\rightarrow
1$

for some non-negative integers $n,m,k.$ It is enough to rule out the second
case. Since cohomological dimension of $B$ is at most $3,$ we see that
$m+k\leq 3.$ When $m=1$ or $m=3,$ the group $B$ is virtually abelian since
$\mathbb{Z}^{k}$ acts effectively on $\mathbb{Z}^{m}$. When $m=2,$ the group
$B=\mathbb{Z}^{2}\rtimes_{\phi}\mathbb{Z},$ a semi-direct product for some
$\phi\in\mathrm{GL}_{2}(\mathbb{Z}).$ Consider the Jordan canonical form of
$\phi.$ If all the eigenvalues $\lambda_{1},\lambda_{2}$ of $\phi$ have norm
different from $1,$ any length function will vanish on $\mathbb{Z}^{2}$ by
Lemma 1.3. Otherwise, $\lambda_{1},\lambda_{2}=\pm 1$ or
$\lambda_{1},\lambda_{2}=\bar{\lambda}_{1}$ are conjugate complex numbers of
norm $1.$ If $\phi$ is $\mathbb{C}$-diagonalizable, $\phi$ is of finite order,
in which case $B$ is virtually abelian. Otherwise, $\phi$ is conjugate (in
$\mathrm{GL}_{n}(\mathbb{C})$) to

$\begin{bmatrix}1&1\\\ 0&1\end{bmatrix}\text{ or }\begin{bmatrix}-1&1\\\
0&-1\end{bmatrix},$

in which case the matrix $\phi$ has the repeated eigenvalues $1$ or $-1.$ We
can choose a basis $\\{v_{1},v_{2}\\}\subset\mathbb{Q}^{2}$ such that the
representation matrix of $\phi:\mathbb{Q}^{2}\rightarrow\mathbb{Q}^{2}$ with
respect to the basis $\\{v_{1},v_{2}\\}$ is of the form

$J=\begin{bmatrix}1&x\\\ 0&1\end{bmatrix}\text{ or }L=\begin{bmatrix}-1&y\\\
0&-1\end{bmatrix}$

for some nonzero $x,y\in\mathbb{Q}.$ Note that a purely positive length
function on $\mathbb{Z}^{2}\rtimes_{\phi}\mathbb{Z}$ can be extended to be a
purely positive length function on $\mathbb{Q}^{2}$ by Lemma 1.1. For any
positive even integer $m,$ we have

$\displaystyle J^{m}v_{2}$ $\displaystyle=$ $\displaystyle
mxv_{1}+v_{2},\text{ or}$ $\displaystyle L^{m}v_{2}$ $\displaystyle=$
$\displaystyle-myv_{1}+v_{2}$

and

$\displaystyle m|x|l(v_{1})$ $\displaystyle\leq$ $\displaystyle
l(J^{m}v_{2})+l(v_{2})=2l(v_{2}),\text{ or}$ $\displaystyle m|y|l(v_{1})$
$\displaystyle\leq$ $\displaystyle l(J^{m}v_{2})+l(v_{2})=2l(v_{2}).$

Since $m$ is arbitrary, we get $l(v_{1})=0.$ This is a contradiction to the
fact that $l$ is purely positive. The proof is finished.

###### Remark 2.7

Some versions of Theorem 2.4 and Theorem 2.4 are obtained by Conner for length
functions coming from semi-norms on groups. However, many length functions are
not from semi-norms (see [18], Section 2, or the final section of the current
paper).

##  3 Stable norms

Following [5, 4], a real-valued function $L:G\rightarrow[0,\infty)$ on a group
$G$ is called a (semi-)norm if $L(gh)\leq L(g)+L(h),L(g)=L(g^{-1})$ for any
$g,h\in G.$ It’s well-known that the stable norm

$\mathrm{sL}(g):=\lim_{n\rightarrow\infty}\frac{L(g^{n})}{n}$

is a length function (see [18]). In this section, we study stable norms on the
Heisenberg group

$\displaystyle H$ $\displaystyle=$ $\displaystyle\langle a,b,c\mid
ac=ca,bc=cb,[a,b]=c\rangle$ $\displaystyle=$
$\displaystyle\\{\begin{bmatrix}1&x&z\\\ &1&y\\\
&&1\end{bmatrix}:x,y,z\in\mathbb{Z}\\}.$

Choose $S=\\{a,b,a^{-1},b^{-1}\\}$ to be a generating set and let $|g|_{S}$ be
the word length defined by $S$ for

$g=\begin{bmatrix}1&x&z\\\ &1&y\\\ &&1\end{bmatrix}\in H.$

Denote $d(x,y,z)=|g|_{S}$ the word length. Blachere [1] shows that
$d(x,y,z)=d(-x,y,-z)=d(x,-y,-z)=d(-x,-y,z)=d(y,x,z)$ for any
$x,y,z\in\mathbb{Z}$. The following is from Theorem 2.2 of [1].

###### Lemma 3.1

Assume that $z\geq 0,x\geq 0,x\geq y\geq-x.$ When $y\geq 0,x\leq\sqrt{z},$ we
have $d(x,y,z)=2\lceil 2\sqrt{z}\rceil-x-y.$ When $y\geq 0,x\geq\sqrt{z}$ and
$xy>z,$ we have $d(x,y,z)=x+y.$

###### Lemma 3.2

Let $L:H\rightarrow[0,\infty)$ be a semi-norm on the Heisenberg group $H.$
There are constants $K,C\geq 0$ such that

$L(c^{n})\leq K\sqrt{n}+C$

for any integer $n\geq 0.$

Proof. Let $|x|_{S}$ be the word length of $x\in H$ with respect to the
generating set $S=\\{f,g,f^{-1},g^{-1}\\}.$ Suppose that $x=s_{1}s_{2}\cdots
s_{|x|_{S}}$ with each $s_{i}\in S.$ It is clear that

$\displaystyle L(x)$ $\displaystyle\leq$ $\displaystyle
L(s_{1})+L(s_{2})+\cdots+L(s_{|x|_{S}})$ $\displaystyle\leq$
$\displaystyle|x|_{S}\max\\{L(s):s\in S\\}.$

Choose an integer $k$ such that $k^{2}\leq n<(k+1)^{2}.$ We have

$\displaystyle L(c^{n})$ $\displaystyle\leq$
$\displaystyle|c^{n}|_{S}\max\\{L(s):s\in S\\}$ $\displaystyle=$
$\displaystyle 2\lceil 2\sqrt{n}\rceil\max\\{L(s):s\in S\\}$
$\displaystyle\leq$ $\displaystyle K\sqrt{n}+C$

for $K=4\max\\{L(s):s\in S\\},C=2\max\\{L(s):s\in S\\}+2.$ Note that the word
length $|c^{n}|_{S}=2\lceil 2\sqrt{n}\rceil,$ twice the upper integer of
$2\sqrt{n},$ by Lemma 3.1.

Proof of Theorem 0.5. For any smooth diffeomorphism $f_{1},$ we have that

$\|Df_{1x}\|\leq\max\\{\sup_{x\in M}\|Df_{1x}\|,\sup_{x\in
M}\|Df_{1x}^{-1}\|\\}.$

Let $L(f_{1})=\log\max\\{\sup_{x\in M}\|Df_{1x}\|,\sup_{x\in
M}\|Df_{1x}^{-1}\|\\}.$ It’s not hard to check that $L(f_{1}f_{2})\leq
L(f_{1})+L(f_{2})$ and $L(f_{1})=L(f_{2}^{-1})$ for any diffeomorphisms
$f_{1},f_{2}.$ Lemma 3.2 finishes the proof.

###### Corollary 3.3

For any

$g=\begin{bmatrix}1&x&z\\\ &1&y\\\ &&1\end{bmatrix}\in H,$

we have the stable word length

$\mathrm{swl}_{S}(g)=|x|+|y|.$

Proof. For any

$g=\begin{bmatrix}1&x&z\\\ &1&y\\\ &&1\end{bmatrix}\in H,$

we have $\mathrm{swl}(g)=\mathrm{swl}(g_{0})$ for
$g_{0}=\begin{bmatrix}1&x&0\\\ &1&y\\\ &&1\end{bmatrix}$ since $\mathrm{swl}$
is a length function vanishing on the center of $H.$ For each positive integer
$n,$ we have

$g_{0}^{n}=\begin{bmatrix}1&nx&\frac{n(n-1)xy}{2}\\\ &1&ny\\\
&&1\end{bmatrix}.$

After replacing $g_{0}$ by $g_{0}^{-1},$ we can always assume that $x\geq 0.$
When $x\geq y\geq 0,$ Lemma 3.1 implies that

$\displaystyle|g_{0}^{n}|$ $\displaystyle=$ $\displaystyle nx+ny,$
$\displaystyle\mathrm{swl}(g_{0})$ $\displaystyle=$ $\displaystyle x+y.$

When $y>x,$ we have

$\displaystyle|g_{0}^{n}|$ $\displaystyle=$ $\displaystyle
d(nx,ny,\frac{n(n-1)xy}{2})=d(ny,nx,\frac{n(n-1)xy}{2})$ $\displaystyle=$
$\displaystyle ny+nx,$ $\displaystyle\mathrm{swl}(g_{0})$ $\displaystyle=$
$\displaystyle ny+nx.$

When $0\geq y>-x,$ we have

$\displaystyle|g_{0}^{n}|$ $\displaystyle=$ $\displaystyle
d(nx,ny,\frac{n(n-1)xy}{2})=d(nx,n|y|,\frac{n(n-1)x|y|}{2})$ $\displaystyle=$
$\displaystyle nx+n|y|.$

When $y\leq-x,$ we have

$\displaystyle|g_{0}^{n}|$ $\displaystyle=$ $\displaystyle
d(nx,ny,\frac{n(n-1)xy}{2})=d(nx,n|y|,\frac{n(n-1)x|y|}{2})$ $\displaystyle=$
$\displaystyle d(n|y|,nx,\frac{n(n-1)x|y|}{2})=n|y|+nx.$

In any case, we have $\mathrm{swl}(g)=|x|+|y|.$

It’s not hard to see that the $\mathrm{swl}$ gives a norm on the
abelianization $H/\langle c\rangle$ which is generated by the image of $a,b.$

###### Corollary 3.4

Let $L:H\rightarrow\mathbb{R}$ be a semi-norm, i.e. $L(gh)\leq
L(g)+L(h),L(g)=L(g^{-1})$ for any $g,h\in H.$ There exists constant $K$ such
that

$\mathrm{sL}(g)\leq K(|x|+|y|)$

for any

$g=\begin{bmatrix}1&x&z\\\ &1&y\\\ &&1\end{bmatrix}\in H.$

Proof. For each integer $k,$ write $g^{k}=s_{1}s_{2}...s_{n}$ for some
$s_{i}\in S=\\{a,b,a^{-1},b^{-1}\\}$ and $n=|g^{k}|_{S}.$ Then we have

$\displaystyle L(g^{k})$ $\displaystyle\leq$
$\displaystyle|g^{k}|_{S}\max\\{L(s):s\in S\\},$ $\displaystyle\mathrm{sL}(g)$
$\displaystyle=$
$\displaystyle\lim\frac{L(g^{k})}{k}\leq\mathrm{swl}(g)\max\\{L(s):s\in S\\}.$

Choose $K=\max\\{L(s):s\in S\\}$ and apply Corollary 3.3 to finish the proof.

###### Corollary 3.5

There exist length functions on $H$ which are not stable norms.

Proof. Let

$g_{1,n}=\begin{bmatrix}1&1&0\\\ &1&n\\\ &&1\end{bmatrix}$

for each integer $n\geq 1.$ Define $l:H\rightarrow\mathbb{R}$ by
$l(g_{1,n})=n^{2},l(g_{1,n}^{k})=|k|l(g_{1,n})$ and all other elements mapping
to $0.$ This is a well-defined length function (see [18], Theorem 5.3). But
$l$ grows quadratically, while any stable norm grows linearly with respect to
the matrix entries by the previous corollary.

## References

  * [1] S. Blachere, Word distance on the discrete Heisenberg group, Colloq. Math.95 no. 1 (2003), 21–36.
  * [2] F. Bertolotti, R. Frigerio, Length functions on mapping class groups and simplicial volumes of mapping tori, arXiv:2205.10846, to appear at Annales de l’Institut Fourier.
  * [3] M. Bridson and A. Haefliger, Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften, vol. 319, Springer-Verlag, Berlin, 1999.
  * [4] D. Calegari, M. Freedman, Distortion in transformation groups, Geometry & Topology 10 (2006) 267–293.
  * [5] G. Conner, Discreteness properties of translation numbers in solvable groups, J. Group Theory 3 (2000), no. 1, 77-94.
  * [6] T. Fritz, S. Gadgil, A. Khare, P. Nielsen, L. Silberman and T. Tao, Homogeneous length functions on groups, Algebra and Number Theory, 12 (2018), 1773-1786.
  * [7] S. M. Gersten and H. B. Short, Rational subgroups of biautomatic groups, Ann. of Math. (2) 134 (1991), no. 1, 125-158.
  * [8] D. Gromoll and J. Wolf, Some relations between the metric structure and the algebraic structure of the fundamental group in manifolds of nonpositive curvature, Bul. Amer. Math. Soc. 4 (1971), 545-552.
  * [9] H. Hu, Some ergodic properties of commuting diffeomorphisms, Ergodic Theory Dynam. Systems 13 (1993), no. 1, 73–100.
  * [10] H. Hu, E. Shi, Z. Wang, Some ergodic and rigidity properties of discrete Heisenberg group actions, Israel Journal of Mathematics 228 (2018), 933-972.
  * [11] A. Katok and B. Hasselblatt, Introduction to the Modern Theory of Dynamical Systems, Encyclopedia of Mathematics and Its Applications 54, Cambridge University Press, 1995.
  * [12] H. Lawson and S. T. Yau, Compact manifolds of nonpositive curvature, J. Differential Geom. 7 (1972), 211-228.
  * [13] E. M. Levič, The representation of solvable groups by matrices over a certain field of characteristic zero. (Russian). Dokl. Akad. Nauk SSSR, 188 (1969), 520-21.
  * [14] J. C. Lennox and D. J. S. Robinson, The theory of infinite soluble groups, Oxford University Press, 2004.
  * [15] T. Prytuła, Solvable subgroup theorem for simplicial nonpositive curvature, Int. J. Algebra Comput., 28 (4) (2018), pp. 605-611.
  * [16] V. N. Remeslennikov, Representation of finitely generated metabelian groups by matrices. (Russian). Algebra i Logika, 8 (1969), 72–5.
  * [17] D. Segal. Polycyclic groups. Cambridge Tracts in Math. (Cambridge University Press, 1983).
  * [18] S. Ye, Length functions on groups and rigidity, arXiv:2101.08902, to appear in the Beyond Hyperbolicity/ Artin Groups, CAT(0) geometry and related topics Conference Proceedings.

NYU Shanghai, No.567 Yangsi West Rd, Pudong New Area, Shanghai, 200124, China.

NYU-ECNU Institute of Mathematical Sciences at NYU Shanghai, 3663 Zhongshan
Road North, Shanghai, 200062, China

E-mail<EMAIL_ADDRESS>


usage. Meanwhile, by selecting and replaying specific types of driving
scenarios (e.g., collision scenarios) through ScenarioRunner, DeepQTest can
better facilitate diagnoses of ADSs.

There are existing works in the literature that study scene representation and
propose scene standards and support toolsets. For instance, GeoScenario [72]
is an open DSL for autonomous driving scenario representation, and it has a
toolset available that can support the design, evaluation, and execution of
scenarios. ASAM OpenSCENARIO [65] is a file format for describing the dynamic
content of driving and traffic simulators. Scenarios defined following the
OpenSCENARIO standard can be executed by Carla ScenarioRunner [24]. Both
specifications can be used for scenario representation and execution, however,
the process of scenario definition requires a lot of manual work, which is
time-consuming. DeepQTest automates both the scenario collection and execution
process using ScenarioCollector and ScenarioRunner.

Finally, the recorded driving scenarios can also be used for regression
testing of advanced ADS versions. Specifically, each scenario is associated
with several attributes characterizing its execution results. By using search-
based techniques (e.g., genetic algorithms), these associated attributes can
support for selection and prioritizing of scenarios for regression testing of
ADSs. The recorded driving scenarios and toolset for collecting and replaying
these scenarios can be found in the replication package which is listed in
Section 6.5.

Multi-objective DeepQTest. In the current design of DeepQTest, only one
objective (i.e., reward) is used to guide the test scenarios generation
process. In practice, however, multiple objectives are often considered due to
the multi-objective nature of many sequential decision and adaptive
optimization problems [57]. In addition, from the results of RQ2 in Section
6.2, correlations can be observed among the three selected reward functions,
i.e., positive correlation between TTC and DTO, negative correlation between
TTC (DTO) and Jerk. This observation inspires us to investigate different
designs of DeepQTest which can optimize multi-objectives at one time.
Considering that the selected rewards are to some extent interrelated, one
possible solution can be deriving one objective by combining the multiple
objectives together. However, if the considered objectives conflict with each
other, and we want to achieve a trade-off between the conflicting objectives,
then multi-objective reinforcement learning (MORL) can be utilized to find a
policy that can optimize multiple objectives simultaneously [88]. We think
that there is a need to provide a multi-objective strategy for DeepQTest in
the future.

##  8 Conclusion and Future work

This paper proposed a reinforcement learning (RL)-based ADS testing approach,
named DeepQTest, which adaptively learns critical configurations of the
operating environment to generate test inputs for ADSs. DeepQTest employs Deep
Q-Learning (DQN) as the RL solution and adopts three reward functions as the
learning guidelines. To extract features from a high-dimensional operating
environment, DeepQTest utilizes multi-modal sensor fusion as the state
encoding. Furthermore, the environment configuration processes are realized
through a list of REST API endpoints specifying which environment parameters
will be configured and their values. In addition, the realism of the
environment configurations is ensured with a list of predefined realistic
constraints and the real-world effect generator, which maps real-world weather
and time to simulation. To assess the cost-effectiveness of DeepQTest, we
compared DeepQTest with three baselines, i.e., random, greedy, and a start-of-
the-art RL-based approach namely DeepCollision. Results show that DeepQTest
significantly outperformed random and greedy strategies in terms of all
selected metrics. Compared to DeepCollision, DeepQTest is capable of
generating more realistic scenarios leading to collisions for testing ADSs. We
also compared different reward functions to study their performance, and Time-
To-Collision achieved the overall best results that is set as a recommended
reward function in DeepQTest.

In the future, we plan to study the generalization of DeepQTest with more case
studies and conduct additional experiments on more ADSs and simulators. In
addition, investigating algorithm settings and tuning hyperparameter settings
is one of our future works. We plan to employ automatic hyperparameter
optimization frameworks (e.g., Optuna [4] and Tune [56]) to facilitate this
process. We also plan to study different RL solutions and the possibility of
integrating these solutions with DeepQTest. Furthermore, environmental
uncertainties are crucial factors for the safety and reliability of ADS, thus,
systematically introducing and quantifying uncertainties in the operating
environment is another future work. Finally, DeepQTest was evaluated with
simulators and the generated driving scenarios tested ADS with the simulated
vehicle in a simulated operating environment, while it is important to
evaluate the effectiveness of generated scenarios in various testing contexts,
e.g., hardware-in-the-loop and physical-world ADS testing. Studying the
transferability of virtual testing to other ADS testing contexts is another
work in the future.

## ACKNOWLEDGMENTS

This work is supported by the Co-evolver project (No. 286898/F20) funded by
the Research Council of Norway. Man Zhang is funded by the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
program (grant agreement No 864972).

## References

  * [1] Raja Ben Abdessalem, Shiva Nejati, Lionel C Briand, and Thomas Stifter.  Testing vision-based control systems using learnable evolutionary algorithms.  In 2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE), pages 1016–1026. IEEE, 2018.
  * [2] Raja Ben Abdessalem, Annibale Panichella, Shiva Nejati, Lionel C Briand, and Thomas Stifter.  Testing autonomous cars for feature interaction failures using many-objective search.  In 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 143–154. IEEE, 2018.
  * [3] Sarder Fakhrul Abedin, Md Shirajum Munir, Nguyen H Tran, Zhu Han, and Choong Seon Hong.  Data freshness and energy-efficient uav navigation optimization: A deep reinforcement learning approach.  IEEE Transactions on Intelligent Transportation Systems, 2020.
  * [4] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama.  Optuna: A next-generation hyperparameter optimization framework.  In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2623–2631, 2019.
  * [5] Andrea Arcuri and Lionel Briand.  A practical guide for using statistical tests to assess randomized algorithms in software engineering.  In 2011 33rd International Conference on Software Engineering (ICSE), pages 1–10. IEEE, 2011.
  * [6] Il Bae, Jaeyoung Moon, Junekyo Jhung, H Suk, Taewoo Kim, Hyunbin Park, Jaekwang Cha, Jincheol Kim, Dohyun Kim, and Shiho Kim.  Self-driving like a human driver instead of a robocar: Personalized comfortable driving experience for autonomous vehicles.  arXiv preprint arXiv:2001.03908, 2020.
  * [7] Francesco Bella and Roberta Russo.  A collision warning system for rear-end collision: a driving simulator study.  Procedia-social and behavioral sciences, 20:676–686, 2011.
  * [8] Raja Ben Abdessalem, Shiva Nejati, Lionel C Briand, and Thomas Stifter.  Testing advanced driver assistance systems using multi-objective search and neural networks.  In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering, pages 63–74, 2016.
  * [9] Mario Bijelic, Tobias Gruber, and Werner Ritter.  Benchmarking image sensors under adverse weather conditions for autonomous driving.  In 2018 IEEE Intelligent Vehicles Symposium (IV), pages 1773–1779. IEEE, 2018.
  * [10] Paul E. Black.  Ratcliff/obershelp pattern recognition.  In Dictionary of Algorithms and Data Structures [online]. Available from: https://www.nist.gov/dads/HTML/ratcliffObershelp.html, 2021.
  * [11] Oliver Bühler and Joachim Wegener.  Evolutionary functional testing.  Computers & Operations Research, 35(10):3144–3160, 2008.
  * [12] Alessandro Calò, Paolo Arcaini, Shaukat Ali, Florian Hauer, and Fuyuki Ishikawa.  Generating avoidable collision scenarios for testing autonomous driving systems.  In 2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST), pages 375–386. IEEE, 2020.
  * [13] Indra M Chakravarty, JD Roy, and Radha Govind Laha.  Handbook of methods of applied statistics.  1967\.
  * [14] Baiming Chen, Xiang Chen, Qiong Wu, and Liang Li.  Adversarial evaluation of autonomous vehicles in lane-change scenarios.  IEEE Transactions on Intelligent Transportation Systems, 2021.
  * [15] Jianyu Chen, Bodi Yuan, and Masayoshi Tomizuka.  Model-free deep reinforcement learning for urban autonomous driving.  In 2019 IEEE intelligent transportation systems conference (ITSC), pages 2765–2771. IEEE, 2019.
  * [16] Long Chen, Xuemin Hu, Bo Tang, and Yu Cheng.  Conditional dqn-based motion planning with fuzzy logic for autonomous driving.  IEEE Transactions on Intelligent Transportation Systems, 2020.
  * [17] Xiaozhi Chen, Huimin Ma, Ji Wan, Bo Li, and Tian Xia.  Multi-view 3d object detection network for autonomous driving.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 1907–1915, 2017.
  * [18] Felipe Codevilla, Antonio M Lopez, Vladlen Koltun, and Alexey Dosovitskiy.  On offline evaluation of vision-based driving models.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 236–251, 2018.
  * [19] Felipe Codevilla, Matthias Müller, Antonio López, Vladlen Koltun, and Alexey Dosovitskiy.  End-to-end driving via conditional imitation learning.  In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 4693–4700. IEEE, 2018.
  * [20] Anthony Corso, Peter Du, Katherine Driggs-Campbell, and Mykel J Kochenderfer.  Adaptive stress testing with reward augmentation for autonomous vehicle validatio.  In 2019 IEEE Intelligent Transportation Systems Conference (ITSC), pages 163–168. IEEE, 2019.
  * [21] Krzysztof Czarnecki.  Operational world model ontology for automated driving systems–part 1: Road structure.  Waterloo Intelligent Systems Engineering Lab (WISE) Report, University of Waterloo, 2018.
  * [22] Shaveta Dargan, Munish Kumar, Maruthi Rohit Ayyagari, and Gulshan Kumar.  A survey of deep learning and its applications: a new paradigm to machine learning.  Archives of Computational Methods in Engineering, 27(4):1071–1092, 2020.
  * [23] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan.  A fast and elitist multiobjective genetic algorithm: Nsga-ii.  IEEE transactions on evolutionary computation, 6(2):182–197, 2002.
  * [24] Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun.  Carla: An open urban driving simulator.  In Conference on robot learning, pages 1–16. PMLR, 2017.
  * [25] Gabriel Dulac-Arnold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin.  Deep reinforcement learning in large discrete action spaces.  arXiv preprint arXiv:1512.07679, 2015.
  * [26] Gabriel Dulac-Arnold, Daniel Mankowitz, and Todd Hester.  Challenges of real-world reinforcement learning.  arXiv preprint arXiv:1904.12901, 2019.
  * [27] Haoyang Fan, Fan Zhu, Changchun Liu, Liangliang Zhang, Li Zhuang, Dong Li, Weicheng Zhu, Jiangtao Hu, Hongye Li, and Qi Kong.  Baidu apollo em motion planner.  arXiv preprint arXiv:1807.08048, 2018.
  * [28] Di Feng, Christian Haase-Schütz, Lars Rosenbaum, Heinz Hertlein, Claudius Glaeser, Fabian Timm, Werner Wiesbeck, and Klaus Dietmayer.  Deep multi-modal object detection and semantic segmentation for autonomous driving: Datasets, methods, and challenges.  IEEE Transactions on Intelligent Transportation Systems, 22(3):1341–1360, 2020.
  * [29] Settimio Ferlisi, Antonio Marchese, and Dario Peduto.  Quantitative analysis of the risk to road networks exposed to slow-moving landslides: a case study in the campania region (southern italy).  Landslides, 18:303–319, 2021.
  * [30] Andrei Furda and Ljubo Vlacic.  Enabling safe autonomous driving in real-world city traffic using multiple criteria decision making.  IEEE Intelligent Transportation Systems Magazine, 3(1):4–17, 2011.
  * [31] Des Greer and Guenther Ruhe.  Software release planning: an evolutionary and iterative approach.  Information and software technology, 46(4):243–253, 2004.
  * [32] Jianmin Guo, Yu Jiang, Yue Zhao, Quan Chen, and Jiaguang Sun.  Dlfuzz: Differential fuzzing testing of deep learning systems.  In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 739–743, 2018.
  * [33] Junyao Guo, Unmesh Kurup, and Mohak Shah.  Is it safe to drive? an overview of factors, metrics, and datasets for driveability assessment in autonomous driving.  IEEE Transactions on Intelligent Transportation Systems, 21(8):3135–3151, 2019.
  * [34] Qishen Ha, Kohei Watanabe, Takumi Karasawa, Yoshitaka Ushiku, and Tatsuya Harada.  Mfnet: Towards real-time semantic segmentation for autonomous vehicles with multi-spectral scenes.  In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5108–5115. IEEE, 2017.
  * [35] Fitash Ul Haq, Donghwan Shin, and Lionel Briand.  Many-objective reinforcement learning for online testing of dnn-enabled systems.  arXiv preprint arXiv:2210.15432, 2022.
  * [36] Fitash Ul Haq, Donghwan Shin, Shiva Nejati, and Lionel C Briand.  Comparing offline and online testing of deep neural networks: An autonomous car case study.  In 2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST), pages 85–95. IEEE, 2020.
  * [37] Fabrice Harel-Canada, Lingxiao Wang, Muhammad Ali Gulzar, Quanquan Gu, and Miryung Kim.  Is neuron coverage a meaningful measure for testing deep neural networks?  In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 851–862, 2020.
  * [38] Mark Harman, Phil McMinn, Jerffeson Teixeira de Souza, and Shin Yoo.  Search based software engineering: Techniques, taxonomy, tutorial.  In Empirical software engineering and verification, pages 1–59. Springer, 2010.
  * [39] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [40] Qiang Hu, Lei Ma, Xiaofei Xie, Bing Yu, Yang Liu, and Jianjun Zhao.  Deepmutation++: A mutation testing framework for deep learning systems.  In 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 1158–1161. IEEE, 2019.
  * [41] Teemu H Itkonen, Jami Pekkanen, Otto Lappi, Iisakki Kosonen, Tapio Luttinen, and Heikki Summala.  Trade-off between jerk and time headway as an indicator of driving style.  PloS one, 12(10):e0185856, 2017.
  * [42] Yaochu Jin.  Surrogate-assisted evolutionary computation: Recent advances and future challenges.  Swarm and Evolutionary Computation, 1(2):61–70, 2011.
  * [43] Shinpei Kato, Shota Tokunaga, Yuya Maruyama, Seiya Maeda, Manato Hirabayashi, Yuki Kitsukawa, Abraham Monrroy, Tomohito Ando, Yusuke Fujii, and Takuya Azumi.  Autoware on board: Enabling autonomous vehicles with embedded systems.  In 2018 ACM/IEEE 9th International Conference on Cyber-Physical Systems (ICCPS), pages 287–296. IEEE, 2018.
  * [44] Christoph G Keller and Dariu M Gavrila.  Will the pedestrian cross? a study on pedestrian path prediction.  IEEE Transactions on Intelligent Transportation Systems, 15(2):494–506, 2013.
  * [45] Jinhan Kim, Robert Feldt, and Shin Yoo.  Guiding deep learning system testing using surprise adequacy.  In 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), pages 1039–1049. IEEE, 2019.
  * [46] B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez.  Deep reinforcement learning for autonomous driving: A survey.  IEEE Transactions on Intelligent Transportation Systems, 2021.
  * [47] B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez.  Deep reinforcement learning for autonomous driving: A survey.  arXiv preprint arXiv:2002.00444, 2020.
  * [48] Barbara Kitchenham, Lech Madeyski, David Budgen, Jacky Keung, Pearl Brereton, Stuart Charters, Shirley Gibbs, and Amnart Pohthong.  Robust statistical methods for empirical software engineering.  Empirical Software Engineering, 22(2):579–630, 2017.
  * [49] Mykel J. Kochenderfer and Kyle H. Wray Tim A. Wheeler.  Algorithms for Decision Making.  MIT press, 2022.
  * [50] Maxim Kolchin and Fedor Kozlov.  A template-based information extraction from web sites with unstable markup.  In Semantic Web Evaluation Challenge: SemWebEval 2014 at ESWC 2014, Anissaras, Crete, Greece, May 25-29, 2014, Revised Selected Papers, pages 89–94. Springer, 2014.
  * [51] Abdullah Konak, David W Coit, and Alice E Smith.  Multi-objective optimization using genetic algorithms: A tutorial.  Reliability engineering & system safety, 91(9):992–1007, 2006.
  * [52] Peter Koonce and Lee Rodegerdts.  Traffic signal timing manual.  Technical report, United States. Federal Highway Administration, 2008.
  * [53] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25:1097–1105, 2012.
  * [54] Bo Li, Tianlei Zhang, and Tian Xia.  Vehicle detection from 3d lidar using fully convolutional network.  arXiv preprint arXiv:1608.07916, 2016.
  * [55] Guanpeng Li, Yiran Li, Saurabh Jha, Timothy Tsai, Michael Sullivan, Siva Kumar Sastry Hari, Zbigniew Kalbarczyk, and Ravishankar Iyer.  Av-fuzzer: Finding safety violations in autonomous driving systems.  In 2020 IEEE 31st International Symposium on Software Reliability Engineering (ISSRE), pages 25–36. IEEE, 2020.
  * [56] Richard Liaw, Eric Liang, Robert Nishihara, Philipp Moritz, Joseph E Gonzalez, and Ion Stoica.  Tune: A research platform for distributed model selection and training.  arXiv preprint arXiv:1807.05118, 2018.
  * [57] Chunming Liu, Xin Xu, and Dewen Hu.  Multiobjective reinforcement learning: A comprehensive overview.  IEEE Transactions on Systems, Man, and Cybernetics: Systems, 45(3):385–398, 2014.
  * [58] Chengjie Lu, Yize Shi, Huihui Zhang, Man Zhang, Tiexin Wang, Tao Yue, and Shaukat Ali.  Learning configurations of operating environment of autonomous vehicles to maximize their collisions.  IEEE Transactions on Software Engineering, 49(1):384–402, 2022.
  * [59] Chengjie Lu, Tao Yue, and Shaukat Ali.  Deepscenario: An open driving scenario dataset for autonomous driving system testing.  In 2023 IEEE/ACM 20th International Conference on Mining Software Repositories (MSR), pages 52–56, 2023.
  * [60] Lei Ma, Fuyuan Zhang, Jiyuan Sun, Minhui Xue, Bo Li, Felix Juefei-Xu, Chao Xie, Li Li, Yang Liu, Jianjun Zhao, et al.  Deepmutation: Mutation testing of deep learning systems.  In 2018 IEEE 29th International Symposium on Software Reliability Engineering (ISSRE), pages 100–111. IEEE, 2018.
  * [61] Hiroya Maeda, Yoshihide Sekimoto, Toshikazu Seto, Takehiro Kashiyama, and Hiroshi Omata.  Road damage detection using deep neural networks with images captured through a smartphone.  arXiv preprint arXiv:1801.09454, 2018.
  * [62] Henry B Mann and Donald R Whitney.  On a test of whether one of two random variables is stochastically larger than the other.  The annals of mathematical statistics, pages 50–60, 1947.
  * [63] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  nature, 518(7540):529–533, 2015.
  * [64] Mustafa Mukadam, Akansel Cosgun, Alireza Nakhaei, and Kikuo Fujimura.  Tactical decision making for lane changing with deep reinforcement learning.  2017\.
  * [65] American Society of Addiction Medicine.  Asam openscenario, 2022.
  * [66] OMG.  Object constraint language v2.0.  Object Management Group Adopted Specification (formal/06-05-01), 2006.
  * [67] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32:8026–8037, 2019.
  * [68] Kexin Pei, Yinzhi Cao, Junfeng Yang, and Suman Jana.  Deepxplore: Automated whitebox testing of deep learning systems.  In proceedings of the 26th Symposium on Operating Systems Principles, pages 1–18, 2017.
  * [69] Zi Peng, Jinqiu Yang, Tse-Hsun Chen, and Lei Ma.  A first look at the integration of machine learning models in complex autonomous driving systems: a case study on apollo.  In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 1240–1250, 2020.
  * [70] Andreas Pfeuffer and Klaus Dietmayer.  Optimal sensor data fusion architecture for object detection in adverse weather conditions.  In 2018 21st International Conference on Information Fusion (FUSION), pages 1–8. IEEE, 2018.
  * [71] Florian Piewak, Peter Pinggera, Markus Enzweiler, David Pfeiffer, and Marius Zöllner.  Improved semantic stixels via multimodal sensor fusion.  In German Conference on Pattern Recognition, pages 447–458. Springer, 2018.
  * [72] Rodrigo Queiroz, Thorsten Berger, and Krzysztof Czarnecki.  Geoscenario: An open dsl for autonomous driving scenario representation.  In 2019 IEEE Intelligent Vehicles Symposium (IV), pages 287–294. IEEE, 2019.
  * [73] Jin Woo Ro, Partha S Roop, and Avinash Malik.  A new safety distance calculation for rear-end collision avoidance.  IEEE Transactions on Intelligent Transportation Systems, 22(3):1742–1747, 2020.
  * [74] Carlos Rodríguez, Marcos Baez, Florian Daniel, Fabio Casati, Juan Carlos Trabucco, Luigi Canali, and Gianraffaele Percannella.  Rest apis: a large-scale analysis of compliance with principles and best practices.  In International conference on web engineering, pages 21–39. Springer, 2016.
  * [75] Guodong Rong, Byung Hyun Shin, Hadi Tabatabaee, Qiang Lu, Steve Lemke, Mārtiņš Možeiko, Eric Boise, Geehoon Uhm, Mark Gerow, Shalin Mehta, et al.  Lgsvl simulator: A high fidelity simulator for autonomous driving.  In 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), pages 1–6. IEEE, 2020.
  * [76] Zhang Ruiming, Liu Chengju, and Chen Qijun.  End-to-end control of kart agent with deep reinforcement learning.  In 2018 IEEE International Conference on Robotics and Biomimetics (ROBIO), pages 1688–1693. IEEE, 2018.
  * [77] Ahmad EL Sallab, Mohammed Abdou, Etienne Perot, and Senthil Yogamani.  Deep reinforcement learning framework for autonomous driving.  Electronic Imaging, 2017(19):70–76, 2017.
  * [78] Lukas Schneider, Manuel Jasch, Björn Fröhlich, Thomas Weber, Uwe Franke, Marc Pollefeys, and Matthias Rätsch.  Multimodal neural networks: Rgb-d for semantic segmentation and object detection.  In Scandinavian conference on image analysis, pages 98–109. Springer, 2017.
  * [79] Adnan Shaout, Dominic Colella, and Selim Awad.  Advanced driver assistance systems-past, present and future.  In 2011 Seventh International Computer Engineering Conference (ICENCO’2011), pages 72–82. IEEE, 2011.
  * [80] Jana Sillmann, Thordis Thorarinsdottir, Noel Keenlyside, Nathalie Schaller, Lisa V Alexander, Gabriele Hegerl, Sonia I Seneviratne, Robert Vautard, Xuebin Zhang, and Francis W Zwiers.  Understanding, modeling and predicting weather and climate extremes: Challenges and opportunities.  Weather and climate extremes, 18:65–74, 2017.
  * [81] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [82] Jonathan Kelly Steven-Waslander.  Motion planning for self-driving cars.  Coursera&University of Toronto, https://www.coursera.org/lecture/motion-planning-self-driving-cars/lesson-3-time-to-collision-pS9zl, 2021.
  * [83] Andrea Stocco, Brian Pulfer, and Paolo Tonella.  Mind the gap! a study on the transferability of virtual vs physical-world testing of autonomous driving systems.  IEEE Transactions on Software Engineering, 2022.
  * [84] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [85] Baidu Apollo team.  Apollo: Open source autonomous driving, 2017.
  * [86] Yuchi Tian, Kexin Pei, Suman Jana, and Baishakhi Ray.  Deeptest: Automated testing of deep-neural-network-driven autonomous cars.  In Proceedings of the 40th international conference on software engineering, pages 303–314, 2018.
  * [87] Simon Ulbrich, Till Menzel, Andreas Reschka, Fabian Schuldt, and Markus Maurer.  Defining and substantiating the terms scene, situation, and scenario for automated driving.  In 2015 IEEE 18th International Conference on Intelligent Transportation Systems, pages 982–988. IEEE, 2015.
  * [88] Peter Vamplew, Richard Dazeley, Adam Berry, Rustam Issabekov, and Evan Dekker.  Empirical evaluation methods for multiobjective reinforcement learning algorithms.  2011\.
  * [89] Harsha Vardhan.  Hd maps: New age maps powering autonomous vehicles.  Geospatial world, 22, 2017.
  * [90] Katja Vogel.  A comparison of headway and time to collision as safety indicators.  Accident analysis & prevention, 35(3):427–433, 2003.
  * [91] Christopher JCH Watkins and Peter Dayan.  Q-learning.  Machine learning, 8(3-4):279–292, 1992.
  * [92] Xiaofei Xie, Lei Ma, Felix Juefei-Xu, Minhui Xue, Hongxu Chen, Yang Liu, Jianjun Zhao, Bo Li, Jianxiong Yin, and Simon See.  Deephunter: A coverage-guided fuzz testing framework for deep neural networks.  In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 146–157, 2019.
  * [93] Mengshi Zhang, Yuqun Zhang, Lingming Zhang, Cong Liu, and Sarfraz Khurshid.  Deeproad: Gan-based metamorphic testing and input validation framework for autonomous driving systems.  In 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 132–142. IEEE, 2018.
  * [94] Zijun Zhang.  Improved adam optimizer for deep neural networks.  In 2018 IEEE/ACM 26th International Symposium on Quality of Service (IWQoS), pages 1–2. IEEE, 2018.
  * [95] Husheng Zhou, Wei Li, Zelun Kong, Junfeng Guo, Yuqun Zhang, Bei Yu, Lingming Zhang, and Cong Liu.  Deepbillboard: Systematic physical-world testing of autonomous driving systems.  In Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering, pages 347–358, 2020.
  * [96] Morvan Zhou.  pytorch tutorials.  https://github.com/MorvanZhou/PyTorch-Tutorial, 2021.
  * [97] Wei Zhou, Julie Stephany Berrio, Stewart Worrall, and Eduardo Nebot.  Automated evaluation of semantic segmentation robustness for autonomous driving.  IEEE Transactions on Intelligent Transportation Systems, 21(5):1951–1963, 2019.
  * [98] Meixin Zhu, Yinhai Wang, Ziyuan Pu, Jingyun Hu, Xuesong Wang, and Ruimin Ke.  Safe, efficient, and comfortable velocity control based on reinforcement learning for autonomous driving.  Transportation Research Part C: Emerging Technologies, 117:102662, 2020.

## Appendix

Algorithm 4 Pseudo-Code of DeepQTest Environment Configuration Learning

1:

2:Let TEnv be the test environment; AS be the environment configuration action
space; terminate be the stopping criteria.

3:

4:$Act_{list}$: a list of actions selected from AS

5:

6:$Act_{list}$ $\leftarrow$ []

7:Initialize replay memory $D$ with capacity N; Initialize Q-network $Q$ with
random weights $\theta$; Initialize target network $\hat{Q}$ with weights
$\theta^{-}=\theta$

8:for episode = 1, M do

9: $s_{t}$ $\leftarrow$ observe a state of TEnv

10: while $\neg$ terminate do

11:

12: $act_{t}=\left\\{\begin{aligned} &arg\max_{a}Q(s_{t},a),&\text{with
probability 1-}{\epsilon}\\\ &\text{randomly select an
action},&{\epsilon}\end{aligned}\right.$

13:

14: terminate, $r_{t}$, $s_{t+1}$ $\leftarrow$ step($act_{t}$, $s_{t}$)

15: Store transition $<s_{t},a_{t},r_{t},s_{t+1}>$ in $D$

16: if $D$ is full then

17: Sample random minibatch of transition $<s_{t},a_{t},r_{t},s_{t+1}>$ from
$D$

18: Update Q-network

19: end if

20: Every $C$ steps reset $\hat{Q}=Q$

21: $s_{t}$ $\leftarrow$ $s_{t+1}$

22: Put $act_{t}$ into $Act_{list}$

23: end while

24:end for

25:return $Act_{list}$

Algorithm 5 Pseudo-Code of Scenario Similarity Calculation

1:

2:Let $S_{a}=<scene_{a}^{1},scene_{a}^{2},...,scene_{a}^{n}>$,
$S_{b}=<scene_{b}^{1},scene_{b}^{2},...,scene_{b}^{n}>$ be two driving
scenarios;

3:A $scene$ is defined as
$scene=<property^{1},property^{2},...,property^{np}>$;

4:

5:$similarity_{scenario}$: $similarity$ between $S_{a}$ and $S_{b}$.

6:function scenarioSimilarity($S_{a}$, $S_{b}$)

7: $similarity_{scenario}\leftarrow 0$

8: for $interval$ $\leftarrow$ $0$ $to$ $n-1$ do

9: $similarity_{ab}$, $similarity_{ba}$ $\leftarrow$ 0, 0

10: for i $\leftarrow$ $1$ $to$ $n-interval$ do

11: $similarity_{ab}$ $\leftarrow$ $similarity_{ab}$ \+
$\textsc{sceneSimilarity}(scene_{a}^{i},scene_{b}^{i+interval})$

12: $similarity_{ba}$ $\leftarrow$ $similarity_{ba}$ \+
$\textsc{sceneSimilarity}(scene_{b}^{i},scene_{a}^{i+interval})$

13: end for

14: $similarity_{scenario}$ $\leftarrow$ $\max$ {$similarity_{scenario}$,
$similarity_{ab}/n$, $similarity_{ba}/n$}

15: end for

16: return $similarity_{scenario}$

17:end function

18:

19:function sceneSimilarity($scene_{a}$, $scene_{b}$)

20: $similarity_{scene}\leftarrow 0$

21: for i $\leftarrow$ $1$ $to$ $np$ do

22: if $property_{a}^{i}$ $\notin$ $Obstacles$ then $\triangleright$
$Obstacles$ is {$NPCVehicles$, $Pedestrians$, $StaticObstacles$}

23: if $property_{a}^{i}$ = $property_{b}^{i}$ then

24: $similarity_{scene}\leftarrow similarity_{scene}+1$

25: else

26: $similarity_{scene}\leftarrow
similarity_{scene}+\textsc{obstacleSimilarity}(property_{a}^{i},property_{b}^{i})$

27: end if

28: end if

29: end for

30: return $similarity_{scene}/np$

31:end function

32:

33:function obstacleSimilarity($obstacles_{a}$, $obstacles_{b}$)

34: $similarity$ $\leftarrow$ $0$

35: $number_{a}$, $number_{b}$ = $\textsc{countObstacles}(obstacles_{a})$,
$\textsc{countObstacles}(obstacles_{b})$

36: $outer_{obstacles}$, $inner_{obstacles}$ $\leftarrow$ $obstacle_{a}$,
$obstacles_{b}$

37: if $number_{a}$ $\leq$ $number_{b}$ then

38: $outer_{obstacles}$, $inner_{obstacles}$ $\leftarrow$ $obstacle_{b}$,
$obstacles_{a}$

39: end if

40: for $i$ $\leftarrow$ $1$ $to$ $\min\\{number_{a},number_{b}\\}$ do

41: $similarity_{i}$ $\leftarrow$ $0$

42: for $j$ $\leftarrow$ $1$ $to$ $\max\\{number_{a},number_{b}\\}$ do

43: $similarity_{i}$ $\leftarrow$
$\max\\{similarity_{i},\textsc{countIdenticalValues}(outer_{obstacles}(i),inner_{obstacles}(j))\\}$

44: end for

45: $similarity$ $\leftarrow$ $similarity$ \+ $similarity_{i}$

46: end for

47: return $similarity$ / $(number_{a}+number_{b})$

48:end function

Table 10: Results of the Vargha and Delaney statistics and the Mann–Whitney U test ($TTC_{Reward}$) - RQ1 DeepQTest vs. (RS, GS) | TTC | DTO | Jerk | #Collision | CollisionTime
---|---|---|---|---|---
$\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$
|  | $DeepQTest_{TTC_{RD}}$
R1 | RS | 0.117 | <0.05 | 0.090 | <0.05 | 0.820 | <0.05 | 0.825 | <0.05 | 0.155 | <0.05
GS | 0.058 | <0.05 | 0.168 | <0.05 | 0.795 | <0.05 | 0.825 | <0.05 | 0.233 | <0.05
R2 | RS | 0.133 | <0.05 | 0.117 | <0.05 | 0.713 | <0.05 | 0.775 | <0.05 | 0.190 | <0.05
GS | 0.195 | <0.05 | 0.138 | <0.05 | 0.716 | <0.05 | 0.700 | <0.05 | 0.226 | <0.05
R3 | RS | 0.158 | <0.05 | 0.155 | <0.05 | 0.552 | 0.579 | 0.750 | <0.05 | 0.228 | <0.05
GS | 0.160 | <0.05 | 0.128 | <0.05 | 0.535 | 0.715 | 0.675 | <0.05 | 0.270 | <0.05
R4 | RS | 0.005 | <0.05 | 0.113 | <0.05 | 0.895 | <0.05 | 0.900 | <0.05 | 0.109 | <0.05
GS | 0.010 | <0.05 | 0.068 | <0.05 | 0.848 | <0.05 | 0.900 | <0.05 | 0.090 | <0.05
|  | $DeepQTest_{TTC_{RN}}$
R1 | RS | 0.075 | <0.05 | 0.045 | <0.05 | 0.897 | <0.05 | 0.900 | <0.05 | 0.100 | <0.05
GS | 0.043 | <0.05 | 0.087 | <0.05 | 0.843 | <0.05 | 0.775 | <0.05 | 0.185 | <0.05
R2 | RS | 0.170 | <0.05 | 0.070 | <0.05 | 0.698 | <0.05 | 0.850 | <0.05 | 0.131 | <0.05
GS | 0.107 | <0.05 | 0.052 | <0.05 | 0.748 | <0.05 | 0.750 | <0.05 | 0.119 | <0.05
R3 | RS | 0.068 | <0.05 | 0.152 | <0.05 | 0.618 | 0.208 | 0.725 | <0.05 | 0.241 | <0.05
GS | 0.087 | <0.05 | 0.085 | <0.05 | 0.512 | 0.903 | 0.625 | 0.122 | 0.316 | <0.05
R4 | RS | 0.072 | <0.05 | 0.043 | <0.05 | 0.848 | <0.05 | 0.800 | <0.05 | 0.203 | <0.05
GS | 0.077 | <0.05 | 0.068 | <0.05 | 0.840 | <0.05 | 0.850 | <0.05 | 0.134 | <0.05
|  | $DeepQTest_{TTC_{SD}}$
R1 | RS | 0.045 | <0.05 | 0.165 | <0.05 | 0.860 | <0.05 | 0.850 | <0.05 | 0.111 | <0.05
GS | 0.092 | <0.05 | 0.185 | <0.05 | 0.833 | <0.05 | 0.825 | <0.05 | 0.150 | <0.05
R2 | RS | 0.102 | <0.05 | 0.070 | <0.05 | 0.637 | 0.140 | 0.775 | <0.05 | 0.188 | <0.05
GS | 0.070 | <0.05 | 0.098 | <0.05 | 0.652 | 0.102 | 0.775 | <0.05 | 0.206 | <0.05
R3 | RS | 0.163 | <0.05 | 0.050 | <0.05 | 0.610 | 0.239 | 0.850 | <0.05 | 0.126 | <0.05
GS | 0.195 | <0.05 | 0.092 | <0.05 | 0.557 | 0.543 | 0.775 | <0.05 | 0.150 | <0.05
R4 | RS | 0.025 | <0.05 | 0.052 | <0.05 | 0.868 | <0.05 | 0.925 | <0.05 | 0.075 | <0.05
GS | 0.077 | <0.05 | 0.055 | <0.05 | 0.802 | <0.05 | 0.800 | <0.05 | 0.121 | <0.05
|  | $DeepQTest_{TTC_{SN}}$
R1 | RS | 0.035 | <0.05 | 0.175 | <0.05 | 0.757 | <0.05 | 0.900 | <0.05 | 0.084 | <0.05
GS | 0.048 | <0.05 | 0.158 | <0.05 | 0.740 | <0.05 | 0.900 | <0.05 | 0.084 | <0.05
R2 | RS | 0.045 | <0.05 | 0.010 | <0.05 | 0.630 | 0.164 | 0.825 | <0.05 | 0.151 | <0.05
GS | 0.058 | <0.05 | 0.102 | <0.05 | 0.740 | <0.05 | 0.800 | <0.05 | 0.163 | <0.05
R3 | RS | 0.270 | <0.05 | 0.102 | <0.05 | 0.718 | <0.05 | 0.825 | <0.05 | 0.139 | <0.05
GS | 0.098 | <0.05 | 0.122 | <0.05 | 0.650 | 0.107 | 0.700 | <0.05 | 0.287 | <0.05
R4 | RS | 0.035 | <0.05 | 0.052 | <0.05 | 0.815 | <0.05 | 0.875 | <0.05 | 0.138 | <0.05
GS | 0.052 | <0.05 | 0.058 | <0.05 | 0.748 | <0.05 | 0.875 | <0.05 | 0.138 | <0.05
Table 11: Results of the Vargha and Delaney statistics and the Mann–Whitney U test ($DTO_{Reward}$) - RQ1 DeepQTest vs. (RS, GS) | TTC | DTO | Jerk | #Collision | CollisionTime
---|---|---|---|---|---
$\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$
|  | $DeepQTest_{DTO_{RD}}$
R1 | RS | 0.198 | <0.05 | 0.055 | <0.05 | 0.713 | <0.05 | 0.750 | <0.05 | 0.203 | <0.05
GS | 0.098 | <0.05 | 0.060 | <0.05 | 0.719 | <0.05 | 0.825 | <0.05 | 0.158 | <0.05
R2 | RS | 0.133 | <0.05 | 0.072 | <0.05 | 0.540 | 0.675 | 0.850 | <0.05 | 0.083 | <0.05
GS | 0.085 | <0.05 | 0.058 | <0.05 | 0.675 | 0.060 | 0.875 | <0.05 | 0.095 | <0.05
R3 | RS | 0.170 | <0.05 | 0.075 | <0.05 | 0.502 | 0.989 | 0.575 | 0.356 | 0.340 | 0.063
GS | 0.163 | <0.05 | 0.068 | <0.05 | 0.547 | 0.617 | 0.700 | <0.05 | 0.287 | <0.05
R4 | RS | 0.212 | <0.05 | 0.075 | <0.05 | 0.823 | <0.05 | 0.750 | <0.05 | 0.229 | <0.05
GS | 0.268 | <0.05 | 0.065 | <0.05 | 0.858 | <0.05 | 0.825 | <0.05 | 0.175 | <0.05
|  | $DeepQTest_{DTO_{RN}}$
R1 | RS | 0.125 | <0.05 | 0.055 | <0.05 | 0.685 | <0.05 | 0.875 | <0.05 | 0.105 | <0.05
GS | 0.130 | <0.05 | 0.080 | <0.05 | 0.665 | 0.076 | 0.875 | <0.05 | 0.107 | <0.05
R2 | RS | 0.080 | <0.05 | 0.060 | <0.05 | 0.455 | 0.636 | 0.775 | <0.05 | 0.161 | <0.05
GS | 0.115 | <0.05 | 0.055 | <0.05 | 0.497 | 0.989 | 0.800 | <0.05 | 0.163 | <0.05
R3 | RS | 0.147 | <0.05 | 0.010 | <0.05 | 0.748 | <0.05 | 0.850 | <0.05 | 0.135 | <0.05
GS | 0.150 | <0.05 | 0.018 | <0.05 | 0.770 | <0.05 | 0.775 | <0.05 | 0.171 | <0.05
R4 | RS | 0.282 | <0.05 | 0.010 | <0.05 | 0.850 | <0.05 | 0.900 | <0.05 | 0.085 | <0.05
GS | 0.328 | <0.05 | 0.033 | <0.05 | 0.772 | <0.05 | 0.875 | <0.05 | 0.087 | <0.05
|  | $DeepQTest_{DTO_{SD}}$
R1 | RS | 0.168 | <0.05 | 0.043 | <0.05 | 0.723 | <0.05 | 0.750 | <0.05 | 0.261 | <0.05
GS | 0.160 | <0.05 | 0.040 | <0.05 | 0.723 | <0.05 | 0.675 | <0.05 | 0.254 | <0.05
R2 | RS | 0.048 | <0.05 | 0.068 | <0.05 | 0.378 | 0.190 | 0.825 | <0.05 | 0.099 | <0.05
GS | 0.087 | <0.05 | 0.080 | <0.05 | 0.438 | 0.508 | 0.850 | <0.05 | 0.109 | <0.05
R3 | RS | 0.100 | <0.05 | 0.048 | <0.05 | 0.730 | <0.05 | 0.800 | <0.05 | 0.158 | <0.05
GS | 0.145 | <0.05 | 0.055 | <0.05 | 0.698 | <0.05 | 0.750 | <0.05 | 0.209 | <0.05
R4 | RS | 0.282 | <0.05 | 0.055 | <0.05 | 0.830 | <0.05 | 0.825 | <0.05 | 0.144 | <0.05
GS | 0.388 | 0.059 | 0.065 | <0.05 | 0.828 | <0.05 | 0.800 | <0.05 | 0.179 | <0.05
|  | $DeepQTest_{DTO_{SN}}$
R1 | RS | 0.233 | <0.05 | 0.070 | <0.05 | 0.797 | <0.05 | 0.825 | <0.05 | 0.168 | <0.05
GS | 0.278 | <0.05 | 0.045 | <0.05 | 0.834 | <0.05 | 0.725 | <0.05 | 0.259 | <0.05
R2 | RS | 0.193 | <0.05 | 0.090 | <0.05 | 0.398 | 0.273 | 0.825 | <0.05 | 0.130 | <0.05
GS | 0.165 | <0.05 | 0.090 | <0.05 | 0.470 | 0.756 | 0.775 | <0.05 | 0.269 | <0.05
R3 | RS | 0.102 | <0.05 | 0.037 | <0.05 | 0.490 | 0.925 | 0.800 | <0.05 | 0.142 | <0.05
GS | 0.105 | <0.05 | 0.025 | <0.05 | 0.472 | 0.776 | 0.800 | <0.05 | 0.138 | <0.05
R4 | RS | 0.228 | <0.05 | 0.035 | <0.05 | 0.688 | <0.05 | 0.850 | <0.05 | 0.146 | <0.05
GS | 0.205 | <0.05 | 0.043 | <0.05 | 0.730 | <0.05 | 0.825 | <0.05 | 0.165 | <0.05
Table 12: Results of the Vargha and Delaney statistics and the Mann–Whitney U test ($Jerk_{Reward}$) - RQ1 DeepQTest vs. (RS, GS) | TTC | DTO | Jerk | #Collision | CollisionTime
---|---|---|---|---|---
$\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$
|  | $DeepQTest_{Jerk_{RD}}$
R1 | RS | 0.618 | 0.208 | 0.338 | 0.081 | 0.682 | <0.05 | 0.675 | <0.05 | 0.315 | <0.05
GS | 0.623 | 0.190 | 0.422 | 0.409 | 0.595 | 0.310 | 0.650 | 0.058 | 0.354 | 0.076
R2 | RS | 0.405 | 0.182 | 0.470 | 0.756 | 0.432 | 0.473 | 0.750 | <0.05 | 0.244 | <0.05
GS | 0.263 | <0.05 | 0.472 | 0.776 | 0.422 | 0.409 | 0.825 | <0.05 | 0.136 | <0.05
R3 | RS | 0.160 | <0.05 | 0.610 | 0.239 | 0.390 | 0.239 | 0.575 | 0.356 | 0.420 | 0.356
GS | 0.152 | <0.05 | 0.578 | 0.409 | 0.405 | 0.310 | 0.650 | 0.058 | 0.335 | <0.05
R4 | RS | 0.290 | <0.05 | 0.228 | <0.05 | 0.855 | <0.05 | 0.800 | <0.05 | 0.190 | <0.05
GS | 0.180 | <0.05 | 0.180 | <0.05 | 0.815 | <0.05 | 0.775 | <0.05 | 0.229 | <0.05
|  | $DeepQTest_{Jerk_{RN}}$
R1 | RS | 0.290 | <0.05 | 0.435 | 0.490 | 0.782 | <0.05 | 0.675 | <0.05 | 0.360 | 0.104
GS | 0.225 | <0.05 | 0.340 | 0.086 | 0.782 | <0.05 | 0.725 | <0.05 | 0.274 | <0.05
R2 | RS | 0.177 | <0.05 | 0.535 | 0.715 | 0.547 | 0.617 | 0.675 | <0.05 | 0.286 | <0.05
GS | 0.263 | <0.05 | 0.512 | 0.903 | 0.560 | 0.525 | 0.700 | <0.05 | 0.282 | <0.05
R3 | RS | 0.280 | <0.05 | 0.738× | <0.05 | 0.487 | 0.903 | 0.600 | 0.196 | 0.389 | 0.162
GS | 0.255 | <0.05 | 0.642 | 0.126 | 0.510 | 0.925 | 0.550 | 0.534 | 0.424 | 0.359
R4 | RS | 0.152 | <0.05 | 0.275 | <0.05 | 0.690 | <0.05 | 0.700 | <0.05 | 0.304 | <0.05
GS | 0.145 | <0.05 | 0.215 | <0.05 | 0.770 | <0.05 | 0.775 | <0.05 | 0.210 | <0.05
|  | $DeepQTest_{Jerk_{SD}}$
R1 | RS | 0.237 | <0.05 | 0.427 | 0.441 | 0.650 | 0.107 | 0.675 | <0.05 | 0.273 | <0.05
GS | 0.253 | <0.05 | 0.502 | 0.989 | 0.568 | 0.473 | 0.700 | <0.05 | 0.271 | <0.05
R2 | RS | 0.273 | <0.05 | 0.360 | 0.133 | 0.585 | 0.365 | 0.725 | <0.05 | 0.240 | <0.05
GS | 0.292 | <0.05 | 0.482 | 0.860 | 0.625 | 0.181 | 0.700 | <0.05 | 0.300 | <0.05
R3 | RS | 0.085 | <0.05 | 0.603 | 0.273 | 0.682 | <0.05 | 0.750 | <0.05 | 0.239 | <0.05
GS | 0.237 | <0.05 | 0.485 | 0.882 | 0.593 | 0.323 | 0.700 | <0.05 | 0.297 | <0.05
R4 | RS | 0.365 | 0.074 | 0.145 | <0.05 | 0.720 | <0.05 | 0.825 | <0.05 | 0.165 | <0.05
GS | 0.325 | <0.05 | 0.158 | <0.05 | 0.734 | <0.05 | 0.825 | <0.05 | 0.171 | <0.05
|  | $DeepQTest_{Jerk_{SN}}$
R1 | RS | 0.445 | 0.561 | 0.393 | 0.250 | 0.680 | 0.053 | 0.625 | 0.110 | 0.390 | 0.176
GS | 0.365 | 0.148 | 0.557 | 0.543 | 0.593 | 0.323 | 0.650 | 0.051 | 0.333 | <0.05
R2 | RS | 0.223 | <0.05 | 0.485 | 0.882 | 0.695 | <0.05 | 0.725 | <0.05 | 0.297 | <0.05
GS | 0.235 | <0.05 | 0.455 | 0.636 | 0.660 | 0.086 | 0.700 | <0.05 | 0.270 | <0.05
R3 | RS | 0.110 | <0.05 | 0.610 | 0.239 | 0.698 | <0.05 | 0.750 | <0.05 | 0.235 | <0.05
GS | 0.182 | <0.05 | 0.795× | <0.05 | 0.682 | <0.05 | 0.625 | 0.118 | 0.366 | 0.135
R4 | RS | 0.355 | <0.05 | 0.235 | <0.05 | 0.647 | 0.114 | 0.825 | <0.05 | 0.181 | <0.05
GS | 0.320 | <0.05 | 0.215 | <0.05 | 0.650 | 0.107 | 0.825 | <0.05 | 0.190 | <0.05
Table 13: Results of the Vargha and Delaney statistics and the Mann–Whitney U
test - RQ2

Reward Comparison | TTC | DTO | Jerk | #Collision | CollisionTime | $Div_{API}$ | $Div_{Scenario}$
---|---|---|---|---|---|---|---
$\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$
|  |  | RD
R1 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.495 | 0.833 | 0.838× | <0.05 | 0.695 | <0.05 | 0.525 | 0.722 | 0.496 | 0.978 | 0.551 | 0.583 | 0.521 | 0.828
$DeepQTest_{Jerk}$ | 0.133 | <0.05 | 0.250 | <0.05 | 0.695 | <0.05 | 0.625 | 0.099 | 0.364 | 0.134 | 0.338 | 0.079 | 0.334 | 0.073
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.128 | <0.05 | 0.100 | <0.05 | 0.542 | 0.655 | 0.600 | 0.196 | 0.354 | 0.108 | 0.276× | <0.05 | 0.302× | <0.05
R2 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.125 | <0.05 | 0.850× | <0.05 | 0.693 | <0.05 | 0.425 | 0.225 | 0.535 | 0.692 | 0.514 | 0.884 | 0.492 | 0.946
$DeepQTest_{Jerk}$ | 0.217 | <0.05 | 0.323 | 0.056 | 0.710 | <0.05 | 0.475 | 0.722 | 0.459 | 0.650 | 0.460 | 0.662 | 0.445 | 0.560
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.440 | 0.704 | 0.170 | <0.05 | 0.552 | 0.579 | 0.550 | 0.394 | 0.453 | 0.604 | 0.471 | 0.758 | 0.476 | 0.807
R3 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.458 | 0.640 | 0.855× | <0.05 | 0.522 | 0.818 | 0.550 | 0.534 | 0.471 | 0.756 | 0.565 | 0.484 | 0.547 | 0.421
$DeepQTest_{Jerk}$ | 0.278 | <0.05 | 0.113 | <0.05 | 0.562 | 0.507 | 0.550 | 0.534 | 0.386 | 0.207 | 0.393 | 0.244 | 0.422 | 0.407
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.347 | <0.05 | 0.055 | <0.05 | 0.545 | 0.636 | 0.500 | 1.000 | 0.431 | 0.441 | 0.329 | 0.063 | 0.371 | 0.085
R4 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.158 | <0.05 | 0.868× | <0.05 | 0.578 | 0.409 | 0.600 | 0.154 | 0.461 | 0.678 | 0.499 | 1.000 | 0.284× | <0.05
$DeepQTest_{Jerk}$ | 0.122 | <0.05 | 0.188 | <0.05 | 0.583 | 0.379 | 0.600 | 0.154 | 0.378 | 0.183 | 0.407 | 0.318 | 0.296× | <0.05
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.420 | 0.113 | 0.100 | <0.05 | 0.530 | 0.756 | 0.500 | 1.000 | 0.419 | 0.373 | 0.420 | 0.390 | 0.454 | 0.625
|  |  | RN
R1 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.525 | 0.584 | 0.880× | <0.05 | 0.620 | 0.199 | 0.475 | 0.696 | 0.667 | 0.068 | 0.703 | <0.05 | 0.686 | <0.05
$DeepQTest_{Jerk}$ | 0.188 | <0.05 | 0.295 | <0.05 | 0.578 | 0.409 | 0.575 | 0.302 | 0.396 | 0.258 | 0.396 | 0.263 | 0.380 | 0.197
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.290 | <0.05 | 0.117 | <0.05 | 0.455 | 0.636 | 0.600 | 0.154 | 0.264 | <0.05 | 0.255× | <0.05 | 0.231× | <0.05
R2 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.170 | <0.05 | 0.855× | <0.05 | 0.757 | <0.05 | 0.550 | 0.447 | 0.476 | 0.797 | 0.527 | 0.765 | 0.540 | 0.640
$DeepQTest_{Jerk}$ | 0.225 | <0.05 | 0.145 | <0.05 | 0.685 | <0.05 | 0.650 | <0.05 | 0.295 | <0.05 | 0.320× | <0.05 | 0.338× | <0.05
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.443 | 0.521 | 0.048 | <0.05 | 0.445 | 0.561 | 0.600 | 0.196 | 0.333 | 0.060 | 0.292× | <0.05 | 0.352 | 0.054
R3 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.378 | 0.189 | 0.820× | <0.05 | 0.472 | 0.776 | 0.425 | 0.302 | 0.547 | 0.603 | 0.565 | 0.476 | 0.501 | 1.000
$DeepQTest_{Jerk}$ | 0.168 | <0.05 | 0.072 | <0.05 | 0.588 | 0.351 | 0.600 | 0.215 | 0.352 | 0.094 | 0.443 | 0.539 | 0.326 | 0.061
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.307 | <0.05 | 0.007 | <0.05 | 0.650 | 0.107 | 0.675 | <0.05 | 0.307 | <0.05 | 0.379 | 0.189 | 0.241× | <0.05
R4 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.233 | <0.05 | 0.880× | <0.05 | 0.562 | 0.507 | 0.450 | 0.447 | 0.613 | 0.219 | 0.664 | 0.074 | 0.453 | 0.811
$DeepQTest_{Jerk}$ | 0.335 | 0.076 | 0.177 | <0.05 | 0.502 | 0.989 | 0.575 | 0.325 | 0.465 | 0.708 | 0.509 | 0.935 | 0.431 | 0.464
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.652 | 0.514 | 0.072 | <0.05 | 0.475 | 0.797 | 0.625 | 0.083 | 0.343 | 0.085 | 0.331 | 0.067 | 0.459 | 0.464
|  |  | SD
R1 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.512 | 0.903 | 0.912× | <0.05 | 0.675 | 0.060 | 0.550 | 0.482 | 0.549 | 0.602 | 0.603 | 0.269 | 0.544 | 0.645
$DeepQTest_{Jerk}$ | 0.260 | <0.05 | 0.245 | <0.05 | 0.823 | <0.05 | 0.625 | 0.099 | 0.431 | 0.453 | 0.500 | 1.000 | 0.361 | 0.136
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.270 | <0.05 | 0.050 | <0.05 | 0.698 | <0.05 | 0.575 | 0.341 | 0.383 | 0.194 | 0.390 | 0.234 | 0.371 | 0.166
R2 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.087 | <0.05 | 0.865× | <0.05 | 0.760 | <0.05 | 0.450 | 0.394 | 0.568 | 0.466 | 0.550 | 0.592 | 0.690 | 0.103
$DeepQTest_{Jerk}$ | 0.113 | <0.05 | 0.147 | <0.05 | 0.642 | 0.126 | 0.600 | 0.178 | 0.331 | 0.065 | 0.341 | 0.087 | 0.534 | 0.860
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.345 | 0.337 | 0.100 | <0.05 | 0.328 | 0.064 | 0.650 | <0.05 | 0.259 | <0.05 | 0.295× | <0.05 | 0.302× | <0.05
R3 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.522 | 0.603 | 0.703× | <0.05 | 0.492 | 0.946 | 0.550 | 0.394 | 0.466 | 0.718 | 0.506 | 0.955 | 0.480 | 0.966
$DeepQTest_{Jerk}$ | 0.240 | <0.05 | 0.048 | <0.05 | 0.510 | 0.925 | 0.625 | 0.064 | 0.274 | <0.05 | 0.285× | <0.05 | 0.256× | <0.05
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.275 | <0.05 | 0.040 | <0.05 | 0.502 | 0.989 | 0.575 | 0.302 | 0.330 | 0.063 | 0.328 | 0.061 | 0.338× | <0.05
R4 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.205 | <0.05 | 0.885× | <0.05 | 0.605 | 0.262 | 0.550 | 0.447 | 0.551 | 0.571 | 0.552 | 0.563 | 0.329 | 0.065
$DeepQTest_{Jerk}$ | 0.120 | <0.05 | 0.240 | <0.05 | 0.613 | 0.229 | 0.575 | 0.270 | 0.346 | 0.094 | 0.364 | 0.140 | 0.300× | <0.05
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.450 | 0.386 | 0.092 | <0.05 | 0.535 | 0.715 | 0.525 | 0.740 | 0.321 | <0.05 | 0.334 | 0.069 | 0.431 | 0.464
|  |  | SN
R1 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.323 | 0.056 | 0.815× | <0.05 | 0.522 | 0.818 | 0.575 | 0.270 | 0.430 | 0.449 | 0.441 | 0.529 | 0.406 | 0.315
$DeepQTest_{Jerk}$ | 0.152 | <0.05 | 0.180 | <0.05 | 0.630 | 0.164 | 0.675 | <0.05 | 0.250 | <0.05 | 0.251× | <0.05 | 0.273× | <0.05
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.335 | 0.076 | 0.055 | <0.05 | 0.713 | <0.05 | 0.600 | 0.208 | 0.380 | 0.183 | 0.417 | 0.378 | 0.479 | 0.828
R2 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.168 | <0.05 | 0.848× | <0.05 | 0.790 | <0.05 | 0.500 | 1.000 | 0.646 | 0.105 | 0.626 | 0.161 | 0.650 | 0.106
$DeepQTest_{Jerk}$ | 0.080 | <0.05 | 0.135 | <0.05 | 0.580 | 0.394 | 0.625 | 0.083 | 0.326 | 0.058 | 0.318× | <0.05 | 0.458 | 0.654
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.390 | 0.133 | 0.077 | <0.05 | 0.235× | <0.05 | 0.625 | 0.083 | 0.239 | <0.05 | 0.261× | <0.05 | 0.302× | <0.05
R3 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.688× | <0.05 | 0.750× | <0.05 | 0.640 | 0.133 | 0.500 | 1.000 | 0.499 | 1.000 | 0.468 | 0.729 | 0.390 | 0.237
$DeepQTest_{Jerk}$ | 0.325 | 0.060 | 0.010 | <0.05 | 0.500 | 1.000 | 0.550 | 0.482 | 0.383 | 0.202 | 0.321 | 0.053 | 0.155× | <0.05
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.287 | <0.05 | 0.005 | <0.05 | 0.323 | 0.056 | 0.550 | 0.482 | 0.372 | 0.165 | 0.356 | 0.120 | 0.292× | <0.05
R4 | $DeepQTest_{TTC}$ | $DeepQTest_{DTO}$ | 0.355 | 0.273 | 0.895× | <0.05 | 0.552 | 0.579 | 0.500 | 1.000 | 0.574 | 0.417 | 0.576 | 0.403 | 0.416 | 0.371
$DeepQTest_{Jerk}$ | 0.198 | <0.05 | 0.405 | 0.310 | 0.583 | 0.379 | 0.550 | 0.482 | 0.395 | 0.255 | 0.393 | 0.245 | 0.315× | <0.05
$DeepQTest_{DTO}$ | $DeepQTest_{Jerk}$ | 0.347 | 0.064 | 0.098 | <0.05 | 0.542 | 0.655 | 0.550 | 0.482 | 0.335 | 0.071 | 0.333 | 0.067 | 0.341 | 0.087