Physical maze solvers. All twelve prototypes implement 1961 Lee algorithm. Andrew Adamatzky 6 1 0 2 n Abstract We overview experimental laboratory prototypes of maze solvers. We speculate that all a J maze solvers implement Lee algorithm by first developing a gradient of values showing a distance 8 fromanysiteofthemazetothedestinationsiteandthentracingapathfromagivensourcesiteto 1 the destination site. All prototypes approximate a set of many-source-one-destination paths using resistance, chemical and temporal gradients. They trace a path from a given source site to the ] T destinationsiteusingelectricalcurrent,fluidic,growthofslimemould,Marangoniflow,crawlingof E epithelial cells, excitation waves in chemical medium, propagating crystallisation patterns. Some of . the prototypes visualise the path using a stream of dye, thermal camera or glow discharge; others s c require a computer to extract the path from time lapse images of the tracing. We discuss the [ prototypes in terms of speed, costs and durability of the path visualisation. 1 v 2 7 6 4 0 . 1 0 6 1 : v i X r a AndrewAdamatzky UniversityoftheWestofEngland,Bristol,UKe-mail:[email protected] 1 Contents Physical maze solvers. All twelve prototypes implement 1961 Lee algorithm...... 1 Andrew Adamatzky 1 Introduction............................................................. 3 2 Resistance gradient....................................................... 5 2.1 Electrical current ................................................. 5 fluidic 2.2 : Fluidic................................................. 7 physarum I 2.3 : Slime mould ....................................... 7 3 Diffusion gradient ........................................................ 7 marangoni 3.1 : Marangoni flow..................................... 8 3.2 Living cells....................................................... 8 temperature 4 Temperature gradient: .................................... 9 5 Temporal gradient........................................................ 10 vlsi 5.1 : VLSI array processor ........................................ 10 wave 5.2 : Excitation waves .......................................... 10 crystall 5.3 : Crystallization ....................................... 11 6 Analysis ................................................................ 11 7 Discussion............................................................... 12 References .................................................................... 14 1 Introduction Tosolveamazeistofindaroutefromthesourcesitetothedestinationsite.Ifthereisjustasingle path to the destination the maze is called a labyrinth. To solve a labyrinth one must just avoid dead ends. In a maze there are at least two paths leading from the entrance to the exit. To solve a maze one must find a shortest path. Not rarely concepts of ‘maze’, ‘labyrinth’ and ‘collision-free shortest path’ are mixed in experimental laboratory papers. We will not differentiate either. All algorithms and physical prototypes that solve shortest collision-free path on a planar graph solve mazes [14]. All algorithms and prototypes that solve mazes solve labyrinths. There are two scenarios of the maze problem: the solver does not know the whole structure of the maze and the solver knows the structure of the maze. 3 4 Adamatzky:PhysicalMazeSolvers The first scenario — we are inside the maze – is the original one. This is how Theseus, the Shannon’s maze solving mechanical mouse, was born [48].1 The mouse per se was a magnet with copper whiskers. The mechanism was hidden under the maze. A circuit with hundred of relays and mechanical drives grabbed the mouse from below the floor and moved to a randomly chosen direction.Whenthemousedetectedanobstaclewithitswhiskerstheunderfloormechanismmoved themouseawayfromtheobstacleandotherdirectionofmovementhasbeenselected.Thetaskwas complementedwhenthedestinationsitewasfound.Beingplacedatanysiteofthemazethemouse was able to find a path towards the destination site. Several electro-mechanical devices have been built in 1950-1970, including well know Wallace’s maze solving computer [57]. The Theseus also inspired a range of robotic mice competitions [61]. The algorithms of a maze traversing agent, see overviews in [58, 12] include random walk [10]; the Dead Reckoning (the mouse travels straight, when it encounters a junction it turns randomly, when it finds itself in the dead end it turns around), Dead End Learning (the agent remembers dead ends and places a virtual wall in the corridor leading to each dead end); Flood Fill (the agent assigns a distance, as crow flies, to each siteofthemazeandthentravelinthemazeandupdatesthedistancevalueswithrealisticnumbers); and, Pledge algorithm where the maze traversing agent is equipped with a compass, which allows to maintain a predetermined direction of motion (e.g. always north); the intersections between the corridors oriented north-south and walls are treated as graph vertices [14, 1]. Hybrids of the Wall Follow and the Pledge algorithms are used in industrial robotics and space explorations: a robot knows coordinates of the destination site, has a compass, turns on a fixed angle and counts turns [33, 32].There are also genetic programming and artificial neural networks for maze solving [26]. The second scenario of maze solving — we are above the maze — is the one we study here. In 1961 Lee proposed the algorithm [30, 46] which became one of the most famous, reused and rediscovered algorithms in last century. We start at the destination site. We label neighbours of the site with ‘1’. Then we label their neighbours with ‘2’. Being at the site labelled i we label its non-yet-labelled neighbours with i+1. Sites occupied by obstacles, or the maze walls, are not labelled. When all accessible sites are labelled the exploration task is completed. To extract the path from any given site of the maze to the destination site we start at the source site. Then we selectaneighbourofthesourcesitewithlowestvalueofitslabel.Weaddthisneighbourtothelist. Wejumpatthisneighbour.Thenweselectitsneighbourwithlowestvalueofthelabel.Weaddthis neighbourtothelist.Wejumpatthisneighbour.Wecontinuelikethattillwegetatthedestination site. Thus the algorithm computes one-destination-many-sources shortest path. A set of shortest path starting from each site of the maze gives us a spanning tree which nodes are sites of the maze andarootisthesitewherewavepatternoflabellingstartedtogrow.InroboticstheLeealgorithm was transformed into a potential method pioneered in [38] and further developed in [59, 24]. The destination is assigned an infinite potential. Gradient is calculated locally. Streamlines from the source site to the destination site are calculated locally at each site by selecting locally maximum gradient [16]. Also, some algorithms assume that the destination has an ‘attracting’ potential and obstacles are ‘repellents’ [27, 6, 8]. Most experimental laboratory prototype of maze solvers implement the Lee algorithm. The gradients developed are resistance (Sect. 2), chemical (Sect. 2), temporal (Sect. 2) and thermal (Sect.2).Thepathsaretracedalongthegradientsbyelectricalcurrent(Sect.2.1),fluids(Sect.2.2), cellular cytoplasm (Sect. 2.3), Marangoni flow (Sect. 3.1), living cells (Sect. 3.2), excitation waves 1 Seehttp://cyberneticzoo.com/mazesolvers/ Adamatzky:PhysicalMazeSolvers 5 (Sect. 5.2) and crystallisation (Sect. 5.3). We present brief descriptions of known experimental laboratory prototypes of maze solvers and analyse them comparatively. 2 Resistance gradient Imagine a maze filled with hard balls. The entrance and the exist are open. We put our hand in the entrance and push the balls. Balls in the dead ends have nowhere to move. The pressure is eventually transferred to the balls nearby exit. These balls start falling out. We add more balls thought entrance and push again. Balls fall out through the exit. Thus a movement of balls is established. The balls are moving along the shortest path between the entrance and the exit. The balls explore the maze in parallel and ‘calculate’ the path from the exit to the entrance. In this section we discuss prototypes which employe electrical and hydrodynamic resistances. 2.1 Electrical current Approximation of a collision-free path with a network of resistors is proposed in [52, 53]. A space is discretised as a resistor network. The resistors representing obstacles are insulators or current thinks. Other resistors have the same initial resistance. An electoral power source is connected to thedestinationandthesourcesites.Thedestinationsiteistheelectricalcurrentsource[15].Current flows in the grid. Current does not flow into obstacles. To trace the path one must follow a current streamlinebyperforminggradientdescentinelectricalpotential.Thatisforeachnodeanextmove is selected by measuring the voltage difference between current node and each of its neighbours, and moving to the neighbours which shows maximum voltage. We are not aware of any large-scale prototype of such path solver. Two VLSI processors have been manufactured [49]. They feature 16×16and18×18cells,2µmnwellSCMOStechnology,3960µ×4240‘µand4560µ×4560µframe size, 16-bit asynchronous data bus. For gradient descent the source is 5 V and the destination is 0 V, and vice verse for gradient ascent. Therearetwowaystorepresentwallsofamaze[15]:DirichletboundaryconditionsandNeumann boundary conditions. When the Dirichlet boundary conditions is adopted the walls, or obstacles, have zero electrical potential and act as sinks of the electrical current [16]. Then the current lines are perpendicular to the walls and an agent, e.g. a robot, travelling along the current lines stays awayfromthewalls[15].IncaseoftheNeumannboundaryconditionsthewallsareinsulators[52]. The walls are not ‘felt’ by the electrical current. Then the current lines are parallel to the walls. This gives the travelling agent less clearance. The original approach of [52] has been extended to networks of memristors (resistors with memory) [39], which could allow for computation of a path in directed planar graph. A shortest path can be visualised, though not digitally recorded, without discretisation of the space. A maze is filled with a continuous conductive material. Corridors are conductors, walls are insulators. An electrical potential difference is applied between the source and the destination sites. The electrical current ‘explores’ all possible pathways in the maze. As proposed in [11] the electrons, driven by the applied electrical field, move along the conductive corridors in a maze until they encounter dead end or the destination site. When the electrons reach dead end they are 6 Adamatzky:PhysicalMazeSolvers cancelled inside the conductor. The electric field inside the dead ends becomes zero. The flow of electronsontheconductivepathwaysleadingthedestinationdoesnotstop.Thustheelectricalflow calculates the shortest path. This path is detected via glow-discharge or thermo-visualisation. glow 2.1.1 : Glow-discharge visualisation Thismazesolverisproposedin[43].Adrawingofamazeistransferredonaglasswaferandchannels areetchedintheglass.Thechannelsarec.250µmwideandc.100µmdeep.Electrodesareinserted in the source and the destination sites. The glass maze is covered tightly and filled with helium at 500 Torr. A voltage of up to 30 kV, above the breakdown voltage, is applied. Luminescence of the discharge shows the shortest path in the maze. Shortest path is visualised in 500 ms. A maze solver using much less pressure and much lower voltage is proposed in [17]. The maze is made of a plexiglas disk, diameter 287 mm, 50 mm height. Channels 25 mm wide and 40 mm deep are cut in the disk. Hole for the anode is made in the center of the disk. Cathode is placed in the destination site. The maze is filled with air, pressure 0.110 Torr. A gas-discharge chamber is made of polyamide in 450 mm diameter and 50 mm height, copper cathode in the form of rectangular plate of 158 mm2 size is fitted on its side surface in a cathode holder. The maze is placed in the gas-discharge chamber. Stainless steel rod anode of 10 mm diameter is placed at the center of the chamber. Voltage of 2kV is applied between the electrodes. The path is visualised by the glow of ionisedairinthemaze’schannels.Experiments[17]alsodemonstratepropagationofstriations,the ionisation waves [28], along the path. assembly 2.1.2 : Assembly of nano particles The maze is solved with nano particles in [34]. A maze is made of polydimethylsilicoxane and filled withsiliconoil.Adropofadispersionofconductivenanoparticles:sphericalcoppernanoparticles 10 µm diameter and metallic carbon nanotubes 10 µm long — is added at the source site. An electricalpotential1–5kVisappliedbetweenthesourceandthedestination.Theparticlesdiffusing from the source site become polarised. The polarised particles experience dipole interactions. The dipole interactions make the particles to form a chain along line of the electric field with maximal strength.Thechainisformedtomaximisetheelectricalcurrentandtominimisethepotentialdrop. The chain of the particles forms a conductive bridge between the electrodes at the source site and the destination site which represents the shortest path. thermo 2.1.3 : Thermo-visualisation A maze solver using electrical current is proposed in [11]. The prototype employs thermal visuali- sation of the electrical current. A maze 10×10 cm is made from copper tracks on a printed board. Coppertracksrepresentcorridors.Theelectricalcurrent2.4Aisappliedbetweenthesourceandthe destination sites. The flow of electrons heats the conductor, due to Joule heating. A local temper- ature of the conductor is proportional to intensity of the flow. In experiments [11] the temperature along the shortest path increased by c. 10oC. The heating is visualised with the infrared camera. The shortest path is represented by the brightest loci on the thermographic image. Adamatzky:PhysicalMazeSolvers 7 2.2 fluidic: Fluidic In a fluidic maze solver developed in [18] a maze is the network of micro-channels. The network is sealed. Only the source site (inlet) and the destination site (outlet) are open. The maze is filled with a high-viscosity fluid. A low-viscosity coloured fluid is pumped under pressure into the maze, viatheinlet.Duetoapressuredropbetweentheinletandtheoutletliquidsstartleavingthemaze viatheoutlet.Avelocityoffluidinachannelisinverselyproportionaltothelengthofthechannel. High-viscosity fluid in the channels leading to dead ends prevents the coloured low-viscosity fluid from entering the channels. There is no pressure drop between the inlet and any of the dead ends. Portions of the ‘filler’ liquid leave the maze. They are gradually displaced by the colour liquid. The colour liquid travels along maximum gradient of the pressure drop, which is along a shortest path from the inlet to outlet. When the colour liquid fills in the path the viscosity along the path decreases. This leads to increase of the liquid velocity along the path. The shortest path — least hydrodynamic resistance path — from the inlet to the outlet is represented by channels filled with coloured fluid. In the experiments [18] channel width varied from c. 90 µm to 200 µm, maze size c. 40×50 mm. The maze is filed with ethanol-based solution of bromophenoll. A dark coloured solution of a food dye in mix of water and ethylene glycol is injected in the maze at a constant flow, velocity c 5– 10 mm/sec. A drop of pressure between the inlet and the outlet is c. 0.75-2.25 Torr. The channels along the shortest path become coloured. The path is visualised in half-a-minute. 2.3 physarum I: Slime mould TheprototypebasedonreconfigurationofprotoplasmicnetworkofacellularslimemouldPhysarum polycephalum is proposed in [35]. The slime mould is inoculated everywhere in a maze. The slime mould develops a network of protoplasmic tubes spanning all channels of the maze. Oat flakes are placedinthesourceandthedestinationsite.Atubelyingalongtheshortest(ornearshortest)path betweensiteswithnutrientsdevelopincreasedflowofcytoplasm.Thistubebecomesthicker.Tubes branchingtositeswithoutnutrientsbecomesmallerduetolackofcytoplasmflow.Theyeventually collapse. The sickest tube represents the path between the sources of nutrients, and therefore, the path between the source and the destination sites. The selection of the shortest protoplasmic tube isimplementedviainteractionofpropagatingbio-chemical,electricpotentialandcontractilewaves in the plasmodium’s body, see mathematical model in [54]. 3 Diffusion gradient A source of a diffusing substance is placed at the destination site. After the substance propa- gates all over the maze a concentration of the substance develops. The concentration gradient is steepest towards the source of the diffusion. Thus starting at any site of the maze and following the steepest gradient one can reach the source of the diffusion. The diffusing substance represents one-destination-many-sources shortest paths. To trace a shortest path from any site, we place a chemotactic agent at the site and record its movement towards the destination site. 8 Adamatzky:PhysicalMazeSolvers 3.1 marangoni: Marangoni flow A diffusion gradient determines a surface tension gradient. A flow of liquid runs from the place of low surface tension to the place of high surface tension. This flow transports droplets. A maze solver proposed in [29] is as follows. A maze is made of polydimethylsiloxane, size c. 16 × 16 mm, channels have width 1.4 mm, and walls are 1 mm high. The maze is filled with a solution of potassiumhydroxide.Asurfactantisaddedtoreducetheliquid’ssurfacetension.Anagaroseblock soakedinahydrochloricacidisplacedatthedestinationsite.Inc.40sapHgradientestablishesin themaze.Thena1µLdropletofamineraloilordichloromethanemixedwith2-hexyldecanoicacid is placed at the source site. The droplet does not mix with the liquid filling the maze. The droplet moves along the steepest gradient of the potassium hydroxide. The steepest gradient is along a shortest path. Exact mechanics of the droplet’s motion is explained in [29] as follows. Potassium hydroxide, which fills the maze, is a deprotonating agent. Molecule of the potassium hydroxide removes protons from molecules of 2-hexyldecanoic acid diffusing from the droplet. A degree of protonation is proportional to concentration of hydrochloric acid, diffusing form the destination site. Protonated 2-hexyldecanoic acid at the liquid surface determines the surface tension. The gradient of the protonated acid determines a gradient of the surface tension. The surface tension decreases towards the destination site. A flow of liquid — the Marangoni flow — is established from the site of low surface tension to the site of high surface tension, i.e. from the start to the destination site. The droplet is moved by the flow [29]; see also discussion on mobility of surface in [40] and more details on pH dependent motion of self-propelled droplets in [13]. Intheprototype [29]apathfromthestartsitetothedestinationsiteistracedbyadropletbut notvisualised.Tovisualisethepathfullyonemustrecordatrajectoryofthedroplet.Avisualisation is implemented in [31]. A dye powder, Phenol Rd, is placed at the start site. The Marangoni flow transports the dye form the start to the destination. The coloured channels represent a path connecting the source site and the destination. Another prototype of a droplet maze solver is demonstrated in [56]. The maze c. 45×75 mm in size,withchannelsc.10mmwide,isfilledwithwatersolutionofasodiumdecanoate.Anitrobenzene dropletloadedwithsodiumchloridegrainsisplacedatthedestinationsite.A5muLdecanoldroplet is placed at the source site. The sodium chloride diffuses from its host nitrobenzene droplet at the destination site. A gradient of salt is established. The gradient is steepest along a shortest path leadingfromanysiteofthemazetothedestinationsite.Adecanoldropletmovesalongthesteepest gradient till the droplet reaches the nitrobenzene with salt droplet at the destination site. 3.2 Living cells Asourceofachemo-attractantisplacedatthedestinationsite.Thechemo-attractantdiffusesalong thechannelsofthemaze.Itreachesthedestinationsiteeventually.Themaximumgradientisalong theshortestpathfromanygivensiteofamazetothedestinationsite.Alivingcellisplacedatthe source site. The cell follows the maximum gradients thus moving along the shortest path towards the destination site. Adamatzky:PhysicalMazeSolvers 9 physarum II 3.2.1 : Slime mould Theslimemouldmazesolverbasedonchemo-attractionisproposedin[4].Anoatflakeisplacedin the destination site. The slime mould Physarum polycephalum is inoculated in the source site. The oatflakes,orratherbacteriascolonisingtheflake,releaseachemoattractant.Thechemo-attractant diffuses along the channels. The Physarum explores its vicinity by branching protoplasmic tubes into openings of nearby channels. When a wave-front of diffusing attractants reaches Physarum, the Physarum halts the lateral exploration. Instead it develops an active growing zone propagating along the gradient of the attractant’s diffusion. The problem is solved when Physarum reaches the source site. The sickest tube represents the shortest path between the destination site and the sourcesite.Notonlynutrientscanbeplacedatthedestinationsitebutanyvolatilesubstancesthat attract the slime mould, e.g. roots of the medicinal plant Valeriana officinalis [45]. epithelium 3.2.2 : Epithelial cells Experimentalmazesolverwithepithelialcellsisproposedin[47].Epithelialcellsmovetowardssites with highest concentration of the epidermal growth factor (EGF). An epithelial cell uptakes EGF. Thus the cell depletes EGF’s concentration in the cell’s vicinity. A 400 µm×400 µm maze is made of orthogonal channels c. 10 µm wide [47]. The channels are filled with epithelium culture medium. There is a uniform distribution of the EGF inside the maze at the beginning of an experiment. The maze is placed in the medium with ‘unlimited’ supply of EGF. A cell is placed at the entrance channel. The cell enters the maze and crawls along its first channel. The cell consumes EGF and decreases EGF concentration in its own neighbourhood. EGF from all channels, accessible from the current position of the cell, diffuses towards the site with low concentration. Supply of EFG in channels ending with dead ends is limited. Unlimited supply of EGF into the maze is provided via exit channel. An EGF diffusion gradient from the exit through the maze to dead ends and the entrance is established. The cell follows the diffusion gradient. The gradient is maximum along the shortest path. The cell moves along the shortest path towards the exit. 4 Temperature gradient: temperature A Marangoni flow is a mass-transfer of a liquid from a region with low surface tension to a region with high surface tension [31]. The mass transfer can move droplets, or any other objects, or dyes. Any methods of establishing a surface tension gradient is OK for tracing a shortest path with Marangoni flow. In [31] a temperature gradient is used. A maze is made from polydimethylsiloxane with channels 1.4 mm wide and 1 mm deep. The maze is filled with hot, c. 99oC, aqueous solution ofsodiumhydroxidewithhexyldecanoicacid.Asteelsphere,diameter4mm,iscooledwithdryice and placed at the destination site in the maze. A phenol red dye powder is placed on the surface of theliquidatthestartsite.Thecoldspherecreatestemperaturegradient.Thetemperaturegradient creates a surface tension gradient. The Marangoni flow is established along a shortest path from any site of the maze to the destination site. The dye powder applied at the source site is dragged by the flow towards the destination site. The trace of the dye represents the shortest path. 10 Adamatzky:PhysicalMazeSolvers 5 Temporal gradient A wave front advances for a fixed distance per unit of time in a direction normal to the front. A wave generated at the source site of a maze reaches the destination site along the shortest path. The wave ‘finds’ the exit. We just need to record the path of the wave. 5.1 vlsi: VLSI array processor An array processor solving shortest path over terrain with elevations is reported in [25]. This is a digital processor of 24 × 25 cells, manufactured with 2 µm CMOS. A cell size is 296 µm × 330 µm, the processor’s size is 7.9 mm × 9.2 mm. An elevations map is encoded to 255 levels of grey and loaded into the processor array. A signal is originated at the destination site. Wave-front of the signal propagates on the array. Each cell delays a signal by time proportional to the ‘elevation’ value loaded into the cells. Then the cell broadcasts the value to its neighbours. When a processor receives signal, the incoming signal direction is stored and further inputs to the cell are ignored. Starting from each cell we can follow the fastest path towards the destination site. 5.2 wave: Excitation waves In[50]alabyrinthsolutioninexcitablechemicalmediumisproposed.Ac.3×3cmlabyrinthismade of vinyl-acrylic membrane. The membrane is saturated with Belousov-Zhabotinsky (BZ) mixture. Impenetrable walls are made by cutting away parts of the membrane. The channels are excitable. The walls are non-excitable. Excitation waves are initiated at the source site by touching the membranewithasilverwire.Thewave-frontspropagatewithaspeedofc.2mm/min.Dynamicsof thewavesisrecordedwith50secintervals.Thelocationsofthewave-frontsarecolour-mapped:the colourdependsonthetimeofrecording.Ashortestpathfromthesourcesitetothedestinationsite is extracted from the time lapse colour maps. In this setup excitation waves explore the labyrinth but the path is extracted by a computer. The approach is slightly improved in [9]. By recording time lapse images of excitation wave fronts propagating in a two-dimensional medium we can construct a set of isochrones: lines which points are at the same distance from the site of the wave origination. By extracting intersection sites of isochrones of waves propagating from the source site to the destination site with isochrones of waves propagating from the destination site to the source site we can extract the shortest path. Experimentsreportin[9]dealnotwithamazebutaspacewithtwoobstacles.Theapproachwould workinthemazeaswell.TheBZmediumdoesnotdoanycomputation.Theresultsareobtainedon acomputer byanalysing dynamicsof theexcitationwave fronts.Somethingis betterthannothing: the approach is successfully used in unconventional robotics [7, 6]. Another BZ based maze solver is proposed in [42]: it exploits light-sensitive BZ reaction. Ex- traction of the path requires an extensive image analysis of the excitation dynamics, therefore this prototype is not worthy of discussion here.