Physarum Can Compute Shortest Paths

Abstract

Physarum Polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s0 and s1. We prove that, under this model, the mass of the mold will eventually converge to the shortest s0 - s1 path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by the biologists and can be seen as an example of a "natural algorithm", that is, an algorithm developed by evolution over millions of years.

Accepted in SODA 2012

References in corpus (1)

• Convergence Properties for the Physarum Solver

Cited by in corpus (24)

• Collaborative search on the plane without communication
• Numerical Solution of Monge-Kantorovich Equations via a dynamic formulation
• Towards a stationary Monge-Kantorovich dynamics: the Physarum Polycephalum experience
• On the Runtime of Universal Coating for Programmable Matter
• The ANTS problem
• Multicommodity routing optimization for engineering networks
• IRLS and Slime Mold: Equivalence and Convergence
• Two Results on Slime Mold Computations
• Physarum-inspired Network Optimization: A Review
• Cohesive urban bicycle infrastructure design through optimal transport routing in multilayer networks
• A revised model of fluid transport optimization in Physarum polycephalum
• Ameba-inspired Self-organizing Particle Systems
• Physarum Dynamics and Optimal Transport for Basis Pursuit
• Convergence of the Non-Uniform Directed Physarum Model
• Solving the Steiner Tree Problem in Graphs using Physarum-inspired Algorithms
• Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation
• On the Convergence Time of a Natural Dynamics for Linear Programming
• Thirty eight things to do with live slime mould
• Towards slime mould electrical logic gates with optical coupling
• A Physarum-Inspired Approach to Optimal Supply Chain Network Design at Minimum Total Cost with Demand Satisfaction
• Memory Lower Bounds for Randomized Collaborative Search and Applications to Biology
• Nearly Tight Bounds for Sandpile Transience on the Grid
• A differential model for growing sandpiles on networks
• Improved Convergence for ${\ell }_{\infty }$ and ${\ell }_1$ Regression via Iteratively Reweighted Least Squares