Robot che si auto-organizzano

 

Tutto e’ iniziato nel 2011 quando i ricercatori in robotica dell'Universita’ di Harvard costruirono per la prima volta i loro 25 robot. Nel 2013 erano diventati 100 e oggi 1000. I ricercatori Michael Rubenstein, Alejandro Cornejo, e il professore Radhika Nagpal  del gruppo Self-Organizing Systems Research descrivono i loro 1000 robot, chiamati swarm robot in quanto imitano uno sciame di insetti, in un articolo apparso sulla rivista Science alcuni mesi fa. In effetti, si tratta di 1024 robot che nell’ambito dei computer e’ l’equivalente del chilo. Per questo motivo questi robot vengono chiamati anche kilobot.

Ogni kilobot e’ un piccolo dispositivo, dal costo irrisorio ($14), che puo’ muoversi grazie a delle gambe vibranti e comunicare con altri robot grazie a dei trasmettitori/ricevitori agli infrarossi.

Lo sciame ha un numero sufficiente di piccoli robot da ridurre l’importanza del singolo. Se qualcuno dei robot si rovina o si rompe non e’ un problema visto l’elevato numero dello sciame. Prevale il comportamento collettivo su quello del singolo. Con cosi tanti robot qualsiasi operazione e' complicata. Un esempio e’ il loro caricamento. Mettere ognuno dei 1024 robot sul loro rispettivo caricabatteria non e’ cosa da poco. Per questo motivo i ricercatori hanno pensato di usare due placche metalliche con i robot inseriti tra loro che si caricano grazie ad una corrente fatta passare attraverso le placche. Allo stesso modo e’ possibile programmare i robot investendoli con dei raggi infrarossi.

Dati i presupposti di elevato numero di robot e infrastruttura di supporto/gestione, è possibile realizzare uno sciame ispirandosi a quanto accade in natura con gli sciami d'insetti, con gli stormi di uccelli o con i banchi di pesci. In tutti questi sistemi biologici ci sono una serie di regole molto semplici che permettono allo sciame/stormo/banco di organizzarsi e controllarsi pur non avendo un capo, un direttore di orchestra. In un banco di pesci, ad esempio, ci sono una serie di regole sul posizionamento reciproco tra i singoli componenti del banco.

Uno dei modelli piu’ utilizzati e’ il cosiddetto modello delle 3 zone che formalizza tramite 3 semplici regole il comportamento del singolo animale all’interno del gruppo.

· Repulsione: quando e’ troppo vicino agli altri individui, l’insetto tende a spostarsi da quest’area.

· Allineamento: gli individui cercano di identificare la possibile direzione del gruppo e si allineano ad essa

· Attrazione: quando gli individui sono troppo distanti dal gruppo, tendono a riavvicinarsi.

Per rendere piu’ realistico il modello delle 3 zone si inserisce un cono di visione che determina un’area attiva di interazione. L’idea e’ di inserire nel modello l’area di percezione del singolo insetto. Per gli uccelli per esempio quest'area e’ legata principalmente alla vista, mentre per i pesci entra in gioco anche la linea laterale.

Per i Kilobot è stato ideato un algoritmo basato su un insieme di funzionalità anch'esse molto semplici, con l'obiettivo di consentire allo sciame di dare forma a sagome arbitrarie:

· un robot puo’ muoversi lungo la periferia di un gruppo di robot misurando la distanza dai robot sulla frontiera del gruppo

· un robot sorgente puo’ generare un messaggio che crea un gradiente nel propagarsi lungo lo sciame

· i robot possono formare un sistema di coordinate locali usando la comunicazione e la distanza dai primi vicini

I robot comunicano tra loro facendo rimbalzare i raggi infrarossi sulla loro superficie. Possono calcolare la distanza da altri robot semplicemente misurando come cambia la brillantezza degli infrarossi: piu’ varia l’intensita’ della luce e piu’ il robot che ha rimandato indietro il raggio e’ lontano. Non possono pero’ individuare la direzione della luce. La localizzazione quindi dipende da un gruppo iniziale di robot usati come semi per stabilire l’origine del sistema di coordinate rispetto al quale individuare la posizione degli altri robot (vedi schizzo sottostante).

Parte superiore dell’immagine: algoritmo utilizzato per i kilobot. Parte inferiore: viene decisa la forma da riprodurre e trasmessa ai robot. Questi utilizzando l’algoritmo a 3 regole spiegato nel testo formano un po’ alla volta la forma richiesta.

 

Una volta che i robot determinano la propria posizione, la procedura per creare una forma arbitraria e’ relativamente semplice : i robot cominciano a muoversi lungo il perimetro dello sciame fino a quando non rilevano di essere entrati nell’area dove la forma verra’ creata. Ogni robot continua a muoversi lungo il perimetro dei robot che sono gia’ all’interno della forma fino a che arriva in prossimita’ dei confini della sagoma o fino a quando non sono a contatto con altri robot gia’ posizionati. In questo modo seguendo 3 semplici regole viene realizzata la forma voluta.

Una collettività di oltre 1000 robot può essere effettivamente considerata uno sciame poiché l'importanza di un singolo robot è in pratica nulla, ed e’ proprio questa una delle principali caratteristiche di uno sciame: il singolo robot può funzionale male o danneggiarsi, ma all'interno dello sciame ve ne sono così tanti che in ultima analisi è il comportamento collettivo a prevalere su quello del singolo.

Data un'immagine bidimensionale i kilobot seguono delle semplici regole per formare la forma voluta. L’effetto e’ simile a quello di uno stormo di uccelli che piroiettano nel cielo. Ad un certo punto non vediamo piu’ il singolo uccello ma vediamo lo stormo come un tutt’uno.

 

Quale sara’ il prossimo passo?

In natura gruppi di migliaia, milioni, miliardi d’individui possono auto-assemblarsi in una grande varieta’ di forme grazie alla semplice interazione locale. Questo motiva nuovi esperimenti con avanzati algoritmi collettivi capaci di rilevare i robot malfunzionanti e recuperare eventuali danneggiamenti esterni, come anche progettare nuovi robot piu’ stabili e fisicamente attaccabili gli uni agli altri per auto-assemblarsi.

 

Video 1: Introduzione ai kilobit

http://youtu.be/ISMwLCFwgK4

Video due: L'uso di un piccolo numero di kilobot

