name: inverse layout: true class: center, middle, inverse — layout: false class: center, middle

Infinite Grid Exploration
by Disoriented Robots

Quentin Bramas (University of Strasbourg, ICUBE)
Stéphane Devismes (Université Grenoble Alpes, VERIMAG)
Pascal Lafourcade (University Clermont Auvergne, LIMOS)

SIROCCO 2019, L’Aquilla, July 4th, 2019 — Mobile Robots:

  • Move on the infinite grid
  • Synchronous
  • No Memory
  • No Communication
  • Execute the same algorithm
  • Exclusive (no robots at the same position)
  • May have lights with finite number of colors
  • Limited Visibility
  • Disoriented (but common on chirality)

    Mobile Robots:

  • Look at the nodes of the grid at distance d
  • Compute a destination (Up,Left,Down,Right,Idle) based on the snapshot
  • Move


  • Start with a predetermined initial configuration
  • Each node of the grid should be visited by a robot in finite time.

Emek, Y., Langner, T., Stolz, D., Uitto, J., & Wattenhofer, R. (2015).
How many ants does it take to find the food?.




Algorithm 1

  • 6 robots
  • lights with fixed colors (3 colors)
  • visibility range = one.