# Solutions to Switched Hamilton-Jacobi Equations and Conservation Laws Using Hybrid Components

Christian Claudel, Alexandre M. Bayen

<figure><img src="image_1.png" /></figure>

## To cite this version:

Christian Claudel, Alexandre M. Bayen. Solutions to Switched Hamilton-Jacobi Equations and Conservation Laws Using Hybrid Components. 11th International Workshop on Hybrid Systems: Computation and Control, Apr 2008, St Louis, United States. 10.1007/978-3-540-78929-1_8. hal-01471102

HAL Id: hal-01471102

https://hal.science/hal-01471102

Submitted on 19 Feb 2017

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Solutions to Switched Hamilton-Jacobi Equations and Conservation Laws Using Hybrid Components

Christian G. Claudel¹ and Alexandre M. Bayen²

¹ Electrical Engineering and Computer Sciences

² Systems Engineering, Civil and Environmental Engineering
University of California, Berkeley

Berkeley, CA, 94720-1710

claudel@eecs.berkeley.edu

**Abstract.** We investigate a class of hybrid systems driven by partial differential equations for which the infinite dimensional state can switch in time and in space at the same time. We consider a particular class of such problems (switched *Hamilton-Jacobi equations*) and define hybrid components as building blocks of hybrid solutions to such problems, using viability theory. We derive sufficient conditions for well-posedness of such problems, and use a generalized *Lax-Hopf formula* to compute these solutions. We illustrate the results with three examples: the computation of the hybrid components of a *Lighthill-Whitham-Richards* equation; a velocity control policy for a highway system; a data assimilation problem using Lagrangian measurements generated from NGSIM traffic data.

## 1 Introduction

This article investigates a particular class of hybrid systems in which modes are not governed by *ordinary differential equations* (ODEs) as in classical hybrid systems theory [20] but by *partial differential equations* (PDEs). Unlike for ODEs for which modes evolve in finite dimensional spaces, functions solving PDEs evolve in “infinite” dimensional spaces (functional spaces). The framework developed for hybrid systems governed by ODEs [20] can be extended to systems governed by PDEs, though to our best knowledge, no general formalism has been developed to this day to characterize such systems in a unifying way. This is due in part to the fact that for systems driven by PDEs, the switching structure is more complex than in the case of ODEs. Indeed, hybridness can occur in different ways. We outline three specific structures of interest to us:

* *Switching the PDE in time on the full spatial domain.* This situation is illustrated in Figure 1 (left) and is the PDE counterpart of hybrid systems as defined by [20]. The PDEs – and/or *boundary conditions* (BCs) – are switched sequentially in time. Switching of boundary conditions has been investigated in the context of highway traffic [19,6] and canal systems [2]. Switching PDEs
in time sequentially appears in general form in [10] and in the context of highway transportation systems in [6].

* *Switching the PDE on parts of the spatial domain.* This is illustrated in Figure 1 (center). This situation is typical of shape optimization problems, or fluid structure interactions problems [12]. Note that the variable $y$ has been used along the vertical axis instead of $t$ to emphasize that this type of switching is also valid for PDEs not modeling phenomena not depending on time (for example elliptic PDEs depending on space variables only).

* *Switching the PDE on parts of the time-space domain.* This is illustrated in Figure 1 (right). Examples include the Lighthill-Whitham-Richards (LWR) PDE with triangular flux function, which can be decomposed into two modes (two one-dimensional wave equations) resulting in a partition of the $(x, t)$ space in regions with forward traveling waves, and regions with backward travelling waves [13,16,1]. This last case is particularly challenging because the switching surfaces are in general not known a priori and must be computed while solving the PDE. If they are known (or if they are derived), additional consistency conditions are needed in order the problem to be well posed, which is the object of the present article.

Not all switched PDE problems fit in one of the three categories above. In particular, the work [18] in the context of biological systems exhibits a source term which is distributed in space and time and can switch modes at every point in the space/time domain. The present article is mostly concerned with the last

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** BC denotes boundary conditions; IC denotes initial conditions. **Left:** PDEs (and BCs) switched in time. **Middle:** PDEs (and ICs) switched in space; **Right:** PDEs switched in space and time.</figcaption></figure>

case in the list above, in which the switching structure can happen concurrently in space and time. It corresponds to a situation fundamentally different than in the case of hybrid systems driven by ODEs: the infinite dimensional state can be partially switched, based on the $(x, t)$ location in time and space of the point of interest. We develop a method to decompose the $(x, t)$ domain of definition of a solution to a hybrid system problem driven by PDEs into *hybrid components*, which are subsets of the $(x, t)$ space in which a different PDE applies (in Figure 1 right, there would be three hybrid components). The definition of these hybrid components is not trivial, as in general, sufficient conditions for existence and well posedness of such solutions are difficult to find. The contributions of this
article is the derivation of sufficient conditions for the use of hybrid components for a class of Hamilton-Jacobi (HJ) PDEs. We construct the general solution (denoted $M(t, x)$) to a class of HJ PDEs (sections 2, 3 and 4), and define hybrid components as parts of the $(x, t)$ solution domain in which we would like another PDE to apply, for which we assume we know a solution $\overline{M}(t, x)$. We use an inf morphism property to construct the solution $M(t, x)$ of the HJ PDE, first without hybrid components (section 4), and then with hybrid components (section 5). We compute a sufficient condition for compatibility of the initial and boundary conditions of the HJ PDE problem with the hybrid components added by $\overline{M}(t, x)$. In section 6, we illustrate the result with three examples. First, we compute the hybrid components of a LWR PDE. Second, we use the method to solve a speed control problem on the highway. Finally, we apply it to data assimilation with NGSIM data.

## 2 Problem Definition

