11institutetext: Department of Informatics, Bioengineering, Robotics, and
Systems Engineering, University of Genoa, Via All’Opera Pia 13, 16145 Genoa,
Italy.
11email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Probabilistic Collision Constraint for Motion Planning in Dynamic
Environments

Antony Thomas  Fulvio Mastrogiovanni  Marco Baglietto

###### Abstract

Online generation of collision free trajectories is of prime importance for
autonomous navigation. Dynamic environments, robot motion and sensing
uncertainties adds further challenges to collision avoidance systems. This
paper presents an approach for collision avoidance in dynamic environments,
incorporating robot and obstacle state uncertainties. We derive a tight upper
bound for collision probability between robot and obstacle and formulate it as
a motion planning constraint which is solvable in real time. The proposed
approach is tested in simulation considering mobile robots as well as
quadrotors to demonstrate that successful collision avoidance is achieved in
real time application. We also provide a comparison of our approach with
several state-of-the-art methods.

##  1 Introduction

Safe and reliable motion planning is an important problem in many robotic
applications. In many real-world applications, for example, in crowded and
dynamic environments such as factories or living spaces, robots are in close
proximity to humans and other robots thus making online computation of
collision free trajectories vital. However, robot state estimates are often
uncertain due to actuation errors, imperfect sensing, and incomplete knowledge
of the environment. This leads to reasoning regarding these uncertainties
during motion planning, localization and while estimating the motions of other
robots or humans. Therefore, the probability of colliding with obstacles is
thus computed incorporating these uncertainties. Furthermore, the collision
probability computation needs to be reasonably fast to be operable in real
time.

Various methods exist to model the uncertainties arising during collision
avoidance planning. Similarly to other approaches [9, 28, 27, 2, 37, 35], in
this paper we model the uncertainties using Gaussian distributions. The robot
and obstacle locations are thus parameterized as Gaussian probability
distribution functions (pdfs). Moreover, uncertain environments are such that
they often preclude the existence of collision free trajectories [1]. For
example, the Gaussian pdf representation assigns to both robot and obstacle
locations a non-zero probability anywhere in the environment. Thus, suitable
trajectories are often computed such that the collision probability falls
within some threshold. Yet, most approaches tend to over estimate the
collision probability and thereby compute sub-optimal trajectories or in some
cases pronounce plans to be infeasible. Thus, to compute safe and efficient
trajectories, computing tight collision probability bounds is essential.

In this paper, we develop an accurate constraint for collision avoidance
during motion planning. For a specific collision probability threshold, the
collision avoidance constraint can then be used for online Model Predictive
Control (MPC) optimization. To be robust to uncertain environments, robot
motion and sensing uncertainties (and obstacle uncertainties) are incorporated
by propagating the uncertainties within the MPC framework. The resulting
collision probability bound is more tighter as compared to prior approaches.
The proposed approach is valid in both 2D and 3D domains subject to the
assumption of spherical geometry for robot, obstacles and we evaluate our
method in Gazebo based simulations (see Fig. 1) in multi-robot setting with
both mobile robots and quadrotors.

(a)

(b)

Figure 1: Snapshots from experiments with a team of (a) mobile robots and (b)
quadrotors.

The paper is organized as follows. In Section 2 we discuss some of the prior
approaches for probabilistic collision avoidance. Notations are introduced in
Section 3. We derive our probabilistic collision constraint and provide a
comparison with other prior methods in Section 4. In Section 3 we validate our
method under different multi-robot scenarios.

##  2 Related Work

In this section we provide a brief overview of existing works on collision
probability computation for motion planning. Several approaches exist that
incorporate various uncertainties to compute collision probabilities. The
starting point of all approaches is to formulate the collision constraint,
that is, the conditions under which a collision occurs between a robot and an
obstacle. The methods differ in their formulation of collision constraint due
to different assumptions regarding the shape of the robot and the obstacles
(for example, point, spherical, ellipsoidal, or rectangular shapes for the
robot and the obstacle), modeling of uncertainties. Overall, most approaches
tend to be overly conservative and provide loose upper bounds. This can lead
to sub-optimal plans or in some case render plans infeasible and thus it is
desirable to compute accurate collision probabilities to ensure safe and
efficient trajectories.

Bounding volume approaches enlarge the robot and obstacles with a larger
volume that them, mostly employing their 3-$\sigma$ uncertainty ellipsoids [5,
21]. In [26] exact collision checking with conservative bounds on the position
of the moving obstacles is performed. Convex hulls of robot links enlarged
according to the sigma standard deviation are used in [23]. An upper bound for
collision probability is computed using rectangular bounding boxes for both
the robot and the obstacle in [15]. Patil et al. [28] truncate the a priori
Gaussian robot state distributions [20] that collide with the obstacle. The
truncated distributions account for collision free samples and are then
propagated to obtain collision probability estimates. Truncating propagated
distributions is also employed in [24] to compute risk-aware and
asymptotically optimal trajectories.

Exact collision probability can be computed by marginalizing the joint
distribution between the robot and obstacle locations [8]. This integration is
then performed over the set of robot and obstacle locations that satisfy the
collision constraint. However, there is no closed form solution to the
integral and numerical integration or Monte Carlo (MC) techniques are employed
[32]. Yet, numerical integration tend to be computationally expensive and
therefore approximate MC methods are employed. MC integration results in a
double summation and this is approximated to a single summation in [22].
Another related approach is the Monte Carlo Motion Planning (MCMP) approach of
Janson et al. [18]. They solve a deterministic motion planning problem with
inflated obstacles. Most often, it is convenient to model the collision
condition as a constraint of an optimal control problem. Yet, MC approaches
tend to be computationally expensive and hard to model within an optimization
framework. Assuming that the robot size is negligible, the integration can be
approximated to a product of the joint distribution evaluated at the robot and
obstacle mean locations and the volume occupied by the robot. Du Toit and
Burdick [9] compute the joint density evaluated at the robot center, whereas
in [27] an upper bound is computed by evaluating the density at the surface of
the robot.

Assuming the robot and the obstacles to be spherical objects, the distance
between spheres is used to formulate the collision constraint as a quadratic
form in random variables in [35, 36]. The cumulative distribution function
(cdf) of the quadratic form gives the required collision probability. Another
popular approach is based on chance-constraints. These methods find an optimal
sequence of control inputs subject to constraints, that is, collision
probability thresholds [4]. Convex polygonal obstacles are considered in [4]
and a Gaussian parameterization allows for obtaining constraints in terms of
the mean and covariance of the robot and obstacle locations. Chance-
constraints are employed in [37] by linearizing the nonlinear collision
constraints to derive an approximate upper bound. Newton’s method combined
with chance-constraints is used in [34] to obtain an upper bound for collision
probability. Future obstacle trajectories are predicted using a Gaussian
Process (GP) based technique that learns the mapping from states to trajectory
derivatives in [1]. In [11] the first-exist times for Brownian motions are
leveraged to compute collision probabilities. [2] focus exclusively on
environment uncertainty and formalize a notion of shadows, a geometric
equivalent of confidence intervals for uncertain obstacles. Though shadows
fundamentally give rise to loose bounds, the computational complexity of
bounding the collision probability is greatly reduced. To incorporate
uncertainties, obstacles are modelled as polytopes with Gaussian-distributed
faces in [33].

Risk-aware motion planning assigns risk to certain regions and paths are
considered by the planning algorithm only if the risk obtained in different
regions are below some predefined thresholds [6]. Planning a collision-free
path of a robot in the presence of risk zones by penalizing the time spent in
these zones is presented in [31]. Jasour et al.[19] employ risk contours map
that takes into account the risk information (uncertainties in location, size
and geometry of obstacles) to obtain safe paths with bounded risks. A related
approach for randomly moving obstacles is investigated in [14]. Collision
avoidance in the context of human-robot interaction are presented in [3, 12].
Formal verification methods have also been used to construct safe plans [7,
30].

##  3 Preliminaries

Throughout this paper vectors will be assumed to be column vectors and will be
denoted by bold lower case letters, that is, x and its components will be
denoted by lower case letters. Transpose of x will be denoted by
$\textbf{x}^{T}$ and its Euclidean norm by
$\mathinner{\\!\left\lVert\textbf{x}\right\rVert}=\sqrt{\textbf{x}^{T}\textbf{x}}$.
The mean of a random vector will be denoted by $\bm{\mu}$, the corresponding
covariance by $\Sigma$ and the expected value by
$\operatorname{\mathbb{E}}(\textbf{x})$. A multivariate Gaussian distribution
of x with mean $\bm{\mu}$ and covariance $\Sigma$ will be denoted using the
notation $\textbf{x}\sim\mathcal{N}(\bm{\mu},\Sigma)$. Matrices will be
denoted by capital letters, that is, $M$, with its trace denoted by $tr(M)$.
The identity matrix will be denoted by $I$ or $I_{n}$ when the dimension needs
to be stressed. A diagonal matrix with diagonal elements
$\lambda_{1},\ldots,\lambda_{n}$ will be denoted by
$diag(\lambda_{1},\ldots,\lambda_{n})$. Sets will be denoted using mathcal
fonts, that is, $\mathcal{S}$. Unless otherwise mentioned, subscripts on
vectors/matrices will be used to denote time indexes and (whenever necessary)
superscripts will be used to indicate the robot or the object that it
represents. For example, $\textbf{x}_{k}^{i}$ represents the state of robot
$i$ at time $k$. The notation $P(\cdot)$ will be used to denote the
probability of an event and the pdf will be denoted by $p(\cdot)$.

At any time $k$, we denote the robot state by $\textbf{x}_{k}$, the acquired
measurement from objects is denoted by $\textbf{z}_{k}$ and the applied
control action is denoted as $\textbf{u}_{k}$. We also make the following
assumptions: (1) the uncertainties are modeled using Gaussian distributions,
(2) the robot and obstacles are assumed to be non-deformable spherical
objects.

To describe the dynamics of the robot, we consider a standard motion model
with Gaussian distributed noise

$\textbf{x}_{k+1}=f(\textbf{x}_{k},\textbf{u}_{k})+n_{k}\ ,\
n_{k}\sim\mathcal{N}(0,R_{k})$ (1)

where $n_{k}$ is the random unobservable noise, modeled as a zero mean
Gaussian distribution. Objects are detected through the robot’s sensors and
assuming known data association, the observation model can be written as

$\textbf{z}_{k}=h(\textbf{x}_{k})+v_{k}\ ,\ v_{k}\sim\mathcal{N}(0,Q_{k})$ (2)

##  4 Probabilistic Collision Avoidance

###  4.1 Collision Constraint

We denote by $\mathcal{R}$ the set of all points occupied by a rigid-body
robot at any given time. Similarly, let $\mathcal{S}$ represent the set of all
points occupied by a rigid-body obstacle. A collision occurs if there exits a
point such that it is in both $\mathcal{R}$ and $\mathcal{S}$. Thus the
collision condition is defined as

$\mathcal{R}\cap\mathcal{S}\neq\\{\phi\\}$ (3)

and we denote the probability of collision as
$P\left(\mathcal{R}\cap\mathcal{S}\neq\\{\phi\\}\right)$. In this work we
assume spherical geometries for $\mathcal{R}$ and $\mathcal{S}$ with radii
$r_{1}$ and $s_{1}$, respectively. We assign body-fixed reference frames to
robot and obstacle centers located at $\textbf{x}_{k}$ and $\textbf{s}_{k}$,
respectively in the global frame. By abuse of notation we will use
$\textbf{x}_{k}$ and $\textbf{s}_{k}$ equivalently to $\mathcal{R}$ and
$\mathcal{S}$. However, when we talk about the distribution of their
locations, we refer to the distribution of their centers (the body-fixed
frame). The collision condition is thus defined in terms of the body-fixed
frames as

$\mathcal{C}_{\textbf{x}_{k},\textbf{s}_{k}}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{R}\cap\mathcal{S}\neq\\{\phi\\}$ (4)

We recall here that the locations of the robot and the obstacles are in
general uncertain. Let us now consider a robot and an obstacle at any given
time instant $k$, distributed according to the Gaussians
$\textbf{x}_{k}\sim\mathcal{N}\left(\bm{\mu}_{\textbf{x}_{k}},\Sigma_{\textbf{x}_{k}}\right)$
and
$\textbf{s}_{k}\sim\mathcal{N}\left(\bm{\mu}_{\textbf{s}_{k}},\Sigma_{\textbf{s}_{k}}\right)$,
respectively. Since the robot and the obstacles are assumed to be spherical
objects, the collision constraint is written as

