Résolution de labyrinthe par remplissage pour robots micromouse

Le remplissage par diffusion est l’algorithme qui gagne la plupart des compétitions Micromouse, et c’est une belle introduction à la planification sous incertitude. Contrairement à la recherche de chemin des manuels, un robot de labyrinthe ne part pas de la carte complète — il doit découvrir les murs en roulant. Le remplissage est fait exactement pour cela. Regardez-le tourner dans le simulateur de résolution de labyrinthe.

Un champ de distances, pas un chemin

Le remplissage attribue à chaque case un nombre : sa distance au but. Les cases du but reçoivent zéro. De là, chaque case voisine non bloquée reçoit un de plus que sa voisine la plus basse, en s’étendant jusqu’à ce que chaque case atteignable ait une valeur.

Le robot ne stocke jamais un itinéraire. Il se tient juste dans une case, regarde ses voisines, et avance vers l’une dont le nombre est exactement inférieur d’un. Le champ de distances est le plan, et c’est pourquoi il se rétablit proprement quand la carte change.

L’optimisme sur les murs inconnus

Le robot ne peut pas voir tout le labyrinthe, donc le remplissage traite chaque mur non encore détecté comme ouvert. Cet optimisme produit l’estimation la plus courte possible et garde le robot en marche vers le but au lieu d’explorer au hasard.

Quand un capteur révèle un mur supposé ouvert, le robot l’enregistre — des deux côtés de l’arête partagée — et recalcule le champ de distances. Le plan se corrige lui-même, et le robot continue d’où il est.

Pourquoi la première course n’est pas le plus court chemin

Une surprise courante : le remplissage ne garantit pas le plus court itinéraire à la première course. Parce qu’il a agi sur des hypothèses optimistes, il a trouvé un chemin vers le but, pas forcément le meilleur. Les vrais robots Micromouse utilisent deux phases :

1. Une course d’exploration qui explore assez du labyrinthe pour bâtir une carte précise.
2. Une course de vitesse le long du plus court chemin que la carte complète révèle.

Au début, une exploration efficace compte plus que l’optimalité de la première course.

Remplissage contre BFS et A*

Le parcours en largeur et A* planifient sur un graphe déjà connu. Le remplissage est conçu pour un labyrinthe encore en découverte : il ré-inonde à chaque nouveau mur. Mathématiquement, l’inondation est un calcul de distances en largeur — la différence est que le remplissage s’attend à ce que la carte continue de changer et qu’il est bon marché à recalculer.

Il bat aussi le simple suivi de mur (gardez toujours une main sur un mur), qui ne peut atteindre un but au centre du labyrinthe et trouve rarement un itinéraire court.

La boucle détection-planification-mouvement

void planOneCell(Maze& map, Robot& robot) {
  map.observe(robot.cell(), robot.senseLeftFrontRight());
  map.floodFill(centerGoals);
  Cell next = map.bestDescendingNeighbor(robot.cell());
  robot.turnAndMoveTo(next);
}

Gardez la détection, la cartographie, la planification et le mouvement en étapes séparées. Cette frontière permet au même planificateur de tourner dans un simulateur de navigateur, sur votre bureau, et sur un ESP32 avec de vrais capteurs de distance et encodeurs.

L’inondation, en entier

Le champ de distances est une expansion en largeur depuis le but, et elle est assez courte pour s’écrire complètement :

const uint8_t N = 16;                       // 16 x 16 maze
uint8_t dist[N][N];                         // distance to goal, per cell
uint8_t walls[N][N];                        // bitmask: 1=N, 2=E, 4=S, 8=W

// A simple ring buffer beats a std::queue on a microcontroller.
uint8_t queueR[N * N], queueC[N * N];

void floodFill(const uint8_t goals[][2], uint8_t goalCount) {
  memset(dist, 255, sizeof(dist));          // 255 = unreachable

  uint16_t head = 0, tail = 0;
  for (uint8_t g = 0; g < goalCount; g++) {
    const uint8_t r = goals[g][0], c = goals[g][1];
    dist[r][c] = 0;
    queueR[tail] = r; queueC[tail] = c; tail++;
  }

  const int8_t dr[4] = {-1, 0, 1, 0};       // N, E, S, W
  const int8_t dc[4] = { 0, 1, 0, -1};

  while (head < tail) {
    const uint8_t r = queueR[head], c = queueC[head];
    head++;

    for (uint8_t d = 0; d < 4; d++) {
      if (walls[r][c] & (1 << d)) continue;             // wall in the way

      const int8_t nr = r + dr[d], nc = c + dc[d];
      if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;

      if (dist[nr][nc] > dist[r][c] + 1) {              // 255 means unvisited
        dist[nr][nc] = dist[r][c] + 1;
        queueR[tail] = nr; queueC[tail] = nc; tail++;
      }
    }
  }
}

