Liquid metal solves maze
Andrew Adamatzky Alessandro Chiolerio Konrad Szaciłowski
cs.ET cond-mat.soft

Automatic Calcium Scoring in Cardiac and Chest CT Using DenseRAUnet
    Jiechao Ma Rongguo Zhang
    December 30, 2023
===================================================================




A room temperature liquid metal features a melting point
around room temperature. We use liquid metal gallium due to its non-toxicity. A physical maze is a connected set of Euclidean domains separated by impassable walls. We demonstrate that a maze filled with sodium hydroxide solution is solved by a gallium droplet when direct current is applied between start and destination loci. During the maze solving the droplet stays compact due to its large surface tension, navigates along lines of the highest electrical current density due its high electrical conductivity, and goes around corners of the maze's corridors due to its high conformability. The  droplet maze solver has a long life-time due to the negligible vapour tension of liquid gallium and its corrosion resistance and its operation enables computational schemes based on liquid state devices. 



Keywords: liquid metal, gallium, unconventional computation, liquid cybernetic systems








§ INTRODUCTION


Dynamic behaviour of liquid meta droplets has been known for a substantial amount of time. The first reports by Alessandro Volta and independently William Henry were published in 1800 <cit.>. These initial reports concern phenomena related to the so-called "mercury beating heart", a fascinating experiment, in which a drop of metal pulsates changing its shape due to a sequence of oxidation and reduction processes taking part at its surface, which in turn result in changes of surface tension at water/metal interface. The full and comprehensive description of these processes was given recently by Najdolski et al <cit.>, however some mechanistic investigations have been reported much earlier <cit.>.   Very recently electrochemical oscillators based on gallium droplets have been described in detail, including various oscillations modes <cit.>. In 2019 Liu, Sheng and He proposed the concept of `liquid metal soft machines': implementation of actuation with liquid metal gallium and its alloys <cit.>. Their extensive studies on shape changing <cit.>, electromagnetic propulsion <cit.> and  self-propulsion <cit.> demonstrated that gallium and similar alloys could be fruitful materials for the implementation of future liquid robots <cit.> and liquid computers <cit.>. Such cybernetic systems could be used to explore complex geometrically constrained spaces, where not other machines can enter. This new paradigm, of liquid state robots, could show particular advantages over specific application domains such as space, extreme environment exploration (where pressure, radiation, temperature are high enough to impair conventional solutions functionality), and as pointed out ultimately, also in high performance computation and data storage <cit.>. Energetic systems able to store, transfer, harvest energy in the liquid state have also been conceived <cit.>. Mobility, as fundamental aspect of autonomy, after computation and homeostasis <cit.>, has been shown to provide an alternative way to transport information in liquid cellular automata <cit.>. To evaluate a potential of the `gallium robots' for programmable navigation in the constrained space we decided to test them on the task of a maze solving. 

To solve a maze means to find a route from the source site to the destination site in a geometrically constrained space. There are two scenarios of the maze problem: (1) the solver does not know the whole structure of the maze 
and (2) the solver knows the structure of the maze. Shannon's maze solving mechanical mouse Theseus <cit.> and Wallace's maze solving computer <cit.> were used in the first scenario in the early 1950s. The second scenario maze solving employs the famous Lee algorithm<cit.> as follows. 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 till the destination site we start at the source site and then descend along the gradient of labels following the lowest numbers. In robotics the Lee algorithm was transformed into a potential method potential method pioneered in  <cit.> and further developed in <cit.>. 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 the maximum gradient <cit.>. 

The Lee maze solving algorithm is physically embedded in the mechanics of the experimental maze solvers proposed so far, see overview in  <cit.>. Examples of the experimental maze solvers are as follows. The shortest obstacle avoided path can be approximated by an electrical current and visualised with a glow-discharge <cit.>, thermal camera <cit.>, or as trace of 
self-assembled conductive particles <cit.>. When a source of electricity is not available the shortest path can be found via Marangoni flow and then visualised with dyes <cit.> or droplets <cit.>. The path from the source to the destination can be explicitly presented by orientation of crystal needles during crystallisation in a supersaturated solution of sodium acetate trihydrate and water <cit.>. The path can be also approximated by gradients of a diffusion of chemo-attractants and then traced by living creatures interacting with such molecules, e.g. slime mould <cit.> or epithelial cells <cit.>. Finally the path can be calculated by analysing geometry of excitation waves in a thin layer of Belousov-Zhabotinsky medium <cit.>. 
Therefore is was so tempting to built an autonomous robotic entity capable of decision-making and information processing. The current study explores the possibility of creation of an autonomous self-propagating and environment-responsible liquid machine.