We consider the class of first order scalar hyperbolic conservation laws with concave flux functions. For illustrative purposes, we will derive the results in the context of highway traffic, which can be modeled by such conservation laws.

**Definition 1** [13,16] [First order scalar hyperbolic conservation laws]. We consider a density function $\rho(t, x)$ (representing the number of vehicles per unit length located at $x$, at time $t$) governed by the following PDE:

$$ \frac{\partial \rho(t, x)}{\partial t} + \frac{\partial \psi(\rho(t, x))}{\partial x} = 0 \qquad (1) $$

where $\psi$ is a concave flux function ranging in the interval $[0, \omega]$.

In the context of traffic flow, the function $\psi$ is referred to as fundamental diagram, and depends on several empirical parameters, such as number of lanes, road geometry and vehicle capabilities. We define $X := [\xi, \chi]$ as the domain in which equation (1) applies (in physical terms, the extent of the highway section of interest). In the case of the highway, if consecutive integer labels are assigned to vehicles entering the highway at location $x = \xi$, one can define a function $M$ tracking the vehicles on the highway: the Moskowitz function $M(\cdot, \cdot)$. The Moskowitz function is a continuous function satisfying $[M(t, x)] = n$ where $n$ is the label of the vehicle located in $x$ at time $t$. It was first introduced in [14], appeared later in the famous Newell trilogy [15], and was formally defined by Daganzo in [8,9].

**Definition 2** [Moskowitz function]. The Moskowitz function solves the following HJ PDE [8,9]:

$$ \frac{\partial M(t, x)}{\partial t} - \psi \left( - \frac{\partial M(t, x)}{\partial x} \right) = 0 \qquad (2) $$
Whenever $\mathbf{M}$ is differentiable, the definition of the Moskowitz function implies that $\rho(t, x) = -\frac{\partial \mathbf{M}(t, x)}{\partial x}$, where $\rho(t, x)$ is the density at location $x$ and time $t$, as defined by [15]. By definition of the Moskowitz function, the iso-level sets of $\mathbf{M}$ represent the vehicles trajectories [9].

**Definition 3 [Capture basin].** [3,4] Given a dynamical system $S$, two sets $\mathcal{K}$ (called the environment) and $\mathcal{C}$ (called the target) satisfying $\mathcal{C} \subset \mathcal{K}$, the capture basin $\text{Capt}_S(\mathcal{K}, \mathcal{C})$ is the subset of states of $\mathcal{K}$ from which there exists at least one evolution solution of $S$ reaching the target $\mathcal{C}$ in finite time while remaining in $\mathcal{K}$.

The capture basin $\text{Capt}_S(\mathcal{K}, \mathcal{C})$ can be numerically computed using the capture basin algorithm [7,17].

**Definition 4 [Auxiliary dynamical system].** The auxiliary system (3) associated to the Moskowitz HJ PDE is defined by:

$$S := \begin{cases} \tau'(t) = -1 \\ x'(t) = u(t) \\ y'(t) = -\varphi^*(u(t)) \end{cases} \qquad (3)$$

where $u(t) \in \text{Dom}(\varphi^*)$, and where the function $\varphi^*$ is defined by:

$$\varphi^*(u) := \sup_{p \in \text{Dom}(\psi)} [p \cdot u + \psi(p)] \qquad (4)$$

**Definition 5 [Epigraphical target].** For any function $\mathbf{f}(t, x)$ defined on a subset $\mathcal{F}$ of $\mathbb{R}_+ \times X$, the associated target function $\mathbf{c}$ is defined as follows:

$$\mathbf{c}(t, x) := \begin{cases} \mathbf{f}(t, x) & \text{if } (t, x) \in \mathcal{F} \\ +\infty & \text{otherwise} \end{cases}$$

The target $\mathcal{C}$ corresponding to the function $\mathbf{c}(\cdot, \cdot)$ is defined as follows:

$$\mathcal{C} := \mathcal{E}\pi(\mathbf{c}) \qquad (5)$$

**Definition 6 [Viability episolution].** Let us consider $\mathcal{K} := \mathbb{R}_+ \times [\xi, \chi] \times \mathbb{R}$ and $\mathcal{C}$ defined by (5). The viability episolution $\mathbf{M}$ is defined by

$$\mathbf{M}(t, x) := \inf_{(t,x,y) \in \text{Capt}_S(\mathcal{K}, \mathcal{C})} y \qquad (6)$$

**Proposition 1 [Barron-Jensen/Frankowska property].** [5] Given an environment $\mathcal{K}$ and a target $\mathcal{C}$ defined by (5), the corresponding viability episolution $\mathbf{M}(t, x)$ is a Barron-Jensen/Frankowska (BJ/F) solution to the Hamilton-Jacobi PDE (2).

**Proof.** See [5] for a proof of this property for the CVN function $\mathbf{N}$, and operate the variable change $\mathbf{M}(t, x) = -\mathbf{N}(t, x) + \int_0^t \psi(v(u))du$. ■
### 3 Properties of the Viability Episolution

**Proposition 2 [Generalized Lax Hopf formula].** The viability episolution defined by equation (6) can be expressed as:

$$ \mathbf{M}(t, x) = \inf_{(u,T) \in \text{Dom}(\varphi^*) \times \mathbb{R}_+} [\mathbf{c}(t - T, x + Tu) + T\varphi^*(u)] \quad (7) $$

It is well known [3,4,5] that for a given environment $\mathcal{K}$, the capture basin of a finite union of targets is the union of the capture basins of these targets:

$$ \mathrm{Capt}_S \left( \mathcal{K}, \bigcup_{i \in I} \mathcal{C}_i \right) = \bigcup_{i \in I} \mathrm{Capt}_S(\mathcal{K}, \mathcal{C}_i) \quad (8) $$