http://youtu.be/Lx8rvBB_A7I

Per approfondire:

ftp://ftp.deas.harvard.edu/techreports/tr-06-11.pdf

Il tempo. Questione di complessita’'?

 

Tutti siamo convinti del fatto che il tempo scorra sempre in avanti senza mai poter tornare indietro. Ma quale meccanismo e’ alla base di un tale comportamento?

Le leggi fondamentali della fisica non dipendono dalla direzione temporale, eppure il futuro e’ cosi significativamente diverso dal passato. Ma perche’? L’origine della freccia del tempo ha interessato fisici e filosofi per piu’ di un secolo. Questi hanno cercato di trovare una soluzione ma senza riuscirci. Ancora oggi questa legge rimane uno dei problemi fondamentali concettuali della fisica. In uno studio recente pubblicato sul giornale Physical Review Letters un gruppo di fisici dell’Universita’ di Oxford ha studiato proprio la “freccia del tempo” evidenziando un modo diverso di guardare a come il tempo si manifesta alle scale universali. Tradizionalmente, il tempo e’ stato descritto con “l’ipotesi del passato”, secondo la quale ogni sistema inizia in uno stato di bassa entropia per poi, guidato dalla termodinamica, portarsi in uno stato con entropia sempre maggiore. In parole semplici: il passato e’ bassa entropia e il futuro alta entropia, un concetto conosciuto come l’asimmetria del tempo termodinamico.

Nella nostra vita di tutti I giorni, possiamo trovare molti esempi di aumento di entropia, come il gas che riempie una camera o un cubetto di ghiaccio che fonde. In questi esempi, si osserva un aumento irreversibile di entropia (e quindi di disordine). Se questo viene applicato su scala universale, si presume che il Big Bang abbia generato l’universo partendo da uno stato di minima entropia. Dopo eoni, mentre l’universo si espandeva e si raffreddava, l’entropia ha iniziato ad aumentare. Per questo motivo il tempo e’ intrinsecamente collegato col grado di entropia, o disordine, del nostro universo. Ma ci sono alcuni problemi.

Subito dopo il Big Bang, il primo universo era un posto molto caldo pieno di particelle primordiali caotiche. Non appena l’universo inizio’ a raffreddarsi, la gravita’ prese il sopravvento rendendo l’universo piu’ ordinato e piu’ complesso: dal raffreddamento delle nuvole di gas, iniziarono a formarsi le prime stelle e poi i pianeti. Questo rese possibile l’inizio della chimica organica, della vita e quindi degli umani che iniziarono a filosofeggiare circa il tempo e lo spazio. Su scala universale, percio’, il disordine effettivamente e’ diminuito e non aumentato come previsto “dall’ipotesi del passato”. Come e’ possibile? Siccome l’entropia e’ una quantita’ fisica dimensionale c’e’ la necessita’ di un riferimento esterno rispetto al quale misurarla. Questo puo’ essere fatto solo per sottosistemi dell’Universo e non per l’intero Universo, in quanto per definizione non c’e’ nulla all’esterno dell’Universo. Quindi se non e’ l’entropia a guidare il tempo in avanti di cosa si tratta? La complessita’ e’ una quantita’ adimensionale che descrive quanto e’ complesso un sistema. Quindi se uno guarda al nostro Universo, la complessita’ e’ direttamente collegata col tempo; come il tempo scorre l’Universo diventa sempre piu’ organizzato e strutturato.

Chi ha posto l’Universo inziale in uno stato di minima entropia? La risposta del team di studiosi e’: la gravita’ e la sua tendenza a creare ordine e complessita’ dal caos. Per provare questa ipotesi il gruppo di fisici ha creato dei modelli al computer per simulare le particelle in un universo virtuale. Essi hanno trovato che indipendentemente dalla simulazione utilizzata, la complessita’ dell’Universo aumenta sempre e non decresce mai col tempo.

Con il Big Bang, l’universo e’ partito da uno stato di minima complessita’ (un brodo di particelle ed energia). Da quel momento in poi col susseguente raffreddamento la gravita’ inizio ‘ a prevalere sulle altre interazioni: i gas cominciarono ad aggregarsi, si formarono le stelle e le galassie cominciarono ad evolversi. L’universo divento’ inesorabilmente piu’ complesso con la gravita’ la forza responsabile dell’aumento della complessita’. Ogni soluzione del modello gravitazionale utilizzato dal gruppo di ricercatori ha la proprieta’ di avere qualche stato passato molto omogeneo caotico (eventualmente proveniente dalla contrazione precedente della materia) e non strutturato che assomiglia molto al plasma che costituiva l’universo al tempo in cui veniva generata la radiazione di fondo cosmica (CMB).

A partire da questo stato col passare del tempo la gravita’ aumenta le inomogeneita’ creando le strutture cosmiche e quindi l’ordine in modo irreversibile. Come l’universo matura, i suoi sotto sistemi diventano abbastanza isolati da far si che altre forze comincino a far sentire I loro effetti e quindi a settare nei sistemi a bassa entropia le condizioni per avere la classica freccia del tempo. In questi sotto sistemi, come la nostra Terra, l’entropia crea una freccia termodinamica del tempo.

L’Universo e’ una struttura la cui complessita’ e’ in crescita. Esso e’ formato da miliardi di galassie separate tra loro da vaste “bolle” vuote. In un passato lontano erano molto piu’ vicine di adesso. Quindi la congettura del team di ricerca e’ che la nostra percezione del tempo risulti da una legge che determina una crescita irreversibile della complessita’.

Il prossimo passo sara’ quello di cercare delle evidenze dalle osservazioni dell’universo. Il team ha stabilito quali tipi di esperimenti mettere in piede per testare la loro idea. Si trattera’ di fare le giuste osservazioni cosmologiche.

Risolto quindi il problema della freccia del tempo? Probabilmente ancora no. Rimane il mistero del perche’ le frecce del tempo di diversi sistemi fisici puntano tutte nella stessa direzione. Le onde elettromagnetiche vengono ritardate non anticipate; I nuclei radioattivi decadono e mai si riassemblano; I sistemi gravitazionali si aggregano e mai si disperdono; noi tutti ricordiamo il passato e non il futuro. Quello che andrebbe dimostrato e’ che effettivamente queste disparate frecce temporali puntano tutte nella stessa direzione indicata dal modello gravitazionale proposto. Comunque i risultati presentati dagli scienziati di Oxford forniscono un nuovo intrigante punto di vista. La loro visione offre l’evidenza che l’ordinaria dinamica gravitazionale (quella Newtoniana per intenderci) puo’ essere sufficiente a produrre un semplice punto iniziale che puo’ dare una direzione al tempo. Non ci resta che aspettare ulteriori sviluppi futuri.

