A discrete Hughes model for pedestrian flow on graphs

1.   Introduction.

In [18], Hughes introduced a by now classical fluidodynamical model to study the motion of a large human crowd (see also [17], [19], [20], [25] and [6] for a review).

The crowd is treated as a "thinking fluid" and it moves at the maximum speed towards a common destination or goal, taking also into account the environmental conditions. In fact, people prefer to avoid crowded regions and this assumption is incorporated in a potential field which gives the direction of the motion. The potential field is described by the solution of an eikonal equation giving the optimal paths to the destination, integrated with respect to a cost proportional to the local crowd density. Hence, for each instant of time, an individual looks at the global configuration of the crowd and updates his/her direction to the exit trying to avoid the crowded, motion expensive regions.

Many situations related to pedestrian motion, for example the study of a crowd escaping from a building, can be described as the problem of finding the shortest path in a network. A model to simulate the behavior of pedestrian motion on network is therefore important for designers to analyze the performance results in terms of number of nodes and connectivity of the environment.

In this paper we introduce both a model for pedestrian motion on networks which on one side can be viewed as a discrete time-finite state analogous of the Hughes model, and a numerical discretization of the Hughes system defined on a graph. The system is composed by a graph eikonal equation where the cost depends on the density of the population, and a graph conservation law which governs the evolution of the population. We show that, under some natural assumptions on the flux, the graph Hughes system is well-posed for any time $n\in N$. Moreover, it shares with the corresponding continuous model some qualitative properties, like e.g. the interpretation of the solution of the graph eikonal equation as a distance from the boundary.

The model here described bears some resemblance to the rational behavior model studied in [13]. People know at each time the global distribution of the population on the graph and, therefore, they accordingly modify their strategy to reach the exit. In [13] this behavior is obtained by introducing an optimization problem at the junctions, whereas here the optimal strategy is given by the solution of the eikonal equation.

We also present an algorithm for the solution of the discrete problem. We consider several examples and we show that the discrete Hughes system captures the natural behavior of the crowd.

The paper is organized as follows. In Section 2, we recall the Hughes model and we formulate its analogous on network. In Section 3, we derive the discrete Hughes system on a graph and in Section 4 we prove the well-posedness of this problem. Section 5 is devoted to the algorithm for the solution of the problem and to numerical experiments aimed at confirming the validity of the proposed model. We conclude the paper with final comments and remarks reported in Section 6.

2.   The Hughes model.

From a mathematical point of view the Hughes model consists in the following system

where $\Omega$ is a bounded domain of $\mathbb{R}^n$ and $\rho$, which takes value in $[0,1]$, is a density field representing the concentration of the pedestrian at $(x,t)$. The problem is completed with some boundary conditions: the initial configuration of the mass

and a no-flux condition on the boundary

for the continuity equation (1); the Dirichlet boundary condition

for the eikonal equation (2). The function $f(\rho )$ is typically given by $1 - \rho$, hence the (absolute value of the) flux is given, as in many other models related to pedestrian and vehicular motion, by $g(\rho)=\rho v_{max} (1-\rho)$. The term $v_{max}$, which can be always normalized to 1, is a maximal speed at which an agent would travel in ideal environment conditions and the term $\rho(1-\rho)$, the so called fundamental diagram (see [16]), indicates that the velocity of a pedestrian is proportional to the crowd density (recall that $\rho\in [0,1]$).

The direction of the motion is given by the potential term $\nabla u$. If the cost $1/f(\rho(x,t))$ is bounded, i.e. if $\rho(x,t)$, the solution of the eikonal equation (2) at time $t$ is given by

where the distance function $d_t:\Omega\times\Omega\to\mathbb{R}^+$ is defined as follows

with $G^S_{x,y}$ the set of the absolute continuous curves in $\Omega$ such that $\xi(0)=y$, $\xi(S)=x$ and $|\dot\xi(s)|=1$ a.e. in $[0,S]$. The term $1/f(\rho(x,t))$ can be interpreted as the current cost associated to the curve $\xi(s)$ and the solution $u$ of (2) selects the curves which minimize the cost for reaching the boundary. Hence, people are directed towards the boundary trying to avoid crowded regions.

