The fundamental nature of every living organism is the efficacy of its actions. No creature, with the exception of humans, spends up energy on unwanted tasks. The frugality of their movements can be replicated in everyday networking problems faced by humans. For instance, the travelling salesman problem is one such idea, which deals with finding the shortest distance between two or more distinct points.
Choosing a better move correctly and quickly is a fundamental skill of living organisms that corresponds to solving a computationally demanding problem. A unicellular plasmodium of Physarum polycephalum searches for a solution to the travelling salesman problem (TSP) by changing its shape to minimise the risk of being exposed to aversive light stimuli.
The TSP is an optimisation problem in which the goal is to find the shortest route between several cities so that each city is visited exactly once, and the start and end points are the same.
The problem is NP-hard, meaning that as the number of cities increases, the time needed for a computer to solve it grows exponentially.
The complexity is due to a large number of possible solutions. For example, for four cities, there are only three possible routes. But for eight cities, the number of possible routes increases to 2520.
Experimental Setup
The type of amoeba used by the scientists was a particular plasmodium, which is fed with oat flakes and weighs around 12 mg. This amoeba changes its shape by syphoning the gel in and out at a velocity of 1mm per second to create pseudopod-like appendages.
An identical chip with 64 lanes was used to fix the physical size of the chip. The time required for communication between the branches of plasmodium should be equalised independent of n.
The plasmodium is placed inside the chip and all the initial states are set to 0. All the lanes were illuminated to block advances of the plasmodium.
- Camera: CCD
- Temperature: 27 deg Celsius
- Humidity: 95%
Stimulating Amoeba With Light
In their experiments, the researchers placed the amoeba in the centre of a stellate chip, which is a round plate with 64 narrow channels projecting outwards, and then placed the chip on top of an agar plate. The amoeba is confined within the chip, but can still move into the 64 channels.
Light stimuli are updated according to recurrent neural network dynamics to solve the Traveling Salesman Problem.
In order to maximise its nutrient absorption, the amoeba tries to expand inside the chip to come in contact with as much agar as possible. However, the amoeba has an aversion for light. So, each channel can be selectively illuminated by light, to manipulate the amoeba to encroach into dark channels.
For instance, if the amoeba branches out in three routes say, Bangalore-Delhi, Bangalore- Mumbai, Bangalore-Assam; then the branch occupying Bangalore-Mumbai route will be left dark avoiding the amoeba from visiting multiple routes simultaneously.
The model is designed such a way that, shorter distance is given preference to be illuminated over longer distances.
The amoeba explores the solution space by continuously redistributing the gel in its amorphous body at a constant rate, as well as by processing optical feedback in parallel instead of serially.
The way these organisms move indicates the presence of a fundamental law, that runs undercurrent as the amoeba retains the rules of the previous activation and replicates it when invoked again.
Groups of the branches perform synchronisation and desynchronisation for sharing information even though they are spatially distant.
The efficacy of this approximation has befuddled the researchers and the mechanism still remains as a mystery.
Key Takeaways
Although a conventional computer can still solve the TSP much faster than an amoeba, especially for small problem sizes, the new results are intriguing and may lead to the development of novel analogue computers that derive approximate solutions of computationally complex problems of much larger sizes in linear time.
“We will investigate further how these complex spatiotemporal oscillatory dynamics enhance the computational performance in finding higher-quality solutions in shorter time,” said coauthor Song-Ju Kim at Keio University.
Researchers are now exploring the use of the amoeba-inspired electronic circuits for tackling the constraint satisfaction problem, satisfiability problem, analogue-to-digital conversion and finding walking manoeuvre of a multi-legged robot. Such an approach to exploit physical parallelism may develop a novel analogue computing paradigm, providing powerful approximation methods for solving complex optimisation problems appearing in a wide spectrum of real-world applications.