La complessità dei sistemi di numerazione e l’Università Stradale di Matematica

Il 28 Dicembre scorso sono stato a Napoli insieme ad amici e rispettive famiglie come ormai mi capita da diversi anni. Lo scopo e’ quello di trascorrere una giornata nella nostra Napoli visto che siamo “emigranti” ormai da piu’ di 20 anni. Rivivere le atmosfere colorate di Napoli, i suoni tipici del Natale, assaggiare i piatti tipici e visitare le mostre di presepi e’ diventata ormai una consuetudine. Non puo’ mancare una visita a San Gregorio Armeno, Piazza Miraglia, Via Duomo e le vie del Decumano.

Mentre passeggiavamo nella zona dei Tribunali all’altezza dell’ex Libreria Guida (vicino Scaturchio a Via Mezzo Cannone) ci siamo imbattuti in un gruppetto di persone che ascoltavano un signore con una bacchetta in mano che puntava dei cartelloni con su quadrati pieni di numeri. La sorpresa e’ stata tanta. E’ strano trovare per strada una persona che parli di matematica facendo divertire il pubblico incuriosito. Partecipando ad uno dei giochi proposti e con una piccola offerta si poteva ottenere una laurea in matematica niente di meno che dall’Universita Stradale Matematica di Napoli.

A consegnare l’onorificenza il signor Giuseppe Polone, campano con appena un diploma di quinta elementare alle spalle. Qui di seguito alcune fotografie scattate in strada.

Il Signor Polone e’ noto per aver partecipato ad alcune trasmissioni televisive come esperto di quadrati magici. Ha girato il mondo ed e’ tornato da poco dagli Stati Uniti per tentare di stabilire un record come lui stesso racconta: "Sono tornato a Napoli dagli Stati Uniti perchè ho intenzione di stabilire il guinnes world record". “Ho solo la quinta elementare ma riesco a fare calcoli estremamente complessi. Vere opere d'arte su carta".

Quando parla di "opere d'arte" Giuseppe si riferisce alla sua "invenzione". Una torre alta 35000 millimetri del peso di 35000 grammi che su ogni lato riporta una serie di quadrati riempiti da numeri sia di tre che di quattro cifre. "Se si somma una qualsiasi riga, colonna o diagonale di quattro numeri" continua Polone, "il risultato sarà sempre 35000".

L’opera matematica viene mostrata e spiegata a tutti, lasciando di stucco curiosi e turisti fermi ad osservare i velocissimi calcoli. "Voglio portare Napoli nel mondo" conclude Giuseppe, "grazie all'intelligenza e all'arte matematica".

Il giochino matematico a cui abbiamo assistito e’ diverso da quello della torre. Di seguito i dettagli. Polone propone 6 matrici con all’interno dei numeri. Chiede di pensare ad un numero da 1 a 60 e di mostrare in quali matrici e’ presente il numero pensato. Fatto cio’ con la meraviglia dei presenti Polone indovina il numero.

Tutti a bocca aperta a chiedersi ma come ha fatto? Appena ci siamo allontanati gli amici, ovviamente, mi hanno chiesto: “ tu che sei un matematico hai capito come ha fatto?”

Ho preso in mano il foglio con le 6 matrici e l’ho guardato. Dopo una decina di minuti, mentre passeggiavamo per le stradine di Napoli ho trovato la soluzione. Si trattava di utilizzare il sistema binario. Come tutti sanno il nostro sistema di numerazione (quello decimale) e’ un sistema posizionale con 10 cifre: 0,1,2,3,4,5....9

A seconda della sua posizione, ogni cifra puo’ avere un valore diverso. Tutto quello che serve sono le potenze di 10 e le dieci cifre da 0 a 9. In questo modo possiamo rappresentare tutti i numeri interi. Per esempio se consideriamo il numero 149 lo possiamo pensare come:

1*10² +4*10¹+9*10⁰
Allo stesso modo per il sistema binario utilizziamo le cifre 0 e 1 e le potenze di 2. Lo stesso numero 149 in base binaria e’ dato da:
1*2⁷+0*2⁶+0*2⁵+1*2⁴+0*2³+1*2²+0*2¹+1*2⁰

Questo significa che se consideriamo tutti i numeri interi tra 1 e 60 questi li possiamo rappresentare come somma di potenze di 2. Nell’immagine di seguito ho riportato una matrice dove vengono rappresentate le potenze di 2 (prima colonna a sinistra) da utilizzare per ottenere i primi 60 numeri interi (riportati nella prima riga). In parole povere una cella bianca indica uno 0 del sistema binario mentre una cella colorata un 1. Il numero 35, per esempio lo possiamo scrivere come:

35=1+2+32=2⁰+2²+2⁵
Osservare il bellissimo pattern che emerge con chiare strutture nidificate.

A questo punto il gioco e’ fatto. Basta raccogliere in matrici 6x6 i numeri appartenenti allo stesso colore. Nella matrice che inizia con 1 avremo tutti i numeri dispari. Nella matrice che inizia con 2 tutti i numeri di colore verde chiaro e cosi via. Osservare che la prima matrice contiene i numeri con il pattern: una cella bianca e una colorata; la seconda i numeri che hanno 2 celle bianche e due colorate, la terza i numeri con tre celle bianche e tre celle colorate e cosi via. Se il nostro spettatore pensa al numero 45, indichera’ la prima, la terza, la quarta e la sesta matrice. Ai “maghi matematici” bastera’ sommare il primo numero in alto a sinistra delle matrici indicate per indovinare il numero pensato. Nel nostro caso avremo: 1+4+8+32=45. E il gioco e’ fatto.

Per chi di voi mi segue da un po’ avra’ capito guardando l’immagine nidificata di cui sopra che questa somiglia all’output di un tipico automi cellulari (vedi mio post). Questo fa pensare che alla base di un semplice sistema di numerazione possa esserci in agguato la complessita’. Non a caso Stephen Wolfram il papa’ degli automi cellulari ha dimostrato che partendo con delle semplici regole matematiche si possono generare delle strutture altamente complesse. La semplicita’ puo’ indurre la complessita’.

