In this thesis, strategies for navigating a crowded area using an autonomous holonomic robot are discussed and evaluated. The focus is set on path planning and the topic is therefore largely decoupled from the prediction (i.e. machine learning) and control theory techniques needed for a practical implementation outside of the simulated environment. Existing methods and algorithms for path planning in highly dynamic environments are compared using several measures via computer simulations in different environments. A new, effective, and yet simple, algorithm is introduced and proven to be useful in certain scenarios. This algorithm, ART, predicts the future states of the crowd and using these predictions finds better paths to the goal than traditional algorithms. / I detta examensarbete utvärderas och diskuteras strategier för navigering bland folk med hjälp av en självstyrd holonomisk robot. Fokus är satt på navigeringsproblemet i sig och närliggande ämnen som maskininlärning och reglerteknik behandlas ej även om en fördjupning på dessa områden vore nödvändigt för en praktisk implementation utanför den simulerade världen. Existerande strategier och algoritmer för navigering av dynamiska miljöer utvärderas genom datorsimuleringar i varierande miljöer. En ny algorithm presenteras och visar sig vara användbar i vissa situationer. Denna algoritm, ART, förutser folkmassans rörelser och använder denna information för att hitta bättre vägar till målet.

This master’s thesis investigates the application of anomaly detection techniques to analyze crowdmovements using cell location data, a topic of growing interest in public safety and policymaking. Thisresearch uses machine learning algorithms, specifically Isolation Forest and DBSCAN, to identify unusualmovement patterns within a large, unlabeled dataset. The study addresses the challenges inherent inprocessing and analyzing vast amounts of spatial and temporal data through a comprehensive method-ology that includes data preprocessing, feature engineering, and optimizing algorithm parameters. Thefindings highlight the feasibility of employing anomaly detection in real-world scenarios, demonstratingthe algorithms’ ability to detect anomalies and offering insights into crowd dynamics.

