# A mean field approach to model flows of agents with path preferences over a
network

Fabio Bagagiolo1, Rosario Maggistro2, Raffaele Pesenti2 *This work was
partially supported by fund POR FSE 2014-2020 - CUP H76C18000250005 (codice
2120-19-11-2018).1Department of Mathematics, Università di Trento, Via
Sommarive, 14, 38123 Povo, Trento, Italy<EMAIL_ADDRESS>of Management, Università Ca’ Foscari Venezia, Fondamenta S. Giobbe, 873,
30121 Cannaregio, Venezia, Italy<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we address the problem of modeling the traffic flow of a
heritage city whose streets are represented by a network. We consider a mean
field approach where the standard forward backward system of equations is also
intertwined with a path preferences dynamics. The path preferences are
influenced by the congestion status on the whole network as well as the
possible hassle of being forced to run during the tour. We prove the existence
of a mean field equilibrium as a fixed point, over a suitable set of time-
varying distributions, of a map obtained as a limit of a sequence of
approximating functions. Then, a bi-level optimization problem is formulated
for an external controller who aims to induce a specific mean field
equilibrium.

###### Index Terms:

Traffic flow optimal control; mean field games; path preference dynamics;
dynamical flow networks.

##  I INTRODUCTION

In the recent years, the continuous growth of traffic flow and the resulting
overcrowding have led some cities to seek solutions to manage this phenomenon.
The crowd motion modeling and the study of flow dynamics have become in the
last decades two of the main targets of the transportation research community.
Different modeling approaches have been proposed which can generally be
classified into two categories: microscopic models and macroscopic models. The
former include the cellular automaton model, the social force model, and the
lattice gas model (see e.g., [1]–[3]), and are particularly well suited for
use with small crowds. Macroscopic models, in contrast, focus on the overall
behavior of pedestrian flows and are more applicable to investigations of
extremely large crowds, especially when examining aspects of motion in which
individual differences are less important [4]–[6]. In this paper, starting
from the results in [7]–[8], we introduce a Mean Field (MF) approach to
modeling and analytically studying the flow of daily agents along the street
of a heritage city. Mean field games (MFG) theory goes back to the seminal
work by Lasry-Lions [9] (see also [10]). This theory includes methods and
techniques to study differential games with a large population of rational
players and it is based on the assumption that the population influences
individuals’ strategies through mean field parameters. Several application
domains such as economic, physics, biology and network engineering accommodate
MFG theoretical models (see [11]–[13]). In particular, models to study of
dynamics on networks and/or pedestrian movement can be found for example in
[14]–[16]. In this paper, beside the usual framing of mean field games (which
is typically defined by the pair made of Hamilton-Jacobi-Bellman and transport
equations), we consider the agent’s path preferences dynamics. In particular,
we assume that it evolves following a perturbed best response to global
information about the congestion status of the whole network and to the
control vector. Moreover, this path preferences dynamics evolves at a slow
time scale as compared to the physical dynamics. We apply these arguments to
the possible paths considering a network topology as in Figure 1.

Our main result shows the existence of a MF equilibrium for our framework.
This equilibrium is a time-varying distribution of agents,
$\widetilde{\rho}(t)$ for $t\in[0,T]$, on the network. Distribution
$\widetilde{\rho}(t)$, when plugged in the cost to minimize, generates an
optimal control $\widetilde{u}(t)$, for any agent starting at the origin $o$
which, in turn, yields the path preference $z(t)$ providing the time-varying
distribution $\widetilde{\rho}$. We also introduce a possible bi-level
optimization problem for an external controller who aims to force the
equilibrium to be as close as possible (in uniform topology) to a reference
value $\widetilde{\rho}$. We suppose that the external controller (the city
hall, for example) may act on the congestion functions choosing them among a
suitable set of admissible functions.

The rest of this paper is organized as follows. In Section II, we describe the
model and state the hypotheses used in the paper. In Section III, we claim the
existence of a MF equilibrium (due to the space limitation, we only include
the sketches of the proofs) and, in Section IV, we define a bi-level
optimization problem. In Section V, we draw conclusions and suggests future
works.

##  II MODEL DESCRIPTION

###  II-A Network characteristics

We model the topology of the network as a directed multi-graph
$\mathcal{G=(V,E)}$, where $\mathcal{V}$ is a finite set of nodes and
$\mathcal{E}$ is a finite set of directed links. Each link
$e=(\nu_{e},\kappa_{e})$ in $\mathcal{E}$ is directed from its tail node
$\nu_{e}$ to its head node $\kappa_{e}\neq\nu_{e}$. An oriented path from a
node $v_{0}$ to a node $v_{r}$ is an ordered set of $r$ adjacent links
$p=(e_{1},e_{2},\ldots,e_{r})$ such that $\nu_{e_{1}}=v_{0}$,
$\kappa_{e_{r}}=v_{r}$, $v_{s}=\kappa_{e_{s}}=\nu_{e_{s+1}}$ for $1\leq s\leq
r-1$, and no node is visited twice, i.e., $v_{l}\neq v_{s}$ for all $0\leq
l<s\leq r$, except possibly for $v_{0}=v_{r}$, in which case the path is
referred to as a cycle. Moreover, let $\ell_{e}$ be the length of the link
$e\in\mathcal{E}$ and let $\ell^{p}=\sum_{e\in p}\ell_{e}$ be the length of
the path $p$. A node $v_{j}$ is said to be reachable from another node $v_{k}$
if there exists at least a path from $v_{k}$ to $v_{j}$.

We hold the following assumptions on the multi-graph $\mathcal{G}$ and on the
agents that move along its links.

###### Assumption 1

  1. 1.

$\mathcal{G}$ contains no cycles.

  2. 2.

$\mathcal{G}$ includes an origin node $o$, from which any node in
$\mathcal{V}$ can be reached, and a destination node $d\neq o$, which is
reachable from any node in $\mathcal{V}$, $o$ included.

  3. 3.

Agents arrive at $o$ in the morning and desire to leave from $d$ in the
afternoon.

We denote $\Gamma$ as the set of all the paths from $o$ to $d$. In particular,
in this paper, we consider a graph $\mathcal{G}$ on which agents have only
three possible paths to reach the destination $d$ starting from the origin $o$
(see Figure 1).

Figure 1:  The graph topology used in the paper.

In this case, the set of path is $\Gamma=\\{p_{1},p_{2},p_{3}\\}$, where
$p_{1}=(e_{1},e_{4})$, $p_{2}=~{}(e_{2},e_{5})$, $p_{3}=(e_{1},e_{3},e_{5})$.
We denote the corresponding link-path incidence matrix by
$A\in\\{0,1\\}^{|\mathcal{E}|\times|\Gamma|}$ with entries

$A_{ep}=\begin{cases}1&\text{if}\quad e\in p,\\\
0&\text{otherwise}.\end{cases}$

For every link $e\in\mathcal{E}$ and time instant $t\in[0,T]$, we denote the
current mass and flow by $\rho_{e}(t)$ and $f_{e}(t)$, respectively, defined
as

$\rho_{e}:[0,T]\to[0,\rho_{\max}],\quad f_{e}:[0,T]\to[0,C_{e}],$

with $T>0$ the final horizon, i.e., the time by which every agent has to reach
the destination $d$, and $C_{e}$ is the maximum flow capacity. Moreover let

$\rho(t):=\\{\rho_{e}(t):e\in\mathcal{E}\\},\quad
f(t):=\\{f_{e}(t):e\in\mathcal{E}\\}$ (1)

be the vectors of masses and flows, respectively.

###  II-B Agents’ dynamics and costs

$\begin{cases}\dot{\theta}_{e}(s)=u^{e}(s),&s\in]t,T],\,\forall
e\in\mathcal{E},\\\ \theta_{e}(t)=0,&\forall t\in[0,T],\,\forall
e\in\mathcal{E},\end{cases}$ (2)

where $\theta_{e}(s)\in[0,\ell_{e}]$, being $\ell_{e}$ the length of the link.
Using this space-coordinates, $\theta_{e}(s)=0$ means that the agent is in
$\nu_{e}$, while $\theta_{e}(s)=\ell_{e}$ means that the agent is in
$\kappa_{e}$ and hence he is inside the link $e$ as long as
$0\leq\theta(s)\leq\ell_{e}$. Note that (2) describes the evolution of a
possible agent which is in $\nu_{e}$ at time $t$ independently of the fact
that he is present at $\nu_{e}$ at that time. By definition, $\theta_{e}(s)$
and $u^{e}(s)$ are equal to $NaN$ when the agent is not on link $e$.
Hereinafter, $NaN$ stands for not a number.

The control, $s\mapsto u^{e}(s)\in\mathbb{R}_{+}$, is measurable and locally
integrable, namely $u^{e}\in L^{1}_{loc}(t,T)\ \forall t$. For ease of
notation, from now on, we call $\mathcal{U}_{e}$ the set of these kind of
controls. There is no loss of optimality in assuming $u^{e}\geq 0$ as we
discuss later in Remark 1. The cost to be minimized by every agent crossing a
link $e$, takes into account: i) the possible hassle of running in the link
$e$ to reach $d$ on time; ii) the pain of being entrapped in highly congested
link; iii) the disappointment of not being able to reach $d$ by the final
horizon $T$. Such a cost can be analytically represented by