Ma e’ vero che dei semplici sistemi di numerazione possono dare origine a dei comportamenti complessi? Guardando alla maggior parte dei testi di matematica sembrerebbe di no. Eppure se guardiamo i risultati di esperimenti eseguiti al computer (quindi non quelli di calcolo a cui siamo abituati) facilmente ci accorgiamo che anche semplici sistemi di numerazione possono portare ad un comportamento complesso. Quale e’ l’origine di questa complessita’? E come e’ legata alla complessita’ degli automi cellulari? Si potrebbe pensare che questa sia una questione semplice e che essa abbia una risposta immediata. Eppure non e’ cosi. La matematica tradizionale non aiuta a trovare una risposta. Anzi secondo quanto riporta Wolfram nel suo voluminoso testo “A new kind of science” la matematica non fa altro che aggiungere confusione alla questione. Secondo lui, il problema di base e’ che i numeri nella matematica tradizionale vengono maneggiati in modo diverso da come vengono maneggiati nei computer. La matematica tradizionale assume che i numeri sono degli oggetti elementari il cui unico attributo rilevante e’ la sua grandezza (dimensione). Ma per un computer i numeri non sono oggetti elementari. In realta’ essi devono essere rappresentati in modo esplicito riportando in genere una sequenza di cifre. Il sistema di base utilizzato dal computer e’ il binario e non quello decimale perche’ l’informazione immagazzinata in un semplice condensatore di una memoria dinamica o il floating gate di una memoria flash e’ la presenza o meno di carica elettrica. Quindi il modo piu’ naturale per maneggiare questa informazione e’ quello di usare un sistema a due cifre. Questo significa che i numeri all’interno di un computer sono rappresentati da sequenze di 0 e 1 in modo simile a quanto succede con gli automi cellulari. E le operazioni con i numeri corrispondono ai diversi modi con cui si possono aggiornare le sequenze di 0 e 1. Nella matematica tradizionale i dettagli di come queste operazioni vengono eseguite sono considerate irrilevanti. Ma quello che vedremo qui e’ come la complessita’ si sviluppa nei sistemi basati su numeri e come essa e’ molto simile a quella degli automi cellulari proprio analizzando questi dettagli.

Per iniziare osserviamo cosa succede partendo col numero 1 e aggiungendo ad esso 1 ad ogni step. Il risultato sara’ la semplice successione dei numeri naturali 1, 2, 3, 4, 5, 6, 7, 8, ... La grandezza di questi numeri ovviamente forma una semplice progressione. Ma se invece di guardare alla grandezza dei numeri guardiamo alla sequenza delle cifre allora emerge qualche cosa di piu’ complicato. E infatti, come visto precedentemente la successione delle cifre in base due dei primi 60 numeri interi forma un pattern molto interessante con una struttura di base nidificata. L’immagine si seguito mostra cosa succede sempre in base 2 se uno invece di aggiungere 1 aggiunge dei numeri diversi come 2, 3, 4, 5… Ad un livello superiore tutte le strutture risultano simili tra loro.

Se invece dell’addizione usiamo la moltiplicazione i risultati che otteniamo sono completamente differenti. Vediamo cosa accade se uno parte con 1 e ad ogni step moltiplica per 2 il risultato precedente. In base due, l’operazione di moltiplicazione per 2 ha un semplice effetto: spostare di un posto verso sinistra la sequenza di cifre aggiungendo uno zero a destra. Il risultato e’ una semplice diagonale nera (vedi immagine a sinistra). Ma se il fattore moltiplicativo e’ 3 anziche’ 2, allora le cose vanno in modo completamente diverso come l’immagine a destra mostra. La complessita’ e’ veramente elevata con delle strutture triangolari che sembrano apparire in modo del tutto casuale. Eppure abbiamo fatto una semplice moltiplicazione per 3.

E se continuiamo a fare evolvere nel tempo questa procedura otteniamo una struttura simile con i triangoli disposti secondo una distribuzione apparentemente casuale.

Esattamente come per gli automi cellulari sembra che un semplice sistema di numerazione puo’ dare origine a comportamenti altamente complessi e apparentemente casuali. Si potrebbe pensare che la complessita’ osservata in questa immagine possa essere una conseguenza del fatto che stiamo osservando i numeri in termini della sequenza delle loro cifre e che questa sia assente nel caso in cui guardiamo i numeri in termini della loro grandezza (dimensione). Ma alcuni esempi mostreranno come cio’ non e’ vero.

Come primo esempio consideriamo cosa accade se moltiplichiamo n per 3/2 partendo con n=1.

1, 3/2 = 1.5, 9/4 = 2.25, 27/8 = 3.375, 81/16 = 5.0625, 243/32 = 7.59375, 729/64 =11.390625, ...

L’immagine di seguito mostra la sequenza delle cifre di questi numeri in base 2. Le cifre direttamente sotto e a sinistra dell’uno originale corrispondono alla parte intera di ogni numero (per esempio 1 in 1.5) mentre le cifre a destra corrispondono alla parte frazionaria (per es. 0.5 in 1.5).

Di nuovo la presenza di strutture complesse allo stesso tempo del tutto casuali. Un fenomeno simile puo’ essere visto anche in sistemi che coinvolgono numeri interi e non solo numeri frazionari. Consideriamo una piccola variante della procedura ora analizzata: se il numero ad un particolare step e’ pari allora va moltiplicato per 3/2; se il numero e’ dispari, allora prima aggiungere 1 e poi moltiplicare per 3/2. Ovviamente questa procedura genera sempre numeri interi e se partiamo con 1 la sequenza di numeri che si ottiene e’

1, 3, 6, 9, 15, 24, 36, 54, 81, 123, 186, 279, 420, 630, 945, 1419, 2130, 3195, 4794, ...

Alcuni di questi numeri sono pari mentre altri dispari. La comparsa di numeri pari e’ dispari sembra del tutto casuale.

