Multi-agent rendezvous

The goal of this thesis is to address the rendezvous problem for multi-agent coordination and search. To rendezvous is to meet or to physically come together, and the applications of this problem range from everyday life to robotics. Example scenarios for these applications are friends coordinating a meeting or robots and autonomous vehicles coming together for load balancing or resource sharing. Each of these tasks require a rendezvous, which can involve a considerable amount of inter-agent coordination. Our goal is to develop energy-efficient rendezvous algorithms so that we can minimize the inter-agent coordination cost, the number of rendezvous attempts, failure rate, total distance traveled and time taken to rendezvous.We study the multi-agent rendezvous problem under two primary constraints: the amount of prior knowledge about the environment and the agents, and the frequency of communication allowed between the agents. These constraints are combined to define four classes of the rendezvous problem, in different environments with different agents. They are: (a) no prior knowledge and no communication, (b) partial prior knowledge and partial communication, (c) no prior knowledge and partial communication and (d) partial prior knowledge and no communication. We specifically consider four scenarios corresponding to each category respectively, as: (1) rendezvous of simulated agents for resource sharing while exploring an unknown environment without communication, (2) rendezvous between humans on street networks with intermittent communication and uncertainties in travel time, (3) rendezvous search by an Autonomous Underwater Vehicle (AUV) for passively floating scientific data collectors with no prior knowledge about the environment or the agent and periodic communication for motion modeling of the floating targets, and lastly, (4) an Autonomous Surface Vehicle (ASV) searching for lost targets at sea with some prior knowledge about the target's probability distribution and no communication until the target is found. We analyze the rendezvous problem in each of these four cases and present algorithms for them. We validate our proposed rendezvous coordination and search algorithms using software tools that we developed for large scale simulation and testing.L'objectif de cette thèse est d'aborder le problème du rendez-vous dans le cadre de la coordination et de la recherche impliquant plusieurs agents. Le concept de rendez-vous signifie atteindre un autre agent, ou le fait que de multiples agents se regroupent physiquement. Les applications de ce problème sont multiples et s'étendent de la vie quotidienne au domaine de la robotique. Voici des exemples illustrant ces applications: des amis souhaitent coordonner une rencontre, ou des robots et des agents logiciels doivent se réunir pour l'équilibrage de charge ou le partage de ressources. Chacune de ces tâches nécessite un rendez-vous, qui peut à son tour nécessiter une quantité considérable de coordination entre agents. Notre objectif est de développer des algorithmes permettant des rendez-vous efficaces en termes d'énergie totale dépensée. En d'autres termes, nous souhaitons minimiser le coût de la coordination inter-agents, le nombre de tentatives de rendez-vous, le taux d'échec, la distance totale parcourue et le temps de voyage nécessaire.Nous étudions le problème de rendez-vous impliquant plusieurs agents selon deux primaire contraintes: d'une part, la quantité préalable de connaissances sur l'environnement et les agents, et d'autre part, fréquence de la communication permise entre les différents agents. Ces contraintes aident à définir quatre catégories de problème du rendez-vous dans des environnements différents avec différents agents. Ces catégories sont: (a) aucune connaissance préalable et aucune communication permise, (b) connaissance partielle préalable et communication partielle permise, (c) aucune connaissance préalable et communication partielle permise; et (d) connaissance partielle préalable et aucune communication permise. Nous considérons spécifiquement quatre scénarios correspondant à chaque catégorie, respectivement: 1) rendez-vous entre agents simulés en vue d'un partage de ressources, avec exploration d'un environnement inconnu sans communication possible, 2) rendez-vous entre humains sur les réseaux routiers avec communication intermittente et des incertitudes au niveau du temps de voyage, 3) recherche de rendez-vous par un véhicule sous-marin autonome afin de faire dériver passivement les appareils de collecte de données scientifiques et ce, sans connaissance préalable de l'environnement ou de l'agent et avec une communication périodique pour la modélisation du parcours des cibles flottantes. Enfin, 4) un véhicule de surface autonome utilisé à des fins de recherche de cibles perdues en mer et ce, avec une certaine connaissance préalable de la distribution de probabilité des cibles mais sans aucune communication permise jusqu'à ce que la cible soit trouvée. Nous analysons le problème de rendez-vous dans chaque situation ci-dessus et proposons des algorithmes pour chaque cas. Nous validons ces algorithmes de recherche et de coordination de rendez-vous à l'aide d'outils logiciels que nous avons développés à des fins de simulations et tests à grande échelle