Delphine Lelièvre

Catherine Poupon

Jeanne Loïc

Je tiens tout d'abord à remercier profondément mon directeur de thèse Bertrand Maury.

Merci de m'avoir proposé un sujet de thèse si passionnant et si original. J'ai beaucoup appris pendant ces trois ans de thèse, et cela est grâce à ton enthousiasme, tes conseils et ton aide que j'apprécient beaucoup. Merci aussi pour ta bonne humeur et ta disponibilité qui ont contribué au bon déroulement de cette thèse. Je suis très honorée que Guillaume Carlier et Pierre Degond aient accepté de rapporter mon manuscrit de thèse. Je vous remercie pour votre lecture soigneuse et pour l'intérêt que vous avez porté à mes travaux. Je souhaite également remercier Cécile Appert-Rolland, Adrien Blanchet et Quentin Mérigot d'avoir accepté de faire partie de mon jury. Depuis mon arrivée à Orsay en Septembre 2013, j'ai toujours été entourée par des personnes sympathiques et aimables. Je remercie tous les membres de l'équipe Équations aux Dérivées Partielles et Analyse Numérique. Je remercie particulièrement Filippo Santambrogio de m'avoir donné la chance de faire mon Master 2 à Orsay et pour les nombreuses discussions qu'on a eues.

Résumé détaillé

Cette thèse porte sur la modélisation de mouvement de foules. Il existe une grande variété de modèles de mouvement de foules, qui peuvent être classifiés selon différents critères. La classification la plus connue des modèles est basée sur la représentation de la foule: microscopique pour les modèles où les individus sont représentés par des disques ou des ellipses et leur comportement est décrit par une Equation Différentielle Ordinaire, et macroscopique où la foule est représentée par une densité qui évolue selon une Equation aux Dérivées Partielles.

Les modèles de mouvement de foules peuvent aussi être classifiés selon le type de dynamique: déterministe si deux individus se comportent exactement de la même manière quand ils sont dans la même situation, et stochastique sinon. La prise en compte de la congestion peut s'effectuer de deux manières différentes, soit l'approche soft qui consiste à appliquer des forces d'interaction à courte portée, soit l'approche hard où chaque individu ne réagit à la présence d'un autre que quand ils sont en contact. Il existe aussi deux types d'interactions entre les individus: les interactions basées sur un processus de décision où chaque individu est considéré capable d'optimiser sa trajectoire en fonction d'observation locale ou globale, et les interactions basées sur un processus mécanique où la foule est représentée par un système de particules physiques réagisssant entre elle par des forces mécaniques.

Le modèle

Dans cette thèse, nous développons un modèle microscopique basé sur la théorie des jeux où les individus sont considérés civilizés et aptes à percevoir leur environnement et à optimiser leurs trajectoires selon certaines préférences et contraintes. Nous suivons l'approche hard pour la prise en compte de la congestion et nous présentons un modèle déterministe. Les individus sont représentés par des disques et chaque individu est influencé par certains voisins (pas nécessairement tous, en pratique ceux qui sont dans son cône de vision). Les relations d'influence entre les individus sont représentés par un graphe: les individus sont les noeuds du graphe et une arrête orientée va d'un individu vers un autre s'il est influencé par lui. Chaque individu a une certaine vitesse souhaitée, c'est la vitesse qu'il souhaite avoir s'il était tout seul, et il est assujetti à respecter une contrainte de non-chevauchement avec les individus qui l'influencent. Nous supposons que chaque individu adapte sa vitesse souhaitée en fonction de l'environnement en suivant un processus de décision personelle. Chaque individu choisit une vitesse qui soit la (parmi les) plus proche(s) possible(s), au sens des moindres carrées, de sa vitesse souhaitée en tenant compte des positions et des vitesses choisis par les individus qui l'influencent pour éviter les collisions. En d'autres termes, les vitesses choisis par les individus doivent former un équilibre de Nash instantané: chaque individu fait son mieux par rapport à un objectif personnel (vitesse souhaitée), tenant compte des positions et des comportements choisis par les individus qui l'influencent. Nous appelons champs de vitesses équilibrées tout champs de vitesses qui réalise un équilibre de Nash.

