Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les problèmes de recherche sur un graphe peuvent être exprimés sous la forme d’un jeu où un ensemble de chercheurs tentent de capturer un ensemble de fugitifs. Lorsqu’un tel jeu est joué en alternance par les deux ensembles de joueurs, nous parlons alors de jeux des policiers et des voleurs (« Cops and Robbers games ») ou plus simplement de jeux policiers-voleurs. Nowakowski et Winkler [28], et indépendamment Quilliot [45], ont introduit la première version des jeux policiers-voleurs dans laquelle un seul policier tente de capturer un seul voleur, les deux se déplaçant à tour de rôle vers des sommets adjacents de leurs positions courantes. Ils ont notamment proposé une jolie caractérisation des graphes gagnants pour le policier qui est basée sur l’existence d’un démantèlement particulier des sommets du graphe ; un démantèlement consistant à retirer un à un les sommets du graphe suivant une certaine règle. Cette caractérisation par démantèlement est par ailleurs intéressante puisqu’elle donne directement un algorithme polynomial de type diminuer pour régner pour résoudre le problème du policier et du voleur. Dans ce mémoire, nous proposons une nouvelle version d’un jeu policier-voleur dans laquelle le voleur se déplace arbitrairement vite dans le graphe et dans laquelle le policier possède une zone de surveillance qui limite le voleur dans ses déplacements. Nous caractérisons les graphes gagnants pour le policier dans ce nouveau jeu en utilisant un concept de démantèlement d’un graphe, similaire à celui de Nowakowski et Winkler [28], Quilliot [45], mais adapté aux conditions de notre nouveau jeu. Nous devons notamment généraliser la définition d’un graphe classique à celle d’un graphe clandestin, qui possède un ensemble de sommets clairs et un ensemble de sommets sombres, afin d’obtenir notre caractérisation par démantèlement. Nous donnons par ailleurs un algorithme qui permet de bâtir une stratégie monotone gagnante pour le policier en nous assurant que le policier sécurise de plus en plus de sommets à chaque tour. / Graph searching problems can be expressed as a game where a group of searchers is trying to capture a group of fugitives on a graph. When players move alternately in such a game, we are then referring to games of Cops and Robbers. Nowakowski and Winkler [28], and independently Quilliot [45], introduced the very first version of cops and robbers games in which a single cop tries to capture a single robber, both players moving alternately from their current positions to neighboring vertices. They notably proposed a very nice characterization of graphs that are winning for the cop, which is based on a particular dismantling scheme of the graph’s vertices; a dismantling scheme consisting in removing one by one each vertex of the graph by following a given rule. This dismantling-like characterization is furthermore interesting since it directly yields a divide-and-conquer algorithm that is polynomial, to solve the cop and robber problem. In this master thesis, we propose a new version of cops and robbers games in which the robber is able to move arbitrarily fast in the graph and in which the cop has a watching area that limits the robber’s moving capabilities. We characterize the cop-winning graphs for this new game by using some dismantling scheme similar to the one given by Nowakowski and Winkler [28], Quilliot [45], but that better fits our new game’s conditions. To obtain this dismantling-like characterization, we particularly need to generalize the definition of a classical graph to an undergrounded graph, whose vertices are split in a set of light vertices and a set of dark vertices. We also give an algorithm that provides a monotonous cop-winning strategy by making sure the cop is securing more and more vertices at each turn.

