Approche déterministe des agents mobiles dans le plan

Tchuidjang, Zacharie (2025). Approche déterministe des agents mobiles dans le plan. Mémoire. Gatineau, Université du Québec en Outaouais, Département d'informatique et d'ingénierie, 48 p.

Prévisualisation

PDF Télécharger (450kB) | Prévisualisation

Résumé

Dans ce mémoire nous étudions deux problèmes principaux. Le premier problème connu sous le nom de chasse au trésor présente un agent modélisé par un point qui navigue dans le plan et doit retrouver un trésor situe à distance au plus D de celui-ci, avec D inconnu. Le trésor est modélisé par un point immobile. Les mouvements de l’agent sont contraints : il peut se déplacer à distance quelconque positive mais seulement dans l’une des directions cardinales. De plus, à partir de sa position actuelle, l’agent a une visibilité limitée à une distance maximale de 1 unité autour de lui. L’objectif de l’agent est de voir le trésor, c’est-à-dire de s’approcher à une distance maximale de 1 unité du trésor.
Le deuxième problème, connu sous le nom de l’approche et qui est un cas plus général du premier, implique deux agents modélisés par des points mobiles dans le plan qui doivent se rapprocher l’un de l’autre. Les agents sont initialement situés à distance au plus D l’un de l’autre, D étant inconnu des deux agents. Chaque agent est identifié par une étiquette représentée par un entier positif unique. Les agents se déplacent de manière synchrone, en suivant les mêmes règles de mouvement que dans le premier problème. Ils commencent simultanément et procèdent en rondes synchrones qui durent une unité de temps. Pendant chaque ronde, un agent peut soit rester immobile soit se déplacer à une distance de 1 unité. Ils ont le même champ de vision restreint a une distance maximale de 1 unité autour d’eux. L’objectif est que les deux agents se rapprochent à une distance maximale de 1 unité l’un de l’autre, c’est-à-dire qu’ils se voient.
Pour chacun de ces problèmes, le temps est mesuré par le nombre de rondes qui s’écoulent entre la mise en mouvement et l’atteinte de l’objectif (trouver le trésor ou l’approche, selon le cas).
Ce mémoire démontre que ces problèmes sont résolubles grâce à des algorithmes déterministes. Pour chaque algorithme présente, nous prouvons son exactitude et analysons sa complexité temporelle.

Type de document:	Thèse (Mémoire)
Directeur de mémoire/thèse:	Pelc, Andrzej
Départements et école, unités de recherche et services:	Informatique et ingénierie
Date de dépôt:	02 juill. 2025 14:35
Dernière modification:	02 juill. 2025 14:35
URI:	https://di.uqo.ca/id/eprint/1807

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt