# Where Should Traffic Sensors Be Placed on Highways?

Sebastian A. Nugroh$\text{o}^{\ast}$, Suyash C. Vishno$\text{i}^{\dagger}$,
Ahmad F. Tah$\text{a}^{\ddagger,\diamond}$, Christian G.
Claude$\text{l}^{\dagger}$, and Taposh Banerje$\text{e}^{\star}$ ∗Department
of Electrical Engineering and Computer Science, University of Michigan, 1301
Beal Ave., Ann Arbor, MI 48109 (snugroho@umich.edu). †Department of Civil,
Architectural, and Environmental Engineering, The University of Texas at
Austin, 301 E. Dean Keeton St. Stop C1700, Austin, TX 78712
<EMAIL_ADDRESS>christian.claudel@utexas.edu). ‡Department of Civil and
Environmental Engineering, Vanderbilt University, 2201 West End Ave,
Nashville, TN 37235 (ahmad.taha@vanderbilt.edu). ⋆Department of Electrical and
Computer Engineering, The University of Texas at San Antonio, 1 UTSA Circle,
San Antonio, TX 78249 (taposh.banerjee@utsa.edu). ⋄Corresponding author. This
work is partially supported by the Valero Energy Corporation and National
Science Foundation (NSF) under Grants 1636154, 1728629, 1739964, 1917164,
1917056, and 2044430

###### Abstract

This paper investigates the practical engineering problem of traffic sensors
placement on stretched highways with ramps. Since it is virtually impossible
to install bulky traffic sensors on each highway segment, it is crucial to
find placements that result in optimized network-wide, traffic observability.
Consequently, this results in accurate traffic density estimates on segments
where sensors are not installed. The substantial contribution of this paper is
the utilization of control-theoretic observability analysis—jointly with
integer programming—to determine traffic sensor locations based on the
nonlinear dynamics and parameters of traffic networks. In particular, the
celebrated asymmetric cell transmission model is used to guide the placement
strategy jointly with observability analysis of nonlinear dynamic systems
through Gramians. Thorough numerical case studies are presented to corroborate
the proposed theoretical methods and various computational research questions
are posed and addressed. The presented approach can also be extended to other
models of traffic dynamics.

###### Keywords:

Traffic sensor placement, highway traffic networks, asymmetric cell
transmission model, robust observer, observability Gramian, convex integer
programming.

##  I Motivation and Paper Contributions

With the development of intelligent transportation systems technologies,
numerous sensing methods for traffic data collection have become popular [1,
2]. Fixed sensors such as induction loops and magnetometers allow network
operators to obtain high-quality measurements of vehicle density besides other
information such as vehicle speeds and flow [1]. Sensors, however, are
generally expensive to install and maintain which makes them infeasible for
installation throughout the network and covering all segments. This poses a
problem for traffic management operations and controls that require knowledge
of the traffic state on all segments. Such operations include traffic control
tasks such as ramp metering [3, 4], and variable speed limit control [5, 4].
While it may only be feasible to collect data from a fixed number of segments
in the network, it is still possible to obtain accurate estimates of the state
of traffic on all the segments if the sensors are strategically placed.

The problem of placing traffic sensors on highway networks has been divided
into two main categories in the literature, one involving estimation and the
other involving observability. Under the former category, the objective is to
determine the optimal placement of sensors that minimizes the estimation error
for unmeasured quantities such as travel time [6, 7, 8], OD matrix [9, 10],
link flows[11]. Under observability, the literature is further divided based
on the type of observability that is considered, full or partial
observability. A fully observable system is one in which all the states are
observable given the available measurements from the sensors. Different
observability problems considered in this category are link flow observability
[12, 13, 14, 15, 16], route flow observability [17, 18] and OD flow
observailibty [19, 20, 21]. The general idea is to determine a sensor
placement configuration that ensures full observability of the system. Partial
observability implies that not all states are observable given the set of
available sensor measurements. Under this category, the literature focuses on
determining such sensor locations that maximize the number of observable
states while obeying some budget constraints. This concept is attractive in
cases where the number of sensors required to achieve full observability is
too large. Interested readers can refer to [2, 22, 23, 16] and references
therein for a detailed literature review of the aforementioned categories of
sensor placement problem. In the current work, we focus on determining the
optimal sensor placement to achieve full observability of the system while
maintaining a balance between the number of sensors and the degree of
observability of the system. Note that the degree of observability is a
quantitative measure of the quality of state estimates that can be obtained by
using a certain sensor placement configuration and is not related to the idea
of partial observability. Unlike the aforementioned studies that utilize the
relationship between the various flows in the network such as link and path
flows, this study uses a traffic dynamics model to determine the relationship
between various state variables. Also, the states considered here are traffic
densities instead of flows.

A study that is closer to the work presented in this paper is [24] which also
considers a traffic dynamics model and applies a control theoretic approach to
determine optimal sensor locations on unconnected highway segments. This
approach is extended to study sensor placement on complex traffic networks in
[25], and then adopted in [26] for studying the observability of highway
traffic with Lagrangian sensors. These studies linearize the nonlinear traffic
dynamics around a steady-state traffic flow. The major drawback of such
approaches is that the linearized dynamics are valid only around the specific
states. Furthermore, these studies consider the Greenshield’s fundamental
diagram [27] which is inferior in modeling traffic flows when compared with
the triangular and trapezoidal fundamental diagrams which are often considered
in the implementation of the cell transmission model (CTM) [28, 29]. [1] does
deal with optimal sensor placement and density reconstruction while
considering the CTM model but to simplify things it still linearizes the model
and thus has the same drawback as above.

There exist some other papers studying the observability properties of traffic
systems considering a traffic dynamics model, albeit do not formally study the
sensor placement. The observability properties related to the switching modes
model[30], which is a piecewise-linearized version of the CTM[29] is studied
in [31]. In [32], the authors propose a ramp-metering controller based on a
switching modes scheme and study the observability properties of the
considered freeway system. A new piecewise affine system model based on CTM is
developed in [33], where its observability is investigated. These studies
however, linearize the traffic dynamics and suffer the same drawback.

This paper investigates the sensor placement problem for highway networks with
ramps having nonlinear traffic dynamics. The traffic model is built using the
asymmetric CTM (ACTM) [34, 35, 28] (a close variant of the CTM) and the
triangular fundamental diagram, and thus is also an improvement over [24, 25,
26] in terms of modeling traffic dynamics, to remove the dependence of optimal
sensor placements on assumptions about traffic states. The traffic sensor
placement is addressed via observability analysis based on the nonlinear
traffic model, which is different from the ones used in the aforementioned
papers.

There exist several approaches in the literature to quantify observability for
nonlinear systems. The two most prevalent approaches include utilizing the
concept from differential embedding and Lie derivative [36, 37], while the
other is based on empirical observability Gramian [38]. In the context of
sensor placement for nonlinear systems, four different approaches have been
proposed recently. The first approach leverages empirical observability
Gramian to find the best set of sensors that maximizes some metrics on the
Gramian matrix—see [39, 40, 41]. Another approach is proposed in [42] where
the observability Gramian around a certain initial state is constructed
through a moving horizon estimation (MHE) framework. As such, the sensor
selection problem is posed as an integer programming (IP) problem which
objective is maximizing the logarithmic determinant of the Gramian. The third
approach, developed in [43], introduces a randomized algorithm for dealing
with the sensor placement problem and accordingly, theoretical bounds for
eigenvalue and condition number of observability Gramian are proposed. The
last and most recent approach is established in [44] where the authors make
use of the numerous observer designs for some classes of nonlinear systems
posed as semidefinite programs (SDP). The resulting problem, which combines
the sensor selection and observer gain synthesis, is posed as a nonconvex
mixed-integer SDP, which can be cast into a convex one through some
relaxation/reformulation techniques.

Herein, based on the nonlinear traffic model developed using ACTM, we
formulate the sensor placement problem using traffic observability analysis.
The resulting problem—categorized as convex IP—is solved via an integer
branch-and-bound (BnB) algorithm and therefore, optimal traffic sensor
locations can be obtained. Notice that the use of nonlinear traffic model and
observability analysis result in traffic sensor locations that are valid for
various traffic conditions. The novelties made in this paper are listed as
follows:

  * •

We present a discrete-time nonlinear state-space model for stretched highway
networks having multiple on- and off-ramps based on ACTM. In addition, we
analytically compute the corresponding Lipschitz constant for the nonlinear
counterparts. The formulated state-space model along with Lipschitz constant
pave the way for implementing various control-theoretic approaches to solve
control and estimation problems prevailing in highway traffic networks.

  * •

We leverage the concept of observability for nonlinear systems to construct
the traffic sensor placement problem, which is equivalent to maximizing the
determinant and trace of observability Gramian matrix given the number of
allocated traffic sensors. To the best of our knowledge, this is the first
attempt to solve traffic sensor placement problem based on the degree of
observability for the nonlinear traffic dynamics.

  * •

We propose a corresponding robust observer framework for Lipschitz nonlinear
discrete-time systems developed using the concept of $\mathcal{L}_{\infty}$
stability for traffic density estimation purpose. By using the optimal
configuration of traffic sensors, the computation of stabilizing observer gain
matrix can be cast as a SDP and as such, can be solved efficiently.

  * •

We verify the effectiveness of our approach to solve the traffic sensor
placement problem through various case studies. Specifically, we (a) study the
performance and computational efficiency of determinant and trace functions in
estimating the system’s initial state, (b) assess their impact on traffic
density estimation performance under noisy conditions, and (c) compare their
results relative to randomized and uniform sensor placement strategies.

The remainder of the paper is organized as follows. In Section II, we provide
the mathematical modeling of stretched highway with ramps using ACTM, which
result in a nonlinear state-space form. Next, Section III discusses our
strategy for addressing traffic sensor placement based on system’s
observability. Section IV develops a simple robust observer design for traffic
density estimation purpose. The proposed approach is extensively tested in
Section V for solving the traffic sensor placement problem and density
estimation via numerous case studies. Finally, Section VI concludes the paper.

Paper’s Notation: Let $\mathbb{N}$, $\mathbb{R}$, $\mathbb{R}_{++}$,
$\mathbb{R}^{n}$, and $\mathbb{R}^{p\times q}$ denote the set of natural
numbers, real numbers, positive real numbers, and real-valued row vectors with
size of $n$, and $p$-by-$q$ real matrices respectively. $\mathbb{S}^{m}$
denotes the set of symmetric matrices with the dimension of $m$. Specifically,
$\mathbb{S}^{m}_{+}$ and $\mathbb{S}^{m}_{++}$ denotes the set of positive
semi-definite and positive definite matrices respectively. For any vector
$z\in\mathbb{R}^{n}$, $\|z\|_{2}$ denotes its Euclidean norm, i.e.
$\|z\|_{2}=\sqrt{z^{\top}z}$, where $z^{\top}$ is the transpose of $z$. The
symbol $\otimes$ denotes the Kronecker product where $\mathrm{det}(\bm{A})$
and $\mathrm{trace}(\bm{A})$ return the determinant and trace of matrix
$\bm{A}$. For simplicity, the notation ’$*$’ denotes terms induced by symmetry
in symmetric block matrices. Tab. I provides the nomenclature utilized in this
paper.

TABLE I: Paper nomenclature: parameter, variable, and set definitions. Notation | Description
---|---
$\Omega$ | the set of highway segments on the stretched highway
|  $\Omega=\\{1,2,\ldots,N\\}$ , $N:=\left\lvert\Omega\right\rvert$
$\Omega_{I}$ | the set of highway segments with on-ramps
|  $\Omega_{I}=\\{1,2,\ldots,N_{I}\\}$ ,
$N_{I}:=\left\lvert\Omega_{I}\right\rvert$
$\Omega_{O}$ | the set of highway segments with off-ramps
|  $\Omega_{O}=\\{1,2,\ldots,N_{O}\\}$,
$N_{O}:=\left\lvert\Omega_{O}\right\rvert$
$\hat{\Omega}$ |  the set of on-ramps, $\hat{\Omega}=\\{1,2,\ldots,N_{I}\\}$ , $N_{I}=|\hat{\Omega}|$
$\check{\Omega}$ |  the set of off-ramps, $\check{\Omega}=\\{1,2,\ldots,N_{O}\\}$ , $N_{O}=|\check{\Omega}|$
$T$ | duration of each time step
$l$ | length of each segment, on-ramp, and off-ramp
$\rho_{i}[k]$ |  traffic density on Segment $i\in\Omega$ at time $kT$, $k\in\mathbb{N}$
$q_{i}[k]$ |  traffic flow from Segment $i\in\Omega$ into the next segment
$\delta_{i}[k],\sigma_{i}[k]$ |  demand and supply functions for Segment $i\in\Omega$
$\hat{\rho}_{i}[k]$ |  traffic density on the on-ramp of Segment $i\in\Omega_{I}$
$r_{i}[k]$ |  traffic flow into Segment $i\in\Omega_{I}$ from the on-ramp
$\hat{r}_{i}[k]$ |  traffic flow into the on-ramp of Segment $i\in\Omega_{I}$
$\hat{\delta}_{i}[k],\hat{\sigma}_{i}[k]$ | demand and supply functions for the on-ramp of
|  Segment $i\in\Omega_{I}$
$\check{\rho}_{i}[k]$ |  traffic density on the off-ramp of Segment $i\in\Omega_{O}$
$s_{i}[k]$ |  traffic flow from Segment $i\in\Omega_{O}$ into the off-ramp
$\check{\delta}_{i}[k],\check{\sigma}_{i}[k]$ | demand and supply functions for the off-ramp of
|  Segment $i\in\Omega_{O}$
$\check{s}_{i}[k]$ |  traffic flow from the off-ramp of Segment $i\in\Omega_{O}$
$f_{in}[k]$ | traffic wanting to enter Segment 1 of the highway
$f_{out}[k]$ |  traffic that can leave Segment $N$ of the highway
$\hat{f}_{i}[k]$ |  traffic wanting to enter the on-ramp of Segment $i\in\Omega_{I}$
$\check{f}_{i}[k]$ |  traffic that can leave the off-ramp of Segment $i\in\Omega_{O}$
$\beta_{i}[k]$ |  split ratio for the off-ramp of Segment $i\in\Omega_{O}$,
|  where $\beta_{i}[k]\in[0,1]$
$\xi_{i}[k]$ |  occupancy parameter for the on-ramp of Segment $i\in\Omega_{I}$
|  where $\xi_{i}[k]\in[0,w_{c}]$
$v_{f}$ | free-flow speed
$w_{c}$ | congestion wave speed
$\rho_{m}$ | maximum density
$\rho_{c}$ | critical density
Figure 1: Triangular fundamental diagram.

##  II Nonlinear Discrete-Time Modeling of Traffic Networks with ramps

This section presents the discrete-time modeling of traffic dynamics on a
stretched highway with arbitrary number and location of ramps. To that end,
here we utilize the Lighthill-Whitman-Richards (LWR) Model [45, 46] for
traffic flow. In this paper, the relationship between traffic density and flux
is given by the triangular-shaped fundamental diagram which has been
extensively used in the literature [28]. It is depicted in Fig. 1 and is
constructed as

$\displaystyle\small
q\left(\rho(t,d)\right)=\begin{cases}v_{f}\rho(t,d),&\;\mathrm{if}\;0\leq\rho(t,d)\leq\rho_{c}\\\
w_{c}\left(\rho_{m}-\rho(t,d)\right),&\;\mathrm{if}\;\rho_{c}\leq\rho(t,d)\leq\rho_{m}.\\\
\end{cases}$ (1)

where $t$ and $d$ denote the time and distance; $\rho(t,d)$ denotes the
traffic density (vehicles/distance) and $q(t,d)$ denotes the traffic flux
(vehicles/time). To represent the traffic dynamics as a series of difference,
state-space equations—a useful bookkeeping for the ensuing discussions—we
discretize the LWR Model with respect to both space and time (this is also
referred to as the Godunov discretization). This approach allows the highway
of length $L$ to be divided into segments (cells) of equal length $l$ and the
traffic networks model to be represented by discrete-time equations. These
segments form both the highway and the attached ramps. Throughout the paper,
the segments forming the highway are referred to as mainline segments. We
assume that the highway is split into $N$ mainline segments.

To ensure computational stability, the Courant-Friedrichs-Lewy condition (CFL)
given as ${v_{f}T}l^{-1}\leq 1$ has to be satisfied. Since each segment is of
the same length $l$, then we have $\rho(t,d)=\rho(kT,l)$, where
$k\in\mathbb{N}$ represents the discrete-time index. For simplicity of
notation, from here on $\rho(kT,l)$ is simply written as $\rho[k]$.

