# RCP: A Temporal Clustering Algorithm for Real-time Controller Placement in
Mobile SDN Systems

Reza Soleymanifar1 and Carolyn Beck 1Authors are with Coordinated Science
Laboratory, University of Illinois at Urbana-Champaign, United States of
America<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Software Defined Networking (SDN) is a recent paradigm in telecommunication
networks that disentangles data and control planes and brings more flexibility
and efficiency to the network as a result. The Controller Placement (CP)
problem in SDN, which is typically subject to specific optimality criteria, is
one of the primary problems in the design of SDN systems. Dynamic Controller
Placement (DCP) enables a placement solution that is adaptable to inherent
variability in network components (traffic, locations, etc.). DCP has gained
much attention in recent years, yet despite this, most solutions proposed in
the literature cannot be implemented in real-time, which is a critical concern
especially in UAV/drone based SDN networks where mobility is high and split
second updates are necessary. As current conventional methods fail to be
relevant to such scenarios, in this work we propose a real-time control
placement (RCP) algorithm. Namely, we propose a temporal clustering algorithm
that provides real-time solutions for DCP, based on a control theoretic
framework for which we show the solution exponentially converges to a near-
optimal placement of controller devices. RCP has linear $\mathcal{O}(n)$
iteration computational complexity with respect to the underlying network
size, $n$, i.e., the number of nodes, and also leverages the maximum entropy
principle from information theory. This approach results in high quality
solutions that are practically immune from getting stuck in poor local optima,
a drawback that most works in the literature are susceptible to. We compare
our work with a frame-by-frame approach and demonstrate its superiority, both
in terms of speed and incurred cost, via simulations. According to our
simulations RCP can be up to 25 times faster than the conventional frame-by-
frame method.

##  I INTRODUCTION

Software Defined Networking (SDN) has had major impacts on the performance of
telecommunication networks, especially wireless networks, and it is predicted
that this paradigm will play an integral role in 5G, UAV and IoT based
networks [1]. The key idea in SDN is to dedicate a network component known as
the controller-node for centralization of network decision making in an
attempt to disentangle the data plane (network packets) from the control plane
(routing process). The immediate advantage of this architecture, among many
others, is to allow the network administrator to reprogram the network without
disrupting the data flow.

We define a Mobile SDN network as any SDN network with non-stationary network
nodes. A wide range of such networks may be found in the literature, e.g.,
Software Defined Vehicular Networks (SDVNs), Low Earth Orbit (LEO)
constellations, Software Defined Mobile Networks (SDMNs), Aeronautical
Telecommunication Networks (ATNs) or drone/UAV networks. Similar to the work
presented in [2] and [3], we may assume controllers are SDN-enabled aerial
devices enabling a flying network infrastructure, as illustrated in Figure 1.
A practical realization of such devices could be drones, or UAV’s. Deploying
this type of SDN controller gives great flexibility in networks in locations
where ground stations may not be present [4].

The controller placement problem (CP) in SDN can be described as the task of
finding the best location and node assignments for one or more controllers in
the network, in the sense that a desired criterion is optimally achieved. In
this setting, the function of the controllers is to disentangle the control
and data flows. Latency between controllers and switches represents the main
considered criterion by the majority of studies to date. Some additional
metrics have been introduced including capacity and load balancing, inter-
controller communication delay, deployment cost and energy consumption [5]. In
recent years, high network node mobility and density, and the more wide-spread
presence of wireless links with an overall higher degree of locational
variability raise the issue of adapting the number of controllers and their
locations according to these changes [6]. As one example, LEO satellites spin
around the Earth in periods less than 130 minutes leading to resource
availability dynamics [7]. According to the results of [8], static optimal
solutions do not adequately solve the CP problem in this setting, and it is
necessary to develop solutions which account for the inherent dynamics present
in the system. Following the work in [9], we define dynamic controller
placement (DCP) as an extension of CP that allows adapting to network
dynamics. While CP has been around since Heller first proposed the problem in
[10], DCP is fairly new and is gaining increasing attention in the scientific
community, due to the ever-growing need for more adaptive placement solutions.

Figure 1: A leaderless UAV/drone based SDN system with mobile network control
nodes.

We define a system snapshot, or frame, as a frozen state of the network at any
fixed time. From an implementation standpoint, a dynamic controller
localization problem can be regarded as a time-indexed set of static
localization problems [11]. This perspective motivates a naive approach to DCP
that is to re-solve CP every time a change in system occurs. However, this
approach is clearly inefficient as previous solutions are not utilized and
adapted to avoid unnecessary computations. We refer to such methods as frame-
by-frame approaches that ignore the temporal relationship between system
snapshots and work with each frame in isolation. A pitfall of this approach is
that if convergence time for CP is slower than the rate at which new network
snapshots arrive–which is frequently the case for large-scale networks–this
technique fails. To the best of our knowledge, all of the key works currently
addressing the DCP problem in the literature fall in the frame-by-frame
category.

Conventionally, mobility of the nodes is simply abstracted as a series of
locations, thus rendering DCP a discrete optimization problem [5, 7, 12]. This
type of modeling yields solutions that tend to be suboptimal compared to open
search methods, but nevertheless makes the problem tractable. In this work we
allow for a dynamic open search that can lead to better placements.

TABLE I: Key research in DCP literature. Paper | Proactive | Context | Objective | Variable | Solution | Real-time
---|---|---|---|---|---|---
[5] | No | SDVN | Load balancing+Latency | Traffic fluctuation | ILP | ✗
[1] | No | 5G SDN | Latency | Packet flows | QP | ✗
[7] | Yes | LEO Constellation | Flow setup time | Network flows | ILP | ✗
[2] | No | Drone SDN | Link quality | Node positions | ILP | ✗
[12] | No | SDN | Load balancing+Latency | Traffic fluctuation | GA | ✗
[13] | No | SDN | Maximum latency | Traffic fluctuation | Heuristic | ✗
[14] | Yes | SDN | Latency+migration | Traffic fluctuation | SA | ✗
[8] | No | ATN | Load balancing | Switch positions | ILP+GA | ✗
[15] | No | SDN | Flow setup time | Network flows | ILP | ✗
[16] | Yes | SDSN | Load balancing+Latency+economic | Network flows | APSO | ✗
[17] | No | SDN | Flow setup time | Network flows | ILP | ✗
[18] | Yes | Data Centers | Latency+synchronization+migration | Request rate | Game theoretic | ✗
Our work | No | Mobile SDN | Latency+Synchronization | Exact node positions | Temporal clustering | ✓

Table 1 lists the approaches that have been used to solve DCP. For real-world
networks with thousands to millions of nodes, which translates to the same
order of constraints and variables in approaches like Integer Linear
Programming (ILP) and Quadratic Programming (QP), the DCP problem cannot be
solved in real-time, because the convergence times for these algorithms fall
in the order of minutes to hours. To the best of our knowledge, this is the
first work to solve the DCP problem in real-time, and does not rely on the
frame-by-frame approach. Loosely speaking, RCP achieves this computational
gain by removing the main loop, consisting of repetitive search in the
solution space, which by default exists for any iterative optimization
procedure that tries to find the placement of controllers. This comes at the
cost of having sub-optimal placements at first, but exponentially converging
to near-optimal placements as time goes by.

We classify the main contributions of our work as (1) finding high quality
solutions for DCP in real-time; (2) using the open search method to explore
all possible placements; (3) exploiting the temporal dynamics of the network
for time complexity efficiency; (4) utilizing the maximum entropy principle in
our algorithm to avoid poor local optima, resulting in better placements and
assignments.

The rest of the paper is organized as follows. In section II we review the
recent research on controller-node placement in SDN. In section III, we
introduce a mathematical framework for the controller-node placement problem
in mobile SDN, and provide an in-depth statement of the problem. In Section IV
we introduce our RCP algorithm and provide an analysis of its convergence
properties. Simulation results are given in Section V demonstrating the
performance of our RCP algorithm, which we henceforth simply refer to as RCP.
Finally we conclude the paper in Section VI, in which we summarize the
contributions of our work and present possible future directions of this
research.

##  II LITERATURE REVIEW

In [7], in which a Low-Earth-Orbit (LEO) constellation setting is considered,
the authors partition the time horizon into static snapshots and compute
optimal placements and assignments of controllers at each time step using ILP.
They assume the incoming flow at each snapshot is already known and
proactively solve the DCP problem. They report that this “dynamic” approach
outperforms the standard static approach by approximately an average of 20%.
In [2], the authors formulate the DCP problem for an SDN enabled drone network
as a Mixed Integer Non-linear Program (MINLP), and propose solving this
problem using a heuristic that relies on decoupling the placement and
assignment tasks.

In [12], the authors use a multi-objective genetic algorithm (GA) to break SDN
networks into domains and sub-graphs assigned to controllers. They use inter-
controller latency, load distribution, and controller numbers as the fitness
metrics of their GA algorithm.

In [13], the authors introduce the algorithm LiDy+, which has run-time
complexity of $\mathcal{O}(n^{2})$ (an improvement over predecessors, with run
time complexities of $\mathcal{O}(n^{2}logn))$, and requires a smaller number
of controllers while achieving a higher controller utilization. This method
relies on heuristics for placing controller modules and for adjusting the
number of controllers needed according to traffic fluctuations. The authors in
[5] develop an ILP for a SDVN that updates the reallocation of roadside units
(RSU) to their corresponding controllers. The dynamics of the network in this
work is abstracted as the number of vehicles communicating with a RSU at each
time step; here the ILP-based algorithm objective is to minimize a mixed
latency and load balancing cost function.