Existence of a solution to (1)-(2) is still an open problem, the main difficulty is given by the possible concentration of population for some $t$ which results in the blow-up of the cost term $1/f(\rho(t))$. Partial results are available only in the one-dimensional case (see [3,4,14]); note that in $\mathbb{R}$, since $|\partial_x u| = \partial_x u \,\hbox{sign}(\partial_x u)$, the first equation in (1) simplifies as

and the solution of the eikonal equation admits an almost explicit representation formula. Moreover, there have been several approaches which regularize the flux function in order to obtain a well-posed problem. In [14], a regularization of the eikonal equation (2) has been introduced in order to avoid the possible blow-up of $|\nabla u|$, leading to the system

for some $\epsilon$, $\delta>0$. Also for this system, existence and uniqueness of a weak solution have been obtained in the one dimensional case.

2.1.   The Hughes model on networks

In the recent years, the theory of entropy solutions for conservation laws and of viscosity solutions for Hamilton-Jacobi equations have been extended to the case of networks (see [16] and [8], [21], respectively), imposing appropriate transition conditions at the intersections.

A network $\mathcal N=(\mathcal V,\mathcal E)$ is composed by a finite collection of points $\mathcal V:=\{v_i\}_{i\in \mathcal I}$ in $\mathbb{R}^n$ connected by continuous, non self-intersecting edges $\mathcal E:=\{e_j\}_{j\in \mathcal J}$. We define $N:=|\mathcal V|, M := |\mathcal E|$ and $\mathcal I:=\{1,\dots,N\}$, $\mathcal J:=\{1,\dots,M\}$. Each edge $e_j\in \mathcal E$ is parametrized by a smooth function $\pi_j:[0,l_j]\to\mathbb{R}^n,\, l_j>0$. Given $v_i\in \mathcal V$, $Inc_i:=\{j\in \mathcal J:v_i\in e_j \}$ denotes the set of edges branching out from $v_i$, and we denote by $d_{v_i}:=|Inc_i|$ the degree of $v_i$. A vertex $v_i$ is called a boundary vertex if $d_{v_i}=1$ and $\partial \mathcal N$ denotes the set of boundary vertices.

For a function $u: \mathcal E\to\mathbb{R}$, $u_j:[0,l_j]\to \mathbb{R}$ is the restriction of $u$ to $e_j$, i.e. $u(x)=u_j(y)$ for $x\in e_j$, $y=\pi_j^{-1}(x)$, and $\partial _j u(v_i)$ is the oriented derivative of $u$ at $v_i$ along the arc $e_j$ defined by

The Hughes system on the network $\mathcal N$ is given by

where the derivatives $\partial _x u_j$ must be interpreted as derivatives with respect to $y=\pi_j^{-1}(x)$, which parametrizes the edge $e_j$.

The system (6) is formally equivalent to $M$ scalar Hughes systems defined on the edges coupled via the transition conditions at the internal vertices where we require the conservation of the flux for the density $\rho$, while the continuity for $u$. We recall that, if we consider the two equations separately, the previous transition conditions are sufficient to get existence of weak solutions for both the equations (for the Hamilton-Jacobi equation also uniqueness, whereas some additional junction conditions are required to obtain the same for the conservation law [16,7]). In principle these two approaches could be combined to study the Hughes {system on networks}, but it seems very difficult since even in the Euclidean case the existence of a solution is still an open problem. Hence, in Section 3 we will consider a discrete system similar to (6) on a graph, where the solution is defined only on the vertices and the edges are reduced to connection information. In this way we will be able to obtain some well-posedness results. Finally, we observe that it is possible to consider the following network version of the regularized system (5)

where, as stated above, the derivatives $\partial _x u_j$ and $\partial _{xx} u_j$ must be interpreted as derivatives with respect to $y=\pi_j^{-1}(x)$, which parametrizes the edge $e_j$. Note that, with respect to the first order system, a Kirchhoff law for $u$ at the internal vertices has to be added.

3.   The Hughes model on graph