As mentioned earlier, traffic is modeled using the ACTM which is originally
given in [34, 35, 28]. The ACTM is a variant of the CTM that departs from the
CTM in its treatment of asymmetric merge junctions such as the on-ramp-highway
junctions. Unlike the CTM, it assumes separate allocations of the available
space on the highway for traffic from each merging branch, which allows for
comparatively simple flow conservation equations at those merges than the
original CTM. A variation to the original ACTM is introduced in the modeling
of the ramps which here are treated as normal segments rather than point
queues as in the original approach. The approach in this paper is similar to
that in [47]. Herein, we define new functions referred to as the demand
function $\delta_{i}[\cdot]$ and the supply function $\sigma_{i}[\cdot]$ to
simplify the ensuing expressions. The demand function equals the traffic flux
leaving Segment $i$ through the highway assuming that the next segment has
infinite storage. The supply function equals the traffic flux that can enter
Segment $i$ through the highway assuming that the previous segment has
infinite storage. These functions are constructed from the triangular FD given
in (1). The demand function $\delta_{i}[\cdot]$, with and without off-ramp,
can be written as

$\displaystyle\small\delta_{i}[k]=\begin{cases}\min\big{(}\bar{\beta_{i}}[k]v_{f}\rho_{i}[k],\bar{\beta_{i}}[k]v_{f}\rho_{c},\frac{\bar{\beta_{i}}[k]}{\beta_{i}[k]}\check{\sigma}_{i}[k]\big{)},\;\mathrm{if}\;i\in\Omega_{O}\\\
\min\big{(}v_{f}\rho_{i}[k],v_{f}\rho_{c}\big{)},\qquad\qquad\qquad\;\;\,\;\mathrm{if}\;i\in\Omega\setminus\Omega_{O}.\end{cases}$
(2)

Here $\check{\sigma}_{i}[k]$ can be given as

$\displaystyle\check{\sigma}_{i}[k]=\min\big{(}w_{c}(\rho_{m}-\check{\rho_{i}}[k]),v_{f}\rho_{c}\big{)}.$
(3)

In (2), the split-ratio $\beta_{i}[k]$ relates the traffic flow from Segment
$i$ into its off-ramp with the traffic flow from Segment $i$ into the next
segment such that

$\displaystyle s_{i}[k]$
$\displaystyle=\beta_{i}[k](s_{i}[k]+q_{i}[k])\implies
s_{i}[k]=\frac{\beta_{i}[k]}{\bar{\beta_{i}}[k]}q_{i}[k].$ (4)

where we define $\bar{\beta_{i}}[k]\overset{\Delta}{=}1-\beta_{i}[k]$ to
simplify the equations. Since
$\frac{\bar{\beta_{i}}[k]}{\beta_{i}[k]}v_{f}\rho_{c}>\bar{\beta}_{i}v_{f}\rho_{c}$,
therefore in (2) we can also simply write
$\check{\sigma}_{i}[k]=w_{c}(\rho_{m}-\check{\rho_{i}}[k])$.

Similarly, the supply function $\sigma_{i}[k]$, with and without on-ramp, can
be represented as

$\displaystyle\small\sigma_{i}[k]=\begin{cases}\min\big{(}w_{c}(\rho_{m}-\rho_{i}[k]),v_{f}\rho_{c}\big{)}-r_{i}[k],\,\qquad\hskip
5.69046pt\mathrm{if}\,i\in\Omega_{I}\\\
\min\big{(}w_{c}(\rho_{m}-\rho_{i}[k]),v_{f}\rho_{c}),\,\qquad\qquad\mathrm{if}\,i\in\Omega\setminus\Omega_{I},\end{cases}$
(5)

where $r_{i}[k]$ is described by the following equation

$\displaystyle
r_{i}[k]=\min\big{(}v_{f}\hat{\rho_{i}}[k],\xi_{i}(\rho_{m}-\rho_{i}[k]),\frac{\xi_{i}}{w_{c}}v_{f}\rho_{c}\big{)}.$
(6)

Here $v_{f}\hat{\rho_{i}}[k]$ is the demand of the on-ramp in free-flow, and
$\frac{\xi_{i}[k]}{w_{c}}$ is the fraction of the flow that Segment $i$ can
receive from its on-ramp. The upstream and downstream flows for any mainline
Segment $i$ are given as

$\displaystyle q_{i-1}[k]$
$\displaystyle=\min\big{(}\delta_{i-1}[k],\sigma_{i}[k]\big{)}$ (7a)
$\displaystyle q_{i}[k]$
$\displaystyle=\min\big{(}\delta_{i}[k],\sigma_{i+1}[k]\big{)},$ (7b)

The discrete-time flow conservation equation for a mainline segment with both
on- and off-ramp can then be written as

$\displaystyle\rho_{i}[k+1]$
$\displaystyle=\rho_{i}[k]+\frac{T}{l}\big{(}q_{i-1}[k]+r_{i}[k]-q_{i}[k]-s_{i}[k]\big{)}$
(8)

Equations for segments with only one or no ramp can be written by removing the
respective flow terms. The flows and conservation equations for the ramps can
also be written similar to the mainline segments. The detailed illustration
for the above model is given in Fig. 2.

Figure 2: Consecutive segments of the highway with ramp connections.

In the present study, we assume an arbitrary structure of the highway with
respect to the positioning of the ramps on different mainline segments. In
that, we assume that every mainline segment having no ramps is followed by a
segment having an on-ramp, which is followed by a segment having an off-ramp,
and which is followed by a segment having no ramps and this structure repeats
throughout the highway. Additionally, we assume that the first and last
mainline segments have no ramps. For example, a highway split into seven
segments has an on-ramp on Segments 2 and 5, an off-ramp on Segments 3 and 6,
and no ramps on Segments 1, 4 and 7. Fig. 3 gives a schematic representation
of the structure of the highway considered in this paper. Note that this
structure of the highway is arbitrarily chosen for experimentation of the
methodology presented in this work. It is easy to consider a different highway
structure as per an actual site where the method may be used.

Figure 3: Schematic of the highway structure considered in this study.

In this paper we assume that the upstream demand at Segment $1$ and downstream
supply at Segment $N$ are known, denoted by $\delta_{0}[k]=f_{\mathrm{in}}[k]$
and $\sigma_{N+1}[k]=f_{\mathrm{out}}[k]$ respectively. Similarly, we assume
that all the on-ramp demands $\hat{f}_{i},i\in\Omega_{I}$ and off-ramp
supplies $\check{f}_{i},i\in\Omega_{O}$ are also known. These known demand and
supply values are lumped into the input vector defined as

$\bm{u}[k]=[f_{\mathrm{in}}\hskip 2.84526ptf_{\mathrm{out}}\hskip
2.84526pt\ldots\hskip 2.84526pt{\hat{f}_{j}}\hskip 2.84526pt\ldots\hskip
2.84526pt{\check{f}_{l}}\hskip
2.84526pt\ldots]^{\top}\in\mathbb{R}^{2+N_{I}+N_{O}},$

where $j\in\Omega_{I}$ and $l\in\Omega_{O}$. The state vector can be defined
as

$\bm{x}[k]:=[\rho_{i}[k]\hskip 2.84526pt\ldots\hskip
2.84526pt\hat{\rho_{j}}[k]\hskip 2.84526pt\ldots\hskip
2.84526pt\check{\rho_{l}}[k]\hskip
2.84526pt\ldots]^{\top}\in\mathbb{R}^{N+N_{I}+N_{O}},$

for which $i\in\Omega$, $j\in\Omega_{I}$ and $l\in\Omega_{O}$. Here, $k$ is
same as the time-index of the simulation where each time step is of duration
$T$. The estimation interval is thus equal to $T$. The equations describing
state vector evolution can be be divided into categories:

  * •

$i\in\Omega\setminus\Omega_{I}\cup\Omega_{O}$

$\displaystyle\begin{split}x_{i}[k+1]&=x_{i}[k]+\frac{T}{l}\Big{(}\min\big{(}\delta_{i-1}[k],\,\sigma_{i}[k]\big{)}\\\
&\quad-\min\big{(}\delta_{i}[k],\,\sigma_{i+1}[k]\big{)}\Big{)}\end{split}$
(9a)

  * •

$i\in\Omega_{I}$, $j=N+\bar{j},\bar{j}\in\hat{\Omega}$

$\displaystyle\begin{split}&x_{i}[k+1]=x_{i}[k]+\frac{T}{l}\Big{(}\min\big{(}\delta_{i-1}[k],\sigma_{i}[k]\big{)}\\\
&\quad\;-\min\big{(}\delta_{i}[k],\,\sigma_{i+1}[k]\big{)}\\\
&\quad\;+\min\big{(}v_{f}x_{j}[k],\xi_{i}[k](\rho_{m}-x_{i}[k]),\frac{\xi_{i}[k]}{w_{c}}v_{f}\rho_{c}\big{)}\Big{)}\end{split}$
(9b)

  * •

$i\in\Omega_{O}$, $j=N+N_{I}+\bar{j},\bar{j}\in\check{\Omega}$

$\displaystyle\begin{split}x_{i}[k+1]&=x_{i}[k]+\frac{T}{l}\Big{(}\min\big{(}\delta_{i-1}[k],\,\sigma_{i}[k])\big{)}\\\
&\quad-\frac{1}{\bar{\beta}_{i}[k]}\min\big{(}\delta_{i}[k],\,\sigma_{i+1}[k]\big{)}\Big{)}\end{split}$
(9c)

  * •

$\bar{i}\in\hat{\Omega},i=N+\bar{i},j\in\Omega_{I}$

$\displaystyle\begin{split}&x_{i}[k+1]=x_{i}[k]+\frac{T}{l}\big{(}\hat{r}_{j}[k]\\\
&\quad-\min\big{(}v_{f}x_{i}[k],\xi_{j}[k](\rho_{m}-x_{j}[k]),\frac{\xi_{j}[k]}{w_{c}}v_{f}\rho_{c}\big{)}\big{)}\end{split}$
(9d)

  * •

$\bar{i}\in\check{\Omega},i=N+N_{I}+\bar{i},j\in\Omega_{O}$

$\displaystyle x_{i}[k+1]$
$\displaystyle=x_{i}[k]+\frac{T}{l}\Big{(}\frac{\beta_{j}[k]}{\bar{\beta}_{j}[k]}\min\big{(}\delta_{j}[k],\sigma_{j+1}[k]\big{)}-\check{s}_{j}[k]\Big{)}$
(9e)

######  Proposition 1.

The evolution of traffic density described in (9) can be written in a compact
state-space form as follows

$\displaystyle\bm{x}[k+1]=\bm{A}\bm{x}[k]+\bm{G}\bm{f}(\bm{x},\bm{u})+\bm{B_{\mathrm{u}}}\bm{u}[k],$
(10)

where $\bm{A}\in\mathbb{R}^{n\times n}$ for $n:=N+N_{I}+N_{O}$ represents the
linear dynamics of the system, $\bm{B_{\mathrm{u}}}\in\mathbb{R}^{n\times m}$
for $m:=2+N_{I}+N_{O}$ represents the way external inputs affecting the
system, $\bm{f}:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}^{g}$
is a vector valued function representing nonlinearities in (9), and
$\bm{G}\in\mathbb{R}^{n\times g}$ is a matrix representing the distribution of
nonlinearities.

The proof and the structures of the matrices and function in (10) are all
provided in Appendix A. The above result is important as it allows us to
perform optimal sensor placement for the traffic dynamical system defined by
(1)–(8), as well as to develop a robust state observer. This also allows for
other control-theoretic studies to use this state-space model for other
traffic engineering applications. The next section presents our strategy to
address the optimal sensor placement problem for the nonlinear traffic
dynamical system derived above.

##  III Observability-based Sensor Placement

In this section we discuss our approach for addressing the traffic sensor
placement problem. The traffic dynamics (10) with measurements can be
expressed as

$\displaystyle\bm{x}[k+1]$
$\displaystyle=\bm{A}\bm{x}[k]+\bm{G}\bm{f}(\bm{x},\bm{u},k)+\bm{B_{\mathrm{u}}}\bm{u}[k]$
(11a) $\displaystyle\bm{y}[k]$ $\displaystyle=\bm{\Gamma}\bm{C}\bm{x}[k],$
(11b)

with $\bm{f}(\bm{x},\bm{u},k):=\bm{f}(\bm{x},\bm{u})$ where $k$ is used to
indicate the time dependence. In the above model, we introduce
$\bm{y}\in\mathbb{R}^{p}$ to represent the vector of measurements, which
corresponds to all of the highway segments equipped with sensors measuring the
density. The matrix $\bm{C}\in\mathbb{R}^{p\times n}$ in (11b) is useful to
determine the placement of traffic sensors, whereas
$\bm{\Gamma}:=\mathrm{Diag}(\bm{\gamma})$ with $\bm{\gamma}\in\\{0,1\\}^{p}$
represents the selection of sensors—that is, $\gamma_{i}=1$ if the $i$-th
highway segment is measured (this consequently leads to nonzero row $i$ in
$\bm{C}$) and $\gamma_{i}=0$ otherwise. It is assumed throughout the paper
that every trajectory of (11) lie in the domain of interest
$\bm{\Omega}:=\mathbfcal{X}\times\mathbfcal{U}$. In the context of traffic
dynamics, $\mathbfcal{X}$ represents the operating region of the states
$\bm{x}$. Since $\bm{x}$ represents the densities, then
$\mathbfcal{X}:=[0,\rho_{m}]^{n}$. Likewise, the set $\mathbfcal{U}$ can be
constructed as $\mathbfcal{U}:=[0,v_{f}\rho_{c}]^{m}$, which represents the
set of admissible inputs.

Having described system (11) with sensor placement, we now state the paper’s
major computational objective: from a given possible set of traffic sensors
$\mathcal{G}_{\gamma}$ such that $\bm{\gamma}\in\mathcal{G}_{\gamma}$, find
the best (or optimal) sensor configuration $\bm{\gamma}^{*}$ such that system
(11) is observable, i.e., the system’s initial state $\bm{x}_{0}:=\bm{x}[0]$
can be uniquely determined from a finite set of measurements. In this paper,
we opt to formulate the traffic sensor placement using the concept of
observability through MHE framework developed in [42]. The framework utilizes
a series of past measurement data to estimate the initial state at each time
window. The reasons of pursuing this approach are two-fold. First, as argued
in [42], this approach is considerably more scalable than using empirical
observability Gramian and second, we experience numerical issues in applying
the method from [44]. With that in mind, we consider the first $N$ observation
window (or $N$ discrete measurements) of system (11) expressed in the equation
below

$\displaystyle\bm{h}(\bm{\gamma},\bm{x}_{0}):=\tilde{\bm{y}}-\bm{g}\left(\bm{\gamma},\bm{x}_{0}\right).$
(12)

In (12), the mapping
$\bm{g}:\mathbb{N}^{p}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{Np}$ is given
as

$\displaystyle\bm{g}^{\top}\left(\bm{\gamma},\bm{x}_{0}\right):=\begin{bmatrix}\left(\bm{\Gamma}\bm{C}\bm{x}[0]\right)^{\top}\,\left(\bm{\Gamma}\bm{C}\bm{x}[1]\right)^{\top}\,\ldots\,\left(\bm{\Gamma}\bm{C}\bm{x}[N-1]\right)^{\top}\end{bmatrix}.$
(13)

Note that $\bm{g}(\cdot)$ defined above is indeed a function of $\bm{x}_{0}$
since for any $k$ such that $0<k\leq N-1$ then we have

$\displaystyle\bm{x}[k]=\bm{A}^{k}\bm{x}[0]+\sum_{j=0}^{k-1}\bm{A}^{k-1-j}\left(\bm{G}\bm{f}(\bm{x},\bm{u},j)+\bm{B_{\mathrm{u}}}\bm{u}[j]\right).$
(14)

######  Remark 1.

The function $\bm{g}(\cdot)$ in (13) is in fact also dependent on input vector
$\bm{u}$, since the $k$-th state $\bm{x}[k]$, as it is seen from (14), relies
on $\mathbfcal{U}_{s}(k-1)$ defined as

$\mathbfcal{U}_{s}(k-1):=\\{\bm{u}[j]\\}_{j=0}^{k-1},\;\text{where}\;\bm{u}[j]\in\mathbfcal{U},\;\forall
j=0,\ldots,k-1,$

i.e., the $k$-th sequence of control inputs. The reason why $\bm{g}(\cdot)$
only takes $\bm{\gamma}$ and $\bm{x}_{0}$ as arguments is due to the
assumption that $\mathbfcal{U}_{s}(i)$ is known for each time index $i$, thus
the dependence of $\bm{g}(\cdot)$ towards input vector $\bm{u}$ can be ignored
for simplicity.

The term $\tilde{\bm{y}}\in\mathbb{R}^{Np}$ in (12) denotes the stacked $N$
measurements data constructed as

