back to list

Dezentralized Gathering on a Grid

How can simple robots find each other without communication, memory, or central control?

Bachelor Thesis, Master Thesis

In this thesis project, you explore the problem of decentralized gathering: how a group of independent agents can autonomously meet at a common location on a grid. The challenge becomes especially interesting when the agents are oblivious, that is, they act based only on their current local perception, make decisions based on a probabilistic or deterministic controller, and have no memory of past actions. Prior work (see the literature below) has shown that under specific circumstances, gathering on a square grid is possible with a stochastic controller but impossible with any deterministic controller.

The thesis may involve:

  • Investigate different 2D grid topologies (triangular, hexagonal) to see if stochastic controllers can achieve gathering and whether deterministic controllers are possible or provably impossible.
  • Extend the gathering problem to 3D grids and study how dimensionality affects controller design and feasibility.
  • Analyze limited sensing scenarios, varying visibility radius or introducing sensing noise, and determine the minimal sensing needed for gathering.
  • Examine minimal memory extensions, e.g., 1-bit memory per agent, and their effect on deterministic gathering possibilities.
  • Introduce obstacles in the grid (walls, holes) and analyze how controllers adapt and whether gathering remains possible.

You will:

  • Understand and analyze the gathering problem on discrete grids for simple agents
  • Study how randomized local rules can lead to global coordination
  • Compare stochastic and deterministic controllers
  • Implement simulations of agent behaviors and evaluating convergence properties

This topic lies at the intersection of distributed algorithms, swarm robotics, and self-organizing systems, and is suitable for students interested in algorithmic thinking, simulation, and emergent collective behavior. If you are interested in this topic, please send an email to both Prof. Groß and Julian Rau including a brief motivation letter, your CV, and your current transcript of records.

Core data

Publications