where $I$ is a finite set. This property can be translated in epigraphical form:

**Proposition 3 [Inf-morphism property].** Let $\mathbf{c}_i$ ($i$ belongs to a finite set $I$) be a family of functions whose epigraphs are the targets $C_i$. Since the epigraph of the infimum of the functions $\mathbf{c}_i$ is the union of the epigraphs of the functions $\mathbf{c}_i$, the target $C := \bigcup_{i \in I} C_i$ is the epigraph of the function $\mathbf{c} := \inf_{i \in I} \mathbf{c}_i$. We thus have the following property:

$$ \forall t \ge 0, x \in X, \quad \mathbf{M}_c(t, x) = \inf_{i \in I} \mathbf{M}_{c_i}(t, x) \quad (9) $$

where $\mathbf{M}_c$ and $\mathbf{M}_{c_i}$ are the episolutions (6) associated to the targets $C$ and $C_i$ respectively.

The inf-morphism property enables us to compute the Moskowitz function using the concept of *hybrid components*.

**Definition 7 [Components of the Moskowitz function].** The component $\mathbf{M}_c$ associated to a target function $\mathbf{c}$ is defined by:

$$ \mathbf{M}_c(t, x) := \inf_{(t,x,y) \in \mathrm{Capt}_S(\mathcal{K}, \mathcal{E}_{\mathrm{pi}}(\mathbf{c}))} y \quad (10) $$

**Definition 8 [Hybrid, initial and boundary components].** Let $\mathcal{D}$ be a given set. We consider through the article three functions $\overline{\mathbf{M}}(\cdot, \cdot)$, $\mathbf{M}_0(\cdot, \cdot)$ and $\gamma(\cdot, \cdot)$ satisfying the following properties:

$$ \overline{\mathbf{M}}(t, x) = \begin{cases} \mathbf{M}_{\text{hybrid}}(t, x) & (\text{given}) \quad \text{for } (t, x) \in \mathcal{D} \\ +\infty & \text{for } (t, x) \notin \mathcal{D} \end{cases} $$

$$ \mathbf{M}_0(t, x) := \begin{cases} \mathbf{M}_{\text{initial}}(x) & (\text{given}) \quad \text{for } t=0 \text{ and } x \in [\xi, \chi] \\ +\infty & \forall t \neq 0 \text{ or } \forall x \notin [\xi, \chi] \end{cases} $$

$$ \gamma(t, x) := \begin{cases} \mathbf{M}_{\text{boundary}}(t) & (\text{given}) \quad \text{for } x = \xi \text{ and } t \ge 0 \\ +\infty & \forall x \neq \xi \text{ or } \forall t < 0 \end{cases} $$
The hybrid component $\mathbf{M}_{\overline{\mathbf{M}}}$, initial condition component $\mathbf{M}_{\mathbf{M}_0}$ and boundary condition component $\mathbf{M}_{\gamma}$ respectively associated to $\overline{\mathbf{M}}$, $\mathbf{M}_0$, and $\gamma$ are defined by:

