A Shortest Path Search Algorithm Using an Excitable Digital Reaction-Diffusion System

Koichi ITO  Masahiko HIRATSUKA  Takafumi AOKI  Tatsuo HIGUCHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.3   pp.735-743
Publication Date: 2006/03/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.3.735
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Multidimensional Signal Processing and Its Application)
Category: Signal Processing Algorithm
reaction-diffusion system,  nonlinear dynamics,  shortest path search,  excitable dynamics,  

Full Text: PDF(2.5MB)>>
Buy this Article

This paper presents a shortest path search algorithm using a model of excitable reaction-diffusion dynamics. In our previous work, we have proposed a framework of Digital Reaction-Diffusion System (DRDS)--a model of a discrete-time discrete-space reaction-diffusion system useful for nonlinear signal processing tasks. In this paper, we design a special DRDS, called an "excitable DRDS," which emulates excitable reaction-diffusion dynamics and produces traveling waves. We also demonstrate an application of the excitable DRDS to the shortest path search problem defined on two-dimensional (2-D) space with arbitrary boundary conditions.