Reaction-diffusion path planning in a hybrid chemical and cellular-automaton processor

To find the shortest collision-free path in a room containing obstacles we designed a chemical processor and coupled it with a cellular-automaton processor. In the chemical processor obstacles are represented by sites of high concentration of potassium iodide and a planar substrate is saturated with palladium chloride. Potassium iodide diffuses into the substrate and reacts with palladium chloride. A dark coloured precipitate of palladium iodide is formed almost every-where except sites where two or more diffusion wavefronts collide. The less coloured sites are situated at the furthest distance from obstacles. Thus, the chemical processor develops a repulsive field. generated by obstacles. A snapshot of the chemical processor is inputted to a cellular automaton. The automaton behaves like a discrete excitable media; also, every cell of the automaton is supplied with a pointer that shows an origin of the cell's excitation. The excitation spreads along the cells corresponding to precipitate depleted sites of the chemical processor. When the destination-site is excited, waves travel on the lattice and update the orientations of the pointers. Thus, the automaton constructs a spanning tree, made of pointers, that guides a traveler towards the destination point. Thus, the automaton medium generates an attractive field and combination of this attractive field with the repulsive field, generated by the chemical processor, provides us with a solution of the collision-free path problem, (C) 2002 Elsevier Science Ltd. All rights reserved.