The authors in [14] cast DCP as a multi-period MINLP with partial information
of future traffic flows. The authors consider both operational and migration
costs and decompose the problem into smaller online problems, solving them
using the Simulated Annealing (SA) algorithm. The authors in [8] design an ILP
algorithm to address dynamic controller placement in Aeronautical
Telecommunication Networks (ATNs). They propose two heuristic algorithms, DPFA
and GA-DPDA, to solve the ILP problem when controller failure happens due to
packet flow overload. In [15], the authors introduce an ILP problem that
considers both migration time and switch re-assignment time. Each time a new
flow profile arrives this ILP is recalculated.

Software Defined Satellite Networking (SDSN) is considered in [16] where
authors partition the time horizon into smaller intervals within which the
average flow per switch is assumed known. They further assume that back-up
controller-nodes are placed throughout the network, and by toggling the on-off
status of controller-nodes they meet the changing network conditions. The
solution approach proposed for this problem uses Accelerated Particle Swarm
Optimization (APSO). In [17], the authors report up to a 50% improvement over
static placement methods using a dynamic controller placement scheme that
relies on solving an ILP that re-calculates optimal placements when system
change occurs.

In [18], the authors consider the controller assignment aspect of DCP and
decompose the problem into a series of stable matching problems with
transfers, for which they propose a hierarchical two-phase algorithm that
efficiently uses knowledge of future arrival rates. They report a 46%
reduction in cost and better load balancing compared to static assignment.

The authors in [9] model and analyze a realization of the mobile core network
as virtualized software instances running in data centers and SDN transport
network elements, with respect to time-varying traffic demands. In [1], the
authors develop a Quadratic Program (QP) that aims to minimize network switch
to controller latency. As network packet flows change and controller overloads
occur, they use another QP to perform switch migration to meet the increased
load.

To summarize, there are two main approaches for the DCP problem in the
literature. Either authors assume they proactively know the value of network
variables in the future, as in [7], [14], [16], [18], or they rely on what we
earlier described as the frame-by-frame approach, as in [2], [13] amongst
others. Both of these methods fall short of real-world practicality. The
former assumes availability of data that is typically not known, and the
latter does not exploit the temporal relationship between network states over
time. To overcome this gap, our work is aimed at creating a new placement
procedure that can work in real-time and exploit given temporal relationships
of the system; this has led to the design of the RCP algorithm.

##  III PROBLEM STATEMENT

We make the same assumptions on the communication protocol, controller type,
and cost function as in [19]. Specifically we assume network drones/UAV’s are
SDN-enabled and programmable via an API such as OpenFlow, similar to that
described in [2]. In this paper, we will maintain a high-level focus on the
topology of the network and placement of controllers

For simplicity, our analyses are given in $\mathbb{R}^{2}$ equipped with the
Euclidean norm; however our results can be extended directly to
$\mathbb{R}^{n}$ (namely, to $\mathbb{R}^{3}$ in which the basic problem
lies). We further assume that the domain of the problem
$\Omega\subset\mathbb{R}^{2}$ is a compact set that serves as the space within
which the network operates. Throughout the paper we use the shorthand notation
$[A]_{ij}=a_{ij}$ to represent the matrix $A$ that is constructed by equating
its $ij$th element to the scalar $a_{ij}$, and $A=\text{diag}(a_{j})$ to
represent the diagonal matrix $A$ that has $a_{j}$ as the $j$th diagonal
element. We also use $I_{n}$ to denote the identity matrix of size $n\times
n$. We may occasionally drop the time index $t\in\mathbb{R}^{+}$ from the
dynamical equations for the sake of readability and in such circumstances the
reader can infer this from the context of the problem. We represent a mobile
network as an undirected graph $G(\mathcal{N},\mathcal{E})$ with $\mathcal{N}$
as the set of nodes of the graph and $\mathcal{E}$ as the set of edges
connecting these nodes. We represent the network nodes by the set
$\mathcal{N}$ and the controller-nodes by the set $\mathcal{M}$. We will use
$N=|\mathcal{N}|$ and $M=|\mathcal{M}|$ to denote the number of regular
network nodes and controller-nodes in the network, respectively. In the
controller-node placement topology under study 111This topology is known as
leaderless if there is no hierarchy amongst the controller-nodes., there is
communication between controller-nodes and their assigned network nodes, and
between controller-nodes themselves, however network nodes do not directly
communicate with each other. In fact, each node is assigned to a controller-
node that serves as a gate between the node and the rest of the network [19].
In this work, we further assume that the delay in the network is proportional
to the Euclidean distance between source and origin of connection. Let
$x_{i}(t),y_{j}(t)\in\mathbb{R}^{2}$ represent the location of the network
node $i\in\mathcal{N}$ and controller-node $j\in\mathcal{M}$, respectively, at
time $t\in\mathbb{R}^{+}$. The dynamics of the network node $i\in\mathcal{N}$
is determined by the function
$\phi_{i}(t,x,y):\mathbb{R}^{+}\times\mathbb{R}^{2N}\times\mathbb{R}^{2M}\rightarrow\mathbb{R}^{2}$
which we assume is continuously differentiable. The velocity of the
controller-node $j\in\mathcal{M}$ is determined by the vector
$u_{j}(t)\in\mathbb{R}^{2}$; it is this velocity function we aim to design to
achieve real-time controller placement by solving a cluster tracking control
problem. We thus represent a mobile SDN system by the following dynamical
system:

$\begin{cases}\dot{x}=&\phi(t,x,y)\\\ \dot{y}=&u\end{cases}$ (1)

where $x\in\mathbb{R}^{2N}$, $y\in\mathbb{R}^{2M}$,
$\phi(t,x,y):\mathbb{R}^{+}\times\mathbb{R}^{2N}\times\mathbb{R}^{2M}\rightarrow\mathbb{R}^{2N}$,
and $u\in\mathbb{R}^{2M}$ are vectors that are constructed by concatenation of
network and controller node location and velocity vectors. Denoting
$\zeta=[x^{T}y^{T}]^{T}\in\mathbb{R}^{2(N+M)}$ as the vector containing all
positional information of the network nodes and controller-nodes, and letting
$f(t,x,y)=[\phi(t,x,y)^{T}u(t)^{T}]^{T}\in\mathbb{R}^{2(N+M)}$ denote the
vector containing the velocities of these nodes; then we compactly refer to
this first order possibly nonlinear state-space system as

$\dot{\zeta}=f(\zeta).$ (2)

Temporal clustering refers to separation of a time-indexed set of objects into
disjoint partitions known as clusters that satisfy a certain degree of
similarity. The most representative point within each cluster is typically
called the centroid, which in this work is equivalent to the location of the
controller-node. Following the approach introduced by Rose (see [20]), we
leverage the Maximum Entropy Principle for our solution, letting $p(y_{j}\mid
x_{i})\in[0,1]$ denote the intensity of association of network node
$i\in\mathcal{N}$ with controller-node (and cluster) $j\in\mathcal{M}$ such
that $\sum_{j\in\mathcal{M}}p(y_{j}\mid x_{i})=1$; this quantity is also
referred to as an association weight. We represent the objective function
$F:\mathbb{R}^{N\times
M}\times\mathbb{R}^{2N}\times\mathbb{R}^{2M}\rightarrow\mathbb{R}$ associated
with this clustering problem by 222This is a relaxed version of the cost
function in [19]. For details refer to [21].

$\displaystyle F(P_{y\mid x},x,y)=$
$\displaystyle\underbrace{\sum_{\begin{subarray}{c}i\in\mathcal{N}\\\
j\in\mathcal{M}\end{subarray}}p(y_{j}\mid x_{i})\lVert
x_{i}-y_{j}\rVert^{2}}_{D_{1}:\text{delay cost}}$ (3) $\displaystyle+\gamma$
$\displaystyle\underbrace{\sum_{\begin{subarray}{c}j\in\mathcal{M}\\\
j^{\prime}\in\mathcal{M}\end{subarray}}\lVert
y_{j}-y_{j^{\prime}}\rVert^{2}\sum_{i\in\mathcal{N}}p(y_{j}\mid
x_{i})}_{D_{2}:\text{synchronization cost}}$ $\displaystyle-T$
$\displaystyle\underbrace{\left(-\sum_{\begin{subarray}{c}i\in\mathcal{N}\\\
j\in\mathcal{M}\end{subarray}}p(y_{j}\mid x_{i})\log p(y_{j}\mid
x_{i})\right)}_{\text{H: entropy}}$

Here we aim to find a set of trajectories for $y_{j}$ which minimizes
$F(P_{y\mid x},x,y)$, thereby minimizing latency and synchronization times by
using a maximum entropy function to help convexify the original problem. Note
that so-called migration 333re-positioning controllers and re-assigning
network nodes. cost is outside the of scope of the present paper and so our
objective function does not reflect this cost, as in [5], [16], and [2] among
others.

##  IV SOLUTION

Based on the results of [21] and [22], in which the authors extend the results
of Rose to show that for a given set of trajectories, $\\{y_{j}(t)\\}$, a
Gibbs distribution will minimize equation (3), we have

