Pianificazione di copertura: percorre un'intera stanza

Un problema diverso dal raggiungere una destinazione

A* trova una rotta verso un obiettivo. Un pianificatore di copertura deve toccare ogni casella raggiungibile, il che cambia completamente l’obiettivo: non c’è un obiettivo vicino al quale stare, non c’è un’euristica che ti guidi e il successo non è binario.

La misura che lo sostituisce è la distanza per metro quadrato percorso. Con un’area del pavimento A e uno strumento di larghezza w, un robot perfetto percorre ogni casella una sola volta e non ripete mai:

d_optimal = A / w

Una stanza di 20 m² con una spazzola da 250 mm richiede 80 m. Ogni valore seguente è un multiplo di questo, perché il confronto tra più percorsi è l’unico che sopravvive al cambiamento di stanza.

La legge che governa la percorrenza senza mappa

Un robot che non sa dove sia passato copre il pavimento nuovo in proporzione a quanta parte del pavimento è ancora scoperta. Si tratta di un’equazione differenziale con una sola soluzione:

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

Leggi tre punti dalla curva e la forma dell’intero problema appare:

Gli ultimi 9% costano più dei primi 90%. Questo è il problema del collezionista di coupon con una spazzola montata ed è l’unico fatto che spiega tutti i robot aspirapolvere che hai mai osservato.

Che cosa accade davvero

La teoria presume che ogni metro cada su un pavimento scelto indipendentemente. Un robot reale percorre linee rette, quindi i metri consecutivi sono correlati: continua a ripassare sulla zona su cui si trova già. Misurato in cinque stanze nel simulatore di copertura:

Tre elementi di quella tabella valgono più di tutto il resto della pagina.

Per la prima metà del pavimento non importa nulla. Al 50%, tutte e tre le strategie rientrano entro il 20% l’una dall’altra. Un robot senza sensori e senza memoria è davvero altrettanto valido di un pianificatore nella prima metà del lavoro, ed è esattamente il motivo per cui l’approccio economico è commercialmente praticabile e per cui un’osservazione superficiale non ne rivela mai la differenza.

Il caso è peggio rispetto alla sua stessa teoria. 6.76× contro un valore previsto di 4.61× al 99%, perché un rimbalzo in linea retta torna a visitare il pavimento appena percorso. Considera 1 − e^(−d) il limite ottimistico, non la stima.

Il pianificatore non termina mai. Si ferma al 90.4% e vi rimane, e non è un bug.

Perché il pianificatore lascia un decimo del pavimento

Un pianificatore di copertura deve mantenere il corpo del robot lontano da ogni parete e da ogni gamba di un tavolo, quindi gonfia ogni ostacolo del raggio del robot più un margine e pianifica nello spazio rimanente. Tutto ciò che rimane all’esterno è pavimento che il robot non può mai raggiungere.

Nella prova misurata, 130 delle 133 caselle mancate dal pianificatore si trovavano entro due celle da una parete o da un mobile. Solo tre erano su pavimento libero. Le aree mancate non sono sparse, ma formano un anello attorno a ogni ostacolo nella stanza.

Questo spiega due caratteristiche di ogni macchina commerciale:

• La spazzola laterale che sporge oltre il telaio. La spazzola è più larga dell’elemento che entra in collisione, quindi raggiunge il pavimento a cui le ruote non possono mai arrivare.
• La passata di seguimento del muro. È un comportamento separato, eseguito separatamente, perché la percorrenza sistematica non può strutturalmente eseguirlo.

Il rimbalzo casuale raggiunge prima o poi quei bordi, per caso, ed è l’unica cosa in cui è migliore.

Scelta delle file

Per una percorrenza sistematica, l’unico parametro davvero importante è la distanza tra le file.

Distingui le file a esattamente una larghezza di spazzola e anche il minimo errore di orientamento lascerà una striscia non pulita tra loro. Niente di ciò che farai in seguito la troverà, perché il piano ritiene che quel pavimento sia già stato completato. Sovrapponi il 10–20% e le strisce si chiudono, al costo esatto della stessa percentuale in distanza.

Questa sovrapposizione, insieme alla distanza percorsa per aggirare i mobili, spiega il valore di 1.35× del pianificatore. Non è uno spreco, ma il prezzo di un piano che sopravvive al contatto con un robot reale.

Due altre scelte contano più di quanto sembrino:

• Percorri le file lungo l’asse maggiore della stanza. Ogni curva costa tempo e non copre nuovo pavimento, quindi dimezzare il numero di file dimezza il sovraccarico delle curve.
• Instrada il passaggio tra un tratto e l’altro, non il tragitto in linea retta. Quando un mobile divide una fila in due tratti, il robot deve passarci attorno. Pianificare quel passaggio come percorso più breve nello spazio libero distingue un piano da un desiderio.

Sensori richiesti da ciascuna strategia

Questa è la vera ragione per cui esistono tutte e tre.

Il rimbalzo casuale richiede un solo bit. Ho colpito qualcosa? Due interruttori a molla e un generatore di numeri casuali costituiscono l’intero robot. Nessun encoder, nessuna mappa, nessuna localizzazione e nulla che possa derivare.

La spirale deve sapere quanto è avanzata dal centro della spirale corrente, quindi ha bisogno di un’odometria grossolana: abbastanza precisa per far crescere un raggio, ma non abbastanza per chiudere un anello.

Una percorrenza pianificata deve sapere dove si trova. File rettilinee, angoli di curva noti e uno spostamento laterale di una larghezza di spazzola sono tutte affermazioni basate sull’odometria, e l’odometria deriva. Dopo dieci file, non sono più parallele. Ecco perché le macchine commerciali che pianificano montano anche un giroscopio, una telecamera rivolta al soffitto o un segnalatore: il pianificatore è economico, ma la localizzazione che presuppone non lo è.

Scegli quindi la strategia in base al budget dei sensori, non all’eleganza dell’algoritmo. Costruisci prima quella casuale: funziona, richiede venti righe e fornisce il riferimento iniziale che il pianificatore deve superare.

Che cosa costa in minuti

Considera quella stanza di 20 m², una spazzola da 250 mm e un robot che viaggia a 0.25 m/s:

Una batteria è un budget di distanza. Un’autonomia di un’ora a 0.25 m/s equivale a 900 m, che coprono comodamente una stanza in modo casuale ma non tre ed è proprio questo, più di qualsiasi intuizione algoritmica, che ha spinto il mercato verso robot dotati di mappa.

Quando qualcosa va storto

Prova tutte e tre le strategie nella stessa stanza nel simulatore di copertura: trascina i mobili mentre sono in esecuzione e i numeri cambieranno di conseguenza. Poi costruisci il robot per la copertura della stanza, che inizia dalla strategia che non richiede nulla e aggiunge sensori solo dove la misurazione mostra che ne vale la pena.