Simulateur de labyrinthe de ligne avec routage LSRB

Commandes

Mode choisit entre le parcours complet en trois actes — exploration, simplification, puis parcours à toute vitesse — et l’accès direct à l’itinéraire final. Run speed règle la vitesse de roulage du robot. Start, Pause et Step le pilotent en continu ou un mouvement par un, Reset rejoue le même labyrinthe, et New maze en génère un nouveau. Placez le focus sur le canevas et utilisez Espace, N, R, M et F pour les mêmes commandes au clavier.

Le bandeau route memory sous le labyrinthe est la partie à regarder. Il se remplit d’un symbole par mouvement pendant que le robot roule, puis se réécrit pendant la phase de simplification à chaque déclenchement d’une substitution.

Théorie

Un robot de labyrinthe de ligne est construit en deux couches, et les garder séparées est ce qui le rend traitable.

La couche basse est un suiveur de ligne ordinaire. Une barrette de réflectance à huit voies lit le ruban, les mesures se réduisent en une seule erreur pondérée, et une boucle PID transforme cette erreur en deux vitesses de roues différentes. Cette couche ignore tout des labyrinthes.

La couche haute ne se réveille que lorsque le ruban se ramifie. Elle classe la jonction — gauche, droite, T, carrefour, impasse ou arrivée — choisit une branche par la règle de la main gauche, et ajoute un caractère à une chaîne. La barre dessinée sur le nez du robot dans ce simulateur est cette barrette, et vous pouvez voir tout un côté s’allumer quand une branche s’ouvre.

Le piège est que la lecture instantanée est ambiguë. Une jonction en T, un carrefour et le bloc d’arrivée annoncent tous tous les canaux au noir. Le robot doit s’engager au-delà de la jonction et relire avant de savoir ce qu’il vient de traverser.

Algorithme

L’exploration utilise la règle de la main gauche : à chaque case, prenez l’option la plus à gauche disponible, et ne faites demi-tour que lorsqu’une impasse ne laisse rien d’autre. Sur un labyrinthe sans boucles, cela atteint toujours l’arrivée, et c’est assez sans état pour être vérifié à la main.

Chaque mouvement ajoute un symbole. L, S et R sont des virages ; B n’apparaît qu’aux endroits où le robot est ressorti d’une impasse en marche arrière. Chaque B dans la chaîne finale marque donc une erreur, avec le virage d’avant et le virage d’après.

Cette fenêtre de trois caractères est toujours remplaçable par un seul virage, car les trois mouvements sont simplement des angles qui s’additionnent. En comptant gauche comme −90°, tout droit comme 0°, droite comme +90° et demi-tour comme 180°, L B L totalise 0°, soit S — traversez tout droit au lieu d’entrer dans l’éperon. Les six règles de substitution sont ce calcul, tabulé.

Un seul passage ne suffit pas : réduire un détour peut rapprocher deux virages qui forment désormais une nouvelle fenêtre réductible, donc les règles sont appliquées à répétition jusqu’à ce que plus rien ne change. Quand la boucle se termine, il ne reste aucun B dans la chaîne, ce qui est la preuve que c’est fini — toute impasse restante en montrerait encore un.

Code source

// Repeat until a full pass changes nothing: collapsing one detour
// can push two turns together that are themselves reducible.
void simplify(String& route) {
  bool changed = true;
  while (changed) {
    changed = false;
    for (int i = 1; i + 1 < route.length(); i++) {
      if (route[i] != 'B') continue;          // windows centre on a turn-back
      route = route.substring(0, i - 1)
            + fold(route[i - 1], route[i + 1])
            + route.substring(i + 2);
      changed = true;
      break;
    }
  }
}

fold est la table de substitution, et elle est courte car ce n’est que de l’arithmétique d’angles : additionnez les deux virages de part et d’autre du demi-tour à 180°, ramenez dans ±180°, et reconvertissez le résultat en symbole.

Hypothèses et différences avec le matériel

Le ruban est rendu comme un noir parfait sur un blanc parfait, sans gondolage, reflet ni ombre, et la barrette de réflectance rend compte de valeurs binaires idéales à hauteur fixe. Une vraie barrette IR voit des réflexions en niveaux de gris qui varient avec la lumière ambiante, la hauteur des capteurs et l’usure du ruban, donc chaque essai sur matériel doit d’abord étalonner le blanc et le noir par balayage comme l’indique la section de câblage. Le simulateur fait aussi tourner la boucle PID à une période parfaite et avance d’une case nette par décision ; sur un Arduino, la gigue de boucle, le patinage des roues et un écart de montage de 2 mm apparaissent comme des erreurs de classification des jonctions. Traitez les gains et la chaîne LSRB d’ici comme la logique à transférer, pas comme des nombres à copier.

Schéma de câblage

Le robot modélisé par ce labo est celui du parcours de construction du solveur de labyrinthe de ligne : un Arduino Nano lisant une barrette de réflectance à huit voies sur ses broches analogiques, et pilotant deux moto-réducteurs via un TB6612FNG.

La règle de câblage qui compte le plus est la séparation des alimentations. La batterie des moteurs atteint la broche VM du pont et rien d’autre ; le 5 V de l’Arduino n’alimente que la logique ; et toutes les masses — carte, pont, barrette de capteurs, moins de la batterie — doivent être reliées entre elles, sinon les signaux de commande n’ont aucune référence et la panne est silencieuse.