In this section, after a preliminary paragraph that introduces our notation on graph, we focus on the discrete Hughes system and its interpretation as a discrete-time finite state model for pedestrian flow on a graph.

3.1.   Basic notations

Let us consider a weighted graph $\Gamma=(V,E,w)$ where $V$ denotes the set of vertices, $E\subset V\times V$ the set of the edges and $w:V\times V\to \mathbb{R}$ the weights of the edges with $w(x,y)>0$ if $(x,y)\in E$ and $w(x,y) = 0$ otherwise. In what follows we will use the notation $w_{xy} := w(x,y)$ for the sake of simplicity. The weight $w_{xy}$ is a parameter which takes into account several properties of the edge $(x,y)$ such as length, capacity, velocity (small weights correspond to a better connection between $x$ and $y$). The graph is assumed to be finite, simple, connected and undirected, hence $w_{xy}=w_{yx}$ for any $(x,y)\in E$.

We set $y\sim x$ if $(x,y)\in E$ and we denote by $I(x)=\{y\in V:\, y\sim x\}$ the set of the neighbors of $x$ and by $|I(x)|$ the degree of $x$, i.e. the cardinality of the set $I(x)$. We set

We denote by $V_b\subset V$ the set of the boundary vertices of the graph and by $V_0=V\setminus V_b$ the set of the internal vertices.

A path connecting $x$ to $y$ is given by a finite subset ${\rm{\gamma }}=\{x_0=x,x_1,\dots, x_N=y\}$ of $V$ such that $x_k\sim x_{k+1}$, $k=0,\dots,N-1$. We denote by $\mathcal G_{xy}$ the set of the paths ${\rm{\gamma }}$ connecting $x$ to $y$. The geodetic distance between two adjacent vertices $x,y$ is

whereas for two arbitrary vertices $x,y\in V$ we define

where the minimum is taken over all the finite paths ${\rm{\gamma }}\in \mathcal G_{xy}$.

3.2.   The discrete Hughes model

Given a weighted graph $\Gamma$, we consider the following discrete Hughes system for a $n\in\mathbb{N}$

where $h^n_{yx}$ denotes the flux between $x$ and $y$ and $\lambda$ is a positive constant. To define the flux $h^n_{yx}$ in (9) we consider a function $h$ satisfying

for a continuous function $m:\mathbb{R} \to\mathbb{R}$, where $a_-=\min(a,0)$, $a_+=\max (a,0)$ and $\partial_1 h$ and $\partial_2 h$ denotes the derivatives of $h$ with respect to the first or the second argument, respectively. We set

where $\delta^n_{yx} = \textrm{sgn}(u^n(y)-u^n(x))$ with $u^n$ given by the second equation in (9).

In order to give specific examples of $h$, we consider flux functions which are consistent with $g(\rho)=\rho(1-\rho)$, i.e. $h(\rho,\rho)=g(\rho)$ for $\rho\in\mathbb{R}$, such as the Lax-Friedrichs flux

Other examples of flux verifying (10)-(11) are given by the Godunov flux

and by the Engquist-Osher flux

In all the previous examples $h$ is consistent with $g$ and satisfies (10)-(11) with $m(v)=g'(v)$. Note that the discrete conservation law in (9) coincides with the numerical scheme for (1) introduced in [24] if the graph $\Gamma$ is given by the discretization points of an interval $[a,b]$ and $h$ is consistent with $g(\rho)=\rho(1-\rho)$ (see also [17]). In the case of a network, it corresponds to discretize the conservation law (1) inside the edges and to impose the conservation of the flux at the vertices. We also refer to [7],[16] for different numerical discretizations of conservation law on networks in the framework of vehicular traffic motion. Concerning the Eikonal equation (2), we recall that approximations of Hamilton-Jacobi equations on networks are discussed in [12] for finite differences and in [10] for semi-Lagrangian schemes.