$p(y_{j}\mid
x_{i})=\exp{\left(-\frac{d(x_{i},y_{j})}{T}\right)}/Z_{i}\quad\forall
i\in\mathcal{N},j\in\mathcal{M},$ (4)

where $d(x_{i},y_{j})=\lVert
x_{i}-y_{j}\rVert^{2}+\sum_{j^{\prime}\in\mathcal{M}}\lVert
y_{j}-y_{j^{\prime}}\rVert^{2}$ is the distance function, or so-called
distortion measure 444Distortion is a term in information theory that
signifies the dissimilarity or distance between two points. between node $i$
and controller-node $j$, and $Z_{i}$ can be seen as the usual normalizing
partition function. These association weights will become “hard” if we let $T$
go to zero, and uniform, as $T$ approaches a very high value. Formulation
$\eqref{eq:F}$ and the “annealing” or “temperature” parameter $T$ ensures that
the total system delay attains a good local minimum in theory, while the nodes
are initially maximally noncommittal towards the controllers. This latter
point is essential since according to the maximum entropy principle in
information theory, among all candidate distributions, the one with highest
entropy best describes the current state of the system. This approach also has
advantages for optimization over the surface of the cost function (3) where
local optima abound [20].

Using the terminology of [11], let
$[P_{y|x}]_{ij}=p(y_{j}|x_{i})\in\mathbb{R}^{N\times M}$ be the matrix that
contains information on the relative shape of the clusters. Similarly define
$[P_{x|y}]_{ij}=p(x_{i}|y_{j})\in\mathbb{R}^{N\times M}$ as the matrix
containing posterior associations (directly analogous to posterior
probabilities) $p(x_{i}|y_{j})$, which we calculate using Bayes’ rule, with
$p(x_{i})=\frac{1}{N}$, for all $i\in\mathcal{N}$. Moreover, define $P_{y}=$
diag$(p(y_{j}))\in\mathbb{R}^{M\times M}$ as the matrix containing information
on the mass of the clusters, where
$p(y_{j})=\sum_{i\in\mathcal{N}}p(y_{j}|x_{i})p(x_{i}).$ Let $\bar{P}_{y\mid
x}$, $\bar{P}_{x\mid y}\in\mathbb{R}^{2N\times 2M}$ and $\bar{P}_{y}\in
R^{2M\times 2M}$, such that $\bar{P}_{y\mid x}=P_{y\mid x}\otimes I_{2}$,
$\bar{P}_{x\mid y}=P_{x\mid y}\otimes I_{2}$, and $\bar{P}_{y}=P_{y}\otimes
I_{2}$. In prior work, we’ve shown that the optimal placement of controller
$y$ with respect to energy function $F$ follows as:

$y=\Theta^{-1}\bar{P}_{x\mid y}^{T}x$ (5)

where $\Theta\in\mathbb{R}^{2M\times 2M}$ is a block matrix with $M^{2}$
blocks of size $2\times 2$. The diagonal blocks are equal to $\eta I_{2}$
where $\eta=\gamma(M-1)+1$ and the non-diagonal blocks are equal to $-\gamma
I_{2}$. We show that for $\gamma\neq\frac{1}{N-M}$ and
$\gamma\neq\frac{1}{N-2M}$, $\Theta^{-1}$ is well defined (see [21]). Ideally
we want the function $F$ to serve as a control Lyapunov function, requiring
the time derivative of $F$ along the trajectory of network nodes and
controllers to be non-positive which then ensures a non-increasing value for
(3), our objective function. Following the development in [21] and [22], we
can show the following.

###### Theorem IV.1

Given the control Lyapunov function (3), for the system defined in (1) the
time derivative of $F$ has the following structure.

$\dot{F}=2\zeta^{T}\Gamma(\zeta)f(\zeta),\;\Gamma(\zeta)=\begin{bmatrix}&I_{2N\times
2N}&-\bar{P}_{y\mid x}\\\ &-\bar{P}_{y\mid x}^{T}&N\Theta P_{y}\end{bmatrix}$
(6)

###### Proof:

Using basic calculus and taking partial derivatives of $F$ with respect to its
constituents we can show that $\forall i\in\mathcal{N}$ and $j\in\mathcal{M}$,

$\frac{\partial F}{\partial
x_{i}}=2\left(x_{i}\sum_{j\in\mathcal{M}}p(y_{j}\mid
x_{i})-\sum_{j\in\mathcal{M}}y_{j}p(y_{j}\mid x_{i})\right)$

and

$\frac{\partial F}{\partial y_{j}}=2\eta Np(y_{j})y_{j}-N\gamma
p(y_{j})\sum_{j^{\prime}\neq
j}y_{j^{\prime}}-\sum_{i\in\mathcal{N}}p(y_{j}\mid x_{i})x_{i}.$

Thus so far we have shown that

$\frac{\partial F}{\partial\zeta}=2\zeta^{T}\Gamma(\zeta).$

The next step is to apply the chain rule

$\frac{dF}{dt}=\frac{\partial F}{\partial\zeta}\frac{\partial\zeta}{\partial
t}=\frac{\partial F}{\partial\zeta}f(\zeta),$

from which the desired result follows. ∎

Our goal here is to design a control law $u\in\mathbb{R}^{2M}$ such that the
output of system (1) asymptotically tracks the optimal placement of
controllers in the 2D plane based on the control Lyapunov function (3).
Following the results of [23], [24], [25], and [11] we propose the following
control law, and show it results in a non-increasing function $F(t).$

###### Theorem IV.2

For the nonlinear system given in Equation (2) if

$u=-\left[k_{0}+\frac{(x^{T}-y^{T}\bar{P}_{y\mid
x}^{T})\phi}{\bar{y}^{T}\bar{P}_{y}\bar{y}}\right]\bar{y}$ (7)

where $K_{0}>0$ is a positive scalar and
$\bar{y}=N\Theta\left(y-\Theta^{-1}\bar{P}_{x\mid y}^{T}x\right)$, then
$\dot{F}(t)\leq 0$ for all $t\in\mathbb{R}^{+}$.

###### Proof:

We can expand equation (6) to get

$\dot{F}=2\left(\left(x^{T}-y^{T}\bar{P}_{y\mid
x}^{T}\right)\phi+\left(-x^{T}\bar{P}_{y\mid x}+Ny^{T}\Theta
P_{y}\right)u\right).$

Now using the definition of $\bar{y}$ and $\frac{1}{N}\bar{P}_{y\mid
x}=\bar{P}_{x\mid y}\bar{P}_{y}$ we can show that

$\dot{F}=2\left(\left(x^{T}-y^{T}\bar{P}_{y\mid
x}^{T}\right)\phi+\bar{y}^{T}\bar{P}_{y}u\right).$ (8)

Substituting the control law (7) into (8) gives us
$\dot{F}=-2K_{0}\bar{y}^{T}P_{y}\bar{y}\leq 0$ for all
$\bar{y}\in\mathbb{R}^{2M}$, since $\bar{P}_{y}$ is assumed to be a positive
definite matrix 555Note that degenerate (zero mass) clusters are not allowed
in this formulation and diagonal elements of this diagonal matrix are always
positive. and $K_{0}>0$. ∎

To make explicit the result that $y$ asymptotically tracks the optimal
placement of controllers we state Corollary IV.1, which follows. We first
introduce Lemma IV.3 without proof which is useful in the proof of Theorem
IV.1. For details please see Lemma E.1. in [11].

###### Lemma IV.3

For a non-negative function $f:\mathbb{R}\rightarrow\mathbb{R}$ of bounded
variation, if $\int_{0}^{\infty}f(t)dt<\infty$ then
$\lim_{t\rightarrow\infty}f(t)=0$.

###### Corollary IV.1

For the dynamics given by system (1) using the control law in (7), $y$
asymptotically tracks the optimal placement of controller nodes. That is:

$\lim_{t\rightarrow\infty}y(t)=\Theta^{-1}P_{x\mid y}x(t)$

###### Proof:

Because the system is constrained within the compact set $\Omega$, the
continuous real-valued function $F$ is bounded from below. Since $\dot{F}\leq
0$ we must have that $F(t)\rightarrow F_{\infty}$ as $t\rightarrow\infty$.
This implies that
$\int_{0}^{\infty}-\dot{F}(\tau)d\tau=F(0)-F(\infty)<\infty$. Because
$-\dot{F}$ is non-negative, using Lemma IV.3 we deduce that
$\lim_{t\rightarrow\infty}-\dot{F}(t)=0$. Since
$-\dot{F}(t)=2K_{0}\bar{y}^{T}\bar{P}_{y}\bar{y}$ and $\bar{P}_{y}$ is
positive definite then we must have $\bar{y}(t)\rightarrow 0$ as $t\rightarrow
0$. Using the definition of $\bar{y}$ and because $\Theta$ is invertible by
design, $y-\Theta^{-1}\bar{P}_{x\mid y}x\in\text{Null}(\Theta)=\\{0\\}$. This
yields that $y(t)\rightarrow\Theta^{-1}\bar{P}_{x\mid y}x$ as
$t\rightarrow\infty$ analogous to Equation (5). ∎

|  |
---|---|---
Figure 2: Performance of RCP for four network topologies and mobility models. |  |
---|---|---
(a) | (b) | (c)
|  |
(d) | (e) | (f)
Figure 3: Performance of RCP for four network topologies and mobility models.