$\mathinner{\\!\left\lVert\textbf{x}_{k}-\textbf{s}_{k}\right\rVert}^{2}\leq(r_{1}+s_{1})^{2}$
(5)

Thus 5 is equivalent to $\mathcal{C}_{\textbf{x}_{k},\textbf{s}_{k}}$. Let us
denote the difference between the two random variables by
$\textbf{w}=\textbf{x}_{k}-\textbf{s}_{k}$. Using the expression for the
difference between two Gaussian distributions, we have
$\textbf{w}\sim\mathcal{N}\left(\bm{\mu}_{\textbf{x}_{k}}-\bm{\mu}_{\textbf{s}_{k}},\Sigma_{\textbf{x}_{k}}+\Sigma_{\textbf{s}_{k}}\right)$.
The collision constraint in (5) can now be written in terms of w,

$\textbf{y}=\mathinner{\\!\left\lVert\textbf{w}\right\rVert}^{2}=\textbf{w}^{T}\textbf{w}\leq(r_{1}+s_{1})^{2}$
(6)

where y is a random vector distributed according to the squared $L_{2}$-norm
of w.

###### Proposition 1

A symmetric matrix $A\in\mathbb{R}^{n\times n}$ with orthonormal eigenvectors
$q_{i}$ can be factorized as

$A=Q\Lambda Q^{T}$ (7)

where the columns of $Q$ correspond to the orthonormal eigenvectors $q_{i}$
and $\Lambda$ is a diagonal matrix comprised of the corresponding eigenvalues
of $A$.

###### Lemma 1

For a symmetric matrix $A\in\mathbb{R}^{n\times n}$ and a random vector x, we
have

$\textbf{x}^{T}A\textbf{x}\leq\lambda_{max}\mathinner{\\!\left\lVert\textbf{x}\right\rVert}^{2}$
(8)

where $\lambda_{max}$ is the maximum eigenvalue of $A$.

###### Proof

From Proposition 1, we have

$\begin{split}\textbf{x}^{T}A\textbf{x}&=\textbf{x}^{T}Q\Lambda
Q^{T}\textbf{x}=\left(Q^{T}\textbf{x}\right)^{T}\Lambda\left(Q^{T}\textbf{x}\right)=\sum_{i=1}^{n}\lambda_{i}(q_{i}^{T}\textbf{x})^{2}\\\
&\leq\lambda_{max}\sum_{i=1}^{n}(q_{i}^{T}\textbf{x})^{2}=\lambda_{max}\mathinner{\\!\left\lVert\textbf{x}\right\rVert}^{2}\\\
\end{split}$

where we have used the fact that the eigenvectors are orthonormal.

###### Proposition 2

For any random variable x, the probability of an event $P(\textbf{x}\leq x)$
is given by its cumulative distribution function (cdf) $F_{\textbf{x}}(x)$,
that is,

$F_{\textbf{x}}(x)=P(\textbf{x}\leq x),\quad-\infty<x<+\infty$ (9)

###### Proposition 3

For n-dimensional $\textbf{x}\sim\mathcal{N}(\bm{\mu},\Sigma)$

$y=(\textbf{x}-\bm{\mu})^{T}\Sigma^{-1}(\textbf{x}-\bm{\mu})\sim\chi^{2}_{n}$
(10)

where $\chi^{2}_{n}$ denotes the chi-squared distribution with $n$ degrees of
freedom.

Let $F_{chi}$ be the cdf of a chi-squared distribution with $n$ degrees of
freedom and let $\textbf{x}\sim\mathcal{N}(\bm{\mu},\Sigma)$, then for any
$-\infty<x<+\infty$ we have

$P((\textbf{x}-\bm{\mu})^{T}\Sigma^{-1}(\textbf{x}-\bm{\mu})\leq
x)=F_{chi}(x)$ (11)

Alternatively, for any $0\leq\epsilon\leq 1$, we have

$P((\textbf{x}-\bm{\mu})^{T}\Sigma^{-1}(\textbf{x}-\bm{\mu})\leq
F_{chi}^{-1}(\epsilon))=\epsilon$ (12)

###### Lemma 2

Let $\textbf{x}\sim\mathcal{N}(\bm{\mu},\Sigma)$,
$\mathinner{\\!\left\lVert\textbf{x}\right\rVert}^{2}\leq\alpha$, $F_{chi}$ be
the cdf of a chi-squared distribution and

$P((\textbf{x}-\bm{\mu})^{T}\Sigma^{-1}(\textbf{x}-\bm{\mu})\leq
F_{chi}^{-1}(\epsilon))=\epsilon$

Then
$\lambda_{max}\left(\alpha-2\textbf{x}^{T}\bm{\mu}+\bm{\mu}^{T}\bm{\mu}\right)\leq
F_{chi}^{-1}(\epsilon)$, where $\lambda_{max}$ is the maximum eigenvalue of
$\Sigma^{-1}$.

###### Proof

From Lemma 1, it follows that

$(\textbf{x}-\bm{\mu})^{T}\Sigma^{-1}(\textbf{x}-\bm{\mu})\leq\lambda_{max}\mathinner{\\!\left\lVert\textbf{x}-\bm{\mu}\right\rVert}^{2}$
(13)

where $\lambda_{max}$ is the maximum eigenvalue of $\Sigma^{-1}$. Expanding
the right-hand side of (13) and using the fact that
$\mathinner{\\!\left\lVert\textbf{x}\right\rVert}^{2}\leq\alpha$, we get

$(\textbf{x}-\bm{\mu})^{T}\Sigma^{-1}(\textbf{x}-\bm{\mu})\leq\lambda_{max}\left(\alpha-2\textbf{x}^{T}\bm{\mu}+\bm{\mu}^{T}\bm{\mu}\right)$
(14)

Thus, for $(\textbf{x}-\bm{\mu})^{T}\Sigma^{-1}(\textbf{x}-\bm{\mu})\leq
F_{chi}^{-1}(\epsilon)$ it suffices that
$\lambda_{max}\left(\alpha-2\textbf{x}^{T}\bm{\mu}+\bm{\mu}^{T}\bm{\mu}\right)\leq
F_{chi}^{-1}(\epsilon)$.

Note that the collision constraint in (6) is of the form
$\mathinner{\\!\left\lVert\textbf{x}\right\rVert}^{2}\leq\alpha$ and this
allows us to define a notion of maximum allowable collision probability. We
remind the readers that $\mathcal{C}_{\textbf{x}_{k},\textbf{s}_{k}}$
represents the collision condition and is therefore equivalent to (5). We now
define the collision constraint that satisfy the required collision
probability threshold.

###### Lemma 3

Given n-dimensional $\textbf{x}\sim\mathcal{N}(\bm{\mu},\Sigma)$, and $P(\
\mathinner{\\!\left\lVert\textbf{x}\right\rVert}^{2}\leq\alpha)\leq\epsilon$,
then

$\lambda_{max}\left(\alpha-2\textbf{x}^{T}\bm{\mu}+\bm{\mu}^{T}\bm{\mu}\right)\leq
F_{chi}^{-1}(\epsilon)$ (15)

where $\lambda_{max}$ is the maximum eigenvalue of $\Sigma^{-1}$ and $F_{chi}$
is the cdf of the chi-squared distribution with n degrees of freedom.

###### Proof

We have

$\begin{split}P(\
\mathinner{\\!\left\lVert\textbf{x}\right\rVert}^{2}\leq\alpha)&=P(\textbf{x}^{T}\textbf{x}\leq\alpha)=P((\textbf{x}-\bm{\mu}+\bm{\mu})^{T}(\textbf{x}-\bm{\mu}+\bm{\mu})\leq\alpha)\\\
&=P((\textbf{x}-\bm{\mu})^{T}(\textbf{x}-\bm{\mu})+2(\textbf{x}-\bm{\mu})^{T}\bm{\mu}+\bm{\mu}^{T}\bm{\mu}\leq\alpha)\\\
&=P(\
\mathinner{\\!\left\lVert\textbf{x}-\bm{\mu}\right\rVert}^{2}\leq\alpha-2\textbf{x}^{T}\bm{\mu}+\bm{\mu}^{T}\bm{\mu})\\\
&=P(\lambda_{max}\mathinner{\\!\left\lVert\textbf{x}-\bm{\mu}\right\rVert}^{2}\leq\lambda_{max}(\alpha-2\textbf{x}^{T}\bm{\mu}+\bm{\mu}^{T}\bm{\mu}))\end{split}$

where $\lambda_{max}$ is the maximum eigenvalue of $\Sigma^{-1}$. Now from
Lemma 1 it follows that

$P(\lambda_{max}\mathinner{\\!\left\lVert\textbf{x}-\bm{\mu}\right\rVert}^{2}\leq\lambda_{max}(\alpha-2\textbf{x}^{T}\bm{\mu}+\bm{\mu}^{T}\bm{\mu}))\\\
=P((\textbf{x}-\bm{\mu})^{T}\Sigma^{-1}(\textbf{x}-\bm{\mu})\leq\lambda_{max}(\alpha-2\textbf{x}^{T}\bm{\mu}+\bm{\mu}^{T}\bm{\mu}))=P(\mathinner{\\!\left\lVert\textbf{x}\right\rVert}^{2}\leq\alpha)=\epsilon$

The required result then directly follows from Lemma 2.

Since the collision constraint in (6) is a Gaussian distribution, for a
collision probability threshold of $\epsilon$ we can directly use the
constraint in (15). We now state the following lemma which is a direct
consequence of Lemma 3.

###### Lemma 4

Given n-dimensional $\textbf{x}\sim\mathcal{N}(\bm{\mu},\Sigma)$, and $P(\
\mathinner{\\!\left\lVert\textbf{x}\right\rVert}^{2}\leq\alpha)\leq\epsilon$,
then

$P(\ \mathinner{\\!\left\lVert\textbf{x}\right\rVert}^{2}\leq\alpha)\leq
F_{chi}^{-1}\left(\lambda_{max}(\alpha-2\textbf{x}^{T}\bm{\mu}+\bm{\mu}^{T}\bm{\mu})\right)$
(16)

###  4.2 Objective Function

We formulate the collision avoidance problem as an optimization problem. At
each time instant $k$, the robot plans for $L$ look-ahead steps and minimizes
an objective function $J_{k}$, subject to collision and other constraints. The
optimization problem can then be formally stated as

$\begin{split}&\underset{\textbf{x}_{k\mathrel{\mathop{\mathchar
58\relax}}k+L},\textbf{u}_{k\mathrel{\mathop{\mathchar
58\relax}}k+L-1}}{\min}\quad J_{k}\\\
&s.t.\quad\textbf{x}_{k+1}=f(\textbf{x}_{k},\textbf{u}_{k})\\\ &\quad\
\,\quad\textbf{u}_{k+l}\in\textbf{U}\\\ &\quad\ \,\quad
P\left(\mathcal{C}_{\textbf{x}_{k+l},\textbf{s}_{k}^{i}}\right)\leq\epsilon\end{split}$
(17)

where

$J_{k}=\sum_{l=0}^{L-1}c_{l}(\textbf{x}_{k+l},\textbf{u}_{k+l})+c_{L}(\textbf{x}_{k+L})$
(18)

with $c_{l}$ denoting the cost term at time $k+l$ and $c_{L}$ denoting the
terminal cost, $\textbf{x}_{k+1}=f(\textbf{x}_{k},\textbf{u}_{k})$ is the
robot dynamics (1), $\textbf{u}_{k+l}\in\textbf{U}$ constraints the control
inputs to lie within the feasible set U and
$P\left(\mathcal{C}_{\textbf{x}_{k},\textbf{s}_{k}^{i}}\right)\leq\epsilon$
enforces a collision probability threshold of $\epsilon$ with obstacles
$\textbf{s}_{k}^{i}$.

