Bouw een micromouse: robot die doolhoven oplost met flood fill

Wat je bouwt

Een robot die in een doolhof wordt gezet dat hij nog nooit heeft gezien, het midden vindt en daarna terugrijdt over de kortste route die hij kan aantonen te bestaan.

Die tweede helft maakt een micromouse anders dan elke andere robot op deze site. Een lijnvolger reageert. Een obstakelvermijder reageert. Een micromouse onthoudt — hij bouwt een kaart tijdens het rijden en plant daarna over cellen die hij nog niet heeft bezocht. Het is het kleinste volledige robotprobleem: meten, bewegen, karteren en plannen, allemaal tegelijk aan de slag.

De strategie met twee ritten

Wedstrijdrobots krijgen meerdere ritten en worden op de snelste gescoord. Dat levert een strategie op die de moeite waard is om over te nemen, ook als niemand de tijd meet:

Rit één — verkennen. Rijd zorgvuldig, leg per cel vast welke muren er staan en bereik het midden. Snelheid is onbelangrijk; de kaart is het product.

Rit twee — benutten. Vul de afstanden in op de voltooide kaart, bereken de kortste route en rijd die af zonder te stoppen om iets te meten wat je al weet.

De splitsing telt, omdat de twee ritten tegengestelde dingen willen. Verkennen vraagt om langzame, voorzichtige beweging en steeds meten. Een snelheidsrit vraagt om moed. Probeer je dat tegelijk, dan krijg je een robot die in geen van beide goed is.

Waarom het algoritme niet het moeilijke deel is

Flood fill is echt eenvoudig: geef de doelcel afstand 0, geef elke buurcel één meer dan de laagste buurcel die hij kan bereiken en stap daarna altijd naar een lager getal. Het zijn een paar tientallen regels en op een raster is het aantoonbaar de kortste route.

Het moeilijke deel is dat het algoritme aanneemt dat de robot weet in welke cel hij zit.

Tel je één cel verkeerd, of draai je een paar keer 88° in plaats van 90°, dan lost de planner de doolhof op voor een robot die ergens anders staat. Het symptoom is frustrerend: het algoritme is volmaakt, de bedrading klopt, en de robot rijdt zelfverzekerd tegen een muer aan.

Daarom besteedt de onderstaande bouwvolgorde de meeste tijd aan bewegen en voegt de planner er als laatste aan. Je kunt de planner los bewijzen in de doolhofsimulator, waar de positie per definitie klopt — en juist daarom is het de moeite waard hem eerst te simuleren.

Onderdelenlijst

Totaal: ongeveer $70–95, plus de doolhof.

Drie afstandssensoren, niet één. Eén sensor voorin dwingt de robot om te draaien om te kijken, en dat kost tijd en — veel erger — bij elke waarneming een richtingsafwijking. Drie vaste sensoren laten de robot alle drie de muren van een cel in één keer aflezen, zonder te bewegen. Dat is het verschil tussen een micromouse die betrouwbaar in kaart brengt en een die bij elke muurcontrole fout ophoopt.

Onthoud dat alle drie de VL53L0X-sensoren opstarten op adres 0x29, dus heb je drie GPIO-pinnen aan XSHUT nodig om ze één voor één op te starten en adressen opnieuw toe te wijzen — en dat bij elke boot te herhalen, want die wijziging verdwijnt zodra de spanning uitvalt.

Let op het RAM. Een 16×16-veld met flood-fill-afstanden opgeslagen als uint8_t is 256 bytes, plus een muurkaart, plus een wachtrij. Op de 2 KB van een Uno past dat, maar alleen als je er bewust mee bezig bent — wat op zich al een goede oefening is, en de reden dat velen hier naar een ESP32 gaan.

Bouwvolgorde

1 — Zorg voor drie zuivere afstandsmetingen. Voor, links en rechts met VL53L0X-time-of-flight-sensoren. Ze delen één I²C-bus en starten op hetzelfde adres, dus start ze één voor één op door de andere in reset te houden en bij het opstarten adressen opnieuw toe te wijzen. Controleer of elke sensor een muur op een bekende afstand ziet voordat je iets monteert.