Les jeux de policiers et voleurs sont étudiés depuis une trentaine d’années en informatique et en mathématiques. Comme dans les jeux de poursuite en général, des poursuivants (les policiers) cherchent à capturer des évadés (les voleurs), cependant ici les joueurs agissent tour à tour et sont contraints de se déplacer sur une structure discrète. On suppose toujours que les joueurs connaissent les positions exactes de leurs opposants, autrement dit le jeu se déroule à information parfaite. La première définition d’un jeu de policiers-voleurs remonte à celle de Nowakowski et Winkler [39] et, indépendamment, Quilliot [46]. Cette première définition présente un jeu opposant un seul policier et un seul voleur avec des contraintes sur leurs vitesses de déplacement. Des extensions furent graduellement proposées telles que l’ajout de policiers et l’augmentation des vitesses de mouvement. En 2014, Bonato et MacGillivray [6] proposèrent une généralisation des jeux de policiers-voleurs pour permettre l’étude de ceux-ci dans leur globalité. Cependant, leur modèle ne couvre aucunement les jeux possédant des composantes stochastiques tels que ceux dans lesquels les voleurs peuvent bouger de manière aléatoire. Dans ce mémoire est donc présenté un nouveau modèle incluant des aspects stochastiques. En second lieu, on présente dans ce mémoire une application concrète de l’utilisation de ces jeux sous la forme d’une méthode de résolution d’un problème provenant de la théorie de la recherche. Alors que les jeux de policiers et voleurs utilisent l’hypothèse de l’information parfaite, les problèmes de recherches ne peuvent faire cette supposition. Il appert cependant que le jeu de policiers et voleurs peut être analysé comme une relaxation de contraintes d’un problème de recherche. Ce nouvel angle de vue est exploité pour la conception d’une borne supérieure sur la fonction objectif d’un problème de recherche pouvant être mise à contribution dans une méthode dite de branch and bound. / Cops and robbers games have been studied for the last thirty years in computer science and mathematics. As in general pursuit evasion games, pursuers (cops) seek to capture evaders (robbers), however here the players move in turn and are constrained to move on a discrete structure. It is always assumed that players know the exact location of their adversary, in other words the game is played with perfect information. The first definition of a cops and robbers game dates back to Nowakowski and Winkler [39] and, independantly, Quilliot [46]. This first definition presents a game opposing a single cop against a lone robber, both with constraints on their speed. Extensions were gradually formulated such as increasing the number of cops and the speed of the players. In 2014, Bonato and MacGillivray [6] presented a general characterization of cops and robbers games in order for them to be globally studied. However, their model does not take into account stochastic events that may occur such as the robbers moving in a random fashion. In this thesis, a novel model that includes stochastic elements is presented. Furthermore, we present in this thesis a concrete application of cops and robbers games in the form of a method of resolution of a problem from search theory. Although cops and robbers games assume perfect information, this hypothesis cannot be maintained in search problems. It appears however that cops and robbers games can be viewed as constraint relaxations of search problems. This point of view is made use of in the conception of an upper bound on the objective function of a search problem that is a applied in a branch and bound method.