The system (9) has been introduced as a discretization of the continuous problem (1)-(2), but nevertheless it inherits some dynamical properties of the original model and it can be interpreted as a discrete-time finite state model for the flow of pedestrians on a graph in the following way. At the initial time, there is a continuum of indistinguishable players distributed on the vertices of the graph $\Gamma$ according to a density function $\bar\rho$, where $\bar\rho(x)$ represents the crowd at the vertex $x$. As in the original Hughes model [18], we assume that people have a complete knowledge of the environment and they choose the minimum distance path to their destination $V_b$, but they have difficult to move against the flow which is proportional to the local crowd density. Each vertex $x\in V$ represents a point at which people can choose which route $(x,y)\in E$ to take and the subset $V_b\subset V$ represents the goal, e.g. the exit of the environment.

The term $\textrm{sgn}(u^n(y)-u^n(x))$ (with $\textrm{sgn}(0)=0$), where $u^n:V\to\mathbb{R}$ is the solution of the graph eikonal equation in (9) at the time $n$, gives the direction of the flow. The function $u^n$, see (24) for more details, is given by the distance function from the boundary integrated along the cost $1/(1-\rho^n)$ which penalizes the vertices with high density $\rho^n$.

The pedestrians having reached a vertex $x\in V$ at a given time $n$ are stirred to the arc which minimizes the distance $u^n$ from the boundary. Moreover, if $x\in V_b$ then $u^n(x)=0$ and $\delta ^n_{yx}>0$ for each $y\in V_0$ such that $(x,y)\in E$. Hence, the flow is always in the direction of the boundary, i.e. the individuals having already reached the destination cannot reenter in the environment.

If we consider the flow $h$ given e.g. by (13), the first of the two terms tell us that the velocity of the pedestrians along the arc $(x,y)$ is given by the average of the velocity at $x$ and $y$; the second term is a small viscosity term given by the graph laplacian

which can be interpreted as a stochastic perturbation of the flux at $x$.

4.   Analytical results for the Hughes model on graph

In this section we prove existence and uniqueness of the solution of the discrete Hughes model. We study separately the discrete eikonal equation and the discrete conservation law present in the system (9) and, then, we will arrive to the well-posedness of the discrete system.

4.1.   The eikonal equation on graph

We study the graph eikonal equation (see [5], [22] for related results)

We assume that, for any $n\in\mathbb{N}$,

for some $\delta >0$, hence there exists a constant $M$ such that

Theorem 4.1.Let us assume that the condition (17) holds. Then, for any $n\in\mathbb{N}$, there exists a unique solution of (16), given by the formula

$($with the convention $\sum_{k=0}^{-1}=0)$.

Proof Existence. The function $u^n$ in (19) is well-defined (i.e., the minimum is achieved) since, for each fixed $x$, the set of admissible paths connecting $x$ to the boundary $V_b$ is finite. We first show that for $x\in V_0$

Given $y\sim x$, let $z\in V_b$ and $\gamma =\{x_0=y,x_1,\dots, x_N=z\}\in \mathcal G_{yz}$ be such that

Then, $\{x, x_0,\dots, x_N=z\}\in \mathcal G_{xz}$ is a path connecting $x$ to $z\in V_b$ and, therefore,

from which we can conclude that (20) holds.

Let us show now that for $x\in V_0$

Let $z\in V_b$ and $\gamma =\{x_0=x,x_1,\dots, x_N=z\}\in \mathcal G_{x,z}$ be such that

Since $x_1\sim z$ and $\{x_1,\dots, x_N\}\in\mathcal G_{x_1z}$, we get

and, therefore,

Combining (20) and (21), we get (16).

Note that the positivity of the cost $1/(1-\rho^n)$ implies $u^n(x)> 0$ for any $x\in V_0$. If $x\in V_b$, considering the stationary path $\gamma =\{x_0=x\} \in\mathcal G_{xx}$ which gives a null cost, we have

and, therefore, $u^n(x)=0$.

Uniqueness. Let $u^n$, $v^n$ be two solutions of (16) and in addition we assume that $\max\limits_{V}\{u^n-v^n\}=\delta$, for a strictly positive $\delta$. We also define $W :=\arg\max\limits_{V}\{u^n-v^n\}$ and $m :=\min\{v^n(x):\, x\in W\}$.

Let $x\in W$ be such that $v^n(x)=m$. Since $u^n(x)=v^n(x)=0$ for $x\in V_b$, then $x$ belongs to $V_0$. Let $z\sim x$ be such that

