Détecter les intersections d'un labyrinthe de lignes

Un suiveur de ligne a un seul travail : garder la ligne centrée. Un robot de labyrinthe de lignes en a deux, et c’est le second qui bloque les débutants. Il doit toujours suivre la ligne, mais il doit aussi remarquer les moments où la ligne offre un choix — et décider de quelle sorte de choix il s’agit.

Cette couche de décision se tient au-dessus de la boucle PID, pas dedans. Le contrôleur ne doit jamais savoir ce qu’est un labyrinthe. Il braque vers une ligne ; la couche des intersections observe les mêmes lectures de capteurs pour y guetter les motifs qui signifient « quelque chose a changé » et prend la main quand l’un apparaît.

Six choses qu’une intersection peut être

Chaque intersection d’un labyrinthe de lignes adhésives se réduit à l’un des six cas. Avec une barrette de réflectance à 8 voies lisant 1 pour l’adhésif noir et 0 pour le support blanc, chacun produit une signature :

• Virage à gauche seul — les capteurs extérieurs gauches passent au noir pendant que le côté droit reste blanc.
• Virage à droite seul — l’image miroir.
• Intersection en T — l’adhésif couvre toute la largeur, sans rien devant.
• Carrefour — l’adhésif couvre toute la largeur, et la ligne continue devant.
• Impasse — chaque capteur lit blanc ; la ligne s’est simplement arrêtée.
• Arrivée — un bloc plein rempli, large et long, qui reste noir à mesure qu’on roule dedans.

La lecture seule est ambiguë

Regardez l’intersection en T, le carrefour et le marqueur d’arrivée. Les trois rapportent 11111111. Une branche à gauche où la ligne continue aussi tout droit rapporte la même chose qu’un simple virage à gauche.

C’est le point à intérioriser : le motif instantané des capteurs ne peut pas classer une intersection. Un robot qui décide dès que ses capteurs extérieurs passent au noir tournera avec assurance à gauche à un carrefour qu’il aurait dû traverser tout droit.

Le correctif est le mouvement, pas plus de capteurs. Quand la barrette signale d’abord un large motif noir :

1. Notez quel côté (ou quels côtés) est passé au noir — c’est l’ensemble des branches disponibles.
2. Continuez d’avancer d’environ une longueur de robot.
3. Relisez. Si les capteurs du centre voient toujours l’adhésif, tout droit était aussi une option. Si tout est blanc, c’était un T. Si tout est encore noir, vous avez roulé dans le bloc d’arrivée.

Alors seulement vous savez quel genre d’intersection vous avez laissée derrière, et alors seulement la couche labyrinthe peut choisir.

Junction classify(Sensors& s) {
  Branches at = s.readWideBranches();      // left / right seen on arrival
  driveForward(ONE_ROBOT_LENGTH);          // commit past the intersection
  Reading after = s.read();

  if (after.allBlack())  return FINISH;    // still on tape = solid block
  at.straight = after.centreOnLine();      // line continued through
  return at.toJunction();
}

Notez que le classifieur roule. C’est inhabituel pour une fonction de détection et c’est le propos — le type d’intersection est une propriété d’une courte trajectoire, pas d’un seul échantillon.

Choisir une branche

Une fois une intersection classée, la couche labyrinthe choisit une branche selon une règle fixe. La règle de la main gauche — toujours prendre la branche disponible la plus à gauche, et faire demi-tour dans une impasse — est le choix standard parce qu’elle est sans état, exhaustive sur un labyrinthe sans boucles, et triviale à vérifier à la main.

La cohérence compte plus que l’astuce ici. Un robot qui préfère toujours la gauche finira par visiter chaque branche atteignable, et le relevé de ses virages est ce que l’étape de simplification d’itinéraire réduira plus tard en trajet optimal. Regardez ce même comportement explorer-puis-optimiser tourner dans le simulateur de résolution de labyrinthe — celui-là détecte des murs plutôt que de l’adhésif, mais la couche de décision au-dessus de la détection est identique.

La barrette doit être plus large que la ligne

La détection d’intersections pose une question précise au capteur : les voies extérieures sont-elles passées au noir pendant que le centre est encore sur la ligne ? Une barrette à peine plus large que l’adhésif ne peut physiquement pas y répondre.

   left branch                    8-channel array, ~60 mm wide
   ────────────────┐          [ 1 1 1 0 0 0 0 0 ]   outer left black -> a branch exists
                   │
   ════════════════╪═══════   [ 0 0 0 1 1 0 0 0 ]   centre still on the line
                   │

La règle empirique est trois fois la largeur de l’adhésif. Plus étroit et le robot ne peut pas distinguer « la ligne a tourné sec » de « la ligne a bifurqué » — qui est la décision centrale sur laquelle repose tout le projet. Une barrette à 8 voies au pas de 8 mm donne environ 60 mm, et c’est pourquoi c’est le choix standard pour de l’adhésif de 19 mm.

Anti-rebond d’une intersection

La barrette traverse une intersection sur plusieurs itérations de boucle, et chacune est une lecture fraîche. Un classifieur qui se déclenche sur le premier large motif se déclenchera souvent deux ou trois fois pour une intersection, remplissant le trajet enregistré de caractères qui n’étaient jamais de vrais virages.