We recall here that to determine the constraint
$P\left(\mathcal{C}_{\textbf{x}_{k+l},\textbf{s}_{k}^{i}}\right)\leq\epsilon$
in (17) it is required to evaluate the constraint in (15), which depends on
the uncertainty or the covariance at each time step. Thus the uncertainty
needs to be propagated at each time step to compute the collision probability
constraint. In this paper we use the Extended Kalman Filter (EKF) uncertainty
propagation; other approaches can be found in [25]. Note that the covariance
dynamics dependent on the robot state and control inputs and hence require
$\frac{L}{2}(n_{\textbf{x}}^{2}+n_{\textbf{x}})$ [16] ($n_{\textbf{x}}$ is the
dimension of x) additional variables in the optimization problem, increasing
the computation time significantly. Thus, similar to [16, 37], we approximate
the uncertainty evolution by propagating the robot uncertainties based on its
last-loop state and control inputs.

###  4.3 Comparison to Other Approaches

We provide a comparison with several state-of-the-art methods using a robot
and a close-by obstacle. For this comparison, we use a 2D example, however our
approach is not limited to 2D scenarios and is equally applicable in 3D
scenarios as it can be seen in Section 3. The robot is located at $(0.38,0)$ m
with radius $0.2$ m and covariance $diag(0.04,0.04)$ $\textrm{m}^{2}$. The
obstacle is located at the origin with radius $0.2$ m. The collision
probability values can be seen in Table 1. To validate the value computed
using our approach, we compute the exact collision probability by performing
numerical integration. Given the current robot state $\textbf{x}_{k}$ and the
obstacle state $\textbf{s}_{k}$, the collision probability is given by

$P\left(\mathcal{C}_{\textbf{x}_{k},\textbf{s}_{k}}\right)=\int_{\textbf{x}_{k}}\int_{\textbf{s}_{k}}I_{c}(\textbf{x}_{k},\textbf{s}_{k})p(\textbf{x}_{k},\textbf{s}_{k})$
(19)

where $I_{c}$ is an indicator function defined as

$I_{c}(\textbf{x}_{k},\textbf{s}_{k})=\begin{cases}1\ &\text{if}\
\mathcal{R}\cap\mathcal{S}\neq\\{\phi\\}\\\ 0\ &\text{otherwise}.\end{cases}$
(20)

and $p(\textbf{x}_{k},\textbf{s}_{k})$ is the joint distribution of the robot
and the obstacle. The numeric integral of (19) gives the exact value and is
used to compare the tightness of the upper bound computed using our approach.
As seen from Table 1 the value computed using our approach provides a tighter
bound when compared to other approaches. The double summation of numerical
integration is approximated to a single summation in [22] and this results in
a much higher value. Other approaches compute loose upper bounds and hence the
resulting values are significantly higher. Our approach thus computes a
tighter upper bound.

Table 1: Comparison of collision probability methods.

Methods | Collision | Computation
---|---|---
| probability | time (ms)
Numerical integral | 0.1728 |  9168.9 $\pm$ 258.0
Approximate Numerical integral [22] | 0.4280 |  18.30 $\pm$ 3.90
Bounding volume [26, 21] | 1 |  0.1480 $\pm$ 0.4411
Maximum probability approximation [27] | 1 |  101.6 $\pm$ 23.86
Chance constraint [37] | 0.5398 |  0.3917 $\pm$ 0.1278
Rectangular bounding box [15] | 0.1601 |  0.067 $\pm$ 0.0070
Our approach | 0.1772 |  0.588 $\pm$ 0.13

##  5 Results

In this section we describe our implementation and then evaluate the
capabilities of our approach. Simulations are performed in the Gazebo
environment with mobile robots as well as quadrotors. The mobile robot
kinematics is as follows

$\textbf{x}_{k+1}=\begin{bmatrix}x_{k}-\frac{v_{k}}{\omega_{k}}\sin(\theta_{k})+\frac{v_{k}}{\omega_{k}}\sin(\theta_{k}+\omega_{k}\Delta
t)\\\
y_{k}+\frac{v_{k}}{\omega_{k}}\cos(\theta_{k})-\frac{v_{k}}{\omega_{k}}\cos(\theta_{k}+\omega_{k}\Delta
t)\\\ \theta_{k}+\omega_{k}\Delta t\end{bmatrix}+n_{k}$ (21)

where the applied control $\textbf{u}_{k}=(v_{k},\omega_{k})^{T}$ is made up
of the linear and angular velocities and $n_{k}$ is the noise as defined in
Section 3. We refer the readers to [10] for the quadrotor dynamics. The ground
truth odometry from Gazebo is used to measure the pose of the robot, mimicking
a motion capture system. This measurement is then corrupted with noise which
is zero mean and is used to estimate the state of the robots employing an EKF.
The optimization of (17) is set up in ACADO [17] which generates a C++
template to run the MPC problem (17), and is then modified according to the
execution platform. For quadrotor control, we use the publicly available RPG-
MPC111https://github.com/uzh-rpg/rpg˙mpc [10] which is also based on ACADO and
modify it to meet our requirements. A look-ahead horizon of $L=1$ second is
used with a discretization of 0.1 seconds for mobile robots and for the
quadrotors we use $L=2$ seconds. The performance is evaluated on an Intel®
Core i7-6500U<EMAIL_ADDRESS>with 8GB RAM under Ubuntu 16.04 LTS.

Comparison to bounding volume approaches: Bounding volume methods [26, 21]
presents a straightforward approach for computing collision probability under
uncertainty by enlarging the robot and obstacles by their 3$-\sigma$
ellipsoids. We provide an efficiency comparison of such methods with ours. We
consider a scenario in which a mobile robot navigates from $(0,0)$ m to
$(3,0)$ m with an obstacle of radius $0.2$ m at $(1.5,0)$ m. We begin with a
measurement noise of
$\Sigma=diag(0.02\textrm{m}^{2},0.02\textrm{m}^{2},1.2\textrm{deg}^{2})$ and
increase it to 4$\Sigma$ and 16$\Sigma$. We define the following metrics to
compare the efficiency: $d-$ minimum distance between the robot and the
obstacle, $l-$ total trajectory length, and $T-$ total trajectory duration.
The results are shown in Table 2 where each given value is an average over 10
different simulations. In all the three cases, the trajectory length and
duration quantities certify our approach as most efficient. This is more
evident as the measurement noise increases as we compute a tight upper bound.

Table 2: Collision probability efficiency with varying measurement noise. | Measurement noise
---|---
| $\Sigma$ |  4$\Sigma$ |  16$\Sigma$
Method |  $d$(m) |  $l$(m) |  $T$(s) |  $d$(m) |  $l$(m) |  $T$(s) |  $d$(m) |  $l$(m) |  $T$(s)
Bounding volume [26, 21] |  0.50 |  3.31 |  16.19 |  0.70 |  3.90 |  16.34 |  0.81 |  4.26 |  16.54
Our method |  0.49 |  3.28 |  16.01 |  0.58 |  3.59 |  16.13 |  0.61 |  3.71 |  16.29

Mobile robot scenarios: In this setting we consider multiple mobile robots
exchanging their initial positions with each robot considering every other
robot as a dynamic obstacle. To this end, the trajectory (pose and covariance)
of each robot is communicated to other robots. The trajectories for two and
four mobile robots exchanging their positions can be seen in Fig. 2a and Fig.
2b. We use a collision probability threshold of $0.1$ and a minimum separation
of $0.2$ meters is achieved between the robots. In both the cases, a
measurement noise of
$\Sigma=diag(0.02\textrm{m}^{2},0.02\textrm{m}^{2},1.2\textrm{deg}^{2})$ is
used to corrupt the ground truth odometry which is then used to estimate the
robot states using EKF. The simulation was run 10 times and the robots
successfully avoided collisions in all the runs. For collision probability
thresholds above $0.2$ the success rate was less $100\%$. The average
computation time for MPC planning is $9.50$ ms and Fig. 2c shows the mean MPC
planning time for each robot. The low computation time thus allows for real
time online planning.

(a)

(b)

(c)

Figure 2: (a), (b) Simulation results of mobile robots exchanging their
positions. The solid lines represent the trajectories executed by the robots.
(c) Mean MPC planning time for four robots R1, R2, R3 and R4, respectively.

Quadrotor scenarios: Similar to the scenario discussed above, here we consider
multiple quadrotors exchanging their initial positions. Each quadrotor
communicates its trajectory, both pose and covariance, with others. The top
view and side view for four and six quadrotors exchanging their initial
positions can be seen in Fig. 3. Close distances between quadrotors are
observed due to our tight bound. We also observed that a success rate of
$100\%$ is achieved for collision probability thresholds below $0.1$. Mean
computation time for MPC planning is $3.05$ ms.

(a)

(b)

(a) Four quadrotors

(b) Six quadrotos

Figure 3: Simulation results of quadrotors exchanging their positions;
trajectories executed visualized by solid lines. The upper plots show the top
view (x-y) and the lower plots show the side view (x-z).

##  6 Conclusion

In this paper we have developed an approach for collision avoidance that
incorporates robot and obstacle state uncertainties and is solvable in real
time. A tight bound for collision probability is provided and a collision
constraint for online MPC planning is derived. The tightness of the bound is
validated by computing the numerical integral which provides the actual value.
A comparison with several state-of-the-art methods is provided and our method
is seen to give a tighter upper bound. We also compare the efficiency of our
approach with bounding volume methods under varied measurement noise. Multi-
robot simulations with both mobile robots and quadrotors are performed to
validate our approach.

Note that currently we assume spherical geometries for robot and obstacles.
Such an assumption is valid since any shape can be enclosed inside a sphere or
using multiple spheres. However, a more appropriate assumption is to consider
the minimum-volume enclosing ellipsoid [29]. For every convex polyhedron,
there exists a unique ellipsoid of minimal volume that contains the polyhedron
and is called the Löwner-John ellipsoid of the polyhedron [13]. Thus the
collision constraint is to be formulated based on the distance between the
ellipsoids. Furthermore, in some cases the assumption of Gaussian distribution
for robot state and other noises may not hold.

