skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Terminating Exploration Of A Grid By An Optimal Number Of Asynchronous Oblivious Robots

Devismes, Stéphane ; Lamani, Anissa ; Petit, Franck ; Raymond, Pascal ; Tixeuil, Sébastien

Computer journal, 2021-01, Vol.64 (1), p.132-154 [Periódico revisado por pares]

Oxford University Press

Texto completo disponível

Citações Citado por
  • Título:
    Terminating Exploration Of A Grid By An Optimal Number Of Asynchronous Oblivious Robots
  • Autor: Devismes, Stéphane ; Lamani, Anissa ; Petit, Franck ; Raymond, Pascal ; Tixeuil, Sébastien
  • Assuntos: Cognitive science ; Computer science ; Data Structures and Algorithms ; Discrete Mathematics ; Distributed, Parallel, and Cluster Computing ; Mobile Computing ; Networking and Internet Architecture ; Robotics ; Ubiquitous Computing
  • É parte de: Computer journal, 2021-01, Vol.64 (1), p.132-154
  • Descrição: Abstract We consider swarms of asynchronous oblivious robots evolving into an anonymous grid-shaped network. In this context, we investigate optimal (w.r.t. the number of robots) deterministic solutions for the terminating exploration problem. We first show lower bounds in the semi-synchronous model. Precisely, we show that at least three robots are required to explore any grid of at least three nodes, even in the probabilistic case. Then, we show that at least four (resp. five) robots are necessary to deterministically explore a $\bf(2,2)$-Grid (resp. a $\bf(3,3)$-Grid). We then propose deterministic algorithms in the asynchronous model. This latter being strictly weakest than the semi-synchronous model, all the aforementioned bounds still hold in that context. Our algorithms actually exhibit the optimal number of robots that is necessary to explore a given grid. Overall, our results show that except in two particular cases, three robots are necessary and sufficient to deterministically explore a grid of at least three nodes and then terminate. The optimal number of robots for the two remaining cases is four for the $\bf(2,2)$-Grid and five for the $\bf(3,3)$-Grid, respectively.
  • Editor: Oxford University Press
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.