La navigation avec les systèmes de navigation par satellites (GNSS) est un réel défi dans des environnements contraints (semi-urbain, urbain, feuillage dense) à cause des multitrajets et du masquage du signal. Cette thèse propose un nombre de solutions architecturales et algorithmiques pour le récepteur GNSS afin de pallier ces problèmes. Ces solutions se veulent capables d’exploiter les atouts des poursuites scalaire et vectorielle tout en minimisant leurs défauts et de profiter de l’efficacité de certaines techniques de filtrage Bayésien non linéaire quant à aborder la non-Gaussianité et les non-linéarités associées au problème de navigation et de poursuite vectorielle. Une attention particulière est accordée à certains estimateurs Bayésiens qui essaient d’approximer la loi a posteriori sans linéariser le modèle de filtrage, notamment le filtre de Kalman et les méthodes de filtrage particulaire, mais aussi au filtre de Kalman étendu, dont l’estimation de la loi a posteriori est basée sur la linéarisation du modèle de filtrage. En premier lieu, une brève étude bibliographique présentant les fondamentaux des systèmes et des récepteurs GNSS ainsi que les algorithmes de navigation et de poursuite y associés est faite. Ensuite le fonctionnement d’un récepteur GNSS en milieux contraints est investigué. La thèse propose des modèles pour caractériser les erreurs de poursuite induites par les multitrajets dans une boucle de poursuite vectorielle. Ces modèles permettent d’exprimer les erreurs de poursuite en fonction du délai, de la phase et de la fréquence d’évanouissement des multitrajets. En exploitant le fait que la présence des multitrajets se reflète sur la sortie moins des corrélateurs, de nouveaux détecteurs de multitrajets sont formulés. Un détecteur de masquage du signal direct est aussi proposé. L’attention se tourne ensuite vers la conception d’architectures robustes de poursuite et positionnement pour un récepteur GNSS, incorporant les détecteurs proposés et d’autres indicateurs de qualité. Une boucle de poursuite vectorielle capable de détecter et d’exclure des mesures qui ne sont pas saines du calcul de la solution de navigation en utilisant les indicateurs de qualité est proposée. Deux autres boucles de poursuite, la boucle de poursuite adaptative scalaire-vectorielle et la boucle de poursuite conjointe scalaire-vectorielle, avec la même capacité de détection et exclusion de fautes, sont formulées. Elles bénéficient de la robustesse de la poursuite vectorielle en milieux contraints et de la précision de la poursuite scalaire en milieux dégagés. Des résultats expérimentaux montrent que les solutions conçues offrent une meilleure alternative de poursuite et positionnement par rapport aux boucles usuelles de poursuite scalaire et de poursuite vectorielle. Enfin, la thèse présente des approches de filtrage Bayésien non linéaire pour résoudre le problème de navigation et de poursuite vectorielle. Des stratégies de filtrage itératives et adaptatives appliquées au filtre de Kalman sont étudiées. Une nouvelle approche de filtrage particulaire dénommée filtre particulaire itératif et adaptatif (IAUPF) est formulée. Cette approche exploite les propriétés de convergence des méthodes itératives, l’immunité à la divergence dont jouissent les filtres adaptatifs, et la synergie entre les approches de filtrage particulaire et de Kalman. Des simulations de Monte Carlo avec une borne inférieure de Cramér-Rao a posteriori comme référence ainsi que des résultats expérimentaux montrent que l’approche IAUPF a une meilleure performance comparativement aux autres estimateurs Bayésiens présentés / Navigation with Global Navigation Satellite Systems (GNSS) is a real challenge in harsh environments (suburban, urban, heavy foliage) due to multipath and signal blockage. This thesis proposes a number of GNSS receiver architectural and algorithmic solutions to deal with this challenge. These solutions aim at exploiting the strengths of scalar and vector tracking while minimizing their weaknesses and at utilizing the efficiency of some nonlinear Bayesian filtering techniques in addressing the nonlinearities and non-Gaussianities associated with the navigation and vector tracking problem. Attention is given to some Bayesian estimators that approximate the posterior distribution without linearizing the filtering model, namely the unscented Kalman and particle filtering methods, as well as to the extended Kalman filter, whose posterior estimation is grounded on linearization of the filtering model.First, a brief literature review that presents the fundamentals of GNSS and GNSS receivers together with the applied navigation and tracking algorithms is provided. Then an investigation of the GNSS receiver operation in multipath environments is performed. The thesis proposes models for characterizing multipath induced tracking errors in a vector tracking loop. These models make it possible to express the tracking errors with respect to multipath delay, multipath phase and multipath fading frequency. By exploiting the fact that multipath presence is mirrored on the Early-minus-Late correlator output, novel multipath detectors are devised. A correlator-based non-line-of-sight detector is designed as well. Attention is then directed towards the design of robust tracking and positioning GNSS receiver architectures that incorporate the proposed detectors among other signal quality indicators. A vector tracking scheme capable of detecting and excluding unhealthy measurements from position-velocity-time calculation in the navigator using correlator-based signal quality indicators is suggested. Two other novel tracking schemes, the adaptive scalar-vector tracking loop and the conjoint scalar-vector tracking loop, with the same fault detection and exclusion capability, are formulated. They benefit from vector tracking robustness in harsh environments and scalar tracking positioning accuracy in open sky environments. Experimental results show that the proposed solutions have better tracking and positioning performance than the usual scalar and vector tracking loops. Finally, the thesis presents a number of nonlinear Bayesian filtering approaches to solve the navigation and vector tracking problem. Iterative and adaptive strategies as applied to the unscented Kalman filter are studied. A novel unscented particle filter approach, the iterated adaptive unscented particle filter (IAUPF), is proposed. This approach exploits the convergence properties of iterative methods, the divergence suppression benefits of adaptive filters and the synergy of unscented Kalman and particle filtering approaches. Monte-Carlo simulations conducted with a posterior Cramér-Rao lower bound used as benchmarking reference as well as experimental results demonstrate that the IAUPF outperforms the other Bayesian estimators that are presented

