FACOLTÀ DI SCIENZEMATEMATICHE FISICHE E NATURALI

Corso di Econo�sica

PHYSARUM POLYCEPHALUM:UN ALGORITMO NATURALE PER LA

PROGETTAZIONE A BASSO COSTO DELLERETI DI TRASPORTO DI UNA CITTÀ

Gabriele D'Acunto

Anno Accademico 2015/2016

Indice

1 Physarum Polycephalum 5

1.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Modello matematico . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Obiettivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Simulazione 7

2.1 Com'è nato questo ABM ? . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Il Modello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 De�nizioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2.2 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2.3 Go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3 Analisi dei risultati . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.4 Conclusione e Futuri sviluppi . . . . . . . . . . . . . . . . . . . . . . 18

3 Bibliogra�a 21

1 Physarum Polycephalum

1.1 Introduzione

Organismo unicellulare costituito da innumerovoli nuclei coordinati tra loro, laPhysarum Polycephalum è una mu�a mucillaginosa dal colore giallastro che pro-spera in ambienti freschi ed umidi e che si nutre di spore e batteri.Sebbene non possegga un sistema nervoso, la Physarum P. mostra interessanti com-portamenti, oggetto di studi di recenti ricerche. Infatti, come riportato da un esperi-mento condotto dai ricercatori T. Nakagaki, H. Yamada e A. Toth, tale mu�a, dopoessere stata posizionata in un labirinto alle cui uscite era stata posta dell'avena (dicui la Physarum P. è ghiotta), ha dimostrato la capacità di ricostruire il tragittopiù breve congiungente le due fonti di cibo.Pur variando la complessità del labirinto, la mu�a ha saputo individuare il percorsorisolutivo ottimale.

Figura 1: Labirinto risolto dalla PhysarumP.

1.2 Modello matematico

A partire da tali studi, A. Tero, R. Kobayashi e T. Nakagaki proposero un modellomatematico per descrivere tale comportamento. Essi schematizzarono la testé cita-ta mu�a come un rete di tubi attraversata da un �uido soddisfacente l'assunzionestandard di Poiseuille della �uidodinamica. Quest'ultima è dovuta al fatto che esso,essendo caratterizzato da un basso numero di Reynolds, si trova in regime laminare.La Physarum P. è dunque rappresentata da un grafo G(N,E) in cui:

• Ni∈(1,...,N) ∈ N rappresentano i nodi (nuclei della mu�a e fonti di cibo stesso);

• ei,j∈(1,...,N) ∈ E rappresentano i capillari;

5

Considerando ora i nodi Ni e Nj, indichiamo con Dij(t) e Lij rispettivamente laconduttività e la lunghezza del capillare congiungente i nodi.Da qui segue che:

Rij(t) =Lij

Dij(t)(1)

è la resistenza del singolo �lamento.Supponendo che ogni nodo abbia pressione pi(t), in approssimazione di Poiseuillela quantità di �usso attraverso un capillare, che descriverà la dinamica di contrazioneed espansione del �lamento stesso, sarà:

Qij(t) =(pi(t)− pj(t))

Rij(t). (2)

Imponendo ora la conservazione del �usso, avremo:∑

iR−1ij (pi − pj) + I = 0 per j = 1∑

iR−1ij (pi − pj)− I = 0 per j = 2∑

iR−1ij (pi − pj) = 0 per j 6= 1, 2

(3)

dove N1 e N2 indicano i pezzi di avena tra cui la mu�a si autorganizzerà. In�ne,la dinamica della conduttività Dij(t) nel tempo sarà:

Dij(t) = f(|Qij(t)|) +Dij(t) (4)

dove f è una funzione crescente con f(0) = 0.

1.3 Obiettivi