$$ \left\{ \begin{array}{l} \mathbf{M}_{\overline{\mathbf{M}}}(t, x) := \inf_{(t,x,y) \in \text{Capt}_S(\mathcal{K}, \varepsilon_{\text{pi}}(\overline{\mathbf{M}}))} y \\ \mathbf{M}_{\mathbf{M}_0}(t, x) := \inf_{(t,x,y) \in \text{Capt}_S(\mathcal{K}, \varepsilon_{\text{pi}}(\mathbf{M}_0))} y \\ \mathbf{M}_{\gamma}(t, x) := \inf_{(t,x,y) \in \text{Capt}_S(\mathcal{K}, \varepsilon_{\text{pi}}(\gamma))} y \end{array} \right. \qquad (11) $$

**Proposition 4 [Domain of influence].** The domain of $\mathbf{M}_c$, also called domain of influence of component $c$, is defined by the following formula:

$$ \text{Dom}(\mathbf{M}_c) = \bigcup_{(t,x) \in \text{Dom}(c)} \left( \bigcup_{T \in \mathbb{R}_+} \{t+T\} \times [x - \nu^{\sharp}T, x + \nu^{\flat}T] \right) \quad (12) $$

**Proof.** The generalized Lax Hopf formula (2) implies that

$$ \text{Dom}(\mathbf{M}_c) = \{(t, x) \in \mathbb{R}_+ \times X \text{ such that } \exists(T, u) \in \mathbb{R}_+ \times \text{Dom}(\varphi^*) \\ \text{and } (t - T, x + Tu) \in \text{Dom}(c)\} $$

Equation (12) is obtained from the previous formula, observing that $u$ ranges in $\text{Dom}(\varphi^*) := [-\nu^{\flat}, \nu^{\sharp}]$. ■

# 4 The Mixed Initial-Boundary Conditions Problem

**Definition 9 [Mixed initial boundary condition problem].** The mixed initial boundary condition problem is defined as:

$$ \left\{ \begin{array}{l} \displaystyle \frac{\partial \mathbf{M}(t,x)}{\partial t} - \psi \left( -\frac{\partial \mathbf{M}(t,x)}{\partial x} \right) = 0 \quad \forall (t,x) \in \mathbb{R}_+^* \times \mathcal{N}, \chi[\text{ s.t. } \mathbf{M} \text{ is differentiable}] \\ \mathbf{M}(0,x) = \mathbf{M}_0(0,x) \qquad \forall x \in X \\ \mathbf{M}(t, \xi) = \gamma(t, \xi) \qquad \forall t \in \mathbb{R}_+ \end{array} \right. \qquad (13) $$

**Remark.** The first line of equation (13) has to be understood in the BJ/F sense. □

<figure><img src="image_4.png" /></figure>

The initial and boundary condition components of the Moskowitz function can be computed as follows:

$$ \begin{aligned} \mathbf{M}_{\mathbf{M}_0}(t, x) &= \inf_{u \in \text{Dom}(\varphi^*)} (\mathbf{M}_0(0, x + tu) + t\varphi^*(u)) \\ \mathbf{M}_{\gamma}(t, x) &= \inf_{u \in \text{Dom}(\varphi^*)} \left( \gamma \left( t - \frac{\xi-x}{u}, \xi \right) + \frac{\xi-x}{u} \varphi^*(u) \right) \end{aligned} \qquad (14) $$

The initial and boundary condition components satisfy the following properties:

$$ \left\{ \begin{array}{l} \mathbf{M}_{\mathbf{M}_0}(0, x) = \mathbf{M}_0(0, x) \quad \forall x \in X \\ \mathbf{M}_{\gamma}(t, \xi) = \gamma(t, \xi) \quad \forall t \in \mathbb{R}_+ \end{array} \right. \qquad (15) $$
provided that the growth condition $\forall \tau \in [0, t]$, $0 \le \gamma(t, \xi) \le \gamma(t - \tau, \xi) + \tau\varphi^*(0)$ is satisfied. We assume in the rest of the article that this condition and the following consistency condition are satisfied:

$$ \inf_{u \in \text{Dom}(\varphi^*)} (\mathbf{M}_0(0, \xi + tu) + t\varphi^*(u)) \ge \gamma(t, \xi) \quad \forall t \in \mathbb{R}_+ \quad (16) $$

**Definition 10** [Mixed initial-boundary conditions target]. In the specific case of mixed initial-boundary conditions, we define the target function $c(t, x)$ by $c(t, x) = \min(\mathbf{M}_0(t, x), \gamma(t, x))$

**Theorem 4.1** [Solution to the mixed initial-boundary conditions problem]. Given this definition, we can express the solution to the mixed initial-boundary conditions problem (13) as:

$$ \mathbf{M}(t, x) = \min(\mathbf{M}_{\mathbf{M}_0}(t, x), \mathbf{M}_{\gamma}(t, x)) \quad (17) $$

The solution $\mathbf{M}$ to the mixed initial-boundary conditions problem is thus expressed in terms of its initial condition component $\mathbf{M}_{\mathbf{M}_0}$ and its boundary condition component $\mathbf{M}_{\gamma}$.

**Proof.** The function $\mathbf{M}(\cdot, \cdot)$ defined by equation (17) is a BJ/F solution to the Moskowitz HJ PDE. Equation (15) in conjunction with consistency condition (16) also implies the following properties:

$$ \left\{ \begin{array}{l} \mathbf{M}(0, x) = \mathbf{M}_0(0, x) \quad \forall x \in X \\ \mathbf{M}(t, \xi) = \gamma(t, \xi) \quad \forall t \in \mathbb{R}_+ \end{array} \right. \quad (18) $$

$\mathbf{M}(t, x)$ is thus solution to problem (13). ■

# 5 Hybrid Components in the Moskowitz Function

**Definition 11** [Hybrid problem]. Let a $C^1$ function $\bar{\mathbf{M}}(\cdot, \cdot)$ be defined on a given set $\mathcal{D} \subset \mathbb{R}_+ \times X$. Our objective is to compute the function $\mathbf{M}(\cdot, \cdot)$, solution to the following hybrid problem:

$$ \left\{ \begin{array}{ll} \displaystyle \frac{\partial \mathbf{M}(t,x)}{\partial t} - \psi \left( \frac{\partial \mathbf{M}(t,x)}{\partial x} \right) = 0 & \forall (t,x) \in \mathbb{R}_+^* \times \mathcal{D}, \chi[\setminus \mathcal{D} \text{ s. t. } \mathbf{M} \text{ is differentiable} \\ \mathbf{M}(0,x) = \mathbf{M}_0(0,x) & \forall x \in X \\ \mathbf{M}(t, \xi) = \gamma(t, \xi) & \forall t \in \mathbb{R}_+ \\ \mathbf{M}(t, x) = \bar{\mathbf{M}}(t, x) & \forall (t,x) \in \mathcal{D} \end{array} \right. \quad (19) $$

The function $\mathbf{M}(t, x)$ is solution to the HJ PDE when $(t, x) \in \mathbb{R}_+^* \times \mathcal{D}$, $\chi[\setminus \mathcal{D}$, and satisfies the set of conditions (19).

The hybrid problem (19) contains an additional hybrid constraint when compared with the mixed initial-boundary conditions problem. Since the mixed initial-boundary is well posed if the consistency condition (16) is satisfied, the
hybrid problem is a priori overconstrained. We seek necessary and sufficient conditions on $\overline{\mathbf{M}}$ for the following inequality to hold:

$$ \mathbf{M}_{\overline{\mathbf{M}}}(t, x) \geq \overline{\mathbf{M}}(t, x) \quad \forall (t, x) \in \mathcal{D} \qquad (20) $$

Note that the converse inequality is always satisfied by definition of the capture basin since $\mathcal{C} \subseteq \text{Capt}_S(\mathcal{K}, \mathcal{C})$. When inequality (20) is satisfied, we have $\mathbf{M}_{\overline{\mathbf{M}}}(t, x) = \overline{\mathbf{M}}(t, x) \quad \forall (t, x) \in \mathcal{D}$. This condition, similar to conditions (15), is required for the construction of the solution to the hybrid problem. Using the generalized Lax-Hopf formula, we can rewrite condition (20) as:

$$ \inf_{(u,T) \in \text{Dom}(\varphi^*) \times \mathbb{R}_+} \left[ \overline{\mathbf{M}}(t-T, x+Tu) + T\varphi^*(u) \right] \geq \overline{\mathbf{M}}(t, x) \quad \forall (t, x) \in \mathcal{D} \qquad (21) $$

Since equation (21) involves a minimization over two variables, it is difficult in general to assess a priori that a $C^1$ function $\overline{\mathbf{M}}$ will satisfy this condition.

**Proposition 5 [Necessary condition for equation (21) to be satisfied].**
Since $\overline{\mathbf{M}}(\cdot, \cdot)$ is differentiable in a neighborhood of $(t, x)$, condition (21) implies the following necessary condition:

$$ \frac{\partial \overline{\mathbf{M}}(t, x)}{\partial t} \leq \psi \left( -\frac{\partial \overline{\mathbf{M}}(t, x)}{\partial x} \right) \qquad (22) $$

**Proof.** Using the generalized Lax Hopf formula, one can rewrite condition (21) as:
$$ \inf_{(u,T) \in \text{Dom}(\varphi^*) \times \mathbb{R}_+} \left[ \overline{\mathbf{M}}(t-T, x+Tu) - \overline{\mathbf{M}}(t, x) + T\varphi^*(u) \right] \geq 0 \quad \forall (t, x) \in \mathcal{D} \qquad (23) $$

which in turn implies $\forall (t, x) \in \mathcal{D}$ and $\forall (T, u) \in \mathbb{R}_+ \times \text{Dom}(\varphi^*)$

$$ \left[ \overline{\mathbf{M}}(t-T, x+Tu) - \overline{\mathbf{M}}(t, x) + T\varphi^*(u) \right] \geq 0 \qquad (24) $$

Dividing equation (24) by $T > 0$, and taking the limit of the resulting expression when $T \to 0$ enables us to write:

$$ \inf_{u \in \text{Dom}(\varphi^*)} \left[ -\frac{\partial \overline{\mathbf{M}}(t, x)}{\partial t} + u \frac{\partial \overline{\mathbf{M}}(t, x)}{\partial x} + \varphi^*(u) \right] \geq 0 \quad \forall (t, x) \in \mathcal{D} \qquad (25) $$

By definition of the inverse Fenchel transform, we have $\psi(\rho) = \inf_{u \in \text{Dom}(\varphi^*)} (-\rho u + \varphi^*(u))$. Equation (25) thus implies $-\frac{\partial \overline{\mathbf{M}}(t, x)}{\partial t} + \psi(-\frac{\partial \overline{\mathbf{M}}(t, x)}{\partial x}) \geq 0$, which in turn implies formula (22).

**Remark.** In terms of traffic, this necessary condition states that it is not possible to set a traffic state function $\overline{\mathbf{M}}$ which prescribes a flow $q$ higher than the equilibrium flow $\psi(\rho)$ associated to the prescribed density $\rho$. □
**Proposition 6** [Sufficient condition for equation (21) to be satisfied].
If $\mathcal{D}$ is convex and condition (22) is valid for all $(t, x) \in \text{Dom}(\overline{\mathbf{M}})$ such that $\overline{\mathbf{M}}$ is differentiable, then condition (21) is satisfied.

**Proof.** Assume that $\mathcal{D}$ is convex and $\overline{\mathbf{M}}(\cdot, \cdot)$ is $C^1$, and satisfies equation (22). Condition (21) can be written as:

$$ \inf_{(u,T) \in \text{Dom}(\varphi^*) \times \mathbb{R}_+} \left[ \overline{\mathbf{M}}(t-T, x+Tu) - \overline{\mathbf{M}}(t,x) + T\varphi^*(u) \right] \geq 0 \quad \forall (t,x) \in \mathcal{D} \quad (26) $$

Since $\mathcal{D}$ is convex, the set $\{(t - \tau, x + \tau u), \tau \in [0, T]\}$ is included in $\mathcal{D}$, provided that $(t - T, x + Tu)$ belongs to $\mathcal{D}$. Since $\overline{\mathbf{M}}(\cdot, \cdot)$ is integrable, we can rewrite condition (26) as: $\forall (t, x) \in \mathcal{D}$,

$$ \inf_{(u,T) \in \text{Dom}(\varphi^*) \times \mathbb{R}_+} \left[ \int_0^T \left( -\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial t} + u \frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial x} + \varphi^*(u) \right) d\tau \right] \geq 0 \quad (27) $$

We now prove that condition (22) implies condition (27). Indeed, condition (22) implies that $\forall \tau \in [0, T]$, $\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial t} \le \psi\left(-\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial x}\right)$. Thus

$$ -\int_{0}^{T} \psi\left(-\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial x}\right) d\tau \le \int_{0}^{T} -\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial t} d\tau \quad (28) $$

Since $\psi(\cdot)$ is concave and lower semicontinuous, Jensen inequality implies:

$$ -\psi\left(\frac{1}{T}\int_{0}^{T} -\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial x}\right) d\tau \le -\frac{1}{T}\int_{0}^{T} \psi\left(-\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial x}\right) d\tau \quad (29) $$