Initialize $y\in\mathbb{R}^{2M}$, starting temperature $T\approx\infty$,
current time $t=0$, time horizon $\tau\in\mathbb{R}^{+}$, time steps
$n\in\mathbb{N}$, and decay rate $0<\alpha<1$;

$\Delta t\leftarrow\frac{\tau}{n}$;

for  _$i=1$ to $n$_ do

update time: $t\leftarrow t+(i-1)\Delta t$;

update association weights $P_{y\mid x}$ using (4): $\small{p(y_{j}\mid
x_{i})=\exp{\left(-\frac{d(x_{i},y_{j})}{T}\right)}/Z_{i}\quad\forall
i\in\mathcal{N},j\in\mathcal{M}}\;$;

update $y$ using control law (7):
$u=-\left[k_{0}+\frac{(x^{T}-y^{T}\bar{P}_{y\mid
x}^{T})\phi}{\bar{y}^{T}\bar{P}_{y}\bar{y}}\right]\bar{y}$ $y(t+\Delta
t)\leftarrow y(t)+u(t)\Delta t$ update system temperature: $T\leftarrow\alpha
T$

end for

Algorithm 1 RCP

##  V Simulations

We performed simulations using Python 3.9.0 on a Razer Blade 15 laptop with
Intel Core i7-10750H @ 2.60 GHz CPU, 16.0 GB RAM and Windows 10 Operating
System. For the initial problem, data is generated as Gaussian distributions
with randomized mean and standard deviations. Each starting cluster
(distribution) is assigned to a destination cluster of equal size and each
point in the initial cluster is assigned to a random point in the respective
destination cluster. The network is modeled as a first-order linear dynamical
system similar to (1) with node positions given by
$x(t):\mathbb{R}^{+}\rightarrow\mathbb{R}^{2}$,
$x(t)=(x_{start}-x_{end})\exp(-kt)+x_{end}$. At $t=0$ we start at
$x_{start}\in\mathbb{R}^{2}$ and as $t\rightarrow\infty$ the system converges
to $x_{end}\in\mathbb{R}^{2}$.

The value $k$ for each point is randomized and is generated using the Rayleigh
distribution with parameter $\sigma=0.5$, and the probability distribution
function $f(x;\sigma)=\frac{x}{\sigma^{2}}\exp(\frac{-x^{2}}{2\sigma^{2}})$.
Rayleigh distributions are typically used for simulation of particle
trajectories, which have coordinate-wise normally-distributed velocities. Due
to arithmetic underflow that can occur in the floating point division in the
update rule (4) we recommend the following normalization approach for any
point $x\in\Omega$:

$x_{new}=\frac{x-\mu}{\sigma_{max}-\sigma_{min}}$ (9)

where $\mu=\frac{\int_{\Omega}xdx}{\int_{\Omega}dx}$ is the mass center of the
domain space $\Omega$. $\sigma_{min}=\min_{x\in\Omega}\left\lVert
x\right\rVert_{\infty}$ and $\sigma_{max}=\max_{x\in\Omega}\left\lVert
x\right\rVert_{\infty}$ are the minimal and maximal values the coordinates of
points in $\Omega$ can take, with $\left\lVert.\right\rVert_{\infty}$ being
the infinity or max norm. After this normalization the network is restrained
within the box $[-1,1]\times[-1,1]$

Figure 2 shows the trajectories generated by RCP algorithm. We encourage the
reader to visit this link
666https://www.youtube.com/playlist?list=PLkmxIANUXsFA2OCG7Uce1vBXYCqvvHSA3
for animations of these controller placement simulations. Starting and ending
positions of the clusters are slightly faded to indicate where the nodes have
started and will end. The purple trajectories show the near-optimal 777It has
been shown and is widely accepted that finding the globally optimal solution
for controller placement is an NP hard problem. Here we work with a high
quality locally optimal solution and refer to it as near-optimal for
convenience. placement of controllers calculated using the frame by frame
approach and the algorithm ECP-LL from [21]. This means that at each time step
ECP-LL finds a near-optimal placement of controllers, shown by the purple dots
along the optimal trajectories for a specific frozen snapshot of system. After
random initialization within $\Omega$, RCP should ideally track these purple
trajectories.

Figure 3 shows various properties of RCP algorithm. Plot (a) shows the CDF
888Cumulative distribution function. of inference time 999Here inference time
is the time it takes to compute optimal placements for a system snapshot. for
RCP algorithm given various network sizes. Plot (b) and (c) show the quartiles
of inference time for both RCP and ECP-LL algorithms using the box plot. Plot
(d) shows the distance of RCP placements to the optimal controller locations.
As can be seen this distance converges to zero as time goes by. Plot (e) shows
the evolution of total network delay for both ECP-LL and RCP algorithms. Plot
(f) compares the inference time of RCP versus ECP-LL algorithm across various
network sizes. A more detailed statistics on the inference time can be seen in
Table 2. These results show that RCP can be up to 25 times faster than
conventional frame by frame approach using ECP-LL.

TABLE II: Average inference time (Milliseconds). Network size | ECP-LL | RCP
---|---|---
| average | STD | average | STD
50 | 22.92 | 8.38 | 0.83 | 0.30
100 | 35.65 | 20.00 | 1.35 | 0.72
500 | 224.79 | 67.29 | 9.03 | 3.22
1000 | 370.30 | 167.19 | 14.27 | 6.56

Computational Complexity We can break down the computational complexity of RCP
as follows: (1) calculating mutual distances between all $x_{i},y_{j}$ pairs
($i\in\mathcal{N}$, $j\in\mathcal{M}$); (2) similar calculations for mutual
distances between controllers; (3) calculating the distortions
$d(x_{i},y_{j})$ for all $i\in\mathcal{N}$, $j\in\mathcal{M}$; (4) calculating
association probabilities; and (5) updating the $y_{j}$ trajectories. The
complexities for these operations are respectively: (1) $\mathcal{O}(NMd)$,
(2) $\mathcal{O}(M^{2}d)$, (3) $\mathcal{O}(Md)$, (4) $\mathcal{O}(NM)$ and
(5) $\mathcal{O}(MNd^{2})$. For terms (1) to (4) the calculations are
analogous to those in the study completed in [21]. For term (5) the result
comes from the fact that updating the $y_{j}$ requires calculating the
numerator $\mathcal{O}(MNd^{2}+Nd)$ and denominator $\mathcal{O}(M^{2}d^{2})$,
plus the final multiplication by $\bar{y}$, $\mathcal{O}(Md)$, which is
dominated by the term $\mathcal{O}(MNd^{2})$ for $N>>M$. For a fixed time
horizon $\tau$ we can express the overall computational complexity of RCP as
$\mathcal{O}(\tau NMd^{2})$. This is a significant gain over other DCP
algorithms like LiDy and LiDy+ discussed in [13], which respectively report
$\mathcal{O}(N^{2})$ and $\mathcal{O}(N^{3})$ complexities in terms of network
size. Using the result in Corollary IV.1 it can be seen that in the limit RCP
becomes a variation of the ECP-LL algorithm in [21] that is computed for only
one iteration per each system snapshot. This observations roughly means that,
in the limit, RCP is $\frac{T}{d}$ times faster than ECP-LL if on average ECP-
LL takes $T$ iterations to converge for each system snapshot. This is because
running ECP-LL over the time horizon will on average require $\mathcal{O}(\tau
TNMd)$ flops.

##  VI CONCLUSION

In this work we introduced RCP, a temporal clustering algorithm for real-time
controller placement in mobile SDN systems. To the best of our knowledge, RCP
is the first algorithm in DCP literature that exploits the temporal
relationships of the network dynamics in order to efficiently adapt placement
solutions in real-time. RCP leverages the principle of maximum entropy to
avoid poor local optima that abound on the surface of our balanced cost
function, and thus consistently provides high quality solutions. Unlike
conventional methods that shrink the decision space into a discrete set, our
algorithm allows use of the open search method for placement, which makes it
unlikely to yield sub-optimal solutions. RCP has linear $\mathcal{O}(n)$
iteration computational complexity with respect to the network size and can be
up to 25 faster than the conventional frame-by-frame approach. There are
several analytical properties of the RCP algorithm such as sensitivity to
temperature scheduling and convergence rate that we intend to address in
follow-up work. A future direction for this work that can improve practicality
of RCP is to include the estimation of the dynamics of the network, which we
assumed herein is fully available to the decision maker. Another important
direction is to incorporate a mechanism that enables RCP to dynamically change
the number of controllers in the network.

—