const uint8_t CONFIRM_SAMPLES = 3;      // consecutive readings that must agree
const unsigned long JUNCTION_DEADTIME_MS = 300;

uint8_t agreeCount = 0;
uint8_t lastPattern = 0;
unsigned long lastJunctionAt = 0;

bool junctionDetected(uint8_t pattern) {
  // Ignore everything for a short while after committing to one.
  if (millis() - lastJunctionAt < JUNCTION_DEADTIME_MS) return false;

  if (pattern == lastPattern) agreeCount++;
  else { lastPattern = pattern; agreeCount = 1; }

  if (agreeCount >= CONFIRM_SAMPLES && isWide(pattern)) {
    lastJunctionAt = millis();
    agreeCount = 0;
    return true;
  }
  return false;
}

Dimensionner le temps mort est un vrai compromis, et il vaut la peine de le faire avec des nombres plutôt qu’au feeling :

deadtime < (minimum spacing between junctions) / speed

À 0,2 m/s avec des intersections espacées d’au moins 15 cm, cela fait 750 ms de marge — donc 300 ms est sûr. Rouler à 0,5 m/s dans un labyrinthe espacé de 10 cm fait tomber le budget à 200 ms, et c’est pourquoi l’exploration roule lentement. Cette contrainte, pas l’algorithme, fixe la vitesse d’exploration.

Le virage lui-même

Classer l’intersection est la moitié du travail ; exécuter le virage sans perdre la ligne est l’autre moitié, et un virage à angle fixe est la mauvaise façon de le faire.

void turnUntilLine(int direction) {
  pivot(direction);
  delay(120);                        // clear the junction's own tape first
  while (!centreOnLine()) {          // then rotate until the new line appears
    if (millis() - startedAt > TURN_TIMEOUT_MS) { stopMotors(); fault(); return; }
  }
  stopMotors();
}

Le delay(120) compte. Juste après le début du virage, les capteurs du centre sont encore sur l’adhésif propre de l’intersection, donc un naïf « tourne jusqu’à voir la ligne » s’arrête instantanément et le robot ne tourne jamais du tout. Dégagez d’abord l’intersection, puis cherchez.

Le délai maximal compte aussi : sans lui, un robot qui dépasse la branche — parce qu’il allait trop vite, ou que la branche était mal détectée — tourne indéfiniment.

La classification complète, avec le tout-droit résolu

En mettant l’anti-rebond, le dépassement en roulant et le virage ensemble :

Junction classifyAndTurn() {
  const Branches at = readWideBranches();     // left and/or right, on arrival

  driveForward(ONE_ROBOT_LENGTH);             // commit past the intersection
  const Reading after = read();

  if (after.allBlack()) return FINISH;        // still on tape = the solid block

  Junction j;
  j.left     = at.left;
  j.right    = at.right;
  j.straight = after.centreOnLine();          // resolved only by moving

  if (!j.left && !j.right && !j.straight) return DEAD_END;
  return j;
}

Le classifieur roule, ce qui est inhabituel pour une fonction de détection et fait tout le propos : le type d’intersection est une propriété d’une courte trajectoire, pas d’un seul échantillon. Trois des six cas — T, carrefour et arrivée — sont indiscernables à l’instant d’arrivée.

Le tester sans labyrinthe

Pas besoin d’un labyrinthe pour vérifier cette couche, et en construire un avant que la détection fonctionne est une façon courante de perdre une soirée. Posez une intersection de chaque type sur une planche et faites rouler le robot sur chacune à tour de rôle, en affichant la classification :

Le test de la courbe douce est celui qui attrape le plus de bogues, et c’est celui auquel personne ne pense. Une courbe serrée met un instant plusieurs capteurs extérieurs sur l’adhésif, ce qui ressemble exactement à une branche. Si votre robot invente des intersections dans les courbes, le correctif est d’exiger que les capteurs extérieurs restent noirs sur une distance minimale, pas juste un nombre minimal d’échantillons — une courbe les relâche vite, une vraie branche non.

Dépannage

Le fiabiliser sur du vrai adhésif

Trois choses cassent la détection d’intersections sur le matériel bien plus souvent que l’algorithme :

• Dérive d’étalonnage. Faites passer le balayage d’étalonnage de la barrette sur l’adhésif noir et le support blanc à chaque mise sous tension, et recommencez en changeant de pièce. L’infrarouge ambiant du soleil et des néons change les lectures.
• Hauteur des capteurs. 5–8 mm au-dessus du sol. Trop haut et le contraste s’effondre ; trop bas et un support légèrement voilé racle la barrette.
• Qualité de l’adhésif. Utilisez de l’adhésif de 18–20 mm et faites des intersections physiquement propres. Un coin effiloché se lit comme une branche intermittente, et aucun code ne corrige un adhésif qui vous ment.

Stabilisez d’abord le simple suivi de ligne sur un ovale simple — réglez-le dans le simulateur de suiveur de ligne, puis sur du vrai adhésif. Un labyrinthe masquera des problèmes mécaniques et de capteurs derrière ce qui ressemble à un bogue de logique.