Développer un modèle de mouvement de foule capable de simuler l'évacuation d'un lieu public de moyenne ou forte affluence devient utile, voire nécessaire, afin que les futures constructions ou aménagements publics puissent offrir une qualité de sécurité optimale à leurs usagers. Les effets des piétons sur les structures du génie civil, comme l'interaction dynamique foule-structure, doivent aussi être pris en compte et modélisés. Dans le cadre de cette thèse, un modèle de foule 2D discret est proposé dans lequel les actions et les décisions de chaque piéton sont traitées individuellement. Ce modèle est aussi capable de modéliser le chargement dynamique d'un piéton sur une structure vibrante. Trois étapes sont nécessaires à l'établissement du modèle proposé. La première concerne la gestion du mouvement et des interactions piéton-piéton et piéton-obstacle. Nous nous sommes inspirés des milieux granulaires pour modéliser les interactions au sein de la foule. Nous avons étudié, implémenté et adapté dans l'environnement MATLAB, le modèle granulaire proposé par Frémond, entrant dans un cadre thermodynamique rigoureux dans lequel les interactions locales sont gérées par l'utilisation de pseudo-potentiels de dissipation, et dans lequel les collisions entre particules peuvent être élastiques ou inélastiques. Une comparaison de ce modèle à deux autres approches déjà adaptées aux mouvements de foule est présentée.La seconde étape consiste à gérer le comportement des piétons. Cette gestion du comportement se fait en plusieurs niveaux de complexité. Dans le premier niveau qui est nécessaire, une stratégie de déplacement est affectée à chaque piéton. La stratégie du chemin le plus court pour qu'un piéton se déplace d'un lieu à un autre a été choisie. Elle a été implémentée à l'aide d'un algorithme de Fast Marching et utilisée pour obtenir la direction souhaitée de chaque piéton au cours du temps. Les autres niveaux de complexité permettent de décrire des comportements plus élaborés tels que l'évitement entre piétons ou le déplacement en sous-groupe, grâce à l'introduction de forces sociales. Une approche originale permettant de former des sous-groupes de piétons à l'aide d'un pseudo-potentiel de dissipation est proposée. La dernière étape concerne le couplage piéton-structure, nous avons cherché à modéliser le chargement dynamique d'un piéton sur une structure vibrante. L'action du piéton sur le sol a été représentée par une force sinusoïdale qui modélise le mouvement d'oscillation de l'individu pendant la marche. En fixant notre attention sur les passerelles, on s'est intéressé au phénomène de synchronisation en fréquence qui peut apparaître entre la fréquence de marche de chaque piéton et la fréquence d'oscillation du système "foule-passerelle". Ce phénomène a été modélisé grâce à l'utilisation d'une équation différentielle de type Kuramoto qui gère la phase de la force de marche de chaque piéton. Un développement analytique du modèle proposé permet d'obtenir les expressions de certains paramètres liés à la synchronisation. Des simulations numériques appliquent ce modèle de foule à l'évacuation des structures du génie civil et à l'interaction foule-passerelle / The development of a model for crowd movement simulating the evacuation of public spaces becomes useful and necessary to determine the effectiveness of transportation infrastructures. The effects of pedestrians on civil engineering structures, such as crowd-structure dynamic interaction, must also be considered and modeled. In this thesis, a 2D crowd model is proposed in which the movement of each pedestrian is represented both in time and space. This model is able to take into account the dynamical pedestrians' action on a moving floor. Three steps are needed to assemble the proposed model. The first concerns the management of pedestrian-pedestrian and pedestrian-obstacle interactions. The non-smooth granular model proposed by Frémond to manage collisions between rigid particles is studied and implemented in a MATLAB environment. This discrete approach applies a rigorous thermodynamic framework in which the local interactions between particles are managed using pseudo-potentials of dissipation. A comparison between this model and two others, already adapted to the crowd, is performed. The second step concerns the management of pedestrians' behavior. A displacement strategy has to be defined for each pedestrian. The strategy of the shortest path to get from one point to another is implemented through a Fast Marching algorithm and is used to obtain the instantaneous desired direction of each pedestrian. Social forces are also introduced in order to manage the interaction between each pedestrian and his nearest environment. An original approach allowing us to create and control subgroups, using pseudo-potentials of dissipation, is implemented. The last step deals with the crowd-footbridge coupling for lateral and vertical oscillations of the structure. An alternating (sinusoidal) sideways force is used in order to take into account the pedestrian's oscillations around his trajectory. This force, due to his walking and his action on the bridge, allows one to define the acceleration of each pedestrian's oscillations around his trajectory. The synchronization of the walking frequency of each pedestrian with the oscillations frequency of the system "crowd-footbridge" is managed via a Kuramoto type differential equation which allows one to govern the evolution of the total phase of the walking force generated by each pedestrian on the bridge. An analytical study is also developed to determine the key parameters of the synchronization phenomenon. Numerical simulations using the proposed model dealing with crowd evacuation of civil engineering structures and pedestrians-footbridge interaction are finally presented

