

A Simplistic Dynamic Circuit Analogue of Adaptive Transport Networks in True Slime Mold
HisaAki Tanaka, Kazuki Nakada, Yuta Kondo, Tomoyuki Morikawa, and Isao Nishikawa
Nonlinear Theory and Its Applications (NOLTA), IEICE, Apr. 2016.
Keyword
Biologyinspired Algorithm,
Shortest Path Search Methods,
Nonlinear Resistive Circuits
Abstract
This paper presents a simplistic dynamic circuit analogue for an adaptive transport network model in true slime mold by Tero et al.
This circuit analogue model is derived from Tero's model through nontrivial simplification under certain assumptions, and it realizes less computational complexity
through a reduction of the number of variables.
Despite of its simplicity, systematic simulations confirm that the shortest path search task is efficiently accomplished with this model;
(i) the shortest path is always identified, for various random networks;
(ii) if there are multiple, competing shortest paths in the network, they are simultaneously identified; and
(iii) for random deletions of a link in the shortest path, a new shortest path is quickly identified accordingly.
The model proposed here is easily implemented on the circuit simulator SPICE for instance, and hence the path search time will be further reduced with certain numerical devices including automatic adaptive numerical integration schemes as well as an acceleration method proposed in the end of the paper.
Download PDF
Figures at a glance
References

A. Tero, R. Kobayashi, and T. Nakagaki,
"Physarum solver: A biologically inspired method of roadnetwork navigation,"
Physica A, 363, pp. 115119, 2006.

A. Tero, R. Kobayashi, and T. Nakagaki,
"A mathematical model for adaptive transport network in path finding by true slime mold,"
J. Theor. Biol., 224, pp. 553564, 2007.

T. Nakagaki, H. Yamada, and Á. Tóth,
"Intelligence: Mazesolving by an amoeboid organism,"
Nature, vol. 407, p. 470, 2000.

T. Miyaji and I. Ohnishi,
"Physarum can solve the shortest path problem on Riemannian surface mathematically rigorously,"
Int. J. Pure and Applied Mathematics, vol. 47, no.3, pp. 353369, 2008.

V. Bonifaci, K. Mehlhorn, and G. Varma,
"Physarum can compute shortest paths,"
J. Theor. Biol., vol. 309, pp. 121133, 2012.

L. Becchetti, V. Bonifaci, M. Dirnberger, A. Karrenbauer, and K. Mehlhorn,
"Physarum can compute shortest paths: convergence proofs and complexity bounds,"
Automata, Languages, and Programming, pp. 472483, Springer, Berlin Heidelberg, 2013.

L. Zhu, M. Aono, S.J. Kim, and M. Hara
"Amoebabased computing for traveling salesman problem: Longterm correlations
between spatially separated individual cells of Physarum polycephalum,"
BioSystems vol. 112, no.1, pp. 110, 2013.

Y. Kondo and H.A. Tanaka,
"An Electric Circuit Analogue of a Mathematical Model for Adaptive Transport Network in True Slime Mold,"
Proc. NOLTA'07, pp. 521524, Vancouver, Canada, 1619 Sep. 2007.

DIMACS, Ninth DIMACS Implementation Challenge — Shortest Paths, 2006.
http://www.dis.uniroma1.it/challenge9/.

T. Ibaraki,
Algorithms and Data Structures in C, Shokohdo, 1999 (in Japanese).

S. Umetani, private communications, 2015.