2 — Laat hem recht rijden en zuiver draaien. Dit is het echte project. Volg muurvolgen en precieze draaien: een PID-regelaar op de zijsensoren om gecentreerd te blijven, draaien met de gyro geïntegreerd in plaats van tellen via encoders, en tegen een voorwand opnieuw rechtzetten zodra die er is. Ga pas verder als de robot tien draaibewegingen aankan en nog steeds de juiste kant op kijkt.

3 — Tel cellen betrouwbaar. Encoders voorspellen waar een grens hoort te liggen; de dalende flank van een zijmuur bevestigt waar die werkelijk ligt. Bij twijfel: geloven de muur — het is een tastbaar oriëntatiepunt, geen opgebouwde schatting.

4 — Leg de muren vast in een kaart. Twee bits per cel voor vier muren, en een 16 × 16-doolhof past in een paar honderd bytes. Leg vast wat je ziet op het moment dat je het ziet.

5 — Voeg flood fill toe. De planner heeft nu eerlijke gegevens. Herbereken de afstanden zodra een nieuw gevonden muur het huidige plan ongeldig maakt — dat herplannen is de hele reden dat flood fill wordt gebruikt in plaats van een eenmalige zoektocht.

Hardwaretips die ertoe doen

Klein wint van snel. De robot moet binnen een cel kunnen draaien. Een compact chassis met de wielen dicht bij het draaipunt wentelt netjes; een lang chassis raakt bij elke draai muren, en geen hoeveelheid afstemming repareert de geometrie.

Speling is een richtingsafwijking. Elke draai op de plek keert de motoren om, en een losse tandwielkast verliest de eerste graden — ongeveer 0,9° richtingsafwijking bij een wiel van 42 mm en 4° speling. N20-motoren met metalen tandwielkast bestaan om precies die reden.

Monteer de zijsensoren iets naar voren en schuin. Recht naar buiten wijzen betekent dat ze een muur pas zien als die precies naast ze ligt, dus de robot ontdekt die muur pas laat. Een kleine voorwaartse hoek geeft de regellus vooruitinformatie.

Geef de sensoren een stabiele voeding. Bij een instabiele voeding kan een VL53L0X plausibele maar onjuiste waarden teruggeven in plaats van duidelijk te falen — het slechtste soort storing, want de kaart vult zich dan met muren die er niet zijn.

Hoe goed het eruit moet zien

Twee van die rijen verdienen nadruk.

Muurdetectie kent geen gedeeltelijke score. Eén verkeerd vastgelegde muur bederft de kaart, flood fill rekent daarna zelfverzekerd een route dwars door die muur, en de snelheidsrit rijdt er pal tegenaan. Er is geen nette terugval, en daarom rijdt de verkenningsrit langzaam.

De drift-rijen zijn het echte project. Het algoritme is niet het moeilijke deel — flood fill is zo’n veertig regels en je kunt het volledig testen in de simulator helemaal zonder hardware. Het moeilijke deel is dat de robot na tien cellen niet meer staat waar hij denkt te staan, en een micromouse die 20 mm per tien cellen afdrijft, raakt aan de overkant van de doolhof een muur. Al het andere dat een echte wedstrijdrobot laat werken — correctie tijdens het muurvolgen, draaien met gyrofusie, encoderkalibratie — bestaat om dat ene getal te bestrijden.

Wat er misgaat

Vrijwel elke regel in die tabel is een fout in beweging of waarneming, niet in het algoritme. Die verdeling is het belangrijkste dat je vóór het begin weet, want ze vertelt je waar je je weekends aan moet besteden.

Wil je de ideeën over karteren en plannen zonder de hardware, dan voert de doolhofsimulator dezelfde strategie in twee fasen in de browser uit, en de leerroute voor padplanning en kartering voert die door naar A* en SLAM. Een veel goedkopere eerste doolhofrobot is de lijndoolhofrobot: die gebruikt tape in plaats van muren en heeft helemaal geen afstandssensoren nodig.