$\displaystyle\tilde{\bm{y}}^{\top}:=\begin{bmatrix}\tilde{\bm{y}}[0]^{\top}\;\,\tilde{\bm{y}}[1]^{\top}\;\,\ldots\;\,\tilde{\bm{y}}[N-1]^{\top}\end{bmatrix}.$

Obviously, for every initial condition of the system
$\bm{x}_{0}\in\mathbfcal{X}$, it holds that $\bm{h}(\bm{\gamma},\bm{x}_{0})=0$
such that $\tilde{\bm{y}}=\bm{g}\left(\bm{\gamma},\bm{x}_{0}\right)$. Hence,
for a fixed $\bm{\gamma}$, the mapping $\bm{g}(\cdot)$ maps the initial state
into the $N$ measurements output. The observability of system (11) with
respect to $\bm{g}(\cdot)$ is formally defined as follows [48].

######  Definition 1.

The system (11) with a prescribed $\bm{\gamma}$ is uniformly observable in
$\mathbfcal{X}$ if, for all admissible inputs $\bm{u}[k]\in\mathbfcal{U}$,
there exists a finite $N>0$ such that the mapping
$\bm{g}\left(\bm{\gamma},\bm{x}_{0}\right)$ defined in (13) is injective (one-
to-one) with respect to $\bm{x}_{0}\in\mathbfcal{X}$.

Note that, from Definition 1, if $\bm{g}\left(\bm{\gamma},\bm{x}_{0}\right)$
is injective with respect to $\bm{x}_{0}$, then $\bm{x}_{0}$ can be uniquely
determined from the set of measurements $\tilde{\bm{y}}$. A sufficient
condition for $\bm{g}(\cdot)$ to be injective is that the Jacobian of
$\bm{g}(\cdot)$ around $\bm{x}_{0}$, denoted by $\bm{J}_{w}(\cdot)$, is full
rank [48]. In fact, it is not difficult to show that, if system (11) has no
nonlinear counterparts, then the Jacobian matrix $\bm{J}_{w}(\cdot)$ reduces
to the $N$-step observability matrix for the linear dynamics.

In this work, we use the concept of observability Gramian to quantify the
system’s osbervability for a given set of sensors. The Gramian $\bm{G}_{v}$
(or Gram matrix) for some finite-dimensional real $k$ vectors
$\bm{v}_{i}\in\mathbb{R}^{n}$ where $i=1,2,\ldots,k$ is constructed as
$\bm{G}_{v}:=\bm{V}^{\top}\bm{V}$ where
$\bm{V}:=\begin{bmatrix}\bm{v}_{1}\,|\,\bm{v}_{2}\,\ldots\,|\,\bm{v}_{k}\end{bmatrix}$.
The observability of a discrete-time linear time-invariant system of the form

$\displaystyle\bm{x}[k+1]=\bm{A}\bm{x}[k],\quad\bm{y}[k]=\bm{C}\bm{x}[k],$
(15)

where $\bm{x}$ is the state and $\bm{y}$ is the output can be determined from
the associated Gramian. The corresponding $N$-step observability Gramian is
given as

$\mathbfcal{W}_{o}:=\mathbfcal{O}_{N}^{\top}\mathbfcal{O}_{N}=\sum_{i=0}^{N-1}(\bm{A}^{i})^{\top}\bm{C}^{\top}\bm{C}\bm{A}^{i},$

where $\mathbfcal{O}_{N}$ denotes the $N$-step observability matrix. The
system (15) is then observable if and only if $\mathbfcal{W}_{o}$ is of full
rank. Using the same analogy, the observability Gramian for the nonlinear
system (11) with respect to $\bm{\gamma}$ around $\bm{x}_{0}$ can be
constructed as

$\displaystyle\bm{W}_{o}(\bm{\gamma},\bm{x}_{0}):=\bm{J}_{w}^{\top}(\bm{\gamma},\bm{x}_{0})\bm{J}_{w}(\bm{\gamma},\bm{x}_{0}),$
(16)

where $\bm{W}_{o}(\cdot)\in\mathbb{R}^{n\times n}$ and
$\bm{J}_{w}(\cdot)\in\mathbb{R}^{Np\times n}$ is given as [42]

$\displaystyle\bm{J}_{w}(\bm{\gamma},\bm{x}_{0}):=\begin{bmatrix}\bm{I}\otimes\bm{\Gamma}\bm{C}\end{bmatrix}\times\begin{bmatrix}\bm{I}\\\
\dfrac{\partial\bm{x}[1]}{\partial\bm{x}[0]}\\\ \vdots\\\
\dfrac{\partial\bm{x}[N-1]}{\partial\bm{x}[0]}\end{bmatrix},$ (17)

where for system (11), by applying chain rule, for $0<k\leq N-1$ the $k$-th
partial derivative can be obtained from

$\displaystyle\dfrac{\partial\bm{x}[k]}{\partial\bm{x}[0]}=\prod_{j=0}^{k-1}\bm{A}+\bm{G}\dfrac{\partial\bm{f}}{\partial\bm{x}}(\bm{x},\bm{u},j),$

where the term
$\tfrac{\partial\bm{f}}{\partial\bm{x}}(\cdot)\in\mathbb{R}^{g\times n}$
denotes the Jacobian of $\bm{f}(\cdot)$ with respect to $\bm{x}$ evaluated at
discrete time $j$. The explicit form of this Jacobian matrix is detailed in
Appendix B. This requires $\bm{x}[j]$ and $\bm{u}[j]$ to be known, which can
be obtained from simulating (11) for up to $j$-th discrete time. In the
context of sensor placement problem, the objective is to find the best
$\bm{\gamma}$ satisfying $\bm{\gamma}\in\mathcal{G}_{\gamma}$ which maximizes
the observability of system (11) based on the observability Gramian (16).

There exist some measures that quantify observability based on Gramian matrix,
some of which include the rank, smallest eigenvalue, condition number, trace,
and determinant—see reference [40]. Each measures has a unique
characterization vis-à-vis observability. The rank of observability Gramian
quantifies the dimension of observable subspace. The smallest eigenvalue of
the Gramian is the worst case metric of observability and reflects the
difficulty of estimating the actual initial state $\bm{x}_{0}$ from the given
set of measurements $\tilde{\bm{y}}$. That is, the estimation error can be
very much sensitive to observation noise when the smallest eigenvalue of the
Gramian matrix is relatively close to zero [49]. The condition number—which
measures the ratio between the largest and smallest eigenvalues of the Gramian
matrix—on the other hand, accentuates the sensitivity of observability.

We realize that the Gramian (16) quantifies the observability on a particular
initial state $\bm{x}_{0}$. Large condition number (which implies ill-
conditioned Gramian matrix) indicates that small change in initial state may
produce a significant impact on observability [49]. The trace of observability
Gramian measures the average observability of the system in all directions in
state space. Therefore, a larger value of the trace indicates an increase in
overall observability [41]. Similar to the trace, determinant of observability
Gramian matrix also measures the system’s observability in every directions in
state space. Nonetheless, as pointed out in [39], determinant has the ability
to capture information from all elements of the Gramian matrix as well as
taking into account information redundancy for the case when multiple sensors
are considered. It is also suggested in [40] that the determinant is a better
measure for quantifying observability than the trace, since trace tends to
overlook (near) zero eigenvalues.

Based on the above considerations, we settle upon maximizing the determinant
and trace of the observability Gramian since, despite their differences
discussed previously, both metrics are popular in sensor placement literature
through empirical observability Gramian; see [40, 41, 39], as well as their
easy implementation on standard optimization interfaces such as YALMIP [50]
and CVX [51]. The resulting sensor placement problem is given as follows

$\displaystyle(\textbf{P1})\;\;\kappa=\operatorname*{minimize}_{\bm{\gamma}}\;\;\;$
$\displaystyle\begin{cases}-\mathrm{det}\left(\bm{W}_{o}(\bm{\gamma},\hat{\bm{x}}_{0})\right),\\\
-\mathrm{trace}\left(\bm{W}_{o}(\bm{\gamma},\hat{\bm{x}}_{0})\right),\end{cases}$
(18a) $\displaystyle\operatorname*{subject\ to}\;\;\;\,$
$\displaystyle\;\bm{\gamma}\in\mathcal{G}_{\gamma},\;\bm{\gamma}\in\\{0,1\\}^{p}.$
(18b)

Notice that P1 only takes the integer variables $\bm{\gamma}$ as the
optimization variable while $\hat{\bm{x}}_{0}$ is fixed. Since the constraint
and objective function are convex (or can be easily transformed into a convex
one)111The trace is linear while determinant is log-concave (and thus
logarithmic determinant is concave) on the set of all positive definite
matrices [52]., then P1 is categorized as a convex IP, which can be solved
optimally via a BnB algorithm. After the observability of the system has been
determined from the solutions of P1, then the measurement equation (11b) can
be reformulate into $\bm{y}[k]=\tilde{\bm{C}}\bm{x}[k]$ where
$\tilde{\bm{C}}\in\mathbb{R}^{n\times\tilde{p}}$ is the reduced state-to-
output matrix that corresponds to the nonzero rows of $\bm{\Gamma}^{*}\bm{C}$,
where $\bm{\gamma}^{*}$ is the optimal solution of P1. The traffic density
estimation is then performed based on $\bm{y}[k]\in\mathbb{R}^{\tilde{p}}$.

##  IV A Robust Observer for State Estimation

The previous section focuses on determining the traffic sensor placement based
on the observability of the traffic dynamics through a finite observation
window. As such, the obvious approach for performing traffic density
estimation is via MHE. However, compared to other approaches such as observers
or Kalman filter (KF)-based estimators, MHE for nonlinear systems is generally
computationally more expensive since a nonlinear least-square problem has to
be solved in every discrete time instance, which make it only suitable for
slow dynamical systems or situations where high-powered computational
resources are available. To that end, herein we employ a robust observer for
estimating traffic density, since observer uses a single gain matrix for all
discrete-time instances and only need to be computed once for a given traffic
sensors configuration.

To develop the robust state observer, the nonlinearities in (10) have to be
identified. In fact, we prove that these nonlinearities satisfy the Lipschitz
continuity condition, which for a vector-valued function is defined as
follows.

######  Definition 2 (Lipschitz Continuity).

Let $\bm{f}:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$.
Then, $\bm{f}$ is said to be Lipschitz continuous in
$\bm{\Omega}\subseteq\mathbb{R}^{n}\times\mathbb{R}^{m}$ if there exists a
constant $\gamma\in\mathbb{R}_{+}$ such that

$\displaystyle\left\lVert\bm{f}(\bm{x},\bm{u})-\bm{f}(\hat{\bm{x}},\bm{u})\right\rVert_{2}\leq\gamma\left\lVert\bm{x}-\hat{\bm{x}}\right\rVert_{2},$
(19)

for all $\bm{x},\hat{\bm{x}}\in\mathbfcal{X}$ and $\bm{u}\in\mathbfcal{U}$.

The next proposition shows that the nonlinear mapping $\bm{f}(\cdot)$ in (10)
is Lipschitz continuous with Lipschitz constant $\gamma_{l}$.

######  Proposition 2.

The non-linear function $\bm{f}(\cdot)$ governing the traffic dynamics (10)
and specified in Appendix A is Lipschitz continuous in $\bm{x}$ and $\bm{u}$
with the Lipschitz constant $\gamma_{l}$ given as

$\displaystyle\gamma_{l}=h\hskip 1.42262pt($ $\displaystyle v_{f},\hskip
1.42262pt\omega_{c},\hskip 1.42262ptl,\hskip 1.42262ptN,\hskip
1.42262ptN_{I},\hskip 1.42262ptN_{O},\hskip 1.42262pt\xi_{1},\hskip
1.42262pt\xi_{2},\hskip 1.42262pt\dots,\hskip 1.42262pt\xi_{N_{I}},$
$\displaystyle\hskip 1.42262pt\beta_{1},\hskip 1.42262pt\beta_{2},\hskip
1.42262pt\dots,\hskip 1.42262pt\beta_{N_{O}})$ (20)

where the function $h\hskip 1.42262pt(\cdot)$ is defined as in (C).

The proof of Proposition 2 is given in Appendix C. In what follows, we
consider the traffic dynamics (11) with the new measurement matrix
$\tilde{\bm{C}}$ and the addition of unknown inputs—which may include
unmodeled dynamics, disturbance, process noise, and measurement
noise—described as

$\displaystyle\bm{x}[k+1]$
$\displaystyle=\bm{A}\bm{x}[k]+\bm{G}\bm{f}(\bm{x},\bm{u})+\bm{B_{\mathrm{u}}}\bm{u}[k]+\bm{B_{\mathrm{w}}}\bm{w}[k]$
(21a) $\displaystyle\bm{y}[k]$
$\displaystyle=\tilde{\bm{C}}\bm{x}[k]+\bm{D_{\mathrm{w}}}\bm{w}[k].$ (21b)

In the above model, the disturbance vector $\bm{w}\in\mathbb{R}^{q}$ lumps all
unknown inputs into a single vector with the corresponding matrices
$\bm{B_{\mathrm{w}}}$ and $\bm{D_{\mathrm{w}}}$ are of appropriate dimensions.
These matrices describe how the external disturbances are distributed in the
system, where $\bm{B_{\mathrm{w}}}$ takes into account any disturbance
affecting the system’s dynamics while $\bm{D_{\mathrm{w}}}$ considers
disturbance affecting the measurements data. Both can be constructed from
observing empirical traffic data. The observer dynamics for (21) are derived
from the classical Luenberger observer given as

$\displaystyle\begin{split}{\hat{\bm{x}}}[k+1]&=\bm{A}\hat{\bm{x}}[k+1]+\bm{G}\bm{f}(\hat{\bm{x}},\bm{u})\\\
&\quad+\bm{B_{\mathrm{u}}}\bm{u}[k]+\bm{L}(\bm{y}[k]-\hat{\bm{y}}[k])\end{split}$
(22a) $\displaystyle\hat{\bm{y}}[k]$
$\displaystyle=\tilde{\bm{C}}\hat{\bm{x}}[k],$ (22b)

where $\hat{\bm{x}}[k]$ is the state estimation vector, $\hat{\bm{y}}[k]$ is
the measurement estimation vector, and $\bm{L}(\bm{y}-\hat{\bm{y}})$ is the
Luenberger-type correction term with $\bm{L}\in\mathbb{R}^{n\times\tilde{p}}$.
By defining the estimation error as $\bm{e}[k]:=\bm{x}[k]-\hat{\bm{x}}[k]$,
then from (21) and (22), the error dynamics can be shown to be in the
following form

$\displaystyle\begin{split}{\bm{e}}[k+1]&=\left(\bm{A}-\bm{L}\tilde{\bm{C}}\right)\bm{e}[k]+\bm{G}\Delta\bm{f}[k]\\\
&\quad+\left(\bm{B_{\mathrm{w}}}-\bm{L}\bm{D_{\mathrm{w}}}\right)\bm{w}[k]\end{split}$
(23a) $\displaystyle\bm{z}[k]$ $\displaystyle=\bm{Z}\bm{e}[k],$ (23b)

where $\Delta\bm{f}[k]:=\bm{f}(\bm{x},\bm{u})-\bm{f}(\hat{\bm{x}},\bm{u})$ and
in particular, $\bm{z}\in\mathbb{R}^{z}$ is the performance output of the
error dynamics with respect to the user-defined performance matrix
$\bm{Z}\in\mathbb{R}^{z\times n}$.

The goal of the observer is to provide asymptotic estimation error for
estimation error dynamics given above. Since the presence of unknown inputs
will not make the estimation error to be exactly zero, a robustness metric,
referred to as and $\mathcal{L}_{\infty}$ stability, is employed. The purpose
of this metric is to provide numerical assurance on the behavior of
performance output $\bm{z}$ against nonzero, time-varying unknown inputs
$\bm{w}$. Our prior work [53] deals with a robust observer design using the
concept of $\mathcal{L}_{\infty}$ stability for traffic density estimation
purpose assuming nonlinear continuous-time traffic dynamics model
corresponding with the Greenshield’s model. Furthermore, our recent work [47]
develops a robust $\mathcal{L}_{\infty}$ observer for the discrete-time model
corresponding with the ACTM. In the sequel, we reproduce a simple numerical
procedure from [47] to find an observer gain $\bm{L}$ that, if successfully
solved, renders the estimation error dynamics (23) to be
$\mathcal{L}_{\infty}$ stable with performance level $\mu$. Compared with
[47], this paper includes the mathematical proof for the next result.

######  Proposition 3.

Consider the nonlinear dynamics (21) and observer (22) in which
$\bm{w}\in\mathcal{L}_{\infty}$ and
$\bm{f}:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ is
locally Lipschitz in $\bm{\Omega}$ with Lipschitz constant $\gamma_{l}$. If
there exist $\bm{P}\in\mathbb{S}^{n}_{++}$, $\bm{Y}\in\mathbb{R}^{n\times p}$,
$\epsilon,\mu_{0},\mu_{1},\mu_{2}\in\mathbb{R}_{+}$, and
$\alpha\in\mathbb{R}_{++}$ such that the following optimization problem is
solved