Questo progetto ha come target quello di simulare tramite NetLogo il comporta-mento della Physarum P. come processo di autorganizzazione. L'assunzione fon-damentale è dunque la stessa che portò A. Turing nel 1952 a sviluppare tale tipodi processo, ovvero l'idea che l'ordine individuale possa causare l'ordine globale. Inparticolare, quest'ultimo scaturisce dalla mutua interazione delle parti, tramite adesempio processi di cooperazione e competizione.Uno dei campi in cui i processi alla Turing trovano impiego è la morfogenesi. Tra-mite essi, ad esempio, è possibile spiegare (e simulare) fenomeni come la formazionedi macchie negli animali oppure delle sinapsi che si dipartono dagli occhi per poi ar-rivare al cervello. Nel caso speci�co della Physarum P., le singole parti (gli agenti)saranno i nuclei della testé citata mu�a. Rispettando la semplice conservazione del

�usso Qij, essi faranno emergere la disposizione �nale dell'organismo che risulteràessere una rete congiungente in maniera ottimale i pezzi d'avena. Taluni, come in-tuito da A. Tero, R. Kobayashi e T. Nakagaki, potrebbero essere l'equivalente deipunti di una città che si vogliono connettere attraverso una rete di trasporti.

6

2 Simulazione

2.1 Com'è nato questo ABM ?

Il processo di maturazione, che mi ha portato alla realizzazione del modello che saràesposto nel paragrafo successivo, si compone di tre steps.Nella sua forma iniziale, fu pensato senza agenti. Sia la Physarum P. che i pezzi diavena erano rappresentati da patches. Ad ogni componente della mu�a, occupantel'intero mondo (chiuso), era assegnata una variabile energia la cui variazione era de-terminata da un processo di competizione tra patches stesse. Assegnato ad ognunaun receptive �eld, esse erano "eccitate" dalle connessioni con le patches in cui si eraveri�cato il passaggio di nutrienti ed inibite dalla degradazione dovuta al trascorreredel tempo (nel caso di mancato approvvigionamento).Successivamente, viste le di�coltà emerse nell'ottenere una rappresentazione gra-�ca del comportamento della Physarum P. soddisfacente, iniziai a sviluppare unsecondo modello alquanto di�erente. In esso entrarono in gioco due specie di agentirappresentanti:

• il fronte dei capillari: tali agenti permettevano di simulare l'espansione spazialedella mu�a in cerca di cibo;

• i nutrienti: collocati sulle patches rappresentanti l'avena, il loro �usso era azio-nato dal passaggio del fronte di capillari, rappresentante il fatto che la mu�aaveva individuato la fonte di cibo e poteva dar via alla fase di consolidamento.

Figura 2: Secondo Modello: avena in rosso, sostanze nutritive in blu, fronte di capillari in

giallo.

L'idea alla base di questo secondo modello era la seguente: simulare la dinamicadei nutrienti utilizzando i risultati ottenuti dallo studio di un Ant Colony. A fermar-mi, in questo caso, è stata la realizzazione del meccanismo di ritorno dei nutrientiai pezzi di avena originari. In particolare, poiché sarebbe stato poco realistico per-mettere alle sostanze nutritive di distinguere fonti di cibo uguali tra loro, gli agentirisultavano confusi in caso di vicinanza di esse e dunque incapaci di creare un cam-

mino ottimo.

7

Pur non avendo proseguito nello sviluppo dei due precedenti ABM, resto convintodel fatto che, con opportune modi�che, si possa riuscire a simulare il comportamentodella Physarum P. tramite essi. A sostegno di ciò espongo due hints:

• Arricchire il primo creando una sequenza di azione delle patches, ovvero farleagire ordinatamente partendo da quelle più vicine ai pezzi di avena;

• Modi�care il secondo non richiedendo ai nutrienti di far ritorno alle fonti dicibo originarie e risolvere il problema della loro vicinanza argomentando che,qualunque essa sia, è possibile studiare il problema con un opportuno scaling.

8

2.2 Il Modello

2.2.1 De�nizioni

Dopo aver brevemente descritto come sia giunto alla sua realizzazione e soprattuttocosa mi abbia spinto a farlo, analizziamo da vicino il terzo modello, oggetto di questoprogetto.Com'è possibile notare nel listato riportato di seguito, ai capillaries del modelloprecedente si aggiungono:

• nodes, caratterizzati da:

1. una propria pressure (secondo quanto riportato nel modello matematicodi A. Tero, R. Kobayashi e T. Nakagaki);