## References

  * [1] Aoude, G.S., Luders, B.D., Joseph, J.M., Roy, N., How, J.P.: Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns. Autonomous Robots 35(1), 51–76 (2013)
  * [2] Axelrod, B., Kaelbling, L.P., Lozano-Pérez, T.: Provably safe robot navigation with obstacle uncertainty. The International Journal of Robotics Research 37(13-14), 1760–1774 (2018)
  * [3] Bajcsy, A., Herbert, S.L., Fridovich-Keil, D., Fisac, J.F., Deglurkar, S., Dragan, A.D., Tomlin, C.J.: A scalable framework for real-time multi-robot, multi-human collision avoidance. In: 2019 international conference on robotics and automation (ICRA). pp. 936–943. IEEE (2019)
  * [4] Blackmore, L., Ono, M., Williams, B.C.: Chance-constrained optimal path planning with obstacles. IEEE Transactions on Robotics 27(6), 1080–1094 (2011)
  * [5] Bry, A., Roy, N.: Rapidly-exploring random belief trees for motion planning under uncertainty. In: IEEE International Conference on Robotics and Automation. pp. 723–730 (2011)
  * [6] Chow, Y., Ghavamzadeh, M., Janson, L., Pavone, M.: Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research 18(1), 6070–6120 (2017)
  * [7] Ding, X.C., Pinto, A., Surana, A.: Strategic planning under uncertainties via constrained markov decision processes. In: IEEE International Conference on Robotics and Automation. pp. 4568–4575 (2013)
  * [8] Du Toit, N.E., Burdick, J.W.: Robotic motion planning in dynamic, cluttered, uncertain environments. In: 2010 IEEE International Conference on Robotics and Automation. pp. 966–973. IEEE (2010)
  * [9] Du Toit, N.E., Burdick, J.W.: Probabilistic collision checking with chance constraints. IEEE Transactions on Robotics 27(4), 809–815 (2011)
  * [10] Falanga, D., Foehn, P., Lu, P., Scaramuzza, D.: PAMPC: Perception-aware model predictive control for quadrotors. In: 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 1–8. IEEE (2018)
  * [11] Frey, K., Steiner, T., How, J.: Collision Probabilities for Continuous-Time Systems Without Sampling. In: Proceedings of Robotics: Science and Systems. Corvalis, Oregon, USA (July 2020)
  * [12] Fridovich-Keil, D., Bajcsy, A., Fisac, J.F., Herbert, S.L., Wang, S., Dragan, A.D., Tomlin, C.J.: Confidence-aware motion prediction for real-time collision avoidance1. The International Journal of Robotics Research 39(2-3), 250–265 (2020)
  * [13] Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York (1988)
  * [14] Hakobyan, A., Kim, G.C., Yang, I.: Risk-Aware Motion Planning and Control Using CVaR-Constrained Optimization. IEEE Robotics and Automation Letters 4(4), 3924–3931 (2019)
  * [15] Hardy, J., Campbell, M.: Contingency planning over probabilistic obstacle predictions for autonomous road vehicles. IEEE Transactions on Robotics 29(4), 913–929 (2013)
  * [16] Hewing, L., Liniger, A., Zeilinger, M.N.: Cautious nmpc with gaussian process dynamics for autonomous miniature race cars. In: 2018 European Control Conference (ECC). pp. 1341–1348. IEEE (2018)
  * [17] Houska, B., Ferreau, H., Diehl, M.: ACADO Toolkit – An Open Source Framework for Automatic Control and Dynamic Optimization. Optimal Control Applications and Methods 32(3), 298–312 (2011)
  * [18] Janson, L., Schmerling, E., Pavone, M.: Monte Carlo motion planning for robot trajectory optimization under uncertainty. In: Robotics Research, pp. 343–361. Springer (2018)
  * [19] Jasour, A.M., Williams, B.C.: Risk contours map for risk bounded motion planning under perception uncertainties. Robotics: Science and Systems (2019)
  * [20] Johnson, N.L., Kotz, S., Balakrishnan, N.: Continuous univariate distributions. john wiley& sons. New York, NY (1994)
  * [21] Kamel, M., Alonso-Mora, J., Siegwart, R., Nieto, J.: Robust collision avoidance for multiple micro aerial vehicles using nonlinear model predictive control. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 236–243. IEEE (2017)
  * [22] Lambert, A., Gruyer, D., Saint Pierre, G.: A fast Monte Carlo algorithm for collision probability estimation. In: 10th IEEE International Conference on Control, Automation, Robotics and Vision. pp. 406–411 (2008)
  * [23] Lee, A., Duan, Y., Patil, S., Schulman, J., McCarthy, Z., Van Den Berg, J., Goldberg, K., Abbeel, P.: Sigma hulls for gaussian belief space planning for imprecise articulated robots amid obstacles. In: IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 5660–5667 (2013)
  * [24] Liu, W., Ang, M.H.: Incremental sampling-based algorithm for risk-aware planning under motion uncertainty. In: 2014 IEEE International Conference on Robotics and Automation (ICRA). pp. 2051–2058 (2014)
  * [25] Luo, Y.z., Yang, Z.: A review of uncertainty propagation in orbital mechanics. Progress in Aerospace Sciences 89, 23–39 (2017)
  * [26] Park, C., Pan, J., Manocha, D.: ITOMP: Incremental trajectory optimization for real-time replanning in dynamic environments. In: Twenty-Second International Conference on Automated Planning and Scheduling (2012)
  * [27] Park, C., Park, J.S., Manocha, D.: Fast and bounded probabilistic collision detection for high-DOF trajectory planning in dynamic environments. IEEE Transactions on Automation Science and Engineering 15(3), 980–991 (2018)
  * [28] Patil, S., Van Den Berg, J., Alterovitz, R.: Estimating probability of collision for safe motion planning under Gaussian motion and sensing uncertainty. In: IEEE International Conference on Robotics and Automation. pp. 3238–3244 (2012)
  * [29] Rimon, E., Boyd, S.P.: Obstacle collision detection using best ellipsoid fit. Journal of Intelligent and Robotic Systems 18(2), 105–126 (1997)
  * [30] Sadigh, D., Kapoor, A.: Safe control under uncertainty with probabilistic signal temporal logic. Robotics: Science and Systems (2016)
  * [31] Salzman, O., Hou, B., Srinivasa, S.: Efficient motion planning for problems lacking optimal substructure. In: Twenty-Seventh International Conference on Automated Planning and Scheduling (2017)
  * [32] Schmerling, E., Pavone, M.: Evaluating Trajectory Collision Probability through Adaptive Importance Sampling for Safe Motion Planning. In: Proceedings of Robotics: Science and Systems. Cambridge, Massachusetts (July 2017)
  * [33] Shimanuki, L., Axelrod, B.: Hardness of 3D Motion Planning Under Obstacle Uncertainty. Workshop on Algorithmic Foundations of Robotics (2018)
  * [34] Sun, W., Torres, L.G., Van Den Berg, J., Alterovitz, R.: Safe motion planning for imprecise robotic manipulators by minimizing probability of collision. In: Robotics Research, pp. 685–701. Springer (2016)
  * [35] Thomas, A., Mastrogiovanni, F., Baglietto, M.: Motion Planning with Environment Uncertainty. In: Italian Conference on Robotics and Intelligent Machines (I-RIM) (2020)
  * [36] Thomas, A., Mastrogiovanni, F., Baglietto, M.: An Integrated Localization, Motion Planning and Obstacle Avoidance Algorithm in Belief Space. Intelligent Service Robotics pp. 1–16 (2021)
  * [37] Zhu, H., Alonso-Mora, J.: Chance-constrained collision avoidance for mavs in dynamic environments. IEEE Robotics and Automation Letters 4(2), 776–783 (2019)


# Evaluating Out-of-Distribution Detectors
Through Adversarial Generation of Outliers

Sangwoong Yoon1 &Jinwon Choi2&Yonghyeon Lee1&Yung-Kyun Noh3,4 &Frank Chongwoo
Park1,5

1Seoul National University, 2Kakao Enterprise, 3Hanyang University,
4Korea Institute for Advanced Study, 5Saige Research
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A reliable evaluation method is essential for building a robust out-of-
distribution (OOD) detector. Current robustness evaluation protocols for OOD
detectors rely on injecting perturbations to outlier data. However, the
perturbations are unlikely to occur naturally or not relevant to the content
of data, providing a limited assessment of robustness. In this paper, we
propose Evaluation-via-Generation for OOD detectors (EvG), a new protocol for
investigating the robustness of OOD detectors under more realistic modes of
variation in outliers111The official code release can be found at
https://github.com/EvG-OOD/evaluation-via-generation.. EvG utilizes a
generative model to synthesize plausible outliers, and employs MCMC sampling
to find outliers misclassified as in-distribution with the highest confidence
by a detector. We perform a comprehensive benchmark comparison of the
performance of state-of-the-art OOD detectors using EvG, uncovering previously
overlooked weaknesses.

##  1 Introduction

Figure 1: An illustration of the OOD detection problem setting. The traffic
signs are inliers, and cat photos are test OOD data. Cat images in the yellow
box are synthesized from the variations of test outliers, residing outside of
the test OOD dataset. A robust OOD detector should also detect these images as
outliers.

Outlier detection, also called out-of-distribution (OOD) detection, is
concerned with determining whether an input lies outside the training data
distribution [1, 2]. An OOD detector is an essential component of a
trustworthy machine learning system, since OOD detection algorithms can pre-
filter irrelevant input and prevent the main machine learning model from
potentially dangerous erroneous decisions; for example, in a traffic sign
classification system, an image of a cat can be filtered by the OOD detector,
so that the downstream classifier does not erroneously classify the cat as a
traffic sign. However, OOD detection is a challenging task, because a detector
does not have access to every possible outlier during training.

The diversity of outliers also makes the accurate evaluation of OOD detectors
difficult. In the standard evaluation protocol, an OOD detector is tested
using a finite number of test OOD data, for instance a collection of cat
photos in the traffic sign classifier case (Figure 1). An immediate concern
for the protocol is that an evaluation result from a test OOD dataset, for
example cats, would not always generalize to other outliers, such as dogs. In
practice, this issue has been addressed by using multiple test OOD datasets.

Meanwhile, the non-trivial degree of variability may also present within a
single test OOD dataset, creating blind spots in evaluation. The number of
data in a test OOD dataset could be insufficient to cover all possible
variations in data, e.g., all possible combinations of eye colors and fur
colors in cats, leaving a detector untested for outlier not included in test
OOD dataset. Factors of variations are often continuous in its nature, and
multiple such factors form a multi-dimensional space of variations. Collecting
enough outliers to fill such a space could be expensive.

In this paper, we address this blind spot of evaluation within each test OOD
dataset. We propose Evaluation via Generation for OOD detectors (EvG), a
protocol for evaluating the robustness of an OOD detector under a natural
variability in a test OOD dataset. Given a test OOD dataset, EvG first
construct a variation model, a set of perceptually relevant variations
constructed from the test OOD dataset. EvG then assesses the robustness of an
OOD detector by searching for its worst-case failure mode within the variation
model, i.e., an outlier that is classified as in-distribution by the detector
with the highest confidence. The search process in EvG is essentially a black-
box optimization, where in each iteration EvG generates a new outlier from the
variation model and use the outlier to test the OOD detector.

A variation model is constructed using a generator function $g$, a mapping
from a low-dimensional continuous vector space to the data space, where the
choice of a generator produces different variation models. In our experiments
for image data, we demonstrate two options for a generator. One is based on an
image transformation that preserves the content of an image invariant, and the
other is a StyleGAN2 model [3]. Both choices of a generator give interesting
variation model where we can evaluate the robustness of OOD detectors.

Finding the worst-case failure mode in a given variation model is not trivial
because of multiple local optima. Therefore, instead of using standard
optimization methods that may get stuck at local minima, we leverage a global
search algorithm based on a probabilistic formulation similar to simulated
annealing [4, 5]. We first devise an adversarial distribution, a distribution
designed to assign a higher probability to outlier samples in a variation
model that are likely to be misclassified by the detector. Then, Markov Chain
Monte Carlo (MCMC) is applied to traverse distant modes in the distribution.

EvG can be viewed as an adversarial attack against OOD detectors. However, EvG
extends the conventional adversarial attack protocol in two aspects. First,
our variation models cover perceptually meaningful manifold of data, unlike
noise-like perturbations used in previous attacks [6, 7, 8, 9]. Also, our
variation models have significantly lower dimensionality than the previous
threat models used for OOD detectors, while demonstrating a similar degree of
effectiveness in attack. Second, optimization is re-formulated as a sampling
which is more suitable for global optimization. Optimization and sampling have
an interesting connection, and sampling can sometime be more effective in
optimization [10].

Using EvG framework, we examine the robustness and the failure modes of more
than 13 existing OOD detectors. Among the tested detectors, at least seven
detectors report near-perfect OOD detection performance on a popular
benchmark, CIFAR-10 (in) vs SVHN (out), effectively being indistinguishable
with respect to their performance. Our investigation reveals that the
detectors in fact have diverging degrees of robustness outside the SVHN test
set.

Our main contributions can be summarized as follows:

  * •

We propose a novel generative framework to evaluate the robustness of OOD
detectors under more natural variations of test OOD data;

  * •

We provide extensive benchmark results for the state-of-the-art OOD detectors
using EvG;

  * •

EvG reveals previously overlooked failure modes in detectors, disclosing a new
room for improvement in OOD detection.

##  2 Related Work

OOD detection. The attention on OOD detection has been increasing with an
increasing needs for the safety and the robustness in machine learning. Table
1 provides a non-comprehensive list of OOD detectors and more discussions on
other detectors can be found in Appendix. Most successful approaches in OOD
detection are using auxiliary OOD data to calibrate confidence [2, 6, 7, 8,
9], using Mahalanobis distance in the feature space of pre-trained network
[11, 12], deep ensemble [13], and self-supervised learning [14, 15, 16]. OOD
detectors based on these ideas all achieves near-perfect (>0.99) AUC score in
CIFAR-10 vs SVHN benchmark. One of the key motivations of this research is to
investigate the difference in the robustness among these detectors.

Robustness of OOD Detectors. As other deep neural networks, OOD detectors are
not robust to the adversarial attack unless adversarially trained [6]. Various
techniques have been proposed to improve the robustness of OOD detectors
against small adversarial perturbations, including adversarial training [6,
9], modification of the last layer [17], interval bound propagation [7], and
an outlier mining method with adversarial training [9]. However, most of such
methods evaluate the robustness of a detector only on small perturbations in a
norm ball. In a few notable exceptions [9, 16], the adversarial corruption
noise [18] which is controlled by discrete parameters. In this work, we aim to
evaluate the robustness of OOD detectors on more natural perturbations of data
which are controlled by continuous parameters.