§ METHODS






Gallium (Sigma Aldrich, UK), its temperature is kept at 36oC using a glass hot tray (RCHP-500G, Royal Catering, UK), two types of mazes were used (Fig. <ref>):
(M_1) PLA 3D printed maze 120 mm  diameter  with  6 mm  wide  and  10 mm  deep channels.
(M_2) nylon 70`mm  diameter  with  4 mm  wide  and 3 mm  deep  channels (Tesco’s  Toy  Mazes,  Tesco). The mazes were filled with 0.5 molar solution of NaOH (Sigma Aldrich, UK). 
Reasons for choosing these two mazes were (1) to check whether the approach is scalable and (2) to consider the case when Gallium droplet is fully immersed in the solution (M_1) and the case when it is half-immersed in the solution (M_2). The DC potential (30 V, 5 A) between starting point and destination sites was provided by  Tenma 72-10495  Bench Top Power Supply  via Platinum electrodes. The videos were recorded with Moto G6 and thermal images were done with FLIR ETS320. The Finite Element Method simulation was performed using Comsol COMSOL 5.3a, Licence No.13075366, d0946613b03f.



§ RESULTS




As soon as DC current is applied between positive electrode E1 (located at the start site in the central chamber of the maze) and negative electrode E2 (located at the destination site in the outside channel), Fig. <ref> the droplet jumps away from E1 by c. 3 mm but then remains motionless for few second (Fig. <ref>a). 

With continued application of DC some gas bubbles start forming at the site of the droplet close to E1, due to water electrolysis. In 7 s the droplet reaches turn 1  of the maze (Fig. <ref>b). While passing turn 1 the droplet got motionless for a few seconds at the wall connecting turns 1 and 2 (Fig. <ref>c) but then quickly dashes along corridor between 2 and 3  (Fig. <ref>d). Corners 3 and 4 almost do not affect the droplets motion (Fig. <ref>e) as it runs toward the turn 5. The droplet is delayed at the turn 5 by approximately 1 s (Fig. <ref>f) and at the turn 6 by approximately 4 s (Fig. <ref>g) till reaching the destination site in 27 s (Fig. <ref>h).



Tracing of the Ga droplet shown in Fig. <ref>i the positions of the droplet every 1 sec are marked. Their distribution, supported by the plot of the velocity (Fig. <ref>a) covered by Ga each second of the experiment, indicate that the droplet is substantially delayed, or even often stays still while gathering a momentum,  when turning the corners. The delay length though does not seem to be affected by the angle of the turn. 





Navigation of a gallium droplet in maze M_2 is illustrated in Fig. <ref>. It takes approximately 82 s for the droplet to reach a vicinity of the electrode E2. Nearly half of this time is spent by the droplet near the starting electrode E1 (Fig. <ref>a) gradually accelerating. By approximately 43 s the droplet reaches the waypoint 2 (Fig. <ref>b). It then dashes by waypoints 3 (Fig. <ref>c), and 4 (Fig. <ref>d). The droplet reaches waypoint 5 by approximately 45 s (Fig. <ref>e). It takes the droplet approximately 1 sec to circumnavigate around the end of the wall, marked 5 in Fig. <ref>f. The passage from the waypoint 5 to the waypoint 6 poses a substantial difficulty for the droplet due to strong electrolyte convection flow resulting from vigorous evolution of gas bubbles at the electrode E_2. Yet by 82^nd s since the beginning of the experiment the droplet approaches the electrode (Fig. <ref>g). Distribution of the droplet positions on the trace (Fig. <ref>h) and the velocity plot (Fig. <ref>b) show that the slowest parts of trajectory are at the beginning of the journey, when the droplet gathers a momentum to overcome its static position and, and at the end of the journey, when the droplet struggles to overcome waves of bubbling from the target electrode. In all other parts the velocity is relatively stable, subject to minor perturbations. The surface of the maze M_2 is much smoother than that of the maze M_1 therefore the droplet spends less time (that the droplet in M_2) turning around corners.
The irregularities in the speed of motion of the gallium droplet may originate from irregularities of the oxide layer formed at the surface of gallium and consequently in small changes in the intensity of Marangoni flow which is directly responsible for droplet motion. The Marangoni flow results from local differences in surface tension of the droplet, as the case with some other types of travelling droplets <cit.>.  This also explains the induction period — the droplet needs to accumulate sufficient amount of oxide (on the anodic side of the droplet) to start its motion.  



In some experiments the droplet did not reach the target electrode E_2 due to its inability to choose between two branched pathways with nearly equal intensity of the current.  One of such experiments is illustrated in Fig. <ref>. The droplet reaches site a. The length of pathways p_abd and p_acd is nearly equal: 38 mm and 42 mm in the maze M_2. Intensity of the current along a pathway is proportional to the length of the pathway. Therefore, on both sides of the droplet the intensity was similar. Thus, droplet was unable to choose which way to proceed (bifurcation point). 





§ DISCUSSION




Why do gallium droplets move along the shortest path? This is because the intensity of electrical current is the strongest along the shortest path, as evidenced in Fig. <ref>, which is consistent with Kirchhoff's current law and Ohmic law, if we assume, for the sake of simplicity, that all the corridors in the maze have almost the same width. Then, the highest intensity current will be observed on a path with lowest resistivity (which corresponds to the shortest path if we assume identical specific resistivity of the liquid throughout the maze).  Approximation of the shortest collision-free path using electrical current was first demonstrated in a network of resistors in 1991 <cit.>:  a space is represented as a resistor network, obstacles are insulators. Later visualisation of the path-solving with electrical current without physical discretisation of space was demonstrated in  <cit.>. The Finite Element Method (FEM) simulation performed in Comsol Multiphysics 5.3 environment over a 2D domain shows the distribution of current density in the maze M_2, where two electrodes have been set in a way similar to the experiments (outer circle, red spot at +180o; inner circle, red spot at -90o) and a voltage drop of 5V forced between them, while medium conductivity has been adjusted to NaOH solution as per experiments. The mesh has been built in order to avoid numerical deviations close to the edges, despite computational complexity. 



This choice is fundamental in highlighting the role of wall conductivity, as shown in Fig. <ref>, a strategy that could be pursued to mitigate the high latency of Ga droplet during vertex bypasses. The top row (panels (a), totally insulating walls and (b), insulating walls with Au conductive layer on each sharp edge) shows in colour scale the (dJ/dx, dJ/dy) quantity integrated over a rigid disk of size half the channel width, comparable to the size of Ga droplet. Therefore this quantity gives a measure of the complexity of the potential field that acts on the droplet as accelerating force. Integrating over smaller sizes does not change the geometry of this planar force field, but it affects its strenght in reason of a direct proportionality. One conclusion is that much smaller droplets will be subject to lower accelerating forces and a proper trade-off with viscous forces could result in faster motion. The bottom row (panels (c), totally insulating walls and (d), insulating walls with Au conductive layer on each sharp edge) shows J as a distribution of red arrows, clearly indicating the maze solving trajectory, and the quantity grad J as black level curves. Differences between the insulated maze case and the maze where sharp edges have been deposited with a gold electrically conductive shell suggest us that such a functionalisation, either of the edges or of the whole wall structure is effective in reducing the strength of potential localised at the edges, thus avoiding droplet latency/pinning.


 Further studies of the programmable navigation of liquid metal droplets will aim to answer the following questions. Given fixed electrical potential and current supplied what is a maximum distance between electrodes the droplet can propagate? Given a gallium droplet of a fixed size what is a narrowest gap the droplet can squeeze into? Will several gallium droplets co-interact, due to them affecting local conductivity of the medium, while navigating towards the exit of the maze?




§ ACKNOWLEDGEMENT


AA acknowledges support of  with grant . 
Authors thank Dr. Tom Draper for kindly assisting with preparation of the NaOH solution. KS acknowledges support from National Science Centre (Poland) for financial support within the contract No. UMO-2015/18/A/ST4/00058. 


10

adamatzky2009hot
Andrew Adamatzky.
Hot ice computer.
Physics Letters A, 374(2):264–271, 2009.

adamatzky2012slime
Andrew Adamatzky.
Slime mold solves maze in one pass, assisted by gradient of
  chemo-attractants.
IEEE transactions on nanobioscience, 11(2):131–134, 2012.

adamatzky2017physical
Andrew Adamatzky.
Physical maze solvers. all twelve prototypes implement 1961 lee
  algorithm.
In Emergent Computation, pages 489–504. Springer, 2017.

adamatzky2019brief
Andrew Adamatzky.
A brief history of liquid computers.
Philosophical Transactions of the Royal Society B,
  374(1774):20180372, 2019.

adamatzkyZenodoJuly2019
Andrew Adamatzky, Alessandro Chiolerio, and Konrad Szaciłowski.
Supplementary materials. Liquid metal solves maze.
http://doi.org/10.5281/zenodo.3344993, 2019.

adamatzky2002collision
Andrew Adamatzky and Benjamin de Lacy Costello.
Collision-free path planning in the belousov-zhabotinsky medium
  assisted by a cellular automaton.
Naturwissenschaften, 89(10):474–478, 2002.

agladze1997finding
K Agladze, N Magome, R Aliev, T Yamaguchi, and K Yoshikawa.
Finding the optimal path with the aid of chemical wave.
Physica D: Nonlinear Phenomena, 106(3-4):247–254, 1997.

ayrinhac2014electric
Simon Ayrinhac.
Electric current solves mazes.
Physics Education, 49(4):443, 2014.

ayrinhac2018electron
Simon Ayrinhac.
The electron in the maze.
In Andrew Adamatzky, editor, Shortest Path Solvers. From
  Software to Wetware, pages 409–420. Springer, 2018.

baroud2010dynamics
Charles N Baroud, Francois Gallaire, and Rémi Dangla.
Dynamics of microfluidic droplets.
Lab on a Chip, 10(16):2032–2045, 2010.

cejkova2014dynamics
Jitka Cejkova, Matej Novak, Frantisek Stepanek, and Martin M Hanczyc.
Dynamics of chemotactic droplets in salt concentration gradients.
Langmuir, 30(40):11937–11944, 2014.

tectomers
Alessandro Chiolerio, Carsten Jost, Thomas C. Draper, and Andrew Adamatzky.
The ph sensitivity of solvated tectomer electronics.
arXiv preprint arXiv:1901.05519v1, 2019.

chiolerio2017smart
Alessandro Chiolerio and Marco B Quadrelli.
Smart fluid systems: the advent of autonomous liquid robotics.
Advanced Science, 4(7):1700036, 2017.

CERES
Alessandro Chiolerio and Marco B. Quadrelli.
Colloidal energetic systems.
Energy Technology, 1800580:1–10, 2019.

connolly1990path
Christopher I Connolly, JB Burns, and R Weiss.
Path planning using Laplace's equation.
In Robotics and Automation, 1990. Proceedings., 1990 IEEE
  International Conference on, pages 2102–2106. IEEE, 1990.

dubinov2014glow
Alexander E Dubinov, Artem N Maksimov, Maxim S Mironenko, Nikolay A Pylayev,
  and Victor D Selemir.
Glow discharge based device for solving mazes.
Physics of Plasmas, 21(9):093503, 2014.

fuerstman2003solving
Michael J Fuerstman, Pascal Deschatelets, Ravi Kane, Alexander Schwartz,
  Paul JA Kenis, John M Deutch, and George M Whitesides.
Solving mazes using microfluidic networks.
Langmuir, 19(11):4714–4722, 2003.

hwang1992potential
Yong K Hwang and Narendra Ahuja.
A potential field approach to path planning.
Robotics and Automation, IEEE Transactions on, 8(1):23–32,
  1992.

lagzi2010maze
István Lagzi, Siowling Soh, Paul J Wesson, Kevin P Browne, and Bartosz A
  Grzybowski.
Maze solving by chemotactic droplets.
Journal of the American Chemical Society, 132(4):1198–1199,
  2010.

lee1961algorithm
Chin Yang Lee.
An algorithm for path connections and its applications.
IRE transactions on electronic computers, 3:346–365, 1961.

Lin1974
Shu-Wai Lin, Joel Keizer, Peter A. Rock, and Herbert Stenschke.
On the mechanism of oscillations in the "mercury beating heart".
Proc. Natl. Acad. Sci., 71(11):4477–4481, 1974.

liu2019
Jing Liu, Lei Sheng, and Zhi-Zhu He, editors.
Liquid metal soft machines.
Springer, 2019.

Mollenkamp2019
Hartwig Moellenkamp, Bolko Flintjer, and Jansen Walter.
200 jahre "pulsierendes quecksilberherz".
CHEMKON, 1(2):117–125, 1995.

nair2015maze
Aswathi Nair, Karthik Raghunandan, Vaddi Yaswant, Sreelal S Pillai, and Sanjiv
  Sambandan.
Maze solving automatons for self-healing of open interconnects:
  Modular add-on for circuit boards.
Applied Physics Letters, 106(12):123103, 2015.

Najdolski
Netodija Najdolski, Valentin Mirceski, Vladimir M. Petrusevski, and Sani
  Demiri.
Mercury beating heart: Modifications to the classical demonstration.
J. Chem. Educ.N, 84(8):1292–1295, 2007.

nikolov2002superspreading
Alex D Nikolov, Darsh T Wasan, Anoop Chengara, Kalman Koczo, George A
  Policello, and Istvan Kolossvary.
Superspreading driven by marangoni flow.
Advances in colloid and interface science, 96(1-3):325–338,
  2002.

pavlov1984method
VV Pavlov and AN Voronin.
The method of potential functions for coding constraints of the
  external space in an intelligent mobile robot.
Soviet Automatic Control, 17(6):45–51, 1984.

reyes2002glow
Darwin R Reyes, Moustafa M Ghanem, George M Whitesides, and Andreas Manz.
Glow discharge in microfluidic chips for visible analog computing.
Lab on a Chip, 2(2):113–116, 2002.

rubin1974lee
Frank Rubin.
The lee path connection algorithm.
IEEE Transactions on computers, 100(9):907–914, 1974.

scherber2012epithelial
Cally Scherber, Alexander J Aranyosi, Birte Kulemann, Sarah P Thayer, Mehmet
  Toner, Othon Iliopoulos, and Daniel Irimia.
Epithelial cell guidance by self-generated egf gradients.
Integrative Biology, 4(3):259–269, 2012.

shannon1951presentation
Claude E Shannon.
Presentation of a maze-solving machine.
In 8th Conf. of the Josiah Macy Jr. Found.(Cybernetics), pages
  173–180, 1951.

tarassenko1991analogue
L Tarassenko and A Blake.
Analogue computation of collision-free paths.
In Robotics and Automation, 1991. Proceedings., 1991 IEEE
  International Conference on, pages 540–545. IEEE, 1991.

tarassenko1991parallel
Lionel Tarassenko, Gillian Marshall, Felipe Gomez-Castaneda, and Alan Murray.
Parallel analogue computation for real-time path planning.
In VLSI for Artificial Intelligence and Neural Networks, pages
  93–99. Springer, 1991.

toyota2009self
Taro Toyota, Naoto Maru, Martin M Hanczyc, Takashi Ikegami, and Tadashi
  Sugawara.
Self-propelled oil droplets consuming “fuel” surfactant.
Journal of the American Chemical Society, 131(14):5012–5013,
  2009.

homeostasis
Scott J. Turner.
Homeostasis as a fundamental principle for a coherent theory of
  brains.
Philosophical Transactions R. Soc. B, 374(20180373), 2019.

mobility
William F. Vining, Fernando Esponda, Melanie E. Moses, and Stephanie Forrest.
How does mobility help distributed systems compute?
Philosophical Transactions R. Soc. B, 374(20180375), 2019.

wallace1952maze
Richard A Wallace.
The maze solving computer.
In Proceedings of the 1952 ACM national meeting (Pittsburgh),
  pages 119–125. ACM, 1952.

wang2015electromagnetic
Lei Wang and Jing Liu.
Electromagnetic rotation of a liquid metal sphere or pool within a
  solution.
Proceedings of the Royal Society A: Mathematical, Physical and
  Engineering Sciences, 471(2178):20150177, 2015.

wyard1995potential
L Wyard-Scott and Q-HM Meng.
A potential maze solving algorithm for a micromouse robot.
In Communications, Computers, and Signal Processing, 1995.
  Proceedings., IEEE Pacific Rim Conference on, pages 614–618. IEEE, 1995.

Yu2018
Zhenwei Yu, Frank W. Yun, David Cortie, Lei Jiang, and Xiaolin Wang.
Discovery of a voltage-stimulated heartbeat effect in droplets of
  liquid gallium.
Phys. rev. Lett., 121:024302, 2018.

zhang2014synthetically
Jie Zhang, Lei Sheng, and Jing Liu.
Synthetically chemical-electrical mechanism for controlling large
  scale reversible deformation of liquid metal objects.
Scientific reports, 4:7116, 2014.

zhang2015self
Jie Zhang, Youyou Yao, Lei Sheng, and Jing Liu.
Self-fueled biomimetic liquid metal mollusk.
Advanced Materials, 27(16):2648–2655, 2015.





