Construire un Micromouse : solveur de labyrinthe

Ce que vous construisez

Un robot déposé dans un labyrinthe jamais vu, qui trouve le centre, puis revient par l’itinéraire le plus court dont il peut prouver l’existence.

Cette seconde moitié fait d’une Micromouse un robot différent de tous les autres de ce site. Un suiveur de ligne réagit. Un éviteur d’obstacles réagit. Une Micromouse se souvient — elle construit une carte en roulant, puis planifie à travers des cellules non visitées. C’est le plus petit problème de robotique complet : perception, mouvement, cartographie et planification, qui doivent tous marcher à la fois.

La stratégie en deux manches

Les souris de compétition ont plusieurs manches et sont notées sur la plus rapide. Cela produit une stratégie à copier même quand personne ne vous chronomètre :

Manche un — explorez. Roulez prudemment, enregistrez quelles cellules ont quels murs, et atteignez le centre. La vitesse est sans importance ; la carte est le produit.

Manche deux — exploitez. Remplissez la carte finie, calculez l’itinéraire le plus court, et roulez-le sans vous arrêter pour capter ce que vous savez déjà.

La division compte car les deux manches veulent des opposés. L’exploration veut un mouvement lent et prudent et une perception constante. La vitesse veut de l’engagement. Tenter les deux à la fois produit un robot mauvais aux deux.

Pourquoi l’algorithme n’est pas la partie dure

Le remplissage par diffusion est vraiment simple : donnez à la cellule objectif la distance 0, donnez à chaque voisine 1 de plus que la plus basse voisine accessible, puis descendez toujours vers un nombre plus petit. Ce sont quelques dizaines de lignes et c’est prouvé le plus court sur une grille.

La partie dure est qu’il suppose que le robot sait dans quelle cellule il est.

Comptez une cellule de travers, ou tournez à 88° au lieu de 90° quelques fois, et le planificateur résout désormais le labyrinthe pour un robot qui est ailleurs. Le symptôme rend fou : l’algorithme est parfait, le câblage est bon, et le robot fonce avec assurance dans un mur.

L’ordre de montage ci-dessous consacre donc l’essentiel à l’effort au mouvement, et ajoute le planificateur en dernier. Vous pouvez prouver le planificateur séparément dans le simulateur de labyrinthe, où la position est exacte par construction — ce qui est précisément pourquoi le simuler d’abord vaut le temps.

Nomenclature

Total : environ $70–95, plus le labyrinthe.

Trois capteurs de distance, pas un. Un seul capteur avant oblige le robot à tourner pour regarder, ce qui coûte du temps et — bien pire — introduit une erreur de cap à chaque observation. Trois capteurs fixes permettent au robot de lire les trois murs d’une cellule en un instant, sans bouger. C’est la différence entre une souris qui cartographie de façon fiable et une qui accumule l’erreur à chaque contrôle de mur.

Rappelez-vous que les trois capteurs VL53L0X démarrent sur l’adresse 0x29, donc il faut trois GPIO sur XSHUT pour les allumer un par un et réassigner les adresses — et le refaire à chaque démarrage, car le changement est volatil.

Surveillez la RAM. Un champ de distances 16×16 stocké en uint8_t fait 256 octets, plus une carte de murs, plus une file. Sur les 2 Ko d’un Uno cela tient, mais seulement avec méthode — ce qui est en soi un bon exercice, et une raison pour laquelle beaucoup passent à un ESP32 ici.

Ordre de montage

1 — Obtenez trois lectures de distance propres. Avant, gauche, droite, avec des capteurs temps de vol VL53L0X. Ils partagent un bus I²C et démarrent à la même adresse, donc allumez-les un par un en maintenant les autres en reset et réassignez les adresses au démarrage. Confirmez que chacun lit un mur à distance connue avant de monter quoi que ce soit.

2 — Faites-le rouler droit et tourner carré. C’est le vrai projet. Suivez suivi de mur et virages précis : une boucle PID sur les capteurs latéraux pour rester centré, des virages intégrés au gyro au lieu des comptes codeurs, et un recalage contre un mur avant dès qu’il y en a un. Ne passez pas à la suite tant que le robot ne peut pas faire dix virages en regardant toujours dans le bon sens.

3 — Comptez les cellules de façon fiable. Les codeurs prévoient où devrait être une frontière ; le front descendant d’un mur latéral confirme où elle est vraiment. Quand ils désaccordent, croyez le mur — c’est un repère physique, pas une estimation accumulée.

4 — Enregistrez les murs dans une carte. Deux bits par cellule pour quatre murs, et un labyrinthe 16 × 16 tient en quelques centaines d’octets. Enregistrez ce que vous voyez au fur et à mesure.

5 — Ajoutez le remplissage. Maintenant le planificateur a des données honnêtes. Recalculez les distances dès qu’un mur nouvellement découvert invalide le plan courant — cette replanification est toute la raison d’utiliser le remplissage plutôt qu’une recherche unique.

Notes matérielles importantes

Petit bat rapide. Le robot doit tourner dans une cellule. Un châssis court avec les roues près du centre de rotation pivote proprement ; un long touche les murs à chaque virage, et aucun réglage ne corrige la géométrie.

Le jeu est une erreur de cap. Chaque pivot inverse les moteurs, et un réducteur lâche perd les premiers degrés — environ 0,9° de cap sur une roue 42 mm pour 4° de jeu. Les moteurs N20 à réducteur métallique existent pour cette raison.

Montez les capteurs latéraux légèrement en avant et inclinés. Les pointer droit sur le côté signifie qu’ils ne voient un mur que parfaitement à côté, donc le robot apprend le mur tard. Un petit angle vers l’avant donne à la boucle de commande une anticipation.

Donnez aux capteurs une alimentation stable. Un VL53L0X renvoie des nombres faux mais plausibles sur un rail affaissé plutôt que de tomber en panne franchement — le pire type de défaut, car la carte se remplit de murs inexistants.

À quoi ressemble un bon résultat

Deux de ces lignes méritent l’emphase.

La détection des murs n’a pas de crédit partiel. Un mur mal enregistré corrompt la carte, le remplissage calcule alors un chemin assuré à travers un mur, et la manche de vitesse fonce droit dedans. Il n’y a pas de dégradation gracieuse, et c’est pourquoi la manche d’exploration va lentement.

Les lignes de dérive sont le vrai projet. L’algorithme n’est pas la partie dure — le remplissage fait environ quarante lignes et vous pouvez le tester entièrement dans le simulateur sans aucun matériel. La partie dure est qu’après dix cellules le robot n’est plus là où il croit être, et une souris qui dérive de 20 mm par dix cellules touchera un mur de l’autre côté du labyrinthe. Tout ce qui fait marcher une vraie Micromouse — correction par suivi de mur, virages fusionnés au gyro, calibration des codeurs — existe pour combattre ce seul nombre.

Quand ça tourne mal

Presque chaque entrée de ce tableau est un défaut de mouvement ou de perception plutôt qu d’algorithme. Cette distribution est la chose la plus utile à savoir avant de commencer, car elle dit où passer vos week-ends.

Si vous voulez les idées de cartographie et de planification sans le matériel, le simulateur de labyrinthe exécute la même stratégie en deux phases en navigateur, et le parcours planification et cartographie la prolonge vers A* et SLAM. Pour un premier robot de labyrinthe bien moins cher, le solveur de labyrinthe de lignes utilise du ruban au lieu des murs et n’a besoin d’aucun capteur de distance.