$\displaystyle(\mathbf{P2})\;\;\operatorname*{minimize}_{\bm{P},\bm{Y},\epsilon,\alpha,\mu_{0,1,2}}\quad\mu_{0}\mu_{1}+\mu_{2}$
(24a) $\displaystyle\operatorname*{subject\ to}\;\;$
$\displaystyle\begin{bmatrix}(\alpha-1)\bm{P}+\epsilon\gamma_{l}^{2}\bm{I}&*&*&*\\\
\bm{O}&-\epsilon\bm{I}&*&*\\\ \bm{O}&\bm{O}&-\alpha\mu_{0}\bm{I}&*\\\
\bm{P}\bm{A}-\bm{Y}\bm{C}&\bm{P}\bm{G}&\bm{P}\bm{B_{\mathrm{w}}}-\bm{Y}\bm{D_{\mathrm{w}}}&-\bm{P}\end{bmatrix}\preceq
0$ (24b) $\displaystyle\begin{bmatrix}-\bm{P}&*&*\\\
\bm{O}&-\mu_{2}\bm{I}&*\\\ \bm{Z}&\bm{O}&-\mu_{1}\bm{I}\end{bmatrix}\preceq
0,$ (24c)

then the error dynamics given in (23) is $\mathcal{L}_{\infty}$ stable with
performance level $\mu=\sqrt{\mu_{0}\mu_{1}+\mu_{2}}$ for performance output
given as $\bm{z}=\bm{Z}\bm{e}$ and observer gain $\bm{L}$ computed as
$\bm{L}=\bm{P}^{-1}\bm{Y}$.

The proof of Proposition 3 is provided in Appendix D. Note that optimization
problem described in (24) is nonconvex due to bilinearity appearing in the
form of $(\alpha-1)\bm{P}$, $\alpha\mu_{0}$, and $\mu_{0}\mu_{1}$. To get a
convex one, one can simply fix the values of $\alpha$ and $\mu_{0}$ or
$\mu_{1}$, and solve for the other variables using any SDP solvers. Having
described our strategies for placing traffic sensors and estimating traffic
density via a robust observer framework, we then perform numerical tests of
these strategies through various case studies—presented in the ensuing
sections.

##  V Case Study: Results and Analysis

This section demonstrates the proposed approach for determining traffic
sensors location and estimating traffic density through $\mathcal{L}_{\infty}$
observer. Specifically, in this numerical study we attempt to answer the
following questions:

  1. –

Q1: How does the observation window length relate to traffic observability and
initial state estimation?

  2. –

Q2: How computationally efficient are the determinant and trace observability
metrics in terms of solving the sensor placement problem?

  3. –

Q3: How do actual and presumed initial states affect the resulting sensors’
location? Are sensor placements robust to changes in initial states?

  4. –

Q4: How reliable is the state estimation when using sensor locations obtained
from utilizing determinant and trace observability metrics?

  5. –

Q5: How does the theory-driven placement of sensors compare to randomized and
uniform sensor placement strategies?

All simulations are performed using MATLAB R2019a running on 64-bit Windows 10
with 3.4GHz IntelR CoreTM i7-6700 CPU and 16 GB of RAM with YALMIP [50] as the
interface to solve all IP and convex SDP. Throughout the section, all highways
are configured with $v_{f}=28.8889$ m/s ($65$ mph), $w_{c}=6.6667$ m/s ($15$
mph), $\rho_{c}=0.0249$ vehicles/m ($40$ vehicles/mile), $\rho_{m}=0.1333$
vehicles/m, and $l=400$ m. The discrete-time step is chosen to be $T=1$ sec.

(a)  (b)  (c)

Figure 4: Results on observability analysis for different number of sensor
allocations: (a) the relative error $\zeta$, (b) inverse optimal value of P1,
denoted by $-\kappa$, and (c) total computational time, which includes the
overall time spent for solving P1 and P3.

(a)  (b)

Figure 5: Relative error $\zeta$ for (a) various presumed initial state
$\hat{\bm{x}}_{0}$ and (b) actual initial state ${\bm{x}}_{0}$.

###  V-A Observability Analysis for Traffic Sensor Placement

Herein, we perform a numerical analysis on sensor placement approach through
traffic network’s observability discussed in Section III. The highway,
referred to the rest of the section as Highway A, stretches for approximately
$3.2$ miles with $13$ segments on the mainline, $4$ on-ramps, and $4$ off-
ramps such that there are $21$ segments in total. The objective of traffic
sensor placement problem translates to finding the set of $r$ highway segments
that must be equipped with traffic sensors such that the entire highway
traffic is observable, which is carried out by solving P1. Realize that P1 is
classified as a convex integer programming (IP) since $\hat{\bm{x}}_{0}$, the
presumed initial state, is fixed. P1 is solved using YALMIP’s branch-and-bound
(BnB) algorithm [50] along with MOSEK [54] solver.

In the first instance of observability analysis, problem P1 is solved with
fixed actual initial state ${\bm{x}}_{0}$ and presumed initial state
$\hat{\bm{x}}_{0}$, which are generated randomly in $(0,\rho_{m}]^{n}$. P1 is
then solved with different observation windows $N$ for varying number of
allocated sensors $r$. In this case, $r=\lceil p\times r_{p}\%\rceil$ where
$\lceil\cdot\rceil$ is the ceiling function, $p=n=21$, and $r_{p}\%$
represents the percentage of sensor’s allocation (from $20\%$ to $90\%$). The
number of allocated sensors is a convex constraint such that, with respect to
(18b), $\bm{\gamma}\in\mathcal{G}_{\gamma}$ is equivalent to
$\sum_{i}\gamma_{i}=r$.

We solve P1 for both observability metrics—the trace and determined metrics
discussed in Section III. It is suggested in [40] to use logarithmic
determinant as opposed to pure determinant to avoid numerical problems.
However, since YALMIP does not have option for realizing logarithmic
determinant objective function particularly for IP, then P1 is solved using
geomean function, which is equivalent to $\sqrt[n]{\mathrm{det}(\cdot)}$. The
maximum iteration of YALMIP’s BnB algorithm is chosen to be $10^{4}$. If the
optimality gap is not satisfied with the default tolerance after the maximum
iteration is achieved, the resulting solution is taken as the final outcome.

In this numerical study, we put our interest on comparing the relative error
$\zeta$, the inverse optimal value of P1, denoted by $-\kappa$, and total
computational time $\Delta t$. The relative error $\zeta$ represents the
difference between actual initial state ${\bm{x}}_{0}$ and the computed
initial state $\tilde{\bm{x}}_{0}$, which is obtained from solving the
following nonlinear least-square problem [42]

$\displaystyle(\textbf{P3})\;\;\operatorname*{minimize}_{\tilde{\bm{x}}_{0}}\;\;$
$\displaystyle\left\lVert\tilde{\bm{y}}_{\gamma}-\bm{g}_{\gamma}\left(\tilde{\bm{x}}_{0}\right)\right\rVert^{2}_{2}$
(25a) $\displaystyle\operatorname*{subject\ to}\;\;\;$
$\displaystyle\;\bm{0}\leq\tilde{\bm{x}}_{0}\leq\bm{1}\times\rho_{m}.$ (25b)

In (25a), $\tilde{\bm{y}}_{\gamma}$ is obtained from simulating the
undisturbed traffic dynamics (11) with a prescribed set of sensors
$\bm{\gamma}$ from $k=0$ to $k=N$ and initial state ${\bm{x}}_{0}$. Likewise,
the nonlinear mapping $\bm{g}_{\gamma}(\cdot)$ is constructed as in (13) with
the same sensor combination $\bm{\gamma}$. Problem P3 is solved by using the
MATLAB data-fitting function lsqnonlin, which implements a trust region
reflective algorithm [55]. The optimality tolerance is set to be $10^{-6}$ and
an initial guess equals to $\hat{\bm{x}}_{0}$. After $\tilde{\bm{x}}_{0}$ is
obtained as the solution of P3, $\zeta$ is computed as

$\displaystyle\zeta:=\dfrac{\left\lVert\tilde{\bm{x}}_{0}-{\bm{x}}_{0}\right\rVert_{2}}{\left\lVert{\bm{x}}_{0}\right\rVert_{2}}.$

Note that $\zeta$ appraises the quality of sensor placement, as smaller
$\zeta$ suggests that the given sensor configuration is capable to provide a
more accurate estimate of the initial state. Of course, this is reasonable if
P3 returns an optimal solution. Nonetheless, as P3 is a nonconvex optimization
problem, then it is highly unlikely that optimal solutions can be obtained. To
reduce the chance of variability, the actual ${\bm{x}}_{0}$ and presumed
$\hat{\bm{x}}_{0}$ initial states are fixed for this particular test.

TABLE II: Sensor locations for two different observation lengths and observability metrics. The notation $(x)+\\{y\\}$ means that the set of sensors $\\{y\\}$ is appended to that of row $(x)$ from the same column. The italicized numbers indicate suboptimal sensor locations. $r$ | $\mathrm{det}$ | $\mathrm{trace}$
---|---|---
$N=100$ | $N=200$ | $N=100$ | $N=200$
$5$ | $\\{1,6,10,16,20\\}$ | $\\{1,6,10,14,15\\}$ | $\\{6,14,17,19,20\\}$ | $\\{6,14,17,19,20\\}$
$7$ | $\mathit{\\{1,6,15,16,17,20,21\\}}$ | $\mathit{\\{1,6,14,16,17,20,21\\}}$ | $(5)+\\{16,21\\}$ | $(5)+\\{15,16\\}$
$9$ | $(7)+\mathit{\\{14,19\\}}$ | $\\{1,14,15,16,17,18,19,20,21\\}$ | $(7)+\\{15,18\\}$ | $(7)+\\{18,21\\}$
$11$ | $(9)+\\{10,18\\}$ | $(9)+\\{6,10\\}$ | $(9)+\\{8,10\\}$ | $(9)+\\{8,10\\}$
$13$ | $(11)+\\{8,12\\}$ | $(11)+\\{8,12\\}$ | $(11)+\\{11,13\\}$ | $(11)+\\{1,11\\}$
$15$ | $(13)+\\{2,5\\}$ | $(13)+\\{2,5\\}$ | $(13)+\\{1,2\\}$ | $(13)+\\{7,9\\}$
$17$ | $(15)+\\{7,11\\}$ | $(15)+\\{9,11\\}$ | $(15)+\\{7,9\\}$ | $(15)+\\{2,13\\}$
$19$ | $(17)+\\{3,13\\}$ | $(17)+\\{3,13\\}$ | $(17)+\\{3,12\\}$ | $(17)+\\{3,12\\}$

The results of this numerical study are depicted in Fig. 4. In particular, it
can be seen from Fig. 4a that larger observation window yields smaller
relative error. Notice that this behavior is reflected better from the trace
but less evident from the determinant—the variations are presumed to be caused
by suboptimal solutions obtained from solving P3. Fig. 4b also indicates this
behavior: larger observation window yields better optimal value P1, which in
turn implies that the observability measure is directly proportional with
observation window. This corroborates first principles in control theory; more
available data (i.e., a larger observation window) results in a better system
observability. The corresponding total computational time for both P1 and P3
are reported in Fig. 4c. It can be observed that, in this test where YALMIP’s
BnB algorithm is utilized, employing the trace in P1 is more efficient than
doing so with the determinant.

TABLE III: Sensor’s locations for two different Euclidean distances between actual ${\bm{x}}_{0}$ and presumed $\hat{\bm{x}}_{0}$ initial states where ${\bm{x}}_{0}$ is fixed and $\hat{\bm{x}}_{0}$ varies. The notation $(x)+\\{y\\}$ means that the set of sensors $\\{y\\}$ is appended to that of row $(x)$ from the same column. The italicized numbers indicate suboptimal sensor locations. $r$ | $\mathrm{det}$ | $\mathrm{trace}$
---|---|---
$\epsilon_{d}=0.16$ | $\epsilon_{d}=0.40$ | $\epsilon_{d}=0.16$ | $\epsilon_{d}=0.40$
$5$ | $\mathit{\\{1,6,15,17,20\\}}$ | $\mathit{\\{1,9,15,16,19\\}}$ | $\\{14,15,18,19,20\\}$ | $\\{14,15,18,19,20\\}$
$7$ | $\mathit{\\{1,5,16,17,18,20,21\\}}$ | $\mathit{\\{1,8,15,17,18,19,21\\}}$ | $(5)+\\{16,17\\}$ | $(5)+\\{16,17\\}$
$9$ | $\mathit{\\{1,6,11,14,15,16,18,19,20\\}}$ | $\mathit{\\{1,5,10,14,16,17,18,19,21\\}}$ | $(7)+\\{3,21\\}$ | $(7)+\\{3,21\\}$
$11$ | $(7)+\\{9,14,15,19\\}$ | $(5)+\\{5,14,17,18,20,21\\}$ | $(9)+\\{6,9\\}$ | $(9)+\\{6,9\\}$
$13$ | $(9)+\\{3,9,17,21\\}$ | $(5)+\\{3,6,11,14,17,18,20,21\\}$ | $(11)+\\{2,5\\}$ | $(11)+\\{2,5\\}$
$15$ | $(11)+\\{3,7,11,12\\}$ | $(9)+\\{3,6,8,12,15,20\\}$ | $(13)+\\{1,8\\}$ | $(13)+\\{1,8\\}$
$17$ | $(13)+\\{2,5,8,12\\}$ | $(13)+\\{2,5,8,12\\}$ | $(15)+\\{4,7\\}$ | $(15)+\\{4,7\\}$
$19$ | $(17)+\\{4,10\\}$ | $(17)+\\{4,10\\}$ | $(17)+\\{10,11\\}$ | $(17)+\\{10,11\\}$
Figure 6: Comparison of relative error (top) and the trace of the Gramian
(bottom) between uniform and different (randomized) sensor costs.

The resulting sensor’s location for observation window $N=100$ and $N=200$ are
shown in Tab. II. For the same number of sensors and observation windows, the
sensor locations for determinant and trace objective functions are quite
distinct. This observation is expected as both metrics measure different
aspect on observability Gramian. Interestingly, as it is seen from Tab. II,
the results from using trace as observability metric suggest a modular-like
behavior222A set function $f:2^{\mathcal{V}}\rightarrow\mathbb{R}$, in which
$\mathcal{V}=\\{1,2,\ldots,p\\}$ for $p\in\mathbb{N}$, is modular if and only
if for any $\mathcal{S}\subseteq\mathcal{V}$ it can be expressed as
$f(\mathcal{S})=w(\emptyset)+\sum_{s\in\mathcal{S}}w(s)$ for some weight
function $w:\mathcal{V}\rightarrow\mathbb{R}$ [56].: the sensor combination
from a particular row covers the ones from its previous rows. This modularity
property is also observed from the determinant objective function, despite
some irregularities for the first three rows, which is caused by suboptimal
solutions. This phenomena is in tandem with the conjecture stated in [42],
claiming that the logarithmic determinant objective function in P1 is
submodular.

Next, we asses the variability of sensor placement due to the differences in
actual ${\bm{x}}_{0}$ and presumed $\hat{\bm{x}}_{0}$ initial states. The
numerical experiment is carried out as follows. First, we set ${\bm{x}}_{0}$
to be fixed and use different values for $\hat{\bm{x}}_{0}$ which are randomly
generated inside $(0,\rho_{m}]^{n}$ in such a way that their Euclidean
distances, computed as
$\epsilon_{d}:=\left\lVert\hat{\bm{x}}_{0}-{\bm{x}}_{0}\right\rVert_{2}$, are
unique to each other. For this scenario, the results are given in Fig. 5a,
which shows the resulting relative error. In another scenario,
$\hat{\bm{x}}_{0}$ is fixed while ${\bm{x}}_{0}$ varies—see Fig. 5b for the
results. It can be seen from both figures that, in general, varying
$\hat{\bm{x}}_{0}$ while fixing ${\bm{x}}_{0}$ yields higher relative error
magnitudes than fixing $\hat{\bm{x}}_{0}$ and varying ${\bm{x}}_{0}$. However,
when ${\bm{x}}_{0}$ is fixed, $\zeta$ experiences minimal variations at least
for $r<14$, whereas more variations occur on the other scenario. Again, these
variations are most likely attributed to the suboptimal solutions obtained
from solving P3 via lsqnonlin. It is also observed that larger distance
$\epsilon_{d}$ does not necessarily result in larger relative error $\zeta$,
suggesting that the proposed method is rather resilient towards the values of
actual and presumed initial states.