Threat Models Beyond Norm Ball. More diverse threat models have been
investigated in the adversarial robustness community, but such techniques are
not yet applied to evaluate the robustness of OOD detectors. GAN is employed
to generate adversarial examples beyond the small norm ball threat model [19],
but it requires an additional classifier and the quality of the generated
samples is poor. However, the paper does show that a model robust to noise-
like attack is not necessarily robust to other types of attack. The ideas of
manipulating an image in a semantic code space to fool a classifier [20] and
parameterizing an attack in the image transformation space [21, 22] are
investigated in supervised learning setting but for OOD detectors.

##  3 Preliminaries: Out-of-Distribution Detection

###  3.1 Problem Setting

We represent a datum as a $D$-dimensional real-valued vector
$\mathbf{x}\in\mathcal{X}\subset\mathbb{R}^{D}$, where $\mathcal{X}$ is the
set of all possible values of a valid datum. For example, when $\mathbf{x}$ is
a $32\times 32$ RGB image, $D=32\times 32\times 3=3{,}072$ and
$\mathcal{X}=[0,1]^{D}$. $\mathcal{X}$ is assumed to be compact.

We are given a set of data which are considered as inlier or in-distribution
$\mathcal{D}=\\{\mathbf{x}_{i}\\}$. The samples $\mathbf{x}_{i}$ are assumed
to be generated from the inlier probability distribution $P_{in}$. The support
of $P_{in}$ is
$\mathcal{S}_{in}=\\{\mathbf{x}|\;p_{in}(\mathbf{x})>0\\}\subset\mathcal{X}\subset\mathbb{R}^{D}$,
where $p_{in}$ is the inlier probability density. A vector $\mathbf{x}$ is an
outlier, or an out-of-distribution (OOD) sample, if $\mathbf{x}$ does not
belong to $\mathcal{S}_{in}$ [23]. In plain words, we define an outlier as a
sample that has no possibility of being generated from the inlier probability
distribution.

An OOD detector $f:\mathbb{R}^{D}\to\mathbb{R}$ is a function which outputs a
larger value for an input more likely to be an outlier. A test sample
$\mathbf{x}^{*}$ is classified as OOD if $f(\mathbf{x}^{*})>\eta_{f}$ for some
threshold $\eta_{f}$. The function value $f(\mathbf{x})$ will be referred to
as a detector score. We shall assume $f(\mathbf{x})$ is bounded. In this
paper, we consider a black-box setting, where any information other than the
function value $f(\mathbf{x})$, such as its gradient, is not accessible.

###  3.2 Evaluation of OOD Detectors

The currently accepted evaluation protocol for OOD detectors relies on one or
multiple test OOD datasets $\mathcal{D}_{out}$, considered as OOD by human
prior knowledge. How well a detector $f$ binary-classifies between
$\mathcal{D}_{in}$ and $\mathcal{D}_{out}$ is considered as an indicator of
the OOD detection performance. The classification result is summarized using
metrics such as the area under the receiver operating characteristic curve
(AUROC or AUC).

Similarly to the adversarial robustness of supervised classifiers (e.g., [24,
25]), the robustness of OOD detectors are evaluated using the worst-case
samples within a set of outliers $\mathcal{T}$ defined from the test OOD
datasets. A common choice of $\mathcal{T}$ in previous works on robust OOD
detection is a $l_{\infty}$-norm ball around an OOD datum $\mathbf{x}_{out}$,
i.e.,
$\mathcal{T}_{\infty}(\mathbf{x}_{out})=\\{\mathbf{x}|\;\|\mathbf{x}-\mathbf{x}_{out}\|_{\infty}\leq\epsilon\\}$,
where $\epsilon>0$ is a small constant. Then the most confusing outlier to $f$
is found via:

$\displaystyle\mathbf{x}_{adv}=\operatorname*{arg\,min}_{\mathbf{x}}f(\mathbf{x})\quad\text{such
that}\quad\mathbf{x}\in\mathcal{T}_{\infty}(\mathbf{x}_{out}).$ (1)

The classification performance on $\mathbf{x}_{adv}$ serves as a measure for
the robustness [7].

Even though an OOD detector is assured to be robust against small-norm
perturbations, it is difficult to conclude that the detector is also robust to
other types of outliers. In particular, the set
$\mathcal{T}_{\infty}(\mathbf{x}_{out})$ is too small to cover
$\mathcal{S}_{out}$. In the subsequent section, we define a larger set
$\mathcal{T}$, called a variation model, by using natural variations of data.

Table 1: The list of OOD detectors used in the experiments. NLL: Negative Log-Likelihood. RE: Reconstruction Error. MSP: Maximum Softmax Probability. Inference time is the time required to perform inference for 10,000 CIFAR-10 test samples on Tesla V100. OOD Detector | Description | $f(\mathbf{x})$ |  Inference Time (sec) |  Additional Data
---|---|---|---|---
Glow [26] | A flow-based generative model. | NLL | 93.7 | $\times$
PXCNN [27] | PixelCNN++. An autoregressive generative model. | NLL | 32.9 | $\times$
AE ([28]) | An unregularized convolutional autoencoder. | RE | 3.5 | $\times$
NAE [29] |  Normalized autoencoder, an energy-based formulation of AE. | RE | 3.5 | $\times$
GOOD [7] |  Guaranteed OOD Detector, based on the interval bound propagation [30]. | MSP | 1.8 | $\bigcirc$
ACET [6] | Adversarial Confidence Enhancing Training. | MSP | 1.8 | $\bigcirc$
CEDA [6] | Confidence Enhancing Data Augmentation. | MSP | 1.8 | $\bigcirc$
SSD [15] |  $k$-means clustering and mahalanobis distance in the self-supervised feature space. | Distance | 7.8 | $\times$
MD [11] |  Mahalanobis distance in classifier feature spaces. The validation split of test OOD dataset is used to tune some parameters. | Distance | 46.5 | $\bigcirc$
SNGP [31] |  Spectral-normalized Neural Gaussian Process with bi-Lipschitz condition | Dempster-Shafer | 6.7 | $\times$
ATOM [9] |  A classifier trained with informative outlier mining and adversarial training. | Logit | 6.0 | $\bigcirc$
OE [32] |  Outlier Exposure. A classifier trained to be less confident on auxiliary OOD data. | MSP | 1.8 | $\bigcirc$
ROWL [8] |  A classifier trained with additional background classes and adversarial training. | Logit | 5.4 | $\bigcirc$
CSI [14] |  The combination of multiple OOD metrics in a self-supervised feature space. | Distance | 266.8 | $\times$

##  4 Evaluation via Generation for OOD Detectors

Here, we introduce Evaluation via Generation for OOD Detectors (EvG), an
evaluation framework for the robustness of OOD detectors under perceptually
meaningful variations of OOD data. EvG consists of two modules: a variation
model and an adversarial distribution. A variation model is responsible for
defining the space of variation. An adversarial distribution is a probability
distribution defined on a variation model, guiding the optimization process
for the worst-case failure of an OOD detector being evaluated. After a
variation model and an adversarial distribution are constructed, then MCMC
sampling is performed to find an outlier sample within the variation model
that is classified as in-distribution with the strongest confidence by a
detector.

###  4.1 Variation Models

A variation model is a set containing plausible variations of a test OOD
dataset. First, we set a low-dimensional compact latent code space
$\mathcal{Z}\subset\mathbb{R}^{D_{\mathbf{z}}}$. Then, we define a variation
model $\mathcal{T}_{g}$ using a generator $g(\mathbf{z})$, a mapping from
$\mathcal{Z}$ to data space $\mathcal{X}$:

$\displaystyle\mathcal{T}_{g}=\\{\mathbf{x}=g(\mathbf{z})|\;\mathbf{z}\in\mathcal{Z}\\}.$
(2)

Thus, $\mathcal{T}_{g}$ forms a $D_{\mathbf{z}}$-dimensional manifold in the
data space, reflecting the intuition that variations in perceptual stimuli may
have a low-dimensional structure [33]. With the careful choice of
$g(\mathbf{z})$, we can ensure that all elements in $\mathcal{T}_{g}$ are
outliers and important mode of variations in a test OOD dataset is reflected.

Instance-Conditional Variation Models. First, we choose $g(\mathbf{z})$ to
represent identity-preserving transforms, i.e., a transformation function
which does not alter the semantic content but changes the low-level
characteristics of data. For images, the affine transform and the color
jittering could be identity-preserving. Such transforms are widely used in
data augmentation techniques, self-supervised learning [34], and adversarial
attack [21, 22], but new in OOD detection. To transform, $g$ needs a base data
as an input.

$\displaystyle\mathbf{x}=g(\mathbf{z};\mathbf{x}_{out}),\quad\mathbf{x}_{out}\in\mathcal{D}_{out}.$
(3)

Then, we obtain an instance-conditional variation model
$\mathcal{T}_{g}(\mathbf{x}_{out})$ from Eq. (2). In our experiments with
image data, we define Affine variation model ($D_{\mathbf{z}}=5$), which has
rotation, translation (x, y), scaling, and shear (x, y) operations, and Color
variation model ($D_{\mathbf{z}}=4$), which can adjust brightness, contrast,
saturation and hue of an image. Both are implemented by TorchVision.

Unconditional Variation Models. A novel outlier example can be synthesized by
re-combining the existing features in the test OOD dataset. Synthesizing a new
example with a high fidelity is generally a difficult task, but recent
developments in generative modeling provide strong tools, such as StyleGAN2
[3]. We use the generator of StyleGAN2 as $g(\mathbf{z})$. This results in an
unconditional variation model $\mathcal{T}_{g}$. In our experiments, we obtain
$g(\mathbf{z})$ by training StyleGAN2 on the test OOD set $\mathcal{D}_{out}$
and refer the resulting variation model as GAN variation model. In this case,
the domain of $\mathbf{z}$ is the surface of a unit sphere in 64-dimensional
space.

Figure 2:  An OOD detector $f$ (CIFAR10 images as inliers) is investigated
under the affine transform variation model with the SVHN images. (Left) Our
sampling-based method, MH, finds one global solution unlike the coordinate
descent method. (Right) Average of the minimum detector scores over 64
different variation models, and the shaded interval that represents the max
and min values.

###  4.2 Adversarial Distributions

With a variation model $\mathcal{T}$, our goal is to find the worst-case
example via solving the following optimization problem with respect to the
latent code $\mathbf{z}$:

$\displaystyle\mathbf{z}^{*}=\operatorname*{arg\,min}_{\mathbf{z}\in\mathcal{Z}}f(g(\mathbf{z}));\quad\mathbf{x}^{*}=g(\mathbf{z}).$
(4)

where $\mathbf{x}^{*}$ is an outlier that the detector considers being the
most inlier in $\mathcal{T}$. Instead of directly solving Eq. (4), we define a
probability distribution that can guide our optimization similarly to
simulated annealing [35, 4].

An adversarial distribution against an OOD detector $f$ on a variation model
$\mathcal{T}$ is defined as follows:

$\displaystyle p_{f}(\mathbf{z})=\frac{1}{Z}\exp(-f(g(\mathbf{z}))/T),\quad
Z=\int_{\mathcal{Z}}\exp(-f(g(\mathbf{z}))/T)d\mathbf{z}<\infty$ (5)

where $T>0$ is the temperature. The form of $p_{f}(\mathbf{z})$ in Eq. (5) can
be seen as an instance of a Gibbs distribution or an energy-based model. Here,
the detector score $f(\mathbf{x})$ serves as an energy. Note that when
$\mathcal{T}_{g}$ is instance-conditional, then there is an adversarial
distribution for each test OOD datum.

An adversarial distribution $p_{f}(\mathbf{x})$ has two important properties
by construction. First, by construction, an adversarial distribution assigns a
high probability density on samples likely to be classified as in-distribution
by the detector. Second, for the limit $T\to 0$, sampling from an adversarial
distribution becomes equivalent to the adversarial search, as the probability
mass is concentrated on $\mathbf{x}^{*}$ in Eq. (4). Hence, sampling from an
adversarial distribution can be viewed as a relaxation of the original
optimization problem Eq. (4), and $T$ governs the degree of relaxation.

###  4.3 MCMC for Optimization

