Reaction-diffusion computing utilises the complex auto-catalytic and diffusive interactions underlying self-organising systems for practical computing tasks – developing variants of classical logical computing devices, or direct spatial embodiments of problem representations and solutions. We investigate the concept of passive and active approaches to reaction-diffusion computing. Passive approaches use front propagation as a carrier signal for information transport and computation. Active approaches can both sense and modify the propagation of the underlying carrier signal. We also consider the differences in attraction and repulsion behaviour for both passive and active approaches. Using particle approximations of reaction-diffusion behaviour in chemical systems, and the plasmodium of Physarum polycephalum, we demonstrate the similarities and differences between the passive and active approaches using both attraction and repulsion behaviour. We provide examples of how the approaches can be used for complex spatially represented computational tasks. We note that the active approach results in second-order emergent behaviour, exhibiting complex quasi-physical properties such as apparent surface tension effects and network minimisation which may have utility in future physical implementations of reaction-diffusion computing devices.
TopIntroduction
The natural world (both purely physical and living) appears to take the assembly of complex structures in its stride - producing complex, dynamic, functional and reliable structures in what would be considered very noisy and unpredictable environments. Such complex pattern forming behaviour exploits properties of self-organisation – the spontaneous formation of order when energy is input into a system. One of the most complex self-organisation mechanisms is reaction-diffusion (RD) patterning, where complex patterns emerge from almost homogeneous environments. Turing’s explanation of how complex patterning could emerge in an almost homogeneous two chemical system, which would previously have been expected to remain at equilibrium, laid the foundation for future exploration of spatial chemical patterning (Turing, 1952).
Babloyantz suggested that the travelling wavefronts from chemical reactions using excitable media could be used to propagate information for spatial problems (Babloyantz & Sepulchre, 1989). The non-equilibrium dynamics of the chemical reactions that underlie excitable media have both an autocatalytic component and a diffusion component. The resulting wavefront propagates forwards at a constant velocity, does not dissipate (at least not significantly) over time and has a post-excitation refractory period so that the shape of the advancing front is made visible. Chemical waves are annihilated at boundaries and where fronts meet, so avoiding reflection and interference patterns. Steinbock, Toth and Showalter used wave propagation in the Belousov-Zhabotinsky (BZ) chemical reaction to traverse the shortest path through a maze (Steinbock, Toth, & Showalter, 1995). Although computationally efficient, since the waves perform a parallel search or route branches, the spatial requirements are substantial since a direct spatial encoding of the problem must be stored, as opposed to a graph encoding in conventional approaches.
There are some disadvantages to the solution of the maze by chemical wave approaches. The first is that the propagation speed of the reaction is inherently slow. Steinbock et al. estimated that their wavefront moved at 2.41mm per minute (approximately 0.04 mms-1). In an attempt to overcome the speed limitation, Asai et al. developed hybrid analogue/digital silicon VLSI circuits that implemented wave propagation and were used to compute approximations of Voronoi diagrams (Asai, Costello, & Adamatzky, 2005). Karahaliloglu also implemented a hardware shortest path device in a coupled cellular neural network on a CMOS substrate (Karahaliloglu, 2006). Ito et al. developed a software model of reaction-diffusion and used a separate backtracking algorithm to traverse the path backwards through the obstacle field to find the shortest path (Ito, Hiratsuka, Aoki, & Huguchi, 2006).
Although reaction-diffusion front propagation provides a powerful means of parallel search, the difficulty in eliciting the results from the wavefront map necessitates a separate stage to ‘read out’ the results. This stage can be a separate software algorithm to traverse the front path, or hybrid systems where chemical processor result is sampled and recorded for further semi-automated processing. Adamatzky noted the difficulty in configuring and programming chemical processors and suggested a multi-layered approach where the output of one reactor could influence the behaviour of another (Adamatzky, 2005). As an example of a multi-layered approach Adamatzky et al. presented a software robot whose trajectory was influenced by reaction-diffusion processor fields via chemo-attraction (as a homing device) and chemo-repulsion (as an obstacle avoidance measure) (Adamatzky et al., 2004).