Robotica Evolutiva: Metodologia E Prospettive

Transcript

ROBOTICA EVOLUTIVA: METODOLOGIA E PROSPETTIVE Stefano Nolfi*, Dario Floreano**, Orazio Miglino***, Francesco Mondada**** *Istituto di Psicologia, C.N.R. 15, Viale Marx - 00187 - Roma e-mail: [email protected] **Laboratorio di Tecnologie Cognitive, AREA Science Park - Trieste e-mail: [email protected] ***Dipartimento di Psicologia, Universita' di Palermo Viale delle Scienze, Palermo e-mail: [email protected] ****Laboratorio di Microinformatica Politecnico Federale, Lausanne, Svizzera e-mail: [email protected] 1. INTRODUZIONE Negli ultimi anni sono stati proposti nuovi approcci basati su una forma di evoluzione simulata per costruire robot autonomi (Brooks, 1992; Cliff, Husband e Harvey, 1993). Il grande interesse suscitato da questi nuovi approcci e' sicuramente attribuibile alla disaffezione sia verso la robotica tradizionale che verso l'Intelligenza Artificiale ed al convincimento che robot realmente autonomi sono troppo difficili da realizzare. Le ragioni per cui la progettazione di sistemi di controllo per robot autonomi presenta serie difficolta' sono sostanzialmente le seguenti: a) E' estremamente difficile coordinare le parti di un robot autonomo, sia a livello della meccanica sia per quanto riguarda il sistema di controllo. Tale complessita', come e' stato sottolineato da Cliff, Harvey e Husbands (1993), cresce in modo esponenziale con l'aumento del numero di parti e di moduli che costituiscono il sistema. b) I robot autonomi interagiscono con un ambiente esterno ed e' estremamente difficile modellare questa interazione (Parisi, Cecconi e Nolfi, 1990; Gaglio, Esposito e Nolfi, 1994). In sistemi di questo tipo ogni azione motoria ha due differenti effetti (si veda Nolfi e Parisi, 1993): (1) determina l'efficienza dell'intero sistema rispetto ad un compito dato; (2) determina gli stimoli che saranno successivamente percepiti dal robot (questo ultimo punto ha un ruolo importante nel successo o fallimento di una sequenza di azioni). Poiche' ogni azione ha effetti anche a lungo termine e' estremamente difficile stabilire quale sia la migliore azione possibile in un dato momento. La robotica evolutiva supera questo tipo di problemi cercando di ottenere sistemi di controllo robotici attraverso un processo evolutivo e adattivo piuttosto che attraverso un processo di progettazione ingegneristica. Cio' non implica che i processi di adattamento e apprendimento siano prerogativa assoluta della Robotica Evolutiva. Meccanismi di apprendimento sono stati e sono utilizzati e studiati anche all'interno della Robotica "classica". Tuttavia il fatto che i processi di apprendimento ed evoluzione siano considerati centrali e fondamentali all'interno della Robotica Evolutiva ha come conseguenza il fatto che il modo di operare, le prospettive e i problemi che si incontrano all'interno di questo nuovo approccio sono spesso profondamente diversi da quelli tradizionali. 2. EVOLUZIONE VERSUS DESIGN I sistemi naturali sono sistemi che si autoorganizzano sviluppando una serie di strategie che permettono la sopravvivenza e la riproduzione. Al contrario, il modo in cui i sistemi artificiali devono svolgere il proprio compito e' di norma determinato da chi sviluppa il sistema. Il ricercatore o l'ingegnere che costruisce un sistema che debba svolgere un certo compito si preoccupa di determinare innanzitutto le risposte che il sistema deve produrre per ciascun possibile stimolo sensoriale e cerca quindi di disegnare il sistema in modo tale che esso produca effettivamente la risposta desiderata per ciascun possibile stimolo. Questa procedura implica che il modo in cui il sistema deve svolgere il compito e' determinato in anticipo. 2.1 Sistemi che interagiscono con un ambiente esterno. Nel caso di sistemi passivi (cioe' sistemi che ricevono passivamente gli stimoli sensoriali e non interagiscono con un ambiente esterno) puo' essere possibile determinare le risposte corrette che il sistema deve fornire. Nel caso di sistemi che interagiscono attivamente con un ambiente esterno invece (per es. nel caso di sistemi che possono modificare la propria posizione relativa rispetto agli oggetti esterni) e' estremamente difficile e probabilmente impossibile determinare le risposte corrette che il sistema deve produrre per ogni possibile stimolo. La ragione fondamentale per cui e' difficile determinare le risposte desiderate corrette per un sistema che interagisce con un ambiente esterno consiste nel fatto che sistemi di questo tipo determinano attraverso il loro comportamento gli stimoli sensoriali che ricevono in ingresso (se un robot autonomo decide di girare in una certa direzione percepira' un determinato stimolo, mentre se gira nella direzione opposta percepira' uno stimolo di tipo diverso). Non e' possibile sapere a priori quale tipo di stimoli il sistema incontrera' se non conosciamo le risposte che il sistema produce per ciascuno stimolo e anche se conoscessimo tali risposte potremmo non essere in grado di prevedere il tipo di stimoli che il sistema incontrera'. Come sottolineato sopra, e' importante considerare che ciascuna azione compiuta dal sistema ha due effetti diversi: (a) determina in che misura il sistema e' in grado di svolgere il proprio compito relativamente a quel particolare stimolo; (b) determina il tipo di stimoli che il sistema incontrera' successivamente. Entrambi questi effetti sono importanti per poter soddisfare adeguatamente il compito finale. Determinare la risposta motoria che il sistema deve dare in modo tale da essere esposto a stimoli utili successivamente (e quindi in modo tale da essere efficiente) e' estremamente difficile per diverse ragioni: (a) ciascuna risposta motoria del sistema puo' avere conseguenze a lungo termine; (b) gli effetti di ciascuna risposta del sistema sono funzione anche delle risposte motorie precedenti e successive che a loro volta possono avere effetti a lungo termine; (c) l'ambiente e il risultato dell'interazione tra il sistema e l'ambiente possono non essere completamente noti. In aggiunta a questo e' necessario notare che i due criteri usati per determinare la risposta desiderata (dare la migliore risposta possibile per lo stimolo contingente e dare una risposta che sia in grado di assicurare una buona successione di stimoli) a volte possono essere in contrasto e necessitano una soluzione di compromesso. Per queste ragioni pensiamo che la strada migliore per sviluppare sistemi che interagiscono con un ambiente esterno non sia quella di disegnare il sistema manualmente, bensi' di lasciare che il sistema progressivamente si adatti a svolgere il compito in questione attraverso un processo di auto-organizzazione. 2.2 La decomposizione funzionale. 2 Un'altra caratteristica distintiva dell'approccio "classico" alla robotica consiste nel fatto che la struttura interna del sistema, analogamente alle risposte desiderate, viene predeterminata. Il compito che il sistema deve svolgere viene scomposto in componenti funzionali (di norma tali componenti funzionali sono almeno tre: percezione, pianificazione e azione) e a ciascuna componente viene associato un diverso modulo del sistema. Questo tipo di approccio presenta il problema di modellare l'interazione tra le varie componenti del sistema; infatti, siccome ciascuna componente interagisce con le altre, in un approccio basato sulla progettazione, tali interazioni devono essere previste e controllate. Questo tipo di difficolta' ha spinto Brooks (Brooks, 1991) ad abbandonare l'idea della decomposizione funzionale e a proporre un approccio basato sulla decomposizione del comportamento desiderato. L'idea e' quella di identificare dei comportamenti indipendenti e di far corrispondere a ciascun comportamento un modulo del sistema di controllo. In questo modo il sistema di controllo puo' essere costruito progressivamente giustapponendo moduli capaci di produrre ciascuno il comportamento corrispondente. Tuttavia, sebbene l'idea di costruire gradualmente comportamenti piu' complessi sia interessante, non si vede come decomporre il sistema in strutture che corrispondono a comportamenti elementari - invece che a moduli funzionali - possa risolvere il problema della difficolta' di modellizzare l'interazione tra le componenti. L'approccio evolutivo si basa invece sull'auto-organizzazione e si pone come obiettivo quello di lasciare scegliere al sistema stesso non solo il modo in cui risolvere il compito dato, ma anche la struttura interna adatta a tale fine. Del resto occorre considerare che se non si conosce in anticipo il tipo di soluzione che il sistema trovera' non si puo' certamente determinare quale e' l'architettura interna piu' adatta ad implementare tale soluzione. Abbandonare la strada della progettazione non lascia altra via se non quella della completa auto-organizzazione del sistema. 3. COSA EVOLVERE E COME EVOLVERLO Per superare i problemi relativi alla progettazione di questo tipo di sistemi appare dunque ragionevole usare una procedura automatica come un algoritmo genetico (Holland, 1975), che gradualmente costruisce il sistema di controllo di un agente autonomo sfruttando le variazioni presenti all'interno di una popolazione di soluzioni durante il processo di interazione tra l'agente e il suo ambiente. L'idea sottostante l'algoritmo genetico e' semplice. Si genera una popolazione di individui (in questo caso sistemi di controllo per robot autonomi) casualmente diversi tra di loro (si crea cioe' una popolazione iniziale di individui) e si valuta l'efficienza di questi diversi sistemi rispetto al compito dato. Naturalmente l'efficienza di questi individui sara' inizialmente bassa in quanto i loro sistemi di controllo sono stati generati in modo casuale, ma proprio per questo motivo vi saranno delle differenze tra le varie prestazioni. Gli individui migliori di questa "generazione" iniziale (G0) hanno la possibilita' di riprodursi generando delle copie di se stessi con l'aggiunta di "mutazioni", ovvero di cambiamenti casuali dei parametri che li definiscono. L'insieme dei "figli" cosi' ottenuti dalla riproduzione degli individui migliori costituisce la generazione successiva (G1). Il processo viene quindi ripetuto per un certo numero di generazioni in modo da selezionare progressivamente individui che hanno ritenuto delle mutazioni adattive, cioe' dei cambiamenti che hanno prodotto un miglioramento della prestazione. Attraverso questo processo di selezione e mutazione (cioe' di introduzione di cambiamenti) si possono ottenere individui progressivamente piu' efficienti. Rimane tuttavia il problema di determinare " Cosa evolvere?" e "Come evolverlo?" 3 Per quanto riguarda la scelta di cosa evolvere sono state fatte proposte diverse. Alcuni autori hanno proposto di evolvere sistemi di controllo nella forma di programmi espliciti scritti in qualche linguaggio di alto livello. Brooks (1992) ad es., propone di usare un'estensione della tecnica di programmazione genetica di Koza (Koza, 1992). Dorigo e Schnepf propongono di usare una forma di "classifier system". Altri propongono di evolvere sistemi di controllo basati su reti neurali (Cliff, Husbands e Harvey, 1993; Floreano e Mondada, 1994a; Nolfi, Miglino e Parisi, 1994; Miglino, Nafasi, Taylor, in stampa). Noi riteniamo che quest'ultima proposta sia la via piu' promettente per una serie di ragioni: a) Le reti neurali possono facilmente sfruttare varie forme di apprendimento che possono favorire il processo evolutivo (Ackley e Littmann, 1991; Nolfi, Elman e Parisi in press) o possono migliorare il prodotto finale. b) Le reti neurali sono resistenti al rumore che e' massivamente presente nell'interazione robot/ambiente. Inoltre e' stato mostrato che introducendo rumore in una rete neurale si possono avere effetti benefici sul corso del processo evolutivo (Miglino, Pedone e Parisi, 1993). c) In accordo con Cliff, Harvey e Husbands (1993) riteniamo che le componenti primitive su cui opera il processo evolutivo debbano essere al livello piu' basso possibile per evitare di introdurre scelte non efficienti. Pesi sinaptici e nodi sono componenti primitivi di basso livello in quanto sono in grado di interagire direttamente con sensori e motori del robot senza richiedere alcuna interpretazione. Il "come" evolvere un sistema di controllo per robot autonomi, vale a dire la metodologia dettagliata da seguire durante il processo di evoluzione, e' invece un problema meno chiaro e meno studiato. Nelle sezioni seguenti ci concentreremo proprio sul problema di come evolvere agenti di controllo per robot autonomi. A questo scopo presenteremo tre diversi esempi di applicazione della metodologia evolutiva per lo sviluppo di reti neurali che controllino dei robot mobili e, nel far cio', discuteremo i vantaggi e gli svantaggi di ciascun approccio. Infine cercheremo di affrontare alcune questioni generali di carattere metodologico. 4. TRE ESEMPI DI ROBOTICA EVOLUTIVA REALIZZATI CON METODOLOGIE DIVERSE In questo paragrafo presentiamo tre diversi esempi di applicazione della metodologia evolutiva per lo sviluppo di sistemi di controllo per robot autonomi. Tutti e tre i casi riguardano l'evoluzione di un sistema di controllo basato su reti neurali con architettura fissa, ovvero non soggetta a cambiamenti durante il processo evolutivo (per esempi di modelli in cui sia l'architettura che i pesi della rete neurale sono soggetti ad evoluzione si veda Nolfi, Miglino e Parisi, in stampa). In tutti gli esperimenti le reti neurali sono costituite da uno strato di neuroni di ingresso che vengono attivati in base allo stato dei sensori del robot, uno strato di neuroni di uscita che determinano lo stato di attivazione dei motori del robot ed eventualmente uno strato di neuroni interni. In alcuni degli esperimenti esistono poi delle connessioni ricorrenti, ovvero delle connessioni fra neuroni dello stesso livello. Di conseguenza in alcuni casi lo stato di attivazione dei neuroni al tempo t puo' dipendere anche dallo stato di attivazione dei neuroni stessi al tempo t-1. In tutti gli esperimenti viene realizzato un processo evolutivo attraverso il quale vengono selezionati i pesi delle reti neurali. Viene creata una generazione iniziale di "genotipi" con valori generati casualmente che codificano i pesi delle corrispondenti reti neurali. Vengono quindi valutati i comportamenti generati da ciascuna rete neurale in base ad un criterio di efficienza detto "fitness". Infine vengono riprodotti i genotipi degli individui migliori. Il processo di riproduzione viene effettuato in due diverse modalita'. In un primo caso viene 4 simulato un tipo di riproduzione agamica in cui la riproduzione consiste nella "clonazione" del genotipo dell'individuo con l'aggiunta di mutazioni generate casualmente. In un secondo caso viene simulato un processo di riproduzione sessuata in cui, oltre alla presenza delle mutazioni, la variabilita' tra genitori e figlio e' dovuta anche al fatto che i genotipi dei genitori vengono incrociati mediante un operatore di ricombinazione (crossover). I vari esperimenti differiscono invece per la metodologia utilizzata. Nel primo esperimento il processo evolutivo e' condotto interamente sul robot reale. Nel secondo esperimento il processo evolutivo e' condotto interamente con una simulazione su computer e poi le reti neurali evolute vengono trasferite e osservate sul robot reale. Nel terzo esperimento il processo evolutivo e' condotto invece parte in reale e parte in simulato. Un'altra differenza importante riguarda il modo in cui sono stati realizzati i simulatori del secondo e del terzo esperimento. Nel secondo esperimento e' stato utilizzato un simulatore cha catturava in modo volutamente approssimativo le caratteristiche dell'ambiente mentre nel terzo esperimento il simulatore e' stato realizzato "campionando" l'ambiente reale attraverso i sensori e gli attuatori del robot fisico. 4.1 L'evoluzione di una abilita' di navigazione usando un robot fisico Floreano e Mondada (1994a) hanno addestrato delle reti neurali per il controllo di un robot autonomo che deve svolgere un compito di navigazione ed evitamento di ostacoli. Per questo esperimento gli autori si sono serviti di un micro-robot di fabbricazione svizzera chiamato Khepera. Il robot (Mondada, Franzi e Ienne, 1993) possiede una forma circolare con un diametro di 55 mm, un'altezza di 30 mm ed un peso di 70 g; esso si poggia su due ruote e su due piccoli supporti di Teflon. Le ruote, controllate da due motori DC, possono muoversi in entrambe le direzioni. Il robot dispone di 8 sensori di prossimita' all'infrarosso (sei posizionati sulla parte frontale del robot e due nella parte posteriore). Il microprocessore motorola 68331 con 256 Kbytes di RAM e di 512 Kbytes di ROM elabora tutte le routine input-output e puo' comunicare con un computer attraverso uno speciale cavo con contatti rotanti. Questa configurazione permette di sfruttare le capacita' di memoria del computer esterno che puo' essere usato per registrare e analizzare il comportamento del robot e nel contempo per fornire energia elettrica al robot evitando tutti i problemi di ricarica delle batterie. Figura 1. Khepera, il micro-robot mobile usato negli esperimenti di robotica evolutiva. L'ambiente in cui il robot agisce e' costituito da uno spazio piano delimitato da mura di forma irregolare. Le dimensione esterne di tale spazio sono approssimativamente 80x50 cm. Le mura sono state realizzate con del polistirolo celeste e il pavimento con un cartoncino grigio. Una lampadina di 60 watt e' stata usata per illuminare costantemente l'ambiente. 5 L'obiettivo degli autori e' quello di sviluppare un sistema di controllo per Khepera in grado di evitare ostacoli mantendo la traiettoria piu' lineare possibile e la velocita' piu' alta possibile. L'addestramento evolutivo e' stato realizzato implementando un algoritmo genetico standard (Goldberg, 1989) con generazioni composte da 80 individui ognuno dei quali puo' compiere 80 azioni. L'architettura della rete neurale e' fissa ed e' formata da un solo strato di pesi sinaptici che connettono gli otto sensori di Khepera con due unita' di uscita. Le unita' di uscita, direttamente collegate ai due motori di Khepera, hanno una soglia di attivazione adattiva, una funzione di attivazione sigmoide e connessioni ricorrenti. I pesi sinaptici e le soglie sono stati codificati nel genotipo come numeri reali. Ogni azione motoria dura 300 ms. La riproduzione degli individui e' sessuata e di conseguenza sono stati usati entrambi gli operatori genetici, mutazioni e crossover. Il criterio di fitness utilizzato (F) e' una funzione della velocita' di rotazione delle due ruote e dei valori di attivazione dei sensori di prossimita' con attivita' massima (I): F = V * (1 - sqrt ( DV ) ) * ( 1 - I ) F ha tre componenti: la prima e' massimizzata dalla velocita' (V), la seconda dal movimento in direzione rettilinea (DV indica la differenza di rotazione delle ruote) e la terza dall'evitamento di ostacoli (I e' tanto piu' grande quanto piu' il robot e' vicino a un ostacolo). E' importante notare che l'intero processo evolutivo viene realizzato interamente sul robot reale. Cio' significa che ogni rete di ogni generazione viene valutata lasciando il robot agire nell'ambiente reale per 80 passi (il "sistema nervoso" di ogni individuo viene sequenzialmente iniettato nel medesimo robot fisico). 0.3 fitness 0.2 0.1 0 0 10 20 30 40 50 60 70 80 90 100 generazioni Figura 2. Fitness del migliore individuo di ogni generazione. Il grafico mostra i valori medi e lo scarto quadratico medio di tre simulazioni (cioe' di tre processi evolutivi condotti partendo da generazioni iniziali casualmente diverse). In meno di 100 generazioni, Khepera evolve la capacita' di muoversi evitando gli ostacoli (figura 2). Comunque, gia' in prossimita' della 50-esima generazione i migliori individui esibiscono un comportamento quasi ottimale. Le loro traiettorie sono prive di punti spigolosi, gli ostacoli vengono evitati aggirandoli dolcemente senza urtare con le mura o incastrarsi negli angoli (per maggiori informazioni si veda Floreano e Mondada, 1994a). Ciascuna delle tre simulazioni richiede circa 60 ore. 4.2. L'evoluzione di un'abilita' di esplorazione usando un approccio simulato 6 Miglino, Nafasi, Taylor (in stampa) usando un programma software abbastanza semplice hanno addestrato delle reti neurali ricorsive a controllare un robot Lego che deve esplorare un determinato ambiente. La struttura del robot e' stata costruita con componenti Lego progettati per esperimenti di micro-robotica. Inoltre il sistema e' stato equipaggiato con un computer di bordo, un Miniboard 2.0 prodotto dal MIT Media Laboratory, (Cambridge, Massachusetts) che riceve dati da due sensori ottici collocati sulla struttura portante e controlla due piccoli motori. Il microprocessore e' un Motorola 6811 con 256 bytes di RAM e 12 Kbytes di ROM. Per ogni ingresso sensoriale il robot puo' compiere una delle seguenti quattro azioni: a) andare avanti di 10 cm.; b) andare indietro di 10 cm; c) girare a destra di 45 gradi; d) girare a sinistra di 45 gradi. Naturalmente, a causa di fattori perturbanti e imprevedibili (attrito, usura dei motori, piccoli problemi meccanici, ecc.), le risposte emesse possono variare di una certa misura rispetto all'azione programmata. Il compito del robot e' quello di esplorare la maggiore percentuale possibile di un'area rettangolare in un determinato numero di passi. Le dimensioni dell'area sono di 2,6 x 2,6 m. L'area non e' circondata da mura, ma la parte centrale (2 x 2 m) ha il pavimento di colore bianco mentre le fasce perimetrali sono di colore nero. Il livello di luminosita' dell'ambiente, non controllato, e' quello di una stanza normalmente illuminata. Il robot ha la possibilita' di compiere 400 passi per un totale di circa 10 minuti. Come sistema di controllo per tale robot e' stata scelta una rete neurale ricorsiva (Elman, 1990) con 2 unita' sensoriali, 2 unita' nascoste, 2 unita' di uscita ed 1 unita' di memoria. L'architettura di tale rete, a differenza dei pesi, e' fissa nel senso che non e' sottoposta a cambiamenti durante il processo evolutivo. L'intero processo di evoluzione e' stato condotto mediante simulazioni su computer. Di consegueza e' stato sviluppato un modello simulato che catturava in modo volutamente non molto preciso le caratteristiche del robot e dell'ambiente. L'ambiente e' stato modellizzato da una griglia di 26 x 26 celle dove ogni cella corrisponde a 10 cm quadrati e dove vengono conservate le relazioni di colorazione tra zona centrale e le fasce periferiche presenti nell'ambiente reale. Tuttavia in simulato, al contrario che nel mondo reale, il robot puo' occupare esclusivamente il centro di una cella (non puo' cioe' occupare due celle contemporaneamente). Di conseguenza, le azioni motorie dell'agente sono rappresentate in simulato come salti da una cella ad un'altra e i due sensori ottici percepiscono sempre il colore (bianco o nero) delle celle poste davanti e dietro al robot. Il genotipo di ogni individuo e' stato rappresentato da un vettore di 17 numeri interi ove ciascun numero codifica il valore del peso corrispondente. Ogni individuo viene posizionato 10 volte in modo casuale nell'ambiente simulato e per ogni riposizionamento ha la possibilita' di eseguire 400 passi. Gli individui vengono valutati in funzione di quante celle visitano per la prima volta in ognuno di queste 10 nuove partenze. Ogni generazione e' costituita da 100 individui di cui i migliori 20 (cioe' gli individui che visitano piu' celle nell'ambiente simulato) hanno la possibilita' di riprodursi generando ciascuno 5 figli. Il tipo di riproduzione e' agamico e di conseguenza le differenze tra padri e figli sono dovute esclusivamente alla presenza delle mutazioni (in particolare il 10% dei geni, cioe' dei valori dei pesi di ciascuna rete, vengono mutati in modo casuale durante il processo riproduttivo). Ciascuna simulazione e' stata interrotta dopo 600 generazioni e ha richiesto circa 3 ore di calcolo usando una SUN SparcStation 2. Le simulazioni hanno mostrato che il processo di evoluzione artificiale produce un comportamento esplorativo efficiente. Tre differenti individui rappresentativi di diverse fasi di una particolare simulazione sono poi stati trasferiti nel robot fisico e testati nell'ambiente reale. Malgrado le traiettorie del robot reale differiscano significatimente da quelle dello stesso sistema simulato, gli autori mostrano che la correlazione tra i valori di fitness osservati 7 nelle due condizioni sono abbastanza alti (0.73). Per maggiori informazioni si veda Miglino, Nafasi e Taylor (in stampa). 4.3 L'evoluzione di un'abilita' di navigazione usando un approccio ibrido (simulato/reale) Nolfi, Miglino e Parisi (1994) hanno sviluppato un sistema di controllo per robot mobili usando un approccio ibrido. Parte del processo evolutivo e' stato condotto mediante un modello simulato su computer e parte e' stato realizzato con il robot reale nell'ambiente fisico. Gli autori si sono serviti di Khepera, il robot descritto nella sezione 4.1. L'ambiente usato e' costituito da un recinto rettangolare di 60 x 35 cm circondato da mura di legno e con un ostacolo di 30 x 5 cm, sempre di legno, collocato al centro. Il modello simulato dell'interazione Khepera/ambiente e' stato realizzato campionando l'ambiente reale. In pratica si e' posto Khepera nel suo ambiente di fronte a un muro e si e' registrata l'attivazione dei sensori facendo compiere al robot dei giri di 360 gradi a distanze diverse rispetto al muro. Il livello di attivazione di ognuno degli otto sensori all'infrarosso sono stati campionati per 180 diversi orientamenti e per 20 diverse distanze. Analogamente e' stata campionata la variazione di angolo e la distanza percorsa da Khepera per ciascuno dei 20x20 stati possibili dei 2 motori. In sostanza, dunque, il simulatore e' stato basato esclusivamente sul campionamento del sistema senso-motorio di Khepera senza ricorrere a nessuna rappresentazione formale. Le informazioni ottenute con il campionamento vengono usate dal simulatore per determinare il livello di attivazione delle unita' di input della rete neurale a seconda della posizione corrente del robot simulato e per calcolare lo spostamento dello stesso robot in base all'attivazione dei motori durante la fase del processo evolutivo condotto in simulato. La forma fisica di Khepera, la struttura dell'ambiente e la posizione del robot sono stati riprodotti accuratamente nel simulatore. Anche in questo caso, l'architettura delle reti neurali e' fissa e consiste in una rete neurale feed-forward con 8 unita' di ingresso (che codificano lo stato degli 8 sensori all'infrarosso), 2 unita' nascoste e 2 unita' di uscita (che codificano lo stato dei due motori). I pesi delle connessioni sono stati rappresentati nel genotipo con dei numero reali. Ogni individuo e' stato valutato riposizionandolo due volte in modo casuale e lasciandolo libero di muoversi per 500 cicli o passi (ove ciascun passo passo corrisponde a 100 ms). La stessa funzione di fitness descritta del paragrafo 4.1 e' stata utilizzata in questo esperimento. Infine, durante il processo di evoluzione condotto nel computer e' stato aggiunto rumore (sotto forma di una variazione casuale aggiunta al valore di attivazione dei sensori). Sono state effettuate 3 diverse simulazioni. La prima parte di ogni esperimento, che e' stata interrotta dopo 300 generazioni, e' stata realizzata in simulato e ha richiesto circa 1 ora di calcolo su un IBM-RISC/6000. La popolazione di reti ottenuta in questo modo e' stata poi trasferita nell'ambiente reale dove il processo evolutivo e' stato proseguito per altre 30 generazioni (che hanno richiesto circa 30 ore per ciascuna simulazione). La figura 3 mostra le prestazioni della migliore rete di ogni generazione nell'ambiente simulato. La figura 4 mostra invece le prestazioni delle stesse reti evolute in simulato testate in reale e delle reti delle ultime 30 generazioni durante le quali il processo evolutivo e' stato condotto nell'ambiente reale. Come si puo' vedere, le prestazioni delle reti evolute decrescono significativamente se testate nell'ambiente reale. Tuttavia prestazioni simili a quelle ottenute nel modello simulato vengono ottenute continuando il processo evolutivo nell'ambiente reale per poche generazioni. Questo risultato mostra come nonostance non ci sia una corrispondenza perfetta tra modello simulato e ambiente reale, le reti neurali evolute in ambiente simulato riescono ad adattarsi facilmente (in poche generazioni) all'ambiente reale. 8 0.7 0.6 fitness 0.5 0.4 0.3 0.2 0.1 0 0 100 200 300 generazioni Figura 3. Prestazioni degli individui migliori per ogni generazione testati nell'ambiente simulato e scarto quadratico medio tra le diverse prove. 0.7 0.6 fitness 0.5 0.4 0.3 0.2 0.1 0 0 100 200 300 generazioni Figura 4. Prestazioni e scarto quadratico medio del migliore individuo di ogni generazione testato nell'ambiente reale. Le prime 300 generazioni sono state evolute nell'ambiente simulato, le ultime 30 generazioni rappresentano il risultato della continuazione del processo evolutivo nell'ambiente reale. 5. EVOLUZIONE IN SIMULATO O REALE L'esperimento descritto nel paragrafo 4.1 dimostra come sia possibile evolvere sistemi di controllo in reale, almeno nel caso di un compito semplice, anche se certamente cio' richiede dei tempi non contenuti. D'altro canto i due esperimenti successivi mostrano come l'evoluzione in simulato ha comunque una sua validita'. Come e' stato affermato da alcuni ricercatori (Brooks, 1992; Floreano e Mondada, 1994a) i modelli di robotica autonoma pubblicati in letteratura presentano una serie di problemi: a) L'attivazione dei sensori non dovrebbe essere confusa, come accade in molti modelli simulati, con la descrizione dell'ambiente. I sensori reali non separano gli oggetti dallo sfondo, non operano in sistemi di coordinate stabili, non ricevono informazioni relative alla posizione assoluta degli oggetti. b) Le simulazioni numeriche, generalmente, non considerano tutte le leggi fisiche di interazione di un agente reale con l'ambiente esterno come la massa, il peso, lo attrito, l'inerzia, ecc. 9 c) I sensori fisici forniscono valori imprecisi e i commandi degli attuatori hanno effetti incerti mentre, al contrario, i modelli simulati usano spesso ambienti a griglia e utilizzano dei sensori non affetti da rumore. d) Piccole differenze nell'elettronica e nella meccanica e piccole asimmetrie e irregolarita' nella struttura fisica dei robot possono produrre differenze nel comportamento di sensori e attuatori difficili da catturare nel modello simulato. Alcuni di questi problemi possono essere superati progettando il modello simulato in modo diverso. Per esempio, si dovrebbe evitare l'uso di sensori e funzioni di fitness che non possono essere implementati su un robot reale (vedi la sezione successiva). Inoltre, progettare i simulatori utilizzando un campionamento dell'ambiente reale, come mostrato nella sezione 4.3, puo' aiutare a catturare delle irregolarita' difficilmente rappresentabili con metodi formali (come ad es. il fatto che sensori uguali possono rispondere in modo diverso a causa della tolleranza dei componenti elettronici o a causa della posizione sul robot). Infine, nelle simulazioni e' opportuno aggiungere rumore sui sensori e sulla risposta generata dagli attuatori per tener conto del fatto che i sensori fisici e gli attuatori non sono perfetti. Miglino, Nafasi, Taylor (in stampa) hanno mostrato peraltro che e' possibile stimare la quantita' opportuna di rumore da introdurre in simulato confrontando il comportamento del robot in simulato con l'aggiunta di diversi livelli di rumore con il comportamento dello stesso robot in reale. Gli esperimenti descritti nelle sezioni 4.2 e 4.3 mostrano come questo tipo di accorgimenti possano essere utilizzati con successo in modelli simulati e di conseguenza come molte delle difficolta' descritte sopra possano essere attenuate. In ogni caso non ci si puo' aspettare che i modelli simulati possano essere sofisticati al punto da eliminare completamente la discrepanza tra ambiente simulato e reale e, d'altra parte, questo non appare necessario. E' sufficiente che vi sia una correlazione significativa tra le prestazioni dello stesso sistema nei due ambienti (simulato e reale). Se cio' si verifica ci si puo' aspettare che, continuando il processo di evoluzione in reale, sia necessario un numero limitato di generazioni per ottenere sistemi perfettamente adattati (come abbiamo mostrato nella sezione 4.3). Da questo punto di vista l'evoluzione in ambienti simulati puo' essere interpretata come una selezione per caratteri correlati e il trasferimento dall'ambiente simulato all'ambiente reale puo' essere visto come una modifica ambientale alla quale e' possibile adattarsi (Prof. Charles Taylor, comunicazione personale; ma si veda anche Falconer, 1981). E' possibile perseguire anche altri tipi di approcci ibridi: per esempio, gli individui maggiormente promettenti di una popolazione che si evolve in un ambiente simulato possono essere testati negli ambienti reali, oppure si possono effettuare test negli ambienti reali a intervalli di tempo prestabiliti durante il processo evolutivo. Un'altra importante ragione che giustifica l'uso di modelli simulati e' il fatto che la simulazione permette lo svolgimento di test preliminari per verificare se le scelte effettuate nella preparazione di un esperimento evolutivo (quali la formula di fitness, il numero di tempo a disposizione di ciascun individuo ecc) siano appropriate, riducendo significativamente il tempo richiesto per il processo evolutivo. E' noto infatti che gli algoritmi genetici sono molto sensibili alle condizioni iniziali e di conseguenza la ripetizione dello stesso esperimento con parametri di partenza casualmente diversi puo' portare a risultati significativamente diversi. L'evoluzione in ambienti simulati puo' permettere di indagare quali insiemi di parametri e condizioni iniziali producono risultati robusti ed efficaci. In questo modo l'esperimento puo' essere condotto in reale una sola volta utilizzando i parametri che sono risultati migliori in simulato con una speranza ragionevole di ottenere buoni risultati. E' probabile che man mano che i problemi studiati diventaranno piu' complessi sara' sempre piu' difficile costruire simulatori che producano comportamenti correlati nella simulazione e nel reale. Nonostante cio' noi pensiamo che, almeno per il momento, l'uso della simulazione puo' svolgere un ruolo importante nella robotica evolutiva. 10 6. LA VALUTAZIONE AUTOMATICA DEGLI INDIVIDUI Lo sviluppo di un sistema di controllo per agenti autonomi implica la valutazione di un numero molto alto di individui. Cio' spinge ad adottare una via automatica alla valutazione degli individui. Il criterio di fitness, quindi, deve basarsi esclusivamente su informazioni che il robot puo' ricavare dai suoi sensori interni o esterni. La funzione di fitness usata nelle sezioni 4.1 e 4.3 e' un buon esempio di criterio di valutazione che puo' essere determinato automaticamente poiche' usa informazioni disponibili al robot (in particolare il livello di attivazione dei sensori all'infrarosso e lo stato di attivazione dei due motori). Viceversa, la funzione di fitness usata nelle simulazioni descritte nella sezione 4.2 e' di difficile applicazione in ambienti reali a meno che non si abbia a disposizione uno strumento che registri la posizione esatta del robot. Nelle simulazioni tutte le informazioni sono utilizzabili e percio' il criterio di fitness puo' essere stabilito arbitrariamente. D'altra parte occorre considerare che anche se ci si propene di realizzare l'intero processo evolutivo in un ambiente simulato, la scelta di una formula di fitness calcolabile solo in simulato puo' rendere difficile, se non impossibile, la valutazione delle prestazioni del robot nell'ambiente reale. Per ovviare a questo tipo di problema si possono utilizzare dei sensori dedicati esclusivamente alla valutazione della fitness. In alcuni esperimenti che stiamo conducendo, ad esempio, cerchiamo di addestrare un robot a fermarsi davanti ad un oggetto di piccole dimensioni e a ignorare oggetti di grandi dimensioni. In questo caso, per consentire la valutazione automatica della fitness degli individui, abbiamo dipinto di nero la porzione di pavimento circostante agli ostacoli di piccole dimensioni. Inoltre, abbiamo collocato nella parte inferiore del robot un sensore all'infrarosso in modo che fosse possibile registrare il colore del pavimento nella posizione corrente al fine di determinare se il robot sia posizionato o meno vicino ad un oggetto di piccole dimenzioni. E' importante osservare che questo sensore non e' accessibile alla rete neurale che controlla il comportamento del robot, ma serve esclusivamente per calcolare la fitness dell'individuo. Di conseguenza, una volta terminato il processo evolutivo, le zone nere sul pavimento possono essere romosse senza che il comportamento del robot ne risenta in alcun modo. 7. VINCOLI HARDWARE L'approccio evolutivo pone dei vincoli sulla costruzione del robot fisico assai diversi rispetto all'approccio classico. Negli approcci piu' tradizionali, nei quali la progettazione passa obbligatoriamente attraverso una fase di modellizzazione, si pongono delle condizioni importanti e molto restrittive a chi deve sviluppare l'hardware del sistema. In effetti, nella modellizzazione dell'interazione tra macchina e mondo esterno, la modellizzazione del robot stesso e' un punto importante di cui occorre tenere conto al momento della progettazione affinche' la modelizzazione sia non solo fattibile, ma possibilmente semplificata. Ne conseguono scelte di sensori con caratteristiche il piu' lineari possibile, di attuatori con gradi di liberta' minimi ma geometricamente ottimali, di schemi elettronici in grado di fornire misure estremamente precise e con un livello di rumore ridotto al minimo ecc. Purtoppo, in un mondo reale fatto di non linearita', di imprecisioni, di geometrie bizzarre e di rumore su molte grandezze fisiche, questi sistemi possono rivelarsi inefficienti. L'approccio evolutivo, rimandando la scelta della struttura di controllo al processo di selezione e mutazione, pone unicamente delle condizioni generali di sufficienza funzionale dei sensori e attuatori utilizzati. Queste condizioni devono essere anch'esse valutate, ma questa valutazione puo' essere semplificata in modo considerevole con l'aumento del numero di dispositivi. I sistemi robotici appropriati per questo approccio dovranno dunque essere 11 dotati di sensori numerosi ed eventualmente ridondanti ma fondamentalmente semplici, senza correzioni di linearita', protezioni contro i rumori o sistemi di misura sofisticati. E' compito del meccanismo evolutivo fare buon uso delle non linearita' o correggerle e di combinare varie misure per ricavarne le informazioni necessarie al funzionamento del sistema. Infine occorre notare che anche i mezzi di lavoro vengono modificati. Nell'approccio classico la modellizzazione svolge un ruolo fondamentale e l'analisi del comportamento si riduce ad una verifica del modello. Nell'approccio evolutivo la parte di modellizzazione si riduce drasticamente per lasciare piu' spazio all'analisi, punto chiave dell'approccio. E' dunque necessario dotarsi di mezzi che permettano una migliore osservazione del comportamento del robot, affinche' la valutazione automatizzata e il controllo del risultato siano facilitati. Il robot Khepera e' un tentativo di sviluppo in questa direzione. I suoi dispositivi sensoriali sono in effetti molto semplici, pur coprendo in modo sufficiente una gamma interessante di esperimenti. Come abbiamo mostrato piu' sopra, nella versione di base Khepera e' dotato di otto sensori di prossimita' basati sull'emissione e sulla ricezione di luce infrarossa. Questi sensori permettono sia una misura della luce infrarossa ambientale che una misura di prossimita' di ostacoli basata sulla riflessione della luce emessa dal robot. Queste misure non sono molto precise, non hanno caratteristiche lineari e dipendono fortemente da fattori esterni come il materiale con cui sono realizzati gli ostacoli, il loro colore, il tipo di illuminazione ecc. Inoltre si possono aggiungere facilmente sensori addizionali grazie a una buona modularita' hardware e software del sistema. Infine, i mezzi di lavoro sviluppati attorno a questa piattaforma sperimentale e la sua stessa miniaturizzazione sono rivolti in modo chiaro nella direzione dell'analisi, piuttosto che in quella della progettazione classica. Khepera e' infatti stato progettato per poter essere facilmente utilizzato su un tavolo, di fianco a una stazione di lavoro e collegato con quest'ultima tramite una linea seriale che permette nello stesso tempo l'alimentazione del robot. Questo tipo di configurazione facilita fortemente la sperimentazione e l'osservazione dei comportamenti risultanti. Inoltre la robustezza di Khepera lo rende ideale per lo svolgimento di simulazioni di lunga durata durante le quali il robot puo' avere comportamenti patologici (dovute alla variazione intrinseca nelle popolazioni di individui), andando a urtare violentemente contro le pareti o spingendo contro di esse. Grazie a qualche accorgimento molto semplice (pareti in poliuretano espanso) e alle leggi fisiche che danno maggior resistenza meccanica relativa a oggetti ridotti omoteticamente, questi esperimenti possono svolgersi senza alcun problema. 8. CONCLUSIONI L'approccio evolutivo alla robotica autonoma presenta certamente delle potenzialita' interessanti. Tuttavia a causa della novita' dell'approccio e del cambiamento radicale di prospettiva che esso implica rispetto alla robotica classica, appare necessario cercare di formalizzare una metodologia appropriata per l'uso di questo approccio in robotica. In questo articolo abbiamo cercato di evidenziare i problemi metodologici piu' importanti e abbiamo cercato di fornire alcune risposte a questi problemi presentando e comparando tra loro tre esempi diversi di applicazione di tecniche evolutive a robot reali. I risultati dei nostri esperimenti mostrano che l'evoluzione di sistemi di controllo per agenti autonomi in reale e' possibile anche se richiede tempi considerevoli (si veda la sezione 4.1). Abbiamo discusso il ruolo della simulazione mostrando modi diversi in cui essa puo' essere usata. In particolare abbiamo mostrato come in alcuni casi anche un modello molto approssimativo del robot e dell'ambiente reale puo' essere sufficiente per evolvere sistemi di controllo che possono successivamente essere trasferiti al robot fisico (sezione 4.2). Inoltre abbiamo discusso alcuni accorgimenti che possono ridurre significativamente la discrepanza tra l'ambiente reale e quello simulato. In particolare, abbiamo mostrato come progettare il 12 simulatore campionando l'ambiente reale attraverso i sensori e gli attuatori del robot fisico puo' produrre un modello che cattura in modo piu' accurato l'interazione tra un particolare robot e l'ambiente relativo (si veda la sezione 4.3). Infine abbiamo mostrato come un approccio ibrido in cui parte dell'evoluzione viene condotta in simulato e parte in reale possa superare il fatto che non e' comunque possibile aspettarsi una completa identita' tra ambiente simulato e reale (si veda la sezione 4.3). Oltre a questo tipo di problemi metodologici, un problema importante e' verificare se questo tipo di approccio possa essere applicato a compiti significativamente piu' complicati di quelli descritti in questo articolo. In particolare appare opportuno cercare di identificare quali tipi di compiti si adattano meglio all'approccio evolutivo. Riguardo a questo punto ci stiamo muovendo in piu' direzioni. In un recente esperimento Floreano e Mondada (1994b) hanno dotato l'ambiente di una zona, segnalata da una sorgente luminosa, dove il robot puo' caricare autonomamente le sue batterie. Il robot e' equipaggiato con alcuni sensori di intensita' luminosa, il criterio di fitness e' esattamente il medesimo di quello utilizzato per il compito di evitamento di ostacoli. La differenza rispetto agli esperimenti descritti nelle sezioni 4.1 e 4.3 e' che, se il robot attraversa la zona di ricarica-batteria, esso puo' aumentare la propria autonomia e conseguentemente prolungare la propria vita. Il robot apprende a svolgere questo compito perfettamente, ritornando periodicamente nella zona di ricarica e sfruttando prima al massimo la propria riserva energetica. Questo comportamento emergente di homing (ritorno al nido) appare basato sullo sviluppo di una mappa topografica interna che permette al robot di scegliere la traiettoria appropriata in funzione della sua posizione e della suo livello di energia. In un altro esperimento recente gli autori hanno affrontato il problema del riconoscimento di oggetti e della coordinazione sensomotoria per il raccoglimento utilizzando un Khepera equipaggiato con un sistema di bracci meccanici (Floreano e Mondada, 1994c). Nell'ambiente di azione del robot sono distribuiti degli oggetti e degli ostacoli. Gli oggetti, come accade in situazioni naturali, hanno diverse forme e dimensioni. Il robot dovrebbe apprendere autonomamente ad approcciare solo gli oggetti che possono essere catturati e rimossi con il suo braccio meccanico. RINGRAZIAMENTI Ringaziamo Domenico Parisi e Charles Taylor per i loro commenti e suggerimenti. Dario Floreano ha potuto fare questa ricerca grazie al Progetto Finalizzato C.N.R. grant n. 93.01065.PF67 (nell'ambito dell'unita' operativa coordinata dal prof. Walter Gerbino), Francesco Mondada grazie alla Fondazione per la Ricerca Scientifica Svizzera (project n. PNR23) e Stefano Nolfi e Orazio Miglino grazie al Progetto Finalizzato "ROBOTICA", C.N.R (nell'ambito dell'unita' operativa coordinata dal prof. Domenico Parisi). RIFERIMENTI BIBLIOGRAFICI Ackley D. H., Littman M. L. (1991), Interactions between learning and evolution, in C. G. Langton, J. D. Farmer, S. Rasmussen, C. E. Taylor (a cura di), Artificial Life II, AddisonWesley. Reading, Mass. Brooks R. A. (1991), New approaches to robotics. Science 253:1227-1232. Brooks R. A. (1992), Artificial life and real robots, in F. J. Varela, P. Bourgine (a cura di), Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life, Cambridge, MA: MIT Press/Bradford Books. 13 Cliff D. T., Harvey I., Husbands P. (1993), Explorations in Evolutionary Robotics. Adaptive Behavior 2: 73-110. Dorigo M., Schnepf U. (1993), Genetis-based machine learning and behavior based robotics: a new syntesys. IEEE Transaction on Systems, Man and Cybernetics, 23:141,153. Elman J. L. (1990), Finding structure in time. Cognitive Science, 2: 179-211. Falconer D. S. (1981), Introduction to Quantitative Genetics, Longman, London. Floreano D., Mondada F. (1994a), Automatic Creation of an Autonomous Agent: Genetic Evolution of a Neural-Network Driven Robot, in D. Cliff, P. Husbands, J. Meyer, S. W. Wilson (a cura di), From Animals to Animats 3: Proceedings of Third Conference on Simulation of Adaptive Behavior, MIT Press, Bradford Books. Floreano D., Mondada F. (1994b), Emergent homing behaviour in a mobile robot. Rapporto Tecnico LAMI n. DF94.14I, Swiss Federal Institute of Technology, Lausanne. Floreano D., Mondada F. (1994c), Active Perception: Navigation, Homing, and Grasping: An Autonomous Perspective, in P. Gaussier, J.-D. Nicoud (a cura di), Proceedings of the International Conference From Perception to Action, IEEE Computer Society Press, Los Alamitos, CA. Gaglio, Esposito F., Nolfi S. (1994), Perceptual Learning and Discovering, in V. Cantoni (a cura di), Human and Machine Vision. Analogies and Differencies, New York, Plenum Press, pp. 371-383. Goldberg D. E. (1989), Genetic Algorithms in Search, Optimization and Machine Learning. Reading, Mass.: Addison Wesley. Holland J. H. (1975), Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor. Koza J. R. (1992), Genetic Programming: the programming of computers by means of natural selection. Cambridge, MA, MIT Press. Miglino O., Pedone R., Parisi D. (1993), A noise Gene for Econets. In Proceedings of Genetic Algorithms and Neural Networks, Reading, Mass.: Addison Wesley. Miglino O., Nafasi K., Taylor C. (in stampa), Selection for Wandering Behavior in a Small Robot. Artificial Life. Mondada F., Franzi E., Ienne P. (1993), Mobile Robot miniaturisation: A tool for investigation in control algorithms. In Proceedings of the third International Symposium on Experimental Robotics, Kyoto, Japan. Nolfi, S., Elman J. L., Parisi D. (in stampa), Learning and Evolution in Neural Networks. Adaptive Behavior. 14 Nolfi, S., Miglino O., Parisi D. (1994), Phenotypic Plasticity in Evolving Neural Networks, in D. P. Gaussier e J-D. Nicoud (a cura di), Proceedings of the International Conference From Perception to Action, Los Alamitos, CA: IEEE Press Nolfi, S., Parisi D. (1993), Self-selection of input stimuli for improving performance, in G. A. Bekey (a cura di), Neural Networks and Robotics, Kluwer Academic Publisher. Parisi, D., Cecconi F., Nolfi S. (1990), Econets: Neural networks that learn in an environment. Network 1:149-168. Parisi, D., Nolfi S. (in press), How learning can influence evolution within a non-Lamarckian framework, in R. K. Belew, M. Mitchell (a cura di), In Plastic Individuals in Evolving Populations, SFI Series, Addison-Wesley 15