Giuseppe Gi

 

Quest'articolo illustra un'originale algoritmo, che progettai ed implementai in Java ai tempi della tesi di laurea sulla quale è pubblicato, per visitare tutti i vertici di un grafo minimizzando il numero di passaggi su ognuno di essi. Non è un tradizionale TSP perché come vedremo alcuni tipici vincoli vengono rilassati, e nuovi ne vengono introdotti per la particolare applicazione di navigazione robotica cui l'algoritmo è destinato. Interessante sarà l'approccio con cui viene affrontato il problema dall'algoritmo, che ricorda, quando se ne osserva l'esecuzione passo-passo il fenomeno fisico dei vasi comunicanti, mentre dal punto di vista logico esso si ispira alla tecnica dell'unione di percorsi disgiunti.

Un'originale algoritmo di navigazione robotica per visitare tutti i vertici di un grafo.
di Giuseppe Giannini

 

I robot domestici come aspirapolvere o tagliaerba automatici (cioè capaci di svolgere autonomamente il compito che li definisce), sono elettrodomestici già oggi disponibili sul mercato. Se volessimo progettarne il software, la prima capacità da fornire a tale macchina sarebbe quella di rappresentare il proprio ambiente di lavoro (un giardino o una stanza) per mezzo di un'appropriata struttura dati, e dotarlo di algoritmi che, manipolando tale rappresentazione, gli permettano di avere un comportamento utile (per esempio potare l'erba del proprio giardino, ma non tranciare il cane che vi scorrazza nel mezzo). Rappresentare un ambiente come una stanza o un giardino può essere banalmente realizzato tramite un grafo, come è possibile osservare in Figura 1.