$\displaystyle J_{e}(t,u^{e})=$
$\displaystyle\int_{t}^{T}\chi_{\\{0\leq\theta_{e}(s)\leq\ell_{e}\\}}\left(\frac{(u^{e}(s))^{2}}{2}+\varphi_{e}(\rho_{e}(s))\right)\,ds$
$\displaystyle+$
$\displaystyle\chi_{\\{0\leq\theta_{e}(T)<\ell_{e}\\}}\alpha\sum_{j\in
p(e)}\ell_{j},$ (3)

where $p(e)$ is the shortest path from $\nu_{e}$ to $d$, $\alpha>0$ is a
constant parameter representing a cost per unit of length and $\chi$ is the
characteristic function. In (II-B), the quadratic term inside the integral
stands for cost i) while the other term stands for the congestion cost ii)
given by the function $\varphi_{e}:[0,\rho_{\max}]\to[0,+\infty[$; the last
addendum stands for cost iii).
We define, with a little abuse of terminology, as value functions the
following:

$\begin{split}V^{e}(t)=&\inf\limits_{\begin{subarray}{c}u^{e}\in\mathcal{U}_{e}\end{subarray}}\Big{\\{}J_{e}(t,u^{e})\\\
&+\min\limits_{\begin{subarray}{c}j\in\mathcal{E}:\nu_{j}=\kappa_{e}\\\ e,j\in
p,\,p\in\Gamma\end{subarray}}\\{V^{j}(\tau(t,u^{e}))\\}\Big{\\}}\quad\forall\
e\in\mathcal{E}\end{split}$ (4)
$V^{0}(t)=\min\limits_{\begin{subarray}{c}e\in\mathcal{E}:\nu_{e}=o\\\ e\in
p,\,p\in\Gamma\end{subarray}}\\{V^{e}(t)\\}.$ (5)

In (4), $\tau(t,u^{e})$ is the time at which an agent entering link $e$ at
time $t$ and choosing a control $u^{e}$ arrives in $\nu_{j}=\kappa_{e}$.
Note that the recursive definition of $V^{e}$ in (4) is not meaningless since
the absence of oriented cycles in the network $\mathcal{G}$ prevents self-
referring, that is it cannot occur that we define $V^{e}$ in terms of itself.
Also $V^{0}$ can be seen as associated to a fictitious link $e_{0}$ with null
length, such that $\nu_{e_{0}}=\kappa_{e_{0}}=o$, through which the flow
enters into the network. Finally, observe that when the distributional
evolution $t\to\rho_{e}(t)$, i.e. the mass of the agents on the link $e$, is
initially given then $V^{e}$ does not depend on $\rho_{e}$.

In this paper, we assume that the physical traffic flow $f$ consist of
indistinguishable homogeneous agents which enter in the network through the
origin node, travel through it on the different paths and finally exit from
the network through the destination node. The relative appeal of the different
paths to the agents is modelled by a time-varying nonnegative vector $z(t)$ in
the simplex

$\mathcal{S}_{\lambda(t)}=\left\\{z\in{\mathbb{R}}_{+}^{|\Gamma|}:\,1^{\prime}z(t)=\lambda(t)\right\\},$
(6)

where $\lambda(t):[0,T]\to[0,\rho_{\max}]$ is the throughput, i.e., the total
flow that goes through the network. We refer to the vector $z(t)$ as the
current aggregate path preference and let

$y^{z}(t)=Az(t)$ (7)

be the flow vector associated to it. The vector $z(t)$ is updated as agents
access global information about the current congestion status of the whole
network (that is embodied by the mass vector $\rho(t)$) and it is also
influenced by the vector $u(t)=\\{u^{e}(t)\neq NaN:e\in\mathcal{E}\\}$.
Hereinafter, $\mathcal{U}$ is the set of these vectors. Specifically, the cost
perceived by each agent, traversing a link $e\in\mathcal{E}$, is given by
(II-B). The cost that an agent expects to incur along a path $p$ is

$J^{p}(t,u)=\sum_{e\in\mathcal{E}}A_{ep}J_{e}(t_{e}^{p},u^{e})$

where $t_{e}^{p}(t)$, when $e\in p$, is the time instant in which an agent,
arriving in $t$ in the origin $o$ and following the path $p$, reaches
$\nu_{e}$. In particular $t_{e}^{p}(t)=t$ when $\nu_{e}=o$ with $e\in p$.
Clearly, $t_{e}^{p}$ depends on the controls $u^{j}$ for each link
$j\in\mathcal{E}$ that precedes the link $e$ along $p$. Arbitrarily, we also
set $t_{e}^{p}(t)=t$ when $e\notin p$. We denote with

$J(t,u)=\\{J^{p}(t,u):p\in\Gamma\\}$

the vector of costs on all the paths $p\in\Gamma$. Then, we assume that the
path preferences are updated at some rate $\eta>0$, according to a noisy best
response dynamics

$\dot{z}(t)=\eta(F^{(\beta)}(t,u)+Q^{(\beta)}(t,u)-z(t)),\ \ z(0)=z_{0},$ (8)

which takes into accounts both the value of $\lambda(t)$ and
$\dot{\lambda}(t)$. Generally in the literature (see e.g., [17], [18]) the
throughput $\lambda$ is constant, hence in the formulation of the noisy best
response dynamics $\dot{z}$ only the function $F^{(\beta)}$ appears. Here, as
$\lambda$ varies over time, we need to introduce also the function
$Q^{(\beta)}$ so that $z$ satisfies the constraint (6). In particular, for
every fixed noise parameter $\beta>0$ the function

$F^{(\beta)}:[0,T]\times\mathcal{U}\to{\mathbb{R}}^{|\Gamma|}_{+}$

is the perturbed best response defined as follows:

$F^{(\beta)}(t,u)=\frac{\lambda(t)\exp(-\beta(J(t,u)))}{1^{\prime}\exp(-\beta(J(t,u)))},$
(9)

which provides an idealized description of the behavior of agents whose
decisions are based on inexact information about the state of the network.
Moreover it is continuous on $[0,T]\ \ \forall u\in\mathcal{U}$ fixed. The
function $Q^{(\beta)}:[0,T]\times\mathcal{U}\to{\mathbb{R}}^{|\Gamma|}_{+}$ is
defined as

$Q^{(\beta)}(t,u)=\frac{\dot{\lambda}(t)\exp(-\beta(J(t,u)))}{1^{\prime}\exp(-\beta(J(t,u)))}.$
(10)

We assume that (10) has the same structure of (9) and it shows how the agents’
preferences $z$ are updated taking into account not only the value of
$\lambda(t)$ but also its time variation. For this reason we consider
$\dot{\lambda}(t)$ and we assign to it the same weight of $\lambda(t)$
selecting the same fixed noise parameter $\beta$. We now describe the local
decision function
$G:\mathcal{S}_{\lambda(t)}\to{\mathbb{R}}_{+}^{|\mathcal{E}|}$ characterizing
the fractions of agents choosing each outgoing link $e$ when traversing a non
destination node $v$. It is given by

$G_{e}(z)=\begin{cases}\displaystyle\frac{y_{e}^{z}}{\displaystyle\sum_{j\in\mathcal{E}:\nu_{j}=\nu_{e}}y_{j}^{z}}&\text{if}\quad{\displaystyle\sum_{j\in\mathcal{E}:\nu_{j}=\nu_{e}}y_{j}^{z}}>0\\\
\,\displaystyle\frac{1}{|\\{j\in\mathcal{E}:\nu_{j}=\nu_{e}\\}|}&\text{if}\quad{\displaystyle\sum_{j\in\mathcal{E}:\nu_{j}=\nu_{e}}y_{j}^{z}}=0\,,\end{cases}$
(11)

for each outgoing link $e$ in $\mathcal{E}$ and it is continuously
differentiable on $\mathcal{S}_{\lambda(t)}$. Equations (11) state that, at
every node $v\in\mathcal{V}$ the outflow is split proportionally to the flow
vector $y^{z}$, if there is flow $y^{z}$ passing through node $v$, otherwise,
the outflow is split uniformly among the immediately downstream links.

Now, for every non-destination node $v$ and outgoing link $e\in\mathcal{E}$
conservation of mass implies that

$\dot{\rho}(t)=H(f(t),z(t))\,,\qquad\rho(0)=\rho_{0}$ (12)

where
$H:\prod_{e\in\mathcal{E}}[0,C_{e}]\times\mathcal{S}_{\lambda}\to{\mathbb{R}}^{|\mathcal{E}|}$
is defined as

$H_{e}(f,z):=G_{e}(z)\bigg{(}\lambda\delta_{\nu_{e}}^{(o)}+\sum_{j:\kappa_{j}=\nu_{e}}f_{j}\bigg{)}-f_{e}\,,\
\forall\ e\in\mathcal{E},$ (13)

in which $\lambda(t)\delta_{\nu_{e}}^{(o)}$ accounts for the exogenous inflow
in the origin node $o$ and each component $f_{e}$ is

$f_{e}(t)=\rho_{e}(t)u^{e}(\rho)/\ell_{e},$ (14)

i.e., the flow on the link $e$ estimated by an agent entering in the very link
at time $t$.
Next we introduce the hypotheses that we will use to prove the existence of a
MF equilibrium:

(H1) the throughput $\lambda:[0,T]\to[0,+\infty[$ is $C^{1}([0,T])$ and
bounded;

(H2) $\rho(0)=0$;

(H3) $\varphi_{e}:[0,\rho_{\max}]\to[0,+\infty[$ are bounded, Lipschitz
continuous and do not depend on the state variable $\theta_{e}$.

Note that $\rho(0)=0$ in (H2) means that no one is around the city at $t=0$,
while (H3) implies that all agents in the same link at the same instant
equally suffer the same congestion.

###### Remark 1

Note that (H1) (H3) also imply that the control choice made by agents at the
beginning of each link does not change as long as the agent remains in the
same link, and it is constant in time. This is a feasible situation whenever
the movement of an agent on a link cannot be interfered by the movements of
agents that enter the same link after him. Note also that the same hypotheses
imply that is not convenient to go back along a link $e$, which in turn
implies that the optimal control $u^{e}$ is always non-negative.

###  II-C Value Functions

In order to define the MF equilibrium instead of coupling the two standard MF
equations, i.e., Hamilton-Jacobi-Bellman equations and mass conservation ones
(12), with the preferences equations (8) we write conditions equivalent in
terms of the value functions. An agent standing at $\nu_{e}$, and hence at
$\theta_{e}=0$, for $e\in\\{e_{4},e_{5}\\}$ at time $t$ has two possible
choices: either staying at $\nu_{e}$ indefinitely or moving to reach
$\kappa_{e}=d$ exactly at time $T$ (it is not optimal to reach $d$ before $T$
and wait there for a positive time length, see, e.g., [7]). Accordingly, the
controls are

$u^{e}_{1}=0,\qquad u^{e}_{2}=\frac{\ell_{e}}{T-t}.$ (15)

Hence, given the cost functional (II-B), we derive

$V^{e}(t)=\min\left\\{\alpha\ell_{e},\,\frac{1}{2}\frac{(\ell_{e})^{2}}{T-t}\right\\}+\int_{t}^{T}\varphi_{e}\,ds$
(16)

(note that we do not display the argument $\rho_{e}$ of $\varphi_{e}$ for
$e\in\\{e_{4},e_{5}\\}$. We use this convention also for the other
$\varphi_{e}$ in the formulas below). An agent standing at $\nu_{e_{3}}$ at
time $t\in[0,T]$, has two possible choices (meaning, the optimal behaviour may
only be one of the following two): staying in $\nu_{e_{3}}$ or moving to reach
$\kappa_{e_{3}}$ at $\tau\in]t,T]$. The controls among which the agent chooses
and the corresponding value function are then, respectively

$u^{e_{3}}_{1}=0,\ \ u^{e_{3}}_{2}=\frac{\ell_{e_{3}}}{\tau-t},$ (17)
$\displaystyle V^{e_{3}}(t)=$
$\displaystyle\min\left\\{\alpha\left(\ell_{e_{3}}+\ell_{e_{5}}\right)+\int_{t}^{T}\varphi_{e_{3}}\,ds,\right.$
(18)
$\displaystyle\left.\inf_{\tau\in]t,T]}\left\\{\frac{1}{2}\frac{(\ell_{e_{3}})^{2}}{\tau-t}+\int_{t}^{\tau}\varphi_{e_{3}}\,ds+V^{e_{5}}(\tau)\right\\}\right\\}.$

An agent standing at $\nu_{e_{1}}$ at time $t$ may choose: staying in
$\nu_{e_{1}}$ or to reach $\kappa_{e_{1}}$ at a certain $\tau\in]t,T]$. Hence,
the control is chosen among

