Simulatie van een lijndoolhofoplosser met LSRB-routering

Bediening

Modus kiest tussen de volledige rit in drie bedrijven — verkennen, vereenvoudigen, en daarna in recordtempo — en direct naar de afgewerkte route springen. Simulatiesnelheid stelt in hoe snel de robot rijdt. Starten, Pauzeren en Stap laten hem doorlopend of per zet draaien, Resetten speelt hetzelfde doolhof opnieuw af, en Nieuw doolhof genereert een nieuw doolhof. Focus het canvas en gebruik spatie, N, R, M en F voor dezelfde bediening vanaf het toetsenbord.

De strook met het routegeheugen onder het doolhof is het deel om in de gaten te houden. Hij vult zich met één symbool per zet terwijl de robot rijdt, en herschrijft zichzelf tijdens de vereenvoudigingsfase zodra elke vervanging vuurt.

Theorie

Een lijndoolhofrobot is in twee lagen opgebouwd, en ze gescheiden houden is wat hem hanteerbaar maakt.

De onderste laag is een gewone lijnvolger. Een reflectiesensorarray met acht kanalen leest de tape, de aflezingen vallen samen tot één gewogen fout, en een PID-lus maakt daarvan twee verschillende wielsnelheden. Deze laag weet niets over doolhoven.

De bovenste laag wordt alleen wakker wanneer de tape vertakt. Hij classificeert het kruispunt — links, rechts, T, kruising, doodlopende weg, of eindpunt — kiest een tak met de linkerhandregel, en voegt één teken toe aan een tekenreeks. De balk die in deze simulator over de neus van de robot getekend staat is die array, en je ziet een hele kant oplichten zodra er een tak opent.

Het addertje is dat de directe aflezing dubbelzinnig is. Een T-kruispunt, een kruising en het eindblok melden allemaal elk kanaal zwart. De robot moet voorbij het kruispunt doorrijden en opnieuw aflezen voordat hij weet wat hij net is overgestoken.

Algoritme

Verkennen gebruikt de linkerhandregel: neem op elke cel de meest linkse beschikbare optie, en draai pas terug wanneer een doodlopende weg niets anders laat. In een doolhof zonder lussen bereikt dat altijd het eindpunt, en het is grotendeels toestandsloos genoeg om met de hand te verifiëren.

Elke zet voegt een symbool toe. L, S en R zijn bochten; B verschijnt alleen waar de robot uit een doodlopende weg terugkeerde. Elke B in de afgewerkte tekenreeks markeert dus een fout, samen met de bocht ervoor en de bocht erna.

Dat venster van drie tekens is altijd vervangbaar door een enkele bocht, omdat de drie zetten hoeken zijn die samen een som vormen. Tel links als −90°, rechtdoor als 0°, rechts als +90° en terug als 180°, dan telt L B L op tot 0°, en dat is S — rij in plaats van het zijpad binnen te rijden gewoon rechtdoor. De zes vervangingsregels zijn die rekenkunde, in een tabel gezet.

Eén doorloop is niet genoeg: het invouwen van een omweg kan twee bochten tegen elkaar aan leggen die nu samen een nieuw vereenvoudigbaar venster vormen, dus de regels worden herhaaldelijk toegepast tot er niets meer verandert. Als de lus eindigt is er geen B meer over in de tekenreeks, en dat is het bewijs dat hij klaar is — elke overgebleven doodlopende weg zou er nog een laten zien.

Broncode

// 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 is de vervangtabel, en hij is kort omdat het alleen hoekrekenkunde is: tel de twee bochten aan weerszijden van de omkering van 180° bij elkaar op, wikkel het naar ±180°, en map het resultaat terug op een symbool.

Aannames en hardwareverschillen

Tape wordt getekend als perfect zwart op perfect wit zonder krulling, schittering of schaduw, en de reflectiesensorarray meldt ideale binaire waarden op vaste hoogte. Een echte IR-array ziet grijsschaalreflecties die meebewegen met het omgevingslicht, de sensorhoogte en slijtage van de tape, dus elke hardwarerit moet eerst op wit en zwart ijken, zoals de bedradingssectie stelt. De simulator draait de PID-lus ook op een perfecte periode en zet per beslissing één schone cel voor; op een Arduino verschijnen lusjitter, wielslip en een montageoffset van 2 mm als verkeerd geclassificeerde kruispunten. Behandel de versterkingen en de LSRB-tekenreeks hier als de logica om over te nemen, niet als getallen om te kopiëren.

Schakelschema

De robot die dit lab modelleert is die uit het bouwpad van de lijndoolhofoplosser: een Arduino Nano die op zijn analoge pinnen een reflectiesensorarray met acht kanalen uitleest en twee kastmotoren aanstuurt via een TB6612FNG.

De bedradingsregel die het zwaarst weegt is de voedingsscheiding. De motoraccu bereikt de VM-pin van de besturing en niets anders; de 5 V van de Arduino voedt alleen de logica; en alle massa’s — bord, besturing, sensorarray, accuminus — moeten met elkaar verbonden zijn, anders hebben de regelsignalen geen referentie en is de storing stil.