Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

| Crea un account

Facca, Enrico (2018) Biologically inspired formulation of Optimal Transport Problems. [Tesi di dottorato]

Full text disponibile come:

[img]
Anteprima
Documento PDF
15Mb

Abstract (inglese)

In this thesis we propose a model that we conjecture is a new and original formulation of the Optimal Transport Problem, a recently expanding area of mathematics that studies optimal strategies to move resources from one place to another. The proposed approach is an infinite-dimensional extension of a model describing the dynamics of Physarum Polycephalum (PP), a slime mold with surprising abilities to find the shortest path connecting two food sources. The original model describes the dynamics of the slime mold on a finite planar graph using a pipe-flow analogy whereby mass transfer occurs because of pressure differences with a conductivity coefficient that varies with the flow intensity. This model has been shown to be equivalent to a problem of "optimal transportation" on graphs.

Our extension abandons the graph structure and moves to a continuous domain, coupling an elliptic diffusion equation enforcing PP density balance with an ordinary differential equations governing the flow dynamics. We conjecture that the new system of equations presents a time-asymptotic equilibrium connected to solutions of many instances of OTP, including the standard L1 case and the congested and branched transport problems.
From a theoretical point of view, we are only able to prove well-posedness of the proposed model for sufficiently small times and under restrictive hypothesis on the the regularity of the diffusion coefficient and the functions describing the initial and final configurations of the transported mass. However, our extensive numerical results show that the approximate solution of our proposed formulation converges at large times to an equilibrium configuration that well compares with the solutions of the different flavors of OTP. In particular, we are able to efficiently recover the numerical solutions that closely resemble the singular and ramified structures typical of branched transport problems. These simulations provide strong support to our conjectures. Notwithstanding the numerical difficulties related mainly to the ill-conditioning of the algebraic systems, the rather simple approach adopted for the discretization of the proposed formulation resulted highly efficient and robust in terms of convergence and computational speed.

We also propose and tackle several applications to real world problems. In particular, we discuss how our formulation can be applied to model the geomorphology of river networks and the dynamics of plant roots. In addition, based on numerical evidence, we argue that the emergence of robustness-enhancing loops in complex networks can be attributed to non-stationarity of the forcing terms rather than optimality of the network configuration.

Abstract (italiano)

In questa tesi proponiamo un nuovo modello che congetturiamo rappresenti una nuova formulazione del Problema di Trasporto Ottimo, un'area della matematica notevolmente sviluppatasi negli ultimi ultimi anni e che studia come trasportare in maniera efficiente delle risorse da un luogo ad un altro.

La formulazione da noi proposta è l'estensione infinito-dimensionale di un modello nato per descrivere il comportamento di una muffa, dal nome Physarum Polycephalum (PP), capace di trovare il cammino minimo tra due fonti di cibo. Nel modello originale, definito su grafi, il corpo di PP viene schematizzata come un tubo attraverso il quale il trasporto di risorse avviene per mezzo di un flusso dato dal prodotto di un gradiente di pressione per un coefficiente di diffusione. Quest'ultimo varia nel tempo in funzione dell'intensità del flusso stesso, descrivendo in tal modo la dinamica adattativa della muffa.

L'equivalenza tra tale modello e la soluzione di problemi di trasporto ottimo su grafi è già stata dimostrata. Il formulazione da noi proposta abbandona la struttura finito dimensionale del grafo per passare in un ambiente continuo. Il derivante modello è descritto da un sistema composto da un'equazione ellittica con un coefficiente di diffusione e un'equazione differenziale ordinaria per il coefficiente. In questa tesi proponiamo la congettura che quest'ultimo sistema ammetta un equilibrio stazionario legato alla soluzione di problemi di trasporto ottimo, sia per il caso L1, sia per i problemi di trasporto congestionato e ramificato.

Da un punto di visto teorico, siamo riusciti a provare che il modello è ben posto solo assumendo determinate ipotesi di regolarità del coefficiente di diffusione e delle densità che descrivono la configurazione iniziale e finale delle masse trasportate. Nonostante ciò, numerosi risultati numerici mostrano come la soluzione approssimata del nostro modello converga a soluzioni stazionarie che ben si confrontano con la soluzione dei sopracitati problemi di trasporto ottimo. Riusciamo inoltre ad ottenere soluzioni numeriche che assomigliano fortemente alle strutture singolari del trasporto ramificato, dando ulteriore supporto alle nostre congetture. Nonostante alcune difficoltà numeriche, essenzialmente legate al malcondizionamenteo di sistemi lineari, lo schema numerico utilizzato per la discretizzazione del nostro modello, la cui implementazione risulta relativamente semplice, si è rivelato estremamente efficiente e robusto, sia da punto di visto delle convergenze numeriche, sia dal punto di vista dell'efficienza computazionale.

Il nostro modello si presta inoltre a numerose applicazioni a problemi reali, come lo studio della morfologia dei fiumi e la modellizzazione dell'evoluzione delle radici delle piante, argomenti discussi nella parte finale della tesi. In ultimo, sulla base di prove numeriche, analizziamo come la presenza di loop in reti complesse, indice della loro robustezza, possa essere interpretata non come una proprietà di "ottimalità" della rete stessa, bensì come un riflesso della non stazionarietà delle forzanti.

Statistiche Download
Tipo di EPrint:Tesi di dottorato
Relatore:Putti, Mario - Cardin, Franco
Correlatore:Putti, Mario
Dottorato (corsi e scuole):Ciclo 30 > Corsi 30 > SCIENZE MATEMATICHE
Data di deposito della tesi:16 Febbraio 2018
Anno di Pubblicazione:16 Febbraio 2018
Parole chiave (italiano / inglese):Optimal Transport Problem, Branched Transport Problem, Numerical solution
Settori scientifico-disciplinari MIUR:Area 01 - Scienze matematiche e informatiche > MAT/08 Analisi numerica
Area 01 - Scienze matematiche e informatiche > MAT/05 Analisi matematica
Struttura di riferimento:Dipartimenti > Dipartimento di Matematica
Codice ID:11136
Depositato il:25 Ott 2018 16:14
Simple Metadata
Full Metadata
EndNote Format

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record