Hence,

from which $u^n(z)-v^n(z)\ge u^n(x)-v^n(x)=\delta$. It follows that $z\in W$ and, by $-w^{-1}_{zx}(v^n(z)-v^n(x))\ge \frac{1}{1-\rho^n(z)}> 0$, we get $m=v^n(x)>v^n(z)$, which is in contradiction with the definition of $m$.

In the next proposition, we give some regularity properties of $u^n$.

Proposition4.1.Let $u^n$ be the solution of (16). Then

where$d$ and $M$ are defined in (8) and (18), respectively.

Proof. Let $x\in V$ be. Then, for any $y\in V_b$ and for any $\gamma =\{x_0=x,x_1,\dots, x_N=y\}\in \mathcal G_{xy}$, by the inequalities in (18) we have

Therefore, the bounds (22) follow immediately.

Let $x\sim y$ and $\gamma=\{x_0=y,x_1,\dots, x_N=z\}\in \mathcal G_{yz}$ be, where $z\in V_b$ is an optimal path for $u^n(y)$. Then, $\{x, x_0,\dots, x_N=z\}\in \mathcal G_{xz}$ is a path connecting $x$ to $z\in V_b$ and, therefore,

which proves the property (23).

Let us define the following function on the graph $\Gamma$:

Then, the solution of (16) can be written as

(cf. with the formula (4) in the continuous case). Therefore, $u^n$ is the distance from the boundary taking into account the distribution of the population on the graph: the term $1/(1-\rho^n(y))$, which is the cost of passing from $x$ to $y$, penalizes the vertices adjacent to $x$ with high population density. The term $\textrm{sgn}(u^n(y)-u^n(x))$ in (9), which can be seen as the normalized discrete gradient of $u^n$, gives the direction of the minimizing path to the boundary. Moreover, if $\rho^n\equiv 0$, then $d_n$ coincides with the path distance $d$ defined in (8).

4.2.   The conservation law on graph

In this section we study the problem

where $h^n_{yx}$ satisfies (10)-(11), $\lambda$ is a positive constant and $\delta^n_{yx}$ is equal to 1 if the flux is directed from $y$ to $x$ and to $-1$ viceversa (for (9), $\delta^n_{yx}=\textrm{sgn}(u^n(y)-u^n(x))$). We rewrite equation (25) as

for a map $G:\mathbb{R}\times \mathbb{R}^{|V|}\to\mathbb{R}$.

Proposition 4.2.Let us assume

where $D$ is defined in (7) and $m$ in (11). Then, the map $G$ is monotone in $[0,1]$, i.e. if $\rho^n(x), \zeta^n(x) \in [0,1]$ for all $x\in V$, $n\in\mathbb{N}$, then

Proof. Observe that

We first prove that $\partial G/\partial \rho^n(y)\ge 0$ for $y\in I(x)$. This follows immediately by (11) and by the identity

Moreover, by (27) we have

and, therefore $G$ is increasing in $\rho^n(x)$.

Proposition 4.3.Let us assume that (27) holds and that $0\le \bar\rho(x)\le 1$ $\forall x\in V$. Then,

(ⅰ) $0\le \rho^n(x)\le 1$, $\forall x\in V$, $n\in \mathbb{N}$.

(ⅱ) If $0\le \bar\rho(x)$ and the inequality in (27) is strict, then $0\le \rho^n(x)$ $\forall x\in V$, $n\in \mathbb{N}$.

(ⅲ) $\sum\limits_{x\in V} \rho^n(x)= \sum\limits_{x\in V} \bar\rho(x)$, $\forall n\in \mathbb{N}$.

(ⅳ) $\sum\limits_{x\in V} |\rho^{n+1}(x)-\rho^n(x)|\le \sum\limits_{x\in V}| \rho^1(x)-\bar\rho(x)|$, $\forall n\in \mathbb{N}$.

Proof. By using (10), the monotonicity of the map $G$ and the following

it follows that

Hence, (i) holds.