2. una variabile food-source-number che distingue i nuclei della mu�a dal-l'avena;

3. un agentset di nodes, in-range-neighbors, con i quali ogni node creeràlegami;

4. una variabile binaria on? che indica se il node è attivo o meno.

• node-links, caratterizzati da:

1. un proprio �ow, rappresentante la quantità di �uido che attraversa ognicapillare;

2. una e�-pressure, di�erenza tra le pressures dei nodes agli estremi del link ;

3. una variabile PrevThickness che registra lo spessore del node al tick pre-cedente, utile per l'integrazione dell'equazione (4).

Proprio quest'ultimi sono la peculiarità di questo modello. Infatti essi, essendogià muniti in NetLogo di thickness e link-length, agevolano e rendono più intuitivol'intero codice. Tramite di essi, i nodes potranno interagire, facendo emergere lacon�gurazione �nale della mu�a.

9

Figura 3: Code. De�nizions

2.2.2 Setup

Consideriamo innanzitutto il blocco setup-patches. In esso è inizialmente creatala prima fonte di cibo, la quale sarà il node 0, distinta dalla seconda grazie al food-source-number. Successivamente sono posizionati, in base ad una density-of-nodes

scelta dall'utente, i nuclei della mu�a, inizialmente nascosti. Nel caso in cui ve nesiano di isolati, un messaggio di errore viene presentato all'utente.Per quanto riguarda invece il blocco setup-links, dopo aver assegnato ad ogni nodel'agentset in-range-neighbors attraverso la funzione ellipse-in (con raggi modi�cabilidall'esterno), sono creati i node-links. Da notare come si evitino le doppie connessionie come si escluda il node stesso dall'agentset. In�ne è imposta la thickness inizialetra [0, 1) e creati capillaries equamente direzionati.

10

Figura 4: Code. Setup

11

Figura 5: Code. Setup

12

2.2.3 Go

Analizziamo ordinatamente cosa succede ad ogni tick.Innanzitutto è aggiornata la variabile life di ogni patch, la quale viene incrementatadal passaggio del fronte dei capillaries. Inoltre essa tende lentamente a zero colpassare del tempo, creando un gradevole e�etto gra�co che rende l'idea del passaggiodalla fase di espansione a quella di sfoltimento e successivo consolidamento dellaPhysarum Polycephalum.A tal punto i capillaries avanzano di un passo, attivando, qualora fossero presenti, inodes della mu�a e mostrando i node-links aventi ambo gli estremi accesi. Da notareche essi muoiono quando l'intero mondo è stato esplorato, momento in cui la fase disfoltimento ha inizio. Ciò è formalizzato dall'imposizione di i pari ad uno.Consideriamo ora il blocco update-pressure. Dopo essere stati riorganizzati inbase alla loro distanza dal node 0 (ordine crescente), i nodes aggiornano in sequenzala loro pressure. In particolare, per ogni node j, i coe�cienti A e B rappresentano:{

A = R−1ij

B = R−1ij pi(5)

dove R−1ij = (thickness)/(link − length).Dati dunque i due coe�cienti, ogni node j aggiorna la sua pressure in accordo conil sistema (3). Inoltre, nel caso in cui esso rimanga isolato, viene eliminato. Dopoessersi aggiornato, il node j si spegne.È ora possibile calcolare il �ow Qij per ogni node-link ed integrare la dinamica (4).Tale operazione viene eseguita tramite:

Dn+1ij = Dn

ij + (|Qij(Dnij, P

n+1ij )| −Dn

ij)dt (6)

con dt = 5× 10−3.In�ne, vengono spenti i links prossimi allo zero e veri�cata la convergenza delsistema, raggiunta quando:

Dn+1ij = Dn

ij. (7)

13

Figura 6: Code. Go

14

Figura 7: Code. Go

15

Figura 8: Code. Go

16

2.3 Analisi dei risultati

Figura 9: A partire da sinistra: a) inizializzazione, b) ricerca di cibo, c) inizio dello

sfoltimento delle connessioni.