Nonostante la mancanza di un ordine, la dimensione dei numeri cresce in modo regolare. Cambiando leggermente la procedura possiamo ottenere una crescita meno regolare. Come esempio possiamo prendere un numero ad un particolare step e se esso e’ pari moltiplicarlo per 5/2 altrimenti aggiungere 1 e moltiplicare per 1/2. Se si parte con 1 questa procedura ritorna 1 come output ad ogni step. Con diversi numeri come punto di partenza questa procedura da’ origine ad un comportamento ripetitivo. Ma qualche volta puo’ generare un comportamento decisamente piu’ complesso.

Anche se guardiamo alla semplice dimensione dei numeri naturali, quindi, possiamo ottenere una elevata complessita’ con comportamenti analoghi a quelli degli automi cellulari. C’e’ comunque da precisare che le regole utilizzate per gli automi cellulari sono molto differenti da quelle utilizzate per i sistemi di numerazione. Le regole degli automi cellulari infatti sono sempre locali: lo stato di una particolare cella dipende solo dallo stato della stessa cella ad un istante precedente e da quello delle celle vicine. Per i sistemi di numerazione, invece non c’e’ alcuna localita’. Nonostante questa differenza il comportmento globale e’ molto simile. Si conferma che usando semplici regole o procedure, anche partendo con una configurazione iniziale semplicissima come puo’ essere il numero 1 e’ possibile generare dei comportamenti altamente complessi. E come Wolphram ipotizza e’ possibile che sia proprio questo fenomeno alla base della maggior parte della complessita’ che osserviamo in natura.

Quando il rumore diventa energia elettrica

 

Secondo quanto pubblicato sul web a fine estate, i ricercatori della Nokia insieme a quelli del Queen Mary University di Londra, sono riusciti a realizzare un prototipo delle dimensioni di un Nokia Lumia 925 in grado di ricaricarsi con il rumore. Si avete capito bene. Si tratterebbe della possibilita’ di produrre energia elettrica a partire dall’energia meccanica prodotta dalle onde sonore del traffico, della musica e della voce. Ancora non si sa quando questi telefonini con all’interno nanogeneratori piezoelettrici sensibili alle onde sonore saranno disponibili sul mercato. Potrebbero essere necessari ancora molti mesi ma quando succedera’ di sicuro porteranno non pochi benefici a tutti gli utenti dei telefonini che oggi hanno il terrore di rimanere senza batteria proprio nel momento di maggiore bisogno. Vediamo allora come funzionano.

L’idea, presentata per la prima volta nel 2006 in un articolo pubblicato su Science (Link), e’ basata sullo sfruttamento dell’effetto piezoelettrico e sulle proprieta’ semiconduttive dell’ossido di zinco (ZnO). La piezoelettricità è la proprietà di alcuni materiali cristallini di polarizzarsi generando una differenza di potenziale quando sono soggetti ad una deformazione meccanica. Tale effetto piezoelettrico si manifesta solo lungo una determinata direzione e le deformazioni ad esso associate sono dell'ordine del nanometro. Esso è presente in quasi tutti i materiali cristallini che sono privi di centro di simmetria. La struttura di tali cristalli è costituita da microscopici dipoli elettrici. In condizioni di quiete, tali dipoli elettrici sono disposti in maniera tale che le facce del cristallo hanno tutte lo stesso potenziale elettrico. Quando viene applicata una forza dall'esterno, comprimendo il cristallo, la struttura del cristallo viene deformata e si perde la condizione di neutralità elettrica del materiale, per cui una faccia del cristallo risulta carica negativamente e la faccia opposta risulta carica positivamente. Il cristallo si comporta dunque come un condensatore al quale è applicata una differenza di potenziale. Se le due facce vengono collegate tramite un circuito esterno, viene quindi generata una corrente elettrica, detta corrente piezoelettrica. Nell’immagine A vengono mostrati i nanofili di ossido di zinco come appaiono ad un microscopio elettronico a scansione (SEM) e in quella B come gli stessi appaiono ad un microscopio elettronico a trasmissione (TEM). In C viene schematizzato il sistema a punta utilizzato perf flettere i nanofili per sviluppare un potenziale elettrico
 

Nella figura B sottostante e’ mostrato il potenziale sviluppato da alcuni nanofili individuati dalle coordinate (x,y) e in E il segnale sviluppato da un singolo nanofilo ( circa 10 mV).
 

Dopo la pubblicazione del 2006 c’e’ stato un continuo progresso in termini di potenziale erogabile dal nanogeneratore come mostrato nell’immagine qui sotto.
 

Oggi il record e’ di 57 V con una corrente di 12 uA usando un nanogeneratore di 1 cm2 la cui struttura e’ mostrata nel riquadro qui sopra. Si tratta di una matrice di nanofili di ossido di Zinco (ZnO) inseriti tra due elettrodi di metallo. Il processo per costruire questo nanogeneratore e’ mostrato di seguito.
 

Si parte con un substrato di Silicio su cui si deposita uno strato di ITO (Indium tin oxide, una soluzione solida di In2O3 e SnO2 con una percentuale del 90% e 10% rispettivamente) che a sua volta vedra’ un sottile strato di ZnO che serve a promuovere la crescita successiva dei fili di ZnO. Lo strato di ITO gioca un ruolo non solo come conduttore ma promuove anche l’adesione tra i semi di ZnO e il substrato di silicio ed e’ trasparente alla luce. Prima di realizzare il secondo elettrodo di alluminio viene depositato un film di PMMA (polymethyl methacrylate) che sommerge i nanofili proteggendoli da eventuale rottura per stress meccanico. Inoltre esso funziona come un diodo schocktty. Quando viene applicata una forza compressiva lo stress e’ trasmesso attraverso il PMMA a tutti i nanofili anche se questi hanno una lunghezza diversa. Inoltre questo strato serve come protezione evitando il contatto diretto dei nanofili con l’elettrodo migliorando cosi la durabilita’ e robustezza del nanogeneratore.

La speranza è che i dispositivi alimentati con le vibrazioni sonore possano presto sostituire i caricabatterie tradizionali. Tuttavia, il professore Joe Briscoe della Queen Mary University di Londra, attualmente impegnato nel progetto con la Nokia, ha ammesso che "per il momento il nuovo tipo di caricabatteria non è in grado di sostituire i metodi di ricarica oggi in vigore". "Credo che i telefoni basati su questo tipo ricarica”  - ha spiegato lo scienziato – “possano avere una loro parte nel futuro, ma probabilmente non basteranno per eliminare completamente la necessità del tradizionale metodo di carica". In ogni caso, la possibilità che ogni cellulare possa essere ricaricato con il suono della voce, i rumori di sottofondo, la musica e altro si appresta a diventare realtà. 