## References

  * [1] N. Mouawad, R. Naja, and S. Tohme, “Optimal and Dynamic SDN Controller Placement,” in 2018 International Conference on Computer and Applications, ICCA 2018, pp. 413–418, Institute of Electrical and Electronics Engineers Inc., 9 2018.
  * [2] M. Alharthi, A. E. M. Taha, and H. S. Hassanein, “Dynamic controller placement in software defined drone networks,” in 2019 IEEE Global Communications Conference, GLOBECOM 2019 - Proceedings, Institute of Electrical and Electronics Engineers Inc., 12 2019.
  * [3] M. A. Sayeed, R. Kumar, and V. Sharma, “Efficient data management and control over WSNs using SDN-enabled aerial networks,” International Journal of Communication Systems, vol. 33, p. e4170, 1 2020.
  * [4] C. Singhal and K. Rahul, “LB-UAVnet: Load Balancing Algorithm for UAV Based Network using SDN,” in International Symposium on Wireless Personal Multimedia Communications, WPMC, vol. 2019-November, IEEE Computer Society, 11 2019.
  * [5] S. Toufga, S. Abdellatif, H. T. Assouane, P. Owezarski, and T. Villemur, “Towards Dynamic Controller Placement in Software Defined Vehicular Networks,” Sensors, vol. 20, p. 1701, 3 2020.
  * [6] K. S. Kalupahana Liyanage, M. Ma, and P. H. Joo Chong, “Controller placement optimization in hierarchical distributed software defined vehicular networks,” Computer Networks, vol. 135, pp. 226–239, 4 2018.
  * [7] A. Papa, T. De Cola, P. Vizarreta, M. He, C. Mas Machuca, and W. Kellerer, “Dynamic SDN Controller Placement in a LEO Constellation Satellite Network,” in 2018 IEEE Global Communications Conference (GLOBECOM), pp. 206–212, IEEE, 12 2018.
  * [8] D. K. Luong, Y. F. Hu, J. P. Li, F. Benamrane, M. Ali, and K. Abdo, “Traffic-aware Dynamic Controller Placement using AI techniques in SDN-based aeronautical networks,” in AIAA/IEEE Digital Avionics Systems Conference - Proceedings, vol. 2019-September, Institute of Electrical and Electronics Engineers Inc., 9 2019.
  * [9] A. Basta, A. Blenk, M. Hoffmann, H. J. Morper, K. Hoffmann, and W. Kellerer, “SDN and NFV dynamic operation of LTE EPC gateways for time-varying traffic patterns,” in Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST, vol. 141, pp. 63–76, Springer Verlag, 2015.
  * [10] B. Heller, R. Sherwood, and N. McKeown, “The controller placement problem,” in Proceedings of the first workshop on Hot topics in software defined networks - HotSDN ’12, (New York, New York, USA), p. 7, ACM Press, 2012.
  * [11] P. Sharma, S. M. Salapaka, and C. L. Beck, “Entropy-based framework for dynamic coverage and clustering problems,” IEEE Transactions on Automatic Control, vol. 57, pp. 135–150, 1 2012.
  * [12] S. Champagne, T. Makanju, C. Yao, N. Zincir-Heywood, and M. Heywood, “A genetic algorithm for dynamic controller placement in software defined networking,” in GECCO 2018 Companion - Proceedings of the 2018 Genetic and Evolutionary Computation Conference Companion, (New York, NY, USA), pp. 1632–1639, Association for Computing Machinery, Inc, 7 2018.
  * [13] M. T. I. ul Huque, W. Si, G. Jourjon, and V. Gramoli, “Large-Scale Dynamic Controller Placement,” IEEE Transactions on Network and Service Management, vol. 14, pp. 63–76, 3 2017.
  * [14] M. He, A. Varasteh, and W. Kellerer, “Toward a Flexible Design of SDN Dynamic Control Plane: An Online Optimization Approach,” IEEE Transactions on Network and Service Management, vol. 16, pp. 1694–1708, 12 2019.
  * [15] M. He, A. Basta, A. Blenk, and W. Kellerer, “How Flexible is Dynamic SDN Control Plane?,” tech. rep., Technical University of Munich, 2018.
  * [16] S. Wu, X. Chen, L. Yang, C. Fan, and Y. Zhao, “Dynamic and static controller placement in Software-Defined Satellite Networking,” Acta Astronautica, vol. 152, pp. 49–58, 11 2018.
  * [17] M. He, A. Basta, A. Blenk, and W. Kellerer, “Modeling flow setup time for controller placement in SDN: Evaluation for dynamic flows,” in IEEE International Conference on Communications, Institute of Electrical and Electronics Engineers Inc., 7 2017.
  * [18] T. Wang, F. Liu, and H. Xu, “An Efficient Online Algorithm for Dynamic SDN Controller Assignment in Data Center Networks,” IEEE/ACM Transactions on Networking, vol. 25, pp. 2788–2801, 10 2017.
  * [19] Q. Qin, K. Poularakis, G. Iosifidis, S. Kompella, and L. Tassiulas, “SDN Controller Placement With Delay-Overhead Balancing in Wireless Edge Networks,” IEEE Transactions on Network and Service Management, vol. 15, pp. 1446–1459, 12 2018.
  * [20] K. Rose, “Deterministic Annealing for Clustering, Compression, Classification, Regression, and Related Optimization Problems,” tech. rep., California Institute of Technology, 1998.
  * [21] R. Soleymanifar, A. Srivastava, C. Beck, and S. Salapaka, “A Clustering Approach to Edge Controller Placement in Software-Defined Networks with Cost Balancing,” IFAC-PapersOnLine, vol. 53, pp. 2642–2647, 1 2020.
  * [22] Y. Xu, S. M. Salapaka, and C. L. Beck, “Clustering and coverage control for systems with acceleration-driven dynamics,” IEEE Transactions on Automatic Control, vol. 59, no. 5, pp. 1342–1347, 2014.
  * [23] P. K. G. B. R. Sepulchre, M. Jankovic, “Constructive Nonlinear Control - R. Sepulchre, M. Jankovic, P.V. Kokotovic - Google Books.”
  * [24] E. D. Sontag, “Lyapunov-like Characterization of Asymptotic Controllability.,” SIAM Journal on Control and Optimization, vol. 21, pp. 462–471, 2 1983.
  * [25] E. D. Sontag, “A ’universal’ construction of Artstein’s theorem on nonlinear stabilization,” Systems and Control Letters, vol. 13, pp. 117–123, 8 1989\.


# Uncertainty-Aware AB3DMOT by
Variational 3D Object Detection

Illia Oleksiienko and Alexandros Iosifidis  DIGIT, Department of Electrical
and Computer Engineering, Aarhus University, Denmark
<EMAIL_ADDRESS>
###### Abstract

Autonomous driving needs to rely on high-quality 3D object detection to ensure
safe navigation in the world. Uncertainty estimation is an effective tool to
provide statistically accurate predictions, while the associated detection
uncertainty can be used to implement a more safe navigation protocol or
include the user in the loop. In this paper, we propose a Variational Neural
Network-based TANet 3D object detector to generate 3D object detections with
uncertainty and introduce these detections to an uncertainty-aware AB3DMOT
tracker. This is done by applying a linear transformation to the estimated
uncertainty matrix, which is subsequently used as a measurement noise for the
adopted Kalman filter. We implement two ways to estimate output uncertainty,
i.e., internally, by computing the variance of the CNNs outputs and then
propagating the uncertainty through the post-processing, and externally, by
associating the final predictions of different samples and computing the
covariance of each predicted box. In experiments, we show that the external
uncertainty estimation leads to better results, outperforming both internal
uncertainty estimation and classical tracking approaches. Furthermore, we
propose a method to initialize the Variational 3D object detector with a
pretrained TANet model, which leads to the best performing models.

###### Index Terms:

3D Object Detection, 3D Object Tracking, Point Cloud, Uncertainty Estimation,
Bayesian Neural Networks, Variational Neural Networks

##  I Introduction

3D Object Detection (3D OD) is the problem that aims to detect objects in the
3D world, providing the coordinates relative to the sensor and true world
sizes of the detected objects. In contrast to 2D Object Detection which is
commonly based on the appearance of objects in an image or video frame, in 3D
OD the size of objects is not distorted by projections and rigid objects
retain their size on every data frame. However, to obtain the data that can
accurately represent objects in 3D requires specialized sensors. Even though
color images [1, 2, 3, 4, 5] or stereo images [6, 7, 8] can be utilized to
obtain 2D-like object detections and use those to estimate the corresponding
3D bounding boxes, the detection accuracy and speed of such methods is
inferior to that of methods, such as VoxelNet [9], SECOND [10], PointPillars
[11] and TANet [12], utilizing point cloud data captured by Lidar sensors.

3D Multiple Object (3D MOT) tracking aims to not only find the position of
objects in the 3D world, but also assign a unique ID to each of them for the
entire duration that an object appears in the data sequence. 3D MOT can be
performed in a single stage, where the object detection in each frame and
objects associations in successive frames are performed by the same model [13,
14, 15], or in two stages, where the detections are generated by a 3D OD model
and the object associations in successive frames are performed separately.

(a) 3D bounding box with the uncertainty provided by the Variational TANet 3D
object detector

(b) 3D bounding boxes with uncertainties provided to the Kalman filter of the
uncertainty-aware AB3DMOT tracker

Figure 1: Examples of a 3D bounding boxes with raw uncertainties obtained by
the proposed Variational TANet (top figure), and the uncertainties provided to
the Kalman filter of the proposed Uncertainty-aware AB3DMOT (bottom figure).
Yellow color represents higher probability, while the purple color represents
lower probability. Blue boxes correspond to the mean predictions.

Most 3D OD methods exploit object detections provided by powerful object
detectors, commonly based on deep neural networks providing point estimates of
their outputs. While recent advances in deep learning have led to remarkable
results, this approach strongly restricts the ability of the object
association step to exploit possible uncertainties in the object detections.
Moreover, there has been some evidence that the predictive uncertainty of
accurate deep learning models does not necessarily correlate with their
confidence in their outputs [16, 17]. Uncertainty estimation in neural
networks allows using the uncertainty in predictions to perform better
decision-making, which is important in critical fields, such as medical image
analysis or autonomous driving. The practical application of uncertainty
estimation includes 3D Object Tracking [18, 19], 3D Object Detection [20, 21,
22], 3D Human Pose Tracking [23], Steering Angle Prediction [24], providing
better prediction and control than without the use of uncertainty.

