Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911811418193920 |
|---|---|
| author | Akker, Erik van den Buchin, Kevin Foerster, Klaus-Tycho |
| author_facet | Akker, Erik van den Buchin, Kevin Foerster, Klaus-Tycho |
| contents | We study the problem of multi-agent online graph exploration, in which a team of k agents has to explore a given graph, starting and ending on the same node. The graph is initially unknown. Whenever a node is visited by an agent, its neighborhood and adjacent edges are revealed. The agents share a global view of the explored parts of the graph. The cost of the exploration has to be minimized, where cost either describes the time needed for the entire exploration (time model), or the length of the longest path traversed by any agent (energy model). We investigate graph exploration on cycles and tadpole graphs for 2-4 agents, providing optimal results on the competitive ratio in the energy model (1-competitive with two agents on cycles and three agents on tadpole graphs), and for tadpole graphs in the time model (1.5-competitive with four agents). We also show competitive upper bounds of 2 for the exploration of tadpole graphs with three agents, and 2.5 for the exploration of tadpole graphs with two agents in the time model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13845 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs Akker, Erik van den Buchin, Kevin Foerster, Klaus-Tycho Data Structures and Algorithms Distributed, Parallel, and Cluster Computing We study the problem of multi-agent online graph exploration, in which a team of k agents has to explore a given graph, starting and ending on the same node. The graph is initially unknown. Whenever a node is visited by an agent, its neighborhood and adjacent edges are revealed. The agents share a global view of the explored parts of the graph. The cost of the exploration has to be minimized, where cost either describes the time needed for the entire exploration (time model), or the length of the longest path traversed by any agent (energy model). We investigate graph exploration on cycles and tadpole graphs for 2-4 agents, providing optimal results on the competitive ratio in the energy model (1-competitive with two agents on cycles and three agents on tadpole graphs), and for tadpole graphs in the time model (1.5-competitive with four agents). We also show competitive upper bounds of 2 for the exploration of tadpole graphs with three agents, and 2.5 for the exploration of tadpole graphs with two agents in the time model. |
| title | Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2402.13845 |