Simulatore di copertura per robot aspirapolvere

Controlli

Strategia passa da una all’altra. La stanza viene ricostruita e l’esecuzione riparte immediatamente, perché un valore di copertura ha significato qualcosa solo per la stanza in cui è stato misurato.

Trascina un qualsiasi mobile con il puntatore oppure premi 1–4 per selezionarne uno e spostarlo con i tasti freccia. L’esecuzione riparte mentre lo trascini. Metti un tavolo al centro del pavimento e guarda aumentare la distanza della spazzata pianificata mentre diminuisce la copertura.

Nuova stanza distribuisce di nuovo i mobili. Velocità di esecuzione scambia morbidezza e pazienza — la strategia casuale ha bisogno di diverse migliaia di mosse per terminare, quindi iniziala ad alta velocità.

Teoria

Un pianificatore di percorso risponde alla domanda come arrivo lì. Un pianificatore di copertura risponde alla domanda come li tocco tutti, e i due hanno quasi nulla in comune.

L’unico metro onesto è la distanza che servirebbe a un robot perfetto. Con un pavimento di area A e una spazzola di larghezza w, coprire ogni quadrato una sola volta senza ripetizioni richiede:

d_optimal = A / w

Tutto ciò che il laboratorio riporta è un multiplo di quel numero. Una strategia a 1.2× impiega il 20% della propria vita a ripercorrere un pavimento già fatto; una a 8× ne impiega sette ottavi.

Il rimbalzo casuale ha una forma chiusa, e non è incoraggiante. Un robot senza mappa copre il nuovo pavimento in proporzione a quanto è ancora scoperto, quindi l’area non coperta decade esponenzialmente:

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

Questa è la curva tratteggiata nel grafico. Leggi tre punti: il 63% del pavimento dopo una distanza ottimale, il 90% dopo 2.3 e il 99% dopo 4.6. L’ultimo decimo della stanza costa il doppio dei primi tre quarti — il problema del collezionista di coupon, con una spazzola.

La copertura sistematica è lineare, quindi termina a 1× più il sovraccarico dovuto alla spaziatura delle file e alle inversioni. In questo laboratorio il sovraccarico è di circa il 35%.

Le esecuzioni misurate restano vicine alla teoria e, quando se ne discostano, lo fanno nella direzione prevista: una vera camminata casuale rivisita il pavimento vicino invece di teletrasportarsi, quindi è leggermente peggiore di quanto suggerisca la curva di campionamento indipendente.

Algoritmo

Rimbalzo casuale. Guidare dritti. In caso di urto scegliere a caso una nuova direzione e verificare che sia libera. È tutto, e richiede un solo bit di percezione e nessuna memoria.

Spirale, poi spostamento. Ruotare di un angolo inversamente proporzionale alla distanza percorsa dal centro: si traccia così una spirale in espansione. In caso di urto, avanzare rettilineo per una distanza fissa e iniziare una nuova spirale. Eccellente su un pavimento aperto — una spirale ha quasi nessuna sovrapposizione — e impotente in una stanza affollata, dove ogni spirala viene interrotta dopo pochi giri.

Spazzata serpentina pianificata. Tre passaggi, e il secondo è quello che le persone saltano:

1. Gonfiare. Ingrandire ogni ostacolo del raggio del robot più un margine di sicurezza. Ciò che rimane è dove può andare il centro del robot.
2. Affettare. Percorrere la mappa gonfiata a file distanti una larghezza di spazzola. Ogni file diventa uno o più tratti liberi.
3. Unire. Visitare i tratti in ordine serpentino e collegare tratti consecutivi con il percorso più breve attraverso lo spazio libero, così il robot passa attorno al divano invece che dentro.

Il passaggio 3 è l’origine del sovraccarico in distanza ed è il motivo per cui una stanza affollata penalizza un pianificatore più di una vuota.

Codice sorgente

La strategia casuale è quella che vale la pena avere per prima su un robot reale, perché funziona con la percezione che hai già:

// 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);
}

L’angolo di rimbalzo deve essere casuale. Una riflessione fissa trasforma la stanza in un tavolo da biliardo e una palla da biliardo su un tavolo rettangolare traccia un percorso chiuso che manca quasi sempre la maggior parte della superficie per sempre.

La spazzata pianificata richiede il passaggio gonfia-affetta-unisci descritto sopra e un’odometria abbastanza buona da mantenere una file dritta, che è una classe di robot diversa. Prototipala qui, dove la posizione è esatta per costruzione, prima di decidere se il tuo hardware può sostenerla.

Ipotesi e differenze hardware

Il laboratorio dà al robot un’odometria perfetta, una mappa perfettamente nota, rotazioni istantanee sul posto e una spazzola che copre un cerchio pulito. Una macchina reale non ha nulla di tutto questo.

Lo slittamento delle ruote e la deriva del giroscopio separano le file entro circa dieci, ed è per questo che i robot commerciali si rlocalizzano rispetto a pareti, elementi del soffitto o un segnalatore. Le inversioni richiedono tempo, che questo laboratorio addebita come distanza zero. E la spazzola non copre un cerchio: copre un rettangolo dietro il robot, quindi tornare indietro sul pavimento già fatto non pulisce nulla.

La differenza tra le strategie sopravvive a tutto questo. Se qui un pianificatore batte il rimbalzo casuale di 3×, su hardware reale lo batte forse di 2×; l’ordine non cambia.

Schema elettrico

La percezione si divide nettamente in tre compiti, e solo il primo è obbligatorio.

Urto. Due microswitch su un paraurti elastico anteriore, collegati attivi bassi a pin capaci di interrupt con le resistenze di pull-up interne abilitate. Questa è la percezione che rende possibile il rimbalzo casuale ed è l’ultima cosa a guastarsi.

Bordo. Sensori di riflettanza rivolti verso il basso agli angoli anteriori, letti a ogni passaggio del ciclo. Un’esecuzione di copertura visita ovunque, cosa che include la sommità delle scale — il calcolo di quanto il robot può superare il bordo prima di fermarsi è svolto qui.

Posizione. Encoder in quadratura su entrambe le ruote e un giroscopio se vuoi file che restino parallele. Solo la strategia pianificata ne ha bisogno, e proprio questa necessità è il motivo per cui esistono le altre due.

Per le strategie di copertura come progetto, vedi il robot per la copertura della stanza; per lo strato reattivo sotto tutte quante, il simulatore di evitamento ostacoli copre le soglie di arresto e la scansione.