In this paper, we propose an uncertainty-aware 3D object tracking pipeline. We
show how the TANet 3D object detector [12] can be formulated and trained as a
Variational Neural Network [25] to generate object detections with uncertainty
in two ways, i.e., internally with variance estimation, and externally with
covariance estimation. We combine them with a two-stage 3D MOT method called
AB3DMOT [26] that utilizes a 3D Kalman filter [27] for state prediction and
Hungarian algorithm [28] for objects’ association. We modify AB3DMOT to use
the predicted output uncertainty of the 3D OD model in the 3D Kalman Filter
and show that this improves the Multi Object Tracking Accuracy (MOTA), F1
score and Mostly Lost (ML) metrics.

The remainder of the paper is structured as follows. Section II describes
related and prior work. In Section III we describe the proposed approach,
including the Variational TANet model and its training and the proposed
uncertainty-aware AB3DMOt. Section IV outlines the experimental protocol and
provides experimental results. Section V concludes this paper111Our code is
available at gitlab.au.dk/maleci/opendr/ua-ab3dmot.

##  II Related Work

3D OD based on Lidar point clouds cannot be performed with standard CNNs, as
the point cloud data consists of a set of irregular 3D point positions. In
order to introduced point cloud data as inputs to Deep Learning methods, one
needs to structure it first, with voxelization being the most popular way of
doing so. Voxelization is performed by selecting a region of interest in the
3D space and splitting it using a grid of same-sized cuboid shapes, called
voxels. VoxelNet [18] creates a 3D grid of voxels and processes points inside
each voxel to create voxel features, which are later processed by 3D and 2D
convolutional layers. To accelerate the process, PointPillars [11] uses voxels
with the maximum vertical size called pillars resulting in a 2D grid that can
be used as input to a 2D CNN model, which is much faster than using 3D
convolutions. TANet [12] introduces the Triple Attention module for extracting
better features from pillars and a Coarse-to-Fine regression module that
produces coarse detections first and then refines them with an additional
subnetwork.

The fastest 2D Multiple Object Tracking (MOT) method called SORT [29] utilizes
2D Kalman Filter [27] and Hungarian algorithm [28] to associate the 2D object
detections provided by a Deep Learning model. The 3D version of SORT, called
AB3DMOT [26], performs better than SORT in 3D MOT by utilizing a 3D Kalman
Filter instead of a 2D one. In [18], the use of uncertainty for 3D SOT is
investigated by training the voxel-based 3D OD method SECOND [10] with an
additional branch to predict the model’s uncertainty, Then, the predicted
uncertainty is used in the Kalman filter’s measurement noise leading to better
tracking results. The use of predicted uncertainty, instead of assuming a
unit-Gaussian distribution over the measurements expressed by using the
identity matrix, for measurement noise is also supported by [30].

Uncertainty estimation in neural networks can be performed using different
ways to model uncertainty. The four main categories of uncertainty estimation
methods defined in [31] are: Deterministic Methods [32, 18] which use a single
network pass with uncertainty estimated from one of the network branches or by
analyzing the behavior of the network; Bayesian Neural Networks (BNNs) [33,
34] that sample different models from the corresponding weight distribution
and process the input using them resulting in a set of predictions, mean and
variance of which are used to estimating the predictive distribution; Ensemble
Methods [35, 36], that can also be seen as BNNs with Categorical distribution;
and Test-Time Data Augmentation methods [37, 38, 39] that apply different
augmentations to the input to create a set of slightly different inputs that
are processed by the same model.

While Deterministic Methods require a single pass of the network leading to
lower inference time, they usually perform worse than the rest of the methods
as they can be seen as a point estimation of statistically better Bayesian
approaches. Variational Neural Networks [25, 40] are similar to BNNs, but
consider a Gaussian distribution over the outputs of each layer, the mean and
variance of which are generated by the corresponding sub-layers. The output
uncertainty is calculated by sampling different values from the corresponding
Gaussian distributions, resulting in multiple predictions for the same input.

##  III Uncertainty-aware 3D Object Tracking

###  III-A Variational TANet

TANet [12] is a pillar-based 3D Object Detection model that improves
PointPillars by introducing the Triple Attention module to extract better
pillar (voxel) features and by using the Coarse-to-Fine fully convolutional
network to process the voxel pseudo image and generate the bounding box
predictions. TANet is an anchor-based method [41], which means that the output
from the Coarse-to-Fine network is a voxel-wise prediction with position and
sizes predicted as offsets from the corresponding anchor. This output is then
processed by a Non-maximum-suppression module to select the most likely boxes
and decoded based on the anchors to create the final 3D bounding boxes.

We train a Variational TANet (VTANet) by replacing the fully convolutional
Coarse-to-Fine module with a Variational Neural Network (VNN) [25, 40] based
version of it. The training is performed using the same loss function and
training procedure, except we use multiple model samples per each data input
and train for the mean of the predictions of all samples.

We propose two ways for the VTANet model to provide its estimated uncertainty
to the subsequent tracker. The first, namely internal, way computes mean and
variance of predictions of the Variational Coarse-to-Fine network and provides
the variance through the decoding stage by treating the values as Gaussian
random variables. The outputs of the CNN are voxel-wise in the form of
$(x,y,z,w,l,h,r)$ with respect to an anchor of the same data format, where
$(x,y,z)$ is the relative position vector, $(w,l,h)$ is the relative size
vector and $r$ is the relative rotation angle. For a set of predictions from
$(x_{i},y_{i},z_{i},w_{i},l_{i},h_{i},r_{i}),i\in[1,S]$, where $S$ is the
number of samples, we compute the mean prediction
$(m_{x},m_{y},m_{z},m_{w},m_{l},m_{h},m_{r})$ and the corresponding variance
$(v_{x},v_{y},v_{z},v_{w},v_{l},v_{h},v_{r})$. The anchor
$(x_{a},y_{a},z_{a},w_{a},l_{a},h_{a},r_{a})$ that corresponds to the
prediction is used to create the decoded predictions
$(\hat{x},\hat{y},\hat{z},\hat{w},\hat{l},\hat{h},\hat{r})$ as follows:

$\displaystyle\begin{split}&d=\sqrt{l_{a}^{2}+w_{a}^{2}},\\\
&(\hat{x},\hat{y})=(m_{x},m_{y})d+(x_{a},y_{a}),\\\
&(\hat{w},\hat{l},\hat{h})=(e^{m_{w}}w_{a},e^{m_{l}}l_{a},e^{m_{h}}h_{a}),\\\
&\hat{r}=m_{r}+r_{a},\\\ &\hat{z}=m_{z}h_{a}+z_{a}+h_{a}/2-\hat{h}/2.\\\
\end{split}$ (1)

The corresponding variances
$(v_{\hat{x}},v_{\hat{y}},v_{\hat{z}},v_{\hat{w}},v_{\hat{l}},v_{\hat{h}},v_{\hat{r}})$
are calculated as follows:

$\displaystyle\begin{split}&d=\sqrt{l_{a}^{2}+w_{a}^{2}},\\\
&\mathrm{v_{exp}}(m,v)=e^{2m+2v}-e^{2m+v},\\\
&(v_{\hat{x}},v_{\hat{y}})=(v_{x},v_{y})d^{2},\\\
&(v_{\hat{w}},v_{\hat{l}},v_{\hat{h}})=\\\
&\>\>\>(\mathrm{v_{exp}}(\hat{w},v_{w})w_{a}^{2},\mathrm{v_{exp}}(\hat{l},v_{l})l_{a}^{2},\mathrm{v_{exp}}(\hat{h},v_{h})h_{a}^{2})\\\
&\hat{r}=v_{r},\\\ &v_{\hat{z}}=v_{z}h_{a}^{2},\\\ \end{split}$ (2)

where $\mathrm{v_{exp}}(m,v)$ is the variance of the exponent of the Gaussian
random variable.

TABLE I: Tracking results on KITTI tracking dataset. Model |  Uncertainty method |  Training Samples |  Inference Samples |  Tracking Parameters | MOTA%$\uparrow$ | F1%$\uparrow$ | ML%$\downarrow$
---|---|---|---|---|---|---|---
Voxel von-Mises [18] |  deterministic |  - |  - |  SORT [29] | - | 55.10 | 30.60
TANet [12] |  - |  - |  - |  AB3DMOT [26] | 68.71 | 85.69 | 8.58
IVTANet + UA-AB3DMOT |  covar |  2 |  4 |  $\alpha=0.6,\>\beta=5$ | 72.30 | 87.34 | 7.74
IVTANet + UA-AB3DMOT |  covar |  2 |  4 |  $\alpha=0,\>\beta=1$ | 72.13 | 87.26 | 7.74
IVTANet + UA-AB3DMOT |  covar |  2 |  4 |  $\alpha=1,\>\beta=0$ | 72.05 | 87.22 | 7.74
VTANet + UA-AB3DMOT |  covar |  3 |  3 |  $\alpha=0.6,\>\beta=5$ | 69.63 | 86.46 | 7.95
VTANet + UA-AB3DMOT |  covar |  3 |  3 |  $\alpha=0,\>\beta=1$ | 69.48 | 86.39 | 8.16
VTANet + UA-AB3DMOT |  covar |  3 |  4 |  $\alpha=0.6,\>\beta=5$ | 69.42 | 86.38 | 9.00
VTANet + UA-AB3DMOT |  covar |  3 |  3 |  $\alpha=1,\>\beta=0$ | 69.15 | 86.31 | 9.00
VTANet + UA-AB3DMOT |  covar |  3 |  4 |  $\alpha=1,\>\beta=0$ | 68.86 | 85.04 | 9.21
VTANet + UA-AB3DMOT |  covar |  2 |  4 |  $\alpha=0.6,\>\beta=5$ | 68.54 | 86.13 | 8.16
VTANet + UA-AB3DMOT |  var |  3 |  4 |  $\alpha=0.5,\>\beta=5$ | 68.46 | 85.91 | 7.95