The corresponding sensor combinations for scenario when ${\bm{x}}_{0}$ is
fixed and $\hat{\bm{x}}_{0}$ varies with two different Euclidean distances are
provided in Tab. III. It can be seen that, for the trace, the sensor
combinations are the same, indicating that it is robust to different actual
and presumed initial states. The same pattern is also observed for the
determinant, despite being less apparent. The first three rows are expected
since they are suboptimal, hence the different sensor combinations. However,
when the solutions are optimal, the resulting sensor combinations are similar
except for $r=15$. Similar results are also obtained for scenario when
${\bm{x}}_{0}$ varies and $\hat{\bm{x}}_{0}$ is fixed.

Lastly, in this section we investigate the impact of different sensor costs
towards the quality of sensor’s configuration. To that end, the following
problem is solved

$\displaystyle(\textbf{P4})\;\;\,\operatorname*{minimize}_{\bm{\gamma},\,t\geq
0}\;\;\;$
$\displaystyle-\mathrm{trace}\left(\bm{W}_{o}(\bm{\gamma},\hat{\bm{x}}_{0})\right)+w\times
t$ (26a) $\displaystyle\operatorname*{subject\ to}\;\;$
$\displaystyle\;\bm{\gamma}\in\mathcal{G}_{\gamma},\;\bm{\gamma}\in\\{0,1\\}^{p},\;\bm{c}^{\top}\bm{\gamma}\leq
t.$ (26b)

Realize that P4 is P1 with the addition of sensor costs and only considers the
trace function since YALMIP faces numerical errors while geomean function is
fused with sensor costs. In this problem, $w\in\mathbb{R}_{++}$ is used to
determine the priority between the two objectives and
$\bm{c}\in\mathbb{R}_{+}^{p}$ represents the costs for all sensors. Two
different values for $w$ are used, where $w\geq 10^{2}$ to signify the sensor
costs. The sensor costs are generated randomly such that $c_{i}\in[0,1]$. The
results are shown in Fig. 6, from which it can be seen that the relative
errors and the degrees of observability for sensor locations determined by
considering sensor costs are considerably worse than not using sensor costs at
all. This happens because P4 has to simultaneously maximizing system’s
observability and minimizing the sensor costs, thereby giving sensor locations
that have lower degree of observability.

(a)  (b)

Figure 7: State estimation results via $\mathcal{L}_{\infty}$ observer for
different allocations of sensor: (a) the estimation error and (b) the
estimation error performance bounds.

(a)  (b)

Figure 8: RMSE for optimal and randomized sensor placement for (a) Highway A
and (b) Highway B. The simulations with randomized sensor placement are
performed $10$ times and the presented results correspond to the average
values.

###  V-B Traffic Density Estimation with Various Sensor Allocations

This section investigates different traffic sensor placements—obtained from
the previous section—for robust traffic density estimation purpose. To that
end, we implement the $\mathcal{L}_{\infty}$ observer proposed in Section IV
and set $\alpha=0.1$ and $\mu_{1}=10^{4}$ to get a convex optimization problem
out of P2, in which SDPNAL+ [57] is used to solve the problem since MOSEK
returns numerical problems. The performance matrix is chosen to be
$\bm{Z}=0.01\bm{I}$. Herein we simulate Highway A with final time $k_{f}=2000$
and invoke Gaussian noise with covariance matrices $Q=\nu\bm{I}$ and
$R=\nu\bm{I}$ where $\nu=10^{-3}$ with corresponding unknown input matrices
$\bm{B_{\mathrm{w}}}=\begin{bmatrix}\bm{B_{\mathrm{u}}}\;\;\bm{O}\end{bmatrix}$
and $\bm{D_{\mathrm{w}}}=\begin{bmatrix}\bm{O}\;\;\bm{I}\end{bmatrix}$, which
simulate process and measurement noise.

In this part of numerical study, we are focused on finding out whether
different observability metrics used to solve P1 have explicit impact on the
quality of traffic density estimation, since according to Tab. II, different
observability metrics return distinctive sensor locations. With that in mind,
we compare the resulting estimation errors $\bm{e}[k]$, root-mean-square error
(RMSE)—which is computed from

$\displaystyle\mathrm{RMSE}$
$\displaystyle=\sum_{i=1}^{n}\sqrt{\frac{1}{k_{f}}\sum_{k=0}^{k_{f}}(e_{i}[k])^{2}},$

and estimation error performance bounds
$\mu\left\lVert\bm{w}\right\rVert_{\mathcal{L}_{\infty}}$, which is obtained
from multiplying the worst case disturbance
$\left\lVert\bm{w}\right\rVert_{\mathcal{L}_{\infty}}$ with performance index
$\mu$ retrieved from solving P2. The sensor locations used in this test, for
both observability metrics, are collected from Tab. II that correspond to
observation window $N=200$.

The results of this numerical test are illustrated in Fig. 7. It is indicated
from Fig. 7b that, as more sensors are utilized, the estimation error is
decreasing. However, it is of importance to note that using determinant as the
observability metric yields better state estimation results than doing so with
trace, since the RMSE for determinant is slightly smaller. This showcases the
prominence of determinant as opposed to trace to quantify observability.
Interestingly, the estimation error performance bounds are increasing as more
sensors are utilized with no noticeable difference for determinant and trace.
This suggests that, regardless of sensor locations, adding sensors increases
the susceptibility of the entire network towards measurement noise. The
trajectories of estimation error for different number of sensors are given in
Fig. 7a, from which it can be observed that utilizing more sensors yields
smaller and faster convergence on estimation error—notice that this
observation is in accordance with RMSE shown in Fig. 7b. It is also observed
from Fig. 7a that, in general, the determinant returns smaller estimation
error compared to the trace. A slight exception occurs when the sensor
allocation is at $30\%$ (also see Fig. 7b). This is suspected to be caused by
suboptimal sensor placement—see Tab. II.

(a)  (b)

Figure 9: Performance of estimation error with $40\%$ measurements for (a)
Highway A (with determinant observability metric) and (b) Highway B (with
trace observability metric).

(a)  (b)  (c)

Figure 10: Comparison between real $\bm{x}[k]$ and estimated $\hat{\bm{x}}[k]$
traffic densities on (a) mainline segments, (b) on-ramps, and (c) off-ramps
for highway B with $40\%$ measurements—sensor locations are obtained form
solving P1 with trace observability metric.

###  V-C Optimal, Randomized, and Uniform Sensor Placement

In the last part of numerical test, we analyze the results of traffic density
estimation with optimal, randomized, and uniform sensor placement. We consider
two highway networks: the first one is Highway A (detailed in Section V-A)
while the other, referred to as Highway B, consists a larger network with $40$
segments on the mainline, $13$ on-ramps, and $13$ off-ramps, giving $66$
highway segments in total with length of $9.9$ miles. The sensor placement and
observer design for Highway A follow from two previous sections. For Highway
B, the sensor placement is acquired from solving P1 with trace observability
metric since it is much more efficient than the determinant, especially for
larger network. The observation window is again set to be $N=200$ with varying
number of sensor allocations. We set the covariant matrix $R$ for Highway B to
be $5\times 10^{-3}\bm{I}$ to simulate a higher measurement noise, while the
final time is set to be $k_{f}=3000$. The remaining parameters for observer
design are chosen to remain the same as in Highway A.

The first results of this numerical experiment are provided in Fig. 8. This
figure showcases the RMSE of traffic density estimation with optimal,
randomized, and uniform sensor placement for both highways. For the uniform
case, the sensors are firstly placed at odd locations and will begin to be
placed at even locations only when all odd locations are used up. Also note
that, to compensate randomization on sensor placement, the simulations for
this case (randomized sensor placement) are performed $10$ times for every $r$
and the results are averaged. For Highway A, the optimal sensor placements
return significantly smaller RMSE than the randomized and uniform ones,
regardless of observability metric being used. For Highway B, the RMSE for
optimal sensor placement with trace is generally smaller than using randomized
or uniform sensor placement. These results suggest that using optimal sensor
placement, regardless of observability metric, gives better traffic density
estimation than doing so with randomized sensor placement.

The second results of this numerical experiment are illustrated in Fig. 9,
where the corresponding error performance norm
$\left\lVert\bm{z}[k]\right\rVert_{2}$ are compared with the estimation error
performance bound $\mu\left\lVert\bm{w}\right\rVert_{\mathcal{L}_{\infty}}$.
Notice the larger value of error performance norm for Highway B due to higher
measurement noise. Specifically for both highways, it can be seen that the
norm of error performance is converging to a value below the estimation error
performance bound within the given simulation window. These findings are in
accordance with the definition of $\mathcal{L}_{\infty}$ stability. The
resulting traffic density estimations for Highway B are depicted in Fig. 10.

##  VI Conclusions, Paper Limitations, and Future Work

Given the thorough computational analysis in the previous section, the
following observations are made, thereby answering the posed research
questions in Section V:

  1. –

A1: Increasing observation window yields smaller initial state estimation
errors while traffic network’s quantifiable observability is directly
proportional with observation window. This corroborates control-theoretic
first principles.

  2. –

A2: Using trace as observability metric allows the sensor placement problem to
be solved more efficiently than doing so with determinant metric for
observability. This is critical if large-scale networks are considered.

  3. –

A3: The resulting sensor placement obtained from solving P1 is robust towards
actual and presumed initial states. This illustrates that the sensor placement
to guarantee a wide range of initial operating conditions.

  4. –

A4: When used to determine optimal sensor locations, the determinant is better
than the trace in term of state estimation error and hence offers better
network-wide observability. This poses tradeoffs between state estimation
quality and computational tractability for the two metrics; see A2 above.

  5. –

A5: The optimal sensor placement outperforms randomized and uniform sensor
placement in estimating traffic density.

The approach in this paper has its own set of limitations. First, we consider
a time-invariant traffic model where in reality, some parameters are in fact
time-varying, which include critical density, split ratio, free-flow speed,
and congestion wave speed. We also do not consider the capacity drop
phenomenon or the stochasticity of traffic in the model presented in this
paper. Second, the sensor placement strategy does not consider the effect of
measurement noise. To that end, future work will include solving the traffic
sensor placement problem while considering a time-varying nonlinear traffic
model incorporating capacity drop and stochasticity and taking measurement
noise into account, which is resulting in a robust sensor placement. Moreover,
the submodularity properties of the determinant and trace—as well as other
observability metrics—for sensor selection purpose will be investigated to
assist in solving the placement problem for large networks. Finally, we point
out that the presented placement approach in the paper can be extended or
utilized to other models in transportation systems beyond stretched highways,
assuming that a nonlinear state-space representation of the dynamics is
possible.

## Acknowledgments

We gratefully acknowledge the constructive comments from the reviewers—they
have contributed positively to this work. We also acknowledge the financial
support from the National Science Foundation through Grants 1636154, 1728629,
1917164, and 1917056.

