Simulatie van dekkingspadplanning voor robotstofzuigers

Bediening

Strategie wisselt tussen de drie. De kamer wordt opnieuw opgebouwd en de rit start onmiddellijk opnieuw, want een dekkingscijfer betekent pas iets naast de kamer waarin hij is gemeten.

Sleep een willekeurig meubelstuk met de aanwijzer, of druk op 1–4 om er een te kiezen en verplaats het met de pijltoetsen. De rit start opnieuw zodra je sleept. Zet een tafel in het midden van de vloer en zie de afstand van de geplande veeg oplopen terwijl de dekking daalt.

Nieuwe kamer strooit het meubilair opnieuw. Simulatiesnelheid ruilt gladheid tegen geduld — de willekeurige strategie heeft enkele duizenden zetten nodig, dus begin hem op snel.

Theorie

Een padplanner beantwoordt hoe kom ik daar. Een dekkingsplanner beantwoordt hoe raak ik alles aan, en die twee hebben vrijwel niets gemeen.

De enige eerlijke maatstaf is de afstand die een perfecte robot nodig zou hebben. Bij een vloer met oppervlakte A en een borstel van breedte w kost elke tegel één keer vegen zonder herhaling:

d_optimal = A / w

Alles wat het lab rapporteert is een veelvoud van dat getal. Een strategie op 1,2× besteedt 20% van haar leven aan vloer die ze al heeft gedaan; een op 8× besteedt zeven achtsten.

Willekeurig stuiteren heeft een gesloten vorm, en die is niet bemoedigend. Een robot zonder kaart bedekt nieuwe vloer naar rato van hoeveel er nog ongedekt is, dus het ongedekte oppervlak neemt exponentieel af:

covered(d) ≈ 1 − e^(−d / d_optimal)

Dat is de stippellijn in de grafiek. Lees er drie punten af: 63% van de vloer na één optimale afstand, 90% na 2,3, en 99% na 4,6. De laatste tiende van de kamer kost tweemaal zoveel als de eerste driekwart — het couponverzamelaarsprobleem, met een borstel.

Systematische dekking is lineair, dus hij eindigt op 1× plus de overhead die de rijafstand en de bochten kosten. In dit lab is die overhead ongeveer 35%.

De gemeten ritten landen dicht bij de theorie, en waar ze ernaast zitten doen ze dat in de richting die je zou verwachten: een echte willekeurige loop bezoekt naburige vloer opnieuw in plaats van te teleporteren, dus hij doet het net slechter dan de onafhankelijke steekproefcurve suggereert.

Algoritme

Willekeurig stuiteren. Rij rechtdoor. Bij een botsing kies je willekeurig een nieuwe richting en controleer je of die vrij is. Dat is het hele verhaal, en het vraagt één bit detectie en helemaal geen geheugen.

Spiraal, dan verplaatsen. Draai met een hoek omgekeerd evenredig met hoe ver je sinds het middelpunt hebt gereisd, dat tekent een uitzettende spiraal. Bij een botsing schiet je een vaste afstand rechtdoor en begin je een nieuwe spiraal. Uitstekend op open vloer — een spiraal heeft nauwelijks overlap — en hopeloos in een rommelige kamer, waar elke spiraal na een paar bochten wordt afgekapt.

Geplande kronkelende veeg. Drie stappen, en de tweede is degene die mensen overslaan:

1. Opblazen. Vergroot elk obstakel met de straal van de robot plus een veiligheidsmarge. Wat overblijft is waar het middelpunt van de robot mag komen.
2. Snijden. Loop de opgeblazen kaart in rijen af op één borstelbreedte van elkaar. Elke rij wordt een of meer vrije stukken.
3. Verbinden. Bezoek de stukken in kronkelende volgorde, en route tussen opeenvolgende stukken met een kortste pad door de vrije ruimte, zodat de robot om de bank heen rijdt in plaats van erin.

Stap 3 is waar de afstandsoverhead vandaan komt, en het is waarom een rommelige kamer een planner harder straft dan een lege.

Broncode

De willekeurige strategie is de eerste die je op een echte robot wilt hebben, want hij werkt met detectie die je al hebt:

// Random-bounce coverage. Two bump switches, no map, no encoders.
const uint8_t BUMP_L = 2, BUMP_R = 3;
const uint16_t CRUISE = 170;      // PWM
unsigned long turnUntil = 0;
int turnDir = 1;

void loop() {
  bool left  = digitalRead(BUMP_L) == LOW;   // switches are active-low with pull-ups
  bool right = digitalRead(BUMP_R) == LOW;

  if (millis() < turnUntil) {                 // still executing a bounce
    drive(turnDir * CRUISE, -turnDir * CRUISE);
    return;
  }

  if (left || right) {
    // Back off first — turning while wedged against a chair leg does nothing.
    reverseFor(320);
    // A random turn between 90 and 270 degrees. The randomness is what stops the
    // robot tracing the same closed loop around the room forever.
    turnDir = right ? -1 : 1;
    turnUntil = millis() + random(420, 1250);
    return;
  }

  drive(CRUISE, CRUISE);
}

De stuiterhoek moet willekeurig zijn. Een vaste spiegeling maakt van de kamer een biljartafel, en een biljartbal op een rechthoekige tafel beschrijft een gesloten pad dat het meeste oppervlak voor altijd mist.

De geplande veeg heeft de opblazen-snijden-verbinden-pass hierboven nodig plus odometrie die goed genoeg is om een rechte rij vast te houden, en dat is een andere klasse robot. Prototipeer hem hier, waar de positie per constructie exact is, voordat je beslist of je hardware het aankan.

Aannames en hardwareverschillen

Het lab geeft de robot perfecte odometrie, een volledig bekende kaart, omslag zonder vertraging en een borstel die een zuivere cirkel bestrijkt. Een echte machine heeft daar geen van alle.

Wielslip en gyroscoopdrift buigen de rijen na ongeveer tien uit elkaar, en daarom lokaliseren commerciële robots zich opnieuw tegen muren, plafondkenmerken of een baken. Bochten kosten tijd waarvoor dit lab geen afstand rekent. En de borstel bestrijkt geen cirkel — hij bestrijkt een rechthoek achter de robot, dus achteruit rijden over vloer die je al hebt gedaan reinigt niets.

Het verschil tussen de strategieën overleeft dat allemaal. Als een planner willekeurig stuiteren hier met 3× verslaat, verslaat hij het op echte hardware misschien met 2×; de volgorde verandert niet.

Schakelschema

De detectie valt netjes uiteen in drie taken, en alleen de eerste is verplicht.

Bumper. Twee microschakelaars op een veerbelaste voorbumper, met active-low bedraad naar pinnen die interrupts kunnen verwerken en met de interne pull-ups aan. Dit is de detectie die willekeurig stuiteren mogelijk maakt en het is het laatste dat uitvalt.

Afgrond. Naar beneden gerichte reflectiesensoren op de voorhoeken, elke lusdoorgang uitgelezen. Een dekkingsrit bezoekt alles, en dat is inclusief de top van de trap — de rekensom voor hoe ver de robot voorbij de rand rijdt voordat hij kan stoppen staat hier uitgerekend.

Positie. Kwadratuurencoders op beide wielen, en een gyroscoop als je rijen evenwijdig wilt houden. Alleen de geplande strategie heeft dit nodig, en die behoefte is de hele reden dat de andere twee bestaan.

Voor de dekkingsstrategieën als bouwproject zie je de kamerdekkingsrobot; voor de reactieve laag eronder behandelt de simulatie van obstakelvermijding de stopdrempels en het aftasten.