If $D\lambda\|m\|_{L^\infty(0,1)}$, by (29) the map $G$ is strictly increasing in $\rho^n(x)$. Moreover, by (28), $G(1,\{\bar\rho(y)\}_{y\in I(x)})$ is the sum of terms non decreasing in $\bar\rho(y)$. Hence, if $0\le \bar\rho(x)$, then, for any $x\in V$,

and, iterating on $n\in\mathbb{N}$, we get (ⅱ).

To prove the equality in (ⅲ), we observe that

In fact, if $\delta^n_{yx}=1$, then $\delta^n_{xy}=-1$ and by (12) we have

We proceed similarly if $\delta^n_{yx}=-1$. Since for each $x\in V$ there is a corresponding node $y\in V$ for which 30) holds, we immediately get

Iterating the previous argument on $n\in\mathbb{N}$ we get (ⅲ).

To prove (ⅳ), we consider the case $n=1$ and we observe that

Moreover, by the monotonicity of $G$, see (i), and the mass conservation in (31), we can write

and similarly

By substituting the previous inequality in (32) we obtain

and, iterating, we get (ⅳ).

The term

represents the cumulative distribution of the population which has already reached the exit at the time $n$. Since if $x\in V_b$ then $\delta_{yx}^n=0$ $\forall y\in V_b$ with $y\sim x$, there is no flow inside the boundary. The assumption (11), which gives a bound on the maximal admissible velocity of the flux, is exploited in conjunction with the assumption (27) in order to get the monotonicity of the map $G$ introduced in (26). This property guarantees that pedestrians can move only of one vertex for unit time. Hence, people on not adjacent vertices of the graph cannot interact in a single time interval.

Remark 4.1. For the numerical simulation, we also consider a homogeneous Di-richlet boundary condition in place of the no-flux boundary condition (3). The corresponding conservation law on the graph is

If we denote with $\tilde \rho^n$ the solution of the previous problem and by $\rho^n$ the solution of (25), by the monotonicity of the scheme $G$ it is immediate to see that $\tilde \rho^n\le \rho^n$ for any $n\in\mathbb{N}$. Hence, also $\tilde \rho^n$ satisfies properties (ⅰ) and (ⅱ) in Prop. 4.3.

As an immediate consequence of the Proposition 4.3 and the assumption (17), we have the well-posedness of the Hughes model on a graph.

Corollary 4.1 Assume that $\lambda D\|m\|_{L^\infty(0,1)}$ and $0\le \bar\rho(x)$ $\forall x\in V$. Then the problem (9) is well-defined $\forall n\in\mathbb{N}$.

Proof. By Proposition 4.3(ⅱ) and the condition (17), the eikonal equation (16) is well-defined $\forall n\in \mathbb{N}$. It follows that also the conservation law (25) is well-defined $\forall n\in \mathbb{N}$.

5.   Numerical results for the Hughes model on graph

In this section we discuss the numerical implementation of the discrete Hughes system (9), which is considered as a discretization of the continuous Hughes system (6) on a graph $\mathcal G$. We introduce a time step $dt$ and a spatial step $dx$. The discretization of the edges of the network $\mathcal N$ is done uniformly with respect to $dx$ with the points of the discretization giving the vertices of the graph $\mathcal G$. The stability condition in (27) is verified if

being $\lambda = dt/dx$ in (25). The choice of the flux function $h$ is an important point. It is well known that a low order scheme gives poor accuracy on smooth regions of the solutions, conversely a high order scheme could develop spurious oscillations bringing to a high local error in non smooth regions of the solutions. We experimentally observed that a good compromise is represented by the Engquist-Osher flux (14).For this reason, from now on we will consider this form of the numerical flux $h$.In the resolution of the system (9), the conservation law is explicit in time, hence its computation does not present any difficulty. The resolution of the eikonal equation is more delicate and we consider a value iteration technique. Taken an initial guess $u_0(x)$, we iterate the explicit system

Under some non restrictive hypotheses (see [23]), such iteration is a contraction and converges monotonically for $k\rightarrow+\infty$ to the solution $u^n$ of (16). It has been shown the relevance of a good initial guess $u_0(x)$ to have a fast convergence (cf. [2]). A perfect candidate to play this role is the function $u^{n-1}(x)$ that is the solution of the discrete eikonal equation at the previous time step.