Skype Translator – Le Deep Neural Networks all’opera

 

E’ di alcuni mesi fa l’annuncio di Microsoft sulla comparsa di Skype Translator per la fine di quest’anno. Si trattera’ di un traduttore automatico che permettera’ di fare telefonate in video con l’aiuto di una traduzione simultanea sia in voce che con i sottotitoli.

La sorpresa e’ arrivata durante la Code Conference di S. Francisco dove il vice presidente di Skype, Gurdeep Pall, ha fatto un esperimento pratico. Parlando in inglese, ha conversato tramite Skype con una dipendente Microsoft di lingua tedesca e la loro discussione e’ stata tradotta in tempo reale. Non e’ ancora chiaro in quante lingue sara’ disponibile Skype Translator e se sara’ un servizio gratuito, ma l’idea di poter parlare, ad esempio, con una persona cinese senza barriere linguistiche, per lavoro o motivi personali e’ davvero una grande novita’. Si tratterebbe del superamento delle barriere linguistiche della Torre di Babele che fino ad ora non era stato possibile con i traduttori disponibili, come per esempio Google Translator, in quanto utili per una traduzione veloce ma non abbastanza precisi. Ma come e’ possibile tutto cio’?

Utilizzando le cosiddette “machine deep learning” sviluppate nell’ambito della ricerca sull’Intelligenza Artificiale. Per capire di cosa si tratta partiamo con l’unita’ piu’ semplice di una rete neurale: il percettrone (perceptron).

Supponiamo di avere 5 immagini di uomini e 5 immagini di qualsiasi altra cosa e di etichettare con 1 le immagini umane e con 0 le altre. L’obiettivo e’ di costruire un algoritmo che sia capace di imparare ad identificare le immagini degli umani una volta che gli vengono presentate nuove immagini mai viste prima (1 per gli umani e 0 per il resto). Questo esempio e’ del tutto generale. I dati potrebbero essere dei sintomi e le etichette le diverse malattie; i dati potrebbero essere le lettere scritte a mano e le etichette le lettere reali corrispondenti. Questo e’ quello che in definitiva fa un algoritmo come il percettrone.

Supponiamo di avere n punti in un piano, etichettati con 0 ed 1. Aggiungiamo un nuovo punto e cerchiamo di prevedere la sua etichetta. Come possiamo fare? Un possibile approccio puo’ essere quello di guardare i primi vicini ed assegnare l’etichetta al punto in base alla quantita’ di 1 e di 0 presenti nelle vicinanze. Per esempio, nell’immagine qui riportata assegneremmo il colore rosso al punto vuoto visto che i primi vicini sono in prevalenza rossi.

Un modo leggermente piu’ intelligente potrebbe essere quello di considerare una linea che meglio separa i dati etichettati e usarla come classificatore (classificatore lineare).

In questo caso, i dati in ingresso verrebbero rappresentati come vettori (x,y) e la funzione in uscita dovrebbe essere qualche cosa come “blu” se il punto cade al di sotto della linea e “rosso” se capita al di sopra. Matematicamente potremmo scrivere la funzione di trasferimento come:

f(x)=w·x+b

dove w e’ un peso opportuno e b un cosiddetto bias (offset verticale). Il risultato di questa funzione potrebbe essere portato in ingresso ad una funzione di attivazione per produrre l’opportuna etichetta. Nel nostro esempio, la funzione di attivazione potrebbe essere:

h(x)=”rosso” se y(x)>f(x)= w·x+b o h(x)=”blu” per gli altri casi.

Per determinare il peso w ottimale, l’algoritmo del percettrone in base ai dati presentati in ingresso sceglie i valori per minimizzare l’errore della risposta in uscita, definito come la differenza tra il valore desiderato e quello reale (oppure utilizzando il cosiddetto mean square error). Ovviamente il percettrone nella sua semplicita’ ha uno svantaggio: esso puo’ solo imparare a separare funzioni lineari. Consideriamo per esempio la funzione XOR, una funzione molto semplice che ritorna 0 se i due valori in ingresso sono uguali altrimenti ritorna 1. In questo caso un classificatore lineare non funzionerebbe correttamente come mostrato sotto.

Per superare questo problema bisogna ricorrere ad un percettrone “multistrato”, anche conosciuto come “feedforward neural network”: in effetti non faremo altro che mettere insieme piu’ percettroni connessi insieme a creare un meccanismo di apprendimento piu’ potente.

La rete neurale ha le seguenti proprieta’:

· Un input, un output e uno o piu’ strati “nascosti” (hidden). Una rete con piu’ strati nascosti viene chiamata Deep Neural Network. Nella figura sopra e’ mostrata una rete con 3 unita’ (anche chiamate neuroni o nodi) in ingresso, uno strato di output con 2 unita’ e due strati nascosti, con 4 unita’ il primo e 3 unita’ il secondo rispettivamente

· Ogni unita’ e’ un singolo percettrone

· Le unita’ dello strato di ingresso servono per trasmettere allo strato nascosto i dati di ingresso, mentre le unita’ nascoste fungono da unita’ di ingresso per lo strato di uscita.

· Ogni connessione tra due neuroni ha un certo peso w simile a quello del percettrone discusso sopra

· Ogni unita’ di uno strato n, in generale e’ connessa ad ogni unita’ dello strato precedente n-1 (anche se e’ possibile disconnettere due neuroni semplicemente settando a zero il proprio peso)

· Lo strato di ingresso serve solo per trasferire i dati di ingresso alla rete che li processera’. Per esempio, se il vettore in ingresso e’ (7,1,2) questo significa che il primo nodo in alto vedra’ il valore 7, quello centrale 1 e quello in basso il valore 2. Questi valori, vengono poi propagati in avanti verso le unita’ nascoste usando una somma pesata come ingresso alla funzione di trasferimento di ogni unita’, che a sua volta calcola il proprio output tramite la funzione di attivazione.

· Lo strato in uscita calcola i valori risultanti allo stesso modo dello strato nascosto. Il risultato e’ l’output finale della rete.

Cosa succede se per i nostri percettroni utilizziamo delle funzioni di attivazione lineari?

