Giuseppe Gi

In questo articolo sulla visione robotica vedremo come realizzare un rilevatore di colori e come progettare una macchina agente (robot) che lo utilizza per seguire oggetti colorati.
Esempi di visione robotica in Java parte II
di Giuseppe Giannini

Nell'articolo scorso abbiamo visto come sia possibile elaborare un'immagine tramite trasformazioni e filtri, abbiamo visto la convoluzione matematica e come usare delle maschere mobili per elaborare i pixel al fine di ottenere delle informazioni sull'ambiente da un'immagine. Abbiamo visto come realizzare un componente di rilevamento movimenti confrontando due fotogrammi consecutivi in flusso video proveniente da una web cam, e abbiamo usato JMF per ottenere tale flusso video. Continuiamo, con questo articolo, il nostro viaggio, realizzando un componente che usando i concetti introdotti, prende in input uno stream video, e rileva oggetti di un determinato colore definito dall'utente, e quindi notifica tale evento alle classi interessate a gestirlo, nel nostro caso un robot il cui compito sarà inseguirlo.

Rilevatore di colori

Questo componente di visione robotica è più semplice da realizzare rispetto al precedente rilevatore di movimenti, e il suo semplice codice è riportato nel listato 1.

1 public void rilevaColore(int[][] img,int in_coloreRif,int in_soglia,int[] out_colorePrevalente,int[] out_numPix){

2      int r=0; int g=0; int b=0;

3      int r1,g1,b1;

4      r1=(int)in_coloreRif & 0xff;

5      g1=(int)(in_coloreRif>>8)& 0xff;

6      b1=(int)(in_coloreRif>>16)& 0xff;

7      int pixel;

8      out_numPix[0]=0;

9      for (int x  = 0; x < img.length; x++) {

10        for (int y  = 0; y < img[0].length; y++) {

11         pixel=img[x][y];

12          r=(int)pixel & 0xff;

13          g=(int)(pixel>>8)& 0xff;

14          b=(int)(pixel>>16)& 0xff;

15          if (Math.abs(r1 - r) <= in_soglia &&

16              Math.abs(g1 - g) <= in_soglia &&

17              Math.abs(b1 - b) <= in_soglia) {

18              out_numPix[0]++;

19              img[x][y]=0xffffff;

20          }

21        }

22      }

23      pixel=img[img.length/2][img[0].length/2];

24      r=(int)pixel & 0xff;

25      g=(int)(pixel>>8)& 0xff;

26      b=(int)(pixel>>16)& 0xff;

27      out_colorePrevalente[0]= 255 << 24 |

                            (int) (b & 0xff) <<16 |//b

                            (int) (g & 0xff) <<8  |//g

                            (int) (r & 0xff);      //r

28    }

Il funzionamento di tale componente è il seguente: dato un colore di riferimento, e una porzione dell'immagine da analizzare, il componente notificherà la presenza di oggetti il cui colore è simile a quello di riferimento. Il grado di similarità è definibile tramite una soglia passata come parametro (int in_soglia) dell'utente. Il metodo, come il precedente rilevatore di movimenti, elabora il flusso video generato da una web cam, (per comodità ogni fotogramma di tale stream viene convertito in una matrice di interi "int[][] img" come mostrato nell'articolo scorso).

Si differenzia dal rilevatore di movimenti perché non usa la convoluzione per tracciare i bordi degli oggetti rilevati, e non esegue il confronto tra due fotogrammi consecutivi, ma si limita a scorrere l'intera immagine listato 1 riga 9 (o una porzione definita dall'utente), e per ogni pixel (r,g,b) effettua un confronto con il colore da rilevare (il colore di riferimento definito dall'utente "int in_coloreRif"), servendosi in tale confronto della soglia di similarità. Se la differenza in valore assoluto tra i due pixel è compresa nella soglia allora il pixel letto viene considerato simile al colore di riferimento (Listato1 riga 15) e viene conteggiato (una variabile viene incrementata Listato1 riga 18) come pixel ricercato. Come potete notare, una particolarità di tale metodo, è che non restituisce nulla, tuttavia avendo passato come parametro in input la variabile "int[] out_numPix" per riferimento e non per valore, le modifiche al suo contenuto sono visibili anche al ritorno dalla funzione. Praticamente e come se avessi scritto in C int* out_numPix. Abbiamo anche colto l'occasione per simulare l'uso dei puntatori in Java, dove passare int[] significa passare per riferimento il contenuto dell'array puntato dall'int[]. Se alla fine della scansione dell'immagine il numero di pixel conteggiati è sufficientemente elevato, cioè superiore ad un limite definito dall'utente, la classe notifica l'evento a tutti gli interessati, utilizzando lo stile dei listener che abbiamo visto nell'articolo scorso.

E' molto delicata la questione della soglia. Prima di tutto diciamo a cosa ci serve un valore di soglia. Immaginiamo di voler rilevare gli oggetti di colore blu, per esempio una palla, e immaginiamo di trovarci in una stanza illuminata da luci al neon. Il colore blu percepito dal robot in questo ambiente non è identico allo stesso oggetto posizionato in un'altra stanza illuminata da una diversa luce per esempio la luce diretta del sole. Sebbene si tratti dello stesso oggetto colorato, i valori numerici del colore variano al variare della luminosità ambientale, quindi occorre utilizzare un valore di soglia per introdurre una certa "tolleranza alle variazioni di luminosità" e asserire così che i colori simili al colore di riferimento possono essere accettati entro tale intervallo. Come il componente di rilevamento movimenti, anche questa classe ha la necessità di notificare eventi.
Gli eventi che vogliamo notificare sono:
⦁ coloreRilevato (RilevatoreColoreEvento)
⦁ coloreNonRilevato(RilevatoreColoreEvento)

Possiamo come di consueto realizzare un'interfaccia software (un listener) che dichiari tali metodi e lasci l'implementazione alle classi interessate a gestirlo.
Chi implementa questi metodi esegue il proprio codice al verificarsi di tali eventi per effetto del polimorfismo.
Nel prossimo paragrafo vedremo come strutturare un'applicazione robotica. Occorre sottolineare che l'approccio dell'applicazione che usa il rilevatore di colori al posto del rilevatore di movimenti (visto nell'articolo scorso) può essere riprogettato (ottimizzandolo da un certo punto di vista).

