Roomba watching: gli algoritmi euristici

Ve lo sarete chiesti, guardando il Roomba che vi pulisce il salotto: come diavolo farà a passare dappertutto?

D’altra parte, il pensionato che è dentro noi, in quei momenti esce allo scoperto. E’ come “Ammazza la vecchia” per Roger Rabbit: quando vediamo un Roomba dobbiamo metterci lì, con le mani dietro la schiena, a giudicare il suo lavoro.

Il problema del commesso viaggiatore

Con il fiorire dei trasporti e dell’informatica si è sentita la necessità di rispondere ad una annosa domanda riguardante la logistica:

Considerando un insieme di città collegate tra loro come posso calcolare un itinerario ottimale che un ipotetico viaggiatore possa percorrere, tale che:

• Si visiti una singola città una sola volta
• Al termine si ritorni al punto di partenza

Molti filosofi approcciarono il problema. Ma, una volta finite le loro abbondanti scorte di Friol, se ne andarono lasciando il cetriolo in mano a matematici ed informatici.

Ok ok, forse sto divagando. Vi aspettavate un articolo sul Roomba ed io invece vi parlo di città, viaggiatori e filosofi. Ma questo problema mi è molto comodo per 2 motivi: il primo è che possiamo sostituire il viaggiatore con il nostro robottino da pulizia preferito e le città con n punti del nostro pavimento.

Abbiamo così ricondotto il nostro problema iniziale a quello del commesso.

Il secondo è che, con questo esempio, posso spiegarvi facilmente cosa sia un grafo.

Teoria dei grafi for dummies

Potrei passare le prossime migliaia di righe nel tentativo di spiegarvi la teoria dei grafi. I grafi sono fantastici, ci si può fare tutto con la giusta inventiva. Ma sono anche piuttosto vasti e più o meno complessi (e poi non mi ricordo più nulla ma questa è un’altra storia), quindi facciamo così:

Prendiamo un foglio di carta

• Le città le rappresentiamo con un cerchio con dentro il nome (le chiamiamo nodi del grafo)
• Le autostrade che le collegano con una linea ( le chiamiamo collegamento)
• La città di partenza del nostro viaggiatore sarà il nostro punto iniziale.

Ecco, questo è un grafo che rappresenta il nostro problema.

In definitiva possiamo definire un grafo come una rappresentazione grafica e schematica di una determinata situazione.

Ora che abbiamo sott’occhio la nostra problematica cerchiamo di capire che giro studiare per il nostro piazzista viaggiatore.

[spoiler]

Giusto per completezza:

supponiamo che due città siano collegate da una strada sterrata di difficile percorrenza: mettiamo su quella linea un numero intero (da 1 a 10, per chiarezza) che aumenta all’aumentare della difficoltà di percorrenza. Avremo quindi 1 per l’autostrada e 10 per il sentiero di montagna. In questo caso parliamo di grafi pesati.

supponiamo che due città siano collegate da una strada a senso unico: in questo caso la linea che le collega sarà una freccia, indicante il “senso di marcia”: si parla quindi di grafi orientati.

[/spoiler]

Questione di complessità

Non ci è difficile capire che quante più città dobbiamo visitare e quante più strade che le collegano ci sono, tanto più il nostro problema sarà complesso.

Non dimentichiamo che, se volgiamo risolvere il problema con una certa efficienza, dobbiamo non solo visitare tutte le città ma anche col minor sbattimento possibile (e quindi senza tornare due volte nello stesso posto).

Facendo due calcoli e ponendo vero il caso peggiore, cioè che le n città che noi vogliamo raggiungere siano tutte interconnesse tra di loro,

per calcolare tutti i possibili itinerari e valutare così il migliore avremo bisogno di n! operazioni.

Torniamo al nostro caso di partenza, il Roomba. Se consideriamo il pavimento composto da infiniti punti e abbiamo bisogno di pulirli tutti quanti, prima di tornare alla base, capiamo subito che non possiamo seguire questo metodo.

Mettiamola così, un moderno pc è in grado di risolvere svariati problemi più o meno complessi ma si arrende di fronte a problemi di complessità esponenziale come questo.

Diavolo d’un Roomba

Già ma il Roomba funziona, forse. Come fa?

Beh, in informatica esistono diverse soluzioni ad un problema estremamente complesso.

