3.3 How Do We Simulate Reaction-Diffusion Processors?
Cellular automata models of reaction-diffusion and excitable media capture essential aspects of natural media in a computationally tractable form. A cellular automaton is a lattice of uniform finite automata. The automata evolve in a discrete time and take their states from a finite set. All automata of the lattice update their states simultaneously. Every automaton calculates its next state depending on the states of its closest neighbors.
We refer a reader to an excellent book by Chopard and Droz (1999) to gain background knowledge on cellular automata simulations of physical phenomena; see also Adamatzky (2001) for specific cellularautomaton models of reaction-diffusion computing.
3.4 Specialized Processors
The spatial representation of a problem is a key feature of reaction-diffusion processors. Data and results are represented through concentration profiles of the reagents or spatial configurations of activity patterns. A computation is defined in a physical space as well. The computation is realized by spreading and interacting waves of the reagents or excitation patterns. A computational code, or a program, is interpreted in a list of possible reactions between the diffusing components and in a form of diffusive or excitation coupling between microvolumes of the computing medium. Usually, such properties could not be changed online. But they can be determined and adjusted to work toward the solution of a particular problem. Therefore most reaction-diffusion processors are intentionally designed to solve a few particular problems—they are specialized. To give the reader a sense of these specialized processors in both automata and laboratory forms, the following sections will show designs of reaction-diffusion processors that subdivide a space and approximate a skeleton of a planar shape.
3.5 Plane Subdivision
Let P be a nonempty finite set of planar points—a Voronoi diagram of the set P is a partition of the plane into such regions, each for any element of P, that a region corresponding to a unique point p contains all those points of the plane that are closer to p than to any other node of P. A unique region assigned to point p is called a Voronoi cell of the point p; a union of all the edges of the Voronoi cells determines the Voronoi diagram.
Assuming the computing space is homogeneous and locally connected (à la cellular automata, where every node is coupled to its closest neighbors by the same diffusive links), we can easily draw a parallel between the distance and the time. There is a very simple intuitive technique for detecting the bisector points separating two given points of the set P. If we drop reagents at these two nodes, the diffusive waves (or phase waves if an active substrate) spread outward from the originating points with the same speed; they travel the same distance from the sites of origination before they meet with one another. The points where the waves meet are the bisector points.
In a naive version of reaction-diffusion computing of a Voronoi diagram, one needs two reagents and a precipitate to mark a bisector separating two points—that is, n reagents are required to approximate a Voronoi diagram of n points. We place n unique reagents on n points of the given set; waves of these reagents spread around the space and interact with each other when they meet. When at least two different reagents meet at the same or adjacent sites of the space, they react and form a precipitate, resulting in: the reaction-sites that contain the precipitate represent edges of the Voronoi cell and therefore constitute the Voronoi diagram. Actually, the number of reagents can be sufficiently reduced (literally to just two states) in cellularautomaton models: when the topology of the spreading waves of the excitation is taken into account (Adamatzky 2001), and in real experimental wet processors (Tolmachev and Adamatzky 1996; Adamatzky and De Lacy Costello 2002a).
In cellular-automaton models (Adamatzky 2001), a colored precipitate is formed when chemical waves collide with each other: colored sites are sites of Voronoi diagram edges, uncolored sites are simply "planar points". If we try to implement this idea in a real chemical medium, we find an even simpler solution: when two or more wave fronts collide, no colored precipitate will form at sites of their collision, while all other parts of the medium are colored with the precipitate. Thus the Voronoi diagram is represented by light (or uncolored) loci of the chemical medium.
A palladium processor (Tolmachev and Adamatzky 1996; Adamatzky and De Lacy Costello 2002a, 2002b) is a first-ever specialized chemical computer after Belousov-Zhabotinsky processors (see, e.g., Kuhnert, Agladze, and Krinsky 1986; Rambidi and Chernavskii 1991; Rambidi, Maximychev, and Usatov 1994; Rambidi et al. 2002) to be used for image processing and computational geometry. An active planar substrate is prepared by mixing agar gel with a solution of palladium chloride. This thin film of agar is placed on an acetate film. Sites corresponding to the planar points, which must be subdivided by Voronoi bisectors, are marked by drops of potassium iodide solution. The potassium iodide diffuses from the given points and fills almost the entire reaction space with a dark color, because a precipitate of palladium iodide is produced as the result of the reaction. When two diffusive wave fronts meet with one another, no precipitate is formed (this may happen due to exhaustion of potassium iodide, or concentration inhibition of the reaction, or even physical interaction—e.g., repulsion—of the diffusive fronts). Thus the bisectors of the Voronoi diagram are represented by colorless zones of the reaction space, as shown in figure 3.1.
Figure 3.1: Voronoi diagram, constructed in experimental reaction-diffusion processor. Bisectors are seen as light (uncolored) segments. Original data points are represented by light discs. (With permission of Benjamin de Lacy Costello, Bristol, UK.)