This thesis deals with the problems of exploration and map construction of a dangerous network by mobile agents, and it introduces new general mechanisms for inter-agent communication, which could be applied to other mobile agents' problems. A dangerous network contains a harmful process called Black Hole that destroys all agents entering the node where it resides, without leaving any observable trace. The task for the agents, which are moving asynchronously, is to construct a map of the network with edges incident on the black hole unambiguously identified. Two types of communication mechanisms are considered: whiteboards and tokens. In the whiteboard model every node provides a shared memory on which agents can read and write. When communication occurs through tokens, instead, the agents have some pebbles that can be placed on and picked up from the nodes. Four different costs for comparing the efficiency of the protocols are taken into account: the number of agents required, the number of moves performed, the size of the whiteboard (or the token capacity at a node), and time. The black hole search problem is considered first in ring networks with whiteboards, and optimal exact time and move complexities are established improving all existing results. The same problem is then studied in arbitrary unknown graphs and it is solved in the token model by using a constant number of tokens in total. The protocol improves on existing results and is based on a novel technique for communicating using tokens. Finally, the new method of communicating using tokens described in the context of black hole search is generalized to propose a novel communication mechanism among the agents that could possibly be employed for any distributed algorithm by mobile agents.

This thesis deals with the problems of exploration and map construction of a dangerous network by mobile agents, and it introduces new general mechanisms for inter-agent communication, which could be applied to other mobile agents' problems. A dangerous network contains a harmful process called Black Hole that destroys all agents entering the node where it resides, without leaving any observable trace. The task for the agents, which are moving asynchronously, is to construct a map of the network with edges incident on the black hole unambiguously identified. Two types of communication mechanisms are considered: whiteboards and tokens. In the whiteboard model every node provides a shared memory on which agents can read and write. When communication occurs through tokens, instead, the agents have some pebbles that can be placed on and picked up from the nodes. Four different costs for comparing the efficiency of the protocols are taken into account: the number of agents required, the number of moves performed, the size of the whiteboard (or the token capacity at a node), and time. The black hole search problem is considered first in ring networks with whiteboards, and optimal exact time and move complexities are established improving all existing results. The same problem is then studied in arbitrary unknown graphs and it is solved in the token model by using a constant number of tokens in total. The protocol improves on existing results and is based on a novel technique for communicating using tokens. Finally, the new method of communicating using tokens described in the context of black hole search is generalized to propose a novel communication mechanism among the agents that could possibly be employed for any distributed algorithm by mobile agents.

La plupart des grandes villes modernes mondiales souffrent des conséquences de la pollution et des bouchons. Une solution à ce problème serait de réglementer l'accès aux centres-villes pour les voitures personnelles en faveur d'un système de transports publics constitués de navettes autonomes propulsées par une énergie n'engendrant pas de pollution gazeuse. Celles-ci pourraient desservir les usagers à la demande, en étant déroutées en fonction des appels de ceux-ci. Ces véhicules pourraient également être utilisés afin de desservir de grands sites industriels, ou bien des sites sensibles dont l'accès, restreint, doit être contrôlé. Afin de parvenir à réaliser cet objectif, un véhicule devra être capable de se localiser dans sa zone de travail. Une bonne partie des méthodes de localisation reprises par la communauté scientifique se basent sur des méthodes de type "Simultaneous Localization and Mapping" (SLAM). Ces méthodes sont capables de construire dynamiquement une carte de l'environnement ainsi que de localiser un véhicule dans une telle carte. Bien que celles-ci aient démontré leur robustesse, dans la plupart des implémentations, le partage d'une carte commune entre plusieurs robots peut s'avérer problématique. En outre, ces méthodes n'utilisent fréquemment aucune information existant au préalable et construisent la carte de leur environnement à partir de zéro.Nous souhaitons lever ces limitations, et proposons d'utiliser des cartes de type sémantique, qui existent au-préalable, par exemple comme OpenStreetMap, comme carte de base afin de se localiser. Ce type de carte contient la position de panneaux de signalisation, de feux tricolores, de murs de bâtiments etc... De telles cartes viennent presque à-coup-sûr avec des imprécisions de position, des erreurs au niveau des éléments qu'elles contiennent, par exemple des éléments réels peuvent manquer dans les données de la carte, ou bien des éléments stockés dans celles-ci peuvent ne plus exister. Afin de gérer de telles erreurs dans les données de la carte, et de permettre à un véhicule autonome de s'y localiser, nous proposons un nouveau paradigme. Tout d'abord, afin de gérer le problème de sur-convergence classique dans les techniques de fusion de données (filtre de Kalman), ainsi que le problème de mise à l'échelle, nous proposons de gérer l'intégralité de la carte par un filtre à Intersection de Covariance Partitionnée. Nous proposons également d'effacer des éléments inexistant des données de la carte en estimant leur probabilité d'existence, calculée en se basant sur les détections de ceux-ci par les capteurs du véhicule, et supprimant ceux doté d'une probabilité trop faible. Enfin, nous proposons de scanner périodiquement la totalité des données capteur pour y chercher de nouveaux amers potentiels que la carte n'intègre pas encore dans ses données, et de les y ajouter. Des expérimentations montrent la faisabilité d'un tel concept de carte dynamique de haut niveau qui serait mise à jour au-vol. / Most large modern cities in the world nowadays suffer from pollution and traffic jams. A possible solution to this problem could be to regulate personnal car access into center downtown, and possibly replace public transportations by pollution-free autonomous vehicles, that could dynamically change their planned trajectory to transport people in a fully on-demand scenario. These vehicles could be used also to transport employees in a large industrial facility or in a regulated access critical infrastructure area. In order to perform such a task, a vehicle should be able to localize itself in its area of operation. Most current popular localization methods in such an environment are based on so-called "Simultaneous Localization and Maping" (SLAM) methods. They are able to dynamically construct a map of the environment, and to locate such a vehicle inside this map. Although these methods demonstrated their robustness, most of the implementations lack to use a map that would allow sharing over vehicles (map size, structure, etc...). On top of that, these methods frequently do not take into account already existing information such as an existing city map and rather construct it from scratch. In order to go beyond these limitations, we propose to use in the end semantic high-level maps, such as OpenStreetMap as a-priori map, and to allow the vehicle to localize based on such a map. They can contain the location of roads, traffic signs and traffic lights, buildings etc... Such kind of maps almost always come with some degree of imprecision (mostly in position), they also can be wrong, lacking existing but undescribed elements (landmarks), or containing in their data elements that do not exist anymore. In order to manage such imperfections in the collected data, and to allow a vehicle to localize based on such data, we propose a new strategy. Firstly, to manage the classical problem of data incest in data fusion in the presence of strong correlations, together with the map scalability problem, we propose to manage the whole map using a Split Covariance Intersection filter. We also propose to remove possibly absent landmarks still present in map data by estimating their probability of being there based on vehicle sensor detections, and to remove those with a low score. Finally, we propose to periodically scan sensor data to detect possible new landmarks that the map does not include yet, and proceed to their integration into map data. Experiments show the feasibility of such a concept of dynamic high level map that could be updated on-the-fly.