5.1.   Synthetic tests.

In this section we consider a simple network composed of five nodes and four edges (see Figure 1, left) discretized to a graph as described above.

The initial density $\bar \rho(x)$ (see Figure 1, right) is defined by the restriction on the graph of the function

The set of the boundary points $V_b$, i.e. the target points, is given by the vertexes in $(0.2,-0.8)$ and $(0.8,0)$, where $u^n$ is imposed equal to zero.

We will consider two possible cases for the boundary conditions (BCs) for the conservation law: the case with a no-flux condition (in such a case the mass is conserved inside the graph) and the case with a homogeneous Dirichlet condition on the target points (see Remark 4.1). Those BCs are {related} to a different choice of the model: the no-flux condition corresponds to target points where the crowd tends to concentrate, for example the stage of a concert, the various points of interest during the annual Hajj, see [1], etc. The homogeneous Dirichlet condition, instead, corresponds to target points which can be seen as exits of large dimensions: any mass touching them exits instantaneously from the graph.

First objective of this section is to show the stability of the discrete system: with this aim we consider a first order numerical flux as in (14). The case with a second order correction (stochastic perturbation adding diffusion) is more regular and it will be take into account in the next Test 3.

We perform the simulation fixing the discretization parameter $dx=0.01$ and the time step $dt=0.002$, hence the stability condition (27) is verified since we observe $\|m\|_\infty \leq 1-2\rho\leq 1$ and $dx/(D\,dt)=5/4$.

Test 1. We start considering the case of homogeneous Dirichlet boundary conditions. At the beginning of the simulation, the two initial masses start to move in the direction of the two target points acting as exits. The mass coming from the edge connecting $(0.2,0)$ to $(0.2,0.8)$ has a shorter path so it arrives on the junction node and it turns in direction of the closer exit $(0.8,0)$ (Figure 1). In Figure 2 it is possible to observe the first interaction time between the two masses: the arrival of the mass coming from the edge connecting $(-1,0)$ to $(0.2,0.8)$ produces a congestion near the exit $(0.8,0)$, therefore the other exit $(0.2,-0.8)$ becomes convenient as it is possible to observe in the graph of the drift potential $u$, see Figure 3 (below) and compare with Figure 2 (below). Therefore, the exit $(0.2,-0.8)$ attracts a part of the mass (Figure 3 above). This phenomena is peculiar of the Hughes model and it has been observed also in other works (see e.g. [20] or [14]). Once reached the target, the mass exits from the graph (Figure 3 above, on the exit $(0.8,0)$).

