Laboratorio di Intelligenza Artificiale
A.A. 2006/2007
Giuseppe Fotino
Marco Rivoltella
Scopo del progetto è costruire un agente autonomo intelligente, che opererà in un ambiente costituito da stanze (realizzate in cartone) collegate tra di loro attraverso delle aperture nelle pareti. L'agente dovrà essere in grado di elaborare la strategia migliore per spostarsi da una posizione di partenza ad una posizione di arrivo, eseguire passo per passo il piano calcolato e reagire di fronte a particolari condizioni di errore. Il robot lavora nell'ipotesi di conoscere esattamente la posizione, le dimensioni di tutte le stanze e come queste sono collegate tra di loro; il robot non conosce la posizione degli eventuali ostacoli presenti lungo il percorso (anche questi realizzati con del cartone), pertanto dovrà rilevarne la presenza attraverso un sensore ed eventualmente elaborare un piano alternativo per giungere alla destinazione prefissata.
In logica, l'ipotesi di conoscenza completa (o del mondo chiuso) afferma che tutti gli atomi veri siano stati comunicati al sistema. L'agente, quindi, considererà falsi tutti gli atomi che non sono stati espressamente dichiarati veri o per i quali la dimostrazione fallisca in un numero finito di passi.
Possiamo affermare che il robot lavora sotto questa ipotesi poiché prima di elaborare ed eseguire il piano conosce esattamente la sua posizione e quella di tutte le stanze; questa condizione si verifica esattamente quando l'agente non incontra alcun ostacolo sul suo cammino. Nel caso in cui siano presenti degli ostacoli, il robot deve acquisire informazioni circa la loro posizione, quindi opera in una situazione di informazione incompleta.
Il robot è stato realizzato utilizzando i mattoncini programmabili della serie Lego MindStorm NXT ® ricalcando la struttura del tribot, ovvero il modello di robot dotato di due ruote motrici e direttrici completamente indipendenti e di una terza ruota più piccola per la stabilità. Il tribot è predisposto per l'utilizzo di quattro diversi sensori; per i nostri scopi è stato sufficiente montare il sensore ad ultrasuoni accoppiato ad un terzo motore per estenderne il raggio d'azione.
Insieme al Mindstorm viene fornito NXT-G, un software di programmazione grafica basato su LabVIEW della National Instruments. Questo software è adatto per una programmazione di base, come il controllo dei motori e dei sensori e per fare calcoli; usa un interfaccia grafica che sfrutta il drag & drop per creare dei flussi di lavoro; in alternativa si possono usare l' NBC (Next Byte Code) o l' NXC (Not eXactly C): il primo è un linguaggio assembler-like, quindi a basso livello, il secondo è un linguaggio C-like.
Dopo alcuni tentativi di utilizzo del linguaggio NXC, a causa delle forti limitazioni che questo imponeva (non consentiva l'utilizzo di struct, l'allocazione dinamica della memoria e la multiprogrammazione) si è scelto di utilizzare LeJOS per le funzionalità offerte rispetto agli altri linguaggi, per esempio la possibilità di lanciare processi concorrenti, per l'ampio pacchetto di librerie disponibili e non ultimo, per la facilità di programmazione (essenzialmente si tratta di Java).
LeJos fu inizialmente concepito come TinyVM da José Solórzano che, nel 1999, iniziò per hobby a sviluppare un progetto open source. Si tratta di un firmware sostitutivo per il Mindstorm, che incorpora una Java Virtual Machine e quindi permette di eseguire programmi scritti in Java. Il nome LeJOS deriva dall'acronimo di Java Operating System (JOS) e legOS.
LeJOS offre tra le altre cose:
java.lang, java.util and java.iojava.lang.math)Il mondo è formato da un insieme di stanze collegate tra loro, realizzate con del cartone e del nastro adesivo. Le stanze comunicano tra di loro attraverso delle aperture nelle pareti (porte). Gli ostacoli sono delle pareti di cartone che è possibile spostare a piacere.
L'ambiente in cui il robot opera è suddiviso in stanze: ogni stanza è un'area rettangolare delimitata da quattro pareti.
All'interno di ciascuna stanza è poi definita “un'area di sicurezza” (PADDING) il cui scopo sarà descritto in seguito. Di tutte le stanze sono note le coordinate del vertice superiore sinistro e le dimensioni espresse in pollici.
L'insieme delle stanze S e delle coppie di stanze comunicanti C ⊂ P(C) costituisce un grafo connesso non orientato. Si è scelto di rappresentare tale grafo mediante un array di elementi di tipo stanza, ognuno dei quali conterrà una lista di riferimenti a quelli adiacenti. Il peso di ciascun arco (il cammino tra due stanze comunicanti) sarà stimato attraverso la distanza tra i loro centri.
La descrizione dell'ambiente viene trasmessa al robot attraverso alcuni file di configurazione.
Secondo l'ipotesi di conoscenza completa, l'agente considererà inaccessibile ogni area non mappata nel file stanze.txt. Ogni riga di questo file descrive completamente una stanza attraverso la quadrupla composta dalle due coordinate del suo vertice superiore sinistro e sue dalle dimensioni.
Due stanze i e j saranno considerate non comunicanti tra loro se nella matrice contenuta in collegamenti.txt (un file di testo che contiene la matrice di adiacenza del grafo delle stanze) non c'è un 1 in posizione i, j.
- import java.util.*;
- import java.io.*;
- public class Mondo
- {
- /* v è l'array delle stanze
- * (xi, yi) sono le coordinate della sorgente
- * (xf, yf) sono le coordinate della destinazione */
- private Vector v;
- public int xi, yi, xf, yf;
- public Mondo() throws Exception
- {
- FileInputStream f = new FileInputStream(newFile("config.txt"));
- this.xi = readInt(f);
- this.yi = readInt(f);
- this.xf = readInt(f);
- this.yf = readInt(f);
- f.close();
- if(xi == -1 || yi == -1 || xf == -1 || yf == -1)
- throw new Exception("file non valido");
- f = new FileInputStream(new File("stanze.txt"));
- v = new Vector();
- int[] array = new int[4];
- int i = 0;
- while((array[i] = readInt(f)) != -1)
- {
- if (i == 3)
- {
- Stanza s = new Stanza(array[0], array[1], array[2], array[3]);
- v.addElement(s);
- i = 0;
- }
- else i ++;
- }
- f.close();
- f = new FileInputStream(new File("collegamenti.txt"));
- for (i = 0; i < v.size(); i++)
- {
- Vector a = new Vector();
- for(int j = 0; j < v.size(); j++)
- {
- a.addElement(new Integer(readInt(f)));
- Stanza s = (Stanza) v.elementAt(i);
- s.setVector(a);
- }
- f.close();
- }
- /* Metodo per la lettura di un intero positivo da file */
- private int readInt(FileInputStream f) throws IOException
- {
- int b;
- int tmp = 0;
- while((b = f.read()) != -1)
- {
- if(b == 32 || b == 13) //CR o BLANK
- return tmp;
- else
- if (b < 48 || b > 57 )
- continue; //ignorati i caratteri non numerici
- else
- tmp = (tmp * 10) + (b - 48);
- }
- return -1;
- }
Gli “ostacoli” (pareti mobili in cartone) costituiscono delle particolari condizioni di errore nell'esecuzione del piano, poiché l'agente non è a conoscenza della loro eventuale disposizione. L'interazione tra agente ed ostacoli sarà descritta in maniera più approfondita nel paragrafo relativo al sensing.
L'algoritmo per l'elaborazione del piano altro non è che una visita del grafo.
In particolare, operando su un grafo finito e di ridotte dimensioni e conoscendo il peso di ogni arco, si è scelto di implementare un algoritmo che, sebbene oneroso dal punto di vista della memoria occupata, garantisce un risultato ottimo.
LOWEST-COST FIRST:
- INPUT(grafo G, nodo Sorgente, nodo Destinazione)
- Per ogni n, nodo del grafo G
- marca il n come non visitato
- imposta il costo di n a ∞
- Costruisci Q, coda di priorità
- Inserisci Sorgente in Q
- Marca Sorgente come visitato
- Imposta il costo di Sorgente a 0
- Finché Q non è vuota
- estrai p, primo elemento di Q
- per ogni elemento v nella lista degli elementi adiacenti
- di p
- se v non è ancora stato visitato
- marca v come visitato
- imposta p come padre di v
- imposta il costo di v uguale al costo di p
- sommato al peso dell'arco pv
- inserisci v in Q nella posizione corretta
- Crea PATH, lista di nodi
- Inserisci Destinazione in PATH
- Finché non arrivi a Sorgente
- prendi u ultimo nodo inserito
- inserisci p, padre di u in PATH
- OUTPUT(PATH)
Si tratta di una visita in ampiezza del grafo delle stanze, avente come nodo sorgente la stanza in cui il robot si trova all'inizio delle operazioni e come nodo destinazione quella in cui è situato il punto di arrivo. La frontiera viene gestita come una coda di priorità ordinata secondo il costo del cammino parziale tra la sorgente ed il nodo che viene inserito di volta in volta; vengono espansi per primi i cammini con costo più basso.
- /* Metodo della classe Mondo che implementa l'algoritmo
- * di visita */
- public Stack visita(int inizio, int fine)
- {
- Stanza stanza;
- PriorityQueue q;
- Stack s;
- for(int i = 0; i< v.size(); i++)
- {
- stanza = (Stanza) v.elementAt(i);
- stanza.setPadre(-1);
- stanza.setCosto(-1);
- }
- q = new PriorityQueue();
- q.insert((Stanza) v.elementAt(inizio));
- stanza = (Stanza) v.elementAt(inizio);
- stanza.setPadre(-2);
- stanza.setCosto(0);
- while(!q.isEmpty())
- {
- Stanza tmp = (Stanza) q.pop();
- Vector adiacenze = tmp.getVector();
- for(int i = 0; i < adiacenze.size(); i++)
- {
- Integer j = (Integer) adiacenze.elementAt(i);
- if (!j.toString().equals("0"))
- {
- stanza = (Stanza) v.elementAt(i);
- if(stanza.getPadre() == -1)
- {
- stanza.setPadre(v.indexOf(tmp));
- stanza.setCosto(stanza.distanza(tmp) + tmp.getCosto());
- q.insert((Stanza) v.elementAt(i));
- }
- }
- }
- }
- s = new Stack();
- for(int index = fine; index != -2;)
- {
- stanza = (Stanza) v.elementAt(index);
- s.push(stanza);
- index = stanza.getPadre();
- }
- return s;
- }
Una volta calcolato il piano è sufficiente scorrere a rovescio la lista dei padri per ottenere il cammino più breve dalla sorgente alla destinazione.
- /* Metodo della classe Movimenti che muove il robot al
- *centro della stanza */
- private void goRoom(Stanza s)
- {
- tn.goTo(s.getA(), s.getB());
- }
- /* Metodo della classe Movimenti che esegue il piano */
- public void run()
- {
- /* calcolo del piano */
- int inizio = mondo.owns((int)tn.getX(), (int)tn.getY());
- int fine = mondo.owns(mondo.xf, mondo.yf);
- Stack s = mondo.visita(inizio, fine);
- /* il piano viene eseguito passo per passo fino al suo
- * completamento o al presentarsi di una condizione di
- * errore */
- while(!killed && !s.empty())
- {
- try
- {
- Stanza room = (Stanza) s.pop();
- goRoom(room);
- }
- catch(Exception e)
- {
- LCD.drawString("Movimenti", 2, 4);
- LCD.refresh();
- }
- }
- if(!killed)
- {
- tn.goTo(mondo.xf, mondo.yf);
- Sens.finish = true;
- }
- }
- /* Arresta il robot */
- public void halt()
- {
- left.stop();
- right.stop();
- }
- /* Segnala la condizione di errore */
- public void kill()
- {
- killed = true;
- tn.updatePosition();
- }
Le operazioni di Sensing, attraverso le quali l'agente acquisisce informazioni sullo stato del mondo, devono essere eseguite con continuità durante l'esecuzione del piano, per poter rilevare la presenza di eventuali ostacoli lungo il percorso. Qualora la rilevazione individuasse un ostacolo “troppo vicino” al robot, questo deve interrompere ogni altra azione cercare di aggirarlo (o quantomeno fermarsi per evitare l'urto !!).
Queste esigenze impongono di strutturare il codice come un insieme di processi correlati tra di loro.
- import lejos.nxt.*;
- import lejos.navigation.*;
- import java.util.*;
- public class Sens extends Thread
- {
- private static final int BETA = 30;
- public static final int MIN = 30;
- private static final int SIGHT = 45;
- public static boolean finish = false;
- public static int offset;
- public static boolean enable = true;
- private UltrasonicSensor uss;
- private Movimenti movthread;//processo del piano generale
- private Drill drill;//processo della reazione
- private Mondo mondo;
- private Motor sensormotor;
- private boolean dead;
- private Stanza attuale;
- private TachoNavigator tn;
- private int distance;
- public void run()
- {
- while(!finish)
- {
- distance = sensing(); //rilevazione
- if(movthread.isAlive())
- {
- /* se un ostacolo viene rilevato il piano principale
- * viene interrotto */
- if(distance < MIN)
- {
- movthread.halt();
- attuale = mondo.getStanza(mondo.owns(movthread.getX(),movthread.getY()));
- tn = movthread.getTN();
- movthread.kill();
- }
- }
- else
- {
- /* avvio del comportamento reattivo */
- if(drill == null)
- {
- float theta = triangola(distance, tn);
- drill = new Drill(tn, theta, sensormotor, attuale);
- drill.start();
- }
- else
- {
- /* terminazione della reazione – breccia trovata */
- if(!drill.finished)
- {
- if(distance > SIGHT)
- {
- drill.halt(); /* entra */
- tn = drill.kill();
- tn.stop();
- tn.updatePosition();
- }
- }
- else
- {
- /* ripianificazione */
- drill = null;
- movthread = new Movimenti(mondo, tn);
- movthread.start();
- }
- }
- }
- }
- /* Metodo della classe Sens che legge dal sensore ad
- * ultrasuoni */
- private int sensing()
- {
- if(enable) //la lettura può essere disabilitata
- {
- int distance = uss.getDistance();
- try
- {
- this.sleep(250); //una lettura ogni 250 ms
- }
- catch(InterruptedException ie){}
- return distance;
- }
- return MIN;
- }
Non appena il sensore ad ultrasuoni rileva un ostacolo, viene immediatamente fermata l'esecuzione del piano principale. A questo punto l'agente reagisce e cerca di aggirare la parete. La reazione si può dividere in quattro fasi principali.
Una procedura determina con precisione (possono comunque verificarsi errori dovuti al sensore, agli attuatori ed alla rapresentazione interna dei numeri a virgola mobile) la posizione dell'ostacolo, ovvero l'angolo che la parete forma con l'asse delle ascisse.
- public float triangola(int distance, TachoNavigator TN)
- {
- /* situazione del robot "al momento dell'impatto"
- * comprensiva delle coordinate x ed y e dell'angolo
- * tra il robot e l'asse delle ascisse */
- int d = distance; /distanza tra robot ed ostacolo
- float x = TN.getX();
- float y = TN.getY();
- float alpha = TN.getAngle();
- int beta = BETA;
- sensormotor.rotate(beta); // ruota il sensore di beta gradi
- int r = uss.getDistance(); //lettura dal sensore
- try
- {
- this.sleep(250);
- }
- catch(InterruptedException ie){}
- /* se la lettura non ha dato un esito soddisfacente
- * (lettura nella breccia oppure parete troppo distante)
- * viene ripetuta dall'altra parte */
- if (r > SIGHT) //SIGTH è un'altra costante
- {
- beta = -beta;
- sensormotor.rotate(2 * beta);
- r = uss.getDistance();
- try
- {
- this.sleep(250);
- }
- catch(InterruptedException ie){}
- }
- sensormotor.rotateTo(offset); // riallinea il sensore
-
- /* un semplice calcolo trigonometrico */
- float gamma = (float)Math.toDegrees
- (Math.atan((r * Math.sin(Math.toRadians(alpha + beta)) -
- d * Math.sin(Math.toRadians(alpha)))
- / (r * Math.cos(Math.toRadians(alpha + beta)) -
- d * Math.cos(Math.toRadians(alpha)))));
- return gamma;
- }
Il robot orienta il sensore perpendicolarmente all'ostacolo e si muove parallelamente a questo, cercando un passaggio attraverso il quale passare. Se dovesse arrivare al bordo della stanza senza averlo trovato, riprenderà a muoversi in direzione opposta per controllare anche dall'altra parte.
Il robot conosce in ogni momento la sua posizione perché questa viene costantemente aggiornata. Poiché il sensore è impegnato nella ricerca del passaggio, non è possibile utilizzarlo per evitare le pareti della stanza (che il robot conosce). Per evitare che sbatta è stato introdotto un PADDING, ovvero un margine entro il quale il robot si ferma.
- /*Metodo run della classe Drill che fa muovere il mindstorm
- * per tutta la lunghezza dell'ostacolo */
-
- public void run()
- {
- Sens.enable = false;
- sx = riposiziona(gamma);
- Sens.enable = true;
- while(!killed) /* finchè il thread non viene ucciso */
- {
- if (forward && stanza.in(tn.getX(), tn.getY()))
- /* se vado avanti e sono nella stanza */
- {
- tn.forward();
- tn.updatePosition();
- }
- else
- {
- tn.stop();
- forward = false;
- }
- if(!forward && stanza.in(tn.getX(), tn.getY()))
- /* sono arrivato in fondo ma non c'è il passaggio */
- {
- tn.backward();
- tn.updatePosition();
- }
- else tn.stop();
- }
- tn.stop();
- if(!killed) /* non c'è nessun buco e il thread è attivo */
- {
- try
- {
- throw new Exception("TU NON PUOI PASSARE!");
- }
- catch(Exception e)
- {
- Sens.finish = true; /* blocco anche il sensore */
- tn.pilot.stop();
- LCD.drawString(e.getMessage(), 2, 2);
- LCD.refresh();
- }
- }
Una volta che il passaggio è stato individuato, posiziono il robot in modo che sia perpendicolare alla parete e lo attraverso.
- /* Quando il sensore rileva un passaggio, uccido il thread,
- * ma prima faccio attraversare il passaggio al robot */
- public TachoNavigator kill()
- {
- killed = true; /* dico al thread di uscire dai cicli */
- if(sx) /* ruoto di + o – 90 gradi */
- tn.rotate(-270);
- else
- tn.rotate(270);
- tn.updatePosition();
- sensormotor.rotateTo(Sens.offset); /* giro il robot */
- tn.travel(8); /* attraverso il passaggio */
- finished = true;
- return tn;
- }
Una volta superato l'ostacolo il robot ricalcola le sue coordinate ed elabora un nuovo piano verso la stessa destinazione.
- drill = null; /* inizializzo drill a null, in modo da *
- * poter evitare successivi ostacoli */
- movthread = new Movimenti(mondo, tn);
- /* faccio ripartire movthread con le nuove coordinate */
- /* movthread si ricalcolerà il piano */
- movthread.start();
Sito ufficiale di Lego Mindstorm NXT ®
Prove tecniche del sensore ad ultrasuoni.
Analisi meccanica dei servomotori.
LeJOS, Java per Lego Mindstorm.
Sito ufficiale Java
Libusb, driver usb per il mindstorm
Il corpo del robot è costituito da un mattoncino programmabile della serie Lego Mindstorms NXT.
Il sensore ad ultrasuoni è lo strumento di cui si serve il robot per analizzare lo spazio circostante.
Il robot può gestire fino ad un massimo di tre servomotori. Due di questi montano le ruote e vengono utilizzati per gli spostamenti all'interno dell'ambiente. La possibilità di controllare in modo indipendente la velocità ed il verso di rotazione di ogni motore permette alle ruote motrici di essere anche direttrici del movimento (similmente a quanto accade per i cingoli di un carro armato).
Il terzo motore, invece, viene utilizzato per estendere il “campo visivo” del sensore ad ultrasuoni ruotandolo in una direzione specifica.
Per una trattazione più completa delle problematiche di ambito meccanico (analisi del rapporto tra coppia applicata e velocità di rotazione
dell'albero motore) si può fare riferimento al materiale fornito da Lego oppure a quello presente in rete.
Scaricate installate Java JDK 6 Update 5.
Una volta conclusa l'installazione cliccate con il tasto destro del mouse su risorse del computer e scegliete proprietà: nuova schermata selezionate avanzate, poi variabili d'ambiente.
Cliccate nuovo e nella nuova finestra impostate una nuova variabile che si chiamerà JAVA_HOME avente come valore il percorso completo di java (di default è C:\programmi\java\jdk1.6.0_05) e confermate. Cercate la variabile PATH modificatela aggiungendo alla fine della riga ; ed il percorso della cartella java\bin (di default è C:\programmi\java\jdk1.6.0_05\bin).
L' NXT può essere collegato al computer via USB con il cavetto fornito dal costruttore oppure via Bluetooth. La comunicazione via USB è più affidabile e veloce, ma richiede l'installazione di alcuni.
Scaricate e installate il driver; una volta conclusa l'installazione riavviate il pc.
Scaricate LeJOS (è un archivio zip) decomprimetelo.
Copiate la cartella di lejos in C:\ .
Cliccate con il tasto destro del mouse su risorse del computer e scegliete proprietà: nella nuova schermata selezionate avanzate, poi variabili d'ambiente.
Cliccate nuovo e nella nuova finestra impostate una nuova variabile che si chiamerà NXJ_HOME avente come valore il percorso completo di lejos (per esempio C:\lejos_nxj) e confermate.
Cercate la variabile PATH modificatela aggiungendo alla fine della riga ; ed il percorso della cartella lejos\bin (C:\lejos_nxj\bin).
Per utilizzare LeJOS sul Mindstorm è necessario sostituire il firmware originale con il firmware di LeJOS: questa operazione installerà una Java Virtual Machine sul brick. Collegate l'NXT al pc con il cavo USB, accendetelo e aspettate che venga riconosciuto dal computer.
Con una graffetta premete il pulsante di reset per almeno 4 secondi: l' NXT emetterà un lieve suono ed entrerà in modalità aggiornamento firmware. Aprite il prompt dei comandi (start » tutti i programmi » accessori » prompt dei comandi) e nella nuova finestra digitate nxjflash.