The second, namely external, way to compute uncertainty runs the full pipeline
of TANet to create $S$ 3D bounding box predictions, where $S$ is the number of
neural network parameter samples. These predictions are then grouped by
finding the best association for each predicted object, similarly to the
Hungarian algorithm on the tracking step. Consider the set of predictions
$P^{S}=\\{p_{i}\>|\>i\in[1,\dots,S]\\}$ where each element $p_{i}$ is a set of
3D bounding boxes $p_{i}=\\{b_{k}\>|\>k\in[1,\dots,K_{i}]\\}$, where $K_{i}$
is the number of predicted boxes for the sample $i$. For different neural
network parameter samples, some boxes with high uncertainty may or may not
appear, which results in slightly different values of $K_{i}$. We define the
association set $A(P)$ as a set of box groups $\\{g_{q}\\}$ where each group
consists of 3D bounding boxes from different samples with the closest
distances to each other, but no more than $1$ meter. The groups are created by
iterating through all boxes for each sample and checking the smallest distance
to the average position of each existing group. If the distance is lower than
$1$ meter, the object is added to the selected group, and otherwise it creates
a new group:

$\displaystyle\begin{split}&\forall i\in[1..S]\>\forall k\in[1..K_{i}]\\\
&\hat{G}(b_{k})=\underset{g_{q}}{\mathrm{argmin}}\>\>|\mathrm{avg}(\\{b^{\mathrm{x,y,z}}\in
g_{q}\\})-b^{\mathrm{x,y,z}}_{k}|\\\
&G(b_{k})=\begin{cases}\hat{G}(b_{k}),&\text{if
}|\mathrm{avg}(\\{b^{\mathrm{x,y,z}}\in\hat{G}(b_{k})\\})-b^{\mathrm{x,y,z}}_{k}|\leq
1,\\\ g_{\text{new}},&\text{otherwise},\end{cases}\\\
&g_{q}=\\{b_{k}\>|\>G(b_{k})=q,\>i\in[1..S],\>k\in[1..K_{i}]\\},\end{split}$
(3)

where $b^{x,y,z}$ is a position of the bounding box $b$ and
$\mathrm{avg}(\cdot)$ is the averaging function. For each group $g_{q}$, we
compute the mean bounding box and the covariance matrix in the form of a
$7\times 7$ matrix for position $(x,y,z)$, size $(w,h,l)$ and rotation
$\alpha$.

###  III-B Initialization of Variational TANet by pretrained model

Instead of training the VTANet model from scratch, we can initialize it based
on an already trained TANet model which provides point estimates. This can be
done based on the fact that infinitely small variance in a Gaussian
distribution transforms it into a Dirac delta distribution, with all
distributional mass placed on the mean value. By following the reverse
process, we initialize the VTANet model with means from the corresponding
pretrained TANet parameters, and the variance weights are set to be small
values by either filling them with constant values or by using Xavier normal
or uniform initialization [42]. Small variance values will not deviate too
much from the initial pretrained values, but allow for training the whole
model together and to find the optimal variance and mean parameters.

###  III-C Uncertainty-Aware AB3DMOT

As shown in [18, 30], the Kalman filter benefits from providing actual
uncertainties instead of assuming a unit-Gaussian distribution over the
measurements. We follow this approach and provide the modified variance
diagonal matrices or covariance matrices from the predicted uncertainties to
the Kalman filter. We modify the uncertainty matrices provided by the detector
with a linear transformation:

$\hat{\Sigma}=\alpha I+\beta\Sigma,$ (4)

where $\hat{\Sigma}$ is the uncertainty provided to the Kalman filter,
$\Sigma$ is the uncertainty predicted by the VTANet object detector, $\alpha$
is a hyperparameter used to control the contribution of the base uncertainty
to $\hat{\Sigma}$, and $\beta$ is a hyperparameter that controls the
contribution of the predicted uncertainty to $\hat{\Sigma}$. This
transformation aims to provide a degree of freedom for the Kalman filter in
using the predicted object detections while utilizing the actual uncertainties
in the predictions. Using the values $\alpha=1$ and $\beta=0$ leads to the
standard AB3DMOT exploiting unit-Gaussian distribution measurement noise in
the Kalman filter. Fig. 1 shows the difference between the uncertainty from
the detector and the modified uncertainty provided to the Kalman filter.

##  IV Experiments

We train TANet and VTANet models using the standard training procedure on
KITTI [43] dataset described in [12]. VTANet models are trained with sample
count in $[1,\dots,4]$ range and each model is evaluated with AB3DMOT on KITTI
tracking dataset with every number of samples from the same range. We train
the internal uncertainty VTANet models that provide the variance values and
the external uncertainty models that provide the covariance values. Each model
is evaluated with the different configuration of uncertainty transformation
parameters $\alpha$ and $\beta$, including $\alpha=0$, $\beta=1$ for the
predicted uncertainty only, $\alpha=1$, $\beta=0$ to not use the predicted
uncertainty and different combinations of $\alpha\in[0,1]$ and
$\beta\in\\{0.1,1,5,10,50\\}$. Additionally, we train IVTANet models which are
initialized with a pretrained TANet values for means and small variance
weights and trained using the same training procedure as VTANet models. We
compare the performance of the proposed method with that of the Voxel von-
Mises method [18], which is the only method we found in the literature
incorporating uncertainty estimation in 3D object tracking. This method
employs SECOND [10] for 3D OD and SORT [29] for objects associations.

Table I shows the performance of the competing models on the KITTI tracking
dataset based on three performance metrics, namely the Multi Object Tracking
Accuracy (MOTA), F1 score, and Mostly Lost (ML). This table also provides
information on the hyperparameter values used for different model, i.e., the
type of adopted uncertainty estimation, the number of network parameter
samples used during training and inference, and the tracking method and
hyperparameter values.

As can be seen, the proposed uncertainty-aware 3D MOT method with a VTANet
trained from scratch, i.e., VTANet + UA-AB3DMOT, provides better MOTA, F1 and
ML scores compared to the classic 3D MOT approach combining TANet with
AB3DMOT, i.e., TANet + AB3DMOT, due to the use of uncertainty. The external
way to compute uncertainty as covariance provides better results compared to
the internal one providing variance across all configurations, and therefore,
only a sub-set of configurations is provided in the results. The Voxel von-
Mises method [18] provides much worse results due to the use of inferior
methods for each of its processing steps, i.e., it adopts the less accurate 3D
detector SECOND [10], the less suited for 3D object detection tracker SORT
[29] and a deterministic uncertainty estimation method that does not rely on a
BNN or an Ensemble method during training. The best MOTA, F1 and ML scores are
achieved by the configurations of the proposed method which employ a VTANet
pretrained using a TANet providing point estimates. Those are denoted by
IVTANet + UA-AB3DMOT in Table I. As can be seen in the results, the use of an
IVTANet 3D object detector improves performance compared to the classic 3D MOT
approach even without exploiting the estimated uncertainty (i.e., when
$\alpha=1$ and $\beta=0$). Overall, the highest performance is achieved by
using a VTANet obtained by training a pretrained TANet combined with the
AB3DMOT model exploiting the estimated uncertainty (IVTANet + UA-AB3DMOT). It
is interesting to see that the use of the same linear combination values
($\alpha=0.6$ and $\beta=5$) leads to the best performance when both VTANet
and IVTANet 3D object detectors are used.

##  V Conclusions

In this paper, we proposed an uncertainty-aware 3D object tracking pipeline
that utilizes a Variational Neural Network-based version of TANet 3D object
detector to generate predictions with uncertainty in two different ways, i.e.,
internally with variance estimation and externally with covariance estimation.
Predictions from the detector are introduced into the uncertainty-aware
tracker that utilizes the estimated uncertainty to determine the measurement
noise in the Kalman filter, leading to an improvement in MOTA, F1 and ML
metrics. We use a pretrained TANet model to initialize mean weights of a
Variational TANet and initialize the variance weights with small values. The
resulting model is trained using the regular training procedure and leads to a
much better tracking performance compare to the models trained from scratch.

## Acknowledgement

This work has received funding from the European Union’s Horizon 2020 research
and innovation programme under grant agreement No 871449 (OpenDR). This
publication reflects the authors’ views only. The European Commission is not
responsible for any use that may be made of the information it contains.