Test 2. In a second simulation we compute the same solution with the no-flux boundary condition. In this case, the mass is conserved. The first part of the test shows the same results as above: the masses are attracted by the target point $(0.8,0)$, but, differently {from the previous test,} the mass starts to concentrate, reducing its speed until the exit $(0.2,-0.8)$ becomes convenient. When also this second target point reaches its maximal value of the density getting congested, the mass reaches a stable configuration (Figure 4). In the case of a coarse time step $dt$, some oscillatory phenomena are observed in the second part of the test (chattering), where essentially the mass changes alternatively objective between the two target points. With a finer time discretization, those oscillatory effects are reduced till disappearing, we observe a convergence to the steady state configuration of Figure 4. {The study of a possible convergence to the solution of a stationary system (which would assume the form of a stationary mean field game [9]) is a question of sure interest and high difficulty that is, for the moment, out of the purposes of the present paper. This test confirms even more than the previous case the stability of the discrete system and the fact that the density is always strictly lower than the maximal value 1, even in the extreme case, when we force the mass to concentrate.

Test 3. As last simulation on this graph, we add to the conservation law a term of the type (15), which can be interpreted, from a model point of view, as a stochastic perturbation in the motion of the mass and, from an analytic point of view, as a second order regularizing term in the equation. In Figure 5 it is possible to see the effects of the diffusive term: the solution is more regular and congestion is not present. This is a phenomenon observed also in [11]: the presence of a stochastic noise prevents the mass to concentrate over a certain ratio. This has the indirect effect to help the overall evacuation time (i.e. the first time step where the density on the domain is null everywhere) for certain configurations of the system (we can observe this comparing Figure 3 with Figure 5). Avoiding congestion brings also some other macroscopic effects: in this case all the mass is exiting by the more convenient ''exit'' located in $(0.8,0)$. Since this arc is not getting congested, the agents do not change strategy using the other ''exit'' in $(0.2,-0.8)$.

5.2.   A stadium evacuation test

The stadium at the Wuhan Sports Centre (Fig. 6, left) is a multi-use stadium located in Wuhan, China. Completed in 2002, it was used as test benchmark for mass-evacuation in [15]. The stadium has 42 bleachers (tiers of seats) distributed on all 3 floors and has 9 exits for evacuation (Fig. 6, right); the capacity declared of the structure is of 54,357 spectators. Transforming a bit the structure (we consider all the edges on the same plane) the evacuation network in this stadium (Fig. 6, right) has 108 arcs and 63 nodes. After a uniform discretization of the arcs, the number of nodes of the graph is around $7\cdot 10^3$ with a similar number of connections.

The choice of the initial density configuration can be variable with respect to the aspect that we want to underline (by choosing a high initial uniform density distribution, we can test the graph in an extremely crowded scenario; a random density choice can simulate some not standard cases of anomalous local concentration of crowd; etc.). In this test, we chose the following initial datum

(we always mean the restriction of such function on the nodes of the graph), this distribution in our intention should render the higher concentration of spectators in the areas closer to the court. We approximate uniformly the arcs using the discretization step $dx=0.01$ and we sample the time with $dt=0.002$. Also in this case the condition (27) is guaranteed (the maximum number of connections per node $D$ is $5$) and the scheme is stable. In Figure 7 we can see the initial distribution of the density and the potential driving the individuals toward one of the exits. In Figure 8 it is shown the evolution of the system in various moments. We can notice that, despite the general symmetry of the structure, the behavior is highly conditioned by the position and the number of the exits. Of particular interest is the difference between the evacuation of sectors A/B and C/D (refer to Fig. 6). As it can be seen from the scheme, the sector A is served by only one exit, differently from C, where two exits are present. Analogously, the sector D has 4 exits conversely to sector B which has just two. This brings to an orderly and efficient evacuation in the sectors C/D, with a well balanced use of the exits available. In the other case (sector A/B), the observed dynamics are different: on the paths toward the only three exits, in proximity to some nodes with multiple access, there are the appearance of high density congested regions. We can observe also some of the phenomena discussed previously: reduction of the speed in the congested regions, changes of strategy, doubtful choice between two strategies (chattering). This has the macroscopic effect to rise up the final time necessary to evacuate the regions involved as we can observe in the last samples of Figure 8: the sectors C/D are already empty, the sectors A/B, instead, show congestion and a laborious flow through them. It is interesting to observe that a more efficient (for evacuation purposes) graph is not trivially a graph with more exits but a structure that avoids to drive big masses of agents to pass at the same time in the same nodes. This is a consequence to the incapacity of the agents represented in the model to forecast the future configuration of the system in order to choose the best strategy to adopt. For those reasons, the model is particularly appropriate to simulate the behavior of a crowd in a known graph in presence of unpredicted events (an evacuation order, unusual high concentration in common transport facilities, etc.).

6.   Conclusions.

In this paper we have presented a discrete Hughes model for pedestrian flow on a graph. We have shown that, differently from the analogous continuous model on a network, this discrete model is well-posed for any time $n\in \mathbb{N}$ under some natural assumptions on the flux, continuing to share some qualitative properties with the corresponding continuous model, as the interpretation of the solution of the graph eikonal equation as a distance from the boundary, change of strategies, congestion, etc.

Several tests have been shown, analyzing and comparing the results and the behaviors obtained with different conditions (no BCs, homogeneous Dirichlet BCs or adding a diffusive term). The experimental examples have confirmed the validity of the proposed model, showing that the discrete system is always stable, even in the extreme case, when we force the mass to concentrate.