A tal proposito riassumo brevemente le tipiche modalità con cui tale rappresentazione può avvenire. I vertici del grafo (o anche nodi del grafo) rappresentano spazi vuoti dell'ambiente (solitamente gli incroci), cioè zone nelle quali il robot può sostare/transitare, gli archi del grafo, che collegano due vertici, ci informano che il robot può spostarsi da un vertice al suo adiacente. L'assenza di un arco o di un vertice ci informa della presenza di ostacoli in quella zona. Teniamo presente che esistono almeno due tipi di ostacoli: quelli fissi come per esempio i muri, e quelli mobili come per esempio le persone. I primi, come accennato, possono essere rappresentati dalla mancanza di archi fra vertici, o dalla mancanza dei vertici stessi nel grafo (quando l'ostacolo è abbastanza grande), i secondi devono essere, invece, intercettati dinamicamente dal robot tramite percezioni sensoriali a seguito delle quali ogni altro processo della macchina deve essere prelazionato in favore di una funzione appropriata. Questo secondo tipo di ostacolo non viene quindi rappresentato in ogni istante dalle caratteristiche del grafo (o dalla geometria del grafo qualora essa fosse deducibile, come accade per esempio in un "grafo a griglia" di cui parleremo nel prossimo paragrafo). 

L'algoritmo che forniremo al nostro robot, lavorerà su grafi la cui rappresentazione si basa sulle liste d'adiacenza. Ogni vertice del grafo ha una lista d'adiacenza che contiene i suoi archi uscenti verso i vertici vicini. L'algoritmo darà al robot la capacità di coprire tutti i punti liberi dell'ambiente, transitando per ognuno di essi il numero minore di volte più vicino a uno. Nel seguito dell'articolo ci occuperemo dello sviluppo di questo algoritmo, mentre rimanderemo ad un futuro articolo la capacità del robot di rilevare ostacoli in movimento (o imprevisti sul suo percorso) mentre segue un cammino su un grafo.

Obbiettivo e Idea di Base
Come accennato nell'introduzione è tramite un grafo che il nostro robot mobile mantiene memoria del suo ambiente conoscendo quindi: gli spazi vuoti; gli ostacoli fissi; e i percorsi per giungere da uno spazio vuoto ad un altro. Il grafo stesso può essere editato dall'agente robotico per mezzo di un algoritmo di esplorazione dell'ambiente o editato dall'utente come elaborazione della planimetria dell'ambiente. Un modo rapido per editare una mappa, è usare una specializzazione di un grafo classico, che chiameremo "grafo a griglia", visibile sulla destra della Figura 1. Si intuisce quindi che i vertici saranno disposti, geometricamente parlando, in righe e colonne, mentre da un punto di vista logico essi saranno mantenuti sempre in liste di adiacenza. La differenza con un tradizionale grafo è che in un grafo a griglia esiste implicitamente un'informazione sulla posizione di un dato vertice, essendo gli stessi organizzati in righe e colonne, inoltre dato un vertice, esso ha al più otto vicini se nel grafo a griglia esistono anche archi trasversali, oppure se sono previsti solo archi orizzontali e verticali i vicini sono al più quattro. La conseguenza di quanto detto, è che per ogni vertice la lunghezza della propria lista di adiacenza è al massimo di quattro o di otto elementi. Queste caratteristiche ci torneranno utili quando specializzeremo l'algoritmo che stiamo per sviluppare per funzionare proprio su questo tipo di grafo. Naturalmente il grafo generico della Figura 1 (sulla sinistra) è più adatto all'esecuzione di algoritmi di cammino minimo, mentre il grafo a griglia ancora in Figura 1 (sulla destra) è più adatto ad algoritmi di copertura di ogni punto dell'ambiente. Per ora gettiamo le specifiche e sviluppiamo dapprima l'algoritmo su un generico grafo, e poi lo specializzeremo per funzionare meglio su un grafo a griglia.
Il problema da risolvere ha la seguente specifica:

⦁ Dato un grafo G (generico o a griglia).
⦁ Coprire tutti i vertici di G passando per essi il numero minimo di volte (preferibilmente una sola ma è possibile se necessario passare più volte).
⦁ Partire da qualsiasi vertice (dipende dalla posizione del robot).
⦁ Non è necessario tornare nel punto di partenza.
⦁ Penalizzare percorsi con numero eccessivo di cambi di direzione, vincolo valido, ovviamente, solo per grafi a griglia che consentono di dedurre la posizione di un vertice rispetto al suo predecessore nel percorso.

Questi vincoli lo rendono, evidentemente, diverso dai problemi TSP (o del commesso viaggiatore) in quanto alcuni di essi risultano rilassati, e si introduce la penalizzazione sui percorsi a "zig zag", che hanno una definizione solo se si parla di grafi a griglia. L’algoritmo che stiamo per sviluppare è stato testato in un simulatore robotico in 3D appositamente realizzato per l'ottimizzazione di algoritmi su grafi finalizzati alla navigazione robotica, e si basa sull’idea che a partire da un percorso qualsiasi P, è possibile considerare i vertici non appartenenti a tale percorso come appartenenti ad altri percorsi P che potrebbero essere inglobati in P stesso. Immaginiamo quindi P come un sottoinsieme di vertici che si espande. L'espansione di P ricorda l'effetto dell'allagamento di un recipiente, tutti i recipienti comunicanti nei quali ci sono i percorsi residui (P ) verranno allagati, e quindi tali percorsi saranno inglobati in P.
Inglobare un percorso in un altro consiste in un’operazione di unione di due liste di vertici del grafo. Occorre quindi considerare un percorso come una lista ordinata di vertici. L’ordine di tale lista è dato dal tempo di visita di un vertice. Se in tale lista esistono due vertici (u,v) tra loro consecutivi significa che nel grafo essi sono collegati da un arco. Se esiste almeno un vertice nella lista di adiacenza di (u) connesso tramite un percorso (P ) con almeno un vertice nella lista di adiacenza di (v), allora è possibile inserire tale sottolista P tra (u) e (v). In altre parole inglobare (in questo algoritmo), significa sostituire l’arco che collega (u) e (v) con un percorso P la cui sorgente è un vertice adiacente a (u) e la destinazione un vertice adiacente a (v). Con il vincolo però che tutti i vertici di P non devono essere già parte di P.

Alla Lavagna
Nelle figure seguenti è facile intuire il funzionamento dell’algoritmo. Esso viene illustrato in maniera visuale, e successivamente, con il listato in pseudocodice.
Nella Figura 2 è visibile un esempio di grafo che useremo per spiegare l'idea di base dell'algoritmo.

Sempre in Figura 2 abbiamo già selezionato un percorso iniziale (liberamente scelto) di due soli vertici e chiamiamo tale percorso P. Idealmente possiamo quindi dividere il grafo in due partizioni, la P contiene tutti i vertici visitati, la U i restanti vertici di G non ancora mai raggiunti. In U, essendo i vertici connessi da archi formano percorsi residui da inglobare in P. L'algoritmo cercherà in U percorsi residui, li ingloberà in P, che espandendosi, coprirà tutto G. Nella Figura 3

si nota come tale passo dell'algoritmo viene eseguito, è cioè: per ogni vertice (u) nel percorso P e il suo successore (v) in tale percorso P, l'algoritmo cerca nelle rispettive liste di adiacenza due vertici che chiamiamo adj(u) e adj(v) tali che essi siano connessi da un percorso P1, con il vincolo che tale P1 non abbia vertici già visitati, cioè che non appartengano alla partizione P ma solo ed esclusivamente ad U. Ora che abbiamo il percorso P1 non ci resta che inglobarlo in P, come visibile in Figura 4, tale operazione che potremmo scrivere come P=P+P1 è molto semplice.

 

Viene, infatti, idealmente rimosso l'arco fra (u) e (v) che nella Figura 4 ora ci appare in grigio, e sostituito con il percorso P1. A questo punto va eseguita un'altra importante operazione, cioè la rimozione di P1 da U. Ciò garantisce che in U rimangano solo i vertici mai visitati e che i prossimi percorsi residui non conterranno vertici di P. Graficamente U si riduce a ogni passo e potremmo scrivere tale operazione come U=U-P1. Nella Figura 5 notiamo che continuando a scorrere P (che è cresciuto) l'attuale vertice (u) ed il suo successore (v) non hanno vertici adiacenti situati in U e connessi fra loro da un percorso residuo P1.

 

Infatti continuando a osservare sempre la Figura 5 adj(u) restituisce solo vertici situati in P, cioè già visitati, l'algoritmo quindi in questo passo non fa niente e continua a scandire P con (u++). A questo punto come ben visibile in Figura 6 sia il vertice (u) che il suo successore (v) hanno rispettivamente un vertice adiacente adj(u) e un adj(v) situati nella partizione U e connessi tra loro da un percorso residuo P1.

 

Quindi l'algoritmo ingloba come visto prima P1 in P. A questo punto, come visibile nella Figura 7, l'insieme U risulta essere vuoto, e P comprende tutti i vertici di G. In Figura 7 si nota anche il percorso che l'algoritmo restituisce.

Prima di vedere come può essere scritto in pseudocodice tale algoritmo occorre considerare il seguente caso speciale, riportato anche graficamente in Figura 8.

 

Per questo caso speciale, supponiamo che dopo aver inglobato tutti i possibili percorsi residui in U, esistano ancora vertici isolati, cioè vertici connessi al grafo ma non facenti parte di percorsi aventi un numero di vertici superiore a uno. In altre parole un tale vertice può essere considerato come un percorso di lunghezza uno in cui cioè la sorgente e la destinazione coincidono. Ma ciò che più conta ai fini della descrizione di questo caso speciale, è che tale vertice ha un solo arco doppio verso un solo altro vertice nel grafo. La conseguenza di ciò è che per passare per tale vertice, occorre passare due volte sia sul vertice a cui è connesso e sia sul suo arco. Se invece, questo vertice avesse avuto due archi doppi uscenti, non ci sarebbero stati ulteriori passaggi.

Pseudocodice
La spiegazione visuale del paragrafo precedente viene ora tradotta in un listato (Listato 1) in pseudocodice.

 

Listato in pseudocodice

1. Sia G il grafo da coprire, e sia P un percorso iniziale costituito anche solo da due vertici per es. v0 ed un suo adiacente; e sia U un grafo temporaneo inizialmente = G - P (in U ci sono quindi i percorsi residui da inglobare in P);
2. While U 0 and percorsi residui in U da inglobare in P (selezionando da questi vertici a coppie);
3. Do coppia consecutiva di vertici u,v del percorso in costruzione P;
u1 ß Adj(u) tale che c(u1)==0 cioè u1 non ancora visitato;
v1 ß Adj(v) tale che c(v1)==0 cioè v1 non ancora visitato;
6. trova un percorso P1 tra u1 e v1 tale che non contenga vertici già visitati (ovvero basta cercarlo in U anziché in G) ;
7. if ( tale P1 esiste ) then
8. PßP+P1 (cioè avremo u-->v che diventa u-->u1-->...-->v1-->v );
9. UßU-P1 (togli i vertici appena visitati da U, che conterrà così i restanti percorsi residui);
10. Incrementa il costo di ogni vertice e arco di P1 di 1 e passa direttamente alla coppia u,v successiva di P ;
11. if dopo aver scandito tutta la lista P non si sono trovate coppie tra le quali inglobare percorsi residui di U then
v ß P (prova a inglobare vertici singoli di U selezionando singoli di P);
ußAdj(v);
14. if ( c(u)==0 cioè non è stato ancora coperto ) then
15. PßP+u (ovvero nel percorso v-->u avremo  v --> u --> v cioè essendo u isolato passo per v 2 volte);
16. c(u)=1;
17. UßU-u;
18. if U>0 then goto 2 else return P (cioè se inglobando un vertice singolo, U è ancora > 0 provo a vedere se tale modifica ha prodotto in P una nuova coppia da espandere. Se invece U=0 ho coperto tutti i vertici e restituisco P);

 

Sebbene l'algoritmo sia stato implementato sia in C++ che in Java, viene qui riportato solo in pseudocodice, in quanto ci permette ancora di lavorare ad un livello d'astrazione molto alto, e possiamo trascurare gli aspetti di ottimizzazione. Tralasciando le righe di codice che si spiegano da sole, particolare attenzione va posta alla riga 6, dove viene cercato un percorso valido tra due vertici (u1) e (v1) appartenenti ad U, e rispettivamente presenti nella lista d'adiacenza di (u) e (v) appartenenti a P. I vertici (u) e (v) sono tra loro adiacenti perché presi dal percorso esistente P (hanno cioè un arco che li collega; vedere Figura2). Ma (u1) e (v1) non devono necessariamente essere tra loro adiacenti (possono non avere un arco che li colleghi direttamente, ma potrebbero essere collegati da un percorso P1).
Se tale percorso P1 cercato nel grafo temporaneo U esiste, e non ha al suo interno vertici già visitati  cioè appartenenti al vecchio P, allora il percorso P1 può essere inglobato in P senza pericolo di passare più di una volta per un vertice (o per un arco) (questa proprietà è garantita dal fatto che man mano che i vertici vengono inseriti in P vengono rimossi da U; quindi in U ci sono solo vertici non ancora visitati, inoltre le ulteriori ricerche in U, di un percorso, lavorano su un numero sempre minore di vertici). Il costo della ricerca di un cammino P1 valido diminuisce ad ogni passo perché la dimensione di U diminuisce ogni volta che si trova un percorso.
Nelle righe 4, e 5 viene scandita tutta la lista di adiacenze sia di (u) che di (v), questo rende l'algoritmo efficace anche per grafi non a griglia ma con un costo notevole. Nel caso dei grafi a griglia, sfruttando le informazioni sulle righe e le colonne della griglia stessa, l’operazione di scorrimento delle liste viene eliminata del tutto, sostituendola con operazioni di accesso diretto, ad un massimo di otto elementi se ci sono anche archi trasversali, soltanto quattro se ci sono solo archi orizzontali e verticali. In generale comunque la scansione delle "Adj" viene interrotta appena si trova un percorso valido per passare direttamente alla successiva coppia u,v in P.
Una nota sulla riga 10: La coppia successiva di P, se P è stato espanso inserendo un P1 potrebbe proprio appartenere a P1. P si espande dinamicamente, nel senso che si allunga nel mentre l'indice lo continua a scandire, vedere nella Figura 3 e 5 come scorrono gli indici u,v sui nuovi vertici appena inseriti. Tenendo conto di tale allungamento, vengono coperte anche nuove coppie appena inserite. Nella Figura 9 infine appare l'output del simulatore che esegue quest'algoritmo.

 

Conclusioni

Sebbene ci siano ancora alcuni aspetti da considerare, credo che quanto esposto precedentemente sia sufficiente per fornire ad un robot mobile la capacità di transitare per ogni punto del suo ambiente, e ci dia una visione d'insieme su come, prodotti robotici già esistenti, possano svolgere tale compito. Questo algoritmo è stato testato in un simulatore, è malgrado un simulatore sia una semplificazione della realtà, l'algoritmo si è dimostrato soddisfacente alle specifiche nella maggior parte dei grafi sottoposti.