## References

  * [1] E. Lovisari, C. Canudas de Wit, and A. Kibangou, “Density/flow reconstruction via heterogeneous sources and optimal sensor placement in road networks,” _Transportation Research Part C_ , vol. 69, no. C, pp. 451–476, 2016.
  * [2] M. Gentili and P. Mirchandani, “Locating sensors on traffic networks: Models, challenges and research opportunities.” _Transportation Research Part C_ , vol. 24, 2012\.
  * [3] M. Papageorgiou and A. Kotsialos, “Freeway ramp metering: An overview,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 3, no. 4, pp. 271–281, 2002.
  * [4] R.-C. Carlson, I. Papamichail, M. Papageorgiou, and A. Messmer, “Optimal motorway traffic flow control involving variable speed limits and ramp metering,” _Transportation Science_ , vol. 44, no. 2, pp. 238–253, 2010.
  * [5] A. Hegyi and S. Hoogendoorn, “Dynamic speed limit control to resolve shock waves on freeways - Field test results of the SPECIALIST algorithm,” in _13th International IEEE Conference on Intelligent Transportation Systems_. IEEE, 2010, pp. 519–524.
  * [6] J. Kianfar and P. Edara, “Optimizing freeway traffic sensor locations by clustering global-positioning-system-derived speed patterns,” _IEEE transactions on intelligent transportation systems_ , vol. 11, no. 3, pp. 738–747, 2010.
  * [7] I. Jovanović, M. Šelmić, and M. Nikolić, “Metaheuristic approach to optimize placement of detectors in transport networks — case study of serbia,” _Canadian journal of civil engineering_ , vol. 46, no. 3, pp. 176–187, 2019.
  * [8] M. Gentili and P. B. Mirchandani, “Review of optimal sensor location models for travel time estimation,” _Transportation research. Part C, Emerging technologies_ , vol. 90, pp. 74–96, 2018.
  * [9] E. Mitsakis, E. Chrysohoou, J. M. Salanova Grau, P. Iordanopoulos, and G. Aifadopoulou, “The sensor location problem: methodological approach and application,” _Transport (Vilnius, Lithuania)_ , vol. 32, no. 2, pp. 113–119, 2017.
  * [10] M. Owais, G. S. Moussa, and K. F. Hussain, “Sensor location model for o/d estimation: Multi-criteria meta-heuristics approach,” _Operations Research Perspectives_ , vol. 6, 2019.
  * [11] N. Mehr and R. Horowitz, “A submodular approach for optimal sensor placement in traffic networks,” in _2018 Annual American Control Conference (ACC)_ , vol. 2018-. AACC, 2018, pp. 6353–6358.
  * [12] S.-R. Hu, S. Peeta, and C.-H. Chu, “Identification of vehicle sensor locations for link-based network traffic applications,” _Transportation Research Part B_ , vol. 43, no. 8, pp. 873–894, 2009.
  * [13] M. Ng, “Synergistic sensor location for link flow inference without path enumeration: A node-based approach,” _Transportation Research, Part B_ , vol. 46, no. 6, pp. 781–788, 2012.
  * [14] L. Bianco, G. Confessore, and P. Reverberi, “A network based model for traffic sensor location with implications on O/D matrix estimates,” _Transportation Science_ , vol. 35, no. 1, pp. 50–60, 2001.
  * [15] M. Shao, L. Sun, and X. Shao, “Sensor location problem for network traffic flow derivation based on turning ratios at intersection,” _Mathematical Problems in Engineering_ , vol. 2016, p. 10, 2016.
  * [16] M. Salari, L. Kattan, W. H. Lam, H. Lo, and M. A. Esfeh, “Optimization of traffic sensor location for complete link flow observability in traffic network considering sensor failure,” _Transportation Research Part B_ , vol. 121, pp. 216–251, 2019.
  * [17] E. Castillo, A. J. Conejo, J. M. Menéndez, and P. Jiménez, “The observability problem in traffic network models,” _Computer-aided civil and infrastructure engineering_ , vol. 23, no. 3, pp. 208–222, 2008.
  * [18] M. Rinaldi and F. Viti, “Exact and approximate route set generation for resilient partial observability in sensor location problems,” _Transportation research. Part B: methodological_ , vol. 105, pp. 86–119, 2017.
  * [19] H. Yang and J. Zhou, “Optimal traffic counting locations for origin–destination matrix estimation,” _Transportation Research Part B_ , vol. 32, no. 2, pp. 109–126, 1998.
  * [20] L. Gan, H. Yang, and S. Wong, “Traffic counting location and error bound in origin-destination matrix estimation problems,” _Journal of Transportation Engineering_ , vol. 131, no. 7, pp. 524–534, 2005.
  * [21] R. Mínguez, S. Sánchez-Cambronero, E. Castillo, and P. Jiménez, “Optimal traffic plate scanning location for od trip matrix and route estimation in road networks,” _Transportation Research Part B_ , vol. 44, no. 2, pp. 282–298, 2010.
  * [22] F. Viti, M. Rinaldi, F. Corman, and C. M. Tampère, “Assessing partial observability in network sensor location problems,” _Transportation research. Part B: methodological_ , vol. 70, pp. 65–89, 2014.
  * [23] E. Castillo, Z. Grande, A. Calviño, W. Y. Szeto, and H. K. Lo, “A state-of-the-art review of the sensor location, flow observability, estimation, and prediction problems in traffic networks,” _Journal of Sensors_ , vol. 2015, pp. 1–26, 2015.
  * [24] S. Contreras, P. Kachroo, and S. Agarwal, “Observability and sensor placement problem on highway segments: A traffic dynamics-based approach,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 17, no. 3, pp. 848–858, 2015.
  * [25] S. Agarwal, P. Kachroo, and S. Contreras, “A dynamic network modeling-based approach for traffic observability problem,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 17, no. 4, pp. 1168–1178, 2016.
  * [26] S. Contreras, S. Agarwal, and P. Kachroo, “Quality of traffic observability on highways with lagrangian sensors,” _IEEE Transactions on Automation Science and Engineering_ , vol. 15, no. 2, pp. 761–771, 2018.
  * [27] B. D. Greenshields, J. R. Bibbins, W. S. Channing, and H. H. Miller, “A study of traffic capacity,” in _Proceedings of the highway research board_ , vol. 14. National Research Council (USA), Highway Research Board, 1935, pp. 448–477.
  * [28] G. Gomes, R. Horowitz, A. A. Kurzhanskiy, P. Varaiya, and J. Kwon, “Behavior of the cell transmission model and effectiveness of ramp metering,” _Transportation Research Part C: Emerging Technologies_ , vol. 16, no. 4, pp. 485 – 513, 2008.
  * [29] C. F. Daganzo, “The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory,” _Transportation Research Part B: Methodological_ , vol. 28, no. 4, pp. 269 – 287, 1994.
  * [30] L. Muñoz, X. Sun, R. Horowitz, and L. Alvarez, “Traffic density estimation with the cell transmission model,” in _Proceedings of the 2003 American Control Conference, 2003._ , vol. 5. IEEE, 2003, pp. 3750–3755.
  * [31] L. Muñoz, X. Sun, R. Horowitz, and L. Alvarez, “Piecewise-linearized cell transmission model and parameter calibration methodology,” _Transportation Research Record_ , vol. 1965, no. 1, pp. 183–191, 2006.
  * [32] A. Ferrara, S. Sacone, S. Siri, C. Vivas, and F. R. Rubio, “Switched observer-based ramp metering controllers for freeway systems,” in _2016 IEEE 55th Conference on Decision and Control (CDC)_. IEEE, 2016, pp. 6777–6782.
  * [33] Y. Guo, “Dynamic-model-based switched proportional-integral state observer design and traffic density estimation for urban freeway,” _European Journal of Control_ , vol. 44, pp. 103–113, 2018.
  * [34] G. C. Gomes, “Optimization and microsimulation of on -ramp metering for congested freeways,” Ph.D. dissertation, University of California, Berkeley, 2004\.
  * [35] G. Gomes and R. Horowitz, “Optimal freeway ramp metering using the asymmetric cell transmission model,” _Transportation Research Part C: Emerging Technologies_ , vol. 14, no. 4, pp. 244–262, 2006.
  * [36] C. Letellier, L. A. Aguirre, and J. Maquet, “Relation between observability and differential embeddings for nonlinear dynamics,” _Phys. Rev. E_ , vol. 71, p. 066213, Jun 2005.
  * [37] A. J. Whalen, S. N. Brennan, T. D. Sauer, and S. J. Schiff, “Observability and controllability of nonlinear networks: The role of symmetry,” _Phys. Rev. X_ , vol. 5, p. 011005, Jan 2015.
  * [38] S. Lall, J. E. Marsden, and S. Glavaški, “Empirical model reduction of controlled nonlinear systems,” _IFAC Proceedings Volumes_ , vol. 32, no. 2, pp. 2598 – 2603, 1999, 14th IFAC World Congress 1999, Beijing, Chia, 5-9 July.
  * [39] M. Serpas, G. Hackebeil, C. Laird, and J. Hahn, “Sensor location for nonlinear dynamic systems via observability analysis and max-det optimization,” _Computers & Chemical Engineering_, vol. 48, pp. 105 – 112, 2013.
  * [40] J. Qi, K. Sun, and W. Kang, “Optimal pmu placement for power system dynamic state estimation by using empirical observability gramian,” _IEEE Transactions on power Systems_ , vol. 30, no. 4, pp. 2041–2054, 2015.
  * [41] A. K. Singh and J. Hahn, “Sensor location for stable nonlinear dynamic systems: Multiple sensor case,” _Industrial & engineering chemistry research_, vol. 45, no. 10, pp. 3615–3623, 2006.
  * [42] A. Haber, F. Molnar, and A. E. Motter, “State observation and sensor selection for nonlinear networks,” _IEEE Transactions on Control of Network Systems_ , vol. 5, no. 2, pp. 694–708, June 2018.
  * [43] S. D. Bopardikar, O. Ennasr, and X. Tan, “Randomized sensor selection for nonlinear systems with application to target localization,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 4, pp. 3553–3560, Oct 2019.
  * [44] S. A. Nugroho and A. F. Taha, “Sensor placement strategies for some classes of nonlinear dynamic systems via lyapunov theory,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_ , 2019, pp. 4551–4556.
  * [45] M. J. Lighthill and G. B. Whitham, “On kinematic waves ii. a theory of traffic flow on long crowded roads,” _Proc. R. Soc. Lond. A_ , vol. 229, no. 1178, pp. 317–345, 1955.
  * [46] P. I. Richards, “Shock waves on the highway,” _Operations research_ , vol. 4, no. 1, pp. 42–51, 1956.
  * [47] S. C. Vishnoi, S. A. Nugroho, A. F. Taha, C. G. Claudel, and T. Banerjee, “Asymmetric cell transmission model-based, ramp-connected robust traffic density estimation under bounded disturbances,” in _2020 American Control Conference, ACC 2020, Denver, CO, USA, July 1-3, 2020_. IEEE, 2020, pp. 1197–1202.
  * [48] S. Hanba, “On the “uniform” observability of discrete-time nonlinear systems,” _IEEE Transactions on Automatic Control_ , vol. 54, no. 8, pp. 1925–1928, 2009.
  * [49] A. J. Krener and K. Ide, “Measures of unobservability,” in _Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference_ , 2009, pp. 6401–6406.
  * [50] J. Löfberg, “YALMIP: A toolbox for modeling and optimization in matlab,” in _Proc. IEEE Int. Symp. Computer Aided Control Syst. Design_ , 2004, pp. 284–289.
  * [51] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.2,” http://cvxr.com/cvx, 2020.
  * [52] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge University Press, 2004.
  * [53] S. A. Nugroho, A. F. Taha, and C. G. Claudel, “A control-theoretic approach for scalable and robust traffic density estimation using convex optimization,” _IEEE Transactions on Intelligent Transportation Systems_ , pp. 1–15, November 2019.
  * [54] E. D. Andersen and K. D. Andersen, _The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm_. Boston, MA: Springer US, 2000, pp. 197–232.
  * [55] T. F. Coleman and Y. Li, “An interior trust region approach for nonlinear minimization subject to bounds,” _SIAM Journal on Optimization_ , vol. 6, no. 2, pp. 418–445, 1996.
  * [56] L. Lovász, _Submodular functions and convexity_. Berlin, Heidelberg: Springer Berlin Heidelberg, 1983, pp. 235–257.
  * [57] L. Yang, D. Sun, and K.-C. Toh, “Sdpnal+: a majorized semismooth newton-cg augmented lagrangian method for semidefinite programming with nonnegative constraints,” _Mathematical Programming Computation_ , vol. 7, no. 3, pp. 331–366, 2015.
  * [58] A. Chakrabarty, S. H. Żak, and S. Sundaram, “State and unknown input observers for discrete-time nonlinear systems,” in _2016 IEEE 55th Conference on Decision and Control (CDC)_ , Dec 2016, pp. 7111–7116.

##  Appendix A State-Space Equation Parameters

In this section, we present the method for deriving the state-space equation
(10). For ease of reading, the time parameter is omitted from the notations
for all the discrete time variables. Also, the state variables are written in
terms of the traffic density variables that they represent. To obtain the
equation (10), we use the analytical expression for the non-linear
$\min(\cdot,\cdot)$ function given as

$\min(a,b)=\dfrac{1}{2}\hskip 1.42262pt(\hskip 1.42262pta\hskip
1.42262pt+\hskip 1.42262ptb\hskip 2.84526pt-\mid a\hskip 1.42262pt-\hskip
1.42262ptb\mid\hskip 1.42262pt).$ (27)

By applying (27) to the non-linear state evolution equations (9) and
simplifying, we can break the equations down to linear and non-linear parts
that are lumped into the state-space equation parameters which are given
below:

$\bm{A}\in\mathbb{R}^{n\times n}$, $n=N+N_{I}+N_{O}$. The elements of $\bm{A}$
can be denoted by $a_{i,j}$ where $,i,j\in[1,n]$, and are given as follows

  * •

$i=1$

$\displaystyle
a_{1,1}=1-\dfrac{T}{4l}\left(v_{f}+w_{c}\right),a_{1,2}=\dfrac{T}{4l}\left(w_{c}-\dfrac{\xi_{2}}{2}\right),$
$\displaystyle a_{1,N+1}=\dfrac{T}{4l}v_{f}$

  * •

$i=N$

$\displaystyle
a_{N,N-1}=\dfrac{T\bar{\beta}_{N-1}}{8l}v_{f},a_{N,N}=1-\dfrac{T}{4l}\left(v_{f}+w_{c}\right),$
$\displaystyle a_{N,n}=-\dfrac{T\bar{\beta}_{N-1}}{4l\beta_{N-1}}w_{c}$

  * •

$i\in\Omega\setminus\Omega_{I}\cup\Omega_{O},i\neq\\{1,N\\},j\in\hat{\Omega},k\in\check{\Omega}$

$\displaystyle
a_{i,i-1}=\dfrac{T\bar{\beta}_{i-1}}{8l}v_{f},a_{i,i}=1-\dfrac{T}{4l}\left(v_{f}+w_{c}\right),$
$\displaystyle
a_{i,i+1}=\dfrac{T}{4l}\left(w_{c}-\dfrac{\xi_{i+1}}{2}\right),a_{i,N+j}=\dfrac{T}{4l}v_{f},$
$\displaystyle
a_{i,N+N_{I}+k}=-\dfrac{T\bar{\beta}_{i-1}}{4l\beta_{i-1}}w_{c}$

  * •

$i\in\Omega_{I},j\in\hat{\Omega}$

$\displaystyle
a_{i,i-1}=\dfrac{T}{4l}v_{f},a_{i,i}=1-\dfrac{T}{4l}\left(v_{f}+w_{c}+\dfrac{\xi_{i}}{2}\right),$
$\displaystyle a_{i,i+1}=\dfrac{T}{4l}w_{c},a_{i,N+j}=\dfrac{T}{4l}v_{f}$

  * •

$i\in\Omega_{O},j\in\check{\Omega}$

$\displaystyle
a_{i,i-1}=\dfrac{T}{4l}v_{f},a_{i,i}=1-\dfrac{T}{4l}\left(\dfrac{1}{2}v_{f}+w_{c}\right),$
$\displaystyle
a_{i,i+1}=\dfrac{T}{4l\bar{\beta}_{i}}w_{c},a_{i,N+N_{I}+j}=\dfrac{T}{4l\beta_{i}}w_{c}$

  * •

$i=N+\bar{i},\bar{i}\in\hat{\Omega},j\in{\Omega_{I}}$

$\displaystyle
a_{i,i}=1-\dfrac{T}{2l}\left(v_{f}+\dfrac{w_{c}}{2}\right),a_{i,j}=\dfrac{T\xi_{j}}{4l}$

  * •

$i=N+N_{I}+\bar{i},\bar{i}\in\check{\Omega},j\in{\Omega_{O}}$

$\displaystyle
a_{i,i}=1-\dfrac{T}{4l}\left(v_{f}+w_{c}\right),a_{i,j}=\dfrac{T\beta_{j}}{8l}v_{f},$
$\displaystyle a_{i,j+1}=-\dfrac{T\beta_{j}}{4l\bar{\beta}_{j}}w_{c}$

The remaining elements of $\bm{A}$ that are not assigned a value above are
equal to 0.

$\bm{f}=\left[f_{1}\hskip 5.69046ptf_{2}\hskip 5.69046pt\dots\hskip
5.69046ptf_{n}\right]^{T}\in\mathbb{R}^{g}$ where $f_{i},i\in[1,n]$ are column
vectors of different but fixed lengths corresponding to the different cases of
mainline sections and ramps, and $g$ is the sum of lengths of all the column
vectors. The elements of each column vector $f_{i}$ can be denoted by
$f_{j,i}$ where $j$ is in the range of the length of $f_{i}$, and are defined
as follows:

  * •

$i=1$

$\displaystyle f_{1,1}=\dfrac{1}{w_{c}l}\mid
f_{in}-\sigma_{1}\mid,f_{2,1}=\dfrac{1}{v_{f}w_{c}l}\mid\delta_{1}-\sigma_{2}\mid,$
$\displaystyle f_{3,1}=\dfrac{1}{w_{c}l}\mid
w_{c}\left(\rho_{m}-\rho_{1}\right)-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{4,1}=\dfrac{1}{v_{f}l}\mid v_{f}\rho_{1}-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{5,1}=\dfrac{1}{w_{c}l}\mid
w_{c}\left(\rho_{m}-\rho_{2}\right)-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{6,1}=\dfrac{1}{v_{f}w_{c}l}\mid
v_{f}\hat{\rho}_{2}-\dfrac{\xi_{2}}{w_{c}}\min\left(w_{c}\left(\rho_{m}-\rho_{2}\right),v_{f}\rho_{c}\right)\mid$
$\displaystyle
f_{7,1}=\dfrac{T}{4l}\left(2f_{in}+\left(\dfrac{\xi_{2}}{2w_{c}}-1\right)v_{f}\rho_{c}+\dfrac{\xi_{2}}{2}\rho_{m}\right)$

  * •

$i=N$

$\displaystyle
f_{1,N}=\dfrac{1}{v_{f}w_{c}l}\mid\delta_{N-1}-\sigma_{N}\mid,f_{2,N}=\dfrac{1}{v_{f}l}\mid\delta_{N}-f_{out}\mid,$
$\displaystyle
f_{3,N}=\dfrac{1}{v_{f}w_{c}l}\mid\bar{\beta}_{N-1}\min\left(v_{f}\rho_{N-1},v_{f}\rho_{c}\right)$
$\displaystyle-\dfrac{\bar{\beta}_{N-1}}{\beta_{N-1}}\check{\sigma}_{N-1}\mid,f_{4,N}=\dfrac{1}{w_{c}l}\mid
w_{c}\left(\rho_{m}-\rho_{N}\right)-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{5,N}=\dfrac{1}{v_{f}l}\mid v_{f}\rho_{N}-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{6,N}=\dfrac{1}{v_{f}l}\mid v_{f}\rho_{N-1}-v_{f}\rho_{c}\mid,$
$\displaystyle
f_{7,N}=\dfrac{T}{4l}\left(\dfrac{\bar{\beta}_{N-1}}{2}v_{f}\rho_{c}+\left(\dfrac{\bar{\beta}_{N-1}}{\beta_{N-1}}+1\right)w_{c}\rho_{m}\right)$

  * •

$i\in\Omega\setminus\Omega_{I}\cup\Omega_{O},i\neq\\{1,N\\}$

$\displaystyle
f_{1,i}=\dfrac{1}{v_{f}w_{c}l}\mid\delta_{i-1}-\sigma_{i}\mid,f_{2,i}=\dfrac{1}{v_{f}w_{c}l}\mid\delta_{i}-\sigma_{i+1}\mid,$
$\displaystyle
f_{3,i}=\dfrac{1}{v_{f}w_{c}l}\mid\bar{\beta}_{i-1}\min(v_{f}\rho_{i-1},v_{f}\rho_{c})$
$\displaystyle-\dfrac{\bar{\beta}_{i-1}}{\beta_{i-1}}w_{c}(\rho_{m}-\check{\rho}_{i-1})\mid,$
$\displaystyle f_{4,i}=\dfrac{1}{w_{c}l}\mid
w_{c}(\rho_{m}-\rho_{i})-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{5,i}=\dfrac{1}{v_{f}l}\mid v_{f}\rho_{i}-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{6,i}=\dfrac{1}{w_{c}l}\mid w_{c}(\rho_{m}-\rho_{i+1})-v_{f}\rho_{c}\mid,$
$\displaystyle f_{7,i}=\dfrac{1}{v_{f}w_{c}l}\mid v_{f}\hat{\rho}_{i+1}$
$\displaystyle-\dfrac{\xi_{i+1}}{w_{c}}\min(w_{c}(\rho_{m}-\rho_{i+1}),v_{f}\rho_{c})\mid,$
$\displaystyle f_{8,i}=\dfrac{1}{v_{f}l}\mid
v_{f}\rho_{i-1}-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{9,i}=\dfrac{T}{4l}\left(\left(\dfrac{\bar{\beta}_{i-1}}{2}+\dfrac{\xi_{i+1}}{2w_{c}}-1\right)v_{f}\rho_{c}+\left(\dfrac{\bar{\beta}_{i-1}}{\beta_{i-1}}\right.\right.$
$\displaystyle\left.\left.+\dfrac{\xi_{i+1}}{2w_{c}}\right)w_{c}\rho_{m}\right)$

  * •

$i\in\Omega_{I}$