We solve the original optimization problem in Eq. (4) by sampling from an
adversarial distribution. Markov Chain Monte Carlo (MCMC) is employed to draw
samples from an adversarial distribution. Due to the ergodicity of a Markov
chain, the chain is guaranteed to visit every minima of the detector score
$f(\mathbf{x})$ given a sufficient number of steps. By choosing the sample
with the lowest detector score from the whole trajectory, we can find the
global minima of $f(\mathbf{x})$. In this way, we are more likely to find the
global minima compared to local optimization methods since the chain in MCMC
explores the entire search space. While any MCMC algorithm can be applicable,
we employ Metropolis-Hastings algorithm (MH, [5]), because MH algorithm is
simple, robust, easy to implement, and has a small number of hyperparameters.

In EvG, an adversarial distribution $p_{f}(\mathbf{z})$ and a generator
$g(\mathbf{z})$ in fact form a generative model over $\mathcal{T}_{g}$. To
draw sample from EvG’s generative model we perform MCMC, which will result in
the optimization of Eq. (4) in the limit.

Figure 2 shows that sampling approach is indeed effective in optimization,
whereas a local optimization algorithm, the coordinate descent in this case,
would stuck in local optima. This is consistently observed throughout many
detector models, which seems because a variation model $\mathcal{T}$ contains
perceptually diverse samples, and a detector function $f$ is often very non-
convex and non-linear.

Table 2: Evaluation of OOD detectors using the adversarial distributions. Clean indicates the test split of a test OOD dataset. AUC scores are evaluated using 10,000 inliers and 5,000 outliers. MinRank is computed from a run which consists of 1,000 MCMC chains. The standard error is computed from five independent runs. The boldface are the largest numbers and the underlined are the smallest numbers among strong detectors. Metric | AUC | MinRank
---|---|---
OOD | SVHN | CelebA | SVHN | CelebA
Variation | Clean | $l_{\infty}$ | Affine | Color | GAN | Clean | $l_{\infty}$ | Affine | Color | GAN | Clean | GAN | Clean | GAN
Weak Detectors |  |  |  |  |  |  |  |  |  |  |  |
Glow | .069 | .071 | .002 | .000 | .000 | .542 | .547 | .008 | .001 | .036 | 8 |  1 $\pm$ 0 | 177 |  24 $\pm$ 1
PixelCNN++ | .076 | .078 | .015 | .000 | .000 | .639 | .644 | .085 | .003 | .053 | 0 |  0 $\pm$ 0 | 391 |  28 $\pm$ 4
AE | .080 | .054 | .032 | .000 | .000 | .533 | .401 | .159 | .001 | .012 | 0 |  0 $\pm$ 0 | 18 |  1 $\pm$ 0
Strong Detectors |  |  |  |  |  |  |  |  |  |  |  |
NAE | .935 | .900 | .755 | .704 | .005 | .874 | .803 | .627 | .343 | .098 | 11 |  0 $\pm$ 0 | 616 |  39 $\pm$ 4
GOOD | .943 | .714 | .565 | .664 | .515 | .939 | .852 | .580 | .664 | .570 | 2141 |  1609 $\pm$ 85 | 3558 |  1720 $\pm$ 161
ACET | .966 | .905 | .753 | .868 | .425 | .986 | .952 | .593 | .904 | .631 | 3414 |  1304 $\pm$ 74 | 4845 |  2917 $\pm$ 158
CEDA | .987 | .690 | .636 | .912 | .435 | .981 | .878 | .343 | .908 | .636 | 3348 |  0 $\pm$ 0 | 3200 |  0 $\pm$ 0
SSD | .989 | .199 | .631 | .936 | .479 | .780 | .231 | .564 | .674 | .288 | 4133 |  691 $\pm$ 54 | 2335 |  1211 $\pm$ 56
MD | .993 | .581 | .747 | .484 | .169 | .796 | .035 | .394 | .064 | .046 | 69 |  2 $\pm$ 0 | 5 |  1 $\pm$ 0
SNGP | .994 | .096 | .761 | .892 | .488 | .882 | .007 | .336 | .613 | .145 | 2427 |  0 $\pm$ 0 | 8 |  13 $\pm$ 2
ATOM | .996 | .992 | .908 | .974 | .616 | .998 | .992 | .867 | .976 | .771 | 6203 |  1522 $\pm$ 98 | 7517 |  1240 $\pm$ 298
OE | .997 | .566 | .751 | .953 | .620 | .992 | .593 | .678 | .916 | .736 | 5636 |  1774 $\pm$ 102 | 5217 |  1947 $\pm$ 161
ROWL | .997 | .875 | .675 | .969 | .659 | .991 | .809 | .374 | .933 | .559 | 5213 |  260 $\pm$ 179 | 2454 |  644 $\pm$ 100
CSI | .998 | .630 | .940 | .992 | .893 | .890 | .463 | .892 | .855 | .484 | 8208 |  6866 $\pm$ 112 | 3727 |  3225 $\pm$ 53

##  5 Experiments

In our experiments, we aim to evaluate the robustness of the state-of-the-art
OOD detectors under variation models. Using Affine, Color, and StyleGAN2
variation models, adversarial distributions are constructed for 13 OOD
detectors, described in Table 1. We first show that adversarial distributions
can find the known weaknesses of baseline detectors. Then, we apply our
methods on the state-of-the-art OOD detectors which show near-perfect
performance on a popular benchmark. Finally, we reveal some interesting
patterns in the failure modes of the detectors. Table 2 summarizes our
experimental results. The extended experimental results can be found in
Appendix.

###  5.1 Experimental Settings

Datasets. We use CIFAR-10 as in-distribution data $\mathcal{D}_{in}$. SVHN and
CelebA are used as test OOD datasets $\mathcal{D}_{out}$. All datasets are
splitted into training, validation, and testing sets. All data are
32$\times$32 RGB images. Details on datasets can be found in Appendix.

Figure 3:  The worst-case samples for the weak detectors. The numbers are the
detector score rank.

CIFAR-10 (in) vs SVHN (out) dataset pairs become popular after the reports
showing that OOD detectors built upon deep generative models, such as
PixelCNN++ or Glow, dramatically fail to detect SVHN as outliers [32, 36],
producing AUC scores close to 0. After this observation, multiple OOD
detectors achieving AUC scores higher than 0.9 or even higher than 0.99 on the
benchmark have been proposed (see Table 2). Given their near-perfect detection
score, we question whether the detectors are indeed robust OOD detectors under
variabilities likely to occur for image data.

OOD Detectors. We implement 13 previously proposed outlier detectors, listed
in Table 1. The detectors are grouped into two, the weak and the strong, based
on their performance on CIFAR-10 vs. SVHN. The _weak_ detectors are outlier
detectors show AUC score close to zero on CIFAR-10 vs. SVHN. _Strong_
detectors are selected from three criteria: 1) AUC score on CIFAR-10 vs SVHN
is higher than 0.9. 2) The code is publicly available and written in PyTorch.
The language constraint is introduced for the unified experiment. 3) The
performance claimed in the original work should be reproducible.

Extended experimental results with more OOD detectors can be found in
Appendix. OOD detectors we considered but not included in the experiment of
this paper are also discussed in Appendix.

Evaluation Metrics. For each detector, we report AUC score of classifying the
set of outliers and the test split of $\mathcal{D}_{in}$. AUC score close to
1.0 indicates a successful OOD detection. Additionally, for unconditional
adversarial distributions, we also compute MinRank, the rank of the smallest
detector score achieved. The rank of the score is computed with respect to the
scores of the test split of $\mathcal{D}_{in}$, which contains 10,000 samples.
An ideal OOD detector should score MinRank of 10,000, since a rank starts from
zero.

###  5.2 Implementation of EvG

Variation Models. We use Affine ($D_{\mathbf{z}}=5$), Color
($D_{\mathbf{z}}=4$), and GAN ($D_{\mathbf{z}}=64$) variation models. The
first two are instance-conditional, and GAN is an unconditional variation
model. Variation models are constructed for each test OOD dataset, SVHN and
CelebA For StyleGAN2, we use an implementation provided by PyTorch-StudioGAN
repository222https://github.com/POSTECH-CVLab/PyTorch-StudioGAN [37].

Adversarial Distributions. To deal with the scale difference in detector
scores $f(\mathbf{x})$, the scores are standardized to have the zero mean and
the variance of one, when evaluated on the validation split of in-distribution
data. For all experiments, the temperature is set $T=1$.

MH algorithm with Gaussian proposal distribution is used. The standard
deviation of the proposal distribution is fixed to $0.1$. A proposal is
randomly accepted based on Metropolis’ criterion. We run 5,000 independent
Markov chains with each chain runs for 2,000 steps. For instance-conditional
adversarial distributions, we use the first 5,000 examples of a test OOD
dataset. Among the visited states in a trajectory, the sample with the
smallest $f(\mathbf{x})$ is selected. More implementation details can be found
in Appendix.

$l_{\infty}$ Attack. For comparison, we also implement a black-box
$l_{\infty}$ attack based on the zeroth-order random coordinate descent with
momentum [38] and run for each OOD detectors for 20,000 steps. Following [7],
we perform the attack on a ball of radius 0.01. The momentum coefficient was
0.999, and the step size starts from 0.1 and is halved every 2,000 steps. Note
that our black-box $l_{\infty}$ should be weaker than their white-box version
used in [7].

Figure 4: The worst-case samples from unconditional adversarial distributions
against 10 strong detectors under GAN variation model on SVHN and CelebA. The
numbers indicate the detector score rank in-distribution test set.

###  5.3 Adversarial Distributions Against Detectors with Known Weaknesses

We confirm the effectiveness of adversarial distributions by applying them on
the weak detectors, Glow, PXCNN, and AE, where the weaknesses have already
been analyzed. It is known that Glow, PXCNN, and AE erroneously classify low-
complexity images, such as monotone images or highly blurry images, as in-
distribution [39, 29]. The known failure mode can be clearly observed from
Figure 3. The worst-case samples from adversarial distributions are consistent
with the previously known tendency. The samples are very blurry and a large
portion of pixels are monotone, which are misclassified as in-distribution by
the weak detectors with high confidence.

###  5.4 Evaluating State-of-the-Art Detectors

Then, we evaluate the robustness of 10 strong detectors using the proposed
variation models and adversarial distributions. Table 2 provides the
quantitative evaluation results. Figure 4 show examples from each adversarial
distributions. As a whole, it is difficult to state a winner, as no detector
is perfectly robust. All the tested detectors demonstrate notable drops in
detection performance under more than one types evaluation set-ups.
Additionally, our method reveals interesting, previously unexplored blind
spots of OOD detectors. Due to the space constraint, more results can be found
in Appendix.

Effectiveness of Low-Dimensional Variation. Considering their low
dimensionality, Affine and Color variation models are surprisingly effective
at finding failure modes for some models. GOOD, ACET, and CEDA, the detectors
trained to be robust against $l_{\infty}$ threat model, show significant
degree of vulnerability under Affine. This indicates that optimizing for the
robustness against one threat model does not necessarily improve the
robustness against other threat models. Meanwhile, CSI show strong robustness
against Affine and Color, probably because transformations similar to Affine
and Color are used during its training.

Characteristic Failure Modes. From Figure 4, there are several noticeable
patterns in the failure modes of the detectors. First, some OOD detectors
exhibit the color bias, classifying an image of a certain color as in-
distribution. For example, MD shows a strong bias by confidently classifying
images with pink or cyan color as in-distribution, recording the lowest AUC
under Color on both datasets.

In Figure 4, each OOD detector has different blind spots, showing distinct
failure examples. ACET tends to classify generated CelebA images with a
certain facial expression as inliers. SSD consistently misclasifies photos of
a white blond female.

Transferability of Failure Modes. We question whether samples from an
adversarial distribution is transferable, i.e., given two detectors
$f_{1}(\mathbf{x})$ and $f_{2}(\mathbf{x})$, are the worst-case outliers from
$p_{f_{1}}(\mathbf{x})$ able to deceive another detector $f_{2}(\mathbf{x})$?
We collect samples from $p_{f_{1}}(\mathbf{x})$ then check if
$f_{2}(\mathbf{x})$ can detect them as outliers. The pairwise results are
displayed in Figure 5.

