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


bramas@unistra.fr — 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

Problem:

  • 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?. —

View

View

View

Algorithm 1

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