We set $f(\cdot, \cdot)$ as $f(T, u) := \frac{1}{T} \int_0^T -\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial x} d\tau$. Equation (22) implicitly implies that $\forall (T, u) \in \mathbb{R}_+ \times \text{Dom}(\varphi^*)$, $-\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial x} \in \text{Dom}(\psi)$ and thus, by integration, that $f(T, u) \in \text{Dom}(\psi)$. We can write the general inequality $\psi(\rho) \le -\rho u + \varphi^*(u)$ as:

$$ \forall (u, T) \in \text{Dom}(\varphi^*) \times \mathbb{R}_+, \quad 0 \le -\psi(f(T, u)) + u f(T, u) + \varphi^*(u) \quad (30) $$

Equations (28) and (29) imply:

$$ -\psi(f(T, u)) + u f(T, u) \le \int_{0}^{T} \left( -\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial t} + u \frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial x} \right) d\tau \quad (31) $$

Since $u$ is constant, equation (30) implies:

$$ 0 \le \int_{0}^{T} \left( -\frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial t} + u \frac{\partial \overline{\mathbf{M}}(t-\tau, x+\tau u)}{\partial x} + \varphi^*(u) \right) d\tau \quad (32) $$

Equation (27) is finally obtained from equation (32) by taking the infimum over the parameters $(T, u) \in \mathbb{R}_+ \times \text{Dom}(\varphi^*)$, and by observing that equation (32) is valid for all $(t, x) \in \mathcal{D}$. ■
**Definition 12 [Construction of the hybrid solutions].** In the specific case of mixed initial-boundary-hybrid conditions, we define the target function $c(t, x)$ as follows:

$$c(t, x) = \min (\mathbf{M}_0(t, x), \gamma(t, x), \overline{\mathbf{M}}(t, x)) \quad (33)$$

The function defined by equation

$$\mathbf{M}(t, x) = \min (\mathbf{M}_{\mathbf{M}_0}(t, x), \mathbf{M}_{\gamma}(t, x), \mathbf{M}_{\overline{\mathbf{M}}}(t, x)) \quad (34)$$

is associated to the target $\mathcal{C} := \mathcal{E}\pi(\mathbf{M}_0) \cup \mathcal{E}\pi(\gamma) \cup \mathcal{E}\pi(\overline{\mathbf{M}})$. This function is thus a solution to the Moskowitz HJ PDE in the BJ/F sense.

**Proposition 7.** We assume that $\mathcal{D}$ is a convex subset belonging to the interior of $\mathbb{R}_+ \times X$, and that condition (22) is valid for all $(t, x) \in \text{Dom}(\overline{\mathbf{M}})$. The function $\mathbf{M}$ defined by equation (34) satisfies conditions (19) if and only if the following set of conditions is satisfied:

$$\left\{ \begin{array}{ll} \mathbf{M}_{\mathbf{M}_0}(t, x) \ge \overline{\mathbf{M}}(t, x) & \text{and } \mathbf{M}_{\gamma}(t, x) \ge \overline{\mathbf{M}}(t, x) & \forall (t, x) \in \mathcal{D} \\ \mathbf{M}_{\overline{\mathbf{M}}}(t, \xi) \ge \gamma(t, \xi) & \text{and } \mathbf{M}_{\mathbf{M}_0}(t, \xi) \ge \gamma(t, \xi) & \forall t \in \mathbb{R}_+ \end{array} \right. \quad (35)$$

**Proof.** Equation (15) implies that the function $\mathbf{M}$ defined by equation (34) satisfies:

$$\left\{ \begin{array}{ll} \mathbf{M}(0, x) = \min (\mathbf{M}_0(0, x), \mathbf{M}_{\gamma}(0, x), \mathbf{M}_{\overline{\mathbf{M}}}(0, x)) & \forall x \in X \\ \mathbf{M}(t, \xi) = \min (\gamma(t, \xi), \mathbf{M}_{\mathbf{M}_0}(t, \xi), \mathbf{M}_{\overline{\mathbf{M}}}(0, x)) & \forall t \in \mathbb{R}_+ \end{array} \right. \quad (36)$$

Note that we always have $\forall x \in X$, $\mathbf{M}_{\overline{\mathbf{M}}}(0, x) \ge \mathbf{M}_0(0, x)$ and $\mathbf{M}_{\gamma}(0, x) \ge \mathbf{M}_0(0, x)$, since $\mathbf{M}_{\gamma}(0, x) = +\infty$ if $x \ne 0$ and $\mathbf{M}_{\overline{\mathbf{M}}}(0, x) = +\infty$ if $\mathcal{D} \subset \text{Int}(\mathbb{R}_+ \times X)$. This consideration and equation (36) imply that $\mathbf{M}$ is solution to equation (19) if and only if equation (35),(2) is satisfied.

The inclusion $\mathcal{C} \subseteq \text{Capt}_S(\mathcal{K}, \mathcal{C})$ (valid for any capture basin) also implies $\forall (t, x) \in \mathcal{D}, \mathbf{M}(t, x) \le \overline{\mathbf{M}}(t, x)$. Hence, $\mathbf{M}$ satisfies equation (19) if and only if equation (35) is satisfied. ■

# 6 Applications

We now illustrate the previous results with three numerical applications computed using the generalized Lax Hopf formula, or the viability algorithm [7].

## 6.1 Switching Solutions of the LWR PDE

In this section, we compute the solution to the LWR PDE (1) with the triangular flux function as the solution to a switched PDE problem. The triangular flux function $\psi$ is defined by:

$$\psi(\rho) = \begin{cases} \nu^{\flat}\rho & \text{if } \rho \le \rho_c \\ \nu^{\sharp}(\omega - \rho) & \text{if } \rho \ge \rho_c \end{cases} \quad (37)$$
where $\omega = 4$ is the jam density, $\nu^b = 3$ is the free flow speed, $\nu^\# = 1$ is the congestion speed, and $\rho_c = 1$ is the critical density. The two corresponding PDEs are associated to the two modes of propagation of traffic (free flow or congestion):

$$ \begin{cases} \frac{\partial \rho}{\partial t} + \nu^b \frac{\partial \rho}{\partial x} = 0 & \rho \in [0, \rho_c] \quad (\text{free flow}) \\ \frac{\partial \rho}{\partial t} - \nu^\# \frac{\partial \rho}{\partial x} = 0 & \rho \in [\rho_c, \omega] \quad (\text{congestion}) \end{cases} $$

where $\nu^b$ is the free flow speed and $\nu^\#$ the speed of back propagating waves. In Figure 2, we show a numerical example of computation (using the generalized Lax Hopf formula (7)) of the partition of the space time domain on which the free flow and the congested PDE apply, for given initial and boundary conditions. The techniques developed earlier are thus illustrated in this Figure, in which one can see the existence of three modes: highway in free flow (white), highway at maximum capacity (gray) and highway congested (black).

<figure><img src="image_5.png" /><figcaption>Fig. 2. Illustration of space and time switched PDEs. The solution to the corresponding LWR PDE (1) with triangular flux function (37) leads to three modes: two hybrid components PDE 1 and PDE 2, and a degenerate mode.</figcaption></figure>

## 6.2 Hybrid Solutions Associated to a Speed Control Policy

We now illustrate the previous results with a variable speed control problem. Variable speed limits are speed limits that are changed by highway operators based on traffic or weather conditions. These speed limits are set for safety or traffic flow management purposes. In this section, we compute the effects of a speed limit set on domain $\mathcal{D} \subset \mathbb{R}_+ \times X$. We consider the following mixed initial-boundary conditions problem:

$$ M_0(0, x) = \begin{cases} -0.7x & \text{if } 0 \le x \le 5 \\ -0.4x - 5.5 & \text{if } 5 \le x \le 14 \\ 41.9 - 3.5x & \text{if } 14 \le x \le 20 \end{cases} $$

$$ \gamma(t, \xi) = \begin{cases} t & \text{if } 0 \le t \le 4 \\ 2t - 4 & \text{if } 4 \le t \le 8 \\ 1.5t & \text{if } 8 \le t \le 10 \end{cases} $$

We use the triangular flux function defined in the previous section. This set of initial and boundary conditions satisfy condition (16). We now augment this problem using a hybrid component corresponding to a speed control policy. The hybrid solution satisfies the HJ PDE outside of a domain $\mathcal{D}$ defined by
$$ \mathcal{D} = \bigcup_{t \in [2,6]} [1 + v(t-2), 7 + v(t-2)] \qquad (38) $$

where $v = 1.3$ is the limited speed at which all the vehicles in set $\mathcal{D}$ are running (by effect of the speed control policy). Since the trajectories of the vehicles are the level sets of $\overline{M}$, we must define $\overline{M}(t, x)$ as:

$$ \forall (t, x) \in \mathcal{D}, \quad \overline{M}(t, x) := M_{\text{MIB}}(2, x - v(t-2)) \qquad (39) $$

where $M_{\text{MIB}}$ is the solution to the associated mixed initial boundary conditions problem.

We compute the solution to the mixed initial boundary conditions problem, as well as the solution to the hybrid problem. The resulting surface for $M(t, x)$ is shown in Figure 3.

<figure><img src="image_6.png" /><figcaption>**Fig. 3.** Solution of the Moskowitz HJ PDE. **Left:** Moskowitz function $M(t, x)$ corresponding to the mixed initial boundary conditions problem. **Right:** Moskowitz function $M(t, x)$ solution to the hybrid problem corresponding to a speed control policy for vehicles located in the set $\mathcal{D}$.</figcaption></figure>

The effects of the speed control policy can also be seen in Figure 4, which shows the level sets of the Moskowitz functions associated to the mixed initial boundary condition problem (left) and to the hybrid problem (right). We recall that the integer-level sets of the Moskowitz function correspond by definition to the trajectories of the vehicles.

## 6.3 Data Assimilation Using Hybrid Components

In this section, we use NGSIM data which contains video extracted trajectories of all vehicles traversing a 0.4 mile section of highway I80 in Emeryville, CA. Since the trajectories of vehicles are the level sets of the Moskowitz function, we can use this data to illustrate the benefits of data assimilation using Lagrangian measurements measurements [11]. We first solve the problem (13) from NGSIM extracted $M_0(0, x)$ and $\gamma(t, \xi)$. This produces the prediction of shown in Figure 5 (left)<fnref n="1" /> and the corresponding error plot of Figure 6 (left). We then add

<footnote n="1">¹ Note that only a subset of the trajectories is shown on this plot for clarity.</footnote>
<figure><img src="image_7.png" /><figcaption>**Fig. 4.** Vehicle trajectories due to speed control policy. **Left:** trajectories corresponding to the mixed initial boundary conditions problem. **Right:** trajectories corresponding to the hybrid problem. Note the modification of speed of the vehicles in the set $\mathcal{D}$ (shaded), as well as the influence of the speed control policy on $\mathcal{D}$ on the upstream traffic.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Fig. 5.** Trajectories simulated using NGSIM data. **Left:** trajectories simulated using the initial and boundary conditions only and solving (13). **Right:** trajectories obtained by adding the hybrid component $\mathcal{D} = [70, 80] \times [650, 700]$ and solving the hybrid problem (19).</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Fig. 6.** Simulation using NGSIM data. **Left:** error in the predictions provided by the Moskowitz function simulated using the initial and boundary condition5s only and solving (13). **Right:** error obtained by adding the hybrid component $\mathcal{D} = [70, 80] \times [650, 700]$ and solving the hybrid problem (19). The color scale represents the magnitude of the absolute error. The black color represents a null error, whereas the white color represents an absolute error greater than 10 vehicles.</figcaption></figure>
a subset of data (hybrid component) depicted by the black square in Figure 5 (right), which leads to locally more accurate estimate of the trajectories, and a significant reduction of error in our predictions in the domain of influence of the hybrid component. This additional information is representative of information available from lagrangian measurements (for example using GPS equipped cell phones traveling onboard vehicles) in the near future [11]. As can be seen, the introduction of the hybrid component creates a discontinuity of M at the boundary of the domain of influence, which a “relabelling” of the vehicles due to additional information provided by the hybrid component. The corresponding reduction of error can be seen in Figure 6 (right). In Figures 5 and 6, the position is given in units of 2.4 ft (between posts 80 ft and 2000 ft), and the time is given in units of 1.2 s (this corresponds to the two first minutes of the NGSIM experiment).

# 7 Conclusion

This article presented a construction method for solutions of systems driven by switched scalar hyperbolic conservation laws, using a Hamilton-Jacobi formulation of the problem. Using an inf morphism property of the solutions to these equations, we constructed hybrid components for the problem, which can be assembled into a solution to the original problem. The solutions can be computed semi-analytically using a generalized Lax-Hopf formula which we presented, or using the capture basin algorithm. We derived sufficient conditions for the problem to be well posed. We illustrated the results with three numerical examples. In the first example, we showed how the method can be used to compute hybrid components of the LWR PDE with a triangular flux function. The second example showed how to compute the effects of control on traffic using the Hamilton-Jacobi equation. Finally, the last example used NGSIM data to demonstrate data assimilation capabilities of the method: “internal” boundary conditions which can be added to an original partial differential equation problem in the form of a hybrid component, which “corrects” the model where information was previously not available. This last application is the most promising, and is currently in implementation with Nokia to integrate Lagrangian (mobile) traffic measurements from GPS equipped cellular phones traveling onboard cars inside existing highway traffic monitoring systems such as the PeMS system in California.

**Acknowledgments.** The authors wish to thank Ryan Herring and Juan Carlos Herrera for computing the aggregated NGSIM data.

# References

1. Alvarez-Icaza, L., Munoz, L., Sun, X., Horowitz, R.: Adaptive observer for traffic density estimation. In: American Control Conference, Boston, MA, pp. 2705–2710 (June 2004)

2. Amin, S., Hante, F., Bayen, A.: On stability of switched linear hyperbolic conservation laws with reflecting boundaries. In: Egerstedt, M., Mishra, B. (eds.) HSCC 2008, LNCS, vol. 4981, pp. 602–605. Springer, Heidelberg (2008)
3. Aubin, J.-P.: Viability Theory. In: Systems and Control: Foundations and Applications, Birkhäuser, Boston, MA (1991)

4. Aubin, J.-P.: Viability kernels and capture basins of sets under differential inclusions. SIAM Journal of Control and Optimization 40, 853–881 (2001)

5. Aubin, J.-P., Bayen, A.M., Saint-Pierre, P.: Dirichlet problems for some Hamilton-Jacobi equations with inequality constraints. Technical report, Preprint di Matematica - n. 4, Scuola Normale Superiore, Pisa, Italy (May 2006)

6. Bayen, A.M., Raffard, R.L., Tomlin, C.: Network congestion alleviation using ad joint hybrid control: Application to highways. In: Lynch, N.A., Krogh, B.H. (eds.) HSCC 2000. LNCS, vol. 1790, pp. 95–110. Springer, Heidelberg (2000)

7. Cardaliaguet, P., Quincampoix, M., Saint-Pierre, P.: Set-valued numerical analysis for optimal control and differential games. In: Bardi, M., Raghavan, T.E.S., Parthasarathy, T. (eds.) Stochastic and Differential Games: Theory and Numerical Methods. Annals of the International Society of Dynamic Games, pp. 177–247. Birkhäuser, Basel (1999)

8. Daganzo, C.F.: A variational formulation of kinematic waves: basic theory and complex boundary conditions. Transporation Research B 39B(2), 187–196 (2005)

9. Daganzo, C.F.: On the variational theory of traffic flow: well-posedness, duality and applications. Networks and Heterogeneous Media 1, 601–619 (2006)

10. Hante, F., Leugering, G., Seidman, T.: Modeling and analysis of modal switching in networked transport systems (submitted, 2007)

11. Herrera, J.C., Bayen, A.M.: Traffic flow reconstruction using mobile sensors and loop detector data. In: The 87th Annual Meeting of TRB (to appear, 2007)

12. Koch, H., zuazua, E.: A hybrid system of PDE's arising in multi-structure interaction: coupling of wave equations in n and n-1 space dimensions. Recent Trends in Partial Differential Equations: UIMP-RSME Santaló Summer School, Recent Trends in Partial Differential Equations, Universidad Internacional Menéndez Pelayo, Santander, Spain, 4 (2006)

13. Lighthill, M.J., Whitham, G.B.: On kinematic waves. II. A theory of traffic flow on long crowded roads. Proceedings of the Royal Society of London 229(1178), 317–345 (1956)

14. Moskowitz, K.: Discussion of freeway level of service as influenced by volume and capacity characteristics. In: Drew, D.R., Keese, C.J., Highway Research Record, vol. 99, pp. 43–44 (1965)

15. Newell, G.F.: A simplified theory of kinematic waves in highway traffic. Transportation Research B 27B(4), 281–303 (1993)

16. Richards, P.I.: Shock waves on the highway. Operations Research 4(1), 42–51 (1956)

17. Saint-Pierre, P.: Approximation of the viability kernel. Applied Mathematics and Optimization 29, 187–209 (1994)

18. Seidman, T.I.: A convection/reaction/switching system. Nonlinear Analysis: Theory, Methods & Applications 67(7), 2060–2071 (2007)

19. Strub, I.S., Bayen, A.M.: Weak formulation of boundary conditions for scalar conservation laws 16, 733–748 (2006)

20. Tomlin, C., Lygeros, J., Sastry, S.: A game theoretic approach to controller design for hybrid systems. Proceedings of the IEEE 88(7), 949–970 (2000)