$u^{e_{1}}_{1}=0,\ u^{e_{1}}_{2}=\frac{\ell_{e_{1}}}{\tau-t}.$ (19)

Consistently, one has

$\displaystyle
V^{e_{1}}(t)=\min\left\\{\alpha\min\left\\{\ell_{e_{1}}+\ell_{e_{4}},\ell_{e_{1}}+\ell_{e_{3}}+\ell_{e_{5}}\right\\}+\int_{t}^{T}\varphi_{e_{1}}\,ds,\right.$
$\displaystyle\left.\inf_{\tau\in]t,T]}\left\\{\frac{1}{2}\frac{(\ell_{e_{1}})^{2}}{\tau-t}+\int_{t}^{\tau}\varphi_{e_{1}}\,ds+\min\\{V^{e_{3}}(\tau),V^{e_{4}}(\tau)\\}\right\\}\right\\}$
(20)

Analogous arguments hold for computing $V^{e_{2}}(t)$ when an agent is
standing at $\nu_{e_{2}}$, indeed in that case the controls are

$u_{1}^{e_{2}}=0,\quad u_{2}^{e_{2}}=\frac{\ell_{e_{2}}}{\tau-t}.$ (21)

Hence the value function is

$\displaystyle V^{e_{2}}(t)$
$\displaystyle=\min\Bigg{\\{}\alpha(\ell_{e_{2}}+\ell_{e_{5}})+\int_{t}^{T}\varphi_{e_{2}}\,ds,$
(22)
$\displaystyle\inf_{\tau\in]t,T]}\left\\{\frac{1}{2}\frac{(\ell_{e_{2}})^{2}}{\tau-t}+\int_{t}^{\tau}\varphi_{e_{2}}\,ds+V^{e_{5}}(\tau)\\}\right\\}\Bigg{\\}}.$

Finally,

$V^{0}(t)=\min\\{V^{e_{1}}(t),V^{e_{2}}(t)\\}.$ (23)

Note that, the optimal controls described in (17), (19), (21) are detected
along with the arrival time $\tau$ along the minimization process carried on
in (18), (II-C), (22). Also, when $\rho$ is given, the construction of the
optimal controls is performed backwardly, starting from the problem (16).
Finally, observe that $V^{0}(t)$ in (23) is determined without the necessity
of computing any optimal control on the fictitious link $e_{0}$. We summarize
the previous discussion as follows.

###### Theorem 1

Suppose that $\rho$ is given and that (H1)–(H3) hold. Then, every value
function $V^{e}:[0,\ell_{e}]\times[0,T]\to\mathbb{R}$, at $0$ i.e, at the
beginning of each link, for all $e\in\cal E$ and for all $t\in[0,T]$, is
determined through (16)-(22). In addition, $V^{e}$ is Lipschitz continuous
with respect to time, with its Lipschitz constant independent of $\rho_{e}$.

###### Remark 2

