4.8 More Complicated Problem: Finding the Shortest Path in a Labyrinth

4.8 More Complicated Problem: Finding the Shortest Path in a Labyrinth

The problem of searching for a path in a labyrinth determined by certain conditions is one of the most prevalent contemporary problems of high computational complexity. There have been a variety of attempts to find effective algorithms for solving this problem (see, for instance, Adamatzky 1996 and references to it).

Proposals to use reaction-diffusion media for solving labyrinth problems have been discussed for the last decade and a half (see, for instance, Conrad et al. 1989; Babloyantz and Sepulchre 1991; P rez-Mu uzuri, P rez-Villar, and Chua 1993; Steinbock, Toth, and Showalter 1995; (Adamatzky 1996; Agladze et al. 1997; Mu uzuri and Chua 1998), relying extensively on the extremely high parallelism of such systems. The most important attempt was an experimental work by Steinbock, Toth, and Showalter (1995), who investigated the navigation of a complex labyrinth based on using the trigger wave processes of Belousov-Zhabotinsky media. Conclusions on the practical applicability of these reaction-diffusion systems has, until now, been pessimistic (Agladze et al. 1997) because of the very low velocity of trigger waves in these media.

Let us define a labyrinth as an object whose topological properties can be associated with a finite oriented graph. This means that the object should be composed of an arbitrary number of vertices and edges connecting them. Let us divide vertices into four classes: starting points that are entrances into the labyrinth (the power of the vertex is equal to 1), intermediate points (the power is ≥2), deadlocks and target points (the power of these vertices is equal to 1).

The graphs with the simplest structure are trees (figure 4.17). They have one starting point and an arbitrary number of branches and target points. Multigraphs containing cyclic combinations of edges are more complicated. In this case, at least two routes might be determined to exist between the chosen starting and target points.

Figure 4.17: Labyrinth structures of different complexity. (A) Simple tree-type labyrinth. (B) Tree-type labyrinth containing cycles (filled with gray color). (C) Complicated labyrinth containing cycles and arbitrary numbers of starting and target points.

The basic principles for using light-sensitive reaction-diffusion media to solve labyrinth problems will be discussed below for the case of relatively simple graphs, the target being to find the shortest path between a starting point and a chosen target point. Three principal points are assumed:

Hybridity

Any information processing system based on reaction-diffusion mechanisms and capable of solving labyrinth problems should be of a hybrid type. It should be a combination of a reaction-diffusion medium with a universal digital computer. This architecture enables the efficient performance of operations of high computational complexity (parallel spreading of a wave along all pathways of labyrinth, etc.) with fast digital processing of any intermediate data.

Let us make some remarks on how to design an effective computational procedure for finding paths in a labyrinth. Given the computational nature of the procedure, the labyrinth should be stored in memory as an image (in the simplest case, as a black-and-white image—e.g., a black picture of the labyrinth on a white background). Suppose that only the starting point of the labyrinth has been defined and that a procedure is to be designed that would give the opportunity to record consecutive steps of the spreading wave. When the wave spreads along the path of the labyrinth, the color changes to that of the background. A more sophisticated procedure could be developed that enables one to follow the wave front and to determine the point where the black labyrinth path would disappear. In this case, it is impossible to distinguish between deadlocks and target points.

Therefore, to find a path in a labyrinth, both starting point and target points should be defined. More precisely, certain features should be included in the labyrinth image to mark target points and to help to determine when a wave would reach it.

Suppose now that the starting point and target points are known. Suppose also that a trigger wave spreads along the labyrinth beginning from its starting point. Eventually, the wave would reach the target point nearest to the starting point. After that, other target points would be successfully determined.

It is easy to see that in this case, only the relative lengths of paths could be determined and not the paths themselves. This technique shows the principal feature of a computational procedure for finding paths in a labyrinth based on wave processes inherent in nonlinear reaction-diffusion media.

The spreading of the wave through a labyrinth is a parallel operation of high computational complexity. A reaction-diffusion medium is able to perform this operation effectively, and consecutive steps of it could be stored in the memory of a digital computing system.

It will be shown below that a computational digital procedure of low computational complexity could be outlined that is capable of finding paths in a labyrinth and is based on the set of data stored in computer memory that describe the spreading wave through the labyrinth.

Image Storage

The most important problem is how to store a labyrinth of arbitrary structure in the reaction-diffusion medium for its further processing. Steinbock, Toth, and Showalter (1995) solved this problem by cutting out rectangular regions of the membrane where ferroin catalyst was immobilized. This procedure allowed the realization of a variety of geometries and provided an effective two-dimensional system. Steinbock, Kettunen, and Showalter (1995, 1996) prepared a reaction-diffusion system by printing an object image on the surface of a membrane, and using a solution of Belousov-Zhabotinsky catalyst instead of ink. These methods, however, are not good enough for a computing device that should be capable of fast reorganization of labyrinth images in the course of its processing and of operative changing labyrinths of different structure (see below).

A light-sensitive B-Z reagent seems an appropriate candidate medium because of the ability of light-sensitive excitable media to store input information for a rather long period of time (Kuhnert, Agladze, and Krinsky 1989). The initial labyrinth image and steps of its further transformation in the medium (that is, spreading wave evolution) can be detected by a video camera and stored in a digital computer memory. After this, finding the shortest paths in a labyrinth can be reduced to image processing operations.

Organization

The main and decisive point of the problem under consideration is how to organize a wave process capable of spreading in a parallel mode through all possible paths of a labyrinth.

Two kinds of traveling processes inherent in interaction-diffusion systems are known (Reusser and Field 1979). The first of these represents the propagation of trigger waves due to the interaction between the chemical reaction and the diffusion of reaction components. The velocity of the trigger waves is very low (~0.05 mm/sec). The second of these, the so-called phase waves, propagate independently of diffusion along a phase gradient in an oscillatory medium. These phase waves are fast, but difficult to control.

The remarkable property of Ru-catalyzed Belousov-Zhabotinsky media is the possibility to control phase processes in the medium by light radiation (see also Agladze, Obata, and Yoshikawa 1995).

The actual picture projected on the surface of the medium is a combination of the chosen black-and-white image (initial labyrinth image) and the arbitrary halftone diffuse-light background produced by the optical system.

If the background is uniform, the input image emerges in the medium and changes simultaneously in a process of its evolution from one state to another at all points of the image. If the background is not uniform, an additional uncontrolled light component adds to the input image and the process of the image emergence becomes more complicated (figure 4.18).

Figure 4.18: Principal scheme explaining the initiation of a light-induced phase wave. Non-uniform light background I(x) is in the upper part of the figure. Temporal evolution of catalyst concentrations at different points of the medium is in the basic part of the figure.

The dynamics of the Belousov-Zhabotinsky reaction is controlled by the concentration of Br ions produced in the initial photochemical process occurring in the input of an initial image. Therefore the moment when an image emerges at a point of the medium (and the subsequent evolution of that image) is determined by the total exposure produced by the initial image and the uncontrolled nonuniform background.

This effect is revealed in the experiment as additional waves spreading along the image under investigation (figure 4.18). Let us define this effect as light-induced phase waves.

Suppose that the self-oscillating mode of a Belousov-Zhabotinsky reaction is chosen for solving labyrinth problems when negative and positive images of input picture alternate in the process of temporal image evolution produced by the medium. Suppose also that the quality of the optical system is high enough and the uncontrolled background is negligibly small. In this case, both the negative and positive images emerge in the process of the input picture evolution simultaneously at all their points.

Let us further suppose that the controlled nonuniform background of some predetermined shape is superimposed on an initial labyrinth image (figure 4.19). This combined picture is used instead of the initial image. Then a light-induced phase wave controlled by the shape of the background will spread through the medium.

Figure 4.19: The initial labyrinth image (I), a non uniform background superimposed on the initial labyrinth image (IW), and first stages of the labyrinth evolution (phase wave spreading) in a Belousov-Zhabotinsky medium (L1–L3).

The procedure for finding the shortest paths in a labyrinth consisted of two basic stages. The first was the excitation of the phase wave at a chosen point of the labyrinth and recording the consecutive steps of the wave spreading through the labyrinth. The images of the labyrinth corresponding to these steps were stored in the computer memory. The second stage was the numerical processing of these images to determine the shortest path between starting and target points of the labyrinth.

Let us begin discussing the technique by investigating the case of the simplest linear treelike labyrinth, having one starting and several target points. The initial labyrinth picture is shown in figure 4.20.

Figure 4.20: Finding the shortest path in a simple tree-type labyrinth. L0 is an initial image of the labyrinth in the Belousov-Zhabotinsky medium, L1–L4, some consecutive steps of its evolution in the process of the wave spreading; LF, the image of the shortest path in the labyrinth; L0-1, the pathway which the wave has passed during the first step of its spreading; L1-1, the result of Paint Bucket operations for L1 image; L1-2, the result of subtraction from the L1 image of parts unconnected with the target point (see details in text).

Let a predetermined nonuniform and monotonically decreasing background be superimposed at a chosen point of the initial labyrinth picture. After projecting this combined picture on the surface of the Belousov-Zhabotinsky reagent, its negative image appears in the medium. At first, an image of the initial labyrinth emerges (black image on the white background). After that, a spreading wave appears, changing consecutively from black to the background color along the labyrinth pathway.

The time necessary to spread this wave through the labyrinth depends on the gradient of the superimposed background intensity. It is easy to make it rather quick (about 3–5 sec) and shorter than the lifetime of the negative image state when it evolves from a negative to a positive state.

The wave spreading in the labyrinth, beginning from the starting point of the labyrinth to its target points, is shown in figure 4.20. Because this process lasts for about 3–5 seconds, it is easy to record consecutive steps of this dispersal with a video camera and store these records in computer memory. Some of these records are shown in figure 4.20.

Finding the shortest path between the starting point and the target point was then performed using numerical image processing of stored records.

Proposals have already been made on how to use a wave propagating through a labyrinth for finding minimal paths (P rez-Mu uzuri, P rez-Villar, and Chua 1993; Agladze et al. 1997; Mu uzuri and Chua 1998; see also references to Mu uzuri and Chua 1998). A different procedure estimated to be more effective computationally was used in this work.

In the process of the wave spreading through the labyrinth, when it passes over a branching point, it is divided into two (or more) fragments (figure 4.21). One of these is connected with the output, but the other one is not. It is easy to find the fragment connected with a target point of the labyrinth if a backward wave is initiated in the medium at this point. As a result, fragments connected with a target point change their color (from black to the color of labyrinth background) while the color of the nonconnected fragment remains unchanged.

Figure 4.21: Basic steps of the procedure for finding the shortest paths in a labyrinth. (A) Wave propagation. (B) Check for connectedness. (C) Removal of deadlocks (subtraction of B and A).

If the complexity of the labyrinth is not too high, it is possible to change this auxiliary reaction-diffusion process by numerical processing images of the labyrinth stored in the memory of the computer. The technique is to fill black fragments with the background color ("paint bucket" operation), initiated at the target point of the labyrinth. Subtracting the resultant image from the initial labyrinth image enables one to remove fragments not connected with the output.

All image processing operations used for the implementation of the procedure discussed can be effectively performed by means of Adobe Photoshop 5.0 software.

Successive repetition of this procedure at every branching point gives the opportunity to exclude all blind channels (and paths to other possible target points) and to determine the path from the starting to the target point.

Two important remarks should be made about the procedure suitable for finding minimal paths in linear treelike labyrinths:

First, the advantage of the above procedure is that there is no need to determine through human intervention where a branching point occurs. The shortest path can be found in this case as a result of reiterated steps that consecutively process records of the spreading wave.

The sequence of operations for each step is as follows (assuming that record processing begins from L1; see figure 4.20):

• Subtraction of record L1 from the initial image of the labyrinth L0 to determine the pathway that the wave traversed going from initial to target points (L0-1)

• Filling fragments of L1 connected with a target point with background color (L1-1)

• Subtraction of L1-1 from L1—that is, rejection of parts not connected with a target point (L1-2, subtraction of any fragment from the background intensity should result in a zero level of intensity)

• Addition of L0-1 and L1-2 to determine the subsequent image of the labyrinth (L01), which is used at the next step instead of L0

• Changing L0 to L01

Each instantaneous image, after processing, is as follows:

• The same as the previous instantaneous image of the labyrinth if the wave has not passed over a branching point

• A changed instantaneous image where some parts of the labyrinth are rejected if the wave has passed over a branching point

The second important remark is that changing the backward wave via a paint bucket operation to determine parts of the labyrinth not connected with a target point is not absolutely correct, because the paint bucket operation is not carried out in parallel. It is possible to use this, however, if the complexity of the labyrinth is not very high and the time of labyrinth processing is not too long.

The procedure discussed is simple and effective in the case of linear treelike labyrinths where all possible pathways from a starting point to target points have nearly the same direction that coincide with the direction of the spreading wave. In a general case, however, this procedure should be changed because light-induced phase waves will spread along the gradient of the background intensity and not necessarily along the pathways of a labyrinth that can change direction significantly.

Changing the procedure offered allows us to elaborate the technique into something suitable for more complicated labyrinths.

This "step-by-step" technique is based on dividing the labyrinth into linear treelike parts and on the reiterative processing of each of them. An individual step of this technique would consist of the following operations:

• Determination of the labyrinth pathway direction at a chosen starting point

• Excitation of a phase wave at a chosen starting point that would spread along the gradient of the background intensity (which coincides in this case with the labyrinth pathway direction) and recording consecutive steps of the spreading

• Rejection of possible blind pathways

• Determination of pathway turning points

The "individual" step ends at a pathway turning point, which is considered as a starting point for the next step.

The most important part of this step-by-step technique is the determination of the pathway turning points. The results shown below were obtained by using visual control of the process of finding paths in a labyrinth. At the same time, algorithms could be offered for the implementation of this technique. (We are presently developing a computerized version of how to carry out the step-by-step procedure without a human being as an operator; this work will be published elsewhere.)

This main idea of moving step by step along a labyrinth pathway (as used here) is analogous to a numerical simulation approach successfully developed by Mu uzuri and Chua (1998) for finding the shortest paths in an arbitrary complex labyrinth.

An example of finding the shortest path in a labyrinth based on the technique discussed is shown in figure 4.22.

Figure 4.22: Finding the shortest path in an arbitrary labyrinth. L0 is the initial image of the labyrinth in the BelousovZhabotinsky medium; (A) stages of its evolution; LF1 and LF2 are images of the shortest paths (see details in text); (B) results of Paint Bucket operations.

The important feature of this case is that the labyrinth under investigation is of a multigraph type containing a cyclic combination of edges. Therefore the path between starting and target points, after using the step-by-step technique, contains some remaining part of this cycle (see figure 4.22, LF1). But this will disappear (see figure 4.22, LF2) if the step-by-step technique is repeated over and over, with the shortest path obtained (figure 4.22, LF1) becoming the new labyrinth.

Several points should be made about the practical implementation of this algorithm and for the estimation of its efficiency. The main operational feature of the Ru-based Belousov-Zhabotinsky system is that it is highly sensitive to small variations in experimental conditions. The quality of the optical system used for the input of initial data should therefore be high, with the reaction vessel being thereafter thoroughly shielded from outside light radiation.

The quality of images produced by the Belousov-Zhabotinsky medium is determined by the constant thickness of the medium layer at all points. Two methods of medium formation satisfying this condition have been elaborated (Rambidi, Kuular, and Machaeva 1998; see below).

Let us make some remarks on the efficiency of the technique discussed above. When a wave goes over a branching point, some part of the labyrinth is removed as a result of the procedure used. The more complicated the labyrinth is, the larger the parts that will be rejected in the process of finding the shortest paths. Therefore, the remarkable feature of this technique is that its efficiency becomes higher as the complexity of the labyrinth increases.

Using a step-by-step procedure significantly increases the time necessary to find the shortest paths in a labyrinth. The efficiency of the procedure depends on the operational time of the reaction-diffusion medium and on the number of labyrinth turning points in this case. Nevertheless, it is sufficiently higher than the efficiency of procedures using trigger waves (Steinbock, Toth, and Showalter 1995; Agladze et al. 1997). The time necessary for processing a labyrinth of average complexity is about 5 minutes, assuming a cycle time of the medium of about 40 seconds. This time is less by an order of magnitude in comparison with that of the "trigger wave procedure" (Steinbock, Toth, and Showalter 1995). Another important feature is that the operational time is linear with the number of the labyrinth pathway turning points.