D’altra parte gli informatici non si arrendono di fronte alla prima difficoltà, noi siamo gente che lavora. Proprio come gli impiegati Mediaset, solo vestiti molto peggio.

Soluzioni esatte

Prima di tutto dobbiamo capire se ci serve avere la soluzione esatta al nostro problema.

Sembra una domanda stupida questa ma in realtà non è così.

La soluzione esatta costa, specialmente in questo caso. E forse può non essere utile. Ma questo caso lo vedremo dopo.

Noi vogliamo fare come si deve, ci piace soffrire. Supponiamo così che la nostra azienda di trasporti,

nel tentativo di ottimizzare le spedizioni a livello nazionale, voglia trovare il percorso ottimale per passare da tutti gli 8.057 comuni della penisola.

Facendo una rapida ricerca su Wikipedia, scopriamo che possiamo farlo visto che il record, oggi, è 33.810 luoghi (quindi vertici del grafo).

Ma questo calcolo ha richiesto dei computer-ninja dedicati al calcolo parallelo impiegandoli per molto tempo.

Applicare un algoritmo del genere a Roomba è fuori discussione,

dovrebbe avere un hardware avanzatissimo e molto tempo a disposizione prima di iniziare la pulizia. Parliamoci chiaro: ognuno di noi, se avesse tra le mani un hardware simile, lo userebbe per giocare a GTA V.

[spoiler]

Nel 2004 è stata calcolata la soluzione esatta al problema del commesso viaggiatore per tutte le 25.000 circa città della Svezia (ho fatto una rapida ricerca: per città in Svezia intendono “tutto”. Non mi capacitavo del fatto che la Svezia avesse il triplo dei nostri comuni e infatti non è così. In quel numero c’è dentro ogni più remoto luogo esistente nello stato scandinavo). Il risultato ottenuto è un percorso di 72.500 km.

Gli svedesi hanno tutto il mio rispetto ora, le svedesi lo avevano già.

[/spoiler]

Ok, l’approccio visto fin’ora non lo possiamo applicare al nostro robottino. Anche perchè prima di tutto sarebbe necessario fare uno scanning della stanza da pulire, in modo da trovare le zone da aspirare, gli ostacoli che le dividono e le vie di collegamento. Ma come facciamo lo scanning? Come possiamo avere la certezza di avere scansionato ogni singolo cm quadro della stanza?

Siamo tornati al problema di partenza.

L’unica soluzione sarebbe programmare manualmente il Roomba ma questo è davvero troppo, anche per noi nerd.

Algoritmi Euristici

Quello che possiamo fare, però, è cercare un algoritmo che permetta a Roomba di coprire il più possibile la superficie del nostro pavimento evitando di volta in volta gli ostacoli che si presentano davanti a noi. Poco importa se non ottimizza il percorso, se passa più volte dallo

stesso punto o se ci mette il triplo del tempo.

Un algoritmo euristico è proprio questo: un procedimento che non dà un risultato ottimale al nostro problema ma che lo rende molto più facile da gestire. Ok, ammetto che detto così non sembra un granchè

ma la realtà è che tutto dipende dal campo di applicazione.

Sheldon: Tom, however, has been chosen by science as a suitable mate for Penny.

Leonard: Chosen by science?

Sheldon: Well, what passes for science on dating sites. They claim to use heuristic algorithms, but it may well be hokum.

Se torniamo alla nostra azienda di trasporti, ad esempio, possiamo forse dire che un algoritmo euristico può essere una cattiva scelta. Ogni chilometro in più, per un camion, vuol dire soldi spesi in carburante, pneumatici, manodopera, usura e quant’altro. A questo punto mi noleggio una server farm e mi faccio calcolare il miglior percorso possibile a livello nazionale, se proprio mi serve.

Ma per il Roomba, se ci pensiamo, la soluzione è perfetta.

Tempi di computazione pressochè nulli, hardware più scarso e quindi costi più bassi. Se passa dieci volte sullo stesso punto pazienza, quel punto sarà più pulito. Visto in quest’ottica non solo la soluzione euristica è da prendere in considerazione ma è addirittura migliore di quella esatta.

Ora, so cosa vi state chiedendo:

Ok, gli algoritmi euristici non sono esatti. Ma quanto si discostano dalla soluzione ottimale?

Questo è difficile dirlo anche perchè, a volte, l’ottimo non c’è.  Come nell’esempio di cui sopra Sheldon – Leonard.