Que ce soit dans une rue commerçante, un supermarché ou un aéroport, les phénomènes de foule sont incontournables et nous affecte au quotidien. Elle constitue un système complexe dont la dynamique collective, résultant des interactions individuelles, est difficile à appréhender et a toujours intrigué les scientifiques de différents domaines. Grâce au progrès technologique, il est aujourd'hui possible de modéliser les mouvements de foule et de les reproduire en simulation. Les simulations de mouvement de foule permettent aux chercheurs de plusieurs disciplines, comme les sciences sociales ou la biomécanique, de mieux étudier et comprendre les mouvements des piétons et leurs interactions. Quant aux sciences de la sécurité et du transport, ils y voient des applications concrètes comme le développement de modèles de foule capables de simuler l'évacuation d'un lieu public de moyenne ou de forte affluence, afin que les futures constructions ou aménagements publics puissent offrir une qualité de sécurité et de service optimale pour les usagers. Dans le cadre de cette thèse, nous avons travaillé sur le perfectionnement du modèle discret proposé et développé par l'équipe dynamique du laboratoire Navier. Dans ce modèle, les actions et les décisions de chaque piéton sont traitées individuellement. Trois aspects du modèle ont été traités dans cette thèse. Le premier concerne la navigation des piétons vers leurs destinations. Dans notre modèle, un piéton est représenté par une particule ayant une direction et une allure souhaitées. Cette direction est obtenue par la résolution d'une équation eikonale. La solution de cette équation permet d'obtenir un champ de vitesses qui attribue à chaque piéton, en fonction de sa position, une direction vers sa destination. La résolution de l'équation une fois ou à une période quelconque donne la stratégie du chemin le plus court ou le plus rapide respectivement. Les effets des deux stratégies sur la dynamique collective de la foule sont comparés. Le deuxième consiste à gérer le comportement des piétons. Après avoir choisi son chemin, un piéton doit interagir avec l'environnement (obstacles, topologie, ...) et les autres piétons. Nous avons réussi à intégrer trois types de comportement dans notre modèle: (i) la poussée en utilisant une approche originale, basée sur la théorie des collisions des corps rigides dans un cadre thermodynamique rigoureux, (ii) le passage agressif (forcer son chemin) modélisé par une force sociale répulsive et (iii) l'évitement ``normal'' en adoptant une approche cognitive basée sur deux heuristiques. Les performances des trois méthodes ont été comparées pour plusieurs critères. Le dernier aspect concerne la validation et la vérification du modèle. Nous avons réalisé une étude de sensibilité et validé le modèle qualitativement et quantitativement. À l'aide d'un plan d'expérience numérique nous avons réussi à identifier les paramètres d'entrée ayant les effets principaux sur les résultats du modèle. De plus, nous avons trouvé les différentes interactions entre ces paramètres. En ce qui concerne la validation qualitative, nous avons réussi à reproduire plusieurs phénomènes d'auto-organisation. Enfin, nous avons testé la capacité de notre modèle à reproduire des résultats expérimentaux issus de la littérature. Nous avons choisi le cas du goulot d'étranglement. Les résultats du modèle et ceux de l'expérience ont été comparés. Ce modèle de foule a également été appliqué à l'acheminement des piétons dans la gare de Noisy-Champs. L'objectif de cette application est d'estimer le temps de stationnement des trains dans la gare / Crowds are present almost everywhere and affect several aspects of our lives. They are considered to be on of the most complex systems whose dynamics, resulting from individual interactions and giving rise to fascinating phenomena, is very difficult to understand and have always intrigued experts from various domains. The technological advancement, especially in computer performance, has allowed to model and simulate pedestrian movement. Research from different disciplines, such as social sciences and bio-mechanics, who are interested in studying crowd movement and pedestrian interactions were able to better examine and understand the dynamics of the crowd. Professionals from architects and transport planners to fire engineers and security advisors are also interested in crowd models that would help them to optimize the design and operation of a facility. In this thesis, we have worked on the imporvement of a discrete crowd model developed by the researchers from the dynamics group in Navier laboratory. In this model, the actions and decisions taken by each individual are treated. In its previous version, the model was used to simulate urgent evacuations. Three main aspects of the model were addressed in this thesis. The first one concerns pedestrian navigation towards a final destination. In our model, a pedestrian is represented by a disk having a willingness to head to a certain destination with a desired direction and a desired speed. A desired direction is attributed to each pedestrian, depending on his position from the exit, from a floor field that is obtained by solving the eikonal equation. Solving this equation a single time at the beginning of the simulation or several times at during the simulation allows us to obtain the shortest path or the fastest path strategy respectively. The influence of the two strategies on the collective dynamics of the crowds is compared. The second one consists of managing pedestrian-pedestrian interactions. After having chosen his/her direction according to one of the available strategies, a pedestrian is bound to interact with other pedestrians present on the chosen path. We have integrated three pedestrian behaviors in our model: (i) pushing by using an original approach based on the theory of rigid body collisions in a rigorous thermodynamics context, (ii) forcing one's way by introducing a social repulsive force and (iii) "normal" avoidance by using a cognitive approach based on two heuristics. The three methods are compared for different criteria. The last aspect is the validation and verification of the model. We have performed a sensibility study and validated the model qualitatively and quantitatively. Using a numerical experimental plan, we identified the input parameters that are the most statistically significant and estimated the effects of their interactions. Concerning qualitative validation, we showed that our model is able to reproduce several self-organization phenomena such as lane formation. Finally, our model was validated quantitatively for the case of a bottleneck. The experimental results are very close to the ones obtained from simulations. The model was also applied to pedestrian movement in the Noisy-Champs train station. The objective of the study was to estimate the train dwell time. The simulation results were similar to the observations