Journal of Intelligent and Robotic Systems 37: 233–249, 2003. © 2003 Kluwer Academic Publishers. Printed in the Netherlands.
233
Experimental Reaction–Diffusion Chemical Processors for Robot Path Planning ANDREW ADAMATZKY1, BENJAMIN DE LACY COSTELLO2, CHRIS MELHUISH1 and NORMAN RATCLIFFE2
1 Faculty of Computing, Engineering and Mathematical Sciences, University of the West of England, Bristol BS16 1QY, UK; e-mail: {andrew.adamatzky,chris.melhuish}@uwe.ac.uk 2 Faculty of Applied Sciences, University of the West of England, Bristol BS16 1QY, UK; e-mail: {ben.delacycostello,norman.ratcliffe}@uwe.ac.uk
(Received: 14 August 2002; in final form: 17 December 2002) Abstract. In this paper we discuss the experimental implementation of a chemical reaction–diffusion processor for robot motion planning in terms of finding the shortest collision-free path for a robot moving in an arena with obstacles. These reaction–diffusion chemical processors for robot navigation are not designed to compete with existing silicon-based controllers. These controllers are intended for the incorporation into future generations of soft-bodied robots built of electro- and chemo-active polymers. In this paper we consider the notion of processing as being implicit in the physical medium constituting the body of a ‘soft’ robot. This work therefore represents some early steps in the employment of excitable media controllers. An image of the arena in which the robot is to navigate is mapped onto a thin-layer chemical medium using a method that allows obstacles to be represented as local changes in the reactant concentrations. Disturbances created by the ‘objects’ generate diffusive and phase wave fronts. The spreading waves approximate to a repulsive field generated by the obstacles. This repulsive field is then inputted into a discrete model of an excitable reaction–diffusion medium, which computes a tree of shortest paths leading to a selected destination point. Two types of chemical processors are discussed: a disposable palladium processor, which executes arena mapping from a configuration of obstacles, given before an experiment and, a reusable Belousov–Zhabotinsky processor which allows for online path planning and adaptation for dynamically changing configurations of obstacles. Key words: unconventional robotics, reaction–diffusion, wave-based processors, excitable media, shortest path computation
1. Introduction This paper deals with unconventional non-silicon controllers – chemical processors that work on the principles of wave-based information processing for the navigation of mobile robots. Chemical controllers discussed in the paper have a limited practical value if considered in the context of conventional silicon robotics because these controllers are intended for future generations of soft-bodied robots built of electro- and chemo-active polymers. In the present paper we tackle processing as implicit in a soft-bodied robot (we do, however, test the idea with chemical
234
A. ADAMATZKY ET AL.
controllers on conventional wheeled robots), whose possible implementations of actuators and sensors are detailed in (Bar-Cohen, 2001). Reaction–diffusion chemical media and excitable media are now typical examples of non-standard computing devices (Adamatzky, 2001). In these nonlinear media, data are represented by a spatial configuration of local perturbations (e.g., pointwise excitations or changes in reactant concentrations) and the computation is executed via the spreading and interaction of diffusive and phase waves. The results of the computation are represented by the spatial concentration profiles in reaction–diffusion chemical media and by excitation patterns in excitable media. Our previous computational and laboratory experiments demonstrated that it is possible to execute effective reactions of a robot, e.g., kinesis and taxis, with excitable chemical media based controllers (Adamatzky and Melhuish, 2001a, 2001b; Adamatzky et al., 2002a, 2002b). In our present work we aimed to obtain a ‘proofof-concept’ by employing two distinct experimental reaction–diffusion chemical controllers in the task of robot motion planning. The collision-free path planning problem – given an experimental arena with obstacles, calculate a shortest path between two selected sites in such a manner that when travelling along the path a robot does not collide with any obstacles – is one of the basic issues in computational robotics and is particulary important for autonomous robots (Takahashi and Schilling, 1989; Hwang and Ahuja, 1992; Tzafestas and Tzafestas, 1999; Murphy, 2000). To solve the problem one must: (i) select a connected subset of farthest from obstacles planar sites, i.e. to approximate a planar Voronoi diagram, and then (ii) calculate the shortest path along the selected subset of planar points. These two steps of optimal path calculation can be implemented in ‘one go’ when the paradigm of artificial potential fields is employed. In this model obstacles generate repulsive fields while a destination point generates an attractive field. A robot starts at a given site within the space and moves, guided by attractive and repulsive field gradients, until it reaches the destination point. A field approach to a shortest path computation has been used since the early 19th century; for example, by employing a graph of a resistance network and then applying a voltage to the graph, then measuring the resistance or capacitance of the network. However, the main ideas on field-based computing were introduced in an algorithmic form just recently in (Vergis et al., 1986) and then were implemented in cellular-automaton models of reaction–diffusion and excitable media (Adamatzky, 1996a, 1996b). In order to calculate the shortest path (without taking the distance from obstacles into consideration) it is sufficient to represent the robot as a positive charge and the destination site as a negative charge. A potential field is then generated at the destination site and this spreads throughout the space whilst remaining at zero at the sites of the obstacles. An optimal path is computed by evaluating the potentials at the sites of the robots-route. This technique has been used, with some modifications, in (Fourie, 2000), and has also been employed in (Hou and
EXPERIMENTAL REACTION–DIFFUSION CHEMICAL PROCESSORS
235
Zheng, 1994; Hussien and McLaren, 1993). Other examples of successful implementations of the potential field technique include the simulation of a potential field with virtual charges (Serradilla and Maravall, 1996), integration of potential field using simulated annealing techniques (Park et al., 2001), evolving artificial potential fields (Vadakkepat et al., 2000), modifications of potential functions (Ge and Cui, 2000), and numerical construction of a potential field as an array of discrete distance values (Barraquand et al., 1992). The potential field approach is also useful to massively parallel VLSI implementation of robot path-planning, where space with obstacles is mapped onto a grid of resistors (Marshall and Tarassenko, 1994; Stan et al., 1994). The analogy of the potential field was also employed in several ‘physics-based’ techniques. Thus, Wang and Chirikjian imitate an artificial potential field as heat transfer, where a distance function is represented by variable thermal conductivity and an optimal path is computed as a flow through minimal resistances (Wang and Chirikjian, 2000). In (Schmidt and Azarm, 1993) the optimal obstacle-free path is dynamically generated via simulation of a diffusion process, and a robot finds a destination site by comparing concentration gradients. It is also possible to represent a destination site as a source of a fluid; if the fluid is viscous then friction coefficients are proportional to the distance from obstacles (Louste and Liegeois, 2000). The optimal path can also be calculated from velocity potentials (Li and Bui, 1998). The approach presented in this work implicitly employs the potential field paradigm (one field is produced by an experimental reaction–diffusion processor, another is then computed using a cellular-automaton model): a repulsive field is generated in thin-layer chemical processors and an attractive field is developed during the space-time excitation dynamic of a discrete nonlinear medium linked to the chemical processors. In this approach we envisage that the navigating robot is supplied with an aerial image. In the field this could be from a satellite, expendable balloon drone, flyby aircraft or even from the distributed sensing of a group of robots. Once the data is received the excitable media computation is rapidly effected. One of the chemical processors discussed in the paper is capable of dynamically updating the obstacle configuration. We have tested these reaction–diffusion processors in 2D space. However, our technique could be applied to the more complex problem of 3D space provided modifications of the experimental conditions of the chemical medium were implemented, see, e.g., (Cross et al., 1997; Stock and Müller, 1996). This paper is structured as follows. The problem of constructing an optimal path in an experimental robotic arena with obstacles is defined and the solution of the problem is outlined in Section 2 in which we also informally discuss our approach step by step. Then we show how to compute obstacle-generated repulsive fields in experimental reaction–diffusion systems including the gel-mediated reaction of palladium chloride and potassium iodide (Section 3) and a thin layer Belousov– Zhabotinsky reaction (B–Z) (Section 4). The computed fields are used as inputs
236
A. ADAMATZKY ET AL.
to a discrete model of an excitable medium that then computes a tree of shortest paths to a selected destination; this is studied in Section 5. The advantages and drawbacks of our present reaction–diffusion approach are discussed in Section 6.
2. The Problem and Its Solution The collision-free path-planning problem addressed in this paper can be considered to be finding the shortest path between two marked sites on a plane in the presence of obstacles. In the design of reaction–diffusion processors we assume that a robot has a single body. The map may be stationary and be known a priori (the case for the palladium processor, Section 3) or dynamic and changing online (the case for the Belousov–Zhabotinsky processor, Section 4). An image of the robot arena is projected onto a reaction–diffusion chemical medium, and the centres or corner points of obstacles are represented by local disturbances of reactant concentrations in the medium. These perturbations generate diffusive gradients and diffusive wave fronts, in the palladium based chemical processor, or as phase excitation waves, in a Belousov–Zhabotinsky chemical processor. The spreading waves build a repulsive field derived from the obstacles. This repulsive field created by the ‘chemical’ waves is then used by a cellular-automaton model of an excitable medium to construct a tree, rooted in a selected destination site, of all shortest paths from the arena’s sites to the destination site. In the next two sections we describe how we addressed the problem using the two chemical implementations discussed above.
3. Computing a Repulsive Field in the Palladium Chemical Processor A distance field around obstacles has been approximated in a palladium processor – a reaction–diffusion chemical processor based on the reaction of palladium chloride gels with potassium iodide – originally discussed in (Tolmachev and Adamatzky, 1996; Adamatzky and Tolmachev, 1997; Adamatzky et al., 2002a, 2002b; de Lacy Costello and Adamatzky, 2003). A gel of agar (2% by weight) containing palladium chloride (in the range 0.2%–0.9% by weight, the lower range is better), was prepared by mixing the solids in de-ionised water (40◦ C). The mixture was heated with a naked flame with constant stirring until it boiled to ensure full dissolution of palladium chloride and production of a uniform gel on cooling. The boiling liquid was then transferred to Petri dishes or alternatively spread on acetate sheets to a thickness of 1–2 mm and left to set. In this application the use of Petri dishes was favoured since the reaction process is relatively slow and drying of the gel can occur if kept open to the atmosphere. The unreacted gel processors were then kept for 30 min; they remained stable for in excess of 24 hours provided drying was controlled. Agar select Sigma-Aldrich Company Ltd. Poole, Dorset, BH12 4XA. Palladium (II) chloride 99% Sigma Aldrich Company Ltd.
EXPERIMENTAL REACTION–DIFFUSION CHEMICAL PROCESSORS
237
(a)
(b) Figure 1. Photographs of the experimental robotic arena (approximately 9 m in diameter) show configurations of circular (a) and rectangular (b) obstacles.
Photographs of the experimental area (Figure 1) were scaled down to the size of a Petri dish (9 cm diameter) and were used as templates to prepare models of the obstacles (Figure 2) from filter paper (any other absorbent material can be used). The filter paper models of obstacles were soaked with a solution of potassium iodide (saturated at 20◦ C), blotted with additional filter paper to remove excess potassium iodide and placed onto the surface of the gel. Experimental arena is circa 9 m in diameter, a camera was positioned 6 m above the centre of the arena. ACS reagent grade, Sigma Aldrich Chemical Company Ltd.
238
A. ADAMATZKY ET AL.
Figure 2. Models of circular (a) and (b) rectangular obstacles, shown in Figure 1, prepared from a filter paper to use in reaction–diffusion chemical processors. The models are precisely scaled down configurations of obstacles in the real robotics arena (scale 1 m : 1 cm approximately).
The clear solution of potassium iodide diffuses from the edges of the ‘obstacles’ into the palladium chloride loaded gel where it reacts to form iodo-palladium species. During the development of the palladium processor colour transitions from yellow (palladium chloride gel) to a dark brown are observed, depending on the presence of certain iodo-palladium species in the gel. At sites where two or more diffusive fronts meet each other almost no precipitate is formed, these sites therefore remain uncoloured; thus uncoloured sites of the gel represent bisectors of a Voronoi diagram, generated by the obstacles. Possible physico-chemical mechanisms of bisector formation are discussed in (Tolmachev and Adamatzky, 1996; Adamatzky and Tolmachev, 1997; Adamatzky et al., 2002; de Lacy Costello and Adamatzky, 2003). Uncoloured or significantly less coloured sites of the gel represent a subset of planar points which are as far from the obstacles as possible – therefore, they indicate all available routes around the obstacles (Figure 3). Then we project the resultant configuration of the palladium processor back onto the arena and the problem of collision-free motion is then solved: a robot moves along lightest parts of the experimental arena. In further sections we represent a grey-level image of a palladium processor in a matrix RP , the greater the value of a cell of RP , the further away from an obstacle it is. 4. Computing a Repulsive Field in the Belousov–Zhabotinsky Chemical Processor We prepared a thin layer implementation of the Belousov–Zhabotinsky (B–Z) reaction using a recipe adapted from (Field and Winfree, 1979): an acidic bromate stock solution incorporating potassium bromate and sulphuric acid ([BrO− 3] = 0.5 M and [H+] = 0.59 M) (solution A); solution of malonic acid (solution B)
EXPERIMENTAL REACTION–DIFFUSION CHEMICAL PROCESSORS
(a)
239
(b)
Figure 3. Photographs of the palladium processor, the processor started its development with a configuration of (a) circular and (b) rectangular obstacles. Uncoloured sites of the processor represent all collision-free routes in the experimental arena.
([CH2 (CO2 H)2 ] = 0.5 M), and sodium bromide (solution C) ([Br− ] = 0.97 M). Ferroin (1,10-phenanthroline iron-II sulphate, 0.025 M) was used as a catalyst and visual indicator of the excitation activity in the BZ medium. To prepare a thin layer of the BZ medium we mixed solutions A (7 ml), B (3.5 ml), C (1.2 ml) and finally when the solution had become colourless ferroin (1 ml) was added and the mixture was transferred to a Petri dish (layer thickness 1 mm). Excitation waves in the B–Z reaction were initiated using silver wires – the addition of silver at specific sites reversibly removes bromide ions from the site, bromide ions act as the main inhibitor of the auto-catalytic reaction in the B–Z reaction and therefore the local removal of the ions triggers wave generation at a specific site. To map the ‘obstacle model’ (Figures 1 and 2) onto the BZ layer we represent centres of the circular obstacles and corner points of rectangular obstacles by thin silver wires; the wires are parallel to each other and perpendicular to the surface of the BZ medium. To start the evolution of the B–Z processor we briefly immersed the tips of all wires into the B–Z mixture. Single circular excitation waves were generated at all sites of the BZ medium which were contacted by the silver wires, these wave-fronts then travelled throughout the medium, where the waves collide with each other they are annihilated thus eventually resetting the medium (Figure 4). The chemical medium is assumed uniform and homogeneous, therefore all wave-fronts travel the same distance in a fixed period of time. When two or more wave fronts meet they annihilate, therefore, every site of the chemical medium can be ‘covered’ by a wave-front originating from only one site within the medium. Figuratively, excitation wave-fronts can be ‘used by obstacles’ to subdivide the space into cells, where every site inside a cell, generated by a specific obstacle, is closer to the obstacle than to any other obstacle. Every site is covered by a
240
A. ADAMATZKY ET AL.
Figure 4. Photographs of BZ-medium, which was excited by a template of silver wires, corresponding to geometry and configuration of rectangular obstacles, shown in Figures 1(a) and 2(a). Contours of excitation-wave fronts super-imposed over the medium’s development time are shown in the right bottom image.
wave front only once because in our experiment, initiation of excitation waves by use of a silver wire gave only one circular wave. Wave-fronts recorded at time t of the BZ medium’s development represent all the points in the medium that lie at a distance tv from the centres of the obstacles, where v is the wave speed (circa 0.1 mm/sec.).
EXPERIMENTAL REACTION–DIFFUSION CHEMICAL PROCESSORS
241
To build a distance field for a given configuration of obstacle, we project the obstacles onto the BZ-medium and extract the positions of the wave-fronts at regular intervals – a matrix of time-lapsed positions of the wave-fronts represents a discrete distance field. Thus 8-bit RGB colour images S = (S 1 , . . . , S m ) of BZ-medium were taken at 15 sec. intervals (see several snapshots in Figure 4). A series S of the images was transformed to a grey-level matrix R = (rx )x∈Z2 using the following rule R=
m
R t −1 ◦ S t ,
t =1
where R 0 = 0, and rxt
=
rxt −1
∗
sxt
=
t, sxt −1 ,
if (sxt −1 = 0) and (B(sxt ) > β), otherwise.
B(sxt ) is a blue component of an RGB colour of the pixel x of snapshot of BZmedium taken at time step t. We considered only the blue component of the colour images because only this component unambiguously represents the position of a wave-front at any given time in the reactions evolution. The value of β may vary from 0 to 50 depending on light intensity during experiments; β = 40 was used in the experiment discussed in the present paper. The matrix RBZ computed from S in two experiments, for circular and rectangular obstacles, is shown in Figure 5. The matrix RBZ represents a distance scalar field derived from a configuration of obstacles, the greater the value of a cell in RBZ the further away it is from the closest obstacle.
Figure 5. Distance matrix R computed from snapshots of BZ-medium ‘excited’ by circular (a) and rectangular (b) obstacles. Values of R are shown by inversed grey-level pixels.
242
A. ADAMATZKY ET AL.
5. Computing a Tree of Shortest Paths from the Fields Computed in the Chemical Processors As we have shown in previous sections, reaction–diffusion chemical processors compute the distance matrix R, R = RP or R = RBZ . This matrix represents a set of all possible obstacle-free routes in an experimental arena, and thus can be used as an internal representation of a robot environment. To navigate between two selected sites of an arena the robot must compute a shortest path from the source to a destination site – the matrix R is used as a basic data-structure in the computation of the shortest path. We have designed a model of a discrete excitable media to assist reaction– diffusion (non) excitable chemical processors in the computation of the shortest path. An excitation wave in a uniform medium travels along the shortest path, therefore to compute the shortest path we excite the source-site, observe how excitation waves spread in the space and record local ‘histories’ of the travelling wave-fronts. The computation is finished when the excitation front reaches a destination-site. Then the shortest path is extracted from the ‘histories’ of the spreading excitations. In principle, this technique can be implemented directly in an excitable chemical medium, e.g., in the BZ-reaction, as demonstrated in (Steinbock et al., 1995; Agladze et al., 1997) and independently discovered in cellular-automaton models of excitation in (Adamatzky, 1996a, 1966b), however in this paper we will stick to a discrete model to specify certain particular details of the computation. To simulate excitation wave dynamics we employed a two-dimensional cellular automaton (CA) – an array of finite automata, called cells, which take finite numbers of states, and update their states in parallel and in discrete time, each cell calculates its next state depending on the states of its eight closest neighbours (Adamatzky, 1996a, 1966b). To record the ‘histories’ of the excitation ‘trajectories’ we supplied each cell of the automaton with a pointer, which points to the cell’s neighbour which excited this cell. The shortest path is extracted then from a configuration of pointers, obtained after running an excitation from a source-cell to a destination-cell. Every cell x of CA updates its state in discrete time t depending on the states of its eight closest neighbouring cells, defined by a rectangular 3 × 3 cell template u(x). At time step t cell x takes a compound state x t , pxt , rx , where x t ∈ {·, +, −} and pxt ∈ (zi , zj ) | zi , zj ∈ {−1, 0, 1} ∪ λ, 0 rx 255. The component x t simulates a ‘physical’ state of the cell x and takes resting (·), excited (+) and refractory (−) states. A resting cell x is excited if at least one of its neighbours is excited and a value rx of the corresponding cell of the matrix R exceeds certain threshold θ. The cell x changes its state from excited to refractory and from refractory to resting unconditionally, i.e. independently of the states of its neighbouring cells.
EXPERIMENTAL REACTION–DIFFUSION CHEMICAL PROCESSORS
243
The component pxt is a state of a pointer, which can be seen as an arrow centered at x and looking toward one of eight neighbours of x or nowhere (pxt = λ); i.e., ‘disconnected’. A pointer pxt at a cell x points to the closest neighbour y of the cell x whose corresponding value ry (of the matrix R) is maximal over the matrix R values of the cell x’s other neighbours which are excited at time t. So far cell state transition rules look as follows:
t t {y = +} > 0 and (rx θ), +, (x = ·) and y∈u(x) x t +1 = t −, x = +, ·, otherwise. t −1 = +) and (x t = +) and y: (y ∈ u(x)) and (y
pxt = ry = min{rz | (z ∈ u(x) and (zt −1 = +)} , t px = pxt −1 , otherwise. The condition rx θ, which is undoubtedly optional, restricts a set of excitable cells from the whole CA lattice to a sublattice G = {x | rx θ}, this does not decrease the time spent on the shortest path computation however it reduces the number of cells excited at each time step. Let at the beginning of the computation only one cell z of G be excited, all other cells be resting and all pointers take state λ; then at moment n t n2 configuration of pointers of CA represents a minimum spanning tree T rooted at the cell x. An excitation wave front, originated in the cell z, passes over all sites of G, and updates states of their pointers (Figure 6). A pointer at a cell can look toward only one neighbour, so a directed graph T is acyclic. The domain G is assumed connected. So, the graph T is a spanning tree. All cells update their states in parallel and using the same rules, thus excitation front gets to a cell x along a shortest path. Therefore, T is a minimum spanning tree. The tree T represents a shortest path around the obstacles (at a maximum distance from any obstacle) from any site of G toward the destination site z. The tree T is rooted at z therefore starting at any site of x, x ∈ G, and moving along the directed edges of T a robot will inevitably reach the site z. The path is shortest because it is a chain of T . The condition ry = min{rz | (z ∈ u(x) and (zt −1 = +)} guarantees that the computed path travels along sites with minimal values R cells and thus each site of the path lies at a maximum distance from the obstacles (Figure 7). To execute real-time navigation a list of vector representations of the computed shortest path is loaded to a memory of the robot’s onboard controller. The robot then implements rotations and forward motions determined by the list of vectors.
244
A. ADAMATZKY ET AL.
Figure 6. Configurations of spanning trees T of pointers computed in CA models of excitable medium from distance field matrices RP , circular obstacles (a) and rectangular obstacles (b), and RBZ , circular obstacles (c). Destination (upper part) and source (lower part) sites of arena are indicated by arrows.
6. Discussion We showed how to approximate sets of collision-free routes in experimental chemical thin-layer reactors – the palladium processor and the Belousov–Zhabotinsky processor. These chemical processors ‘label’ sites of an experimental arena, which are most distant from obstacles, whereby a robot minimises a risk of collision with obstacles if it travels along these ‘labelled’ routes. The palladium processor does not require any supporting computing devices to approximate a set of collision-free routes: this set is represented by sites of the medium without precipitate and thus uncoloured. This is its great advantage.
EXPERIMENTAL REACTION–DIFFUSION CHEMICAL PROCESSORS
245
Figure 7. Shortest paths mapped onto the robotic arena with obstacles. The path is computed from the experimental thin-layer chemical medium – palladium processor, circular obstacles (a) and rectangular obstacles (b), and the Belousov–Zhabotinsky processor, circular obstacles (c) – assisted with two-dimensional cellular automaton models of excitable medium.
The main disadvantage of the palladium processor is that the initial state is not restorable and thus we could hardly implement the dynamical configuration of obstacles represented in reagent concentrations in the processor. No obstacle can be added online in the palladium processor. So, we classify it as a disposable robotic controller. This is a limitation. However, in contrast, the Belousov–Zhabotinsky processor is a reusable one, because when all excitation fronts, generated by obstacles, collide and annihilate the whole medium returns to its resting state and
246
A. ADAMATZKY ET AL.
it can be re-excited. In the Belousov–Zhabotinsky processor we can recalculate the shortest paths for dynamically changing configurations of obstacles. Also we can add/delete obstacles online. Thus obstacle avoidance is implementable in the chemical reaction–diffusion processor. However, there are no stationary structures – which may represent the processor’s memory as precipitate concentration profiles do in the palladium processor – in the Belousov–Zhabotinsky medium, therefore the medium needs an assistance of an external computing device to store results of the computation. To find all collision-free routes was the first step of the reaction–diffusion path planning. The second step is to calculate a shortest collision-free path between two given sites of the experimental arena. In present paper we implemented this step using a cellular-automaton model of an excitable (reaction–diffusion) medium. Luckily, this discrete excitable medium calculates not just a single path but a ‘onedestination-many-sources’ spanning tree of all shortest free paths from every site of an obstacle-free subspace of the arena to one selected site. A robot gets immediate benefits even at the first step of the reaction–diffusion computing to avoid collision with obstacle it must stick to less coloured sites of the palladium processor and must not intersect steep parts (which indicate a head of excitation pulse) of excitation-wave fronts in the Belousov–Zhabotinsky processor. There are many limitations of the present realisations of thin-layer chemical controllers, which we are planning to overcome in future experiments: 1. Sites within the chemical processors, corresponding to obstacles in the robotic arena, are perturbed by mechanical application of reagents. Optical excitation is desirable and this will be studied in our forthcoming experiments. 2. In the present experimental setup neither the reaction–diffusion chemical controllers nor the robot interact with their environments in real time. It is possible to assemble several chemical processors onboard the robot and assign different tasks, e.g., taxis, obstacle avoidance, interaction with other robots, to different processors and correspondingly interpret space-time phenomena of wave dynamics. 3. Diffusion wave-fronts in the palladium processor and excitation wave-fronts in the Belousov–Zhabotinsky processor travel very slowly and this is the limiting factor for the robots velocity. Therefore real time experiments of obstacle avoidance are only feasible if the robot travels slowly. However, as the processor directly equates to a scaled down version of the robots actual environment the robots average velocity can be many times that of the reactions wave speed. In this class of processor the more obstacles that are present the faster the processor will compute the shortest path and thus the higher the average velocity of the robot. To increase the speed of the reaction–diffusion processing (and thus the robot velocity) one can either scale down the chemical processor, employ other types of faster wave based media, find alternative more rapid methods of interrogating the processors, or alter the reaction conditions e.g. temperature. In addition we
EXPERIMENTAL REACTION–DIFFUSION CHEMICAL PROCESSORS
247
are currently studying a class of chemical processors which operate at the edge of a highly nonlinear region (de Lacy Costello and Adamatzky, 2002) – the advantages of these processors over the conventional chemical processor described would be increased processing speed and operation on a microscopic scale. Further work to address the issues of robot navigation in three dimensions will be undertaken. Currently the only way of implementing this would be to have multiple layered processors where each individual processor corresponds to a height level within the robots environment. As these layers are not directly connected the pre-processing and analysis stages in order to map and analyse the various computed paths would be a massive task. A method of implementing the processors in a single representative three-dimensional media plus a method of accurately interrogating the reactions to represent three-dimensional objects is actively being pursued. The reaction–diffusion chemical processors for robot navigation are not designed to compete with existing silicon-based controllers. They are fabricated for incorporation in future designs of soft-bodied robots built of chemo- and electro-active polymers. Obviously, it may be more efficient to implement the reaction–diffusion processor in silicon based devices, there is already significant evidence of the viability of this approach (Binczak et al., 1998; Branciforte et al., 1999; Arena et al., 2000; Bonaiuto et al., 2001). The silicon implementation would not, of course, work in non-silicon robotic architectures. This class of reaction–diffusion chemical processors is the only type which is pragmatically feasible for integration into the architecture of non-silicon robots (Kennedy et al., 2001), particularly robotic arrays of actuators synthesised from oscillating pH-sensitive gels (Tabata et al., 2002). Acknowledgements We acknowledge support of the EPSRC (grant GR/R31225/01). Thanks to Chris Bytheway and Jason Welsby (UWE, Bristol) for preparing the experimental arena. References Adamatzky, A.: 1994, Reaction–diffusion algorithm for constructing discrete generalized Voronoi diagram, Neural Networks World 3, 241–254. Adamatzky, A.: 1996a, Voronoi-like lattice partition of lattice in cellular automata, Math. Comput. Modelling 23, 51–66. Adamatzky, A.: 1996b, Computation of shortest path in cellular automata, Math. Comput. Modelling 23, 105–113. Adamatzky, A.: 2001, Computing in Nonlinear Media and Automata Collectives, Institute of Physics Publishing. Adamatzky, A. and Melhuish, C.: 2001a, Phototaxis of mobile excitable lattices, Chaos Solitons Fractals 13, 171–184. Adamatzky, A. and Melhuish, C.: 2001b, Towards the design of excitable lattice controllers for (nano)robots, Smart Engrg. Systems Design 3, 265–277.
248
A. ADAMATZKY ET AL.
Adamatzky, A. and Tolmachiev, D.: 1997, Chemical processor for computation of skeleton of planara shape, Adv. Mater. Optics Electr. 7, 135–139. Adamatzky, A., De Lacy Costello, B., and Ratcliffe, N. M.: 2002a, Experimental reaction–diffusion pre-processor for shape recognition, Phys. Lett. A 297, 344–352. Adamatzky, A., De Lacy Costello, B., Melhuish, C., Rambidi, N., Ratcliffe, N., and Wessnitzer, J.: 2002b, Excitable chemical controllers for robots, in: Proc. EPSRC/BBSRC Int. Workshop Biologically-Inspired Robotics: The Legacy of W. Grey Walter, 14–16 August 2002, Bristol, UK. Agladze, K., Magome, N., Aliev, R., Yamaguchi, T., and Yoshikawa, K.: 1997, Finding the optimal path with the aid of chemical wave, Phys. D 106, 247–254. Arena, P., Branciforte, M., Di Bernardo, G., Lavorgna, M., and Occhipinti, L.: 2000, Reaction– diffusion CNN chip, in: Proc. of the 2000 IEEE Internat. Sympos. on Circuits and Systems, IEEE, Vol. 3, pp. 419–422, 427–430. Bar-Cohen, Y. (ed.): 2001, Electroactive Polymer (EAP) Actuators as Artificial Muscles, SPIE Press. Barraquand, J., Langlois, B., and Latombe, J. C.: 1992, Numerical potential field techniques for robot path planning, IEEE Trans. Systems Man Cybernet. 22, 224–241. Binczak, S., Comte, J. C., Michaux, B., Marquie, P., and Bilbault, J. M.: 1998, Experimental nonlinear electrical reaction diffusion lattice, Electron. Lett. 34, 1061–1062. Bonaiuto, V., Maffucci, A., Miano, G., Salerno, M., Sargeni, F., Serra, P., and Visone, C.: 2001, Hardware implementation of a CNN for analog simulation of reaction–diffusion equations, in: ISCAS 2001, Proc. of the 2001 IEEE Internat. Sympos. on Circuits and Systems, IEEE, Vol. 2, pp. 485–488. Branciforte, M., Di Bernardo, G., Doddo, F., and Occhipinti, L.: 1999, Reaction–diffusion CNN design for a new class of biologically-inspired processors in artificial locomotion applications, in: Proc. of 17th Internat. Conf. on Microelectronics for Neural, Fuzzy and Bio-Inspired Systems, IEEE, pp. 69–76. Cross, A. L., Armstrong, R. L., Gobrecht, C., Paton, M., and Ware, C.: 1997, Three-dimensional imaging of the Belousov–Zhabotinsky reaction using magnetic resonance, Magnetic Resonance Imaging 15, 719–725. De Lacy Costello, B. P. J. and Adamatzky, A. I.: 2002, unpublished data. De Lacy Costello, B. P. J. and Adamatzky, A. I.: 2003, On multi-tasking in parallel chemical processors: Experimental findings, Internat. J. Bifurcation Chaos 13, in press. Fourie, C. J.: 2000, Intelligent path planning for a mobile robot using a potential field algorithm, in: Proc. of the 29th Internat. Sympos. on Robotics, Advanced Robotics, Beyond 2000, DMG Business Media, Redhill, UK, 1998, pp. 221–224. Ge, S. S. and Cui, Y. J.: 2000, New potential functions for mobile robot path planning, IEEE Trans. Robotics Automat. 16, 615–620. Hou, E. S. H. and Zheng, D.: 1994, Mobile robot path planning based on hierarchical hexagonal decomposition and artificial potential fields, J. Robotic Systems 11, 605–614. Hussien, B. and McLaren, R. W.: 1993, Real-time robot path planning using the potential function method, Automation Construct. 2, 241–250. Hwang, Y. K. and Ahuja, N.: 1992, Gross motion planning – A survey, ACM Computing Surveys 2, 219–291. Kennedy, B., Melhuish, C., and Adamatzky, A.: 2001, Biologically inspired robots, in: Y. Bar-Cohen (ed.), Electroactive Polymer (EAP) Actuators as Artificial Muscles, SPIE Press. Li, Z. X. and Bui, T. D.: 1998, Robot path planning using fluid model, J. Intelligent Robotic Systems 21, 29–50. Louste, C. and Liegeois, A.: 2000, Near optimal robust path planning for mobile robots: the viscous fluid method with friction, J. Intelligent Robotic Systems 27, 99–112. Marshall, G. F. and Tarassenko, L.: 1994, Robot path planning using VLSI resistive grids, IEE Proc. Vision Image Signal Process. 141, 267–272. Murphy, R.: 2000, An Introduction to AI Robotics, MIT Press.
EXPERIMENTAL REACTION–DIFFUSION CHEMICAL PROCESSORS
249
Park, M. G., Jeon, K. H., and Lee, M. C.: 2001, Obstacle avoidance for mobile robots using artificial potential field approach with simulated annealing, in: Proc. of 2001 IEEE Internat. Sympos. on Industrial Electronics, IEEE, Piscataway, NJ, USA, Vol. 3, pp. 1530–1535. Schmidt, G. K. and Azarm, K.: 1993, Mobile robot path planning and execution based on a diffusion equation strategy, Adv. in Robotics 7, 479–490. Serradilla, F. and Maravall, D.: 1996, A navigation system for mobile robots using visual feedback and artificial potential fields, in: Cybernetics and Systems ’96, Proc. of 13th European Meeting on Cybernetics and Systems Research, Austrian Soc. Cybernetic Studies, Vienna, Vol. 2, pp. 1159– 1164. Stan, M. R., Burleson, W. P., Connolly, C. I., and Grupen, R. A.: 1994, Analog VLSI for robot path planning, J. VLSI Signal Processing 8, 61–73. Steinbock, O., Tóth, A. and Showalter, K.: 1995, Navigating complex labyrinths: Optimal paths from chemical waves, Science 267, 868–871. Stock, D. and Müller, S. C.: 1996, Three-dimensional reconstruction of scroll waves in the Belousov– Zhabotinsky reaction using optical tomography, Phys. D 96, 396–403. Tabata, O., Hirasawa, H., Aoki, S., Yoshida, R., and Kokufuta, E.: 2002, Ciliary motion actuator using self-oscillating gel, Sensors Actuators A 95, 234–238. Takahashi, O. and Schilling, R. J.: 1989, Motion planning in a plane using generalized Voronoi diagram, IEEE Trans. Robotics Automat. 5, 143–150. Tolmachev, D. and Adamatzky, A.: 1996, Chemical processor for computation of Voronoi diagram, Adv. in Mater. Opt. Electron. 6, 191–196. Tzafestas, C. S. and Tzafestas, S. G.: 1999, Recent algorithms for fuzzy and neurofuzzy path planning and navigation of autonomous mobile robots, Systems Sci. 25, 25–39. Vadakkepat, P., Tan, K. C., and Liang, W. M.: 2000, Evolutionary artificial potential fields and their application in real time robot path planning, in: Proc. of 2000 Congress. on Evolutionary Computation. CEC00, IEEE, Piscataway, NJ, Vol. 1, pp. 256–263. Vergis, A., Steiglitz, K., and Dickinson, B.: 1986, The complexity of analog computation, Math. Comput. Simulation 28, 91–113. Wang, Y. F. and Chirikjian, G. S.: 2000, A new potential field method for robot path planning, in: Proc. IEEE Internat. Robotics and Automation Conference, San Francisco, CA, IEEE, Piscataway, NJ, pp. 977–982.
