fig 1: particolare del braccio meccanico
Mario Danzo e Ivo Fumagalli – Marzo 2008
Quattro piedistalli e tre palline colorate, una blu, una rossa e una gialla, ognuna su un piedistallo. Un braccio meccanico con sensori in grado di spostare una pallina per volta dalla sua posizione sul piedistallo vuoto e vedere il colore delle palline.
Per risolvere il problema abbiamo realizzato un braccio meccanico con Lego Mindstorm NXT. Il robot comprende diversi sensori dividibili in due categorie: sensori per il movimento del robot e sensori per comprendere il mondo circostante.
fig 1: particolare del braccio meccanico
La struttura comprende anche una base in legno con dei fori per tenere i piedistalli e un cubo che indica la fine corsa.
Per scrivere il pianificatore abbiamo deciso di utilizzare interamente URBI. Le prestazioni non potranno sicuramente essere paragonate a linguaggi compilati di più basso livello come il C++, ma abbiamo ritenuto interessante fare questo esperimento per vedere se i tempi di calcolo diventano proibitivi o se effettivamente il carico di lavoro per il processore non è così eccessivo.
Le posizioni dei piedistalli sono come in figura, l’obiettivo è quello di raggiungere la seguente configurazione: in posizione 1 la sfera blu, nella 2 la rossa nella 3 la gialla e la posizione 4 rimane vuota.
fig 2: robot e ambiente (esempio)
Per far questo bisogna:
Possiamo pensare al problema partendo da un livello base/macchina che corrisponde al nucleo operativo che esegue le azioni, ad un livello intermedio ci sono le funzioni primitive usate per controllare direttamente il robot, poi le funzioi derivate da quelle primitive usate per compiti di più alto livello. Ad un livello più astratto è presente il pianificatore che risolve il problema.
fig 3: schema dei vari livelli di astrazione del problema
Lo stato del sistema è dato dalle posizioni delle tre palline e del piedistallo vuoto. Internamente l’abbiamo rappresentato con un array di quattro elementi.
Per esempio lo stato in figura2 è così descritto: [“blu”,“rosso”,“giallo”,“vuoto”]
I cambiamenti di stato avvengono tramite la funzione sposta(colore), che fa spostare la sfera di quel colore sul piedistallo vuoto
Quindi considerando il seguente stato: [“blu”,“giallo”,“rosso”,“vuoto”]
ed eseguendo la mossa sposta(“rosso”)
si raggiunge lo stato: [“blu”,“giallo”,“vuoto”,“rosso”].
fig 4: esempio di transizione di stato mediante un’azione
Le funzioni si dividono in funzioni primitive che sono responsabili del controllo diretto del robot e le funzioni derivate che implementano funzioni più complesse.
scendi, gira, sali, chiudi, apri RETURN NULL
guarda RETURN colori[]
vai, azzera, sposta RETURN NULL
dove RETURN posizione.
A causa di un’incorretta gestione degli array da parte di URBI non abbiamo potuto lavorare direttamente su di essi, ma siamo stati costretti a creare delle funzioni personalizzate per la gestione di queste strutture dati. In questo modo però le prestazioni del pianificatore sono calate notevolmente.
Tutte queste funzioni restituiscono un array
Il tempo di calcolo per tutte queste funzioni è lineare rispetto alla dimensione dell’array di input
f, g, h, RETURN float
eurmin RETURN stato
elencomosse RETURN array
stessopadre RETURN boolean
f, g, h, hanno tempo di calcolo costante, mentre eurmin, elencomosse e stessopadre hanno tempo di calcolo lineare
L’algoritmo di pianificazione utilizza un albero in cui i nodi rappresentano gli stati in cui si può trovare il robot, in particolare la radice è lo stato iniziale esplorato dai sensori, mentre gli archi che li collegano rappresentano le azioni che fanno evolvere il sistema da uno stato ad un altro
fig 5: esempio di albero del pianificatore
Abbiamo utilizzato come algoritmo di ricerca A*, in cui per ogni nodo p il valore di f(p) è la somma dell’euristica h e del costo g: f(p) = h(p) + g(p)
La funzione euristica h(p) assegna ad ogni pallina nella posizione scorretta una penalità di 1 mentre il vuoto in una posizione corretta ha una penalita di 1/2. Questo perché è più sfavorevole avere il buco nella posizione giusta e quindi ci vorranno più mosse per raggiungere l’obiettivo.
L’euristica cosi definita è una sottostima delle mosse necessarie per raggiungere l’obiettivo.
fig 6: calcolo del valore dell’euristica per un nodo
La figura 7 mostra intuitivamente che far eseguire due volte consecutivamente la stessa mossa lo stato non si modifica, quindi abbiamo sfruttato questo fatto per ottimizzare il pianificatore riducendo di 1/3 il numero dei nodi calcolati e introdotti in frontiera.
fig 7: eseguire due volte consecutivamente la stessa mossa non modifica lo stato
Per evitare la formazione di cicli all’interno dell’albero di ricerca e quindi limitare ulteriormente il numero di nodi visitati, prima di inserire un nuovo nodo nell’albero cerchiamo se nel percorso a ritroso, dal padre alla radice esiste già un altro nodo che rappresenta uno stato con la stessa configurazione, quindi inseriamo questo nuovo nodo solo se la ricerca ha esito negativo.
La dimensione della frontiera varia in base allo stato di partenza. Nel caso peggiore (rosso - giallo - blu - vuoto) si raggiungono al massino 12 stati presenti contemporaneamente, quindi anche un linguaggio interpretato come URBI riesce a gestire questo problema.
Problemi relativi al sensore della luce sono stati dovuti ad un limite tecnico del sensore e alle differenze di visione durante la giornata. Problemi maggiori ne abbiamo avuti nella distinzione della sfera rossa e di quella gialla, molte volte le vedeva troppo simili. Per l’esperimento quindi si è scelto di operare in ambiente standard con luce completamente artificiale.
Il sensore ad ultrasuoni del lego è risultato molto impreciso soprattutto nei tempi di risposta. Questo ha causato problemi soprattutto nella ricerca del blocco di fondo corsa. Nonostante l’introduzione di un soft-test la precisione non è aumentata sufficientemente.
Lo stesso problema è stato riscontrato anche da un altro gruppo che ha programmato in Java e ha sostituito il firmware standard con LeJos.
Essendo urbi un linguaggio interpretato e ad alto livello risulta più lento nella pianificazione rispetto a linguaggi compilati più vicini al codice macchina come per esempio il C++.
I tempi di calcolo sono di circa un secondo per ogni stato visitato, sicuramente un tempo eccessivo per problemi più complessi, ma accettabile nel nostro caso dove non vengono mai visitati più di 15 stati.
Al termine di questo lavoro possiamo quindi affermare che questo ambiente di programmazione non è adatto per svolgere compiti che fanno ampio uso di strutture dati, e CPU.
Durante il progetto è capitato diverse volte che il lego si spegnesse o che perdesse il controllo dei sensori. Questo tipo di comportamento presumiamo sia dovuto ad un problema di comunicazione tra la centralina NXT e URBI. Effettuando delle ricerche su internet non siamo riusciti a trovare analogie con altre persone.
Lasciare ad URBI il compito di pianificare una soluzione è veramente sconsigliabile, serve sicuramente un linguaggio di programmazione più efficiente. URBI offre librerie Java e C++, sarebbe quindi possibile riscrivere il progetto in uno di questi due linguaggi, e comandare il robot importando le sue librerie.
Esistono sensori compatibili con il lego mindstorm1 che potrebbero migliorare l’interazione del robot con l’ambiente.
1 http://www.lswn.it/robotica/articoli/robot_sensori_e_comportamenti_intelligenti
http://complubot.educa.madrid.org/sensores/sensor_temperatura/sensor_temperatura_index.php
http://digilander.libero.it/Valter_NXT/elenconxt.html