## References

  * [1] Xiaozhi Chen, Kaustav Kundu, Ziyu Zhang, Huimin Ma, Sanja Fidler, and Raquel Urtasun,  “Monocular 3d object detection for autonomous driving,”  in CVPR, 2016, pp. 2147–2156.
  * [2] Tong He and Stefano Soatto,  “Mono3d++: Monocular 3d vehicle detection with two-scale 3d hypotheses and task priors,”  in AAAI, 2019, pp. 8409–8416.
  * [3] Bin Xu and Zhenzhong Chen,  “Multi-level fusion based 3d object detection from monocular images,”  in CVPR, 2018, pp. 2345–2353.
  * [4] Zengyi Qin, Jinglu Wang, and Yan Lu,  “Monogrnet: A geometric reasoning network for monocular 3d object localization,”  in AAAI, 2019, pp. 8851–8858.
  * [5] Thomas Roddick, Alex Kendall, and Roberto Cipolla,  “Orthographic feature transform for monocular 3d object detection,”  in BMVC, 2019, p. 285.
  * [6] Yan Wang, Wei-Lun Chao, Divyansh Garg, Bharath Hariharan, Mark E. Campbell, and Kilian Q. Weinberger,  “Pseudo-lidar from visual depth estimation: Bridging the gap in 3d object detection for autonomous driving,”  in CVPR, 2019, pp. 8445–8453.
  * [7] Yurong You, Yan Wang, Wei-Lun Chao, Divyansh Garg, Geoff Pleiss, Bharath Hariharan, Mark Campbell, and Kilian Q. Weinberger,  “Pseudo-LiDAR++: Accurate Depth for 3D Object Detection in Autonomous Driving,”  in ICLR, 2020.
  * [8] Chengyao Li, Jason Ku, and Steven L. Waslander,  “Confidence guided stereo 3d object detection with split depth estimation,”  IROS, pp. 5776–5783, 2020.
  * [9] Yin Zhou and Oncel Tuzel,  “Voxelnet: End-to-end learning for point cloud based 3d object detection,”  in CVPR, 2018, pp. 4490–4499.
  * [10] Yan Yan, Yuxing Mao, and Bo Li,  “SECOND: sparsely embedded convolutional detection,”  Sensors, vol. 18, no. 10, pp. 3337, 2018.
  * [11] Alex H Lang, Sourabh Vora, Holger Caesar, Lubing Zhou, Jiong Yang, and Oscar Beijbom,  “PointPillars: Fast Encoders for Object Detection from Point Clouds,”  in CVPR, 2019.
  * [12] Zhe Liu, Xin Zhao, Tengteng Huang, Ruolan Hu, Yu Zhou, and Xiang Bai,  “Tanet: Robust 3d object detection from point clouds with triple attention,”  in AAAI, 2020, pp. 11677–11684.
  * [13] Tianwei Yin, Xingyi Zhou, and Philipp Krähenbühl,  “Center-based 3d object detection and tracking,”  CoRR, vol. abs/2006.11275, 2020.
  * [14] Hou-Ning Hu, Qi-Zhi Cai, Dequan Wang, Ji Lin, Min Sun, Philipp Krähenbühl, Trevor Darrell, and Fisher Yu,  “Joint monocular 3d vehicle detection and tracking,”  in CVF, 2019, pp. 5389–5398.
  * [15] Martin Simon, Karl Amende, Andrea Kraus, Jens Honer, Timo Sämann, Hauke Kaulbersch, Stefan Milz, and Horst-Michael Gross,  “Complexer-yolo: Real-time 3d object detection and tracking on semantic point clouds,”  in CVPR, 2019, pp. 1190–1199.
  * [16] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger,  “On calibration of modern neural networks,”  in ICML, 2017, pp. 1321–1330.
  * [17] Matthias Minderer, Josip Djolonga, Rob Romijnders, Frances Ann Hubis, Xiaohua Zhai, Neil Houlsby, Dustin Tran, and Mario Lucic,  “Revisiting the Calibration of Modern Neural Networks,”  in NeurIPS, 2021.
  * [18] Yuanxin Zhong, Minghan Zhu, and Huei Peng,  “Uncertainty-aware voxel based 3d object detection and tracking with von-mises loss,”  arXiv:2011.02553, 2020.
  * [19] Jianren Wang, Siddharth Ancha, Yi-Ting Chen, and David Held,  “Uncertainty-aware self-supervised 3d data association,”  in RSJ, 2020, pp. 8125–8132.
  * [20] Di Feng, Lars Rosenbaum, and Klaus Dietmayer,  “Towards safe autonomous driving: Capture uncertainty in the deep neural network for lidar 3d vehicle detection,”  in ITSC, 2018, pp. 3266–3273.
  * [21] Gregory P. Meyer, Ankit Laddha, Eric Kee, Carlos Vallespi-Gonzalez, and Carl K. Wellington,  “Lasernet: An efficient probabilistic 3d object detector for autonomous driving,”  in CVPR, 2019, pp. 12677–12686.
  * [22] Gregory P. Meyer and Niranjan Thakurdesai,  “Learning an uncertainty-aware object detector for autonomous driving,”  in IROS, 2020, pp. 10521–10527.
  * [23] Ben Daubney and Xianghua Xie,  “Tracking 3d human pose with large root node uncertainty,”  in CVPR, 2011, pp. 1321–1328.
  * [24] Antonio Loquercio, Mattia Segu, and Davide Scaramuzza,  “A general framework for uncertainty estimation in deep learning,”  RA-L, vol. 5, no. 2, pp. 3153–3160, 2020.
  * [25] Illia Oleksiienko, Dat Thanh Tran, and Alexandros Iosifidis,  “Variational neural networks,”  arxiv:2207.01524, 2022.
  * [26] Xinshuo Weng, Jianren Wang, David Held, and Kris Kitani,  “3D Multi-Object Tracking: A Baseline and New Evaluation Metrics,”  IROS, 2020.
  * [27] R. E. Kalman,  “A New Approach to Linear Filtering and Prediction Problems,”  J. Basic Eng., vol. 82, no. 1, pp. 35–45, 1960.
  * [28] H. W. Kuhn,  “The hungarian method for the assignment problem,”  Nav. Res. Logist., vol. 2, no. 1‐2, pp. 83–97, 1955.
  * [29] Alex Bewley, ZongYuan Ge, Lionel Ott, Fabio Tozeto Ramos, and Ben Upcroft,  “Simple online and realtime tracking,”  in IEEE International Conference on Image Processing, 2016, pp. 3464–3468.
  * [30] Rebecca L. Russell and Christopher Reale,  “Multivariate uncertainty in deep learning,”  IEEE Transactions on Neural Networks and Learning Systems, vol. 33, no. 12, pp. 7937–7943, 2022.
  * [31] Jakob Gawlikowski, Cedrique Rovile Njieutcheu Tassi, Mohsin Ali, Jongseok Lee, Matthias Humt, Jianxiang Feng, Anna M. Kruspe, Rudolph Triebel, Peter Jung, Ribana Roscher, Muhammad Shahzad, Wen Yang, Richard Bamler, and Xiao Xiang Zhu,  “A survey of uncertainty in deep neural networks,”  arxiv:2107.03342, 2021.
  * [32] Murat Sensoy, Lance Kaplan, and Melih Kandemir,  “Evidential deep learning to quantify classification uncertainty,”  in NeurIPS, 2018, p. 3183–3193.
  * [33] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra,  “Weight Uncertainty in Neural Networks,”  in JMLR, 2015, vol. 37, pp. 1613–1622.
  * [34] Martin Magris and Alexandros Iosifidis,  “Bayesian learning for neural networks: an algorithmic survey,”  Artificial Intelligence Review, 2023.
  * [35] Ian Osband, John Aslanides, and Albin Cassirer,  “Randomized prior functions for deep reinforcement learning,”  in NeurIPS, 2018, vol. 31, pp. 8626–8638.
  * [36] Matias Valdenegro-Toro,  “Deep sub-ensembles for fast uncertainty estimation in image classification,”  arxiv:1910.08168, 2019.
  * [37] Guotai Wang, Wenqi Li, Sébastien Ourselin, and Tom Vercauteren,  “Automatic brain tumor segmentation using convolutional neural networks with test-time augmentation,”  in BrainLes. 2018, vol. 11384, pp. 61–72, Springer.
  * [38] Guotai Wang, Wenqi Li, Michael Aertsen, Jan Deprest, Sébastien Ourselin, and Tom Vercauteren,  “Aleatoric uncertainty estimation with test-time augmentation for medical image segmentation with convolutional neural networks,”  Neurocomputing, vol. 338, pp. 34–45, 2019.
  * [39] Ibrahem Kandel and Mauro Castelli,  “Improving convolutional neural networks performance for image classification using test time augmentation: a case study using MURA dataset,”  Health Inf. Sci. Syst., vol. 9, no. 1, pp. 33, 2021.
  * [40] Illia Oleksiienko, Dat Thanh Tran, and Alexandros Iosifidis,  “Variational neural networks implementation in pytorch and jax,”  Software Impacts, vol. 14, pp. 100431, 2022.
  * [41] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun,  ,”  in Advances in Neural Information Processing Systems, 2015, vol. 28.
  * [42] Xavier Glorot and Yoshua Bengio,  “Understanding the difficulty of training deep feedforward neural networks,”  in AISTATS, 2010, vol. 9, pp. 249–256.
  * [43] Andreas Geiger, Philip Lenz, and Raquel Urtasun,  “Are we ready for autonomous driving? the KITTI vision benchmark suite,”  in CVPR, 2012, pp. 3354–3361.