×

Towards a stationary Monge-Kantorovich dynamics: the Physarum Polycephalum experience. (English) Zbl 1385.49012

Summary: In this work we propose an extension to the continuous setting of a model describing the dynamics of slime mold, Physarum Polycephalum (PP), which was proposed to simulate the ability of PP to find the shortest path connecting two food sources in a maze. The original model describes the dynamics of the slime mold on a finite-dimensional 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. We propose an extension that abandons the graph structure and moves to a continuous domain. The new model couples an elliptic diffusion equation enforcing PP density balance with an ordinary differential equation governing the flow dynamics. We conjecture that the new system of equations presents a time-asymptotic equilibrium and that such an equilibrium point is precisely the solution of Monge-Kantorovich partial differential equations governing optimal transportation problems. To support this conjecture, we analyze the proposed model by recasting it into an infinite-dimensional dynamical system. We are then able to show well-posedness of the proposed model for sufficiently small times under the hypotheses of Hölder continuous diffusion coefficients and essentially bounded forcing functions. Numerical results obtained with a simple fixed-point iteration combining \(\mathcal P_1 / \mathcal P_0\) finite elements with backward Euler time stepping show that the approximate solution of our formulation of the transportation problem converges at large times to an equilibrium configuration that well compares with the numerical solution of the Monge-Kantorovich equations.

MSC:

49K20 Optimality conditions for problems involving partial differential equations
49M25 Discrete approximations in optimal control
35J70 Degenerate elliptic equations
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
90B06 Transportation, logistics and supply chain management

References:

[1] A. Adamatzky, {\it Physarum Machines: Computers from Slime Mould}, World Scientific, Singapore, 2010.
[2] L. Ambrosio, {\it Lecture notes on optimal transport problems}, in Mathematial Aspects of Evolving Interfaces, Lecture Notes in Math. 1812, Springer, Berlin, 2003, pp. 1-52. · Zbl 1047.35001
[3] L. Ambrosio, A. Carlotto, and A. Massaccesi, {\it Lecture Notes on Partial Differential Equations}, (2010). · Zbl 1416.35001
[4] J. W. Barrett and L. Prigozhin, {\it A mixed formulation of the Monge-Kantorovich equations}, Math. Model. Numer. Anal., 41 (2007), pp. 1041-1060. · Zbl 1132.35333
[5] P. Bochev and R. B. Lehoucq, {\it On the Finite Element Solution of the Pure Neumann Problem}, SIAM Rev., 47 (2005), pp. 50-66. · Zbl 1084.65111
[6] V. Bonifaci, K. Mehlhorn, and G. Varma, {\it Physarum can compute shortest paths}, J. Theoret. Biol., 309 (2012), pp. 121-133. · Zbl 1411.92332
[7] V. Bonifaci, K. Mehlhorn, and G. Varma, {\it Physarum can compute shortest paths: A short proof}, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 2012, SIAM, Philadelphia, 2012, pp. 233-240. · Zbl 1420.68088
[8] G. Bouchitté, G. Buttazzo, and P. Seppecher, {\it Shape optimization solutions via Monge-Kantorovich equation}, C. R. Acad. Sci. Paris Ser. I Math, 324 (1997), pp. 1185-1191. · Zbl 0884.49023
[9] F. Brezzi and M. Fortin, {\it Mixed and Hybrid Finite Element Methods}, Springer, Berlin, 1991. · Zbl 0788.73002
[10] G. Buttazzo and E. Stepanov, {\it On regularity of transport density in the Monge-Kantorovich problem.}, SIAM J. Control Optim., 42 (2003), pp. 1044-1055. · Zbl 1084.49036
[11] S. Campanato, {\it Equazioni ellittiche del ii^o ordine e spazi L^(2,łambda)}, Ann. Mat. Pura Appl. (4), 69 (1965), pp. 321-381. · Zbl 0145.36603
[12] M. Colombo and G. Mingione, {\it Bounded minimisers of double phase variational integrals}, Arch. Ration. Mech. Anal., 218 (2015), pp. 219-273. · Zbl 1325.49042
[13] L. De Pascale and A. Pratelli, {\it Sharp summability for Monge transport density via interpolation}, ESAIM Control Optim, Calc. Var., 10 (2004), pp. 549-552. · Zbl 1072.49033
[14] L. C. Evans and W. Gangbo, {\it Differential Equations Methods for the Monge-Kantorovich Mass Transfer Problem}, Mem. Amer. Math. Soc., 653, AMS, Providence, RI, 1999. · Zbl 0920.49004
[15] M. Feldman and R. J. McCann, {\it Uniqueness and transport density in Monge’s mass transportation problem}, Calc. Var. Partial Differential Equations, 15 (2002), pp. 81-113. · Zbl 1003.49031
[16] M. Giaquinta and L. Martinazzi, {\it An Introduction to the Regularity Theory for Elliptic Systems, Harmonic Maps and Minimal Graphs}, Edizione della Normale, Pisa, 2012. · Zbl 1262.35001
[17] C. B. Morrey Jr, {\it Second-order elliptic systems of differential equations}, in Contributions to the Theory of Partial Differential Equations, Princeton University Press, Princeton, NJ, 1954, pp. 101-159. · Zbl 0057.08301
[18] T. Nakagaki, H. Yamada, and A. Toth, {\it Maze-solving by an amoeboid organism}, Nature, 407 (2000), 470.
[19] A. Tero, R. Kobayashi, and T. Nakagaki, {\it A mathematical model for adaptive transport network in path finding by true slime mold}, J. Theoret. Biol., 244 (2007), pp. 553-564. · Zbl 1450.92052
[20] A. Tero, S. Takagi, T. Saigusa, K. Ito, D. P. Bebber, M. D. Fricker, K. Yumiki, R. Kobayashi, and T. Nakagaki, {\it Rules for biologically inspired adaptive network design.}, Science, 327 (2010), pp. 439-442. · Zbl 1226.90021
[21] G. Troianiello, {\it Elliptic Differential Equations and Obstacle Problems}, Univ. Ser. Math., Plenum, New York, 1987. · Zbl 0655.35002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.