First, some of the failure modes are shared. Worst-case outliers from other
detectors are able to fool NAE and MD, indicating that the outliers are also
one of the failure modes of them. Second, the failure mode of one detector is
more readily transferable to another detector with the similar inductive bias.
For example, GOOD, ACET, CEDA, and OE share the same structure as a
classifier. Both SSD and CSI utilize the self-supervised learning. Third, the
failure modes are not very transferable between strong detectors built upon
different inductive biases, such as OE and CSI. They are successful in
detecting each other’s worst-case samples.

Figure 5:  AUC scores evaluated against other detectors’ adversarial
distribution samples. (up) SVHN (down) CelebA

##  6 Discussion

Extensions. As a framework, the proposed method has a significant degree of
flexibility in designing a variation model $\mathcal{T}_{g}$. Therefore, with
an appropriate choice of $g(\mathbf{z})$, our method is certainly extensible
to other types of data, such as audio anomaly detection [40] or robot
collision detection [41]. Our method will be particularly helpful in a domain
where additional collection of test OOD data is infeasible or costly. Also,
our method will be directly benefited from the rapid progress in generative
modelling. The fidelity and coverage of our protocol would increase as
generative models become more capable of generating diverse and realistic
data.

Future Work. To facilitate the development of OOD detection methods, we intend
to publish EvG as an online software suite for evaluating the robustness of
OOD detectors. We also plan to publish an online leaderboard displaying the
results from an adversarial distribution analysis, and to update the
leaderboard with the latest OOD detection methods.

##  7 Conclusion

In this paper, we have addressed the limitations of the current robustness
evaluation protocol and proposed a novel framework, Evaluation via Generation,
which utilize a generative approach to investigate the failure modes of OOD
detectors beyond noise-like perturbations or preset corruptions. The proposed
framework posing new challenges in OOD detection by discovering unexplored
weaknesses in the existing OOD detectors, We expect our framework to stimulate
the advance of trustworthy machine learning, where a model needs to be
evaluated beyond the fixed test dataset.

## References

  * [1] Douglas M Hawkins.  Identification of outliers, volume 11.  Springer, 1980.
  * [2] Dan Hendrycks and Kevin Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  arXiv preprint arXiv:1610.02136, 2016.
  * [3] Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila.  Analyzing and improving the image quality of stylegan.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [4] Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi.  Optimization by simulated annealing.  science, 220(4598):671–680, 1983.
  * [5] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller.  Equation of state calculations by fast computing machines.  The journal of chemical physics, 21(6):1087–1092, 1953.
  * [6] Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf.  Why relu networks yield high-confidence predictions far away from the training data and how to mitigate the problem.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [7] Julian Bitterwolf, Alexander Meinke, and Matthias Hein.  Certifiably adversarially robust detection of out-of-distribution data.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 16085–16095. Curran Associates, Inc., 2020.
  * [8] Vikash Sehwag, Arjun Nitin Bhagoji, Liwei Song, Chawin Sitawarin, Daniel Cullina, Mung Chiang, and Prateek Mittal.  Analyzing the robustness of open-world machine learning.  In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security, AISec’19, page 105–116, New York, NY, USA, 2019\. Association for Computing Machinery.
  * [9] Jiefeng Chen, Yixuan Li, Xi Wu, Yingyu Liang, and Somesh Jha.  Atom: Robustifying out-of-distribution detection using outlier mining.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 430–445. Springer, 2021.
  * [10] Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I Jordan.  Sampling can be faster than optimization.  Proceedings of the National Academy of Sciences, 116(42):20881–20885, 2019.
  * [11] KIMIN Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin.  A simple unified framework for detecting out-of-distribution samples and adversarial attacks.  In 32nd Conference on Neural Information Processing Systems (NIPS). Neural Information Processing Systems Foundation, 2018.
  * [12] Stanislav Fort, Jie Ren, and Balaji Lakshminarayanan.  Exploring the limits of out-of-distribution detection.  arXiv preprint arXiv:2106.03004, 2021.
  * [13] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell.  Simple and scalable predictive uncertainty estimation using deep ensembles.  Advances in neural information processing systems, 30, 2017.
  * [14] Jihoon Tack, Sangwoo Mo, Jongheon Jeong, and Jinwoo Shin.  Csi: Novelty detection via contrastive learning on distributionally shifted instances.  arXiv preprint arXiv:2007.08176, 2020.
  * [15] Vikash Sehwag, Mung Chiang, and Prateek Mittal.  {SSD}: A unified framework for self-supervised outlier detection.  In International Conference on Learning Representations, 2021.
  * [16] Umar Khalid, Ashkan Esmaeili, Nazmul Karim, and Nazanin Rahnavard.  Rodd: A self-supervised approach for robust out-of-distribution detection.  arXiv preprint arXiv:2204.02553, 2022.
  * [17] Alexander Meinke and Matthias Hein.  Towards neural networks that provably know when they don’t know.  In International Conference on Learning Representations, 2020.
  * [18] Dan Hendrycks and Thomas Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  arXiv preprint arXiv:1903.12261, 2019.
  * [19] Yang Song, Rui Shu, Nate Kushman, and Stefano Ermon.  Constructing unrestricted adversarial examples with generative models.  Advances in Neural Information Processing Systems, 31:8312–8323, 2018.
  * [20] Ameya Joshi, Amitangshu Mukherjee, Soumik Sarkar, and Chinmay Hegde.  Semantic adversarial attacks: Parametric transformations that fool deep classifiers.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4773–4783, 2019.
  * [21] Jiyu Chen, David Wang, and Hao Chen.  Explore the transformation space for adversarial images.  In Proceedings of the Tenth ACM Conference on Data and Application Security and Privacy, pages 109–120, 2020.
  * [22] Bo Yang, Kaiyong Xu, Hengjun Wang, and Hengwei Zhang.  Random transformation of image brightness for adversarial attack.  Journal of Intelligent & Fuzzy Systems, (Preprint):1–12, 2021\.
  * [23] Bernhard Schölkopf, John C Platt, John Shawe-Taylor, Alex J Smola, and Robert C Williamson.  Estimating the support of a high-dimensional distribution.  Neural computation, 13(7):1443–1471, 2001.
  * [24] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In 2nd International Conference on Learning Representations, ICLR 2014, 2014.
  * [25] Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein.  Robustbench: a standardized adversarial robustness benchmark.  NeurIPS 2021 Datasets and Benchmarks Track, 2021.
  * [26] Durk P Kingma and Prafulla Dhariwal.  Glow: Generative flow with invertible 1x1 convolutions.  In Advances in Neural Information Processing Systems, pages 10215–10224, 2018.
  * [27] Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik P Kingma.  Pixelcnn++: Improving the pixelcnn with discretized logistic mixture likelihood and other modifications.  arXiv preprint arXiv:1701.05517, 2017.
  * [28] D. E. Rumelhart, G. E. Hinton, and R. J. Williams.  Learning Internal Representations by Error Propagation, page 318–362.  MIT Press, Cambridge, MA, USA, 1986.
  * [29] Sangwoong Yoon, Yung-Kyun Noh, and Frank Park.  Autoencoding under normalization constraints.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12087–12097. PMLR, 18–24 Jul 2021.
  * [30] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli.  On the effectiveness of interval bound propagation for training verifiably robust models.  arXiv preprint arXiv:1810.12715, 2018.
  * [31] Jeremiah Liu, Zi Lin, Shreyas Padhy, Dustin Tran, Tania Bedrax Weiss, and Balaji Lakshminarayanan.  Simple and principled uncertainty estimation with deterministic deep learning via distance awareness.  Advances in Neural Information Processing Systems, 33:7498–7512, 2020.
  * [32] Dan Hendrycks, Mantas Mazeika, and Thomas Dietterich.  Deep anomaly detection with outlier exposure.  In International Conference on Learning Representations, 2019.
  * [33] H Sebastian Seung and Daniel D Lee.  The manifold ways of perception.  science, 290(5500):2268–2269, 2000.
  * [34] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR, 2020.
  * [35] Martin Pincus.  Letter to the editor—a monte carlo method for the approximate solution of certain types of constrained optimization problems.  Operations research, 18(6):1225–1228, 1970.
  * [36] Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan Gorur, and Balaji Lakshminarayanan.  Do deep generative models know what they don’t know?  In International Conference on Learning Representations, 2019.
  * [37] Minguk Kang and Jaesik Park.  ContraGAN: Contrastive Learning for Conditional Image Generation.  In Conference on Neural Information Processing Systems (NeurIPS), 2020.
  * [38] Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh.  Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models.  In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15–26, 2017.
  * [39] Joan Serrà, David Álvarez, Vicenç Gómez, Olga Slizovskaia, José F. Núñez, and Jordi Luque.  Input complexity and out-of-distribution detection with likelihood-based generative models.  In International Conference on Learning Representations, 2020.
  * [40] Yuma Koizumi, Shoichiro Saito, Hisashi Uematsu, Noboru Harada, and Keisuke Imoto.  Toyadmos: A dataset of miniature-machine operating sounds for anomalous sound detection.  In 2019 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA), pages 313–317. IEEE, 2019.
  * [41] Kyu Min Park, Younghyo Park, Sangwoong Yoon, and Frank C Park.  Collision detection for robot manipulators using unsupervised anomaly detection algorithms.  IEEE/ASME Transactions on Mechatronics, 2021.
  * [42] Antonio Torralba, Rob Fergus, and William T Freeman.  80 million tiny images: A large data set for nonparametric object and scene recognition.  IEEE transactions on pattern analysis and machine intelligence, 30(11):1958–1970, 2008.
  * [43] Ingo Steinwart, Don Hush, and Clint Scovel.  A classification framework for anomaly detection.  Journal of Machine Learning Research, 6(Feb):211–232, 2005.
  * [44] Charline Le Lan and Laurent Dinh.  Perfect density models cannot guarantee anomaly detection.  arXiv preprint arXiv:2012.03808, 2020.
  * [45] A Krizhevsky.  Learning multiple layers of features from tiny images.  Master’s thesis, University of Tront, 2009.
  * [46] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng.  Reading digits in natural images with unsupervised feature learning.  In NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
  * [47] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.  Deep learning face attributes in the wild.  In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
  * [48] Lucas Theis, Aäron van den Oord, and Matthias Bethge.  A note on the evaluation of generative models.  arXiv preprint arXiv:1511.01844, 2015.
  * [49] Partha Ghosh, Mehdi S. M. Sajjadi, Antonio Vergari, Michael Black, and Bernhard Scholkopf.  From variational to deterministic autoencoders.  In International Conference on Learning Representations, 2020.
  * [50] Jie Ren, Peter J. Liu, Emily Fertig, Jasper Snoek, Ryan Poplin, Mark Depristo, Joshua Dillon, and Balaji Lakshminarayanan.  Likelihood ratios for out-of-distribution detection.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [51] Zhisheng Xiao, Qing Yan, and Yali Amit.  Likelihood regret: An out-of-distribution detection score for variational auto-encoder.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20685–20696. Curran Associates, Inc., 2020.
  * [52] Stanislav Fort.  Adversarial vulnerability of powerful near out-of-distribution detection.  arXiv preprint arXiv:2201.07012, 2022.

## Appendix

Appendix is organized as follows:

  * •

Section A: Extended Experimental Results

  * •

Section B: Additional Discussion

  * •

Section C: Datasets

  * •

Section D: Implementation of EvG

  * •

Section E: Implementation of OOD Detectors

##  Appendix A Extended Experimental Results

Figure 6 and Figure 7 show the samples from instance-conditional adversarial
distributions, confirming that OOD detectors can be easily fooled by simple
affine and color transforms.

Figure 6: Examples from instance-conditional adversarial distributions against
strong detectors under Affine and Color variation models on SVHN. The numbers
indicate the detector score rank in-distribution test set. Note that these are
not the worst-case samples but chosen to compare the results from different
detectors. Figure 7: Examples from instance-conditional adversarial
distributions against strong detectors under Affine and Color variation models
on CelebA. The numbers indicate the detector score rank in-distribution test
set. Note that these are not the worst-case samples but chosen to compare the
results from different detectors.

##  Appendix B Additional Discussion

###  B.1 Ethics Statement