$\displaystyle
f_{1,i}=\dfrac{1}{v_{f}w_{c}l}\mid\delta_{i-1}-\sigma_{i}\mid,f_{2,i}=\dfrac{1}{v_{f}w_{c}l}\mid\delta_{i}-\sigma_{i+1}\mid,$
$\displaystyle f_{3,i}=\dfrac{1}{v_{f}l}\mid
v_{f}\rho_{i-1}-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{4,i}=\dfrac{1}{w_{c}l}\mid w_{c}(\rho_{m}-\rho_{i})-v_{f}\rho_{c}\mid,$
$\displaystyle f_{5,i}=\dfrac{1}{v_{f}l}\mid v_{f}\rho_{i}-v_{f}\rho_{c}\mid,$
$\displaystyle f_{6,i}=\dfrac{1}{w_{c}l}\mid
w_{c}(\rho_{m}-\rho_{i+1})-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{7,i}=\dfrac{1}{v_{f}w_{c}l}\mid
v_{f}\hat{\rho}_{i}-\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-\rho_{i}),v_{f}\rho_{c})\mid,$
$\displaystyle f_{8,i}=\dfrac{1}{w_{c}l}\mid
w_{c}(\rho_{m}-\rho_{i})-v_{f}\rho_{c}\mid$ $\displaystyle
f_{9,i}=\dfrac{T\xi_{i}}{8l}\left(\rho_{m}+\dfrac{v_{f}\rho_{c}}{w_{c}}\right)$

  * •

$i\in\Omega_{O}$

$\displaystyle
f_{1,i}=\dfrac{1}{v_{f}w_{c}l}\mid\delta_{i-1}-\sigma_{i}\mid,f_{2,i}=\dfrac{1}{v_{f}w_{c}l}\mid\delta_{i}-\sigma_{i+1}\mid,$
$\displaystyle f_{3,i}=\dfrac{1}{v_{f}l}\mid
v_{f}\rho_{i-1}-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{4,i}=\dfrac{1}{w_{c}l}\mid w_{c}(\rho_{m}-\rho_{i})-v_{f}\rho_{c}\mid,$
$\displaystyle
f_{5,i}=\dfrac{1}{v_{f}w_{c}l}\mid\min(v_{f}\rho_{i},v_{f}\rho_{c})-\dfrac{1}{\beta_{i}}w_{c}(\rho_{m}-\check{\rho}_{i})\mid,$
$\displaystyle f_{6,i}=\dfrac{1}{w_{c}l}\mid
w_{c}(\rho_{m}-\rho_{i+1})-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{7,i}=\dfrac{1}{v_{f}l}\mid v_{f}\rho_{i}-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{8,i}=\dfrac{T}{4l}\left(\left(\dfrac{3}{2}-\dfrac{1}{\bar{\beta}_{i}}\right)v_{f}\rho_{c}+\left(1-\dfrac{1}{\beta_{i}}-\dfrac{1}{\bar{\beta}_{i}}\right)w_{c}\rho_{m}\right)$

  * •

$i=N+\bar{i},\bar{i}\in\hat{\Omega},j\in{\Omega_{I}}$

$\displaystyle f_{1,i}=\dfrac{1}{w_{c}l}\mid\hat{\sigma}_{j}-\hat{f}_{j}\mid,$
$\displaystyle f_{2,i}=\dfrac{1}{v_{f}w_{c}l}\mid
v_{f}\hat{\rho}_{j}-\dfrac{\xi_{j}}{w_{c}}\min(w_{c}(\rho_{m}-\rho_{j}),v_{f}\rho_{c})\mid,$
$\displaystyle f_{3,i}=\dfrac{1}{w_{c}l}\mid
w_{c}(\rho_{m}-\hat{\rho}_{j})-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{4,i}=\dfrac{1}{w_{c}l}\mid w_{c}(\rho_{m}-\rho_{j})-v_{f}\rho_{c}\mid,$
$\displaystyle
f_{5,i}=\dfrac{T}{2l}\left(\left(\dfrac{1}{2}-\dfrac{\xi_{j}}{2w_{c}}\right)v_{f}\rho_{c}+\left(\dfrac{1}{2}-\dfrac{\xi_{j}}{2w_{c}}\right)w_{c}\rho_{m}\right)$

  * •

$i=N+N_{I}+\bar{i},\bar{i}\in\check{\Omega},j\in{\Omega_{O}}$

$\displaystyle
f_{1,i}=\dfrac{1}{v_{f}w_{c}l}\mid\delta_{j}-\sigma_{j+1}\mid,f_{2,i}=\dfrac{1}{v_{f}l}\mid\check{\delta}_{j}-\check{f}_{j}\mid,$
$\displaystyle
f_{3,i}=\dfrac{1}{v_{f}w_{c}l}\mid\min(v_{f}\rho_{j},v_{f}\rho_{c})-\dfrac{1}{\beta_{j}}\check{\sigma}_{j}\mid,$
$\displaystyle f_{4,i}=\dfrac{1}{w_{c}l}\mid
w_{c}(\rho_{m}-\rho_{j+1})-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{5,i}=\dfrac{1}{v_{f}l}\mid
v_{f}\check{\rho}_{j}-v_{f}\rho_{c}\mid,f_{6,i}=\dfrac{1}{v_{f}l}\mid
v_{f}\rho_{j}-v_{f}\rho_{c}\mid,$ $\displaystyle
f_{7,i}=\dfrac{T}{2l}\left(\left(\dfrac{\beta_{j}}{4}+\dfrac{\beta_{j}}{2\bar{\beta}_{j}}-\dfrac{1}{2}\right)v_{f}\rho_{c}+\left(\dfrac{1}{2}+\dfrac{\beta_{j}}{2\bar{\beta}_{j}}\right)w_{c}\rho_{m}\right)$

$\bm{G}\in\mathbb{R}^{n\times g}$ is of the form

$\begin{bmatrix}G_{1}&0&\cdots&\cdots&0\\\ 0&G_{2}&\ddots&&\vdots\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\ \vdots&&\ddots&G_{n-1}&0\\\
0&\cdots&\cdots&0&G_{n}&\end{bmatrix},$ where $G_{i},i\in[1,n]$ are row
vectors with the same number of columns as the number of rows in $f_{i}$. The
elements of each row vector $G_{i}$ can be denoted by $G_{i,j}$, where $j$ is
in the range of the length of $G_{i}$, and are defined as follows:

  * •

$i=1$

$G_{i}=\dfrac{Tv_{f}w_{c}}{4}\left[\begin{matrix}-\dfrac{2}{v_{f}}&2&-\dfrac{1}{v_{f}}&\dfrac{1}{w_{c}}\end{matrix}\right.\\\
\left.\begin{matrix}\left(\dfrac{1}{v_{f}}-\dfrac{\xi_{2}}{2v_{f}w_{c}}\right)&-1&\dfrac{4}{Tv_{f}w_{c}}\end{matrix}\right]$

  * •

$i=N$

$G_{i}=\dfrac{Tv_{f}w_{c}}{4}\left[\begin{matrix}-2&\dfrac{2}{w_{c}}&-1&-\dfrac{1}{v_{f}}&\dfrac{1}{w_{c}}\end{matrix}\right.\\\
\left.\begin{matrix}&-\dfrac{\bar{\beta}_{N-1}}{2w_{c}}&\dfrac{4}{Tv_{f}w_{c}}\end{matrix}\right]$

  * •

$i\in\Omega\setminus\Omega_{I}\cup\Omega_{O},i\neq\\{1,N\\}$

$G_{i}=\dfrac{Tv_{f}w_{c}}{4}\left[\begin{matrix}-2&2&-1&-\dfrac{1}{v_{f}}&\dfrac{1}{w_{c}}\end{matrix}\right.\\\
\left.\begin{matrix}\left(\dfrac{1}{v_{f}}-\dfrac{\xi_{i+1}}{2v_{f}w_{c}}\right)&-1&-\dfrac{\bar{\beta}_{i-1}}{2w_{c}}&\dfrac{4}{Tv_{f}w_{c}}\end{matrix}\right]$

  * •

$i\in\Omega_{I}$

$G_{i}=\dfrac{Tv_{f}w_{c}}{4}\left[\begin{matrix}-2&2&-\dfrac{1}{w_{c}}&-\dfrac{1}{v_{f}}&\dfrac{1}{w_{c}}&\dfrac{1}{v_{f}}\end{matrix}\right.\\\
\left.\begin{matrix}-1&-\dfrac{\xi_{i}}{2v_{f}w_{c}}&\dfrac{4}{Tv_{f}w_{c}}\end{matrix}\right]$

  * •

$i\in\Omega_{O}$

$G_{i}=\dfrac{Tv_{f}w_{c}}{4}\left[\begin{matrix}-2&\dfrac{2}{\bar{\beta}_{i}}&-\dfrac{1}{w_{c}}&-\dfrac{1}{v_{f}}&1\end{matrix}\right.\\\
\left.\begin{matrix}\dfrac{1}{v_{f}\bar{\beta}_{i}}&\dfrac{1}{2w_{c}}&\dfrac{4}{Tv_{f}w_{c}}\end{matrix}\right]$

  * •

$i=N+\bar{i},\bar{i}\in\hat{\Omega},j\in{\Omega_{I}}$

$\displaystyle
G_{i}=\dfrac{Tw_{c}}{4}\left[\begin{matrix}-2&2v_{f}&-1&\dfrac{\xi_{j}}{w_{c}}&\dfrac{4}{Tw_{c}}\end{matrix}\right]$

  * •

$i=N+N_{I}+\bar{i},\bar{i}\in\check{\Omega},j\in{\Omega_{O}}$

$G_{i}=\dfrac{Tv_{f}}{4}\left[\begin{matrix}-\dfrac{2w_{c}\beta_{j}}{\bar{\beta}_{j}}&2&-w_{c}\beta_{j}&-\dfrac{w_{c}\beta_{j}}{v_{f}\bar{\beta}_{j}}&1\end{matrix}\right.\\\
\left.\begin{matrix}-\dfrac{\beta_{j}}{2}&\dfrac{T}{4v_{f}}\end{matrix}\right]$

$\bm{B_{u}}\in\mathbb{R}^{n\times(2+N_{I}+N_{O})}$. The elements of
$\bm{B_{u}}$ can be denoted by $\bm{B}_{i,j}$ and are given by the following
function
$\bm{B}_{i,j}=\begin{cases}\dfrac{T}{2l}f_{in},&\mathrm{if}\>i=j=1\\\
-\dfrac{T}{2l}f_{out},&\mathrm{if}\>i=N,j=2\\\
\dfrac{T}{2l}\hat{f}_{k},&\mathrm{if}\>i=N+\bar{i},j=2+\bar{i},\bar{i}\in\hat{\Omega},k\in\Omega_{I}\\\
-\dfrac{T}{2l}\check{f}_{k},&\mathrm{if}\>i=N+N_{I}+\bar{i},j=2+N_{I}+\bar{i},\\\
&\bar{i}\in\check{\Omega},k\in\Omega_{I}\\\ 0,&\mathrm{otherwise}.\end{cases}$

##  Appendix B Calculation of Jacobian Matrix

To calculate the Jacobian matrix for the non-linear vector valued function
$\bm{f}(\bm{x},\bm{u})$ containing $\mid\cdot\mid$ and $\min(\cdot,\cdot)$
functions, we first replace all the $\min(\cdot,\cdot)$ functions by their
analytical form (27) and then calculate the derivative using the definition of
the derivative for $\mid\cdot\mid$ function given as

$\displaystyle\dfrac{\partial\mid x\mid}{\partial x}=\dfrac{x}{\mid
x\mid},x\neq 0$ (28)

At $x=0$, we simply take the derivative to be 0. The elements of the Jacobian
matrix can be calculated using (28) along with the chain rule of
differentiation. For example, the element $f_{2,i}$ in
$f_{i},i\in\Omega_{I},j=N+\bar{j},\bar{j}\in\hat{\Omega}$ can be
differentiated with respect to the state variable $x_{i}$, for
$\delta_{i-1}\neq\sigma_{i}$, as follows:

$\displaystyle\dfrac{\partial f_{1,i}}{\partial x_{i}}$
$\displaystyle=\dfrac{1}{v_{f}w_{c}l}\cdot\dfrac{\partial\mid\delta_{i-1}-\sigma_{i}\mid}{\partial
x_{i}}$
$\displaystyle=-\dfrac{1}{v_{f}w_{c}l}\cdot\dfrac{\delta_{i-1}-\sigma_{i}}{\mid\delta_{i-1}-\sigma_{i}\mid}\cdot\dfrac{\partial\sigma_{i}}{\partial
x_{i}},$

where

$\displaystyle\dfrac{\partial\sigma_{i}}{\partial x_{i}}$
$\displaystyle=\dfrac{\partial\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})}{\partial
x_{i}}-\dfrac{\partial r_{i}}{\partial x_{i}}.$

Here, for $w_{c}(\rho_{m}-x_{i})\neq v_{f}\rho_{c}$,

$\displaystyle\dfrac{\partial\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})}{\partial
x_{i}}$
$\displaystyle=-\dfrac{w_{c}}{2}\left(1-\dfrac{w_{c}(\rho_{m}-x_{i})-v_{f}\rho_{c}}{\mid
w_{c}(\rho_{m}-x_{i})-v_{f}\rho_{c}\mid}\right),$

and for
$v_{f}x_{j}\neq\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})$,

$\displaystyle\dfrac{\partial r_{i}}{\partial x_{i}}$
$\displaystyle=-\dfrac{\xi_{i}}{2w_{c}}\cdot\dfrac{w_{c}}{2}\left(1-\dfrac{w_{c}(\rho_{m}-x_{i})-v_{f}\rho_{c}}{\mid
w_{c}(\rho_{m}-x_{i})-v_{f}\rho_{c}\mid}\right)\cdot$
$\displaystyle\left(1+\dfrac{v_{f}x_{j}-\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})}{\mid
v_{f}x_{j}-\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})\mid}\right).$

Therefore, the derivative can be written as

$\displaystyle\dfrac{\partial f_{1,i}}{\partial
x_{i}}=\dfrac{1}{2v_{f}l}\cdot\dfrac{\delta_{i-1}-\sigma_{i}}{\mid\delta_{i-1}-\sigma_{i}\mid}\left(1-\dfrac{w_{c}(\rho_{m}-x_{i})-v_{f}\rho_{c}}{\mid
w_{c}(\rho_{m}-x_{i})-v_{f}\rho_{c}\mid}\right)\cdot$
$\displaystyle\left(1-\dfrac{\xi_{i}}{2w_{c}}\left(1+\dfrac{v_{f}x_{j}-\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})}{\mid
v_{f}x_{j}-\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})\mid}\right)\right).$

Note that the above expression is valid when $\delta_{i-1}\neq\sigma_{i}$,
$w_{c}(\rho_{m}-x_{i})\neq v_{f}\rho_{c}$ and
$v_{f}x_{j}\neq\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})$.
If, on the other hand, $w_{c}(\rho_{m}-x_{i})=v_{f}\rho_{c}$, then

$\displaystyle\dfrac{\partial f_{1,i}}{\partial
x_{i}}=\dfrac{1}{2v_{f}l}\cdot\dfrac{\delta_{i-1}-\sigma_{i}}{\mid\delta_{i-1}-\sigma_{i}\mid}\cdot$
$\displaystyle\left(1-\dfrac{\xi_{i}}{2w_{c}}\left(1+\dfrac{v_{f}x_{j}-\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})}{\mid
v_{f}x_{j}-\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})\mid}\right)\right),$

if
$v_{f}x_{j}=\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})$,
then

$\displaystyle\dfrac{\partial f_{1,i}}{\partial x_{i}}=$
$\displaystyle\dfrac{1}{2v_{f}l}\cdot\dfrac{\delta_{i-1}-\sigma_{i}}{\mid\delta_{i-1}-\sigma_{i}\mid}\left(1-\dfrac{\xi_{i}}{2w_{c}}\right)\cdot$
$\displaystyle\left(1-\dfrac{w_{c}(\rho_{m}-x_{i})-v_{f}\rho_{c}}{\mid
w_{c}(\rho_{m}-x_{i})-v_{f}\rho_{c}\mid}\right).$

if both $w_{c}(\rho_{m}-x_{i})=v_{f}\rho_{c}$, and
$v_{f}x_{j}=\dfrac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})$,
then

$\displaystyle\dfrac{\partial f_{1,i}}{\partial x_{i}}=$
$\displaystyle\dfrac{1}{2v_{f}l}\cdot\dfrac{\delta_{i-1}-\sigma_{i}}{\mid\delta_{i-1}-\sigma_{i}\mid}\left(1-\dfrac{\xi_{i}}{2w_{c}}\right).$

and if $\delta_{i-1}=\sigma_{i}$, then $\dfrac{\partial f_{1,i}}{\partial
x_{i}}=0.$ Similarly, other elements of the Jacobian matrix can also be
derived.

##  Appendix C Calculation of Lipschitz constant

In this section we present the methodology for calculating a Lipschitz
constant $\gamma$ that satisfies