Le présent travail de recherche s'intéresse à l'apprentissage implicite de régularités dans des tâches motrices continues (ex : tâche de poursuite de cible) et discrètes (ex : tâche de Temps de réaction Sériel). Dans un premier temps, une réanalyse des travaux de Wulf et collaborateurs, portant sur l'apprentissage moteur implicite, a permis de mettre en évidence l'existence de problèmes méthodologiques et de biais potentiels, pouvant expliquer le fait que ces auteurs obtiennent un apprentissage implicite dans leur tâche de poursuite continue. Cependant, en respectant une méthodologie plus rigoureuse, il apparaît qu'il est bien difficile d'obtenir un tel apprentissage dans une tâche continue. Ceci nous a donc conduit, dans un second temps, à essayer de comprendre pourquoi il était plus facile de tirer bénéfice d'une répétition dans une tâche discrète que dans une tâche continue. Pour se faire, une tâche de TRS classique a été modifiée (nouveau périphérique, contrainte de précision, déplacement autonome et continu de la cible). Le but était de rendre cette tâche discrète la plus similaire possible à une tâche continue afin de voir si l'apprentissage implicite continuait à se manifester avec de telles modifications. Au final, les résultats obtenus ne permettent pas de fournir une réponse exhaustive pour expliquer la différence d'apprentissage existant entre les tâches continues et les tâches discrètes. L'ensemble des travaux réalisés au travers de cette thèse a, cependant, largement contribué à délimiter plus clairement les situations dans lesquelles l'apprentissage est possible. Dans le même temps, ces travaux constituent un apport dans la littérature restreinte sur l'apprentissage moteur implicite et enrichissent le débat « discret / continu », en ouvrant la voie vers de nouvelles perspectives de recherche.

On présente dans ce mémoire, une approche globale du probème de poursuite radar de cibles manoeuvrantes à faible rapport signal/bruit, par filtrage non-linéaire particulaire. Le filtrage particulaire, dont les bases ont été jetées dès 1989, permet d'aborder tous les cas où les non-linéarités présentes posent des difficultés de résolution aux techniques de filtrage dynamique. Il consiste à construire une approximation-mesure de la probabilité conditionnelle de la variable d'état à estimer par particules aléatoires, dont la dynamique est régie par le flot stochastique du système, et qui sont pondérées, via la règle de Bayes, par les mesures jusqu'à l'instant courant. Ce travail présente en premier lieu le traitement direct des mesures radar brutes en sortie d'échantillonneur/convertisseur. On montre notamment que la prise en compte de la dynamique de cible dans l'intégration cohérente des récurrences RADAR, permet d'atteindre les limites théoriques de détection, jusqu'alors inacessibles. Cela conduit notamment à revoir le problème de détection, car l'intégration d'un modèle de dynamique permet de relever le rapport signal/bruit équivalent, et minimise les problèmes de fausse alarme. En second lieu, on détaille le post-traitement des données de position délivrées par un radar de poursuite usuel, en particulier pour le modèle générique de missile à loi de navigation proportionnelle. On présente dans ce cas la résolution du problème de détermination de but visé, qui se pose en terme d'un test d'hypothèses sur le modèle de dynamique de l'assaillant.

Reproduction de : Thèse de doctorat : Automatique et Informatique industrielle : Lille 1 : 2006. / N° d'ordre (Lille 1) : 3827. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. p. 181-192. Liste des publications et des communications.

Cette thèse porte sur l'application des techniques de filtrage statistiques au radar passif. L'objectif de cette thèse est d'adapter les méthodes à somme de gaussiennes et les méthodes particulaires pour la détection et/ou la poursuite dans un contexte multi-cible. Nous nous intéressons aux problématiques liées à des cibles fortement manoeuvrantes à rapport signal sur bruit pouvant être très faible. En guise d'application, la radio FM et la télévision numérique DVB-T seront exploitées comme sources d'opportunité par le système de localisation passive. Dans un premier temps, cette thèse récapitule l'état de l'art dans le domaine du radar passif, du filtrage statistique et des approches conventionnelles de pistage radar à base de données seuillées. Dans un deuxième temps, cette thèse explore l'apport du filtrage particulaire en radar passif. Avec une modélisation convenable du problème de poursuite d'une cible sous la forme d'un système dynamique non-linéaire, nous montrons comment le filtrage particulaire, appliqué sur les sorties bruitées (non-seuillées) du corrélateur, améliore les performances en terme de poursuite par rapport aux approches conventionnelles. Une extension au cas multi-cible est également traitée. L'ingrédient essentiel de l'algorithme proposé est l'intégration d'un système de synchronisation de l'instant d'échantillonnage du corrélateur (et le cas échéant de la fréquence de corrélation) qui permet à l'algorithme particulaire de compenser automatiquement la dynamique des cibles. Dans un troisième temps, nous exposons un nouveau système de détection/poursuite multi cible basé sur le filtrage bayésien avec la méthodologie "track-before-detect". Ce système est implémenté par une approximation à base de somme de gaussiennes ou une approximation à base de filtrage particulaire. Nous proposons également une technique d'annulation successive d'interférence qui permet de gérer la présence de lobes secondaires importants. Des simulations utilisant un signal radio FM, ont permis de confirmer le potentiel du système de détection/poursuite proposé.