Voilà tout l’algorithme. Sur un labyrinthe 16×16 il visite au plus 256 cases et tourne en bien moins d’une milliseconde sur un Arduino — et c’est pourquoi ré-inonder à chaque mur nouvellement découvert est tout à fait abordable, et pourquoi personne ne s’embête avec des mises à jour incrémentales.

Enregistrer un mur des deux côtés

Le bogue de remplissage le plus courant n’est pas du tout dans l’inondation. Un mur est partagé entre deux cases, et l’enregistrer d’un seul côté produit une carte où le robot peut le traverser dans un sens et pas dans l’autre :

void setWall(uint8_t r, uint8_t c, uint8_t dir) {
  walls[r][c] |= (1 << dir);

  const int8_t dr[4] = {-1, 0, 1, 0};
  const int8_t dc[4] = { 0, 1, 0, -1};
  const int8_t nr = r + dr[dir], nc = c + dc[dir];
  if (nr < 0 || nr >= N || nc < 0 || nc >= N) return;

  walls[nr][nc] |= (1 << ((dir + 2) % 4));   // the same wall, from the other side
}

Le (dir + 2) % 4 est la direction opposée — nord devient sud, est devient ouest. Le symptôme d’une erreur ici est un robot qui planifie un itinéraire droit à travers un mur qu’il a lui-même enregistré, ce qui est vraiment déroutant à regarder.

La mémoire, sur un Arduino

Un labyrinthe 16×16 dans les 2 Ko de SRAM d’un Uno est serré mais jouable, et l’arithmétique vaut d’être faite avant de l’apprendre à vos dépens :

La file est la partie chère et la plus facile à réduire : un seul tableau d’octets tassés r<<4|c la divise par deux à 256 B. Si c’est encore serré, tasser la carte des murs à 2 bits par case récupère 192 B de plus. La plupart atteignent à ce stade un ESP32 ou un Mega à la place, et c’est un choix raisonnable — mais l’exercice de le faire tenir est instructif en soi.

Choisir les cases du but

Un but Micromouse standard est un bloc 2×2 au centre, pas une case unique, et ce n’est pas un détail. Amorcer les quatre cases avec la distance 0 signifie que le robot vise la face du bloc la moins chère à atteindre — ce qui est à la fois plus rapide et plus robuste que de s’engager sur une case précise qu’il faudrait peut-être aborder depuis une direction gênante.

Le code ci-dessus le gère déjà : passez les quatre cases dans goals, et l’inondation part de chacune simultanément. C’est un vrai avantage de l’approche par champ de distances — des buts multiples ne coûtent rien, tandis qu’A* exigerait une heuristique modifiée.

Explorer proprement

Le remplissage dit au robot où aller étant donné ce qu’il sait. Il ne dit rien de ce qu’il devrait apprendre, et un robot qui ne fait que descendre le gradient atteindra le but sans avoir vu l’essentiel du labyrinthe — ce qui fait du « plus court chemin » de la course de vitesse le plus court seulement parmi les couloirs qu’il a parcourus par hasard.

Le compromis usuel en compétition est la deuxième ou troisième ligne : atteignez le but, puis inondez en retour vers le départ et roulez cela, ce qui révèle naturellement un autre ensemble de couloirs. Deux traversées produisent typiquement une carte assez bonne pour que la course de vitesse soit à quelques pour cent de l’optimal.

Dépannage

Cette cinquième ligne est la plus importante, et elle vaut d’être dite plainement : l’algorithme n’est pas la partie dure d’un Micromouse. Le remplissage fait quarante lignes et vous pouvez le vérifier complètement dans le simulateur sans matériel. La partie dure est qu’après dix cases le robot n’est plus où il croit être, et un plan parfait exécuté depuis une position fictive fonce dans un mur.

Essayez vous-même

Avancez pas à pas dans le simulateur de résolution de labyrinthe case par case et regardez le champ de distances se recalculer chaque fois que le robot découvre un mur. Voir les nombres changer est la façon la plus rapide de comprendre pourquoi le robot a toujours un plan.