Notice that, since the optimal controls are necessarily equi-bounded by a
constant depending only on the parameters of the problem and since from (H1)
follows that the inflow $\lambda(t)\delta_{\nu_{e}}^{(o)}$ is bounded and
continuous, by results on the mass conservation equations ((see, e.g., [19]),
follow that all $\rho_{e}$ are Lipschitz continuous, with Lipschitz constant
$\tilde{L}$ depending only on the parameters of the problem.

##  III EXISTENCE OF A MEAN FIELD EQUILIBRIUM

In this section we give a proof of the existence of a MF equilibrium. Let
$L(w)$ be the Lipschitz constant of a function $w$. As space to search for a
fixed point, we choose

$X=\left\\{w:[0,T]\to[0,\rho_{\max}]:{L(w)\leq\tilde{L}},\,|w|\leq\rho_{\max}\right\\}^{5},$
(24)

the Cartesian product five times of the space of Lipschitzian functions with
Lipschitz constant not greater than $\tilde{L}$ and overall bounded by
$\rho_{\max}$, where $\tilde{L}$ is the constant introduced in Remark 2. Note
that $X$ is convex and compact with respect to the uniform topology.

Fixed the noisy parameter $\beta>0$, we then search for a fixed point of the
multi-function $\psi:~{}X\to~{}X$, with
$\rho\mapsto\rho^{\prime}\in\psi(\rho)$ where $\rho^{\prime}$ is obtained as
follows: (i) $\rho$ is inserted in (16)–(22), the optimal control $u$ is
derived; (ii) $u$ is inserted in (8) and the path preference vector $z$ is
obtained; (iii) $\rho^{\prime}$ is derived from (12) after the computation of
(11) and (14):

$\rho$$u$$J(t,u)$$z$$H(f,z)$$\rho^{\prime}$$f$

###### Remark 3

Note that in general $\psi$ is not single valued, that is $\psi(\rho)$ is a
nonsigleton subset of $X$. Indeed the optimal control may not be unique as,
for any fixed $t$, the minimization procedure in (16)–(22) may return more
than one minimizer. In particular, in (16)–(22) this may happen even along a
whole time interval. Hence, when a multiplicity situation occurs, $\psi$ can
be built in many ways, as many as the different optimal behaviors. Indeed, for
example, if the controls in (19) are both optimal we get two different flows
$f_{e_{1}}$ and $f^{\prime}_{e_{1}}$ (see (14)) and hence, through (12), two
different densities $\rho_{e_{1}}$ and $\rho^{\prime}_{e_{1}}$ of which we
should consider the convexification. Note that the controls’ multiplicity does
not influence the computation of $z$ and hence $G(z)$, but only the flows $f$
used in (12) to get the fixed point of $\psi$. To bound the times at which
such multiplicities appear, we will obtain $\psi$ and its fixed point
$\widetilde{\rho}$ through a limiting procedure.

Fixed $\beta>0$, let $\left\\{\psi_{\varepsilon}\right\\}_{\varepsilon>0}$ be
a sequence of functions approximating $\psi$ in a suitable sense, and
$\rho_{\varepsilon}$ its corresponding fixed points. The single function
$\psi_{\varepsilon}$ is obtained through (i)–(iii) above, with the difference
that in (ii), rather than choosing optimal controls, one chooses
$\varepsilon-$optimal controls and, along time, an $\varepsilon-$_optimal
stream_. Accordingly the path preference vector will be computed once the
values of that $\varepsilon-$_optimal stream_ are given. We divide the
construction into two steps.

_Step 1: $\varepsilon$-optimal streams._

###### Definition 1

Assume for each link $e=(\nu_{e},\kappa_{e})\in\mathcal{E}$ to be in
$\theta_{e}=0$, i.e., at node $\nu_{e}$, and let $u^{e}_{j}$, $j\in\\{1,2\\}$
be the controls defined through (15) (17) (19) (21). Consider also a partition
$\tau^{e}=\\{t^{n}\\}_{n}$ of the interval $[0,T]$, and fix $\varepsilon>0$.
Then ${u}^{e}_{\varepsilon}$ is an $\varepsilon-$optimal stream for the link
$e$ associated to the partition $\tau^{e}$ if

${u}^{e}_{\varepsilon}(s)=u^{e}_{j_{n}}(s),\ \ s\in[t^{n},t^{n+1}[$

where $u^{e}_{j_{n}}$ is optimal at $t^{n}$ and $\varepsilon$-optimal at all
$s\in]t^{n},t^{n+1}[$, that is, it realizes the minimum cost up to an error
not greater than $\varepsilon$.

Notice that an $\varepsilon$-optimal stream associated to a general partition
$\tau$ may or may not exist, but it certainly does when the partition is
refined enough. Indeed, considering the functions involved in the minimization
process in (16), (18), (II-C), (22), if the minimum is realized up to the
error $\varepsilon$, the minima are attained within intervals of type
$[t+h_{\varepsilon},T],$ for some suitable $h_{\varepsilon}>0$, so that the
functions cited above are Lipschitz continuous. Denote by $L$ the greater of
Lipschitz constants of these functions. Then a control $u^{e}_{j}$ optimal at
$t$ remain $\varepsilon$-optimal at least along $[t,t+\varepsilon/L[$. In
addition, for every link $e$, there may exist more than one
$\varepsilon$-partition, as optimal controls determined in
$\theta_{e}=0\,,\forall\,e\in\mathcal{E},$ may be multiple. Anyway, the number
of $\varepsilon$-partitions is overall bounded by a number $M_{\varepsilon}$,
as the optimal controls at every $\theta_{e}=0$ are at most two. This argument
proves the following.

###### Lemma 1

Fixed $\varepsilon>0$, set
$N=\max\\{n\in{\mathbb{N}}:n<(TL)/\varepsilon\\}+1$. Consider the partition
$\tau_{\varepsilon}$ of $[0,T]$ such that:

  * $(i)$

$t^{0}_{\varepsilon}=0$; $t^{N}_{\varepsilon}=T$;

  * $(ii)$

$t^{n}_{\varepsilon}=nL/\varepsilon$, for all $n\in\\{1,\dots,{N-1}\\}$.

Then the set of $\varepsilon$-optimal streams associated to
$\tau_{\varepsilon}$ is nonempty and finite.

Now, for a fixed $\varepsilon>0$, consider the partition $\tau_{\varepsilon}$
defined in Lemma 1. Consider then the vector
$u_{\varepsilon}=\\{u_{\varepsilon}^{e}:e\in\mathcal{E}\\}$ whose components
are $\varepsilon$-optimal streams associated to $\tau_{\varepsilon}$ in
$\theta_{e}=0$. As consequence of Lemma 1 the $\varepsilon$-optimal vectors
$u_{\varepsilon}$ are a finite number of elements. Note that once
$u_{\varepsilon}$ is fixed, all agents make the same decision, in time.
Indeed, given the value of the $\varepsilon$-stream on each subinterval of
$\tau_{\varepsilon}$, each agent, in that subinterval, can evaluates the total
cost that he expects to incur in each path $p\in\Gamma$ and consequently it
will be possible to compute $z$ through (8). Hereinafter, we refer to this $z$
as $z_{\varepsilon}$, since its value depends on $u_{\varepsilon}$. The
possibility for agents to split into fractions among different vectors
$u_{\varepsilon}$ (that is, splitting among multiple optimal controls on
instants of $\tau_{\varepsilon}$), is given by an $\varepsilon-$split function
$\mu_{\varepsilon}$ so defined.

###### Definition 2

Consider the partition $\tau_{\varepsilon}$. An _$\varepsilon$ -split
function_ is a vector
$\mu_{\varepsilon}=(\mu_{j}^{(e)}:\,j=1,2,\,e\in\mathcal{E})\in
L^{\infty}(0,T)^{2\times|\cal E|}$ whose components $\mu^{(e)}_{j}$, called
_split fractions_ , are constant on subintervals induced by
$\tau_{\varepsilon}$ and satisfy:

  * $(i)$

$\mu^{(e)}_{j}(s)\geq 0,$ for all $s\in[0,T]$, and $\mu^{(e)}_{j}(t)=0$ if
$u^{e}_{j}$ is not optimal at $(0,t)$ for $t\in\tau_{\varepsilon}$;

  * $(ii)$

$\sum_{j=1}^{2}\mu^{(e)}_{j}(s)=1$ for all $s\in[0,T]$.

We can see $\mu_{j}^{(e)}$ as the fraction of agents who choose the control
$u_{j}^{e}$ in the link $e\in\mathcal{E}$.

_Step 2: Construction of $\psi_{\varepsilon}(\rho)$._

Let $\beta>0$, $\varepsilon>0$ and
$\rho=(\rho_{e_{1}},\rho_{e_{2}},\rho_{e_{3}},\rho_{e_{4}},\rho_{e_{5}})\in X$
be fixed. Let also $\tau_{\varepsilon}$ be the partition of $[0,T]$ described
above. We now built the multifunction $\psi_{\varepsilon}(\rho)\subseteq X$
with compact and convex images and closed graph, to which later we can apply
Kakutani fixed point theorem.

(a) We define $\tilde{\psi}_{\varepsilon}(\rho)\subseteq X$ as the finite set
of vectors
$\rho^{\prime}=~{}(\rho_{e_{1}}^{\prime},\rho_{e_{2}}^{\prime},\rho_{e_{3}}^{\prime},\rho_{e_{4}}^{\prime},\rho_{e_{5}}^{\prime})\in
X$ constructed in the following way. We consider an $\varepsilon-$optimal
vector $u_{\varepsilon}$, associated to $\tau_{\varepsilon}$ in $\theta_{e}=0$
for every $e\in\mathcal{E}$. Then, we use $u_{\varepsilon}$ to determine the
path preference vector $z_{\varepsilon}$. Finally, given the arrival flow of
agents $\lambda(t)\delta^{(0)}$ and computed the flow $f$ associated to the
initially given $\rho$ and to $u_{\varepsilon}$ (14), we solve (12) whose
solution is the total mass $\rho^{\prime}$. We repeat the construction for all
possible (and finite, by Lemma 1) choices $u_{\varepsilon}$ and call the set
of all outcomes $\tilde{\psi}_{\varepsilon}(\rho)$ which is a finite set.

(b) We define $\psi_{\varepsilon}(\rho)\subseteq X$ as follows. We consider an
arbitrary $\varepsilon$-split function $\mu_{\varepsilon}$ and assume that at
every point of $\tau_{\varepsilon}$ the outflow of agents $f_{e}$ from every
link $e$ gets split in fractions $\mu_{1}^{(e)}f_{e}$, $\mu_{2}^{(e)}f_{e}$
among the links $e^{\prime}$ immediately downstream the link $e$. At the end
of the process the output is $\rho^{\prime}$. We define
$\psi_{\varepsilon}(\rho)$ as the set of all $\rho^{\prime}$ generated by all
possible choices of the $\varepsilon$-split function $\mu_{\varepsilon}$.
Clearly $\psi_{\varepsilon}(\rho)\supset\tilde{\psi}_{\varepsilon}(\rho)$.

###### Lemma 2

The set $\psi_{\varepsilon}(\rho)$ is a non-empty convex and compact subset of
$X$, for any $\rho\in X$. Moreover, the map
$\rho\mapsto\psi_{\varepsilon}(\rho)$ has closed graph and it has a fixed
point $\rho_{\varepsilon}\in X$.

###### Proof:

We preliminarily observe that the set $\psi_{\varepsilon}(\rho)$ is non-empty
by construction. In addition, it is also closed and, hence, it is compact
since $X$ is compact. Moreover, it is possible to prove that
$\psi_{\varepsilon}(\rho)$ is the convex hull of
$\tilde{\psi}_{\varepsilon}(\rho)$ which is the set of all $\rho$ whose
corresponding $\mu_{\varepsilon}$ are obtained through all possible
$\varepsilon-$streams. Observe that the set $\tilde{\psi}_{\varepsilon}(\rho)$
is finite and includes at most $M_{\varepsilon}$ elements. Hence the set
$\psi_{\varepsilon}(\rho)$ has a finite number of extremal points. This fact,
together with the regularity assumptions (H1) and (H3), implies, reasoning as
in [8] but taking into account $z$, that the multifunction
$\rho\mapsto\psi_{\varepsilon}(\rho)$ has closed graph. Hence, by the Kakutani
theorem, there exists a fixed point
$\rho_{\varepsilon}\in\psi_{\varepsilon}(\rho_{\varepsilon})$. ∎

Hereinafter, we denote by $\rho_{\varepsilon}$ a fixed point for
$\psi_{\varepsilon}(\rho)$, i.e., a total mass that satisfies
$\rho_{\varepsilon}\in\psi_{\varepsilon}(\rho_{\varepsilon})$.

Before stating the existence of a MF equilibrium, we introduce the following
definition that help restrict the equilibrium concept to the purpose of our
problem.

###### Definition 3

Let $\psi$ and $\psi_{\varepsilon}$ be the functions described at the
beginning of Section III with $\beta>0$ fixed.

  * •

A $\varepsilon$-MF equilibrium is a total mass $\rho_{\varepsilon}\in X$ that
satisfies $\rho_{\varepsilon}\in\psi_{\varepsilon}(\rho_{\varepsilon})$.

  * •

A MF equilibrium is a total mass $\rho\in X$ that satisfies
$\rho\in\psi(\rho)$.

Note that $\rho\in\psi(\rho)$ implies that $\rho$ induces a set of optimal
controls as in (15), (17), (19), (21) used both to compute the corresponding
path preference vector $z$ and to define the fractions of flows according to a
split function $\mu$. Such a function is given as in Definition 2 but with the
difference that $\mu$ is not linked to any $\varepsilon$-partition, and its
components are not necessarily piecewise constant. Finally, using (12) we get
again $\rho$.

###### Theorem 2

Assume (H1)–(H3). Then there exists a MF equilibrium.

###### Proof:

We proceed similarly to Theorem 2 of [8], but with the suitable changes due to
the presence of the agent’s preference dynamics (8). ∎

###### Remark 4

In the construction of the multi-function $\psi$ we have fixed a priori the
noisy parameter $\beta>0$. Hence, we actually found a multi-function
$\psi_{\beta}$ such that $\rho_{\beta}\in\psi_{\beta}(\rho_{\beta})$. Given
the simple structure of (8) and (12) and to the properties of (9) and (10), it
seem reasonable that for $\beta\to+\infty$ there exist a multi-function
$\bar{\psi}$ and the corresponding fixed point $\bar{\rho}$ such that
$\lim_{\beta\to+\infty}\psi_{\beta}=\bar{\psi}$ and
$\lim_{\beta\to+\infty}\rho_{\beta}=\bar{\rho}$. The answer seem positive,
however, we have not yet covered all the details which we will pursue in
future research.

##  IV BI-LEVEL OPTIMIZATION

In this section, we discuss how the results introduced in the previous
sections can be used by a central authority (CA), e.g., the city hall,
interested in controlling the value of the mass $\rho$. For any given input
flow $\lambda(t)\delta^{(0)},t\in[0,T]$, heritage CA may be consider
sustainable for their historical centers that mass of agents is closed to some
reference value $\widetilde{\rho}$. Typically, a CA may slow down (and
sometimes also speed up) the agent flows by intervening on the width of the
streets with mobile barriers. Formally, we can assume that the CA can consider
congestion cost functions of the form

$\displaystyle\varphi_{e}(\rho_{e})=\alpha^{\prime}_{e}\rho_{e}(t)+\alpha^{\prime\prime}_{e}\quad\forall\
e\in\mathcal{E},$

where $(\alpha^{\prime},\alpha^{\prime\prime})$ are parameters in a compact
$K\in{\mathbb{R}}^{5}\times{\mathbb{R}}^{5}$.

Then, the CA is interested in solving the bi-level problem:

$\displaystyle\displaystyle\inf_{\left(\alpha^{\prime},\alpha^{\prime\prime}\right)}\left(\sup_{\rho}\|\rho-\widetilde{\rho}\|_{\infty}\right)$
$\displaystyle\text{subject to}\quad\inf_{u(\rho)\in
U_{\alpha^{\prime},\alpha^{\prime\prime}}}\hat{J}(t,u)$ (25)

with $\hat{J}(t,u)=\\{J_{e}(t,u^{e}):e\in\mathcal{E}\\}$ and where the CA
chooses the value of pair $(\alpha^{\prime},\alpha^{\prime\prime})$ in the
light of the expected response of the agents. We claim that, if the set
$U_{\alpha^{\prime},\alpha^{\prime\prime}}$ is a compact set of controls
depending by $(\alpha^{\prime},\alpha^{\prime\prime})$, then the existence of
a pair $(\alpha^{\prime},\alpha^{\prime\prime})^{*}$ solution of (25) can be
proved provided that a unique MFG equilibrium exists for each fixed
$(\alpha^{\prime},\alpha^{\prime\prime})\in K$.

##  V CONCLUSIONS

In this paper the existence of a mean-field equilibrium for a traffic flow
model is provided and a bi-level optimization problem is formulated. In future
research we plan to refine the optimization problem from both a theoretical
and an applicative perspective, and to consider different objectives of
central authority. Moreover a comparison between our MF model and the Wardrop
one also through numerical simulations will be provided. A further step could
be to consider a more general networks that includes oriented cycles. For this
kind of networks the backward approach used for the resolution of equations
(16)-(23) cannot immediately applied.

## References

  * [1] C. Burstedde, A.Kirchner, K. Klauck, A. Schadschneider, J. Zittartz, “Cellular automaton approach to pedestrian dynamics-applications”, Pedestrian and Evacuation Dynamics, Germany, pp. 87-98, 2001.
  * [2] D. Helbing, A. Johansson, “Pedestrian, crowd, and evacuation dynamics”, _Encyclopedia of Complexity and Systems Science_ , vol. 16. Springer, New York, pp. 6476-6495, 2009.
  * [3] R.Y. Guo, H.J. Huang, “A mobile lattice gas model for simulating pedestrian evacuation”, _Physica A_ , vol. 387, pp. 580-586 2008.
  * [4] R.L. Hughes, “A continuum theory for the flow of pedestrians”, _Transp. Res. B_ , vol. 36, pp. 507-535, 2002.
  * [5] S.P. Hoogendoorn, P.H.L. Bovy, “Pedestrian route-choice and activity scheduling theory and models”, _Transp. Res. B_ , vol. 38, pp. 169-190, 2004.
  * [6] S.P. Hoogendoorn, P.H.L. Bovy, “Dynamic user-optimal assignment in continuous time and space”, _Transp. Res. B_ , vol. 38, pp. 571-592, 2004.
  * [7] F. Bagagiolo, R. Pesenti, “Non-memoryless Pedestrian Flow in a Crowded Environment with Target Sets”, Advances in Dynamic and Mean Field Games, _Ann. Internat. Soc. Dynam. Games_ , vol 15, Birkhäuser, Cham, 2017.
  * [8] F. Bagagiolo, S. Faggian, R. Maggistro, R. Pesenti, “Optimal control of the mean field equilibrium for a pedestrian tourists’ flow model”, _Netw. Spat. Econ._ , DOI: 10.1007/s11067-019-09475-4, 2019.
  * [9] J.M. Lasry, P.L. Lions, “ Juex à champ moyen II. Horizon fini et controle optimal”, _C. R. Math._ , vol. 343, pp. 679-684, 2006.
  * [10] M. Huang, P. Caines, R. Malhame, “Large population dynamic games; closed-loop McKean- Vlasov systems and the Nash certainly equivalence principle”, _Commun. Inf. Sys._ , vol. 6, pp. 221-252, 2006.
  * [11] Y. Achdou, F. Camilli, I. Capuzzo Dolcetta, “ Mean field games: numerical methods for the planning problem”, _SIAM J. Control Optim._ , vol. 50(1), pp. 77-109, 2012.
  * [12] A. Lachapelle, M.-T. Wolfram, “On a mean field game approach modeling congestion and aversion in pedestrian crowds”, _Transp. Res. B_ , vol. 45(10), pp. 1572-1589, 2011.
  * [13] O. Guéant, J.M. Lasry, P.L. Lions, “Mean field games and applications”, Paris-Princeton Lectures on Mathematical Finance, Springer, Berlin Heidelberg, pp. 205?266, 2011.
  * [14] F. Camilli, E. Carlini, C. Marchi, “A model problem for mean field games on networks”, _Discrete Contin. Dyn. Syst._ , vol. 35, pp. 4173-4192, 2015.
  * [15] E. Cristiani, F. Priuli, A. Tosin, “ Modeling rationality to control self-organization of crowds: an environmental approach”, _SIAM J. Appl. Math._ , vol. 75, pp. 605-629, 2015.
  * [16] F. Bagagiolo, D. Bauso, R. Maggistro, M. Zoppello, “Game theoretic decentralized feedback controls in Markov jump processes”, _J Optim. Theory Appl._ , vol. 173, pp. 704-726, 2017.
  * [17] G. Como, K. Savla, D. Acemoglu, M.A. Dahleh, and E. Frazzoli, “Stability analysis of transportation networks with multiscale driver decisions”,_SIAM J. Control Optim._ , vol. 51, no. 1, pp. 230–252, 2013.
  * [18] R. Maggistro, G. Como, “Stability and optimality of multi-scale transportation networks with distributed dynamic tolls”, Proc. of the 57th IEEE CDC 2018, pp. 211-216, DOI: 10.1109/CDC.2018.8619804.
  * [19] P. Cardaliaguet, Notes on mean field games. Unpublished notes.
https://www.ceremade.dauphine.fr/ cardaliaguet/MFG20130420.pdf


# Guidance system for Visually Impaired Persons using Deep Learning and
Optical flow

11st Shwetang Dubey  (Member IEEE)
Information Technology
Indian Institute of information technology, Allahabad
Prayagraj, India
<EMAIL_ADDRESS>22nd Alok Ranjan Sahoo  (Member IEEE)
Information Technology
Indian Institute of information technology, Allahabad
Prayagraj, India
<EMAIL_ADDRESS>33rd Pavan Chakraborty  (Member IEEE)
Information Technology
Indian Institute of information technology, Allahabad
Prayagraj, India
<EMAIL_ADDRESS>
###### Abstract

Visually impaired persons find it difficult to know about their surroundings
while walking on a road. Walking sticks used by them can only give them
information about the obstacles in the stick’s proximity. Moreover, it is
mostly effective in static or very slow-paced environments. Hence, this paper
introduces a method to guide them in a busy street. To create such a system it
is very important to know about the approaching object and its direction of
approach. To achieve this objective we created a method in which the image
frame received from the video is divided into three parts i.e. center, left,
and right to know the direction of approach of the approaching object. Object
detection is done using YOLOv3. Lucas Kanade’s optical flow estimation method
is used for the optical flow estimation and Depth-net is used for depth
estimation. Using the depth information, object motion trajectory, and object
category information, the model provides necessary information/warning to the
person. This model has been tested in the real world to show its
effectiveness.

###### Index Terms:

YOLOv3, Deep Learning, Object detection, Visually Impaired, Neural network,
DepthNet, Optical Flow.

††publicationid: pubid: 979-8-3503-4210-9/23/$31.00 ©2023 IEEE

##  I Introduction

According to a report published by WHO on 14 October 2021[21], there are at
least 2.2 billion peoples who are having vision impairment. Around 1 billion
are having moderate or severe vision impairment or blindness. The number was
around 285 million in 2010. 246 million were having serious blindness. So, the
rise in visual impairment necessitates the development of an algorithm to give
real-time suggestions to fully or partially blind persons. Hence, this paper
intends to give a method for guiding visually impaired persons in real to
avoid obstacles.

The real challenge with the guidance system is the response time of that
model. As when a person is moving on the road then it means that when any
object comes in front of him then he will not be able to avoid it unless the
guidance system gives him a good response in real-time. So the main challenge
here was to generate a system that can not only give good object detection and
depth estimation but also can give better time accuracy so that obstacle
avoidance can be performed in real-time.

Here we are using the YOLOv3[9] model for object detection as it can give out
output much faster than other object detection algorithms like R-CNN, Fast
R-CNN, and Mask R-CNN [10][12][11]. Since all YOLO models are trained to do
classification and bounding box regression simultaneously so it works much
faster than R-CNN or Fast R-CNN. This YOLOv3 object detection algorithm is
trained on the COCO[18] dataset which has a total of 80 classes. So we will be
able to detect any object if they belong to one of these 80 classes. This
YOLOv3 algorithm generates an Anchor box around the detected object which can
be further used for depth estimation if we have the feed from both the left
and right camera.

In this paper we are giving a model to generate voice commands for the user in
a real-time situation for assisting a visually impaired person to move. We
also performed optical flow analysis to get the motion of the approaching
object towards the camera to generate proper instruction for the blind person.
We have divided the frame into 3 parts i.e. left, right, and center then
according to the position of the approaching object, the instruction is
generated. The main contribution of this paper is the following:

  * •

Used YOLOv3 object detection algorithm for classification of objects in video
frames from both left and right images.

  * •

A method to divide the entire image into 3 segments i.e. left, right, and
center to generate instruction properly.

  * •

Created an optical flow-based method to give the trajectory of the moving
object for object tracking.

  * •

Depth estimation is also performed for detecting depth in real time.

  * •

Finally Google text-to-speech converter is used for generating speech
instruction for blind persons.

##  II RELATED WORK

In recent years lots of methods have been developed for vision-based obstacle
detection and avoidance systems but most of them use different technologies
like WiFi, RFID, laser, etc. but the use of cameras for object detection and
avoidance is very limited. Vision-based obstacle avoidance system was first
introduced by Sainarayanan et al.[3]. In this the team has used they used
grayscale images for detection and the background removal is done by using a
neural network and obstacle pixels are enhanced. Ulrich et al.[24] proposed a
method of histogram comparison. In this method, first color image is filtered
and then converted to HSV color space and then the color histograms of the
candidate area and reference area are matched. Joachim et el.[15] derived a
method to detect obstacles using human color vision and then the auto-focused
stereo camera is used to get the depth of obstacles from a person. Rodríguez
et al.[22] proposed a model which was based on the cumulative grid in front of
visually impaired users for obstacle detection and avoidance. In this method
basically a stereo vision is used for obstacle detection and background
reduction.

###  II-A Obstacle detection

Bernabei et el.[4] proposed a method that basically uses an RGB-D sensor for
depth estimation and obstacle detection. In this paper basically, a 3D points
cloud is generated using Microsoft Kinect, and then the volume of the obstacle
in front of the person is calculated finally according to the volume
instructions are generated. Vlaminck et al.[25] presented a method where he
used RANSAC on a 3D point cloud for plane segmentation. After getting
different planes they used that information for ground, wall, and obstacle
detection. This method is good but not in real-time situations as RANSAC takes
too much time to process the 3D point cloud. Moreover, in this paper, they
considered obstacles to be on ground level which is not true for all cases.
Rodríguez et al.[22] published a paper that uses a stereo camera for screen
capture and then they generated a map of that place using visual SLAM and used
that map for autonomous navigation of the visually impaired person.

###  II-B Feedback system using voice command

After detecting the obstacle the second part of this problem is to make an
alert mechanism that can alert the visually impaired person in real-time. This
is a hard task to describe where the location of an obstacle and how to avoid
it to a blind person as he can not understand the world as we do. There are
multiple ways used to describe scenes by different researchers. Joachim et
al.[15] used a text-to-speech engine to convert the text into the form of
speech and then used a speaker to alert a person. The vOICe [13] system is
introduced to give complete views of the scene through image-to-sound
renderings. In this system the image is scanned from left the right and any
elevation is represented as pitch and brightness as loudness. So using sound
illusion created by the speaker a rough figure of the scene is created in the
person’s mind. This system is still in the development stage and needs a lot
of practice from users to clearly understand how to use it. This is why this
system is usually suitable for younger people. Sainarayanan et al. [3] used
the segmentation of the image into two parts left and right for this purpose.
The warning voice is generated according to the position of the obstacle in
these two segments and then sent to the user through headphones.

###  II-C Feedback system using tactical sensors

Johnson and Higgins et al.[16] created a tactical feedback system in which
different motors are attached to generate the vibration signal for the
obstacle present in front of the user. According to the location of the
obstacle, motors are assigned. This system needs training of the user for
proper functioning. Nguyen et al.[20] used an eclectic pulse-based system for
feedback. Electric pulses are generated in data gloves and give instructions
through nerves present in the skin.

##  III Method

In this section, we will describe how we performed our experiment and what are
different methods used for obstacle detection, depth estimation, and warning
generation. We are basically using the object detection method for obstacle
detection in both stereo inputs and then depth is estimated using stereo
vision and finally warning is generated using a GOOGLE text-to-speech
generation algorithm.

###  III-A Obstacle detection using YOLOv3

Obstacle detection is one of the basic problems to create effective methods
for visually impaired guidance systems. As we know obstacles can be on any
elevation and will keep moving towards the person or going away from the
person so the location of an obstacle is keep changing in a real-time
environment. To detect those objects and classify them as obstacles is one of
the biggest challenges of this problem. Here we are using the YOLOv3[9] object
detection algorithm for obstacle detection because it is very fast and creates
anchor boxes around the object. YOLOv3 is trained on the COCO dataset which
has 80 classes so it can predict the object if it belongs to one of these
classes. YOLOv3 uses Darknet-53 as a backbone feature extractor which has 53
convolutional layers making it a powerful network. YOLOv3 has skip connection-
based architecture like ResNet and 3 prediction heads like FPN. Basically,
YOLOv3 is not as accurate as YOLOv4[5] or YOLOv5 but this is much faster so we
used this model for our method as it can give results in real-time, and using
that we can create a good guidance system. We have used YOLOv3 in our captured
frames for obstacle detection and then monocular depth estimation is performed
for the depth estimation of the object.

Figure 1: YOLOv3 comparison with other object detection models. This shows
YOLOv3 is faster and better this is why we are using it for our model.[9]

###  III-B Depth estimation

Depth estimation is one of the basic needs for this type of problem as we need
to find the depth of the obstacle from the person to generate a warning in
time. Since we are using only one camera for our objective so depth estimation
becomes one of the most challenging works for this problem. Monocular depth
estimation is often considered an ill-posted problem as estimating depth only
from the pixel values is not generally possible. But current development in
deep learning techniques made it possible up to a good extent. There are many
deep learning-based techniques available for depth estimation like FlowNet
architecture by Dosovitskiy et al.[7], who applied a supervised encoder-
decoder CNN-based method to estimate the optical flow using channel-
concatenated image pairs, and Zhou et al.[26] who used unsupervised settings
for depth and pose estimation from a video sequence.

Figure 2: The $I^{t}h$ frame in the figure is a current frame and optical flow
uses current and previous frames for flow detection. YOLOv3 model is used for
object detection and Depth net is used for depth prediction from $I^{t}h$
frame. Finally, all three inputs are given to the model to generate a warning
signal.

In our approach, we used DephtNet[17] for depth estimation which is a
recurrent neural network architecture for monocular depth estimation. In
DepthNet convolutional LSTM (ConvLSTM)- based architecture is used for depth
estimation and the fully connected LSTM layer is replaced by a stack of
ConvLSTM layers. The LSTM layers allow the network to learn temporal
information better but here convolutional layer is also used as it retains the
spatial relationship between the grid cells. DepthNet uses multiple frames
from the video feed for depth estimation from a scene which goes into an
encoder-decoder setup. As this network is trained on the KITTI dataset so it
is suitable for outdoor performance tasks. Depth calculated from this method
is fast and more accurate as it uses multiple frames of video of the same
scene so we are using this method in our task. The loss function used here is
the Eigen scale invariant loss function by Eigen et al.[8]. Given a predicted
depth map $y_{i}$ and ground true depth map as $y_{i}^{*}$ the loss function
is given by:

$L(y,y^{*})=\frac{1}{n}\sum_{i}d_{i}^{2}-\frac{\lambda}{n^{2}}(\sum_{i}d_{i})^{2}$
(1)

where $d_{i}=log(y_{i})-log(y_{i}^{*})$ for the $i^{t}h$ pixel and $n$ is
total number of pixels.

The depth map evaluated from the DepthNet is mixed with the optical flow
obtained and then given to the model to generate the warning according to
distance from the person. The warning is generated according to the quadrant
of the obstacle in the image. The next section is about how we obtained
optical flow from the video feed.

###  III-C Optical flow estimation

Optical flow or optical flow is the pattern of apparent motion of objects,
edges, and surfaces in a visual scene caused by the relative motion between an
observer (an eye or a camera) and the scene. Motion field can be defined as
the real-world 3D motion and the optical flow field is its projection to the
2D image. So any motion in 3D generates a vector in 2D and that vector is
defined as the optical flow of that particular object. J.L. Barron and N. A
Thacker [14] proposed that a 2D Motion Field can be defined as -2D velocities
for all visible points. We used Lucas-Kanade[19] method for optical flow
estimation from the video feed. This method has two assumptions for optical
flow estimation i.e the two images are separated by a small time increment
${\Delta}t$, in such a way that objects have not displaced significantly and
the images depict a natural scene containing textured objects exhibiting
shades of gray which changes smoothly.

Since we are using the camera on a person who is moving at a slow speed and
also obstacles approaching him are also not that fast so we are satisfying
both assumptions up to a good level so we are using this model for our optical
flow estimation. Lucas Kanade’s[19] method solves basic optical flow equations
for all the pixels in that neighborhood using least squares error. This method
is very fast in operation so it is most suitable for our task as we want to
create a real-time system. The disadvantage of this method is errors in moving
boundaries. If $P1,P2....Pn$ are pixels of the window and
$I_{x}(p_{n}),I_{y}(p_{n}),I_{t}(p_{n})$ are partial derivatives of the image
I with respect to position x,y, and the time t of point $P_{n}$ at the current
time. $V_{x}andV_{y}$ are components velocity vector then the equations
according to Lucas Kanade’s method can be given as:

$Av=b$

, where

$A=\begin{bmatrix}I_{x}(p_{1})&I_{y}(p_{1})\\\ I_{x}(p_{2})&I_{y}(p_{2})\\\
\vdots&\vdots\\\
I_{x}(p_{n})&I_{y}(p_{n})\par\end{bmatrix},v=\begin{bmatrix}V_{x}\\\
V_{y}\end{bmatrix},b=\begin{bmatrix}-I_{t}(p_{1})\\\ -I_{t}(p_{2})\\\
\vdots\\\ -I_{t}(p_{n})\end{bmatrix}$

Lucas Kanade used a least squares criterion-based approach for optical flow
estimation. So:

$V=(A^{T}A)^{-1}A^{T}b$

where, $A^{T}$ is transpose of matrix $A$,

This equation gives the same importance to all the pixels of the image but we
want to give more importance to the center pixels so in the Lucas Kanade
method weighted version of the least square is used.

$V=(A^{T}WA)^{-1}A^{T}Wb$ (2)

Where W is $n\times n$ dimension diagonal matrix containing weights assigned
to pixels $p_{n}$.

The flow-chart for Lucas Kanade’s method can be given as:

  * •

Calculate flow $u(i-1),v(i-1)$ from level i-1.

  * •

Up sample $u(i-1),v(i-1)$ to create $u^{*}(i),v^{*}(i)$ of twice resolution as
of level i and then multiply them with 2.

  * •

Now as $u^{*}(i),v^{*}(i)$ apparent velocities so we apply this block
displacement.

  * •

Then apply Lucas Kanade to find $u^{{}^{\prime}}(i)$ and$v^{{}^{\prime}}(i)$.

  * •

$u(i)=u^{*}(i)+u^{{}^{\prime}}(i)$
$v(i)=v^{*}(i)+v^{{}^{\prime}}(i)$
Finally we apply these two formulae to find optical flow for $Ith$ level.

We compute above defined Lucas Kanade to the highest level to get optical
flow. So after calculating the optical flow and depth map, we have depth
information as well as information about the flow of objects in front of a
person so now we will use these two pieces of information in our model to
create a model which can be used for real-time prediction of warning for a
visually impaired person.

###  III-D Evaluation of Obstacle Location

One of the most challenging tasks for generating a guidance system is to find
the location of the obstacle in the image or in the video frames. For this
particular task, we have used a special kind of method in which we divided the
entire image or frame into 3 parts ie. Left, Center, and Right. The left part
is basically the left of the person who is having the camera and so as others.
Here as we already calculated the depth map using DepthNet[17] and optical
flow using Lucas Kanade[19] so we created an algorithm to generate an alert
using all these three values. As if the object is detected using YOLOv3[9] and
it belongs to the right side of the image then it is most likely not going to
be an obstacle for the moving visually impaired person but if its depth map
and optical flow show it is moving towards the person then warning should be
generated. And same goes for left-side obstacles also. So here we generated an
algorithm that uses all three inputs i.e. depth map, optical flow, and object
detection outputs, and then generates the warning using these three values in
real-time.

We have divided the image into 3 parts, consider if the complete width of the
image is 1280 then the image is divided using the following formula
$0\>to\>448$ width is considered as left and if the depth value corresponding
to those value is less than 210 then a warning is generated that object is
approaching from the left. If the width value is between $448\>to\>832$ and
the depth is less than 220 the warning is generated that the obstacle is in
front and if the width value is between $832\>to\>1280$ and depth is less than
210 then a warning is generated that object is approaching from the right. So
using this small method we are generating warning text in our program and we
are doing it in a real-time environment.

###  III-E Text to speech

We are using Google text-to-speech converter API to convert the generated
warning text into speech a blind person can listen to. The API used in this
method is commonly known as gTTS [1]. We used this API because it generates
mp3 files for speech and this gTTS supports $30+$ languages like Hindi,
English, Tamil, German, etc., and 100+ voices with localized accents for some
languages like English, French, Mandarin, etc. so this a very useful tool
provided by google for this particular task. Google Text to Speech accepts a
maximum of 100 and if the length is longer than that then it is handled by
dividing the text into two parts. In our use case, we do not need to do that
as we are generating only small text files as warning symbols. The text
messages which are used as warnings are:

  * •

The object is approaching from the left.

  * •

The object is approaching from the center.

  * •

The object is approaching from the right.

##  IV Experiments and Results

In this section, we will apply our model to the real-time environment and will
see how the model performs. We are using a single-camera framework for this
purpose where we record the moving scene in front of the visually impaired
person. The model is working in real time but for evaluation purposes, we
recorded the video and applied the model to our computer.

###  IV-A Datasets

Here we are using the Common objects in Context COCO[18] dataset for obstacle
detection purposes. This dataset is made of a total of 328K images of 80
different object categories. This dataset was developed by Microsoft for
different tasks like object detection, captioning, keypoint detection, etc.
This dataset is having images of very common objects like persons, cars,
chairs, etc. The video is captured from a single camera installed on top of a
moving person. This video is used as input to our model and for frame
capturing.

###  IV-B Implementation details

In our experiment we used an MP4 video file as input for implementing our
model. The output video file is of shape 2560*720 in which the object is
detected and written as well as audio based warning is generated. We used
Lucas Kanade’s method for optical flow estimation, using trajectories made by
optical flow to judge from which side the object is approaching the person. We
used the search window size for Lucas Kanade as $15\times 15$, maximal pyramid
level number used is 4 so a total of five levels have been used. The shi-
Tomasi corner detection method is used for corner detection with a maximum
number of corners of $200$ and quality level parameter of $0.03$ and a maximum
distance of $10$. Depth net used for depth estimation uses encoding and
decoding phases where the encoding phase consists of $3\times 3$ ConvLSTM
layers of size $\\{32,64,64,128,128,256,256,512\\}$ filters respectively,
except first two layers where $7\times 7$ and $5\times 5$ filter size is used.
A ReLu activation function is used for the ConvLSTM layer and a hard sigmoid
is used for the recurrent step. In the decoding phase, a number of
deconvolution layers have been used of sizes
$\\{512,256,256,128,128,64,64,32\\}$ respectively. The filter size used for
deconvolution layers is $3\times 3$ and $1\times 1$. Finally, we have used a
Google text-to-speech converter to convert the text available into a voice
signal so that the person can be alerted. We are English language for our
experiment since it is mostly accepted language.

Figure 3: Output of model when a person is coming from the front. The lines
are showing the optical flow.

###  IV-C Experimental setup

The proposed model uses a Pytorch and Google-Colaboratory GPU for processing
purposes. We used a single video camera on the forehead of the moving person
to record a video feed for testing. Then we deploy our model to a laptop
attached to the forehead camera to generate the warning according to the
approaching obstacle. The text-to-speech converter is then used to convert the
text which we got from our model to convert into a voice command to instruct
the visually impaired person about the incoming obstacles. For now, we also
used some random moving person video from the internet to test our model and
it is working well in those inputs and giving sufficient output.

###  IV-D Testing on videos

We have tested this model on different videos available on YouTube for
prediction. Using this model the output achieved is fast as the objects can be
faster recognized using the YOLOv3 method. As we can see in the Fig.1 the
YOLOv3 is faster compared to previous methods in the evaluation part. At the
table, we are watching a video with our eyes and observing from which side the
person or obstacle is approaching and then we have tested our model on the
same video to generate warnings for the visually impaired person. We have
repeated this process for three videos and the results are shown in the table.
The optical flow model generates warnings only for approaching objects.

TABLE I: Table For testing on YouTube video | Observation by | Observation by
---|---|---
| human | model
YouTube Video Link | Total human | Total warning
| approached | generated
|  | (Correctly)
www.youtube.com/watch | 9 | 8
?v=EXUQnLyc3yE[2] |  |
www.youtube.com/watch | 10 | 9
?v=SotdSIWmg7Q[6] |  |
www.youtube.com/watch | 8 | 8
?v=6NBwbKMyzEE[23] |  |

##  V Conclusion and Future Work

As technology is growing these days and as it is making the life of a human
being easier and easier this is our little effort to make the life of visually
impaired persons easier using the latest deep learning technologies. We have
created our model in such a way that it can perform in real-time so that it
can be really helpful. At the same time, our model should be more and more
accurate as it will be assisting the blind person. That is why we are using
optimal models which are neither too heavy nor too much inaccurate. In the
future, we will try to find solutions for different environmental conditions
and will try to make a better model which can work on any environmental
condition and in real time.

## References

  * [1] Google Cloud Text-to-Speech API  URL: https://cloud.google.com/text-to-speech/
  * [2] AUDIOVIDEO+  URL: https://www.youtube.com/watch?v=EXUQnLyc3yE
  * [3] G. Balakrishnan, G. Sainarayanan, R. Nagarajan and SazaliYaacob  “A Stereo Image Processing System for Visually Impaired”  In _World Academy of Science_ 20 2008-08-23 EngineeringTechnology
  * [4] D. Bernabei et al.  “A low-cost time-critical obstacle avoidance system for the visually impaired”  International conference on indoor positioningindoor navigation (IPIN), 2011
  * [5] Alexey Bochkovskiy, Chien-Yao Wang and Hong-Yuan Mark Liao  “YOLOv4: Optimal Speed and Accuracy of Object Detection”  In _ArXiv_ abs/2004.10934, 2020
  * [6] CNN  URL: https://www.youtube.com/watch?v=SotdSIWmg7Q
  * [7] Alexey Dosovitskiy et al.  “FlowNet: Learning Optical Flow with Convolutional Networks”  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , 2015, pp. 2758–2766  DOI: 10.1109/ICCV.2015.316
  * [8] David Eigen, Christian Puhrsch and Rob Fergus  “Depth Map Prediction from a Single Image using a Multi-Scale Deep Network”  In _Advances in Neural Information Processing Systems_ 27 Curran Associates, Inc., 2014  URL: https://proceedings.neurips.cc/paper_files/paper/2014/file/7bccfde7714a1ebadf06c5f4cea752c1-Paper.pdf
  * [9] Ali Farhadi and Joseph Redmon  “Yolov3: An incremental improvement”  In _Computer vision and pattern recognition_ 1804, 2018, pp. 1–6  Springer Berlin/Heidelberg, Germany
  * [10] Ross Girshick  “Fast R-CNN”  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , 2015, pp. 1440–1448  DOI: 10.1109/ICCV.2015.169
  * [11] Ross Girshick, Jeff Donahue, Trevor Darrell and Jitendra Malik  “Rich Feature Hierarchies for Accurate Object Detection and Semantic Segmentation”  In _2014 IEEE Conference on Computer Vision and Pattern Recognition_ , 2014, pp. 580–587  DOI: 10.1109/CVPR.2014.81
  * [12] Kaiming He, Georgia Gkioxari, Piotr Dollár and Ross Girshick  “Mask R-CNN”  In _2017 IEEE International Conference on Computer Vision (ICCV)_ , 2017, pp. 2980–2988  DOI: 10.1109/ICCV.2017.322
  * [13] “http://www.seeingwithsound.com”, 2016
  * [14] J.L.Barron and N.A.Thacker  “Computing 2D and 3D Optical Flow”  University of Manchester, 2005
  * [15] A. Joachim, H. Ertl and D Thomas  “Design and Development of an indoor navigation and object identification system for the blind”  ACM SIGACCESS accessibility, computing, 2004
  * [16] L.A. Johnson and C.M Higgins  “A navigation aid for the blind using tactile-visual sensory substitution”  28th Annual international conference of the IEEE engineering in medicinebiology society, 2006, pp. 6289–6292
  * [17] Aran C.S. Kumar, Suchendra M. Bhandarkar and Mukta Prasad  “DepthNet: A Recurrent Neural Network Architecture for Monocular Depth Prediction”  In _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , 2018, pp. 396–3968  DOI: 10.1109/CVPRW.2018.00066
  * [18] Tsung-Yi Lin et al.  “Microsoft COCO: Common Objects in Context”  In _Computer Vision – ECCV 2014_ Cham: Springer International Publishing, 2014, pp. 740–755
  * [19] B.D. Lucas and T. Kanade  “An Iterative Image Registration Technique with an Application to Stereo Vision”  Proceedings of Imaging Understanding Workshop, 1981, pp. 121–130
  * [20] T.H. Nguyen et al.  “Antenna design for tongue electrotaticle assitive device for the blind and visually impaired”  7th European conference on attennaspropagation, 2013
  * [21] World Health Organization  “World report on vision”, 14/10/2021, pp. 180  World Health organization
  * [22] A. Rodríguez et al.  “Assisting the Visually Impaired: Obstacle Detection and Warning System by Acoustic Feedback”  Sensors, Dec. 2012, pp. 17476–17496  DOI: 10.3390/s121217476
  * [23] 101GreenLight TV  URL: https://www.youtube.com/watch?v=6NBwbKMyzEE
  * [24] I. Ulrich and J. Borenstein  “VFH/sup */: local obstacle avoidance with look-ahead verification”  In _Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065)_ 3, 2000, pp. 2505–2511 vol.3  DOI: 10.1109/ROBOT.2000.846405
  * [25] M. Vlaminck et al.  “Obstacle detection for pedestrians with a visual impairment based on 3d imaging.”  2013 International conference on 3D imaging (IC3D), 2013, pp. 1–7
  * [26] Tinghui Zhou, Matthew Brown, Noah Snavely and David G. Lowe  “Unsupervised Learning of Depth and Ego-Motion from Video”  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017, pp. 6612–6619  DOI: 10.1109/CVPR.2017.700