Our main ethical concern is that a subset of OOD detectors used in our
experiment, OE, CEDA, ACET and GOOD, are trained using 80 Million Tiny Images
dataset [42], which is retracted by authors over ethical concerns. While we
were aware of the issue of the dataset, the use of models trained on the
dataset was inevitable because of the reproducibility. We have tried to train
OOD detectors using alternative datasets but failed to reach the performance
of detectors originally trained on 80 Million Tiny Images. To minimize the
effect of the retracted dataset, the dataset was never used directly. We only
used the publicly available model checkpoints, and did not download or access
to a copy of dataset.

###  B.2 Limitations

Our methods still rely on a specific choice of test OOD datasets which need
human design. However, this is a limitation that is common for any existing
evaluation protocols for OOD detection. It is a fundamental challenge in OOD
detection that the set of all possible outliers is so vast. Even though an OOD
detector turns out to be perfect under EvG, we can not guarantee that the
tested model is indeed an ideal OOD detector that can detect all possible
outliers.

###  B.3 Definition of Out-of-Distribution (OOD)

Besides the definition of OOD-ness we introduced in Section 2, there is
another popular definition of OOD-ness based on a density sub-level set [43].
For an $\eta>0$, $\\{\mathbf{x}|\;p_{in}(\mathbf{x})\leq\eta\\}$ is defined as
the set of all possible outliers $\mathcal{S}_{out}$. Setting $\eta=0$, the
density sub-level set based definition coincides with the support-based
definition. While a density sub-level set can be arbitrarily distorted under
an invertible coordinate transform [44], the support-based definition provides
an invariant characterization of OOD-ness.

###  B.4 Room for Improvement in OOD Detection

Table 2 reveals that there is a room for improvement in OOD detection, even
besides the samples found by EvG. First, the performance on SVHN does not
transfer to CelebA. CSI, SNGP, NAE, MD, and SSD show unsatisfactory
performance on CelebA. This is why using multiple OOD dataset in evaluation is
important. Second, MinRank shows that the worst-case performance of OOD
detectors are not very satisfactory. Having Clean MinRank less than 5,000
means that if we set a decision threshold so that no outlier is present, we
need to misclassify more than half of inliers as OOD.

###  B.5 GAN Generation Failures

We found that GAN may fail to generate a realistic image and produce a noise-
like image instead. This failure does not happen when GAN is run to generate
samples freely in a conventional way as a typical GAN. This phenomenon
indicates that there are points in GAN’s latent space that does not map to
realistic images. We could not find a measure to suppress this generation
failure. However, even though the generated noise are not realistic, we can
tell they were not in-distribution, so we decide to keep them in the
experiments.

###  B.6 What Makes a Detector Robust?

From Table 2, we can now assess the effectiveness of different ideas in robust
OOD detection. First, adversarial training is effective in defending
$l_{\infty}$ attack. In other words, an algorithm is highly unlikely to be
robust against $l_{\infty}$ attack when it is not trained in an adversarial
way. GOOD, ACET, CEDA, ROWL, and ATOM are all trained adversarially and show
better $l_{\infty}$ robustness than the others. Second, many OOD detectors
rely on auxiliary dataset. Given that no auxiliary data is used, the
performance of CSI is impressive.

##  Appendix C Datasets

In our experiments, we use CIFAR-10, SVHN, and CelebA to demonstrate the
proposed methods and to evaluate OOD detection algorithms, and their details
are described in Table 3. In all cases, we use the official test split as our
test datasets. For CIFAR-10 and SVHN, the official train split is randomly
splitted into train (90%) and valid split (10%). For CelebA, we use the
official train-valid split as it is given. Each CelebA image is center-cropped
into a 140$\times$140 image and scaled to 32$\times$32 using the bilinear
interpolation.

Table 3: Statistics for datasets. Dataset | License | Train | Valid | Test
---|---|---|---|---
CIFAR-10 [45] | Not described | 45,000 | 5,000 | 10,000
SVHN [46] | For non-commercial use only | 65,930 | 7,327 | 26,032
CelebA [47] | For non-commercial research purposes only | 162,770 | 19,867 | 19,962

No augmentation is applied to test data. However, random horizontal flip with
probability 50% and uniform dequantization [48] are applied to training images
in the training of the binary classifiers and the autoencoders in the
adversarial search and adversarial distributions.

##  Appendix D Implementation of EvG

###  D.1 Metropolis-Hasting Algorithm

To generate samples from an adversarial distribution, we apply Metropolis-
Hastings algorithm [5] in $\mathcal{Z}$. An initial state $\mathbf{z}_{0}$ is
drawn from an uniform distribution. Given a state $\mathbf{z}_{t}$ at time
$t$, a candidate for the next state $\bar{\mathbf{z}}_{t+1}$ is generated by
the proposal distribution. We use a Gaussian distribution which is centered at
$\mathbf{z}_{t}$ and has the fixed standard deviation of 0.1 as our proposal
distribution. A proposed sample is accepted with the probability of
$\min\\{1,\exp((E(\bar{\mathbf{z}}_{t+1})-E(\mathbf{z}_{t}))/T)\\}$, yielding
$\mathbf{z}_{t+1}=\bar{\mathbf{z}}_{t+1}$. Otherwise,
$\mathbf{z}_{t+1}=\mathbf{z}_{t}$. We take the final state of a Markov chain
as a generated sample. As stated in the previous paragraph, the final state is
rejected if $\mathbf{z}\not\in\mathcal{T}_{h}$. An accepted sample is mapped
to $\mathcal{X}$ by $\mathbf{x}=f(\mathbf{z})$.

###  D.2 Variation Models

#### Affine

($D_{\mathbf{z}}=5$) We use torchvision.transforms.functional.affine function
to apply affine transform on an image. There are five degrees of freedom and
their parameter bounds are selected as follows: angle (-45 $\sim$ 45),
translation on x-axis (-10 $\sim$ 10), translation on y-axis (-10 $\sim$ 10),
scale (0.9 $\sim$ 1.5), and shear (-30 $\sim$ 30). These parameters are set by
hand.

#### Color

($D_{\mathbf{z}}=4$) We use adjust_brightness, adjust_contrast,
adjust_saturation, adjust_hue from torchvision.transforms.functional.
Parameters and their bounds are given as follows: brightness (0.5 $\sim$ 1.5),
contrast (0.5 $\sim$ 1.5), saturation (0 $\sim$ 2), and hue (-0.5 $\sim$ 0.5).

#### StyleGAN2

($D_{\mathbf{z}}=64$) We train two StyleGAN2 networks, one for SVHN and one
for CelebA. We use the default setting of PyTorch-StudioGAN
repository333https://github.com/POSTECH-CVLab/PyTorch-StudioGAN except that we
change the latent dimensionality to 64. The training took 24 hours on two
A6000 GPUs and went smoothly. The randomly generated samples from the trained
GAN are shown in Figure 8. The samples are realistic and almost not
distinguishable to the real samples.

Figure 8: Comparison between real OOD images (SVHN and CelebA) and images
generated from StyleGAN2 used in our experiments.

##  Appendix E Implementation of OOD Detectors

###  E.1 Implementation of Weak and Strong Detectors

In this section, we describe how OOD detectors are implemented in our
experiments.

#### AE

The architecture of the autoencoder is similar to what is used in [49] and is
described in Table 4 with a different dimensionality of the latent space
$D_{Z}=128$. AE is trained for 500 epochs on in-distribution training set
using Adam optimizer with the learning rate $1\times 10^{-4}$. A mini-batch
contains 128 samples. A model with the smallest reconstruction error on
validation split is selected.

Table 4: Autoencoder architecture. ConvN(M) indicates a 2D convolution
operation with a $N\times N$ kernel and $M$ output channels. BN denotes batch
normalization, and ReLU means the rectified linear unit activation.

Encoder
---
Conv4(128)-BN-ReLU-
Conv4(256)-BN-ReLU-
Conv4(512)-BN-ReLU-
Conv4(1024)-BN-ReLU-
FC(1024)-BN-ReLU-
FC(128)-Tanh

Decoder
---
ConvT8(1024)-ReLU-
ConvT4(512)-ReLU-
ConvT4(256)-ReLU-
ConvT1(3)-Sigmoid

#### PXCNN

PXCNN is implemented based on an open-sourced code
repository444https://github.com/pclucas14/pixel-cnn-pp and re-trained on
CIFAR-10. All the model parameters are set to the default values, i.e.,
nr_resnet=5, nr_filters=80, nr_logistic_mix=10,
resnet_nonlinearity=‘concat_elu’. An input image is linearly scaled into
$[-1,1]$, and horizontal flipped with the probability of 50%. The model is
trained for 200 epochs where a mini-batch contains 64 samples. We use Adam
optimizer with the learning rate $1\times 10^{-4}$ which is decayed by a
multiplicative factor of 0.999995 every iteration.

#### Glow

Glow is implemented based on two
repositories555https://github.com/chaiyujin/glow-pytorch
666https://github.com/chrischute/glow and traianed on CIFAR-10. Our Glow model
utilizes a multi-scale architecture with three levels of the latent
representations are present, i.e., L=3. Each level contains 32 flow steps. We
use 1$\times$1 invertible convolution and ActNorm with the scale of 1.0. The
model is trained for 500 epochs with the batch size of 64. Adam optimizer with
the learning rate 1$\times 10^{-4}$ is utilized. The gradient is clipped so
that its norm is no larger than 0.1.

#### NAE

The pre-trained model is downloaded from the official
repository777https://github.com/swyoon/normalized-autoencoders. We use
Conv32Big version, which showed better performance on CIFAR-10 vs SVHN.

#### OE

Among the available pre-trained models in the official
repository888https://github.com/hendrycks/outlier-exposure, we select the best
performing version, i.e., cifar10_allconv_oe_scratch_epoch_99.pt. We normalize
an input image with means=(0.4914, 0.4822, 0.4465) and std=(0.2471, 0.2435,
0.2615), where each component corresponds to RGB, respectively.

#### CEDA, ACET, GOOD

The pre-trained models are provided by the official repository of
GOOD999https://gitlab.com/Bitterwolf/GOOD. Among multiple versions of GOOD, we
use GOOD80, as recommended in the original paper.

#### MD

We implement MD following the official
repository101010https://github.com/pokaxpoka/deep_Mahalanobis_detector. Based
on the pre-trained ResNet-32 provided by the official repository, we train the
weights of each layer where Mahalanobis distance is computed. 1,000 SVHN
images are used to determine such weights. Note that using test OOD dataset
during the training is usually not acceptable in a typical OOD detection
setting.

#### SSD

We use the official training script to train SSD
111111https://github.com/inspire-group/SSD.

#### CSI

We download the unlabelled multi-class CIFAR-10 model from the official
repository121212https://github.com/alinlab/CSI.

###  E.2 Detectors Not Included in Experiments

We have considered other OOD detectors such as Likelihood Ratio [50], Input
Complexity [39], and Likelihood Regret [51]. However, we could not include
them in our experiments for the following reasons. Meanwhile, we are planning
to include ViT [12] to our experiments in the open-source version.

#### Likelihood Ratio

While there is the official public repository written in
TensorFlow131313https://github.com/google-research/google-
research/tree/master/genomics_ood/images_ood, we have failed to reproduce the
result in PyTorch.

#### Input Complexity

We confirm that the log-density estimates from generative models are
correlated to the bits after compression, but fail to achieve AUC score higher
than 0.9 in CIFAR-10 vs SVHN setting. For generative models, PXCNN and Glow
are tested, and for image compression algorithms, PNG, JPEG2000, and FLIF are
tried. Our generative models are implemented as Section D. For PNG and
JPEG2000, we use OpenCV141414https://opencv.org/, and for FLIF, we use
imageio-flif151515https://codeberg.org/monilophyta/imageio-flif. No
combination of a generative model and a compression algorithm results in AUC
higher than 0.9.

#### Likelihood Regret

The method is very slow, particularly because it does not support batch
processing, i.e., only one sample can be processed at a time. We decide that
the method is too slow to apply the adversarial distribution approach.

#### ViT

OOD detection using Vision Transformer [12] will be added to the open-source
version of the project. It requires extra resources to integrate into the
current code base because its implementation is in JAX. However, we believe
the integration is possible and will be completed very soon. Although ViT show
impressive results in OOD detection, a recent investigation confirm that it is
not adversarially robust against noise-like perturbations [52]. Therefore, we
suspect that ViT could be vulnerable under the variation models proposed in
this paper.