Comment explorer un arbre inconnu avec des agents à énergie limitée ?
| Autor: | Bampas, Evangelos, Chalopin, Jérémie, Das, Shantanu, Hackfeld, Jan, Karousatou, Christina |
|---|---|
| Přispěvatelé: | Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Institute of Mathematics, TU Berlin, Technische Universität Berlin (TU), ANR-14-CE36-0002,ANCOR,Algorithm Design for Microrobots with Energy Constraints(2014), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Algorithmique Distribuée (DALGO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Technical University of Berlin / Technische Universität Berlin (TU) |
| Rok vydání: | 2018 |
| Předmět: |
Computer Science::Multiagent Systems
FOS: Computer and information sciences Computer Science - Data Structures and Algorithms [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] agents mobiles Data Structures and Algorithms (cs.DS) énergie limitée [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] exploration arbre inconnu |
| Zdroj: | ALGOTEL 2017-19èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications ALGOTEL 2017-19èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2017, Quiberon, France |
| DOI: | 10.48550/arxiv.1802.06636 |
| Popis: | International audience; We wish to explore an unknown tree with a team of k >= 1 initially collocated mobile agents. Each agent has limited energy and cannot,as a result, traverse more than B edges. The goal is to maximize the number of nodes collectively visited by all agents during the execution.Initially, the agents have no knowledge about the structure of the tree,but they gradually discover the topology as they traverse new edges. We assume that the agents can communicate with each other at arbitrary distances, therefore the knowledge obtained by one agent after traversing an edge is instantaneously transmitted to the other agents.We propose an intuitive algorithm based on depth-first search and westudy its performance compared to the optimal solution that we could obtain if we knew in advance the map of the tree. We prove that this algorithm has a constant competitive ratio. We also provide a lower bound on the competitive ratio of any algorithm.; On souhaite explorer un arbre inconnu avec une équipe de k \geq 1 agents mobiles initialement regroupés sur un sommet. Chaque agent dispose d'une énergie limitée et ne peut pas traverser plus de B arêtes. On souhaite maximiser le nombre de sommets visités par l'équipe d'agents lors de l'exécution. Initialement, les agents n'ont aucune connaissance sur la structure de l'arbre, mais ils en découvrent la topologie au fur et à mesure qu’ils traversent de nouvelles arêtes. Nous supposons que les agents peuvent communiquer entre eux à distance illimitée, donc la connaissance qu'un agent obtient lors de la traversée d'une arête est instantanément transmise aux autres agents. Nous proposons un algorithme très intuitif, basé sur le parcours en profondeur, et nous étudions son efficacité par rapport à la solution optimale qu'on peut obtenir lorsqu'on connaît initialement la carte. Nous prouvons que cet algorithme a un rapport de compétitivité constant. Nous fournissons également une borne inférieure sur le rapport de compétitivité réalisable par un algorithme quelconque. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|