L’uscita finale della rete sara’ ancora una qualche funzione lineare degli ingressi, opportunamente aggiustati con tanti pesi diversi collezionati lungo la rete. In altre parole, una composizione lineare di tante funzioni lineari e’ ancora una funzione lineare. Quindi se utilizziamo delle funzioni di attivazione lineari, la rete neurale non sara’ piu’ potente di un singolo percettrone indipendentemente dal numero di strati utilizzati. Per questo motivo la maggior parte delle rete neurali utilizzano funzioni di attivazione non lineari. Le funzioni di attivazione piu’ utilizzate sono: logistica, tangente iperbolica, binaria e rectfier. Nella formula sottostante, k e’ la funzione di attivazione, w_i i pesi e g_i i vettori in ingresso.

Di seguito la schematizzazione di un singolo neurone con funzione di attivazione a soglia. Il neurone riceve in ingresso uno stimolo dato dalla somma del prodotto dei singoli ingressi per i pesi associati. Nel nostro caso U=1.5·0.5+1·3+2·(-1)=1.75. Se la somma supera una certa soglia (nel nostro esempio il valore theta) il neurone si attiva e in uscita si avra’ il valore U-ɵ=1.75-1=0.75

L’algoritmo piu’ comune per il learning (addestramento) di un percettrone a multistrato e’ conosciuto come backpropagation. La procedura di base e’ la seguente:

· Un campione per il training viene presentato in ingresso alla rete e propagato attraverso di essa.

· In uscita viene calcolato l’errore E=0.5(t-y)² dove t e’ il valore di riferimento (target) e y e il valore reale calcolato dalla rete.

· L’errore E viene minimizzato usando un metodo chiamato stochastic gradient descent. Il valore ottimale di ogni peso viene determinato in modo da far raggiungere all’errore un minimo globale. Durante la fase di training, i pesi vengono cambiati di poco nella direzione del minimo globale, anche se questa non e’ un’attivita’ semplice visto che spesso i pesi raggiungono dei minimi locali come quelli mostrati di seguito.

L’algoritmo di backpropagation fornisce un metodo per aggiornare ogni peso tra due neuroni rispetto all’errore di uscita. Il peso di un dato nodo (per esempio il nodo i-esimo) viene aggiornato seguendo la semplice relazione:

dove E e’ l’errore di uscita della rete e w_i e il peso in input al neurone i-esimo. Il parametro alfa controlla la velocita’ di discesa lungo il gradiente, e nei casi piu’ semplici e’ una costante. Si tratta di muoversi nella direzione del gradiente rispetto al peso w_i. Dapprima vengono calcolati gli errori in uscita delle diverse unita’, e quindi propagati all’indietro nella rete in modo efficiente per cercare di raggiungere il minimo globale.

Lo strato nascosto (hidden layer) e’ dove la rete immagazzina la rappresentazione astratta dei dati di training, cosi come il cervello ha una rappresentazione interna del mondo reale. Secondo il teorema dell’approssimazione universale, un singolo strato nascosto con un numero finito di neuroni puo’ essere specializzato ad approssimare qualsiasi funzione. Comunque nella realta’ una rete neurale puo’ avere piu’ di uno strato nascosto per permettere astrazioni maggiori anche se ci sono degli effetti collaterali.

Man mano che si aggiungono strati nascosti, l’algoritmo di backpropagation diventa meno utile nel passare le informazioni agli strati precedenti. Si puo’ presentare inoltre, il cosiddetto problema di overfitting. Esso descrive il fenomeno dell’interpolazione dei dati di training in modo troppo “preciso” (lasciatemi passare il termine), e la rete finisce col perdere in flessibilita’. E’ come se la rete imparasse a memoria perdendo la capacita’ di generalizzare cioe’ la capacita’ di fornire una risposta corretta a nuovi ingressi (non presentati nella fase di addestramento della rete).

Altro problema che affligge tutti i sistemi di apprendimento supervisionato (cioe’ quelli con addestramento) e’ la cosiddetta maledizione della dimensionalita’, un progressivo decadimento delle prestazioni all’aumentare della dimensione dello spazio di ingresso. Questo avviene perche’ il numero di esempi necessari ad ottenere un campionamento sufficiente dello spazio di ingresso aumenta esponenzialmente con il numero delle dimensioni.

Per superare questi problemi sono stati sviluppati degli algoritmi particolari. Il primo e’ quello delle reti auto-associative progettate ed addestrate per trasformare un pattern in ingresso in se stesso, in modo che, in presenza di una versione degradata o incompleta di un pattern di ingresso, sia possibile ottenere il pattern originale. Una rete auto-associativa in generale e’ una rete neurale feedforward con 3 strati: un ingresso, un’uscita e uno strato nascosto. Concettualmente, la rete viene addestrata per ricreare in uscita i dati presentati in ingresso con lo strato nascosto che immagazzina i dati compressi cioe’ una rappresentazione compatta che cattura le caratteristiche fondamentali dei dati in ingresso. Una vera e propria riduzione della dimensione del campione in ingresso.

 

Il secondo algoritmo sviluppato e’ stato quello delle cosiddette Restricted Boltzmann machines (RBM) un tipo di rete neurale stocastica.

Questo tipo di rete e’ composto da uno strato di ingresso/uscita chiamato visibile e uno strato nascosto. Diversamente dalle reti feedforward, le connessioni tra lo strato visibile e quello nascosto sono non direzionali (cioe’ i dati possono viaggiare in entrambi le direzioni visibile-nascosto e nascosto-visibile) e le diverse unita’ neuronali possono essere completamente connesse (in questo caso si parla di macchina di Boltzmann) o parzialmente connesse (in questo caso si parla di macchina di Boltzmann ristretta). In generale una rete RBM ha le unita’ binarie (con stati 0 o 1) assegnate con una certa probabilita’ secondo una distribuzione di Bernoulli.

Queste reti erano note agli scienziati fin dagli anni 80 ma solo di recente hanno visto di nuovo un grosso interesse da parte della comunita’ scientifica in seguito all’introduzione di un nuovo algoritmo di training (addestramento) non supervisionato chiamato “contrastive divergence”.

Questo algoritmo e’ costituito da 3 fasi: quella positiva, quella negativa e quella dell’aggiornamento dei pesi.

Fase positiva

· Un campione v (si tratta di un vettore multidimensionale) e’ presentato in ingresso alla rete