Infatti, nell'applicazione per rilevare i movimenti, l'approccio non è ad "eventi" (un comportamento ad eventi si ha quando il robot esegue direttamente un'azione se si verifica un certo evento) ma è di tipo "monitoraggio continuo", cioè il robot esegue in continuazione azioni, leggendo il proprio vettore di caratteristiche X periodicamente oppure può decidere di non leggerlo per un pò perchè sta eseguendo un'azione che può influenzare una certa percezione. Quindi il vettore di cratteristiche viene costruito separatamente da dei thread che ricevono degli eventi. Vedremo tra breve cos'è un vettore di caratteristiche nel dettaglio, per ora consideriamolo come una qualche rappresentazione dell'ambiente del robot. Nel rilevatore di colori invece i thread oltre a costruire il vettore di caratteristiche a seguito di notifiche da parte dei rilevatiri di colori, propagano tali eventi notificandoli direttamente robot che va a leggere il vettore aggiornato. In ogni caso occorre sviluppare politiche di sincronizzazione sul vettore condiviso tra gli scrittori (i rilevatori di colori) e i lettori (il decisore delle azioni). Questo secondo approccio è più adatto a questo tipo di percezione (colore), è va bene per esempio in applicazioni in cui il robot deve seguire un bersaglio (di un certo colore) che si muove. Se invece usassimo questo stile di programmazione anche con i rilevatori di movimento, il robot muovendosi riceverebbe eventi continui perché l'intero ambiente gli parrebbe in movimento (movimento relativo), e quindi non sarebbe adatto. Suggerisco per chi fosse interessato ad approfondire tali tematiche a riflettere sui sistemi di visione dei ragni e di alcune rane.

Agenti Stimolo-Risposta

Prima di procedere, vorrei presentarvi un possibile modello architetturale del nostro robot. Un agente S-R
(Stimolo Risposta) è una macchina che reagisce in un determinato modo se e quando si verifica un certo evento percepito nell’ambiente in cui si trova. Per esempio, il nostro robot deve essere capace di rilevare un oggetto in movimento che entra nel suo campo visivo, e se di colore blu inseguirlo. Per ottenere questo risultato possiamo rappresentare l’ambiente del robot (nel nostro caso l’immagine che percepisce) come un vettore di quattro elementi denotati con s1, s2, s3, s4 che, rispettivamente rappresentano la porzione sinistra dell’immagine, quella centrale superiore quella centrale inferiore e quella destra. Quindi ciò che facciamo è suddividere l’immagine percepita in celle che abiliteremo a percepire eventi sotto il controllo di thread dedicati. Chiamiamo questo vettore input sensoriale (Figura1).

Il valore di queste celle può essere un intero, che rappresenta l’intensità di colore prevalente nella rispettiva porzione dell’immagine, oppure informare sulla presenza in quella porzione di un oggetto in movimento. Ciò che il robot deve fare, ora che ha un vettore di percezione, è usare una funzione che selezioni un’azione appropriata alla configurazione dell’input sensoriale. In alcune applicazioni, l’input sensoriale viene analizzato separatamente dalla funzione di selezione azione, e in questo caso viene generato un nuovo vettore intermedio tra percezione e azione. Tale vettore denotato con X prende il nome di vettore di caratteristiche, e va pensato ad un livello di astrazione maggiore rispetto al vettore sensoriale. Contiene di solito descrizioni categoriche di qualità dell’ambiente, oppure altri tipi di dati scelti dal progettista. Per esempio un elemento del vettore potrebbe essere di tipo booleano e rispondere con true o false alla caratteristica dell’ambiente “Esiste un oggetto in movimento di colore blu di fronte?”. Con una sola domanda catturiamo tre diverse percezioni; movimento, colore e posizione. Il vettore di caratteristiche viene generato dall’elaborazione del vettore sensoriale, e la sua produzione è visibile nella Figura 2.

Nel nostro esempio vogliamo che il robot segua oggetti in movimento di colore blu. Il vettore X di caratteristiche potrebbe contenere quindi le seguenti categorie di input sensoriali.

1. x1 :: Oggetto blu in movimento a destra
2. x2 :: Oggetto blu in movimento a sinistra
3. x3 :: Oggetto blu in allontanamento (quando si rileva in s2)
4. x4:: Oggetto blu in avvicinamento (quando si rileva in s3)
5. x5 :: Oggetto blu fermo
6. x6 :: Oggetto non blu in movimento

La funzione di azione=f(X) potrebbe essere:

⦁ avanti se x3=1
⦁ indietro se x4=1
⦁ null se x5=1 or x6=1
⦁ sinistra se x1=1
⦁ destra se x2=1

Questo semplice modello fornisce una base per programmare macchine che, nonostante non siano dotate di intelligenza artificiale, possono comportarsi in maniera anche molto complessa, specie se invece di limitarsi ad eseguire azioni l’agente invoca sottoprogrammi o routine.
Un modo per selezionare l’azione appropriata da eseguire in base ad una configurazione del vettore di caratteristiche è il sistema a produzione. In tale sistema vi sono un certo numero di regole scritte nella forma:
à .
La regola è , mentre, l’azione che sarà compiuta se la regola viene soddisfatta è .
Nella figura 3 potete osservare lo schema del nostro robot modellato sulle macchine S-R con sistema a produzione.

In questa figura le transizioni sono numerate, e una dettagliata spiegazione di ciò che accade è riportata di seguito:
1. Il sensore legge dall’ambiente ciò che è abilitato a rilevare, per esempio una web-cam rileva una o più immagini, un sensore di distanza una certa misura ecc.
2. L’agente non riceve direttamente in input gli output dei sensori, bensì un vettore di attributi che hanno senso ai fini del suo funzionamento. Ciò oltre a renderlo indipendente dal sensore, lo rende indipendente dall’ambiente, cioè lo stesso programma scritto per funzionare in un simulatore può funzionare nel mondo reale.
3. Il vettore di caratteristiche va pensato come una lista di qualità del tipo: “esiste un oggetto blu nell’ambiente”? vero/falso oppure “ci sono oggetti in movimento rilevati a nord?” vero/falso. L’agente non sa quale sensore abbia riempito tali campi del vettore, né se l’abbia fatto scandendo il mondo reale o una rappresentazione simulata.
4. Tale vettore viene dato ad un comportamento che l’agente può caricare anche a run-time. Il comportamento è la funzione di selezione azione.
5. L’azione potrebbe essere un comando o una funzione.

Il robot completo

Ora che abbiamo tutti gli ingredienti costruiamo il componente che pilota il robot in base alle percezioni della webcam, uno schema completo dell'architettura del progetto è visibile nella figura 4.

L'applicazione client che risiede sul robot dipende dalla scheda elettronica che controlla i servocomandi del robot stesso. Di seguito vi mostro un frammento di codice in linguaggio basic, che personalmente trovo inadatto ad applicazioni serie. Tuttavia e molto diffuso su schede per robot economiche, mentre le più recenti schede che supportano java hanno lo svantaggio di essere più costose.

'{$STAMP BS2}
comando var byte
main:
debug "valore iniziale comando=",comando,CR
serin 16,16468,[comando]
debug "Ricevuto comando=",comando,CR
if comando = "1" then cameraSu
if comando = "2" then cameraGiu
if comando = "3" then cameraSx
if comando = "4" then cameraDx
goto main
sub cameraGiu: pulsout 13,250 return
sub cameraSu: pulsout 13,1000 return
sub cameraDx: pulsout 12,250 return
sub cameraSx: pulsout 12,1000 return

In questo frammento di codice, l'applicazione non fa altro che eseguire i comandi ricevuti da un host (il nostro pc) tramite la porta seriale (oppure tramite un ricevitore radio seriale). Sul host risiede l'applicazione server che esegue i rilevatori di colori e dopo aver elaborato il vettore di caratteristiche prodotto scrive sulla porta seriale il comando giusto in base alla sua configurazione. Nell'articolo precedente abbiamo mostrato anche un frammento di codice per scrivere byte sulla porta seriale da Java, se ve lo siete perso, potete contattarmi.

In figura 5 infine, è possibile notare un'istanza di un rilevatore colori in azione con il pannelo di controllo aperto per settare la soglia e il colore target da rilevare.

 Conclusioni

Non è stato semplice farci entrare tutto in questi due articoli, e molte cose sono state semplificate. Tuttavia gli spunti non credo che vi manchino per costruire vostre applicazioni di visione robotica, e se le abbinate alle applicazioni di navigazione robotica su grafi (viste in passato sempre su questa rivista) potrete davvero realizzare macchine interessanti.

Programmazione O.O.

11 Dicembre 2016

Visite: 1464

Leggi tutto: Visione robotica in Java parte II

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.

Programmazione O.O.

25 Luglio 2017

Visite: 3483

Leggi tutto: Originale algoritmo per visitare tutti i vertici di un grafo