L'étape de décision est suivie par une étape de correction qui consiste à projeter le champs de vitesses équilibrées choisi sur l'ensemble de champs de vitesses globalement admissibles (qui n'autorisent pas un chevauchement des disques représentant les individus). En fait, dans le cas où le graphe d'influence n'est pas complet (un individu peut ne pas être influencé par un de ses voisins), les vitesses équilibrées peuvent ne pas être globalement admissibles. Cette manière de traiter les contacts physiques est basée sur un principe mécanique, et est inspirée du modèle de mouvement de foule purement granulaire de Maury et Venel [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF].

Le modèle est décrit en détail au deuxième chapitre où nous considèrons le problème de trouver un champs de vitesses équilibrées compatibles avec les exigences mentionnées ci-dessus (l'étape de projection a été étudié dans [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF]). Nous abordons la question d'existence et Indépendamment de la modélisation de mouvement de foule, nous cherchons au Chapitre 6 à établir un lien entre un schéma de type Volumes Finis pour l'équation de Fokker-Planck et un cadre flot gradient par rapport à une distance de type Wasserstein discrète récemment introduite dans [START_REF] Disser | On gradient structures for Markov chains and the passage to Wasserstein gradient flows[END_REF][START_REF] Maas | Long-time behavior of a finite volume discretization for a fourth order diffusion equation[END_REF]. Finalement, une conclusion et quelques perspectives sont décrites au Chapitre 8.

Formulation mathématique du modèle

Nous considèrons N individus et nous notons par q i ∈ R d , d = 1, 2, la position de l'individu i et par U i (q i ), noté U i pour des raisons de simplicité, sa vitesse souhaitée. La configuration de tous les individus est notée par q = (q 1 , . . . , q N ) ∈ R dN . Les individus sont représentés par des disques de centres q 1 , . . . , q N et de rayons r 1 , . . . , r N respectivement, contraints à respecter une contrainte de non-chevauchement. En d'autres termes, la configuration des individus doit 2 CONTENTS appartenir à l'ensemble de configurations admissibles suivant: K = q ∈ R dN , D ij (q) ≥ 0, ∀i ̸ = j où D ij (q) = |q iq j |r ir j est la distance entre les individus i et j. Considèrons une configuration admissible q ∈ K, nous appelons un champs de vitesses équilibrées, qu'on note u(q) = (u 1 , . . . , u N ), tout champs de vitesses qui réalise un équilibre de Nash instantané: la vitesse de chaque individu doit être la plus proche possible de sa vitesse souhaitée parmi toutes les vitesses qu'il considère comme possible, tenant compte des positions et vitesses des individus qui l'influencent. Le fait que les contraintes sur la vitesse d'un individu dépendent des vitesses des autres ne définit pas proprement un champs de vitesses, mais définit plutôt un ensemble (possiblement vide) de champs de vitesses compatibles avec ces exigences.

q i q j D ij e ij -e ij
Nous notons par Λ l'ensemble des champs de vitesses u = (u 1 , . . . , u N ) tels que:

u i = argmin w∈R d 1 2 |w -U i | 2 + I C i (q,u -i ) (w), ∀i = 1, . . . , N (1)
où

C i (q, u -i ) = w ∈ R d , ∀j ∈ I i , D ij (q) = 0 ⇒ e ij (q) • (w -u j ) ≤ 0 , (2)
I C i (q,u -i ) est la fonction indicatrice de l'ensemble C i (q, u -i ), avec la notation usuelle u -i = (u 1 , . . . , u i-1 , u i+1 , . . . , u N ) et e ij (q) = (q jq i )/|q jq i |.

L'ensemble de champs de vitesses globalement admissibles est défini par:

C(q) = v = (v 1 , . . . , v N ) ∈ R dN , ∀j ̸ = i, D ij (q) = 0 ⇒ e ij (q) • (v i -v j ) ≤ 0 . ( 3
)
Dans le cas où un champs de vitesses équilibrées existe, nous définissons le champs de vitesses réelles comme la projection euclidienne du champs de vitesses équilibrées sur C(q).

Commençons par quelques remarques sur l'approche Nash utilisée pour définir le champs de vitesses équilibrées:

• Dans la définition formelle d'un équilibre de Nash général, la fonctionnelle coût n'a pas de valeurs infinies. Pour le cas du problème qu'on considère, nous supposons qu'une vitesse u i non admissible (n'appartenant pas à C i (q, u -i )) est possible mais infiniment insatisfaisante. En d'autres termes, un individu peut choisir une vitesse non admissible si et seulement si c'est le seul choix possible pour lui.

• Nous allons voir que les équilibres de Nash ne sont pas uniques en général, même l'existence n'est pas tourjours guarantie, ce qui nous empêche pour l'instant de parler de problème d'évolution.

Étude théorique du modèle

Nous considèrons deux cas particuliers de graphe d'influence: le cas d'un graph complet (chaque individu peut être influencé par tous ses voisins), et le cas d'un graph dirigé acyclique où les relations d'influence entre les individus sont structurés d'une manière hiérarchique.

Cas d'un graphe complet

min v∈C(q) 1 2 (v -U ) • M (v -U ), (4)
où C(q) est défini par (3), a une unique solution qui est une solution particulière du Problème [START_REF] Reda | Interpretation of Finite Volume discretization schemes for the Fokker Planck equation as gradient flows for the discrete Wasserstein distance[END_REF].

Ce procédé constructif de détermination de solutions au Problème 1 permet d'obtenir plusieurs solutions. En plus, ce procédé est basé sur des principes mécaniques (en fait ce n'est que le modèle granulaire introduit dans [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF]), et donc la loi d'action et de réaction est automatiquement satisfaite: cette démarche est exclusive au cas complet.

Nous montrons à la Proposition 2. l'inclusion est stricte en dimension deux, ce qui veut dire que certains équilibres de Nash sont véritablement de type théorie des jeux et ne peuvent être construits par un procédé mécanique. Idée de la preuve: Nous utilisons le tri topologique qui permet de numéroter les noeuds d'un graphe dirigé acyclique de la façon suivante: j > i si et seulement si une arrête orientée va de i vers j. Pour des raisons de simplicité, nous supposons que les individus sont numérotés selon le tri topologique. L'individu qui porte le numéro N ira à sa vitesse souhaitée, ensuite pour chaque individu i, pour i = N -1, . . . , 1, la vitesse équilibrée de i est la solution d'un problème de minimisation qui dépend des vitesses équilibrées de N, . . . , i -1 qui ont déjà été calculées.

Cas d'un graphe hiérarchique

Remarquons que cette manière de calculer une solution unique au problème n'est possible que si les ensembles C i (q, u -i ) sont non vides pour tout i (les u -i étant déjà calculés grâce à la structure hiérarchique).

En pratique, nous considèrons les situations d'évacuation où les ensembles d'influence des individus sont leurs cônes de vision définis par:

V (q i , U i , α, l) = x ∈ R 2 , (x -q i ) • U i ||x -q i || ||U i ||
≥ cos α and ||xq i || ≤ l .

où α est l'angle de vision et l est la longueur du cône de vision. Dans ce cas, le graphe d'influence est hiérarchique si la condition suivante est satisfaite:

||∇U || 2 < cos α max i r i ,
et les ensembles C i (q, u -i ) sont automatiquement non vides. Sous cette condition, le problème admet donc une unique solution (application directe de la Proposition 3.2.2).

Nous appelons modèle hiérarchique ce cas particulier du modèle de Nash instantané qui sort du cadre de la théorie des jeux. Dans le cas où le graphe d'influence est basé sur les cônes de vision des individus, le modèle hiérarchique décrit bien les situation d'évacuation où les individus souhaitent se diriger vers la même cible.

Cas général

Dans le cas d'un graphe d'influence qui contient des cycles, l'approche représente des difficultés en terme de détermination de champs de vitesses réelles. En fait, la théorie classique d'existence d'équilibres de Nash généraux ne s'applique pas à ce problème à cause de la forme particulière de la fonctionnelle coût. Les résultats d'existence exigent par exemple la continuité des fonctionnelles coût comme dans [START_REF] Debreu | A social equilibrium existence theorem[END_REF][START_REF] Irving | A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points[END_REF][START_REF] Ky | Fixed-point and minimax theorems in locally convex topological linear spaces[END_REF], leurs majorations et minorations [START_REF] Dasgupta | The existence of equilibrium in discontinuous economic games, I: Theory[END_REF], ou la semi-continuité de la dépendence des ensembles de stratégies admissibles pour un individu sur les stratégies des autres [START_REF] Kenneth | Existence of an equilibrium for a competitive economy[END_REF]. Même dans les cas où un équilibre de Nash existe, quand le graphe d'influence contient des cycles on n'a pas a priori d'unicité de solutions au Problème [START_REF] Reda | Interpretation of Finite Volume discretization schemes for the Fokker Planck equation as gradient flows for the discrete Wasserstein distance[END_REF] et des outils doivent être développés afin de choisir un équilibre de Nash parmi les équilibres existants. Ceci demande une description psychologique fine des interactions entre les individus (politesse, agressivité, capacité à élaborer des stratégies basées sur des prédictions,. . . )

Simulations numériques du modèle hiérarchique

Nous proposons un schéma numérique pour approcher l'unique solution du modèle hiérarchique, basé sur un développement à l'ordre un des contraintes sur les vitesses comme proposé dans [START_REF] Maury | A time-stepping scheme for inelastic collisions[END_REF].

Pour un temps t 0 = 0 donné, notons par τ > 0 le pas de temps et t n = nτ une subdivision d'un intervalle [0, T ] où T est fixé. À chaque instant t n , nous calculons le champs de vitesses réelles u n des individus en deux étapes (décision et correction), toutes les deux basées sur un développement à l'ordre un des contraintes sur les vitesses.

Considérons un individu i, pour tout j ∈ I i , si i prend la vitesse w pendant un temps τ , le développement à l'ordre 1 de D ij (q n + τ v) est

D ij (q n + τ v) = D ij (q n ) + τ ∇D ij (q n ) • v + o(τ ), = D ij (q n ) + τ e ij (q n ) • (ũ n j -w)
qui est une expression affine qui dépend des vitesses u n j déjà calculées grâce à la numérotation CONTENTS hiérarchique. Nous imposons simplement à cette expression d'être positive.

L'approximation de la solution se fait en deux étapes:

Première étape

Nous déterminons la solution de chacun des problèmes de minimisation suivants en suivant l'ordre du tri topologique i = N, N -1, . . . , 1:

ũn+1 i = argmin w∈C τ i (q n ,ũ n -i ) 1 2 |w -U i (q n i )| 2 où C τ i (q n , ũn -i ) = w ∈ R d , ∀j ∈ I i (q n ), D ij (q n ) + τ e ij (q n ) • (ũ n j -w) ≥ 0 .
Notons que, grâce à la structure hiérarchique, tous les indices j correspondent à des individus qui ont déjà choisis leurs vitesses équilibrées ũn j .

Processus ------→

Deuxième étape

Le vecteur de vitesses équilibrées ũn+1 est projeté sur l'ensemble des vitesses globalement admissibles:

u n+1 = argmin v∈C τ (q n ) 1 2 |v -ũn | 2 C τ (q n ) = v ∈ R dN , ∀j ̸ = i, D ij (q n ) + τ e ij (q n ) • (v j -v i ) ≥ 0 .
où l'expression D ij (q n ) + τ e ij (q n ) • (v jv i ) est de nouveau un développement à l'ordre 1 de

D ij (q n + τ v).

Confrontation des résultats numériques avec des expériences réelles d'évacuation

Nous proposons de comparer les résultats numériques pour le modèle hiérarchique avec des expériences d'évacuation réelles décrites dans [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF][START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF]. Pour faire cela, nous lançons des simulations numériques en situation d'évacuation en périodique (un individu qui sort de la pièce est réinjecter à une position aléatoire à l'entrée de la pièce, voir • Loi de puissance des temps entre deux sorties consécutives: Comme proposé dans [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF],

nous traçons le complémentaire de la fonction de répartition des intervalles de temps entre deux sorties (qui est 1 moins la fonction de répartition) en échelle log-log. Nous remarquons l'apparition d'une loi de puissance pour les temps longs. Cette loi de puissance a été observée pour les expériences décrites dans [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF] avec des exposants assez proches pour les expériences et les simulations numériques du modèle hiérarchique(voir

Introduction

General introduction

Pedestrian crowds have been studied empirically over more than five decades by many researchers. Some of these empirical studies are devoted to develop a level-of-service concept [START_REF] John J Fruin | Design for pedestrians: A level-of-service concept[END_REF], others to design pedestrian facilities [START_REF] Pauls | The movement of people in buildings and design solutions for means of egress[END_REF] or to write guidelines [START_REF]Highway Capacity Manual[END_REF]. Many researchers have also been interested in describing the relation between the speed of pedestrians and their density [START_REF] Bd Hankin | Passenger flow in subways[END_REF][START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF][START_REF] Fang | On the relationship between crowd density and movement velocity[END_REF]. These empirical data permitted researchers to deduce some properties of the behavior of pedestrians and describe some effects commonly observed in crowd motion. A complete review about characteristics of pedestrians can be found in [START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF][START_REF] Buchmueller | Parameters of pedestrians, pedestrian traffic and walking facilities[END_REF] and a survey about empirical observations is presented in [START_REF] Michael | Walking, crossing streets and choosing pedestrian routes: A survey of recent insights from the social/behavioral sciences[END_REF].

An important tool to evaluate the safety of pedestrian facilities and predict pedestrian behavior is crowd motion modeling. The first model was originated in the '70s and the subject began to attract the attention of many researchers. Nowadays, there exists a wide variety of crowd motion models describing different situations from everyday life, emergency situations, special events, etc... These models can be classified according to many criteria, here are some examples of classifications:

• Representation of individuals: microscopic or macroscopic -Microscopic models represent each pedestrian as an agent occupying a certain space at a certain time. The movement of each pedestrian is described by an Ordinary Differential Equation using its position and velocity. In this approach, each individual tries to reach his destination while taking into consideration the movement of other pedestrians and the presence of obstacles. One of the main advantages of this class of models is the possibility to take differentiated interactions between individuals into consideration, and this is what makes microscopic models more flexible. But this advantage does not come without cost, implementing microscopic models for large crowd is computationally expensive.

-For macroscopic models, the crowd is represented by a density in pers/m 2 that evolves through a Partial Differential Equation. These models are convenient when dealing with a large crowd since the number of involved pedestrians has no influence on computational times, but they are less flexible than microscopic models in general.

• Dynamics of the equations: deterministic or stochastic -For models with deterministic dynamics, the behavior of individuals depends on the current or the past situations, and two pedestrians behave exactly in the same way when they are in the same situation.

-For models with stochastic dynamics, the behavior of the crowd is based on some probabilities that make it possible for two pedestrians in the same situation to behave differently. Among stochastic models, some of them are made by adding noise to the variables like the position or the velocity, and others are intrinsically stochastic like the cellular automata models where the movement of pedestrians is based on probabilities (cf. Chapter 1).

• Congestion handling: soft approach or hard approach -The soft approach consists in applying short range interaction forces between individuals. Most of the existing models are of the soft approach type, individuals anticipate collision and slow down or deviate from their course before the occurring of contact.

-The hard approach treats contacts as non-smooth events. It models individuals in a hurry wishing to go at their desired velocity as long as possible and so they only adapt their movement when contact (or quasi-contact) occurs.

• Accounting for interactions: mechanical setting or decision process -The mechanical class contains models based on a representation of the crowd as a system of physical particles, interacting through forces of the mechanical type.

These models are mostly inspired from physical principles as interaction forces, kinetic theory and thermodynamics.

-The decision making class is for all those approaches that are based on a representation of agents as active entities in the sense that the effective action of each one of them results from a decision process based on local or global observations. Individuals are no longer treated as passive particles submitted to general laws, but rather as entities able to take decisions at their very own level.

A state of the art about crowd motion modeling is presented in the first chapter of this thesis.

We also propose some crowd motion models in Chapters 2, 3 and 5.

Description of the proposed models

We propose in this thesis crowd motion models based on hard congestion handling. We consider civilized pedestrians able to perceive their environment and take decisions to optimize their trajectories according to some preferences and constraints. The proposed models belong to the following classes according to the aforementioned classification: deterministic dynamics, hard congestion handling, based on a decision making process.

First, we propose a microscopic model based on game theoretic principles. Individuals are represented by disks and each one of them has a desired velocity, it is the one he would like to have in the absence of others. An individual is not necessarily influenced by all his neighbors, notably in real-life situations we are mainly influenced by the ones we see. We represent the influence relations between individuals by a directed graph: each individual is a node of the graph, and a directed edge goes from an individual to another one if he is influenced by him. The determination of the actual velocity of the crowd, that is the adaptation of the desired velocity according to the environment (individuals, obstacles,. . . ), is done through an individual decision process. Individuals are considered as thinking entities, each one of them chooses an actual velocity that approaches best, in the least squares sense, his desired one taking into consideration the positions and the chosen velocities of other individuals that influence him to avoid collisions.

The problem is formulated in a generalized Nash game framework and some theoretical questions are addressed. Two particular cases of influence graph are investigated: the case of a complete influence graph (each individual is influenced by all the others), and the case of a directed acyclic graph (hierarchical interactions between individuals). For the first case, we give a constructive proof of existence of Nash equilibria. We also show that, in some cases, there is no uniqueness of solutions and we describe the set of Nash equilibria. Indeed, the approach shall not lead in general to an evolution model in a strict sense. For the case of a directed acyclic influence graph, we show existence and uniqueness of solutions, which makes it possible to talk about an evolution model. The Nash equilibrium model with hierarchical influence graph will be called the hierarchical model since, as we shall see, in this particular case the game theoretical aspects disappears. We pay a particular attention to evacuation situations where the influence graph of individuals based on their cones of vision (each individual is influenced by others he sees) is natively hierarchical.

We propose a numerical strategy to solve the hierarchical model and perform some numerical simulations. The numerical results are confronted with real evacuation experiments.

Precisely, some comparison tests are done in order to investigate whether the hierarchical model based on the cones of vision is able to reproduce some crowd effects observed in evacuation experiments.

We also propose in this thesis to write a macroscopic counterpart of the hierarchical model based on the cones of vision. The whole crowd is represented by a density and is supposed to have a desired velocity field that corresponds to individuals' preferred motion. At every point of the domain, we associate to the desired velocity a cone of vision centered in the same direction. Two approaches are proposed. The first one is obtained by roughly translating the modeling principles of the hierarchical model to the macroscopic level. The actual velocity field is defined as the closest to the desired one among velocity fields that do not increase the density in the already saturated zones and the velocity correction (difference between the actual velocity and the desired one) should belong to the opposite of the cones of vision. The second approach consists in relaxing the directional condition related to the cones of vision by considering a family of minimization problems whose solution is expected to converge to a macroscopic counterpart of the hierarchical solution. We lay out some questions related to these approaches and make the first steps towards writing such models.

Independently of the crowd motion modeling, we present some developments in establishing a link between the continuous gradient flow framework in continuous Wasserstein spaces and a recently introduced discrete gradient flow framework in discrete Wasserstein spaces. At the continuous level, it is known that the Fokker-Planck equation can be interpreted in the Wasserstein space as the gradient flow for the relative entropy functional with respect to a specific stationary measure (coming from the potential in the Fokker-Planck equation). At the discrete level, a similar framework has been proposed where the euclidean domain is replaced by a network. A discrete heat equation on the network is defined using a Markov kernel, and is interpreted in a discrete Wasserstein space as a gradient flow for a discrete relative entropy with respect to the stationary measure of the Markov kernel. Our goal is to investigate the link between the continuous framework and the discrete one. We show in this thesis that a space discretization of the Fokker-Planck equation using a Finite Volume scheme leads to an Ordinary Differential Equation that can be interpreted as a discrete Heat equation on the underlying network for a Markov kernel. The resulting discrete Heat equation is consistent with the gradient flow structure in the discrete Wasserstein space.

Structure of the thesis

The first chapter is devoted to the description of the state of the art. We start by recalling some existing crowd motion models: the social force model, models based on anticipating behavior, the granular model, network models, fluid dynamics models, hyperbolic conservation law models, models based on game theoretic principles, the macroscopic model based on hard congestion constraint and cellular automata models. Then, we recall some known data (body dimensions and walking speed) and empirical results on the flow rate of placid pedestrians.

We end this chapter by a review on some crowd motion effects, notably: the Faster is Slower effect, the zipper effect, the capacity drop, the effect of the presence of an obstacle on the fluidity of evacuations, the stop-and-go waves and the formation of lanes in multidirectional flows.

In Chapter 2, we introduce the principles of the instantaneous Nash equilibrium model.

We write its mathematical formulation and pay particular attention to the case of complete influence for which we prove existence of solutions that are not unique in general. We also describe the set of solutions and give a constructive procedure to build solutions. Some remarks are given for the case of a general influence graph.

We consider in Chapter 3 the particular case of the Nash equilibrium model where the influence graph is directed and acyclic, that we call hierarchical model. We prove existence and uniqueness of solutions and describe the procedure used to build the solution. We also consider the case where the influence graph is based on the cones of vision of individuals and provide a sufficient condition in evacuation cases so that the influence graph is directed and acyclic. We end this chapter by describing a numerical scheme to solve the model and we give CONTENTS a comparison between the hierarchical model and the granular model recalled in Chapter 1.

Chapter 4 is devoted to the confrontation of the numerical results of the hierarchical model with empirical data. We describe in the first section of this chapter the evacuation experiments involved in the comparison and the performed numerical simulations. For the comparison between numerical simulations and controlled evacuation experiments, we are especially interested in two effects observed when looking to the time lapses between consecutive egresses: the alternation between short and long time lapses and their power-law distribution.

Then, we show the ability of the hierarchical model to reproduce some crowd motion effects known in the literature that are: the Faster is Slower effect, the beneficial effect of an obstacle upon evacuation fluidity and the capacity drop phenomenon.

In Chapter 5, we describe first the transition from the granular model to its macroscopic counterpart (both described in Chapter 1) by considering the same modeling principles. Then, we introduce a macroscopic counterpart of the hierarchical model in the spirit of the transition from the granular model to its macroscopic counterpart. We prove the well-posedness of the instantaneous model and propose a numerical strategy to solve the problem. An example of numerical simulation for this model is also displayed. A second approach is also discussed in this chapter. A family of minimization problems depending on a parameter are introduced by relaxing one of the conditions of the previous approach. The sequence of minimizers is shown to converge to a macroscopic counterpart of the microscopic hierarchical solution in dimension one, and the case of dimension two is still under current investigation.

Finally, we start Chapter 6 by reviewing the gradient flow framework of the Fokker-Planck equation with respect to the continuous Wasserstein distance. We recall the discrete Wasserstein distance on graphs and a convergence result of this discrete metric to its continuous counterpart. We introduce then a Finite Volume discretization of the Fokker-Planck equation in space. The resulting Ordinary Differential Equation is shown to be the gradient flow of the discrete relative entropy functional with respect to the discrete Wasserstein distance.

Chapter 1

State of the art

Existing models

In this section, we recall some existing crowd motion models that have been studied over the last five decades. It is actually difficult to propose a structured classification since many criteria can be used (microscopic or macroscopic, deterministic or stochastic,... see the Introduction for more details). The list is for sure non-exhaustive but we try to give at least one example for each criterion of the classifications mentioned in the Introduction.

The social force model

The social force model is a microscopic model introduced by Helbing and Molnár in [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF], based on a system of inertial particles interacting through so-called social forces. Each individual is represented by a disk of center q i and radius r i and his velocity u i evolves according to the Ordinary Differential Equation:

du i (t) dt = F i (t)
where F i (t) is the sum of all forces exerted on the individual i at time t. The term F i (t) is composed of different physical forces that describe interactions between individuals (repulsion force), an individual and a wall or an obstacle (repulsion force) and his own will to move in his desired direction and at his desired speed (acceleration force). The acceleration force term is of the following form:

U i e i (t) -u i (t) τ i
where U i is the desired velocity, e i (t) is the desired direction of motion and τ i is a relaxation time. The repulsive force between two individuals i and j reads:

⃗ f ij (q) = -∇ q ij V ij (b(q ij ))
where 2 and s j = v j ∆ t is the order of the step width of pedestrian j. After this seminal work, this model has been developed in many directions. For example, an element of asymmetry has been included to account for cones of vision, but the very philosophy remains based on mutual interaction forces which mimic mechanical interactions. This model has also been generalized in [START_REF] Chraibi | Generalized centrifugal-force model for pedestrian dynamics[END_REF] where individuals are no longer represented by discs but rather by ellipses and the reaction field of the forces is reduced to the cone of vision. The macroscopic limit of the social force model is computed in [START_REF] Kretz | The Inflection Point of the Speed-Density Relation and the Social Force Model[END_REF] in dimension one.

q ij = q i -q j , b(q ij ) = (1/2) (|q ij | + |q ij -s j e j |) 2 -(s j )

Models based on anticipating behavior

The Follow-the-Leader model [START_REF] Argall | A rigorous treatment of a follow-the-leader traffic model with traffic lights present[END_REF] is a one dimensional microscopic model of the decision making type, based on a speed that decreases with the inter-individual distance. Consider N individuals and denote by x i (t) the position of individual i at time t, we suppose that:

x 1 (t) < x 2 (t) < • • • < x N (t)
The velocity of individual i depends on the distance to the individual in front of him, i.e. on

x i+1x i , and the positions evolve according to:

ẋi = φ i (x i+1 -x i ), i = 1, . . . , N
where φ i (d) is a increasing function. An example of φ is:

φ i (d) = U i 1 -exp - d -d m d s (1.1)
where U i is the desired velocity of i, d s is a characteristic security distance and d m is the length of the interval representing an individual. An example of function φ is displayed in Figure 1.1. The leader of the file is individual N who goes at his desired velocity and each agent reduces its speed in order to prevent collision in case the person in front of him suddenly stops. An extension of this model is described in [START_REF] Fehrenbach | Time-delayed Follow-the-Leader model for pedestrians walking in line[END_REF] where the authors introduced a time delay in the Follow-The-Leader model. This modification is done after performing some controlled experiments of pedestrians walking in a circular domain without passing each other, where the authors observed a delay in the response of an individual when the behavior of his predecessor changes.

More sophisticated anticipation processes have also been proposed. For example, a cognitive model was proposed by Moussaid et al. [START_REF] Moussaïd | How simple rules determine pedestrian behavior and crowd disasters[END_REF] based on behavioral heuristics where individuals try to avoid collision with others by adapting the direction of their velocity and keeping a safety distance to others. In [START_REF] Degond | Visionbased macroscopic pedestrian models[END_REF], each individual is supposed to choose a cruising direction such that, after a fixed time interval, his estimated point reached in this direction is the closest to his target point, among all directions belonging to his cone of vision. A similar approach has also been proposed in [START_REF] Ondřej | A synthetic-vision based steering approach for crowd simulation[END_REF], where individuals choose a velocity direction belonging to their cone of vision to avoid collision until a certain threshold of distance-to-interaction, and then decelerate.

Granular model

The granular model has been introduced by Maury and Venel in [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF] and is based on hard congestion handling. Each individual i is represented by a rigid disk of center q i and radius r i , and the configuration of individuals is denoted by q = (q 1 , . . . , q N ). The model is based on two principles:

• Each individual i has a desired velocity denoted by U i (q), it is the one he would like to have in the absence of others,

• Disks representing individuals should satisfy a non-overlapping constraint. More precisely, the configuration of individuals is constrained to belong to a set of admissible configurations defined by:

K = q ∈ R 2N , D ij (q) ≥ 0, ∀i ̸ = j
where D ij (q) = d(q i , q j )r ir j is the distance between individuals i and j.

The actual velocity field u(q) is defined as the closest, in the least square sense, to U (q) among all admissible velocities which do not allow an overlapping of disks representing individuals.

Admissible velocities are described by the set:

C(q) = v ∈ R 2N , ∀i ̸ = j, D ij (q) = 0 ⇒ e ij (q) • (v i -v j ) ≤ 0
where e ij (q) = (q jq i )/|q jq i | and the problem reads:

u(q) = P C(q) U (q)
where P C(q) is the euclidean projection operator on C(q). Although this equation seems quite simple, the proof of well posedness of the evolution problem shows some difficulties since the set of admissible velocities C(q) does not depend smoothly on the configuration q. The proof calls on some tools from Convex Analysis. First, the problem is reformulated as a differential inclusion using sweeping processes introduced by Moreau [START_REF] Jacques | Evolution problem associated with a moving convex set in a Hilbert space[END_REF] and then the theory in [START_REF] Fenel | Relaxation of an optimal control problem involving a perturbed sweeping process[END_REF][START_REF] Fenel | BV solutions of nonconvex sweeping process differential inclusion with perturbation[END_REF] is used to prove existence and uniqueness of solutions. Further details on the theoretic study of the problem can be found in [START_REF] Maury | A discrete contact model for crowd motion[END_REF][START_REF] Venel | Modélisation mathématique et numérique des mouvements de foule[END_REF].

The granular model is based on mechanical interactions: individuals are considered as grains interacting through physical forces. The interactions between individuals are symmetric in that case and the law of action and reaction holds. That means pedestrians are allowed to push each other when their desired velocities lead them to overlap. The behavior of individuals in the granular model is justified in the case of highly congested crowds where mechanical forces are exerted at the level of physical contact between individuals.

Network models

In these models the space is represented by a network and each individual occupies a node of it. Individuals can move from a node to another one when the nodes are linked by an oriented edge going from the first node to the second one. For some of them, called Route choice models, the way pedestrians chooses to move is calculated deterministically, for example, the chosen paths are the shortest ones among all paths that link the sources and the destinations as in [START_REF] Borgers | City centre entry points, store location patterns and pedestrian route choice behaviour: A microlevel simulation model[END_REF][START_REF] Borgers | A Model of Pedestrian Route Choice and Demand for Retail Facilities within Inner-City Shopping Areas[END_REF][START_REF] Piet | Route Choice: Wayfinding in Transport Networks: Wayfinding in Transport Networks[END_REF]. Traffic congestion and other conditions could be taken into consideration by attributing different weights to the oriented edges as it has been done in [START_REF] Gwynne | Modelling occupant interaction with fire conditions using the buildingEXODUS evacuation model[END_REF]. Queuing models [START_REF] Gunnar | Modeling and simulation of pedestrian traffic flow[END_REF][START_REF] Steven | Modeling circulation systems in buildings using state dependent queueing models[END_REF] are also based on graphs, where the arrival of an individual at a node is managed using a probability law. Then the pedestrian spends a certain amount of time at the node before continuing on his next destination, leaving the queue.

Fluid dynamics models

The crowd movement was compared to fluid dynamics for the first time by Henderson [START_REF] Lf Henderson | The statistics of crowd fluids[END_REF][START_REF] Leroy F Henderson | On the fluid mechanics of human crowd motion[END_REF]. The author noticed that, for large crowds, one can describe the crowd movement using equations obtained from the Maxwell-Boltzmann theory. The proposed model is inspired by classical mechanics and thermodynamics: the crowd is considered as a compressible gas, governed by laws like momentum conservation, first and second laws of thermodynamics.

This description of the crowd as a continuum of particles of gas or fluid type has been further investigated in [START_REF] Helbing | A fluid dynamic model for the movement of pedestrians[END_REF][START_REF] Hoogendoorn | Gas-kinetic modeling and simulation of pedestrian flows[END_REF][START_REF] Bellomo | On the modeling of traffic and crowds: A survey of models, speculations, and perspectives[END_REF].

Hyperbolic conservation laws models

The Lighthill-Whitham-Richards model [START_REF] Michael | On kinematic waves. II. A theory of traffic flow on long crowded roads[END_REF][START_REF] Paul | Shock waves on the highway[END_REF] is a macroscopic counterpart of the Follow-

The-Leader model: each individual reduces its speed function of the density (decreasingly).

The general form of equation for this model is:

∂ t ρ + ∂ x (ρv(ρ)) = 0
where ρ is the density of the crowd and v(ρ) is the velocity that depends on the density. One of the simplest examples of v is v(ρ) = 1ρ. Another example was given by Weidmann in [START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF]:

v(ρ) = U 1 -exp -ρ s 1 ρ - 1 ρ max
where ρ s = 1.913 and ρ max is the maximum density (see Figure 1.4 for the plot of the velocity in terms of the density according to Weidmann [START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF]). This example of relation between the velocity and the density is the macroscopic counterpart of the relation between the velocity and the distance between individuals for the Follow the Leader model described by (1.1).

In [START_REF] Blandin | Well-posedness of a conservation law with non-local flux arising in traffic flow modeling[END_REF], the density is transported by a velocity that depends on a density average in dimension one. Some models inspired from the traffic flow theory and using conservation laws can be found in [START_REF] Rinaldo | Pedestrian flows and nonclassical shocks[END_REF][START_REF] Colombo | A class of nonlocal models for pedestrian traffic[END_REF]3,[START_REF] Goatin | A mixed system modeling two-directional pedestrian flows[END_REF][START_REF] Blandin | Well-posedness of a conservation law with non-local flux arising in traffic flow modeling[END_REF]. The celebrated macroscopic Hughes' model [START_REF] Hughes | The flow of large crowds of pedestrians[END_REF][START_REF] Roger | A continuum theory for the flow of pedestrians[END_REF] is based on a sophisticated decision making process, it relies on a non-trivial optimization process: each agent optimizes its way (according to some prescribed goal) according to the current density distribution of the crowd, attempting to avoid overcrowded areas. This approach has been implemented at the local level in [START_REF] Carrillo | An improved version of the Hughes model for pedestrian flow[END_REF] where the optimization process is based on the density of the crowd within his cone of vision.

Models based on Game theoretic principles

In [START_REF] Degond | A hierarchy of heuristic-based models of crowd dynamics[END_REF], a macroscopic counterpart of the Heuristic-Based model in [START_REF] Moussaïd | How simple rules determine pedestrian behavior and crowd disasters[END_REF] is proposed with three different closures: a monokinetic distribution function, a von Mises-Ficher distribution function and a hydrodynamic limit associated to a Local Thermodynamical Equilibrium. The equilibrium in the third closure is compared to Nash equilibria in a game theoretic framework.

Another case where a macroscopic model is deduced from its microscopic counterpart can be found in [START_REF] Carlier | A continuous theory of traffic congestion and Wardrop equilibria[END_REF]. A Wardrop equilibrium, that is a particular case of Nash equilibrium, is used to define a solution for congested traffic on networks and then the theory is extended to the continuous setting replacing the network by a domain in R 2 . The optimization process can even be delocalized in time, i.e. each agent designs its strategy with respect to the behavior of other agents in the future, see e.g. [START_REF] Lachapelle | On a mean field game approach modeling congestion and aversion in pedestrian crowds[END_REF][START_REF] Santambrogio | A modest proposal for MFG with density constraints[END_REF][START_REF] Degond | Large-scale dynamics of Mean-Field Games driven by local Nash equilibria[END_REF], where a Nash equilibrium-like macroscopic model is proposed, based on Mean Field Games.

Macroscopic model based on hard congestion handling

This model was introduced by Maury, Roudneff-Chupin and Santambrogio in [START_REF] Maury | A macroscopic crowd motion model of gradient flow type[END_REF][START_REF] Maury | Handling congestion in crowd motion modeling[END_REF] and is based on a strong expression of the congestion constraint, as the aforementioned granular model. Pedestrians are represented by a density that is subject to remain below a certain maximal value. At every point x in the domain Ω, we denote by U (x) the desired velocity of an individual at x. The pedestrian's density is transported by an admissible velocity field that is the closest to the desired velocity field of the crowd respecting the congestion constraint.

More precisely, the density evolves according to the following system:

⎧ ⎨ ⎩ ∂ t ρ + ∇ • ρu = 0 u = P Cρ U (1.2)
where P Cρ is the L 2 -projection operator, C ρ is the set of admissible velocity fields that do not concentrate the crowd in the already saturated zones:

C ρ = {v ∈ L 2 (Ω) 2 , Ω v • ∇q ≤ 0 ∀q ∈ H 1 ρ (Ω)}
and H 1 ρ (Ω) = {q ∈ H 1 (Ω), q ≥ 0 a.e. in Ω, q = 0 a.e. in [ρ < ρ max ]}. It has been shown in [START_REF] Maury | A macroscopic crowd motion model of gradient flow type[END_REF] that in the case where the desired velocity has a gradient structure, for example U = -∇D where D is the distance to the exit door, Equation 1.2 corresponds to the gradient flow of the functional Φ defined below, in the Wasserstein spaces of probability measures:

Φ(ρ) = ⎧ ⎨ ⎩ Ω D(x)dρ(x), if ρ ∈ K, +∞, otherwise.

Cellular automata

It is a particular class of models that was first described by Nagel in [START_REF] Nagel | From particle hopping models to traffic flow theory[END_REF]. Many other researchers developed this first model and made it among the most studied microscopic models.

Cellular automata models are neither microscopic nor macroscopic models and they are intrinsically discrete in space and time. The space is discretized into relatively big grid cells and each cell can accomodate at most one individual. Obstacles are handled by making some cells unreachable by individuals. Random Sequential Update (RSU) that is moving individuals one by one in a random chosen order to highlight the individual will to express himself [START_REF] Keßel | Microscopic simulation of pedestrian crowd motion[END_REF][START_REF] Klüpfel | Microscopic modelling of pedestrian motion-comparison of simulation results with an evacuation exercise in a primary school[END_REF]. The second one is the Parallel Update (PU) which consists on updating the positions of all the individuals simultaneously. If many pedestrians want to access the same cell, one is chosen randomly to occupy it and the positions of the others are kept unchanged [START_REF] Kirchner | Simulation of competitive egress behavior: comparison with aircraft evacuation data[END_REF][START_REF] Schadschneider | From Ant Trails to Pedestrian Dynamics-Learning from Nature[END_REF][START_REF] Kirchner | Friction effects and clogging in a cellular automaton model for pedestrian dynamics[END_REF][START_REF] Kirchner | Simulation of evacuation processes using a bionics-inspired cellular automaton model for pedestrian dynamics[END_REF]. For both methods, individuals are allowed to move either in four directions or in eight directions depending on the model, and the direction is chosen according to some probabilities based on individuals' goals and possibly accounting for the environment. A floor field is introduced to cellular automata models in [START_REF] Schadschneider | Cellular automaton approach to pedestrian dynamicstheory[END_REF][START_REF] Burstedde | Simulation of pedestrian dynamics using a two-dimensional cellular automaton[END_REF][START_REF] Schadschneider | From Ant Trails to Pedestrian Dynamics-Learning from Nature[END_REF] to modify the transition rates to neighbouring cells. Each agent is supposed to leave a virtual trace which influences the motion of other pedestrians and a static component is used to memorize preferred areas, walls and obstacles. The floor field transforms the long-range interactions between pedestrians into local interactions with "memory".

Characteristics of pedestrians

Modeling crowd dynamics requires a good knowledge about the characteristics of pedestrians, especially for microscopic modeling where pedestrians are usually represented by disks

Characteristics of pedestrians

or ellipses. Here we represent three of these characteristics that are investigated in [START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF][START_REF] Buchmueller | Parameters of pedestrians, pedestrian traffic and walking facilities[END_REF]: the body dimensions of human beings, their walking speed and the flow rate of placid pedestrians. For emergency evacuations, the flow rate of panicked pedestrians is quite different from the case of placid ones, panicked individuals are willing to behave selfishly and aggressively. Empirical data for massive evacuation experiments are missing for obvious reasons:

the dangerous nature of such situations makes it impossible to reproduce them by controlled experiments. However, some evacuation experiments are done with some restrictions on the behavior of pedestrians to ensure safety. Two of them are described in Annex A and used in Chapter 4 to validate the hierarchical model described in Chapter 3.

Dimensions and walking speed

The dimensions of the human body vary according to many factors as: gender, descent and age. The average human body dimensions has a width of 45.6cm and a depth of 28.2cm, which gives an average diameter of about 37cm when representing individuals with a circular shape. The height of individuals also vary widely between populations, for example the world's tallest country is The Netherlands with an average height of 1.838m for men while the world's shortest country is Peru with a height average of 1.64m, and the situation is almost the same for women. Since it is sufficient to study the motion of pedestrians represented in dimension 2, the height dimension is not of central importance for the work presented in this thesis.

According to [START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF], the walking speed of free pedestrians follows a normal distribution with an estimated mean of 1.34m/s and a standard deviation of 0.37m/s. This result is deduced from the mean speed and the standard deviation observed by researchers from many countries (The Netherlands, UK, USA, Australia, Austria, Saudi-Arabia, Hong Kong, Sri Lanka, Canada, India, Singapore and Thailand). The variation of walking speed is due to many influencing factors:

• Conditions of pedestrians: lifestyle, cultural and religious differences, age, gender, legs height, health status, selfish behavior,...

• Place: outdoor (parc, street, mountain,...), indoor (home, work, shopping mall, stairs...)

• Environmental conditions: temperature, weather, daytime,...

Flow rates of placid pedestrians

The flow rate is the number of persons who pass per unit of time and it is expressed in general in pers/s. Its value depends on the available space for pedestrians. For example, it is known that the flow rate decreases through bottlenecks (doors or narrow corridors), but the dependence of the flow rate on the bottleneck width is different according to researchers. On one hand, the authors in [START_REF] Serge | Pedestrian behavior at bottlenecks[END_REF] affirm that the flow rate varies in a step wise manner with the bottleneck width because the flow is supposed to depend on the integer number of pedestrian lanes allowed to pass at a time through the bottleneck. On other hand, the flow rate is found

Empirical values of flow rate

The results of empirical studies show close values of maximum flow rate for American and European pedestrians (between 1.4 and 1.53 pers/sm) and smaller values for Asians (between 1 and 1.29 pers/sm) according to [START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF]. The difference between those values is caused by smaller Asian body buffer zone and safety distances, and also by the cultural difference between these populations. Other researchers found different values for the flow rate: 1.3pers/s in [START_REF] Philip | SFPE handbook of fire protection engineering[END_REF], 1.6 pers/s in [START_REF] Vitaly | [END_REF], 1.85pers/m in [START_REF] Kretz | Experimental study of pedestrian flow through a bottleneck[END_REF] and 1.9pers/s in [START_REF] Seyfried | New insights into pedestrian flow through bottlenecks[END_REF]. These differences are actually due to different measurement situations (locations, pedestrian attributes, trip purpose).

Flow rate and placid pedestrian speed

The flow rate is correlated to the speed and density of pedestrians. For low densities, pedestrians are free to walk at their desired velocity or free-flow speed. When the density increases, placid pedestrians decrease their walking speed to avoid contact with others or to keep a safety distance from them. But when the pedestrian density reaches its maximum (considered around 5 pers/m 2 ) individuals can hardly move.

The relation between velocity and density, called fundamental diagram, has been investigated by many researchers over the last five decades. Some of these relations are illustrated in Figure 1.4, and here are some details about their locations (measurements are performed in everyday situations):

• [START_REF] John J Fruin | Design for pedestrians: A level-of-service concept[END_REF] Fruin (1971): peak-hour flows at commuter bus terminal.

• [START_REF] Older | Movement of pedestrians on footways in shopping streets[END_REF] Older (1968): shopping streets.

• [START_REF] Tanaboriboon | Pedestrian characteristics study in Singapore[END_REF] Tanariboon et al. ( 1986): different measurements in Singapore.

• [START_REF] Mark | Pedestrian speed-flow-density relationships[END_REF] Virkler and Elayadath (1994): pedestrian tunnel after University of Missouri football games.

• [START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF] Weidmann (1993): 25 sets of data from controlled laboratory experiments where measurements are performed on multidirectional flows. [START_REF] Daamen | Modelling passenger flows in public transport facilities[END_REF][START_REF] Mark | Pedestrian speed-flow-density relationships[END_REF][START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF] The relation between the flow rate and the density of walking pedestrians is easily deduced from the fundamental diagram (by representing the density × speed in terms of the density) and is illustrated in Figure 1.4. The pedestrian flow is zero for zero density, then it increases with the density until reaching its maximum at a prescribed density, and then decreases to attain zero again at the maximum density. The increasing phase of this curve is called the free flow phase while the decreasing phase is known as the congested flow phase. The values of maximum flow rate and its corresponding density as well as the maximum density differ from an experiment to another due to different circumstances. So this variety of values do not come in contradiction with each other, but rather complete each other to have a panorama of empirical data for different situations.

Crowd motion effects

Since the main goal of crowd motion modeling is to help designing walking facilities and predicting crowd behavior, it is very important for the models to be able to reproduce the effects observed in empirical data.

Faster is Slower

The Faster is Slower effect was described by Helbing et al. [START_REF] Helbing | Simulating dynamical features of escape panic[END_REF] as one of the characteristic features of escape panic. When pedestrians are in a rush, they tend to increase their velocity and show maladaptive pushing behavior that leads to a reduction of the flow through the exit.

From the psychological standpoint, this is due to panic in critical situations where pedestrians adopt a selfish attitude. This clumsy behavior of pedestrians leads to serious consequences:

pressure arches tend to form upstream the exit, inducing a drastic reduction of the flux by granular clogging.

The Faster is Slower effect has been investigated from the experimental point of view in [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF][START_REF] Garcimartín | Flow of pedestrians through narrow doors with different competitiveness[END_REF] where some experiments of evacuation drills are analyzed in order to reveal the features of such phenomena and test the evidence of the Faster is Slower effect. Two types of experiments are performed: low competitiveness and high competitiveness. The difference in the behavior of the participants in the two experiments induce clearly different consequences, in particular individuals are close to be injured in the competitive case, with some jams upstream the exit door. The evacuation is shown to be smoother and faster for the low competitiveness case. The recorded videos of the two evacuations can be found on the following link: https://www.youtube.com/watch?v=q-k4fCiiMlk.

The Social-Force model introduced by Helbing and Molnar in [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF] is shown to be able to produce this effect in the non-stationary case [START_REF] Parisi | Microscopic dynamics of pedestrian evacuation[END_REF] as well as in the stationary case [START_REF] Parisi | Why "faster is slower" in evacuation process[END_REF].

This was proven by simulating evacuations with different desired velocities and showing that the curve representing the evacuation time for the non-stationary simulations (resp. the flow rate for the stationary simulations) versus the desired velocity displays a minimum (resp. a maximum).

Zipper effect

The zipper effect is a self organization phenomenon leading to an optimization of the available space and velocity inside a bottleneck. This effect has been observed in the experiment of unidirectional flow through bottlenecks described in [START_REF] Serge | Pedestrian behavior at bottlenecks[END_REF]. The zipper effect is characterized by the formation of intercalated lanes of pedestrians as shown in Figure 1.5 (in the middle).

This effect supports the hypothesis reported in Section 1.2 the flow rate through a bottlenecks increases in a step wise manner with the width of the bottleneck.

Another effect that has been ascribed to a generalized zipper effect in [START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF], is the alternation between short and long time lapses. This effect occurs especially when the width of the bottleneck is about two times the diameter of pedestrians. In this case, pedestrian lanes are formed upstream the exit door. Individuals from the same lane try to maintain a minimal distance between them, while individuals standing shoulder to shoulder from different lanes may come close to contact. As a result, pedestrians exits the room by packs of two individuals (see [START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF] for more details about this effect).

Capacity drop

The capacity drop phenomenon is specific to crowd movement passing through a bottleneck.

When the inflow increases gradually, the outflow increases as well until a certain threshold where the capacity of the door drops down leading to a decrease in the outflow. The outflow then remains at a lower level until the inflow falls down. Empirical studies of this effect are done in [START_REF] Cepolina | Understanding capacity drop for designing pedestrian environments[END_REF] where the inflow and outflow of a crowd passing through a bottleneck in a underground station are plotted against time (see Figure 1.6). The inflow reaches its maximum after 30s and 15s later the outflow decreases dramatically to a lower level, then it increases slightly and remain stable until the inflow reaches zero.

Effect of an obstacle

The effect of placing an obstacle upstream the exit door is becoming widely investigated nowadays. It is sometimes referred to as a Braess' paradox since an obstacle is supposed to reduce the available space near the exit which should decrease the outward flow. However, the experiments show that placing an obstacle upstream the exit door boosts the evacuation fluidity increasing the outward flow rate. This effect is observed experimentally in [START_REF] Jiang | Obstacle optimization for panic flow-reducing the tangential momentum increases the escape speed[END_REF] where the authors show that placing an obstacle in front of the door maximizes the escape efficiency.

In [START_REF] Zuriguel | Effect of obstacle position in the flow of sheep through a narrow door[END_REF], a similar experiment to prove the efficiency of placing an obstacle is done for the flow of sheep in a narrow door.

Analyzing the effects on placing obstacles, Helbing et al. [START_REF] Helbing | Selforganized pedestrian crowd dynamics: Experiments, simulations, and design solutions[END_REF] interpreted the presence of an obstacle as a pressure absorber that fluidizes the evacuation increasing the efficiency of the escape. Also, Zuriguel et al. [START_REF] Zuriguel | Silo clogging reduction by the presence of an obstacle[END_REF] suggested that the clogging reduction is caused by the pressure decrease in the region of arches formation. Different shapes of obstacles are tested using the social force model in [START_REF] Escobar | Architectural design for the survival optimization of panicking fleeing victims[END_REF] to find the most efficient shape and placing two pillars or two walls forming a reversed V are shown to have bigger influence on the exit flow compared to the other tested obstacle shapes.

Stop-and-go waves

Stop-and-go waves are observed in unidirectional pedestrian flow and are characterized by a periodic variation of the density of pedestrians in space and time. These walking disturbances are in general observed when pedestrians walk in a corridor or queue. It has been observed in the experiments described in [START_REF] Lemercier | Realistic following behaviors for crowd simulation[END_REF][START_REF] Portz | Analyzing stop-and-go waves by experiment and modeling[END_REF], where a group of pedestrians are asked to walk in a cir-

Lane formation

Another effect in pedestrian dynamics is the formation of lanes when two groups of individuals are walking in opposite directions. It is a self-organization effect that occurs spontaneously and is considered as a pattern reflecting "collective intelligence" [START_REF] Helbing | Pedestrian, crowd and evacuation dynamics[END_REF]. This effect leads to a reduction in the internal friction and reduce the delays in oppositely moving crowds. Moreover, these lanes are known to have an increasing width when the movement continues over long distances [START_REF] Helbing | Pedestrian, crowd and evacuation dynamics[END_REF]. They occur specially in underground metro lines connections and shopping streets. An experiment showing the formation of lanes is done by the research project HERMES of the German Federal Ministry of Education and Research, and is available here https://www.youtube.com/watch?v=J4J__lOOV2E. A deeper study about the formation of lanes in done in [START_REF] Moussaid | Traffic instabilities in self-organized pedestrian crowds[END_REF] where the authors describe some performed controlled experiments of two groups of pedestrians walking in opposite directions in a circular domain. The flow of pedestrians is observed to segregate into lanes of uniform walking directions. The authors studied the stability of the formed lanes and observed that the flow segregation vanishes when the walking velocities of pedestrians fluctuate.

In [START_REF] Victor | Cellular automata microsimulation for modeling bi-directional pedestrian walkways[END_REF][START_REF] Burstedde | Simulation of pedestrian dynamics using a two-dimensional cellular automaton[END_REF][START_REF] Keßel | Microscopic simulation of pedestrian crowd motion[END_REF][START_REF] Kirchner | Simulation of evacuation processes using a bionics-inspired cellular automaton model for pedestrian dynamics[END_REF][START_REF] Schadschneider | From Ant Trails to Pedestrian Dynamics-Learning from Nature[END_REF], it is shown that the cellular automata model reproduces this effect. The social force model is also shown in [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF] to be able to reproduce this effect and it has been shown that the number of formed lanes increases linearly with the width of the corridor. For example, for a wide corridor of width 10m, 4 to 5 lanes are formed for a density of 0.3pers/m 2 . In [START_REF] Helbing | Freezing by heating in a driven mesoscopic system[END_REF], a stochastic term is added to the social force model to distort the velocity of pedestrians. Unless this term is significant, the model still shows lane formation but when the term becomes important, lanes disappear and individuals are blocked forming a crystal lattice.

Chapter 2

Instantaneous Nash equilibrium model Contents

Description of the Nash equilibrium model

We propose in this chapter a new microscopic model, based on a decision making process, in the hard congestion setting. We aim at describing highly crowded situations (quasi-contact), yet restricted to civilized interactions between agents. Neighboring agents may then be in quasi physical contact, but not to the point of creating physical interaction forces. Individuals are supposed to have a desired velocity field, and the actual velocity field will be defined as an instantaneous Nash equilibrium. Each individual is represented by a disc, and tends to reach a personal objective encoded in a desired velocity. The model is based on the following ingredients:

• Influence network on the set of individuals: we suppose that each individual is influenced by some of its neighbors, and we shall represent the influence relations by a directed graph (see Figure 2.1 for an example). Each agent, i.e. each vertex of the graph, points to the agents that influence him (typically the set of persons which he sees, in practical applications).

• Game theoretic principles: we consider that the velocities that may be globally chosen by the crowd are equilibrium velocities, i.e. they realize an instantaneous Nash equilibrium. Let us start by recalling Nash equilibria for non-cooperative games. A game is constituted of three elements: a set of players, a set of actions (or strategies) available to each player and a utility function that presents each player's satisfaction over actions. A game is said to be non-cooperative when each individual search for his own satisfaction without caring about the satisfaction of others, like a racing game for example. This is translated by a utility function for each individual that do not account for the utility functions of the others, but on their strategies only. In game theory, a list of actions (an action for each player) is called a Nash equilibrium if the chosen action by each player maximizes his utility function taking into consideration the equilibrium strategies of other players. In other words, no player can benefit from changing his action assuming other players' actions fixed (see [START_REF] Nash | Equilibrium points in n-person games[END_REF] for the formal definition of Nash equilibria).

Example 1

Consider a game of two pedestrians/players A and B situated on a grid, in the spirit of cellular automata, where players cannot overtake each other. The configuration of players is displayed in Figure 2.2. At each time step, a player can either move to a neighboring cell or stay at his previous position. Each player has three possible strategies: -1 (goes to the left), 0 (does not move) or 1 (goes to the right). We assume that player A wants to go to the right and player B wants to go to the left and they both influence each other. The configuration of players is constrained then to satisfy a non-overlapping condition: both players cannot occupy the same cell at the same time. We translate this unaccepted situation by a utility function that takes the value -∞ when an overlapping occur, in other words, we suppose that both players are infinitely unsatisfied in that case. to his chosen strategy and the strategy chosen by the other player. A Nash equilibrium is a couple of strategies such that each player could only do worse by unilaterally changing his strategy. In that case, three Nash equilibria exists: (-1, -1), (0, 0) and (1, 1), which means that both players choose the same strategy. Actually, if the players choose another couple of strategies at least one of them could do better by changing his strategy. For example, when players choose strategies that lead to an overlapping, their satisfaction is -∞ and they can obviously do better by choosing a couple of strategies that do not violate the constraint. Also, take for example the case where player A chooses -1 and player B chooses 0, player A could do better by choosing 0 and then (-1, 0) could not be a Nash equilibrium for this game.

A B -1 0 1 -1 (-10, 10) (-10, 0) (-10, -10) 0 (-∞, -∞) (0, 0) (0, -10) 1 (-∞, -∞) (-∞, -∞) (10, - 10
)
Table 2.1: Player's satisfaction over couples of possible strategies.

It is common in Nash equilibrium problems to consider that each player tries to maximize a utility function. However, for the case of the game we are going to introduce, we shall see that it is more appropriate to consider minimization problems instead of maximization ones.

From now on, we consider that each player has a cost function (that is just the opposite of the utility function) measuring the cost he pays for choosing a strategy according to the chosen strategies of the others.

For our model, we define a game for which the players are the pedestrians and their available strategies are the velocities they are able to have. We suppose that the cost function of a player is finite if his chosen velocity is admissible, in the sense that it preserves the nonoverlapping constraints with his influential neighbors. It is equal in that case to the euclidean norm of his desired velocity mines his chosen one. Otherwise, his cost function is considered equal to +∞. A Nash equilibrium is then a list of velocities such that the velocity of each individual approaches best his desired one among all velocities that he considers as feasible,

given the positions and velocities of neighbors who influence him.

Remark 2.1.1. In the formal definition of generalized Nash equilibrium problems [START_REF] Facchinei | Generalized Nash equilibrium problems[END_REF], the utility function is not supposed to have infinite values. Actually, in the case where the feasible strategy set of an individual depends on the strategies chosen by others (like the case of the game we consider here), we just search for a Nash equilibrium such that the action of each player belongs to his feasible strategy set depending on others' choices. However, in our case we consider that the unfeasible strategies of a player are possible but infinitely unsatisfying. A player can then choose an unfeasible strategy if and only if it is the only possible option for him. We shall see that the violation of the non-overlapping constraints will be recovered in this case by an extra step in the determination of the actual velocities of individuals.

The following example illustrates Remark 2.1.1.

Example 2

We consider a game of three pedestrians/players A, B and C, in the same context of Example 1.

The configuration of players is displayed in Figure 2.3. We suppose that player A wants to go to the left and is not influenced by the other players, player B does not want to move and is influenced by players A and C, and player C wants to go to the right and is not influenced by the others. The utility function of each player is 10 if his chosen strategy is his desired one, -∞ if his chosen strategy leads to an overlapping with at least one of his influential neighbors, and -10 if his chosen velocity is not his desired one but does not lead to an overlapping with his influential neighbors. Since player A is not influenced by the others, his desired strategy is admissible for him and then he chooses the strategy 1. The case is similar for player C who chooses the strategy -1. For player B, whatever strategy he chooses, his utility function is -∞. The list of strategies (1,0,-1) is a Nash equilibrium because each player does his best considering the strategies chosen by the others, even if it leads to a non-admissible configuration.

A B C

Figure 2.3: Example of configuration of three players on a grid.

Mathematical formulation

We consider N individuals. The position of an individual i is denoted by q i and the configuration of all individuals is denoted by q = (q 1 , . . . , q N ) ∈ R dN , d = 1, 2. We denote by U i (q i ) the desired velocity of individual i, i.e. the velocity he would like to have in the absence of others. In the case where individuals are interchangeable, we can write it U (q i ), but we shall keep the possibility to handle people with different objectives. In the following U i will stand for U i (q i ), where q i corresponds to the current configuration. We identify individuals with discs centered at q 1 , . . . , q N , with respective radii r 1 , . . . , r N , constrained to satisfy a non-overlapping condition. In other words, the configuration of individuals should belong to the set of feasible configurations defined by:

K = q ∈ R dN , D ij (q) ≥ 0, ∀i ̸ = j
where D ij (q) = |q iq j |r ir j is the distance between individuals i and j.

We suppose that each individual is influenced by some others (not necessarily all of them) and we denote by I i the set of pedestrians that influence i. In practical cases, this set corresponds to the cone of vision of the individual. We consider that each individual accounts for all others belonging to his set of influence. We represent the influences between individuals by a directed graph associated to the configuration q. This graph is built as follows:

• Each individual represents a node of the graph

• An oriented edge links the node i to the node j if and only if i accounts for j, i.e. j ∈ I i .

Considering a feasible configuration q ∈ K, we shall call equilibrated a velocity field u(q) = (u 1 , . . . , u N ) that is a Nash equilibrium to the game defined on the crowd. The fact that the constraints on an individual's velocity depend on others' velocities does not properly define a velocity field, but rather leads to define a (possibly empty) set of velocities that are compatible with those requirements.

More precisely, we shall denote by Λ the set of all those velocity fields u = (u 1 , . . . , u N ) such that

u i = argmin w∈C i (q,u -i ) 1 2 |w -U i | 2 , ∀i = 1, . . . , N (2.1)
where

C i (q, u -i ) = w ∈ R d , ∀j ∈ I i , D ij (q) = 0 ⇒ e ij (q) • (w -u j ) ≤ 0 , (2.2)
with the usual notation u -i = (u 1 , . . . , u i-1 , u i+1 , . . . , u N ) and e ij (q) = (q jq i )/|q jq i |. In the case where C i (q, u -i ) is empty 1 , we consider that the minimizing functional is +∞ and

thus any u i ∈ R d is admissible.
Let us start with some preliminary remarks on Nash equilibria. 1 In other words, we consider the minimization problems:

u i = argmin w∈R d 1 2 |w -U i | 2 + I Ci(q,u-i) (w) for all i = 1, . . . , N where I Ci(q,u-i) (w) is the characteristic function of C i (q, u -i ). q i q j D ij e ij -e ij r i r j Figure 2.4: Notation 1.
As we shall see, Nash equilibria are not unique in general. We claim that this native indeterminacy of velocities makes sense in many situations, in particular when there is a direct conflict between individuals. A conflict between civilized agents is likely to lead to a fuzzy phase during which each actor hesitates to step forward as far as he does not know what its opponent is up to. We shall not address in details this very phase of indecision, but rather describe a general framework able (together with additional ingredients to model conflicts) to describe such situations. Besides, we shall see that the deterministic character will be recovered in some particular situations, e.g. emergency evacuation of a room, or more general situations where the influence graph is acyclic, which rules out local or collective conflicts, and makes it possible to determine actual velocities in a hierarchical way. This particular type of influence graph is the subject of Chapter 3.

2. In the case where some individuals have neighbors that do not influence them, equilibrated velocities may not be feasible in the sense that they would lead to overlapping of discs. More precisely, they may not belong to the set

C(q) = v = (v 1 , . . . , v N ) ∈ R dN , ∀j ̸ = i, D ij (q) = 0 ⇒ e ij (q) • (v i -v j ) ≤ 0 . (2.3)
We focus now on the study of the general Nash equilibrium model. We start by investigating some simple examples to illustrate the previous remarks.

Some illustrative examples Example 1: Non uniqueness

Consider two individuals in contact in dimension one (see Figure 2.5). We suppose that individuals 1 and 2 have the following desired velocities and influence sets: It corresponds to the situation in Example 2 with a person standing between the two groups.

U 1 = 1, U 2 = -1,
He can see the two persons belonging to distinct groups moving backward, while they do not see him, and he will find himself squashed in the middle. This example is the continuous counterpart of Example 2 in Section 2.1. The possibility that some collisions may occur (as for Examples 2 and 3) will make it necessary to perform an extra step in actual computations, that is projecting the equilibrated velocity field on the set of globally admissible velocities. Therefore, in the case where some neighbors do not influence each other, the Nash equilibrium model will be used to define a new desired velocity field which accounts for the tendency of pedestrians to avoid contacts (decision process), and it will be followed by a global projection step to handle the physical contacts that have not been anticipated by individuals. The problem in that case reads:

1 2 3 U 1 U 2 U 3
• Decision step: ũi = argmin

w∈C i (q,ũ -i ) 1 2 |w -U i | 2 , ∀i = 1, . . . , N where C i (q, ũ-i ) is defined by (2.2),
• Correction step: u = argmin v∈C(q) 1 2 |v -ũ| 2 where C(q) is defined by (2.3).

The second step of the model comes actually from the granular model in [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF]. For this model, individuals are also supposed to have desired velocities as if they are alone, and their actual velocity field is defined as the projection of the desired velocity field on the set of globally admissible velocity fields C(q): The difference between the two models appears clearly when looking to their saddle point formulations.

u g = argmin v∈C(q) 1 2 |v -U | 2 . ( 2
Proposition 2.2.1. The collection of minimization problems (2.1)(2.2) is equivalent to the collection of saddle-point formulations: for each i = 1, . . . , N, there exists nonnegative Lagrange multipliers

(λ i ij ) j∈I c i such that ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ũi + j∈I c i λ i ij e ij = U i , e ij • (ũ i -ũj ) ≤ 0, ∀j ∈ I c i , j∈I c i λ i ij e ij • (ũ i -ũj ) = 0, (2.5)
where I c i ⊂ I i is the set of individuals j that influence i, and that are in contact with i, i.e. such that D ij = 0.

Proof. The functional is quadratic and the constraints are affine thus automatically qualified.

Therefore ũi is a solution of Problem (2.1)(2.2) if and only if there exists Lagrange multipliers

(λ i ij ) j∈I c i such that (ũ i , λ i
) is a solution of the saddle point formulation (2.5) (by Kuhn-Tucker theorem, see [START_REF] Allaire | Analyse numérique et optimisation: Une introduction à la modélisation mathématique et à la simulation numérique[END_REF] for more details). Proposition 2.2.2. The minimization problem (2.4)(2.3) is equivalent to its saddle point formulation: there exists nonnegative Lagrange multipliers (λ g ij ) j̸ =i such that

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ u g i + j̸ =i λ g ij e ij = U i , e ij • (u g i -u g j ) ≤ 0, ∀j ̸ = i, j̸ =i λ g ij e ij • (u g i -u g j ) = 0, (2.6)
Proof. The same arguments as for the proof of Proposition 2.2.1 hold to show this equivalence.

Since interactions are symmetric between individuals for the granular model (two neighboring individuals influence each other in the same way), the Lagrange multipliers (λ g ij ) j̸ =i that quantify the interaction forces are also symmetric, i.e. it holds that λ g ij = λ g ji , ∀i ̸ = j. However, the situation is different for the Nash equilibrium model, it could happen that

λ i ij ̸ = λ j ij .
Take for example the case where an individual i is influenced by another individual j whereas j is not influenced by i. For such situations, if the desired velocity of i is not feasible and leads to an overlapping between i and j, we have λ i ij > 0 and λ j ji = 0. In that case, λ i ij quantifies the correction that i makes on his desired velocity to avoid collision with j. Even in the case where i and j influence each other mutually, the action of i over j is not necessarily the same as the action of j on i, as we shall see in the case of complete influence graph in Section 2.3.

Theoretical issues

We discuss in this section the existence and uniqueness questions for the Nash equilibrium model. We mainly focus on the case of complete influence graph and give some remarks at the end of the section on the general case on influence graph.

Complete influence graph

We address now the existence and uniqueness questions for Problem (2.1)(2.2) in the case where all interactions are accounted for, i.e. the case where each individual is influenced by all his neighbors and all the edges of the graph are directed in two ways (i → j and j → i for all i ̸ = j). Two examples of complete influence graphs in dimensions one and two are displayed in Figures 2.8 and 2.9. The Nash equilibrium problem reads in this case:

u i = argmin w∈C i (q,u -i ) 1 2 |w -U i | 2 , ∀i = 1, . . . , N (2.7)
where C i (q, u -i ) is now:

C i (q, u -i ) = w ∈ R d , ∀j ̸ = i, D ij (q) = 0 ⇒ e ij (q) • (w -u j ) ≤ 0 . (2.8)
In the one dimensional case, the problem can be simply written for each cluster of N individuals as follows: We state the existence result in the following proposition, which gives a constructive process to build an infinite number of equilibria. This process is based on mechanical principles, so that the law of action and reaction automatically holds: it restricts this approach to the complete case. Note also (see Proposition 2.3.4 below) that, in dimension two, this process will not make it possible to build all Nash equilibria.

u i = argmin u i-1 ≤w≤u i+1 1 2 |w -U i | 2 , ∀i = 1, . . . , N (2.9)
min v∈C(q) 1 2 (v -U ) • M (v -U ), (2.10)
where C(q) is defined by (2.3), has a unique solution that is a particular solution of Problem (2.7)(2.8).

Proof. We proceed using the saddle point formulations of both Problems (2.7)(2.8) and

(2.10)(2.3). Problem (2.10)(2.3) is equivalent to its saddle point formulation, we denote by (u M , λ M ), λ M ≥ 0, its saddle-point, so we have for all i = 1, . . . , N,

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ m i u M i + j̸ =i,D ij =0 λ M ij e ij = m i U i , e ij • (u M i -u M j ) ≤ 0, ∀j ̸ = i, D ij = 0, j̸ =i,D ij =0 λ M ij e ij • (u M i -u M j ) = 0.
(2.11)

Hence, setting

λ i ij = λ M ij /m i , the couple (u M i , (λ i ij ) j̸ =i,D ij =0
) satisfies the saddle point formulation (2.5) of Problem (2.7)(2.8).

We shall see that some Nash equilibria cannot be recovered as limits of such mechanical equilibria. Let us first establish the closed character of Λ. Proposition 2.3.2. For the case of a complete influence graph, the set Λ of all Nash equilibria is closed in R dN .

Proof. Let (u n ) n ⊂ Λ be a convergent sequence and let u be its limit. We denote by

(λ i,n ij ) j̸ =i,D ij =0
the nonnegative Lagrange multipliers associated to u n i , for all i = 1, . . . , N and n ∈ N:

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ u n i + j̸ =i,D ij =0 λ i,n ij e ij = U i e ij • (u n i -u n j ) ≤ 0, ∀j ̸ = i, D ij = 0, j̸ =i,D ij =0 λ i,n ij e ij • (u n i -u n j ) = 0
(2.12)

Let J i be the set:

J i = j ̸ = i, (λ i,n ij )

has an infinite number of non-zero terms

After some rank, the sequence

j∈J i λ i,n ij e ij is equal to j̸ =i,D ij =0 λ i,n ij e ij = U i -u n i
and is then convergent. Since the set of nonnegative linear combinations of (e ij ) j∈J i is closed, the limit can be written in the form

j∈J i λ i ij e ij
for some λ i ij ≥ 0, for all j ∈ J i . We set λ i ij = 0 for all j / ∈ J i , so we can write:

u i + j̸ =i,D ij =0 λ i ij e ij = U i .
We pass to the limit in the second equation of (2.12) to get:

e ij • (u i -u j ) ≤ 0
for all j ̸ = i. So it remains to be proved that the complementary condition

j̸ =i,D ij =0 λ i ij e ij • (u i -u j ) = 0
holds. For j ∈ J i , there exists a sub-sequence still denoted by (λ i,n ij ) j̸ =i,D ij =0 such that λ i,n ij is strictly positive starting a given rank. The complementary condition

λ i,n ij e ij • (u n i -u n j ) = 0
is satisfied for all n ∈ N, so e ij • (u n iu n j ) = 0 for n sufficiently large. Passing to the limit in the last equality we get e ij • (u iu j ) = 0 for all j ∈ J i . Then, the following holds for all i = 1, . . . , N:

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ u i + j̸ =i,D ij =0 λ i ij e ij = U i e ij • (u i -u j ) ≤ 0, ∀j ̸ = i, D ij = 0, j̸ =i,D ij =0 λ i ij e ij • (u i -u j ) = 0, which means that (u, (λ i ij ) j̸ =i,D ij =0
is a solution of the saddle point formulation of Problem (2.7)(2.8), and thus u belongs to Λ.

We denote by Λ m the set of all those velocity fields which can be obtained as a solution of (2.10), where M is a diagonal matrix associated to masses m 1 , . . . , m N > 0. We have already shown that Λ m ⊂ Λ, and the previous proposition extends the inclusion to the closure: Λ m ⊂ Λ. A natural question arises: does it hold that Λ m = Λ ? The answer is yes in dimension one and it is proved in Proposition 2.3.3. However, we show in Proposition 2.3.4 that it is not true in dimension two, which means that some equilibria are genuinely of the game-theoretic type and cannot be recovered by mechanical principles. Proposition 2.3.3. In the one dimensional setting, it holds that Λ m = Λ.

Proof. We have already proved that Λ m ⊂ Λ, it remains to be demonstrated that Λ ⊂ Λ m .

Let U be a desired velocity field for a cluster of N individuals in contact, and u ∈ Λ be an equilibrated velocity field solution to Problem (2.9). The equilibrated velocity of an individual is either equal to his desired one if this latter is admissible, or equal to the equilibrated velocity of one of its neighbors (or both if u i-1 = u i+1 ) if his desired velocity is not admissible. We can then assort the individuals in two groups: the first one for individuals who have their desired velocity as their equilibrated one, and the second one for the rest of individuals. We assign an infinite mass for the individuals of the first group. Consider now a sub-cluster of all individuals of the second group having the same equilibrated velocity. Since no individual could benefit from having a velocity greater than the maximum desired velocity of the subcluster and its closest neighbors (the two individuals on the left and right of the sub-cluster, if they exist) or less than its minimum, the equilibrated velocity of the sub-cluster lies between these two values. Thus the equilibrated velocity could be written as a weighted average of the desired velocities of the individuals in the sub-cluster and possibly their closest neighbors. We denote by u 1 = (u 1,x , u 1,y ), u 2 = (u 2,x , u 2,y ), u 3 = (u 3,x , u 3,y ) and u 4 = (u 4,x , u 4,y ) an equilibrated velocity field solution of Problem (2.7)(2.8). Expanding the constraints on the equilibrated velocities of individuals in contact 1 ↔ 2, 2 ↔ 3, 3 ↔ 4 and 4 ↔ 1, we obtain respectively: u 1,x ≤ u 2,x , u 2,y ≤ u 3,y , u 3,x ≤ u 4,x and u 4,y ≤ u 1,y , so the individual minimization problems reads:

u 1 = argmin u 1,x ≤u 2,x ,u 1,y ≥u 4,y 1 2 [(1 -u 1,x ) 2 + u 2 1,y ], u 2 = argmin u 2,x ≥u 1,x ,u 2,y ≥u 3,y 1 2 [u 2 2,x + (1 + u 2,y ) 2 ] u 3 = argmin u 3,x ≥u 4,x ,u 3,y ≤u 2,y 1 2 [(1 + u 3,x ) 2 + u 2 3,y ], u 4 = argmin u 4,x ≤u 3,x ,u 4,y ≤u 1,y 1 2 [u 2 4,x + (1 -u 4,y ) 2 ].
Taking for example the following velocities

u 1 = U 1 + U 4 = (1, 1), u 2 = U 1 + U 2 = (1, -1)
,

u 3 = U 2 + U 3 = (-1, -1) and u 4 = U 3 + U 4 = (-1, 1)
, we can easily verify that they solve the above minimization problems and form then a Nash equilibrium of Problem (2.7)(2.8). We represent in Figure 2.10 the desired velocities of the individuals as well as their equilibrated ones. For this particular Nash equilibrium, each individual has been influenced by the person on his right only. This could also be deduced when looking at the directions of these velocities for each individual. Consider for instance the interaction between 1 and 2.

Consider the velocities that would result from a projection of the desired velocity field on the set of feasible velocities, for some non degenerated mass matrix M (see Eq. (2.10)). Since m 1 and m 2 are finite and positive, the horizontal velocity of individual 1 is necessarily reduced, which is not the case here (individual 1 fully imposes his horizontal velocity to individual 2).

Focusing on 1 ↔ 2 interaction, the considered equilibrated velocity field can be obtained only by having m 1 /m 2 going to infinity. Similarly, considering the remaining interactions 2 ↔ 3,

Concluding remarks

In this section, we give some remarks on the existence of solutions in the case of a nonsymmetric graph with cycles and on the uniqueness of solutions in the case of a cyclic influence graph. The case of a directed acyclic influence graph (hierarchical situation) is the subject of Chapter 3, where we prove existence and uniqueness of solutions for this special case.

Theoretical issues (existence)

Apart from the case of a complete influence graph and a directed acyclic one, the general theory on the existence of Nash equilibria does not apply due to the particular form of the cost functions considered for the game. Actually, the classic existence results require either continuity of the cost functions as in [START_REF] Debreu | A social equilibrium existence theorem[END_REF][START_REF] Irving | A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points[END_REF][START_REF] Ky | Fixed-point and minimax theorems in locally convex topological linear spaces[END_REF], its boundedness [START_REF] Dasgupta | The existence of equilibrium in discontinuous economic games, I: Theory[END_REF], or semi-continuous dependency of the admissible set of strategies for an individual upon the strategies of other players [START_REF] Kenneth | Existence of an equilibrium for a competitive economy[END_REF]. Some weaker conditions on the cost functions have been recently proposed to prove existence of Nash equilibria for discontinuous games [START_REF] Michael R Baye | Characterizations of the existence of equilibria in games with discontinuous and non-quasiconcave payoffs[END_REF][START_REF] Philip | On the existence of pure and mixed strategy Nash equilibria in discontinuous games[END_REF][START_REF] Nessah | The existence of equilibria in discontinuous and nonconvex games[END_REF][START_REF] Barelli | On the existence of Nash equilibria in discontinuous and qualitative games[END_REF], but are not satisfied by the cost functions considered in this chapter. The existence issue in general is still an open question.

Modeling issues (uniqueness)

In the case of an influence graph which contains cycles, solutions are not unique in general and one needs to make choices in order to obtain a proper evolution model. This indeterminacy is inherent to some situations, and reflects conflicts that are not meant to be resolved in a systematic way. For example, it corresponds to the situation of two face-to-face individuals in a corridor heading to opposite directions where a conflict may arise and lead to a phase of hesitation, possibly with slight back and forth moves. In the case of a complete influence graph, an actual computation of a Nash equilibrium can be made by affecting different masses to individuals (those masses may vary in time), which quantify their respective willingness, together with their impoliteness. Nevertheless, in the general (non symmetric) case with cycles, the issue is much more delicate and calls for a finer psychological description of interactions between individuals, including politeness, aggressive behavior, capacity to instantaneously elaborate strategies based on what is expected from neighbors,. . . With this goal in mind, we started investigating some controlled experiments to study interactions between individuals whose anticipating trajectories intersect (cf. Appendix A). This work is still under current investigation.

Description of the hierarchical model

We propose in this chapter a crowd motion model for evacuation situations where individuals are considered civilized and respectful. The model is a particular case of the Nash equilibrium model described in Chapter 2 and is also based on a decision process in a hard congestion setting. Individuals are supposed to have desired velocities, it is the ones they would like to have if they were alone. We consider that each individual is influenced by some others and a directed graph is associated to the influence relations (each individual points to his influencers). In practice, the influence set of an individual would be his cone of vision. We consider the case where the influence graph is directed and acyclic (hierarchical), hence the name of the model. This particular case of influence graphs is characterized by extreme asymmetrical

Mathematical formulation of the problem

We use the same notation as in Chapter 2. Let Ω ⊂ R d , d = 1, 2, be a domain and consider N individuals whose positions are denoted by q = (q 1 , . . . , q N ) ∈ R dN . We suppose that each individual has a desired velocity U i (q i ) that we write U i for simplicity. Individuals are represented by discs centered at q 1 , . . . , q N , with respective radii r 1 , . . . , r N , and they are constrained to satisfy a non-overlapping condition. In other words, the configuration of individuals q should belong to the set of feasible configurations defined by:

K = q ∈ R dN , D ij (q) ≥ 0, ∀i ̸ = j
where D ij (q) = |q iq j |r ir j is the distance between individuals i and j. We suppose that each individual is influenced by some neighbors (not all of them) and we denote by I i the set of pedestrians that influence i.

q i q j D ij e ij -e ij r i r j Figure 3.

2: Some notation

We represent the influences between individuals by a directed graph associated to the configuration q that is built as follows:

• Each individual represents a node of the graph

• An oriented edge links the node i to the node j if and only if i accounts for j, or equivalently, j ∈ I i

We are interested in the case where the influence graph between individuals is directed and acyclic (hierarchic). According to [START_REF] Thomas H Cormen | Introduction to algorithms[END_REF], it means that there exists an indexing of the individuals such that i < j ⇐⇒ j ∈ I i .

We suppose that individuals are indexed according to this order. In practice, this model will be used in situations where all individuals point toward the same direction (e.g. evacuation of a room), so that the influence graph based on cones of vision will be natively hierarchical.

The first step of the model, that is the decision step, consists in computing an equilibrated velocity field ũ = (ũ 1 , . . . , ũN ) solution to a collection of personal minimization problems where each individual tries to approach best his desired velocity, taking into consideration non-overlapping constraints with his influential neighbors. The minimization problems read: ũi = argmin

w∈C i (q,ũ -i ) 1 2 |w -U i | 2 , ∀i = N, . . . , 1 ( 3 . 1 )
where

C i (q, ũ-i ) = w ∈ R d , ∀j ∈ I i , D ij (q) = 0 ⇒ e ij (q) • (w -ũj ) ≤ 0 , (3.2)
with the usual notation u -i = (u 1 , . . . , u i-1 , u i+1 , . . . , u N ) and e ij (q) = (q jq i )/|q jq i |. The set C i (q, ũ-i ) is the personal set of admissible velocities for i that takes into consideration The second step of the model is a collision handling to solve conflicts that have not been handled in the first step. The equilibrated velocity field ũ is projected on the set of globally admissible velocity fields as for the granular model in [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF]:

u = argmin v∈C(q) 1 2 |v -ũ| 2 (3.3)
where

C(q) = v = (v 1 , . . . , v N ) ∈ R dN , ∀j ̸ = i, D ij (q) = 0 ⇒ e ij (q) • (v i -v j ) ≤ 0 . ( 3.4)
Existence and uniqueness of solutions comes from the fact that the set C(q) is closed and convex and the minimization functional is strictly convexe and l.s.c.

Theoretical issues

We address now the existence and uniqueness questions for Problem (3.1)(3.2). We start by proving that the minimization problems characterizing the equilibrated velocities of individuals can be formulated in a saddle point manner.

Proposition 3.2.1. The collection of minimization problems (3.1)(3.2) is equivalent to the collection of saddle-point formulations:

for each i = 1, . . . , N, there exist nonnegative Lagrange multipliers

(λ i ij ) j∈I c i such that ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ u i + j∈I c i λ i ij e ij = U i , e ij • (u i -u j ) ≤ 0, ∀j ∈ I c i , j∈I c i λ i ij e ij • (u i -u j ) = 0, (3.5)
where I c i ⊂ I i is the set of individuals j that influence i, and that are in contact with i, i.e. such that D ij = 0.

Proof. The functional is quadratic and the constraints are affine thus automatically qualified.

Therefore u i is a solution of Problem (3.1)(3.2) if and only if there exists Lagrange multipliers (λ i ij ) j∈I c i such that (u i , λ i ) is a solution of the saddle point formulation (3.5) (by Kuhn-Tucker theorem, see [START_REF] Allaire | Analyse numérique et optimisation: Une introduction à la modélisation mathématique et à la simulation numérique[END_REF] for more details).

We consider now the case of an arbitrary hierarchical influence graph and end up this section with a concrete example of influence graph based on the cones of vision.

Directed acyclic influence graph

Two examples of directed acyclic graphs in dimension one and two are displayed in Figures 3.3

: Example of directed acyclic graph in dimension two

We prove in the following theorem the existence and uniqueness of solutions to this problem. Particularly, we show that all velocities can be uniquely determined in a frontal way, starting from the most influential individuals (who do what they want) to the less influential ones (who do what they can).

Proposition 3.2.2. We suppose that the influence graph of individuals is directed and acyclic, then Problem (3.1)(3.2) has a unique solution.

Proof. The proof is based on a construction procedure that enables us to explicitly determine a solution of Problem (3.1)(3.2), and then we prove that this solution is unique.

We start by enumerating the nodes of the directed acyclic graph using the inverse ordering of the so-called topological sorting algorithm [START_REF] Thomas H Cormen | Introduction to algorithms[END_REF]. This algorithm gives a linear ordering of the nodes of a directed acyclic graph such that: j > i if and only if there is a directed edge from i to j. The ordering of the nodes using the topological sorting algorithm is not necessarily unique, but we will see that this is not problematic. We suppose that individuals are indexed according to the topological sorting algorithm, and solve the problem as follows:

• Individual N has no leader, so no constraints are imposed on his velocity and we have ũN = U N .

• Individual N -1 has at most individual N in his influence set. Since ũN has already been determined, the actual velocity ũN-1 is the unique solution of the minimization problem (3.1)(3.2) for i = N -1.

• The actual velocities ũN , . . . , ũj+1 being determined, ũj is the unique solution of the minimization problem (3.1)(3.2) for i = j.

Suppose now that there exist two possible orderings for a given configuration using the topological sorting algorithm, a solution of Problem (3.1)(3.2) can be determined using a more general procedure. We consider the following partition of nodes and proceed as follows:

• E 0 is the subset of individuals that have no leaders. For any j ∈ E 0 , we have ũj (q) = U j .

• E 1 is the subset of individuals whose leaders are all in E 0 . For any j ∈ E 1 , ũj (q) is uniquely computed by the minimization problem (3.1)(3.2) for i = j since the velocities of individuals in E 0 have already been determined.

• E k , for k = 2, . . . , N, is the subset of individuals whose leaders are in E 0 ∪E 1 ∪• • •∪E k-1 ,
with at least one leader in E k-1 . For any j ∈ E k , ũj (q) is uniquely computed by the minimization problem (3.1)(3.2) for i = j since the velocities of individuals in Remark 3.2.3. In the case where C i (q, ũ-i ) is empty for an individual i (as for Example 3 in Chapter 2), the functional is equal to +∞ and then any velocity in R d is a minimizer of the problem 1 and leads to an overlapping with others. In this case, we consider that the individual chooses his desired velocity as an equilibrated velocity, to keep in consideration his personal objective, and the collision in handled by the second step of the model.

E 0 ∪ E 1 ∪ • • • ∪ E k-

Case where I i is the cone of vision of i

We consider now the practical case where each individual is influenced by others he can see, i.e. the ones that are in his cone of vision. This cone ranges to the left and to the right by an angle α < π/2 with respect to the line of sight of an individual (considered colinear with the direction of his desired velocity) and has a fixed length that we denote by l. The cone of vision of an individual i is then defined by:

V (q i , U i , α, l) = x ∈ R 2 , (x -q i ) • U i ||x -q i || ||U i || ≥ cos α and ||x -q i || ≤ l . (3.6)
1 Remark that Problem (3.1)(3.2) can be written as:

u i = argmin w∈R d 1 2 |w -U i | 2 + I Ci(q,u-i) (w)
In the one-dimensional case, the cone of vision is simply a segment of length l:

V (q i , U i , l) = {x ∈ R, x is between q i and q i + sgn (U i )l } .

(3.7) The influence set of i is now defined by:

q i V (q i , U i , α, l) α U i
I i = {j ∈ P \ {i}, q j ∈ V (q i , U i , α, l)}
and the problem reads: ũi = argmin

w∈C i (q,ũ -i ) 1 2 |w -U i | 2 , ∀i = 1, . . . , N (3.8)
where

C i (q, ũ-i ) = w ∈ R d , ∀j ∈ I i , D ij (q) = 0 ⇒ e ij (q) • (w -ũj ) ≤ 0 . ( 3.9)
We aim now to prove the existence and uniqueness of solutions to Problem (3.8)(3.9)

for the case of an evacuation (all individuals want to reach a target at the boundary of the domain). This result is obtained by proving that, under some conditions, the influence graph based on the cones of vision is acyclic. The problem fits then the frame of the hierarchical model (3.1)(3.2) and Theorem 3.2.2 could be applied.

Proposition 3.2.4. Let Ω be a convex domain with exits located on its boundary. We consider that all individuals have desired velocities pointing either to the closest point of an exit door

or to its center. We suppose that each individual is influenced by others in his cone of vision centered about the direction of his desired velocity, and that the following condition is satisfied: Proof. Without loss of generality, we suppose that the desired velocity field U is normalized.

||∇U || 2 < cos α max i r i . ( 3
U i U i U j -U j θ i θ j (θ i + θ j )/2
For every couple of individuals (i, j), let θ i = (U i , e ij ) and θ j = (U j , e ji ). We ensure that individuals i and j do not see each other mutually when max(θ i , θ j ) > α. To satisfy this constraint, it is sufficient to have

cos θ i + θ j 2 ≤ cos α.
We have (see Figure 3.7):

cos θ i + θ j 2 = ||U i -U j || 2 ≤ (r i + r j ) ||∇U|| 2 2 ≤ max i r i ||∇U|| 2 .
By prescribing the last term to be less than cos α, we obtain exactly condition (3.10). Therefore, the influence graph based on the cone of vision is hierarchical under this condition and Problem (3.8)(3.9) has a unique solution.

The decision taken by each individual reduces2 his desired velocity in the direction where he wants to go. In other words, his decision based velocity is smaller than his desired velocity in the direction of his desired movement, as stated in the following proposition.

Proposition 3.2.5. Let U be a desired velocity field and ũ be the equilibrated desired velocity field resulting from the decision process of each individual (Problem (3.1)(3.2)). Then the following holds:

U i • ũi ≤ ||U i || 2 , ∀i = 1, . . . , N.
Proof. Using the saddle point formulation (3.5) of the hierarchical model where I c i is the set of individuals that are in the cone of vision of i and are in contact with him, we have:

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ũi + j∈I c i λ i ij e ij = U i , e ij • (ũ i -ũj ) ≤ 0, ∀j ∈ I c i , j∈I c i λ i ij e ij • (ũ i -ũj ) = 0, (3.11)
The first line implies that:

ũi • U i + j∈I c i λ i ij e ij • U i = ||U i || 2 .
Since individual i could only be influenced by others in his cone of vision whose angle is strictly less than π/2, we have λ i ij e ij • U i ≥ 0 for all j ∈ I c i , which ends the proof.

Numerical solution for the hierarchical model

We propose in this section a numerical scheme to approximate the unique solution of the hierarchical model, based on a first order expansion of the constraints on the velocity.

Time discretization

Let t 0 = 0 be the initial time, τ > 0 a time step and t n = nτ the computational times.

We suppose that condition (3.10) is satisfied for all time t ∈ [0, T ], with T fixed. Consider a given initial configuration q 0 = q(t 0 ) ∈ K. At each time step we start by re-indexing the individuals according to the topological sorting algorithm, so that any individual i is influenced by individuals with an index j > i. We keep the same notation for readability reasons. We update the individuals' positions as follows: q n+1 = q n + τ u n+1 where u n+1 is the actual velocity computed in two steps, both based on a first order expansion of the non-overlapping constraints as proposed in [START_REF] Maury | A time-stepping scheme for inelastic collisions[END_REF].

The first step corresponds to individual adaptation (decision taking phase). Starting from i = N , N -1, . . . , each individual i picks the velocity ũn i that approaches best his desired one U i , subject to constraints with neighbors that influence him. When i's turn comes, all velocities ũn i+1 ,. . . , ũn N have already been computed. For all j ∈ I i , if i takes the velocity w during τ , the first order expansion of

D ij (q n + τ v) is D ij (q n + τ v) = D ij (q n ) + τ ∇D ij (q n ) • v + o(τ ), = D ij (q n ) + τ e ij (q n ) • (ũ n j -w)
that is an affine expression which depends on velocities that have already been computing, thanks to the hierarchical ordering. We simply prescribe that the previous expression is non-negative.

The second step (global preservation of non-overlapping constraints) consists in projecting the equilibrated velocity ũn on the set of admissible velocities that ensure the non-overlapping of individuals at each time step. These velocities should satisfy, for all i ̸ = j,

D ij (q n ) + τ e ij (q n ) • (u n j -u n i ) ≥ 0,
that is again the first order expansion of D ij (q n +τ u n ) ≥ 0. It has been shown in Proposition 2, Section 4 in [START_REF] Maury | A time-stepping scheme for inelastic collisions[END_REF] that it is sufficient for the velocity field v to satisfy this condition to be feasible, thanks to the convexity of the distance D ij .

To sum-up, the algorithm reads as follows:

First step

We solve the following minimization problems in the following order i = N, N -1, . . . , 1:

ũn+1 i = argmin w∈C τ i (q n ,ũ n -i ) 1 2 |w -U i (q n i )| 2
where

C τ i (q n , ũn -i ) = w ∈ R d , ∀j ∈ I i (q n ), D ij (q n ) + τ e ij (q n ) • (ũ n j -w) ≥ 0 .
Note that, because of the hierarchical indexing, all indices j correspond to individuals that have already decided their velocity ũn j .

Second step

The vector of equilibrated velocities ũn+1 is projected on the set of globally admissible velocities (with respect to the non-overlapping constraint):

u n+1 = argmin v∈C τ (q n ) 1 2 |v -ũn | 2
where

C τ (q n ) = v ∈ R dN , ∀j ̸ = i, D ij (q n ) + τ e ij (q n ) • (v j -v i ) ≥ 0 .
The minimization problems in the first step are local, they involve a very few degrees of freedom. The problem in the second step is global, thus possibly more expensive, but it is a simple quadratic minimization problem with affine constraints, we propose to solve it by the Uzawa algorithm. The numerical scheme of the hierarchical model will be implemented and

Description of the real experiments and the numerical simulations

We propose to compare the numerical results for the hierarchical model based on the cones of vision defined in Chapter 3 and the granular model [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF] recalled in Chapter 1, and confront the results with real evacuation experiments described in [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF][START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF]. We describe in this section the real experiments used in this chapter to validate the hierarchical model, as well as the parameters used to perform the numerical simulations.

Real experiments

The first set of experiments involved in the comparison are evacuation drills done by Garcimartín et al. [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF]. During these experiments, a total of 85 participants were asked to exit a room through a door of length 75cm. These experiments were performed two times with different competitiveness level. In the first run, individuals were asked to exit the room as fast as they could while trying to avoid physical contact with others and pushing is banned (low competitiveness). In the second run, individuals were asked to do the same but they were allowed to push each other while evacuating (high competitiveness), excluding violent shoving. Other controlled experiments have been described in [START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF] involving 80 participants asked to exit a room through a door of length 72cm and for each run a fixed percentage of pedestrians were asked to behave selfishly, while the rest of individuals were asked to behave politely. The experiments were performed imposing some kind of "periodic boundary conditions" which means that evacuated pedestrians are re-injected in the room again after a while. More details about these experiments are given in Appendix A, and the reader is referred to [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF][START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF] for the complete description of the experimental procedures.

Numerical simulations

In order to compare the hierarchical model to the aforementioned experiments, we run some numerical simulations with the same conditions as for the experiments. We consider a room Ω of size 7m × 7m with one exit of width 75cm situated on the center of a wall. We represent individuals by disks of radii ranging between 17.5cm and 20cm considered as averages between the width and depth of a human body (see Chapter 1 for more details and [START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF][START_REF] Buchmueller | Parameters of pedestrians, pedestrian traffic and walking facilities[END_REF] for a complete description of the parameters of pedestrians). We fix the angle 1 of the cone of vision to α = π/3 and its length to 5m, but we only represent the edges of the influence graph when the distance between two individuals is less or equal to 0.5m. We consider an initial configuration q 0 ∈ K of N individuals randomly distributed on Ω and we fix the time step to τ = 0.1s. The desired velocities at each time step point toward the exit door. In particular, we consider the case where the desired velocity field is the opposite of the gradient of the distance to the exit door: U (q) = -∇D(q).

We run numerical simulations in the following three cases: the granular model, the hierar- The disks representing individuals have colors that corresponds to their instantaneous frustration defined in [START_REF] Faure | Crowd motion from the granular standpoint[END_REF] by:

chical
f i = 1-(u i • U i )/|U i | 2 for each individual i. It is a dimensionless
quantity, that measures the farness of the actual velocity from the desired one. It equal to 0 when the individual achieves his desired velocity and equal to 1 when the individual is not moving or has an actual velocity orthogonal to his desired one. As it has been mentioned in [START_REF] Faure | Crowd motion from the granular standpoint[END_REF], for the case of a desired velocity written as the gradient of a dissatisfaction functional, we have: which means that f i is larger or equal to 1 when individual i is not reducing his dissatisfaction.

d dt D(q i ) = ∇D • dq i dt = -u i • U i = f i -1, ∀i = 1, . . . , N
The color of the disks ranges between white and red, white being for individuals going at their desired velocity (low frustration level) and red for individuals not satisfied at all with their actual velocities (high frustration level).

Comparison between modeling results and empirical data

In this section, we confront the numerical results of the hierarchical model based on the cones of vision with the low competitiveness experiment by Garcimartín et al. [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF] and the second set of experiments by Nicolas et al. [START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF] (purposeful walkers) with 100% selfish individuals.

Particularly we are interested in investigating the alternation between short and long time lapses and the power-law distribution of time lapses.

Alternation between short and long time lapses

This effect has been reported in [START_REF] Serge P Hoogendoorn | Extracting microscopic pedestrian characteristics from video data[END_REF][START_REF] Serge | Pedestrian behavior at bottlenecks[END_REF][START_REF] Seyfried | New insights into pedestrian flow through bottlenecks[END_REF][START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF] and was ascribed to a generalized zipper effect in [START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF]. A first comparison test is done to investigate whether the hierarchical model based on cones of vision is able to produce the effect of alternation between short and long time lapses. For this purpose, we compare the correlation function for numerical results with those of real data from the experiments described in [START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF] and [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF].

The correlation function between time lapses (∆t j ) j ordered by the rank of exit is defined by:

C(k) = ⟨(∆t j -⟨∆t⟩)(∆t j+k -⟨∆t⟩)⟩ ⟨(∆t j -⟨∆t⟩) 2 ⟩

Power-law distribution of large time lapses

We are also interested in comparing the probability of occurrence of large time lapses between consecutive egresses for numerical simulations and real experiments. This probability gives us an idea about the frequency of clogging in evacuation processes. For this purpose, we follow the procedure done in [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF] where the authors plotted the complementary cumulative distribution function (CCDF) for the two runs (low and high competitiveness), which is one minus the cumulative distribution function of time lapses. This probability distribution is computed as follows: we order the time lapses from smaller to larger, and for every time lapse distribution. Note that the fact that the exponents of the power-law are greater than 3 is highly significant. Actually, when it is not the case, i.e. when the exponent is strictly less that 3, the average time lapse between consecutive egresses (first moment of the probability distribution) may not converge, inducing undefined average flow rate and mean evacuation time.

Discussion

The hierarchical model compares favorably to the experiments by Garcimartín et al. [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF] with low competitiveness level. Actually, it has already been shown in Proposition 3. Regarding the experiments by Nicolas et al. [START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF], the hierarchical model compares favorably to the experiment of purposeful crowd with 100% selfish pedestrians. This result may seem paradoxical, but it has been reported in [START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF] that the highest attained level of competitiveness in the experiments is low compared to the competitiveness level of the experiments by Garcimartín et al. [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF]. Particularly, the Faster is Slower effect is not observed, but on the contrary, a Faster is Faster effect is reported. The authors claim that this result is not contradictory to the one obtained in other experiments, but is simply due to the low competitiveness level even for the most selfish participants in the experiment. The competitiveness threshold is not attained to observe such effect.

Comparison between different modeling results

We propose in this section to compare three situations of simulations described in Section 4.

j δt (t) = 1 δ t j H(t j -t)H(t + δ t -t j ) ( 4 . 1 )
where H is the Heaviside function:

H(t j -t)H(t + δ t -t j ) = ⎧ ⎨ ⎩ 1, if t ≤ t j ≤ t + δ t 0, otherwise
and (t j ) j are the exit times ordered by the rank of egress. We compare the granular model to the hierarchical model based on the cones of vision in order to show the Faster is Slower effect, or equivalently the Slower is Faster effect. The effect of an obstacle is also investigated in section. We compare different shapes of obstacles (one pillar, two pillars, triangular shape and reversed V shape) and show that the reversed V obstacle is more efficient than the others.

We compare the average flow for evacuation simulations with and without an obstacle and show that the presence of an obstacle fluidifies the evacuation.

Faster is Slower

First, we compare two non-periodic evacuation simulations for the hierarchical model based on the cones on vision and the granular model and find out whether these models are able to reproduce this effect. In fact, individuals in the hierarchical model are considered civilized and respectful, while for the granular model, individuals are rather aggressive and selfish, considered as in competition to exit the room the fastest possible up to pushing people in front of them. It has been already proved in Proposition 3.2.5 that the decision process based on the visual information of each pedestrian reduces his desired velocity in his desired direction of motion. As a consequence, individuals have a tendency to go slower in the direction where they want to go for the hierarchical model based on cones of vision, compared to the granular model. The effect we seek to recover here is rather a "Slower is Faster" effect, which is equivalent to the classical Faster is Slower effect. Some snapshots of the evacuation simulations are represented in Figure 4.17 to illustrate a first difference point between the two models. For example, the second snapshot of the granular evacuation shows a jam occurring upstream the exit door while for the hierarchical is done in [START_REF] Faure | Crowd motion from the granular standpoint[END_REF] and the authors showed that the duration of jams is related to the width of the door. If the latter is smaller that 2 times the diameter of pedestrians, a stable jam systematically develops, while if it is greater than 2.7 times the diameter of individuals, the evacuation always gets to its end.

The periodic evacuation simulations also emphasizes this effect. We empirically compute the mean of time lapses between consecutive egresses and the flow mean for the granular model and the hierarchical model. The result is displayed in Table 4. to the flow rate of the hierarchical model. This is due to the creation of jams apparent in the sudden fall of the flow rate many times during the evacuation. However, the flow rate of the hierarchical model seems to be more stable in general with higher values of flow rate.

Also, the exponent of the power-law distribution of large time lapses for the granular model is 2.64 which is very low compared to the one obtained for the hierarchical model based on cones of vision (5.67) which means that long time lapses are more likely to occur in this case.

Although the exponent for the granular model is not close to the one obtained for the high competitiveness case of the experiments (4.83), the variation of the exponents goes in the right direction (the exponent decreases with the increasing competitiveness level).

Model

Effect of an obstacle

It is known for evacuation situations that placing an obstacle upstream the exit door boosts the outward flow. In order to explore whether the hierarchical model is able to reproduce this effect, we start by searching for the obstacle shape that increases most the outward flow. For this purpose, we consider four different shapes of obstacles: one pillar, two pillars, triangular shape and reversed V shape, and run periodic evacuation simulations for each shape. Snapshots of the simulations are displayed in Figure The highest average flow is observed for the case of a reversed V obstacle. The average flow of pedestrians is 3.18 ± 0.04 pers/s for the simulation of the hierarchical model without obstacle, whereas it is 3.6 ± 0.027 pers/s with a reversed V obstacle upstream the door, so the average flow of pedestrians increases by 13.2%, which proves the ability of the model to reproduce this effect. We also run some non-periodic evacuation simulations and compare the evacuation time in the absence and the presence of an obstacle. An example is shown in Figure (4.17) showing that the evacuation gets to its end faster in the case of the obstacle.

Capacity drop

The capacity drop is a phenomenon known to occur in evacuation situations. When the density upstream the door increases, the outward flow increases as well until a certain critical value of the density, then decreases slightly and attain a stable level afterwards. To test the ability

Motivations

This chapter addresses the possibility to write a macroscopic counterpart of the hierarchical model described in Chapter 3 in the spirit of the transition made to write the macroscopic counterpart [START_REF] Maury | A macroscopic crowd motion model of gradient flow type[END_REF][START_REF] Maury | Handling congestion in crowd motion modeling[END_REF] of the granular model [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF], both recalled in Chapter 1.

In the microscopic granular model, individuals are represented by disks subject to nonoverlapping constraints. It is based on the following two principles: each individual has a desired velocity, it is the one he would like to have in the absence of others, and the actual velocity field of the crowd is defined as the projection of the desired velocity field on the set of admissible velocity fields that do not allow an overlapping of disks representing individuals. The macroscopic counterpart of the granular model is written by considering the same modeling principles at the macroscopic level. The crowd is represented by a density ranging between zero and a prescribed maximum density. The model is also based on two principles: the crowd has a desired velocity field that represents individuals' tendencies if they were alone, and the actual velocity field is defined as the projection of the desired velocity field on the set of admissible velocity fields that do not increase the density in the already saturated zones. The mathematical formulation of both models is recalled in Section 5.2.

The hierarchical model described in Chapter 3 is based on the same representation of individuals as for the granular model. We consider that an individual is not necessarily influenced by all the others and suppose that the interactions between individuals are hierarchical, i.e. no cycles of individuals influencing each other exist. We consider here the case where each individual is influenced by others in his cone of vision, which natively gives hierarchical relations in evacuation cases. The actual velocity field is computed in two steps. First, a decision step where each individual chooses an equilibrated velocity that approaches best his desired one among all velocities that do not violate the non-overlapping constraints with his leaders. Second, a correction step to handle collisions that have not been anticipated by individuals, i.e. collisions between individuals that do not see each other. This step is performed by projecting the equilibrated velocity field on the set of globally admissible velocity fields that do not allow an overlapping of disks representing individuals. Note that for the granular model, the desired velocity field is directly projected on the set of admissible velocity fields, while for the hierarchical model, we compute first the equilibrated velocity field that takes into consideration the willing of each individual to respect others in his cone of vision, and then project the equilibrated velocity field on the set of admissible velocity fields.

Looking to the transition between the granular model and its macroscopic counterpart, a natural question arises: is it possible to write a macroscopic counterpart of the hierarchical model based on the cones of vision by translating its modeling principles to the macroscopic level as for the granular model? This question raises many issues, some of which are discussed along the chapter. We also make the first steps towards writing such model.

The granular model and its macroscopic counterpart

In this section, we briefly recall the mathematical framework of the granular model and its macroscopic counterpart and describe the difference between them. We refer the reader to [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF][START_REF] Maury | A macroscopic crowd motion model of gradient flow type[END_REF][START_REF] Maury | Handling congestion in crowd motion modeling[END_REF] for more details.

We start by describing the granular model. Consider N individuals represented by rigid disks of centers q 1 , . . . , q N ∈ R d , for d = 1, 2, and respective radii r 1 , . . . , r N . The configuration of all individuals is denoted by q = (q 1 , . . . , q N ) ∈ R dN . Each individual i has a desired velocity U i (q i ) and we denote by U (q) the desired velocity field of all individuals. The set of admissible configurations is defined by:

Q = q ∈ R dN , D ij (q) ≥ 0, ∀i ̸ = j
where D ij (q) = |q iq j |r ir j is the distance between individuals i and j. For an admissible configuration of individuals q, the actual velocity u(q) = (u 1 , . . . , u N ) is the unique solution of the minimization problem:

u(q) = argmin v∈C(q) 1 2 |v -U (q)| 2 (5.1)
where

C(q) = v ∈ R dN , ∀i ̸ = j, D ij (q) = 0 ⇒ e ij (q) • (v i -v j ) ≤ 0 (5.2)
and e ij (q) = (q jq i )/|q jq i |. This is equivalent to say that the actual velocity field u is the euclidean projection of the desired velocity field U on the set of admissible velocity fields C(q): u = P C(q) U . The evolution problem is shown to be well posed in [START_REF] Maury | A discrete contact model for crowd motion[END_REF][START_REF] Venel | Modélisation mathématique et numérique des mouvements de foule[END_REF] and the proof is based on a reformulation of the problem as a differential inclusion using sweeping processes [START_REF] Jacques | Evolution problem associated with a moving convex set in a Hilbert space[END_REF], and the theory in [START_REF] Fenel | Relaxation of an optimal control problem involving a perturbed sweeping process[END_REF][START_REF] Fenel | BV solutions of nonconvex sweeping process differential inclusion with perturbation[END_REF] is used to prove the existence and uniqueness of solutions.

In [START_REF] Maury | A macroscopic crowd motion model of gradient flow type[END_REF][START_REF] Maury | Handling congestion in crowd motion modeling[END_REF], a macroscopic counterpart of the granular model is introduced. The crowd is represented by a nonnegative density ρ constrained to remain below a prescribed maximum density supposed equal to 1 without loss of generality. The crowd has a desired velocity field U such that U (x) would be the desired velocity of an individual standing at x. For simplicity reasons, we represent here the case of a domain Ω without exits and refer the reader to [START_REF] Maury | A macroscopic crowd motion model of gradient flow type[END_REF] for the full description of the model. The actual velocity field u is defined as the closest, in the least squares sense, to the desired velocity field U among all velocity fields that do not concentrate the density of the crowd in the already saturated zones (congestion constraint),

i.e. those whose (weak) divergence is nonnegative on saturated zones. We denote by K the set of admissible densities defined by: K = {ρ ∈ P(Ω), ρ ≤ 1 a.e. in Ω} .

(5.3) 84

The granular model and its macroscopic counterpart

The actual velocity field is the unique solution of the problem:

min v∈C(ρ) 1 2 Ω |U -v| 2 (5.4)
where

C(ρ) = v ∈ L 2 (Ω), Ω v • ∇q ≤ 0 ∀q ∈ H 1 ρ (Ω) (5.5)
and

H 1 ρ (Ω) = q ∈ H 1 (Ω), q ≥ 0, q(1 -ρ) = 0 a.e. in Ω . ( 5.6)
The solution of this minimization problem is then the projection of the desired velocity field U on the set of admissible velocity fields C(ρ): u = P C(ρ) U . In the case where the desired velocity field has a gradient structure, e.g. U = -∇D where D is the distance to the target, the problem is shown in [START_REF] Maury | A macroscopic crowd motion model of gradient flow type[END_REF] to correspond to the gradient flow of the functional Φ defined below, in the Wasserstein spaces of probability measures:

Φ(ρ) = ⎧ ⎨ ⎩ Ω D(x)dρ(x), if ρ ∈ K, +∞, otherwise.
An example of evacuation simulation for this model is displayed in Figure 5.1, and Figure 5.

2
shows two evacuation simulations for the same initial condition using the granular model and its macroscopic counterpart.

These models describe highly congested crowds with selfish and aggressive agents. The individuals are allowed to push each other when they are in contact for the granular model, or when the density is saturated for its macroscopic counterpart. The defect of this macroscopic model is that evacuation is always smooth, notably jams never occur and neither Faster is Slower effect nor capacity drop could be observed. On the contrary, a "Faster is Faster" effect is observed (the quickier individuals want to go, the quickier they really go). Actually, a macroscopic density is moldable so it could not be clogged upstream an exit door, whereas the disks representing individuals in the granular model are rigid and undeformable which makes the interaction between individuals considerable. The fact that the macroscopic counterpart of the granular model does not reproduce crowd effects related to the reduction of the capacity of a bottleneck enlightens the high dependence of jams upon geometrical representation.

First approach

The aim of this section is to propose a macroscopic counterpart of the hierarchical model by roughly translating the velocity constraints from the microscopic level to the macroscopic one. The crowd is represented by a density ranging between zero and a prescribed maximum density. We consider a desired velocity field that corresponds to the preferred motion of an individual if he is alone in the domain. We associate a field of cones of vision to the desired velocity field: at every point of the domain, we consider the cone of vision centered in the direction of the desired velocity at that point with a fixed angle.

The admissible velocity fields should satisfy the congestion constraint, that is not increasing the density in the already saturated zones. The directional character of the interactions between individuals for the hierarchical model is translated by a condition on the velocity correction, that is the actual velocity minus the desired one. We impose to the velocity correction to belong to the opposite of the cone of vision at every point of the domain, which means that the actual velocity could only be smaller or equal to the desired velocity in the directions of the cone of vision. We define then the actual velocity field as the closest, in the least squares sense, to the desired velocity field among all admissible velocities satisfying the congestion constraint and the directional condition. For the case of an evacuation, the desired velocity field points to the exit and then the associated field of cones of vision induce a natural hierarchy on the crowd. Individuals who are the closer to the door are the most influential ones, and the farther they get, the lesser influence they have.

Mathematical formulation

Consider a domain Ω ⊂ R d , whose boundary Γ is composed of the exit Γ out and the walls Γ w .

The maximum density is supposed equal to 1 in the interior of Ω, without loss of generality.

We suppose that the density can be concatenated on Γ out , notably, the mass that exits the domain will be stocked at Γ out . The set of admissible densities is

K = ρ ∈ P( Ω), ρ = ρ Γout + ρ Ω , ρ Ω ≤ 1 a.e. , supp ρ Γout ⊂ Γ out . ( 5.7)
We consider a desired velocity field U sufficiently smooth. In evacuation situations, a natural example of desired velocity field is U = -∇D where D is the distance to the exit door. We suppose that the cones of vision V (., U ) have a fixed angle < π/2 to the left and right of the line of sight. For every x ∈ Ω, the cone of vision at x is defined by:

V (x, U ) = w ∈ R 2 , w • n i (x, U ) ≤ 0, i = 1, 2 .
where n 1 (x, U ) and n 2 (x, U ) are the outward normal vectors to the half-planes forming the cone (see Figure 5.3 for an example). We omit the dependence of n 1 and n 2 on the space variable and U for simplicity reasons. Admissible velocity fields are constrained to have a nonnegative (weak) divergence on saturated zones, formalized in a dual manner, and the correction made on the desired velocity field U , that is u -U should belong to the opposite of the field of cones of vision V (., U ). We denote by C(ρ, U) the set of admissible velocity fields:

n 1 n 2 U i q i
C(ρ, U) = v ∈ (L 2 (Ω)) 2 , Ω v • ∇q ≤ 0, ∀q ∈ H 1 ρ (Ω), v -U ∈ -V (., U ) a.e. ( 5.8)
where H 1 ρ (Ω) = q ∈ H 1 (Ω), q ≥ 0 a.e. in Ω, q = 0 a.e. in [ρ < 1], q Γout = 0 .

(5.9)

The actual velocity field is then solution to the minimization problem:

u = argmin v∈C(ρ,U ) J(v) = argmin v∈C(ρ,U ) 1 2 Ω |U -v| 2 (5.10)
which is equivalent to say that u = P C(ρ,U ) U . Proof. The functional J is strictly convex and l.s.c., and the set C(ρ, U) is closed and convex, thus Problem (5.10) has a unique solution.

One dimensional case

In this case, the solution of Problem (5.11) can be computed explicitly on each interval where the density is saturated. Problem (5.10) reads:

u = argmin v∈C(ρ,U ) J(v) = argmin v∈C(ρ,U ) 1 2 Ω |U -v| 2 (5.11)
where U (y) ≤ u(x) < U(x) which contradicts the fact that u is increasing and bounded from above by U , then we necessarily have u = ū.

C(ρ, U) = v ∈ L 2 (Ω), Ω v q ′ ≤ 0 ∀q ∈ H 1 ρ (Ω), v ≤ U a.

Example

We show in Figure 5.4 an example of desired velocity and its corresponding actual velocity according to Problems (5.4) and (5.11). We suppose that the density is saturated on ]0, 1[. For This setting resembles to the one represented in Section 4.1 in [START_REF] Berthelin | A model for the formation and evolution of traffic jams[END_REF], where the authors consider two sticky blocks (clusters) transported in the same direction with different velocities (the block on the left has a velocity greater than the one on the right). When collision occurs, the two blocks form a new one evolving according to the velocity of the block on the right.

Twofold saddle point formulation and numerical solution

We propose in this section to solve numerically Problem (5.10) using its twofold saddle point formulation and applying the Uzawa algorithm. For this purpose, we start by introducing two linear operators B 1 and B 2 defined below as well as their adjoints:

B 1 : (L 2 (Ω)) 2 -→ (H 1 ρ (Ω)) ′ v -→ -∇ • v B * 1 : H 1 ρ (Ω) -→ (L 2 (Ω)) 2 q -→ ∇q B 2 : (L 2 (Ω)) 2 -→ L 2 (Ω) × L 2 (Ω) v -→ (-v • n 1 , -v • n 2 ) B * 2 : L 2 (Ω) × L 2 (Ω) -→ (L 2 (Ω)) 2 (δ 1 , δ 2 ) -→ -δ 1 n 1 -δ 2 n 2
It can be easily shown that the linear operators B 1 and B 2 are continuous (note that the vectors n 1 and n 2 are sufficiently smooth because they only depend on the space variable and U which is sufficiently smooth). The set of admissible velocity fields can be written using these operators as:

C(ρ, U) = v ∈ (L 2 (Ω)) 2 , ⟨B 1 v, q⟩ ≤ 0, ∀q ∈ H 1 ρ (Ω), B 2 (v -U ) ≤ 0 a.e.
and the Lagrangian of Problem (5.10) reads:

L(v, q, δ) = 1 2 ||U -v|| 2 L 2 + ⟨B 1 v, q⟩ + ⟨B 2 (v -U ), δ⟩. for (v, q, δ) ∈ L 2 (Ω) × H 1 ρ (Ω) × (L 2 + (Ω))
⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ u -U + B * 1 p + B * 2 λ = 0, ⟨B 1 u, q⟩ ≤ 0, ∀q ∈ H 1 ρ (Ω), ⟨B 2 (U -u), δ⟩ ≤ 0, ∀δ ∈ (L 2 + (Ω)) 2 , ⟨B 1 u, p⟩ = 0, ⟨B 2 (U -u), λ⟩ = 0.
(5.12)

Proof. The proof is a straightforward application of Proposition 2.4, page 176 of [START_REF] Ekeland | Convex analysis and variational problems[END_REF]. The Lagrangian is actually concave, u.s.c. in its primal variable, and convex, l.s.c. in its dual variables.

The twofold saddle-point formulation (5.12) can be solved numerically using the Uzawa algorithm. We present the numerical scheme in the following paragraph and show a first example of computation of actual velocity field for Problem (5.10).

Uzawa Algorithm

The Uzawa algorithm is commonly used to solve saddle-point problems. The algorithm consists in constructing a sequence of multipliers (p k , λ k ) k such that the associated sequence in the primal space (u k ) k converges to the unique solution of the primal problem (5.10). It is actually a way to replace a constrained minimization problem by a sequence of unconstrained minimization problems. The Uzawa algorithm is built as follows:

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ u k+1 = U -B * 1 p k -B * 2 λ k , p k+1 = [p k + r B 1 u k+1 ] + , λ k+1 = [λ k + r B 2 (U -u k+1 )] + (5.13)
where r is a fixed parameter.

Remark that B 1 u k+1 belongs to (H 1 ρ (Ω)) ′ , while p k and p k+1 belong to H 1 ρ (Ω) which makes it necessary to identify the Hilbert space H 1 ρ (Ω) with its dual (H 1 ρ (Ω)) ′ . On one hand, we have:

⟨B 1 u k+1 , v⟩ = Ω u k+1 • ∇v, ∀v ∈ H 1 ρ (Ω)
by definition of the duality brackets in L 2 (Ω), and on the other hand, we have:

⟨B 1 u k+1 , v⟩ = Ω ξ k+1 • v + Ω ∇ξ k+1 • ∇v, ∀v ∈ H 1 ρ (Ω)
using the scalar product of H 1 (Ω) where ξ k+1 is the representative of B 1 u k+1 in H 1 ρ (Ω). So by identification, ξ k+1 is the solution of the following variational problem:

⎧ ⎨ ⎩ Ω ξ k+1 • v + Ω ∇ξ k+1 • ∇v = Ω u k+1 ∇v, ∀v ∈ H 1 ρ (Ω) ξ = 0, on Γ out
⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ u k+1 = U -B * 1 p k -B * 2 λ k , ξ k+1
solution of Problem (5.14)

p k+1 = [p k + r ξ k+1 ] + , λ k+1 = [λ k + r B 2 (U -u k+1 )] + (5.15)
The convergence of the algorithm is ensured provided that the parameter r satisfies:

0 < r < 2c ||B 1 B * 1 || + ||B 2 B * 2 ||
where c is the coercivity constant of the bilinear form associated to J (see [START_REF] Ciarlet | Introduction a l'analyse numerique matricielle et a l'optimisation[END_REF] for more details about the convergence of the Uzawa algorithm).

We aim now to compare the macroscopic counterpart of the hierarchical model described by Problem (5.10) to the macroscopic counterpart of the granular model described by Prob-lem (5.4). We start by writing the saddle-point formulation for Problem (5.4): (5.16) where B 1 has been defined earlier in this section by:

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ u -U + B * 1 p = 0, ⟨B 1 u, q⟩ ≤ 0, ∀q ∈ H 1 ρ (Ω), ⟨B 1 u, p⟩ = 0,
B 1 : (L 2 (Ω)) 2 -→ (H 1 ρ (Ω)) ′ v -→ -∇ • v
We also use the Uzawa algorithm to compute a numerical solution of Problem (5.16):

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ u k+1 = U -B * 1 p k ξ k+1
solution of Problem (5.14)

p k+1 = [p k -r ′ ξ k+1 ] + .
(5.17)

where r ′ satisfies 0 < r ′ < 2c/||B 1 B * 1 || to ensure the convergence of the algorithm.

Example:

We show in Figure 5.5 an example of computation of the actual velocity for Problems (5.4) and (5.10). We consider a convergent corridor where the density of the crowd is saturated. We suppose that all individuals want to exit the domain through its narrowest part with a velocity of modulus 1. The actual velocity fields according to Problems (5.4) and (5.10) are computed using the Uzawa algorithms (5.17 For the solution of Problem (5.4), the individuals in the narrowest part of the domain are pushed by the ones who are behind them and go at a velocity of module ≃ 2. The module of the actual velocity then decreases when the corridor gets wider. The situation is not the same for the solution of Problem (5.10) where the individuals in the narrowest part of the domain go at their desired velocity of module 1, i.e. they are not pushed by the others. The module of the actual velocity then decreases when the corridor gets wider with a minimum module of actual velocity less than the one for Problem (5.4).

Second approach

We propose in this section another perspective to define a macroscopic counterpart of the hierarchical model. Instead of minimizing the L 2 -norm of the desired velocity field minus the actual one under congestion and directional constraints as for the first approach, we propose to minimize a weighted L 2 -norm of their difference under congestion constraint only.

The constraint on the correction of the desired velocity field is relaxed by considering weight functions on the domain depending on the distance to the exit door and a parameter ϵ. We consider that the weight of a point is always greater than the weight of another one situated farther from the exit, and their ratio tends to +∞ when ϵ tends to 0. These weight functions quantifies how much an individual takes on himself and respects others that are closer than him to the exit door, and at the limit, the interaction between them becomes completely asymmetric. The hierarchy on the crowd follows then automatically by the choice of the weight functions.

We aim to prove that the sequence of minimizers converges to a macroscopic counterpart of the hierarchical solution. The proof is restricted here to dimension one. A similar result can be expected in higher dimensions, but raises additional issues which are under current investigation.

Mathematical formulation

We use the same notation of Section 5.3. For ϵ > 0, we consider the following minimization problem:

min v∈C(ρ) J ϵ (u) = min v∈C(ρ) 1 2 Ω a ϵ |U -v| 2 (5.18)
where

C(ρ) = v ∈ (L 2 (Ω)) 2 , Ω v • ∇q ≤ 0 ∀q ∈ H 1 ρ (Ω)
and a ϵ is smooth and reflects the distance to the door in the following way:

• For every x, y ∈ Ω such that D(x) < D(y), we have: a ϵ (x)/a ϵ (y) → +∞ when ϵ -→ 0.

• a ϵ is positive and attain its maximum only on Γ out .

For example, one can consider: a ϵ (x) = e 1 (D(x)+1)ϵ , ∀x ∈ Ω. Note that the approach presented in Section 5.3 and the one presented in this section are equivalent in dimension one. Notably, we prove in Proposition 5.4.5 below that the sequence of minimizers for Problems (5.18) converges to the unique solution of Problem (5.11) in dimension one.

Remark 5.4.1. The microscopic version of this family of minimization problems reads for

N individuals:

min v∈C(q) 1 2 N i=1 m ϵ,i (q i )|v i -U i (q i )| 2 (5.19)
where C(q) is defined by (5.2) and m ϵ,i (q i ) = a ϵ (q i ) is the weight attributed to individual i.

We proved in

One dimensional setting

Let Ω =]0, 1[ be a domain where the density of the crowd is saturated. We assume that all individuals want to reach the exit door located on the right (U = 1). Problem (5.18) reads in dimension one:

min v∈C(ρ) J ϵ (u) = min v∈C(ρ) 1 2 Ω a ϵ |U -v| 2 (5.20)
where

C(ρ) = v ∈ L 2 (Ω), Ω v q ′ ≤ 0 ∀q ∈ H 1 ρ (Ω) .
or in other words, v ∈ L 2 (Ω) is increasing. We aim to prove that the sequence of minimizers of Problem (5.20) converges to the unique solution of Problem (5.11). We start by proving some lemmas.

Lemma 5.4.3.

There exists a subsequence of minimizers (u ϵ ) ϵ ⊂ L 2 (Ω) converging a.e. to a function u ∈ L 2 (Ω) that is increasing and bounded.

Proof. We can easily show that for every ϵ > 0, we have: min U ≤ u ϵ (x) ≤ max U for a.e. x ∈ Ω. Actually, suppose that there exists a non zero measure set A ⊂ Ω such that u ϵ (x) < min U for a.e. x ∈ A, then by setting u ϵ equal to min U on this set, one does better.

We follow the same reasoning to show that u ϵ (x) ≤ max U . Taking into consideration the fact that u ϵ is an increasing function, bounded on ]0, 1[, the sequence (u ϵ ) ϵ is bounded in BV(Ω). Since BV(Ω) is compactly injected in L 1 (Ω) (Sobolev embedding theorem) and Ω has a finite measure, there exists a subsequence of u ϵ , that we still denote by u ϵ , such that u ϵ converges a.e. to u ∈ L 1 (Ω) and u is particularly in BV(Ω). Since min U ≤ u ϵ (x) ≤ max U for a.e. x ∈ Ω and u ϵ is increasing, then we have: min U ≤ u(x) ≤ max U for a.e. x ∈ Ω and u is also increasing.

Lemma 5.4.4. The limit u of the sequence of minimizers (u ϵ ) ϵ satisfies u(x) ≤ U (x) for a.e.

x ∈ Ω.

Proof. The sequence of minimizers (u ϵ ) ϵ and their limit u belong to BV(Ω), thus the right and left limits exist at every point in Ω. We aim to show first that lim • If u(1 -) < U(1 -), then there exists ϵ 0 > 0 such that ∀ϵ < ϵ 0 , we have u ϵ (1 -) < U(1 -).

By the definition of the left limit, ∀e > 0, there exists δ > 0 such that

|u ϵ (x) -u ϵ (1 -)| < e whenever 1 -δ < x < 1.
For e sufficiently small, we have

u ϵ (x) < U(1 -), ∀x ∈]1 -δ, 1[. By letting u ϵ (x) = min y∈[x,1[
U (y), ∀x ∈]1δ, 1[, one does better which contradicts the fact that u ϵ is a minimizer of Problem (5.20).

• If u(1 -) > U(1 -), then there exists ϵ 0 > 0 such that ∀ϵ < ϵ 0 , we have

u ϵ (1 -) > U(1 -).
By the definition of the left limit, ∀e > 0, there exists δ > 0 such that

|u ϵ (x) -u ϵ (1 -)| < e whenever 1 -δ < x < 1
So for e sufficiently small, we have u ϵ (x) > U(1 -), ∀x ∈]1δ, 1[. When ϵ gets smaller, a ϵ becomes extremely large on ]1δ, 1[ so the gap between u ϵ and U on this interval becomes very expensive compared with any possible gap elsewhere. Hence by letting u ϵ (x) closer to U (x) when ϵ approaches 0, such that at the limit u(1 -) becomes equal to U (1 -), one does better.

To prove that u(x) ≤ U (x), we suppose by contradiction that there exists a non-zero measure set A ⊂ Ω such that u(x) > U(x) a.e. in A. We follow the same reasoning as for u(1

-) > U(1 -)
to come to a contradiction.

We prove in the following proposition that the limit of the sequence of minimizers is the unique solution of Problem (5.11). x ∈ A. Thus:

Ω a ϵ |ū -U | 2 < Ω a ϵ |u ϵ -U | 2
which contradicts the fact that u ϵ is a minimizer of Problem (5.20).

This chapter corresponds to the paper [START_REF] Reda | Interpretation of Finite Volume discretization schemes for the Fokker Planck equation as gradient flows for the discrete Wasserstein distance[END_REF] by Fatima Al Reda and Bertrand Maury, to appear in "Topological Optimization and Optimal Transport in the Applied Sciences"(De Gruyter) in July 2017.

Introduction

We aim here at identifying gradient flow structures in some space-discretization schemes of the Fokker-Planck equation on general meshes, in the spirit of the approaches proposed recently in [START_REF] Disser | On gradient structures for Markov chains and the passage to Wasserstein gradient flows[END_REF][START_REF] Maas | Long-time behavior of a finite volume discretization for a fourth order diffusion equation[END_REF] for cartesian discretizations. Since the core of the paper consists in building links between macroscopic notions / properties and their discrete counterparts, in a context where two reference measures are present (uniform Lebesgue measure and stationary measure associated to an attractive potential), let us start by fixing some principles in terms of notation.

Probability measures will be denoted by the letter p (we shall use the same letter to denote their density with respect to the underlying Lebesgue measure, or its discrete counterpart), stationary measures (with respect to some evolution process) by π, and relative densities with respect to π by ρ. All discrete notions will be singled out by a tilda sign, e.g. p, π, etc ... The space variable will be denoted by r, while x and y will be used to denote discrete vertices.

Since the seminal work of Jordan, Kinderlehrer and Otto [START_REF] Jordan | The variational formulation of the Fokker-Planck equation[END_REF] in 1998, it is known that the Fokker-Planck (FP) equation in a domain Ω:

∂ t p -∆p -∇ • (p∇Φ) = 0,
with appropriate no-flux boundary conditions, can be interpreted in the Wasserstein space as the gradient flow for

H(p) = Ω p log p π dr = Ω ρ log (ρ) dπ with ρ = p/π ,
that is the relative entropy with respect to the stationary measure π = e -Φ , up to a normalization constant. This property is schematized in the diagram below (see Fig. 6.

1, blocks

A -B -C, on the top), and we refer the reader to [START_REF] Ambrosio | Gradient flows: in metric spaces and in the space of probability measures[END_REF][START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF] for a thorough description of the underlying theory.

At the discrete level, a similar framework has been proposed in [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF][START_REF] Mielke | A gradient structure for reaction-diffusion systems and for energy-drift-diffusion systems[END_REF]. The euclidean domain is replaced by a network N, defined by its (finite) set of vertices V and a Markovian kernel

(K(x, y)) x,y∈V , with K(x, y) ≥ 0 , y∈V K(x, y) = 1 ∀x ∈ V.
The stationary measure is denoted by π, it verifies π = t K π. It is unique as soon as K is irreducible, i.e. ∀ x, y ∈ V there exists a path (x 0 = x, x 1 , x 2 , . . . , x m = y) such that K(x, x 1 ) × K(x 1 , x 2 ) × . . . × K(x m-1 , y) > 0, and then π(x) > 0 for all x ∈ V . We say that K is reversible if π(x)K(x, y) = K(y, x) π(y) for all x, y in V (detailed balance equation

dρ/dt + (I -K)ρ = 0 dp/dt + (I -t K)p = 0 ∂ t p -∆p -∇ • (p∇Φ) = 0 or ∂ t ρ -1 π ∇ • (π∇ρ) = 0 with t K π = π, ρ = p/π. with π = e -Φ , ρ = p/π. H(p) = p log(p/π) dx H(ρ) = x∈V ρ(x) log(ρ(x))π(x). Gromov Hausdorff convergence convergence convergence Space disc. quadrature π = e -Φ . A B C Ã B C 1 3 1 ′ 2 3 ′
Heat flow on a network K = (K(x, y))

∂ t ρ + (I -K) ρ = 0, (6.1)
where ρ is the density of a probability measure p on V with respect to π. Note that the straight discrete counterpart of FP equation would be an equation of the measure p itself, with K replaced by t K, and p(x) = 1, but we shall follow [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF] in favoring densities with respect to π, i.e. densities ρ verifying ρ(x) π(x) = 1. It has been established in [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF] that (6.1), for an appropriate metric W 2 which is the discrete counterpart of the standard Wasserstein distance, is a gradient flow of the discrete relative entropy

H( ρ) = x∈V ρ(x) log( ρ(x)) π(x) ( 6 . 2 )
with respect to the Wasserstein-like metric W 2 (see Section 6.2 for detailed definitions).This discrete setting is also schematized in Fig. 6.1 (blocks à -B -C, on the bottom).

Although it was not the original purpose in [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF], a connection can be made between the two settings by means of discretization strategies. As detailed in the next section, an euclidean domain Ω can be partitionned into cells (e.g. Voronoï cells associated to a collection of points in the domain, see Fig. 6.2). Now consider the network associated to those cells (one may consider that the vertices are the centroids of the cells). To any measure µ on Ω one can associate a discrete measure that is, for each vertex associated to cell K, the measure µ(K).

As detailed in [START_REF] Gigli | Gromov-Hausdorff Convergence of Discrete Transportation Metrics[END_REF], a link can be made between the Wasserstein distance on the euclidean domain and the discrete Wasserstein distance on the network, at least in the case of a regular decomposition (cartesian grid). This link will be described more precisely in the next section, it is indicated by the arrow 2 in Fig. 6.1 that relates blocks B and B. Besides, integrating any function of the density at the continuous level has a discrete counterpart (we are especially interested in entropy-like functionals), it consists in summing up the corresponding values for the discrete densities built as described above. This approach can be seen as a quadrature formula to compute the approximation of an integral, for which convergence properties can be expected as the cell decomposition is refined. It is indicated by the arrow 3 in Fig. 6.1 that relates blocks C and C.

The core of the present article is an attempt toward closing the diagram by expliciting the link between blocks A and à (arrow 1). More precisely, we aim at showing that, in the context of Finite Volume methods, some space discretization strategies of the FP equation lead to Ordinary Differential Equation that are consistent with the gradient flow structure on the underlying network. Note that this interpretation of Finite Volume discretization schemes as gradient flows has already been addressed in two recent papers. In [START_REF] Maas | Long-time behavior of a finite volume discretization for a fourth order diffusion equation[END_REF], the authors use this gradient flow structure to characterize the long time behavior of discrete solutions to a fourth order equation. In [START_REF] Disser | On gradient structures for Markov chains and the passage to Wasserstein gradient flows[END_REF], a finite volume scheme is studied in the discrete Wasserstein setting, and a new type of convergence proof is proposed in this context. In both cited papers, the space discretization is regular (i.e. 1-dimensional for the second one, and d-dimensional with a cartesian grid for the first one). We aim here at showing that an extension to non regular space-discretization is not out of reach. In particular, we show that Finite Volume discretization strategies for very general meshes lead to problems that can be interpreted as gradient flows for a discrete Wasserstein-like metric, with a functional that can be seen as an approximation of its continuous counterpart. Let us make it clear, though, that no discrete-tocontinuous convergence result is known for the Wasserstein distance for non regular meshes.

The outline of the paper is as follows. In Section 6.2 we recall the main obtained result on the FP equation and its gradient flow formulation, we define the Wasserstein-like distance of Maas and state his first result in terms of gradient flows using this distance. Then we describe the Gromov-Hausdorff convergence in the special case of the d-dimensional torus and show the convergence of the discrete relative entropy H to its continuous counterpart H. Section 6.3

proposes a Finite Volume discretization of the FP equation in space and the analysis of the Markov chain deduced from this discretization and seen as an ODE in time. We show that this ODE is the gradient flow of the discrete relative entropy H and we finalize the paper with some conclusive remarks and perspectives.

N Ω Figure 6.2: From the Euclidean domain to the associated network

Preliminaries

We describe in this section with some details the constitutive blocks of the diagram presented in Fig. 6.1.

Blocks A-B-C: Fokker Planck equation as a gradient flow, continuous setting.

Let us first recall some basic facts on the Wassertein space of measures and gradient flows therein (we refer to [START_REF] Villani | Optimal transport: old and new[END_REF][START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF][START_REF] Ambrosio | Gradient flows: in metric spaces and in the space of probability measures[END_REF] for a detailed presentation of these considerations). Let Ω be a bounded domain. For any two measures p 0 and p 1 in P(Ω), the (quadratic) Wasserstein distance between them is defined by

W 2 (p 0 , p 1 ) 2 = inf γ∈Π Ω×Ω r ′ -r 2 dγ(r, r ′ ),
where Π is the subset of P(Ω × Ω) for all those γ with marginals p 0 and p 1 , respectively, i.e.

Ω×Ω ϕ(r) dγ(r, r ′ ) = Ω ϕ(r) dp 0 (r) , Ω×Ω ψ(r ′ ) dγ(r, r ′ ) = Ω ψ(r ′ ) dp 0 (r ′ )
for any continuous functions ϕ and ψ.

An alternative formulation has been proposed by Benamou-Brenier [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF], it consists in writing the squared Wasserstein distance as follows (we consider here a convex domain):

W 2 (p 0 , p 1 ) 2 = inf pt,ψt 1 0 Ω |∇ψ t (r)| 2 p t (
∂ t p t + ∇ • (p t u t ) = 0 , u t = -grad H(p t ) for a.e. t,
where the gradient is defined according to Def. 6.2.1.

Let us consider the case where H reads

H(p) = Ω f (r) dp(r) + Ω g(p(r)) dr,
where f and g are regular functions. Then the transport velocity u t can be identified as Proof. It is a straightforward application of the definitions above

u t = -∇f -∇ g ′ (p t ) . ( 6
d dt H( ρ t )| t=0 = x∈V (f (x) + g ′ ( ρ t (x))) d ρ t dt (x) π(x)| t=0 = - x∈V (f (x) + g ′ ( ρ t (x))) ∇ • (Θ( ρ t ) • v t )(x) π(x)| t=0 = -f + g ′ • ρ, ∇ • (Θ( ρ) • ṽ0 ) π = ∇(f + g ′ • ρ), Θ( ρ) • ṽ0 1 = ∇f + ∇g ′ • ρ, ṽ0
ρ which concludes the proof.

Heat flow equation as gradient flow of the discrete entropy.

Note that the heat flow equation

d ρ dt + (I -K) ρ = 0, (6.11)
where K = (K(x, y)) x,y is the Markov matrix, can also be written

d ρ dt (x) -∇ • (∇ ρ)(x) = 0 ∀x ∈ V.
We may now identify the heat flow equation with the gradient flow for the relative entropy. Theorem 6.2.8. The gradient flow in D(V ) (according to Def (6.2.6)) of the discrete relative entropy

H( ρ) = x∈V ρ(x) log( ρ(x)) π(x)
is the heat flow equation (6.11).

Proof. For a detailed proof, we refer the reader to [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF], Theorem 1.2. From Proposition 6.2.7, we have that grad

H( ρ) = ∇(1 + log( ρ)) = ∇(log( ρ))
for g( ρ) = ρ log ρ and f = 0, and the discrete gradient flow equation of H is:

d ρ dt (x) -∇ • (Θ( ρ) • ∇(log( ρ)))(x) = 0 ∀x ∈ V.
Notice that: Θ( ρ) • ∇(log( ρ)) = ∇( ρ), which concludes the proof.

Link B -B (arrow 2): Link between continuous and discrete Wasserstein metrics.

A first result of convergence of the discrete transportation metric was proven in [START_REF] Gigli | Gromov-Hausdorff Convergence of Discrete Transportation Metrics[END_REF] (Theorem 3.15).

We consider the space P(T d ) of all the probability measures on the d-dimensional torus

T d = R d /Z d endowed
) ≡ D(T d n )
. The convergence result is established in the sense of Gromov-Hausdorff that is defined by: Definition 6.2.9. A sequence of compact metric spaces (X n , d n ) is said to converge in the sense of Gromov-Hausdorff to a compact metric space (X, d), if there exists a sequence of maps f n : X → X n which are:

• ϵ n -isometric, i.e., for all x, y ∈ X, In order to strenghen the relation between the discrete setting and the continuous one, we are going to show the convergence of the discrete relative entropy to its continuous counterpart ( C -→ C in the Diagram of Fig. 6.1). We consider a collection of n points V in Ω, and construct a partition (K x ) x of the domain which is relative to V , i.e. each cell K x of the partition contains one point of V (which is x) and:

|d n (f n (x), f n (y)) -d(x, y)| ≤ ϵ n • ϵ n -surjective, i.e., for all x n ∈ X n there exists x ∈ X with d(f n (x), x n ) ≤ ϵ n for some sequence ϵ n → 0.
Ω = x∈V K x , K x ∩ K y = ∅ ∀x ̸ = y ∈ V.
Let h be the diameter of the partition K x , i.e. h = max x∈V diam(K x ). For any probability measure p in P(Ω), we define its discrete counterpart by:

p(x) = Kx p(r) dr, ∀x ∈ V, p ∈ P(V ) ( 6 . 1 2 )
and then we define its discrete density by:

ρ(x) = p(x) π(x) , ∀x ∈ V, ρ ∈ D(V ).
Proposition 6.2.12. Let p, π be two C 1 (Ω) densities with respect to the Lebesgue measure, bounded from below and above, i.e. ∃ m, M > 0 such that 0 < m ≤ p, π ≤ M , and p h , π h be their discrete counterpart defined according to (6.12). We denote by ρ h the discrete density of p h with respect to π h . Then, the discrete relative entropy:

H h ( ρ h ) = x∈V h ρ h (x) log( ρ h (x)) π h (x)
converges to the continuous relative entropy:

H(p) = Ω p(r) log p(r) π(

r) dr

when h → 0, at the first order in h.

Proof. We substract the continuous and the discrete quantities:

H(p) -H( ρ h ) = x∈V Kx p(r) log p(r) π(r) dr -p h (x) log p h (x) π h (x) = x∈V Kx p(r) log p(r) π(r) -log p h (x) π h (x) dr ≤ x∈V Kx p(r)C p(r) π(r) - p h (x) π h (x) dr
where C is a Lipchitz constant for log on [ m M , M m ]. Then, by straightforward computations using the boundedness from below and above of the measures we can bound the difference by C ′ × h where C ′ is a constant depending on m, M and C.

Discretization of the Fokker-Planck equation

We re-write the Fokker-Planck system by replacing ∇Φ by -∇π/π in the first equation, we get:

∂p ∂t -∇ • ∇p -p ∇π π = 0, or equivalently: ∂p ∂t -∇ • (π∇ p π ) = 0 (6.13)
Finite volume discretization. Let V be a collection of points in Ω, and let (K x ) x be the associated Voronoi tesselation. We denote by N the dual network of the space discretization (two vertices are connected whenever the corresponding cells are adjacent). Then we discretize in space the FP equation (in its form (6.13)) by a Finite Volume scheme (see e.g. [START_REF] Eymard | Finite volume methods[END_REF]). By which can be seen as an evolution equation on the network N.

Semi-discretized equation written with probability densities:. An equivalent semi-discretized equation of (6.14) is written with the probability densities ρ with respect to π, i.e. p(x) = Equation (6.16) is not exactly of the heat flow type (6.11), since Q is not of the form K -I, where K would be a stochastic matrix. Yet, as pointed out in [START_REF] Erbar | Gradient flow structures for discrete porous medium equations[END_REF], a connection can be made between the two settings: For a matrix Q as above, we set q x = y∼x Q(x, y) and q max = max x q x .

We then define the matrix K as follows:

K(x, y) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩
Q(x, y) q max , if x ̸ = y q maxq x q max , if x = y Proposition 6.3.1. The matrix K resulting from the space discretization of the FP equation (6.13) as described above is an irreducible and reversible Markov Kernel that admits π as stationary measure.

Proof. The matrix K has the following properties:

(i) K(x, y) = Q(x, y)/q max ≥ 0 for x ̸ = y, K(x, x) = (q maxq x )/q max ≥ 0, and y∈V K(x, y) = y∼x Q(x, y) q max + q maxq x q max = y∼x Q(x, y) q max + 1 -y∼x Q(x, y) q max = 1.

(ii) K(x, y) ̸ = 0 for x ∼ y and the network is strongly connected, we deduce that K is irreducible and then has a unique stationary measure.

(iii) π satisfies the detailed balance equation for all x, y ∈ V : π(x)K(x, y) = π(x) Q(x, y) q max = π(x) q max |Γ xy |θ( π(x), π(y)) |x -y| π(x) = π(y) q max |Γ xy |θ( π(x), π(y)) |x -y| π(y) = π(y) Q(y, x) q max = π(y)K(y, x) so K is reversible, and we have: which proves that π is the unique stationary measure of K.

By definition of K, we have that 1

q max Q = (K -I),
so that the solution to (6.16), that is the space-discretized solution, is the solution to the heat flow equation d dt ρ + (I -K) ρ = 0, up to an affine time renormalization. Now recall that the continuous FP equation is the gradient flow in the Wasserstein sense (see Def(6.2.1)) for the relative entropy (6.7). We have the following discrete counterpart of this property for the Finite Volume discretization scheme (6.16), that is a direct consequence of the previous developments: Proposition 6.3.2. The space discretized scheme (6.16) is a gradient flow for the discrete relative entropy (6.2), up to an affine time renormalization, with respect to the discrete Wasserstein distance W 2 (see Def 6.2.4).

Conclusive remarks, perspectives

We described in this paper how some space discretization Finite Volume schemes, possibly on unstructured meshes, can be proved to be deeply respectfull of the underlying gradient flow structure. Given a PDE that is the Wasserstein gradient flow of some functionnal, the ODE resulting from space discretization can be identified as a gradient flow for a discrete functionnal that is an approximation of the continuous one, in the Wasserstein space of measures defined on the underlying network, the vertices of which are the finite volume cells. This overall consistency with respect to Wasserstein metric, that is expressed by Fig. 6.1, can be used to improve the numerical analysis of a scheme, e.g. by charaterizing its long-time behaviour (as in [START_REF] Maas | Long-time behavior of a finite volume discretization for a fourth order diffusion equation[END_REF] in the case of a cartesian mesh). Note that the approach is currently limited to the semi-discretized scheme. Let us add that the considered scheme treats the advection in a diffusive manner, and as such it is intrinsically of the centered type, so that stability issues can be expected. In particular, an Euler Explicit scheme is likely to lead to unconditionnal unstability. Implicit time-stepping may, in the contrary, provide some stability. Note that Implicit Euler time-stepping applied to (6.16) leads to a problem that is formally very similar to the so-called JKO scheme applied at the discrete level to compute the gradient flow. Implicit schemes are then likely to recover some properties of the JKO one .

Let us finally stress that the diagram of Fig. 6.1 is not fully realized. Indeed, the arrow 2 between blocks B and B ′ , which expresses a link between the Wasserstein distance in a domain, and the discrete Wasserstein distance on the network obtained by space discretization, is not covered by a full theory. The only known convergence results ( [START_REF] Gigli | Gromov-Hausdorff Convergence of Discrete Transportation Metrics[END_REF]) concern cartesian grids, in the case without potential. In the presence of a non-constant potential, the framework that has been presented may appear puzzling, because the discrete Wasserstein distance involves the stationnary measure (non uniform in general), which depends on the potential Φ, whereas its continuous counterpart pertains to the flat domain, and therefore does not depend on Φ.

This apparent paradox is due to the fact that, at the discrete level, the distance W 2 is defined for densities with respect to the stationary measure π. Comparing both distances would amount to consider two probabilties p 0 and p 1 , compute their discrete counterparts p 0 and p 1 , together with π, then ρ 0 = p 0 / π, ρ 1 = p 1 / π, and finally estimate W 2 ( ρ 0 , ρ 1 ), and check that the latter converges to W 2 (p 0 , p 1 ) when the discretization is refined. Although not covered by any theoretical result, and in spite of the fact that W 2 "sees" the measure π, while W 2 does not, such a property can be expected, because π is involved twice in the discretization process : firstly by computation of ρ from p, and then, in a hidden way, through the definition of W 2 .

One can check in very simple situations that both effect tend to compensate each other, i.e.

the dependence of W 2 ( ρ 0 , ρ 1 ) upon π asymptotically vanishes. It can also be seen in the very definition of the distance itself: each time π(x) is involved, it is multiplied by a quantity of the type θ( ρ(x), ρ(y)), where x and y are connected. In the context of Finite Volume schemes, when the discretization is refined, x and y get closer, so that this quantity is asymptotically close to ρ(x), and finally the real dependence is upon p(x), which does no longer depend on the stationnary measure. As for non cartesian meshes, the analogy that we established advocate for a convergence of the discrete Wasserstein metric toward the continuous one, but it remains to be rigorously proven.

Chapter 7

Conclusion and perspectives

Conclusion

We proposed a new microscopic model based on Nash equilibria. Each individual is influenced by some of its neighbors and has a certain desired velocity. The influence relations between individuals are represented by a directed graph: the nodes are the individuals and the directed edges links each person to his influencers. We define the equilibrated velocity field as a solution of a Nash equilibria problem: each individual tries to do his best by approaching his desired velocity, respecting non-overlapping constraints with his influential neighbors. The type of the influence graph determines/constrains the existence and uniqueness of solutions. Two particular cases are considered in this thesis: the case of a complete influence graph (each individual is possibly influenced by all the others), and the case of a directed acyclic influence graph where the relations between individuals are structured in a hierarchical way. For the first case, we prove existence of solutions in Chapter 2 by showing that the solution of the granular model (described in [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF] and recalled in Chapter 1) is a particular solution. Uniqueness is not guaranteed for this case. We describe the set of possible solutions, and show that some Nash equilibria cannot be built using the granular model. The second case, that we call the hierarchical model, is characterized by the existence and uniqueness of solutions that can be computed in a frontal manner as proved in Chapter 3. We also consider the case where the influence graph is based on the cones of vision of individuals: each person is influenced by others he sees. The influence graph based on cones of vision is natively hierarchical in evacuation situations. This property is considered for numerical simulations.

In the case where the influence graph is not complete, some unwanted collisions may occur between individuals not influencing each other. In this case an extra step is performed in the model: the equilibrated velocity field is projected on the set of globally admissible velocity fields. A numerical strategy is proposed to solve the hierarchical model and the latter is compared to the granular model [START_REF] Maury | Handling of contacts in crowd motion simulations[END_REF][START_REF] Maury | A discrete contact model for crowd motion[END_REF] in Chapter 3. The numerical results are confronted with real evacuation experiments and the hierarchical model is shown to be able to produce some crowd effects: the alternation between short and long time lapses, the powerlaw distribution of time lapses, the Faster is Slower effect, the beneficial effect of the presence of an obstacle upon evacuation fluidity and the capacity drop phenomena.

The principles of the hierarchical model are translated to the macroscopic level. We describe the macroscopic model in Chapter 5 and a preliminary study of the difficulties raised by this approach is represented.

Beside crowd motion modeling, we establish a link between some space discretization strategies of the Finite Volume type for the Fokker-Planck equation in general meshes (Voronoï tesselations) and gradient flows on the underlying networks of cells, in the framework of discrete Wasserstein distances on graphs recently proposed in [START_REF] Maury | A time-stepping scheme for inelastic collisions[END_REF].

Perspectives

In this section, we propose some possible perspectives of the work presented in this thesis.

Some of them are under current investigation.

Existence of Nash equilibria in the general case

In Chapters 2 and 3, we proved existence of Nash equilibria in the case where the influence graph is complete or acyclic. In the case of a general influence graph which contains cycles, the existence of Nash equilibria is still under current investigation. Actually, as already mentioned at the end of Chapter 2, the classical theory of existence of Nash equilibria does not apply due to the particular form of the game considered. The cost functions are discontinuous and not finitely valued, and the strategy sets of individuals may be empty, not necessarily compact and do not depend continuously on the strategies of others. Some of these issues may be overcome by making some additional assumptions on the cost functions and the strategy sets (high values of cost functions instead of infinite ones, prescribed maximum module of velocities,...), but this is still not sufficient to apply known existence theorems. For example, continuity of cost functions is required for the first existence theorems in infinite games [START_REF] Debreu | A social equilibrium existence theorem[END_REF][START_REF] Irving | A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points[END_REF][START_REF] Ky | Fixed-point and minimax theorems in locally convex topological linear spaces[END_REF], some forms of weak continuity of the cost functions are introduced in [START_REF] Michael R Baye | Characterizations of the existence of equilibria in games with discontinuous and non-quasiconcave payoffs[END_REF][START_REF] Philip | On the existence of pure and mixed strategy Nash equilibria in discontinuous games[END_REF][START_REF] Bagh | Reciprocal upper semicontinuity and better reply secure games: a comment[END_REF][START_REF] Tian | Existence of equilibria in games with arbitrary strategy spaces and preferences: a full characterization[END_REF][START_REF] Barelli | On the existence of Nash equilibria in discontinuous and qualitative games[END_REF][START_REF] Nessah | The existence of equilibria in discontinuous and nonconvex games[END_REF] but they are not verified by the functions we consider, and semi-continuous dependence of admissible strategies on the strategies of others is required in [START_REF] Kenneth | Existence of an equilibrium for a competitive economy[END_REF].

Even in the case where a Nash equilibrium exists, this solution is in general not unique.

In the case of a complete influence graph, we can attribute a weight for each individual (depending on his dimension, aggression level,...) and consider the weighted granular model whose solution is a Nash equilibrium (see Proposition 2.3.1 in Chapter 2). In the general case, the problem of specifying rules to select one of the infinitely many possibilities, in such a way that the selection remains measurable in time, raises unresolved issues in terms of mathematics and modeling. Let us make it straight that the underlying problem does not call for some kind of entropy-like condition, but rather assumptions on the behavior of individuals facing a conflicting situation. In the case of a direct conflict between two individuals, it is possible to resolve the problem by attributing different weights to individuals as for the weighted granular model or simply by making the interaction between them completely asymmetric (turning the undirected edge of the influence graph to a directed one). When the topology of the graph becomes more complicated, this possibility is ruled out due to the complexity of the interactions.

(resp. densities). For the case of the macroscopic granular model, the density of the crowd is transported with the desired velocity field, and then the density is projected on the set of admissible densities (remaining below a maximum value) according to the quadratic Wasserstein distance. We propose to study a similar catching-up scheme where the prediction step is performed in the same way as for the macroscopic granular model, but the projection of the correction step is changed. We suggest to project the density of the crowd on the set of densities remaining below a maximum value, according to a modified Wasserstein distance where the quadratic cost is finite if the displacement yx belongs to the opposite of the cones of vision. This approach fits in the framework of constrained transport introduced recently by Jimenez and Santambrogio [START_REF] Jimenez | Optimal transportation for a quadratic cost with convex constraints and applications[END_REF] where the authors prove existence of an optimal transport map between two given probability measures, for a quadratic cost with convex constraints on the transport map. In [START_REF] Jimenez | Optimal transportation for a quadratic cost with convex constraints and applications[END_REF], the displacement is constrained to belong to a fixed convex set. An extension of this work to the case where the convex set depends on the space variable is necessary in order to study the suggested catching-up algorithm for the macroscopic hierarchical model.

performed. In the first one, participants are just instructed to "head for the door" (placid walkers), while for the second one, they are told to "walk purposefully, but without running, pushing or hitting others" (purposeful walkers). Placid walkers are quiet calm and relaxed, whereas purposeful walkers are somewhat precipitous but not to the point to be in competition

  d'unicité de champs de vitesses équilibrées dans deux situations différentes aux Chapitres 2 et 3. Particulièrement, nous montrons l'existence de solution dans le cas où le graphe d'influence est complet au deuxième chapitre, sans unicité de solutions en général, et décrivons l'ensemble de solutions possibles. Nous considèrons le cas d'un graphe d'influence dirigé acyclique au troisième chapitre où nous montrons l'existence et l'unicité de solution au problème. Ce cas particulier du modèle est appelé le modèle hiérarchique en référence à la structure hiérarchique du graphe d'influence. Nous terminons le troisième chapitre par la description d'un schéma numérique permettant d'approcher l'unique solution du modèle hiérarchique. Le Chapitre 4 est dédié à la confrontation des résultats numériques du modèle hiérarchique avec des expériences réelles d'évacuation. Le modèle se compare favorablement à ces expériences et nous montrons sa capacité à reproduire certains effets observés en réalité. Nous introduisons au cinquième chapitre une première tentative pour écrire une version macroscopique du modèle hiérarchique. Nous décrivons le modèle, présentons des résultats préliminaires en une dimension et décrivons les difficultés posées par la généralisation des résultats à la dimension deux.

Figure 1 :

 1 Figure 1: Notation

Figure 2 :Proposotion 2 .10 page 43 .

 2243 Figure 2: Exemple d'un graphe d'influence complet

  3.2 page 44 que l'ensemble des équilibres de Nash solutions du Problème (1)(2) est un ensemble fermé. Si nous notons par Λ m l'ensemble de CONTENTS tous les équilibres de Nash obtenus comme solutions du Problème(4), où M est une matrice diagonale associée à des masses m 1 , . . . , m N > 0, alors nous avons Λ m ⊂ Λ. La proposition précédente permet de conclure l'inclusion suivante: Λ m ⊂ Λ. Une question naturelle se pose donc: est-ce que Λ m = Λ ? La réponse est oui en dimension un comme le montre la Proposition 2.3.3 page 45. Par contre, nous montrons à la Proposition 2.3.4 page 46 que

Figure 3 :Proposition 3 . 2 .2 page 54 .

 33254 Figure 3: Exemple d'un graphe d'influence dirigé acyclique

Figure 4 :

 4 Figure 4: Comparaison entre le modèle granulaire et le modèle hiérarchique.

Figure 4 .

 4 1 page 67) et d'autres non périodiques. Pour chaque simulation, nous extrayons les instants de sortie des individus et mémorisons la longueur des intervalles de temps entre deux sorties consécutives. Nous montrons la capacité du modèle à reproduire certains effets de mouvement de foule observés en réalité: • Alternation entre intervalles de temps entre deux sorties court et long: Comme proposé dans [101], nous calculons la corrélation entre les temps écoulés entre deux sorties et trouvons une corrélation négative pour les temps entre deux sorties consécutives. Cet effet a été observé pour les expériences décrites dans [101] et le modèle hiérarchique est prouvé apte à reproduire cet effet avec une valeur de corrélation assez proche de celle des expériences (voir Figure 4.5 page 69).

Figure 4 .

 4 Figure 4.7 page 70). • Faster is Slower: Nous comparons le modèle hiérarchique au modèle granulaire décrit dans [90, 89]. Nous prouvons à la fin du Chapitre 3 que les vitesses équilibrées du modèle hiérarchique sont plus petites que les vitesses souhaitées dans la direction souhaitée des individus, ce qui veut dire que les individus ont une tendance à aller moins vite pour le modèle hiérarchique comparé au modèle granulaire. Les simulations numériques montrent que les individus vont en fait plus vite pour le modèle hiérarchique comparé au modèle granulaire (flux moyen plus important pour le modèle hiérarchique), ce qui prouve la capacité du modèle à reproduire l'effet Faster is Slower, ou de façon équivalente Slower is Faster (voir Tableau 4.1 page 76).

Figure 1 . 1 :

 11 Figure 1.1: Example of function φ for the Follow-the-Leader model with d s = 1m and d m = 0.5m

Figure 1 . 2 :

 12 Figure 1.2: Example of space discretization for the cellular automata model

Figure 1 . 3 :

 13 Figure 1.3: Example of pedestrians passing through a narrow corridor: on the left, a situation that supports the step wise increasing of the flow rate with the density increase; and on the right, a situation that supports the continuous dependence of the flow rate on the density. Figure from http://physicsworld.com

Figure 1 . 4 :

 14 Figure 1.4: Velocity/Flow-Density relation according to some researchers[START_REF] Daamen | Modelling passenger flows in public transport facilities[END_REF][START_REF] Mark | Pedestrian speed-flow-density relationships[END_REF][START_REF] Weidmann | Transporttechnik der Fussgänger: Transporttechnische Eigenschaften des Fussgängerverkehrs (Literaturauswertung)[END_REF]

Figure 1 . 5 :

 15 Figure 1.5: Zipper effect in a corridor with different width values[START_REF] Schadschneider | Evacuation dynamics: Empirical results, modeling and applications[END_REF]

Figure 1 . 6 :

 16 Figure 1.6: Pedestrian inflow and outflow patterns observed at a width restriction in a London underground station where capacity drop occurs during a period of decrease in inflow (flow expressed in pedestrians per 5 second period). Figure taken from [22].

  cle without overtaking each other. The authors considered different number of pedestrians in the circle and many trials were performed. It has been observed that the speed of pedestrians fluctuate periodically during a trial. In Figure 1.7, the authors plotted the evolution of the pedestrians' positions in time colored by their speed. Stop-and-go waves are easily observed in the plot.

Figure 1 . 7 :Figure 1 . 8 :

 1718 Figure 1.7: Evolution of the positions of individuals in time colored by the speed (figure from [81])

Figure 2 . 1 :

 21 Figure 2.1: Example of influence graph on individuals. The edges of the graph are represented by blue dotted vectors and desired velocities in plain black vectors.

I 1 =

 1 {2} and I 2 = {1}. In this case, there exists a continuum of Nash equilibria: any couple (u, u) such that u ∈ [-1, 1] is a solution. It corresponds to the situation of two faceto-face individuals heading to opposite directions. This conflict sometimes leads to phase of hesitation, possibly with slight back and forth moves. This example is the continuous counterpart of Example 1 in Section 2.1.

2 Figure 2 . 5 : Example 1 Example 2 :

 22512 Figure 2.5: Example 1

2 Figure 2 . 6 : Example 2 Example 3 :

 22623 Figure 2.6: Example 2

Figure 2 . 7 :

 27 Figure 2.7: Example 3

. 4 )

 4 Let us give now some considerations on modeling behavior. The granular model considers individuals as active and nonsocial: each individual tends to behave as if he were alone, and interactions do not correspond to individual decision, they are rather of mechanical nature (actual contact between grains). The Nash equilibrium model (2.1)(2.2) considers individuals as thinking entities able to perceive their close neighborhood (in terms of positions and velocities), and to make decisions to optimize their behavior according to an instantaneous objective (desired velocity) within a set of possibilities conditionned by the neighbors' behavior. The game theoretic aspect comes from the fact that the constrained set for an individual depends on the strategy of other players.

Figure 2 . 8 :Figure 2 . 9 :

 2829 Figure 2.8: Example of complete influence graph in dimension one

Proposition 2 . 3 . 1 .

 231 We assume that the influence graph is complete, i.e. each individual can be influenced by all the others. We consider a collection of strictly positive masses m 1 , . . . , m N , and denote by M ∈ M dN the associated diagonal matrix M = (m 1 , m 1 , . . . , m N , m N ) (or simply M = (m 1 , . . . , m N ) in the one-dimensional setting). Then, the problem:

Proposition 2 . 3 . 4 .

 234 In the two dimensional setting, the inclusion Λ m ⊂ Λ is strict.Proof. Consider the configuration of individuals represented in Figure(2.10) where the desired velocities of individuals are: U 1 = (1, 0), U 2 = (0, -1), U 3 = (-1, 0) and U 4 = (0, 1).

Figure 2 . 10 :

 210 Figure 2.10: Four individuals forming a cycle

  interactions between individuals: two individuals cannot influence each other neither directly nor indirectly, i.e. no cycles between individuals can occur. Hierarchic influence relations based on the cones of vision are appropriate for evacuation scenarios where the influence of an agent becomes increasingly significant when he get closer to the door. Individuals in front of the exit door are the most influential ones and the influence of their behavior propagates in an upstream way throughout the crowd. For example, consider a single file of pedestrians in a narrow corridor and suppose they all want to go to the right. Since we consider civilized agents, each one of them respects the individual in front of him and adapt his desired velocity according to his motion. If the leader of the crowd decides to stop suddenly, all pedestrians behind him cannot do better than stopping too.The actual velocities of individuals are computed in two steps. First, a decision step where each individual tries to approach his desired velocity taking into consideration the velocities of his influential neighbors. This step models the tendency of individuals to avoid contact with the others that influence them. Second, a correction step to avoid collisions that have not been anticipated by individuals in the first step. In terms of modeling, this would correspond to the situation of two persons walking without seeing each other (see Figure3.1 for an example). As soon as a physical contact occurs between them, the interaction no longer relies on a decision process: they start interacting in a mechanical (and thus symmetric) way.

2 Figure 3 . 1 :

 231 Figure 3.1: Example of situation where two individuals do not see each other and are close to overlap.

  the decided velocities of his influential neighbors. Browsing the individuals from the largest index to the smallest one allows us to compute the equilibrated velocities of individuals in a frontal manner through the minimization problems (3.1)(3.2). The existence and uniqueness of solutions to Problem (3.1)(3.2) are proved in Theorem 3.2.2.

Figure 3 . 3 :

 33 Figure 3.3: Example of directed acyclic graph in dimension one

1

 1 have already been determined. Hence, Problem (3.1)(3.2) has a unique solution.

Figure 3 . 5 :

 35 Figure 3.5: An example of cone of vision and its corresponding influence graph in dimension two.

. 10 )Figure 3 . 6 :

 1036 Figure 3.6: Acyclicity condition (3.10)

Figure 3 . 7 :

 37 Figure 3.7: Notation used in the proof of Theorem 3.2.4

  model based on the cones of vision without obstacles, and the hierarchical model based on the cones of vision with an obstacle placed upstream the exit. For each case, we run two types of numerical simulations. The first type corresponds to periodic evacuation simulations (evacuated individuals are re-injected at a random position at the back of the room) for the same initial configuration of N = 80 individuals performed during 3000s. The second type corresponds to non-periodic evacuation simulations (the simulation gets to its end when all individuals are out of the domain) for the same initial configuration of N = 150 individuals. A snapshot of a periodic evacuation simulation is represented in Figure (4.1) and another one for non-periodic evacuation is displayed in Figure (4.2). We extract the time lapses between consecutive egresses for all simulations and base our analysis on it. These simulations are used to validate the capability of the hierarchical model to reproduce the following crowd phenomena: • The alternation between short and long time lapses for the hierarchical model, a quantitative comparison is done with the experiments, • Power-law distribution of time lapses for the hierarchical model and the granular one, with a quantitative comparison between the exponent value for the hierarchical model with the experiments, • The Faster is Slower effect, or equivalently the Slower is Faster effect, by showing that when pedestrians decide to go slower they actually go globally faster, • The effect of the presence of an obstacle on the outward flow rate for the hierarchical model, several obstacle shapes are tested, • The drop in the door capacity when the number of individual involved in the evacuation simulation increases. For the capacity drop phenomenon, we run periodic evacuation simulations for N = 15, 20, 25, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150 and 160 individuals, and we follow the evolution of the flow rate in terms of the number of pedestrians in the evacuation simulation.

Figure 4 . 1 :

 41 Figure 4.1: Snapshot of a periodic evacuation simulation for the hierarchical model.

Figure 4 . 2 :

 42 Figure 4.2: Snapshot of a non-periodic evacuation simulation for the hierarchical model.

  3)(4.4)(4.5)(4.6) the correlation functions for respectively: the periodic evacuation experiment by Nicolas et al. [101] (reproduced), the non-periodic experiment with low competitiveness by Garcimartín et al. [49], and the numerical simulation of the hierarchical model and the granular model with periodic boundary condition. The first three plots show a negative dip for k = 1 which means that statistically anti-correlation exists between successive time lapses, which asserts the effect for the real experiments, and the ability of the hierarchical model to produce it. Moreover, the value of the correlation function for k = 1 is -0.233 ± 0.06 (95% confidence level, see Appendix B) for the numerical simulation which is consistent with the ones obtained for the low competitiveness experiment by Garcimartín et al. (0.23) and the experiment by Nicolas at al. (0.29). The effect is not apparent for the numerical simulations of the granular model. The correlation between time lapses is almost zero for all k = 1, . . . , 7 which means that no correlation exists for the case of the granular model.

Figure 4 . 3 :

 43 Figure 4.3: Correlation between time lapses for a periodic evacuation experiment by Nicolas et al. [101].

Figure 4 . 4 :

 44 Figure 4.4: Correlation between time lapses for an evacuation experiment by Garcimartín et al[START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF] with low competitiveness.

Figure 4 . 5 :

 45 Figure 4.5: Correlation between time lapses for a periodic evacuation simulation for the hierarchical model.

Figure 4 . 6 :

 46 Figure 4.6: Correlation between time lapses for a periodic evacuation simulation for the granular model. 69

Figure 4 . 7 :

 47 Figure 4.7: CCDF for the numerical results of the granular model and the hierarchical model.

Figure 4 . 8 :

 48 Figure 4.8: CCDF for the controlled experiments by Garcimartín et al. [49].

2 . 5 ,

 25 Chapter 3, that the decision step of the hierarchical model reduces the desired velocity of an individual in his desired direction of motion. If an individual sees his neighbor, he shall respect him and chose an equilibrated velocity that do not violate the non-overlapping constraint with him. Now when the anticipating trajectories of two individuals intersects (usually the case in evacuation situations) and they do not influence each other, the collision is handled by the granular projection (projection of the equilibrated velocity field on the set of globally admissible velocity fields). So the decision step reduces the competitiveness level compared to the granular model (direct projection of the desired velocity field on the set of globally admissible velocity fields) where the competitiveness between individuals can reach high levels due to the mechanical nature of the interactions.

1 :

 1 the granular model, the hierarchical model without obstacles and the hierarchical model with an obstacle upstream the exit. The comparison is based on a study of the distribution of time lapses and the time dependent flow rate for periodic simulations and the evacuation time for non-periodic simulations. The time dependent flow rate is a moving average of the flow through the exit door, computed over a time window δ t . It is computed as follows:

Figure 4 . 9 :

 49 Figure 4.9: Distribution of time lapses for the granular model.

Figure 4 . 10 :

 410 Figure 4.10: Distribution of time lapses for the hierarchical model without obstacles.

Figure 4 . 11 :

 411 Figure 4.11: Distribution of time lapses for the hierarchical model with a reversed V obstacle upstream the exit.

Figure 4 . 12 :

 412 Figure 4.12: Time dependent flow rate for the granular model for δ t = 1s (thin lines) and δ t = 7s (thick lines).

Figure 4 . 13 :

 413 Figure 4.13: Time dependent flow rate for the hierarchical model without obstacles for δ t = 1s (thin lines) and δ t = 7s (thick lines).

Figure 4 . 14 :

 414 Figure 4.14: Time dependent flow rate for the hierarchical model with a reversed V obstacle upstream the exit for δ t = 1s (thin lines) and δ t = 7s (thick lines).

Figure 4 . 15 :

 415 Figure 4.15: Cumulated number of evacuated pedestrians in time for evacuation simulations for the granular model and the hierarchical model.

1 .

 1 The mean flow is computed as the inverse of the time lapses mean and the errors represent a 95% confidence interval (see Appendix B for details about the computation of the confidence intervals). The time lapses mean is smaller for the hierarchical model compared with the granular one, and the flow undergoes an increase of 31.4% which highlights the fact that individuals go globally faster for the hierarchical model. The time dependent flow rates defined by (4.1) for δ t = 1s and δ t = 7s are displayed in Figures(4.

  [START_REF] Berthelin | A model for the formation and evolution of traffic jams[END_REF]) and (4.13) for 130s of the periodic evacuation simulations. The flow rate of the granular model is subject to high fluctuations compared

  (4.16) and the resulting average flows are shown in

Figure 4 . 16 :

 416 Figure 4.16: Periodic evacuation simulation for the hierarchical model with different obstacle shapes.

Figure 4 . 17 :

 417 Figure 4.17: Evacuation of 150 pedestrians: Granular model (left), Hierarchical model (middle), and Hierarchical model with a reversed V obstacle (right).

  of the hierarchical model to reproduce this effect, we run periodic evacuation simulations for different number of individuals and follow the evolution of the average flow through the exit.The result is displayed in Figure4.18.

Figure 4 . 18 : 5 Towards a macroscopic counterpart of the hierarchical model Contents 5 . 1 83 5. 2 84 5. 3 87 5. 3 . 2 89 5. 4 92 5. 4 . 1

 41855183284387328949241 Figure 4.18: Evolution of the outward flow rate in terms of number of pedestrians in the simulation.

Figure 5 . 1 :

 51 Figure 5.1: Example of evacuation simulation computed according to the macroscopic model in [88, 91] (figure from [111])

Figure 5 . 2 :

 52 Figure 5.2: Example of evacuation simulation computed according to the granular model and its macroscopic counterpart (figure from [111])

Figure 5 . 3 :

 53 Figure 5.3: Example of desired velocity, its associated cone of vision and the outward normal vectors to the cone.

Proposition 5 . 3 . 1 .

 531 Problem (5.10) has a unique solution.

e. Proposition 5 . 3 . 2 .

 532 Let Ω =]0, 1[ be a domain where the density ρ is saturated. Then, the unique minimizer of Problem(5.11) is: u(x) = min y∈[x,1] U (y), for almost every x ∈ Ω. Proof. Let ū(x) = min y∈[x,1]U (y). Suppose by contradiction that there exists a non-zero measure set A ⊂ Ω where the minimizer u is different from ū a.e. on A, and u = ū a.e. on A c . Then u(x) is necessarily greater or equal to ū(x) for a.e. x ∈ A, since otherwise one can do better. If ū(x) = U (x), then u(x) is necessarily equal to ū(x). Now if ū(x) = min y∈[x,1] U (y) < U(x), then min y∈[x,1]

  the case of Problem(5.4), some individuals have actual velocities greater than their desired one, they are actually pushed by individuals behind them who want to go faster, while for the actual velocity according to Problem(5.11), all individuals do their best by having the closer possible velocity to their desired one, respecting individuals in front of them.

Figure 5 . 4 :

 54 Figure 5.4: Desired velocity and its corresponding actual velocity in two cases: the granular model (left) and hierarchical model (right).

(5. 14 )

 14 According to Lax-Milgram Theorem, the variational problem (5.14) has a unique solutionξ k+1 in H 1 ρ (Ω).At each time step, we compute ξ k+1 the representative of B 1 u k+1 in H 1 ρ (Ω) by solving the variational problem (5.14) and then we update the Lagrange multipliers p k and λ k . The algorithm then reads:

  ) and (5.15) respectively, implemented with Freefem++. The result is displayed in Figure 5.5 where we represent: on top, the desired velocity field, on the middle the actual velocity fields for Problem (5.4) (left) and Problem (5.10) (right), and on bottom the module of the actual velocity field for Problem (5.4) (left) and Problem (5.10) (right).

Figure 5 . 5 :

 55 Figure 5.5: The desired velocity field (top), the actual velocity field and its norm according to the hierarchical model (left), and the granular model (right).

Proposition 5 . 4 . 2 .

 542 For every ϵ > 0, Problem (5.20) has a unique solution that we denote by u ϵ .Proof. The functional J ϵ is strictly convex and l.s.c., and the set C(ρ) is closed and convex, thus Problem (5.20) has a unique solution.

  write: u(1 -) = lim x→1 - u(x) and U (1 -) = lim x→1 - U (x). By contradiction, suppose that u(1 -) ̸ = U (1 -):

Proposition 5 . 4 . 5 .

 545 The sequence of minimizers (u ϵ ) ϵ converges to u defined by: u(x) = min y∈[x,1] U (y). Proof. Let ū(x) = min y∈[x,1]U (y) and suppose that u ̸ = ū, i.e. there exits a non-zero measure set A ⊂ Ω such that u(x) ̸ = ū(x) for a.e. x ∈ A. Since ū is the unique minimizer of Problem (5.11), we have: u(x) ≤ ū(x) ≤ U (x) for a.e. x ∈ Ω and u(x) < ū(x) ≤ U (x) for a.e. x ∈ A, which implies that |ū(x) -U (x)| 2 < |u(x) -U (x)| 2 for a.e. x ∈ A. Since u ϵ converges pointwise to u, then there exist ϵ 0 > 0 such that ∀ϵ ≤ ϵ 0 we have: |ū(x) -U (x)| 2 < |u ϵ (x) -U (x)| 2 for a.e.

Figure 6 . 1 :

 61 Figure 6.1: Continuous setting versus discrete setting

. 5 )

 5 Now consider the Fokker-Planck equation on a domain Ω: entropy functional: H(p) = Ω p(r) log p(r) π(r) dr = -Ω log(π(r)) dp(r) + Ω p(r) log(p(r)) dr. (6.7)

Theorem 6 . 2 . 10 .Remark 6 . 2 . 11 .

 62106211 Now we are ready to state the convergence theorem of the discrete metrics W 2,n : The metric spaces (P(T d n ), W 2,n ) converge to (P(T d ), W 2 ) in the sense of Gromov-Hausdorff as n → ∞. An informal convergence result can be done for a general stationary measure by discretizing the continuous FP equation with the scheme described in Section 6.3 and writing the corresponding discrete distance which looks almost like a discretization of the continuous Wasserstein distance.Link C -C (arrow 3): Quadrature for the entropy functionnal.

  |x -y| π(x) θ( π(x), π(y)) ρ(y)-y∼x |Γ xy | |x -y| π(x) θ( π(x), π(y)) ρ(x). ⎪ ⎪ ⎪ ⎪ ⎩ |Γ xy |θ( π(x), π(y)) |x -y| π(x) , if x ∼ y -y∼x |Γ xy |θ( π(x), π(y)) |x -y| π(x) , if x = y 0 o t h e r w i s eon the network N.

  y∈V π(y)K(y, x) = y∈V π(x)K(x, y) = π(x)

  to exit the fastest possible way. The experiments are performed imposing "periodic boundary conditions" which means that evacuated pedestrians are re-injected in the room again by following one of two possible circuits (sketched in Figure A.2). A study of the correlations between time lapses is done in this paper for all the performed experiments, as well as an analysis about their distribution, the dependence of the flow rate on the pedestrian density and the dynamics in the exit zone. We refer the reader to[START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF][START_REF] Garcimartín | Flow of pedestrians through narrow doors with different competitiveness[END_REF][START_REF] Nicolas | Pedestrian flows through a narrow doorway: Effect of individual behaviours on the global flow and microscopic dynamics[END_REF] for more details about the procedures used to carry out the evacuation experiments.

Figure A. 2 :A. 2

 22 Figure A.2: A sketch of the experimental geometry (left) and a snapshot of the evacuation experiment (right) by Nicolas et al. [101]

Figure A. 3 :

 3 Figure A.3: Example of influence graphs based on the cones of vision taken from a real controlled experiment. The heads of the pedestrians are represented by the blue points and their velocities are represented by the blue vectors. The influence graph based on the cones of vision is drawn in black.

Contents 1.1 Existing models . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.2 Characteristics of pedestrians . . . . . . . . . . . . . . . . . 24 1.3 Crowd motion effects . . . . . . . . . . . . . . . . . . . . . . 27

Table 2

 2

	.1 shows the satisfaction of each player according
	A	B
	Figure 2.2: Example of configuration of two players on a grid

Table 4 .

 4 1: Different evacuation situations with their respective mean of time lapses and flow rate.

		Time lapses (mean)	Flow rate
	Granular Hierarchical Hierarchical with obstacle	0.41 ± 0.02 s 0.31 ± 0.004 s 0.28 ± 0.002 s	2.42 ± 0.1 pers/s 3.18 ± 0.04 pers/s 3.6 ± 0.027 pers/s

Table 4 .

 4 Table (4.2). 2: Different obstacle shapes with their respective flow rates and confidence intervals.

	Obstacle shape Time lapses (mean)	Flow rate
	No obstacle One pillar Two pillars Triangle Reversed V	0.31 ± 0.004 s 0.3 ± 0.003 s 0.29 ± 0.003 s 0.29 ± 0.003 s 0.28 ± 0.002 s	3.18 ± 0.04 pers/s 3.26 ± 0.032 pers/s 3.44 ± 0.032 pers/s 3.45 ± 0.032 pers/s 3.6 ± 0.027 pers/s

  2 where L 2 + (Ω) is the set of L 2 functions that are nonnegative a.e. in Ω. Problem (5.10) can be formulated in a saddle point manner, as stated by the following proposition.

	Proposition 5.3.3. The minimization problem (5.10) is equivalent to the twofold saddle point
	formulation: there exists nonnegative Lagrange multipliers (p, λ) ∈ H 1 ρ (Ω)×(L 2 + (Ω)) 2 such that

  Chapter 2, Proposition 2.3.1, that the solution of Problem(5.19) is a particular solution of the Nash equilibrium model described in the same chapter. Passing to the limit, the solution of Problem(5.19) is also a Nash equilibrium. Moreover, if no couples of neighboring individuals have the same distance to the exit door, then the limit solution is the unique solution of the hierarchical model where each individual is influenced by all the others that are closer than him to the exit door.

  with the L 2 -Wasserstein metric and the d-dimensional periodic lattice T d n = (Z/nZ) d and endow the space of probability densities D(T d n ) with the renormalised discrete transportation metric W 2,n = W 2 /n √ 2d where the Markov kernel K is the one of a simple random walk (uniform transition probabilities) and whose stationary measure δ is the uniform measure on T d n . In this special case of δ, we can identify probability measures on T d n with their probability densities with respect to δ. So we consider that P(T d n

↔

[START_REF] Ambrosio | Gradient flows: in metric spaces and in the space of probability measures[END_REF], and 4 ↔ 1, we obtain that m 2 /m 3 → +∞, m 3 /m 4 → +∞ and m 4 /m 1 → +∞. This is impossible since, by cyclicity, the product of these four ratios is 1.

Individuals go slower in their desired direction of motion for the hierarchical model based on cones of vision compared with the granular one where the desired velocity is directly projected on the set of globally admissible velocity fields.

According to Proposition 3.10, a condition on the angle of vision and the desired velocity should be satisfied to ensure the acyclicity of the influence graph. One can prove that it is sufficient to have an angle of vision equal to π/3.

We start with 15 individuals evacuating periodically in the domain, the flow rate in this case is 1.75 ± 0.02 pers/s. It then increases to attain its maximum 3.56 ± 0.02 pers/s for 40 pedestrians, before decreasing moderately to attain a local minimum of 3.18 ± 0.04 for 80 pedestrians. For 90 pedestrians, the flow rate attains a local maximum of 3.29 ± 0.02 pers/s, then decreases slightly to achieve a more or less stable flow rate afterwards.

Remerciements

Acknowledgement

The authors would like to thank F. Santambrogio for interesting discussions and suggestions.

Both authors are partially supported by ANR Project Isotace (ANR-12-MONU-0013).

We propose to illustrate the difference between the hierarchical model based on cones of vision and the granular model by an example. We obtain from (6.5)

which identifies the FP equation (6.6) as a gradient flow in the Wasserstein sense for the relative entropy functional (6.7). We refer again to [START_REF] Ambrosio | Gradient flows: in metric spaces and in the space of probability measures[END_REF][START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF] for a thorough presentation of these facts.

Blocks à -B -C: Discrete setting. Let V be a finite set. Definition 6.2.3. We say that (K(x, y)) x,y∈V is an irreducible and reversible Markov kernel on V × V if K satisfies:

Let (K(x, y)) x,y∈V be as in the definition. We denote by π the unique stationary measure of K, such that

We define the associated set of probability densities on V by

Following [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF], we define the discrete gradient, the discrete divergence and the two scalar products with respect to a fixed ρ ∈ D(V ) and π resp., as follows:

• Discrete gradient: For a function ψ : V → R, we define its discrete gradient ∇ ψ :

• Discrete divergence: For a discrete field u : V × V → R, we define its discrete divergence

Note that for an anti-symmetric field u, i.e. u(x, y) =u(y, x), the discrete divergence reads:

• Scalar product with respect to π: For ψ, φ : V → R, we define their scalar product with respect to π by

• Scalar product with respect to ρ: For u, v : V × V → R, we define their scalar product with respect to ρ by

where θ(•, •) is defined by (6.9), and we denote by ∥ u ∥ ρ the associated norm:

Note that the latter is a discrete counterpart of the norm of a velocity field in L 2 p , with p = ρπ.

We denote by ⟨., .⟩ 1 the scalar product with respect to the density ρ = 1 defined by: ρ(x) = 1, ∀x ∈ V . We can easily check that the integration by parts formula holds in the following sense:

The definition of the discrete transportation metric is inspired by the Benamou-Brenier formulation, it translates Eq. ( 6.4) at the discrete level. It is defined as (see [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF][START_REF] Chow | Fokker-Planck equations for a free energy functional or Markov process on a graph[END_REF][START_REF] Mielke | A gradient structure for reaction-diffusion systems and for energy-drift-diffusion systems[END_REF]): Definition 6.2.4. For ρ 0 , ρ 1 ∈ D(V ) we set:

where the infimum runs over all piecewise

where:

is the logarithmic mean of α and β.

Using the definitions of the discrete gradient and the discrete divergence, W 2 can also be formulated as follows (see [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF], Lemma 3.5):

where the infimum runs over all piecewise

where

) and • denotes the entrywise product of two matrices.

The Wasserstein gradient of a functional may now be defined following [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF], Prop. 4.2. Definition 6.2.5. Let H : D(V ) → R be a functional. We shall say that H admits a gradient w ∈ R V ×V at ρ ∈ D(V ), and then write

if, for any measure path t → ρ t on D(V ) defined in a neighborhood of 0, with

After computing the gradient of a functional H, we can write its gradient flow equation in D(V ). Definition 6.2.6. Let H : D(V ) → R be a functional and grad H be its gradient according to Def (6.2.5). We define the discrete gradient flow equation of H by:

Like in the continuous setting, the gradient (in the previous sense) of a certain class of functionals can be computed explicitly. Proposition 6.2.7. Let H be a generalized entropy functional :

where f, g are differentiable functions, f, g

Evolution problem of the hierarchical model

In Chapter 3, we study the well posedness of the instantaneous hierarchical model and prove existence and uniqueness of solutions, which makes it possible to talk about an evolution problem for this case.

Even if the evolution problem seems to be simple, its theoretical study reveals some difficulties. Actually the Cauchy-Lipschitz Theorem does not apply and the problem requires more advanced tools to be solved. In [START_REF] Venel | Modélisation mathématique et numérique des mouvements de foule[END_REF], a theoretical study of the granular model is done and the evolution problem is proved to be well posed, thanks to the theory of maximal monotone operators and sweeping processes. A naive thought to prove the well posedness of the hierarchical model would be to apply the result obtained for the granular model, considering the equilibrated velocity field as a new desired velocity field. However, the result obtained in [START_REF] Venel | Modélisation mathématique et numérique des mouvements de foule[END_REF] requires a desired velocity field that is Lipschitz and bounded, which is not the case for the equilibrated velocity field (not continuous, thus not Lipschitz). Also, remark that the evolution problem of the hierarchical model is outside the scope of maximal monotone operators theory.

For the case of a cluster of individuals walking in the same direction in dimension one, the sweeping process theory introduced in [START_REF] Jacques | Evolution problem associated with a moving convex set in a Hilbert space[END_REF] can be used to prove the well posedness of the problem. Actually, in this case the leader of the crowd walks at his desired velocity for all times, and the one that succeeds him adapts his velocity to avoid overlapping: if the two individuals are in contact, the one behind will have an actual velocity equal to the minimum between his desired one and the desired velocity of the leader, and if not, he walks at his desired velocity. The problem can then be formulated as an hierarchical succession of sweeping processes and hence proved to be well posed.

The situation becomes more complicated in the two dimensional setting. The structure of the influence graph between individuals changes over time at a frequency that is hard to anticipate. This calls for a deeper investigation of the problem in order to establish wellposedness of the evolution problem under general assumptions.

Macroscopic model

In the continuity of the work done in Chapter 5, one can tackle the question of well posedness of the evolution problem associated to the macroscopic counterpart of the hierarchical model.

The classical theory for transport equation does not apply because of the lack of regularity of the actual velocity field (in general just L 2 ), which prompts a search for other tools to study the problem.

A possible way to answer the question of well posedness of the macroscopic evolution problem is by studying a catching-up algorithm. This approach is introduced by Moreau [START_REF] Jacques | Evolution problem associated with a moving convex set in a Hilbert space[END_REF] and is used in [START_REF] Venel | Modélisation mathématique et numérique des mouvements de foule[END_REF][START_REF] Maury | Handling congestion in crowd motion modeling[END_REF] to prove the well posedness of the granular model and its macroscopic counterpart. The catching-up algorithm is based on two steps: a prediction step consisting in transporting the crowd with its desired velocity, and a correction step consisting in projecting the new configuration (resp. density) of the crowd on the set of admissible configurations Appendix A

Experimental data A.1 Controlled evacuation experiments

The set of experiments involved in the comparison are evacuation drills done by Garcimartín et al. [START_REF] Garcimartín | Experimental evidence of the "Faster Is Slower" effect[END_REF]. During these experiments, a total of 85 participants are asked to exit a room through a door of length 75cm. The participants were boys and girls of about 22 years old, and they were students at the School of Architecture at the University of Navarra, Spain. Two sets of runs are done. In the first set, individuals are asked to exit the room as fast as they could while trying to avoid physical contact with others and pushing was banned (low competitiveness).

This set of runs is performed five times. In the second set, individuals are asked to do the same but they were allowed to push each other while evacuating (high competitiveness), excluding violent shoving. This set of runs is performed seven times. A snapshot of the evacuation experiment is displayed in

Confidence intervals

A confidence interval for a mean consists of a range of values (interval) that act as good estimates of the unknown population mean. The confidence level describes the uncertainty associated with a sampling method. It is the probability that the confidence interval contains the true value of the population mean. The confidence level then relates to the reliability of the estimation procedure and is usually set to 90%, 95% or 99%. For the case of the numerical simulations represented in Chapter 4, the time lapses mean and the flow rate are calculated with a 95% confidence interval. To do so, for each numerical simulation we extract all time lapses as a sample. We denote by n the sample size, M and S respectively the random variables equal to the mean of the sample and its standard deviation, µ the time lapses mean (population mean) and σ the standard deviation of time lapses. It is known that the random variable

follows a Student's-t distribution with n -1 degrees of freedom. The random variable T is a pivotal quantity, i.e. it does not depend on the unknowns µ and σ. We compute the 97.5th percentile of the above distribution and denote it by c, it satisfies:

Consequently,

which gives a 95% confidence interval for the population mean µ. We compute the mean of the sample m and its standard deviation s, and we deduce the confidence interval of the

Abstract :

We are interested in the modeling of crowd motion. We propose a microscopic model based on game theoretic principles. Each individual is supposed to have a desired velocity, it is the one he would like to have in the absence of others. We consider that each individual is influenced by some of his neighbors, practically the ones that he sees. A possible actual velocity is an instantaneous Nash equilibrium: each individual does its best with respect to a personal objective (desired velocity), considering the behavior of the neighbors that influence him. We address theoretical and modeling issues in various situations, in particular when each individual is influenced by all the others, and in the case where the influence relations between individuals are hierarchical. We develop a numerical strategy to solve the problem in the second case (hierarchical model) and propose numerical simulations to illustrate the behavior of the model. We confront our numerical results with real experiments and prove the ability of the hierarchical model to reproduce some phenomena. We also propose to write a macroscopic counterpart of the hierarchical model by translating the same modeling principles to the macroscopic level and make the first steps towards writing such model. The last problem tackled in this thesis is related to gradient flow frameworks in the continuous and discrete Wasserstein spaces. It is known that the Fokker-Planck equation can be interpreted as a gradient flow for the continuous Wasserstein distance. We establish a link between some space discretization strategies of the Finite Volume type for the Fokker-Planck equation in general meshes (Voronoï tesselations) and gradient flows on the underlying networks of cells, in the framework of discrete Wasserstein-like distance on graphs recently introduced.

Université Paris-Saclay Espace Technologique / Immeuble Discovery Route de l'Orme aux Merisiers RD 128 / 91190 Saint-Aubin, France