Com'è possibile notare nella �gura in alto, si è scelto di inizializzare il sistema aduna density-of-nodes medio-alta. Essendo le dimensioni del mondo (chiuso) 13× 13,la lunghezza delle connessioni è pari al massimo delle coordinate x ed y. Durantela fase di espansione della Physarum P. sono attivati e mostrati i nodes ed i node-links. Nel momento in cui l'intero spazio è stato esplorato (o meglio quando tuttii nodes ed i node-links sono attivi) si da il via alla fase di sfoltimento e successivoconsolidamento delle connessioni.

Figura 10: Raggiungimento della convergenza alla traiettoria ottima.

Come evidenziato nei plots in Figura 10, il cutting delle connessioni è molto piùveloce rispetto alla fase di reinforcement. Il sistema converge in�ne alla traiettoriaottima. È interessante inoltre studiare il caso di connessioni con raggio minore,lasciando inalterata la density-of-nodes.

17

Figura 11: Connessioni a corto raggio.

Dalla Figura 11 si evince che in tal caso il sistema non converge ad un'unicasoluzione. Ciò è dovuto al fatto che tra i vari modi di connettere le due fonti di cibonon sia presente quello ottimale. In tal modo viene meno l'unicità della soluzioneed il sistema risulta (giustamente) incapace di scegliere tra percorsi aventi "costo"equivalente. Nel caso speci�co, a�nché il sistema converga alla traiettoria ottima, ènecessario elevare ad un valore di 80 la densità dei nodes.

2.4 Conclusione e Futuri sviluppi

Essendo ben noto quanto sia necessario lo sviluppo di tecnologie da applicare a reticomplesse come quella dei trasporti, gli obiettivi futuri di questa ricerca sono:

• Migliorare l'integrazione dell'equazione (4) ricorrendo all'utilizzo di un algo-ritmo di integrazione di ordine più elevato. Un modo possibile di attuare taleoperazione è combinare l'utilizzo di NetLogo con quello di R.

• Ridurre i tempi della fase di consolidamento. Come evidenziato dai plots inFigura 10, essa rappresenta circa i 2/3 delle iterazioni necessarie al sistema perconvergere.

• Generalizzare il modello al caso di più fonti di cibo, rappresentanti i quartieridi una città.

In particolare, una possibile via da percorrere per realizzare quest'ultima esten-sione sarebbe quella di lasciar "ordinare" alla Physarum P. le fonti di cibodurante la sua fase di espansione. Per meglio dire lasciarle assegnare ad ognu-na il proprio food-source-number, distinguendo così nodes di immissione e discarico. A tal proposito riporto il seguente blocco di codice:

18

Figura 12: Code. Generalizzazione

Ogniqualvolta la mu�a incontra un pezzo di avena (i quali inizialmente hannotutti food-source-number pari a 3), lo classi�ca in base al food-source-number diquello più vicino (precedentemente incontrato).

L'ABM analizzato mostra chiaramente come l'ordine macroscopico emerga dalbasso verso l'alto, tramite l'assegnazione di una singola regola ad ogni agente. Ciòrende �essibile l'analisi del comportamento della Physarum P., presentando all'uten-te un ampio panorama di risultati da interpretare, che aiuta a comprendere meglioil fenomeno.

19

3 Bibliogra�a

Riferimenti bibliogra�ci

[1] V. Bonifaci, K. Mehlhorn, and G. Varma. Physarum can compute shortestpaths Journal of Theoretical Biology, 309:121-133, 2012.

[2] X. Zhang, Y. Zhang, Z. Zhang, S. Mahadevan, A. Adamatzky, Y. Deng. Ra-pid Physarum Algorithm for shortest path problem. Applied Soft Computing,23:19-26, 2014.

[3] Wilensky, U. (2003). NetLogo Fur model.http://ccl.northwestern.edu/netlogo/models/Fur. Center for Connected

Learning and Computer-Based Modeling, Northwestern University, Evanston,

IL.

[4] Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Cen-

ter for Connected Learning and Computer-Based Modeling, Northwestern

University, Evanston, IL.

[5] https://www.youtube.com/watch?v=czk4xgdhdY4.

21