$\displaystyle\lvert\lvert\bm{f}(\bm{x},u)-\bm{f}(\hat{\bm{x}},u)\rvert\rvert_{2}\leq\gamma\lvert\lvert\bm{x}-\bm{\hat{x}}\rvert\rvert_{2}$

To calculate $\gamma$, we use the following inequalities related to the
$\mid\cdot\mid$ function:

$\displaystyle\mid\mid a\mid-\mid b\mid\mid\hskip 5.69054pt\leq\hskip
5.69054pt\mid a-b\mid$ (29a) $\displaystyle\mid a\pm b\mid\hskip
5.69054pt\leq\hskip 5.69054pt\mid a\mid+\mid b\mid$ (29b) $\displaystyle\mid
a_{1}\mid+\mid a_{2}\mid\hskip 5.69054pt\leq\hskip
5.69054pt\sqrt{2}(a_{1}^{2}+a_{2}^{2})^{1/2}=\sqrt{2}\lvert\lvert\bm{a}\rvert\rvert_{2}$
(29c)

By using one or more of these inequalities we can calculate the Lipschitz
constant for each component of the vector function $\bm{f}(\cdot)$, and
combine them to obtain the final $\gamma$.

For example, let us calculate the the Lipschitz constant for the expression
$f_{1,i},i\in\Omega_{I}$, which, for $j=N+\bar{j},\bar{j}\in\hat{\Omega}$, is
given as

$\displaystyle
f_{1,i}=\frac{1}{v_{f}w_{c}l}\mid\min(v_{f}x_{i-1},v_{f}\rho_{c})-\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})$
$\displaystyle-\min\big{(}v_{f}x_{j},\frac{\xi_{i}}{w_{c}}\min(w_{c}(\rho_{m}-x_{i}),v_{f}\rho_{c})\big{)}\mid.$

Using (27), (29a), and (29b), and simplifying, we can write the following
inequality for $\mid f_{1,i}-\hat{f}_{1,i}\mid$:

$\displaystyle\mid
f_{1,i}-\hat{f}_{1,i}\mid\leq\frac{1}{2v_{f}w_{c}l}(2v_{f}\mid
x_{i-1}-\hat{x}_{i-1}\mid$
$\displaystyle+2\Big{(}1-\frac{\xi_{i}}{2w_{c}}\Big{)}w_{c}\mid
x_{i}-\hat{x}_{i}\mid+2v_{f}\mid x_{j}-\hat{x}_{j}\mid$
$\displaystyle+\xi_{i}\mid x_{i}-\hat{x}_{i}\mid).$

By applying (29c) to combine the terms with the same coefficients and then
adding up all the coefficients, we can write the above inequality as

$\displaystyle\mid
f_{1,i}-\hat{f}_{1,i}\mid\leq\frac{1}{l}\Big{(}\frac{\sqrt{2}}{w_{c}}+\frac{1}{v_{f}}\Big{)}\lvert\lvert\bm{x}-\bm{\hat{x}}\rvert\rvert_{2}.$

Let us call the coefficient of
$\lvert\lvert\bm{x}-\bm{\hat{x}}\rvert\rvert_{2}$ in the above equation as
$\gamma_{1,i}$. We can obtain the $\gamma_{i}$ corresponding to $f_{i}$ by
adding these coefficient values for all the components of the vector $f_{i}$.

The values of $\gamma_{i}$ for different cases of mainline sections and ramps
are given below:

  * •

$i=1$

$\displaystyle\frac{1}{l}\Big{(}\frac{1+\sqrt{2}}{w_{c}}+\frac{1}{v_{f}}+\frac{\xi_{2}}{v_{f}w_{c}}+4\Big{)}$

  * •

$i=N$

$\displaystyle\frac{1}{l}\Big{(}\frac{2\bar{\beta}_{N-1}}{w_{c}}+\Big{(}1+2\frac{\bar{\beta}_{N-1}}{\beta_{N-1}}\Big{)}\frac{1}{v_{f}}+4\Big{)}$

  * •

$i\in\Omega\setminus\Omega_{I}\cup\Omega_{O},i\neq\\{1,N\\}$

$\displaystyle\frac{1}{l}\Big{(}\frac{1+\sqrt{2}+2\bar{\beta}_{i-1}}{w_{c}}+\Big{(}1+\frac{\bar{\beta}_{i-1}}{\beta_{i-1}}\Big{)}\frac{2}{v_{f}}+\frac{\xi_{i+1}}{v_{f}w_{c}}+4\Big{)}$

  * •

$i\in\Omega_{I}$

$\displaystyle\frac{1}{l}\Big{(}\frac{2+\sqrt{2}}{w_{c}}+\frac{2}{v_{f}}+\frac{\xi_{i}}{v_{f}w_{c}}+5\Big{)}$

  * •

$i\in\Omega_{O}$

$\displaystyle\frac{1}{l}\Big{(}\frac{2+\bar{\beta}_{i}}{w_{c}}+\big{(}2+\frac{\bar{\beta}_{i}}{\beta_{i}}+\frac{1}{\beta_{i}}\Big{)}\frac{1}{v_{f}}+4\Big{)}$

  * •

$i=N+\bar{i},\bar{i}\in\hat{\Omega},j\in{\Omega_{I}}$

$\displaystyle\frac{1}{l}\Big{(}\frac{1}{w_{c}}+\frac{\xi_{j}}{v_{f}w_{c}}+3\Big{)}$

  * •

$i=N+N_{I}+\bar{i},\bar{i}\in\check{\Omega},j\in{\Omega_{O}}$

$\displaystyle\frac{1}{l}\Big{(}\frac{1+\bar{\beta}_{j}}{w_{c}}+\Big{(}1+\frac{\bar{\beta}_{j}}{\beta_{j}}+\frac{1}{\beta_{j}}\Big{)}\frac{1}{v_{f}}+4\Big{)}$

So, for every $f_{i},i\in[1,n]$, there exists a $\gamma_{i}$ such that$\mid
f_{i}-\hat{f}_{i}\mid\leq\gamma_{i}\lvert\lvert\bm{x}-\hat{\bm{x}}\rvert\rvert_{2},\gamma_{i}\geq
0$. Since we know that

$\displaystyle\lvert\lvert\bm{f}(x,u)-\bm{f}(\hat{x},u)\rvert\rvert_{2}^{2}=\sum_{i=1}^{n}\mid
f_{i}-\hat{f}_{i}\mid^{2}\leq\sum_{i=1}^{n}\gamma_{i}^{2}\lvert\lvert\bm{x}-\hat{\bm{x}}\rvert\rvert_{2}^{2}$

then $\gamma$ for $\bm{f}(x,u)$ can be defined using function $h(\cdot)$ which
is given by (C).

$\displaystyle h\hskip 1.42262pt$ $\displaystyle(v_{f},\hskip
1.42262pt\omega_{c},\hskip 1.42262ptl,\hskip 1.42262pt\xi_{1},\hskip
1.42262pt\xi_{2},\hskip 1.42262pt\dots,\hskip 1.42262pt\xi_{N_{I}},\hskip
1.42262pt\beta_{1},\hskip 1.42262pt\beta_{2},\hskip 1.42262pt\dots,\hskip
1.42262pt\beta_{N_{O}})$
$\displaystyle=\frac{1}{l}\Bigg{(}\Big{(}\frac{1+\sqrt{2}}{w_{c}}+\frac{1}{v_{f}}+\frac{\xi_{2}}{v_{f}w_{c}}+4\Big{)}^{2}$
$\displaystyle+\Big{(}\frac{2\bar{\beta}_{N-1}}{w_{c}}+\Big{(}1+2\frac{\bar{\beta}_{N-1}}{\beta_{N-1}}\Big{)}\frac{1}{v_{f}}+4\Big{)}^{2}$
$\displaystyle+\sum_{\begin{subarray}{c}i\in\Omega\setminus\Omega_{I}\cup\Omega_{O},\\\
i\neq\\{1,N\\}\end{subarray}}\Big{(}\frac{1+2\bar{\beta}_{i-1}+\sqrt{2}}{w_{c}}+\Big{(}1+\frac{\bar{\beta}_{i-1}}{\beta_{i-1}}\Big{)}\frac{2}{v_{f}}$
$\displaystyle+\frac{\xi_{i+1}}{v_{f}w_{c}}+4\Big{)}^{2}+\sum_{i\in\Omega_{I}}\Big{(}\frac{2+\sqrt{2}}{w_{c}}+\frac{2}{v_{f}}+\frac{\xi_{i}}{v_{f}w_{c}}+5\Big{)}^{2}$
$\displaystyle+\sum_{j\in\Omega_{I}}\Big{(}\frac{1}{w_{c}}+\frac{\xi_{j}}{v_{f}w_{c}}+3\Big{)}^{2}$
$\displaystyle+\sum_{i\in\Omega_{O}}\Big{(}\frac{2+\bar{\beta}_{i}}{w_{c}}+\big{(}2+\frac{\bar{\beta}_{i}}{\beta_{i}}+\frac{1}{\beta_{i}}\Big{)}\frac{1}{v_{f}}+4\Big{)}^{2}$
$\displaystyle+\sum_{j\in\Omega_{O}}\Big{(}\frac{1+\bar{\beta}_{j}}{w_{c}}+\Big{(}1+\frac{\bar{\beta}_{j}}{\beta_{j}}+\frac{1}{\beta_{j}}\Big{)}\frac{1}{v_{f}}+4\Big{)}^{2}\Bigg{)}^{1/2}$
(30)

##  Appendix D Proof of Theorem 3

Let $\bm{z}=\bm{Z}\bm{e}$ be the performance output for estimation error
$\bm{e}$ and $\bm{w}$ be an unknown bounded disturbance. Let
$V(\bm{e})=\bm{e}^{\top}\bm{P}\bm{e}$ be a Lyapunov function candidate where
$\bm{P}\succ 0$. It can be shown that—for example, see [58]—the estimation
error dynamics (23) is $\mathcal{L}_{\infty}$ stable with performance level
$\mu=\sqrt{\mu_{0}\mu_{1}+\mu_{2}}$ if there exist constants
$\mu_{0},\mu_{1},\mu_{2}\in\mathbb{R}_{+}$ such that

$\displaystyle\mu_{0}\left\lVert\bm{w}\right\rVert_{2}^{2}$ $\displaystyle\leq
V(\bm{e})\;\Rightarrow\Delta{V}(\bm{e})\leq 0$ (31a)
$\displaystyle\left\lVert\bm{z}\right\rVert_{2}^{2}$
$\displaystyle\leq\mu_{1}V(\bm{e})+\mu_{2}\left\lVert\bm{w}\right\rVert_{2}^{2},$
(31b)

for all $t\geq 0$ where
$\Delta{V}(\bm{e})\triangleq{V}(\bm{e}[k+1])-{V}(\bm{e}[k])$. First, realize
that (31a) holds if there exists $\alpha>0$ such that

$\displaystyle{V}(\bm{e}[k+1])-{V}(\bm{e}[k])\;$
$\displaystyle+\alpha\left(V(\bm{e}[k])-\mu_{0}\left\lVert\bm{w}[k]\right\rVert_{2}^{2}\right)$
$\displaystyle\leq 0$
$\displaystyle\Leftrightarrow{\bm{e}}^{\top}[k+1]\bm{P}\bm{e}[k+1]-(1-\alpha){\bm{e}}^{\top}[k]\bm{P}{\bm{e}}[k]\;$
$\displaystyle-\alpha\mu_{0}\bm{w}^{\top}[k]\bm{w}[k]$ $\displaystyle\leq 0$

which is equivalent to

$\displaystyle\begin{bmatrix}\bm{e}\\\ \Delta\bm{f}\\\
\bm{w}\end{bmatrix}^{\top}\left(\bm{\Pi}+\bm{\Psi}^{\top}\bm{P}^{-1}\bm{\Psi}\right)\begin{bmatrix}\bm{e}\\\
\Delta\bm{f}\\\ \bm{w}\end{bmatrix}$ $\displaystyle\leq 0,$ (32)

where
$\bm{\Pi}:=\mathrm{Blkdiag}\left(\left[(\alpha-1)\bm{P},\bm{O},-\alpha\mu_{0}\bm{I}\right]\right)$
and $\bm{\Psi}$ is defined as

$\displaystyle\bm{\Psi}\triangleq\begin{bmatrix}\bm{P}\bm{A}-\bm{P}\bm{L}\bm{C}&\bm{P}\bm{G}&\bm{P}\bm{B_{\mathrm{w}}}-\bm{P}\bm{L}\bm{D_{\mathrm{w}}}\end{bmatrix}.$

Since the nonlinear function $\bm{f}(\cdot)$ is locally Lipschitz in
$\bm{\Omega}$, then it holds that

$\displaystyle\left\lVert\Delta\bm{f}[k]\right\rVert_{2}^{2}$
$\displaystyle\leq\gamma_{l}^{2}\left\lVert\bm{e}[k]\right\rVert_{2}^{2}$
$\displaystyle\Leftrightarrow\Delta\bm{f}^{\top}\Delta\bm{f}-\gamma_{l}^{2}\bm{e}^{\top}\bm{e}$
$\displaystyle\leq 0$ $\displaystyle\Leftrightarrow\begin{bmatrix}\bm{e}\\\
\Delta\bm{f}\\\
\bm{w}\end{bmatrix}^{\top}\begin{bmatrix}-\gamma_{l}^{2}\bm{I}&*&*\\\
\bm{O}&\bm{I}&*\\\ \bm{O}&\bm{O}&\bm{O}\end{bmatrix}\begin{bmatrix}\bm{e}\\\
\Delta\bm{f}\\\ \bm{w}\end{bmatrix}$ $\displaystyle\leq 0.$ (33)

By applying the S-procedure to (32) from (33) for $\epsilon\geq 0$, we get

$\displaystyle\mathrm{Blkdiag}\left(\left[(\alpha-1)\bm{P}+\epsilon\gamma_{l}^{2}\bm{I},-\epsilon\bm{I},-\alpha\mu_{0}\bm{I}\right]\right)+\bm{\Psi}^{\top}\bm{P}^{-1}\bm{\Psi}\preceq
0,$

which, thanks to the Schur Complement, is equivalent to

$\displaystyle\begin{bmatrix}\begin{array}[]{c|c}\mathrm{Blkdiag}\left(\left[(\alpha-1)\bm{P}+\epsilon\gamma_{l}^{2}\bm{I},-\epsilon\bm{I},-\alpha\mu_{0}\bm{I}\right]\right)\vspace*{0.0cm}&*\\\
\hline\cr\bm{\Psi}&-\bm{P}\end{array}\end{bmatrix}\preceq 0.$

Notice that the above is equivalent to (24b) provided that
$\bm{Y}\triangleq\bm{P}\bm{L}$. Next, substituting $\bm{z}=\bm{Z}\bm{e}$ to
(31b) yields

$\displaystyle\left\lVert\bm{Z}\bm{e}\right\rVert_{2}^{2}-\mu_{1}V(\bm{e})-\mu_{2}\left\lVert\bm{w}\right\rVert_{2}^{2}$
$\displaystyle\leq 0$
$\displaystyle\Leftrightarrow\bm{e}^{\top}\bm{Z}^{\top}\bm{Z}\bm{e}-\mu_{1}\bm{e}^{\top}\bm{P}\bm{e}-\mu_{2}\bm{w}^{\top}\bm{w}$
$\displaystyle\leq 0$ $\displaystyle\Leftrightarrow\begin{bmatrix}\bm{e}\\\
\bm{w}\end{bmatrix}^{\top}\begin{bmatrix}\bm{Z}^{\top}\bm{Z}-\mu_{1}\bm{P}&\bm{O}\\\
\bm{O}&-\mu_{2}\bm{I}\end{bmatrix}\begin{bmatrix}\bm{e}\\\
\bm{w}\end{bmatrix}$ $\displaystyle\leq 0$
$\displaystyle\Leftrightarrow\begin{bmatrix}\bm{Z}^{\top}\bm{Z}-\mu_{1}\bm{P}&\bm{O}\\\
\bm{O}&-\mu_{2}\bm{I}\end{bmatrix}$ $\displaystyle\preceq 0$

By employing congruence transformation (provided that $\mu_{1}>0$) and
applying the Schur Complement, it is not difficult to show that the above is
equivalent to (24c). Finally, the objective function (24a) tries to minimize
the performance index, which dictates how much the disturbance $\bm{w}$ will
impact the performance vector $\bm{z}$. This implies that if optimization
problem (24) is solved, then the estimation error dynamics given in (23) is
$\mathcal{L}_{\infty}$ stable with performance level
$\mu=\sqrt{\mu_{0}\mu_{1}+\mu_{2}}$ and observer gain given as
$\bm{L}=\bm{P}^{-1}\bm{Y}$, thus completing the proof.  $\blacksquare$