· Il vettore v e’ propagato allo strato nascosto allo stesso modo delle reti feedforward; indichiamo il suo output con il vettore h.

Fase negativa

· Si propaga il vettore h indietro allo strato visibile ottenendo un nuovo vettore v’

· Il vettore v’ viene propagato indietro allo strato nascosto ottenendo un nuovo vettore h’

Aggiornamento dei pesi

w(t+1)=w(t)+a(vh^T-v’h’^T)

dove a rappresenta la velocita’ di apprendimento della rete e T indica il vettore trasposto (l’operazione di trasposizione trasforma una riga in colonna e viceversa). La fase positiva riflette la rappresentazione interna dei dati reali (h a partire da v). La fase negativa, invece rappresenta il tentativo della rete di ricreare i dati sulla base della rappresentazione interna (v’ a partire da h). Lo scopo principale dell’algoritmo e’ quello di generare dei dati il piu’ vicino possibile ai dati reali e questo e’ riflesso nella formula di aggiornamento dei pesi. In altre parole, la rete ha una qualche percezione di come i dati in ingresso possono essere rappresentati, e quindi prova a riprodurre i dati reali sulla base di questa percezione. Se la riproduzione non e’ abbastanza vicina alla realta’, la rete aggiorna i pesi e prova di nuovo.

Sia le reti auto-associative che le macchine di Boltzmann hanno la proprieta’ interessante di avere le unita’ nascoste che funzionano come dei veri e propri rivelatori di caratteristiche “feature detectors” e questo e’ alla base delle deep neural net come vedremo tra poco. Prima vediamo meglio la proprieta’ delle unita’ nascoste. Supponiamo di voler addestrare una rete neurale a distinguere immagini che rappresentano delle motociclette da quelle che rappresentano dei visi. Abbiamo molti pixels in ingresso e un output pari a 0 per le motociclette e un 1 per un viso. Se usassimo una rete neurale con un singolo strato e un peso per ogni pixel quello che la rete cercherebbe di fare e’ classificare ogni pixel come appartenente ad una moto o ad un viso. Ovviamente questo e’ impossibile in quanto un pixel nero potrebbe essere parte sia dell’immagine della moto che di un viso. Sicuramente sarebbe piu’ utile avere a disposizione un rivelatore di un “manubrio” o di una “ruota”. Sotto la spinta di queste motivazioni sono stati sviluppati dei metodi di “deep lerning” che mirano, tramite l’utilizzo di architetture profonde, all’apprendimento di gerarchie di “features”, con quelle ai livelli piu’ alti formate attraverso la composizione di quelle ai livelli piu’ bassi. Ispirandosi all’architettura profonda del cervello, i ricercatori nel campo delle reti neurali hanno provato ad addestrare reti multistrato sfruttando un algoritmo di apprendimento non supervisionato (le RBM/auto-associative con learning contrastive divergence) e addestrando singolarmente ogni strato nascosto per superare il problema dell’overfitting. Queste strutture stacked (impilate una nell’altra) sono molto potenti e producono risultati veramente impressionanti. Google, per esempio, ha utilizzato una rete profonda costituita da diverse reti auto-associative per imparare a distinguere un viso umano da quello di un gatto (link). Un esempio di rete profonda con blocchi auto-associativi e’ quello mostrato di seguito.

Lo strato nascosto I agisce come strato di ingresso per lo strato nascosto II e cosi via. Il training di una rete del genere procede come segue:

1. Viene effettuato l’addestramento del primo blocco auto-associativo (le connessioni rosse) usando il metodo di backpropagation con tutti i dati di training disponibili.

2. Si effettua l’addestramento del secondo blocco auto-associativo (connessioni verde). Il training inizia presentando i dati in ingresso allo strato rosso e propagato ai neuroni del secondo strato nascosto (quello verde). In seguito vengono aggiornati i pesi (input-hidden e hidden-output) del secondo strato nascosto (quello verde) utilizzando l’algoritmo backpropagation e tutti i dati di training gia’ utilizzati per addestrare il primo strato nascosto. Questa procedura viene ripetuta per tutti gli strati nascosti.

3. Gli steps precedenti vengono chiamati pre-training e servono per inizializzare i pesi della rete. Comunque a questo stadio non esiste ancora un mappatura tra lo strato di ingresso e quello di uscita. Per realizzarla, la rete viene addestrata come una normale feedforward usando l’algoritmo di backpropagation (questo step viene chiamato fine-tuning).

Come con le reti auto-associative, e’ possibile “impilare” anche delle macchine di Boltzmann (RBM) per realizzare delle reti deep conosciute come Deep Belief Netwroks (DBN). In questo caso lo strato nascosto della prima RBM funzionera’ da strato visibile per lo strato nascosto della seconda RBM e cosi via. Lo strato di ingresso della prima RBM e’ lo strato di ingresso dell’intera rete.

L’addestramento della rete procede in questo modo:

1. Viene effettuato il training della prima RBM utilizzando l’algoritmo “contrastive divergence” utilizzando tutti i dati di addestramento.

2. Parte l’addestramento della seconda RBM. Poiche’ lo strato visibile della seconda RBM e’ lo strato nascosto della prima RBM, l’addestramento inizia presentando i dati di training in ingresso alla prima RBM e da qui propagati. La stessa cosa verra’ ripetuta per tutti gli strati nascosti.

3. Allo stesso modo delle reti auto-associative stacked, dopo il pre-training va fatta la mappatura dello strato di ingresso e quello di uscita utilizzando l’algoritmo di backpropagation (fine-tuning).

Le deep neural networks hanno fatto “risorgere” l’interesse per l’intelligenza artificiale da parte degli scienziati del mondo accademico e di quelli di compagnie come Google, Facebook e Microsoft. Gli sforzi di questi teams sono impressionanti: basta ricordare i progressi fatti nell’ambito del riconoscimento vocale, del riconoscimento delle immagini e delle traduzioni automatiche, giusto per citarne alcuni. La mole di dati nonche’ la potenza di calcolo a disposizione oggi e’ di diversi ordini di grandezza superiore a quella di alcuni anni fa. Questo non puo’ che aiutare lo sviluppo di algoritmi di apprendimento sempre piu’ sofisticati. Di sicuro saremo testimoni di una svolta epocale nell’ambito dell’intelligenza artificiale. Non ci resta che attendere.