Wikipedia ci dice, comunque, che nel caso del commesso viaggiatore la soluzione

ottenuta da un algoritmo euristico fatto come si deve si discosta (statisticamente) del 2-3% della soluzione ottimale. Questo ci permette di calcolare oggi, con un algoritmo euristico, la soluzione al problema del commesso viaggiatore per milioni di città a fronte delle sole 33.000 e spicci della soluzione esatta.

A questo punto quasi quasi anche l’azienda di trasporti può cambiare idea al riguardo.

Facciamo quindi muovere Roomba in maniera più o meno casuale, con buona pace dell’ottimizzazione, in modo tale che a lungo termine copra tutta la superficie della stanza (la fase di pulizia dura molti minuti, quindi Roomba probabilmente tornerà più volte sullo stesso punto ed aspirerà tutto il pavimento).

In particolare mi pare di capire da quel poco che ho trovato che Roomba si muova a spirale da un punto specifico del pavimento ma non ho trovato molta documentazione al riguardo.

Algoritmi Bug

Ci rimane solo una cosa da capire, ovvero come evitare ostacoli che si possono trovare sul pavimento quali sedie, tavoli e tavolini, mobili, calze abbandonate dal giorno prima, vuoti di birra, vecchi Roomba caduti in battaglia, ospiti ubriachi.

Ebbene sì, noi informatici abbiamo la soluzione anche per questo problema. D’altra parte come detto siamo gente che lavora. E anche gente che si ubriaca ma questo non è così importante.

Gli algoritmi Bug fanno proprio al caso nostro.

Chiamati così non perchè fortemente buggati (quelli sono solo i miei…) ma perchè ispirati al mondo degli insetti, questi algoritmi permettono ad un robot di bypassare un ostacolo casuale trovato sul proprio percorso, in maniera più o meno efficiente.

Per gli amanti della soluzione esatta abbiamo l’algoritmo Bug 1, per gli amanti dell’euristica l’algoritmo Bug 2.

La differenza tra i 2 è piuttosto semplice.

Nel primo caso, incontrato un ostacolo, questo verrà completamente circumnavigato e “mappato” prima di essere superato

mentre nel secondo caso verrà seguito il profilo dell’ostacolo solo fino al raggiungimento, da parte del robot, della traiettoria che aveva prima di incontrarlo.

Meglio un immagine, anzi 2:

Algoritmo Bug 1

Algoritmo Bug 2

Entrambe le soluzioni hanno pregi e difetti, epic win ed epic fail che potete trovare ben descritti in questo pdf dell’ Università di Pavia.

Quello che ci interessa e che a Roomba, per mettere all’opera questi algoritmi, non serve niente di particolarmente evoluto o costoso.

Così ad occhio direi che sono sufficienti dei sensori di prossimità per localizzare l’ostacolo e un hardware che gli permetta di capire quanto e come si è mosso rispetto agli assi x e y del pavimento.

In definitiva, come detto, la soluzione euristica nel caso del Roomba è quella vincente. Facendo muovere Roomba più o meno casualmente nella nostra stanza puntiamo sul fatto che, col passare del tempo, passerà ovunque.

Grazie agli algoritmi bug gli ostacoli non saranno un problema e verranno evitati senza intoppi (il più delle volte, almeno…).

Quando la batteria ha raggiunto un livello sufficientemente basso facciamo tornare il nostro robot a cuccia.

A questo punto abbiamo il pavimento pulito e il tempo libero per giocare all’ Xbox, perfetto!

Conclusioni

Il Roomba è figo e lo voglio.

Note e Fonti

Come detto queste sono solo supposizioni, raccontatemi pure nei commenti le vostre perplessità al riguardo, soprattutto se siete esperti di automazioni e robototica. Se ho sbagliato tutto pazienza, al peggio vi ho parlato di robottini, bug, Sheldon e gente ubriaca: cosa volete di più?

• Pagina wiki sulla teoria dei grafi
• pagina wiki sul problema del commesso viaggiatore (in inglese)
• Pagina wiki degli algoritmi euristici con relativo link al dettaglio sul commesso viaggiatore in italiano
• Volete visitare tutta la Svezia in soli 72.500 km? Eccovi l’itinerario
• Maggiori info sugli algoritmi Bug
• Pagina per vari hacking di Roomba in modo da farlo diventare un plotter, un aggeggio che disegna, un vibratore e molto altro.