Smart search strategies for random targets

Researchers at TU Darmstadt present new approaches to a problem of statistical physics

2024/04/02

Whether bacteria in search of food or microrobots that automatically collect toxins or waste, again and again this is a problem in statistical physics that has not yet been clarified satisfactorily: how does an “agent” have to move in order to collect randomly distributed targets as skilfully as possible? Researchers at TU Darmstadt have now presented an approach in the renowned journal Proceedings of the National Academy of Sciences (PNAS) that can be used to systematically determine efficient search strategies. It could help to intelligently design tasks such as the search for cancer cells or environmental rehabilitations in the future.

One problem in statistical physics that has been studied for decades addresses the question of how an “agent” has to move in order to efficiently collect randomly distributed targets. This can be, for instance, a bacterium in search of essential chemicals, a bird of prey on the hunt for food, or a (micro)robot collecting toxin molecules or waste materials.

The question of the optimum movement strategy is particularly challenging in the typical case where the food distribution is unknown to the agent but is spatially correlated; that is to say, it changes continuously in space rather than abruptly. For example, bacteria not only find a high concentration of nutrients directly at a food source, but also in the area around it because the corresponding molecules spread diffusively.

Bacteria have developed so-called chemotactic search strategies to exploit such correlations. Here, they measure the change in food concentration along their path and change their direction of movement so that they statistically move in the direction of ascending concentration. This allows them both to take advantage of their experience of the food concentration increasing in a specific direction and to explore their environment in order to constantly check to see whether the food concentration might be increasing more in another direction.

There is currently a similar problem in the field of artificial microswimmers that, like bacteria, can move autonomously in their environment: how can they be programmed to efficiently collect toxin molecules or microplastics? Statistical physics has not yet found satisfactory answers to such challenging search problems. Previous approaches have been limited to phenomenological models, which essentially only describe the movement of bacteria. By the same token, there are still no systematic approaches to systematically determine the optimum search strategies. That is why it is still largely unclear how efficient the search strategies described in phenomenological models and the evolutionarily developed tactics (strategies) by the bacteria really are.

Researchers at TU Darmstadt from the Soft Matter Theory Group led by Professor Benno Liebchen (Department of Physics, Institute for Condensed Matter Physics) have now taken a look at this knowledge gap. As part of the publication "Smart Active Particles Learn and Transcend Bacterial Foraging Strategies”, they have, for the first time, developed a method to systematically determine efficient search strategies.

In it, an agent is considered that moves at a constant speed and that can decide in each time step either to continue in the same direction as last time or to change its direction of movement (randomly). The agent chooses between these two options with the help of artificial neural networks, into which, among other things, the “food concentration” visible to the agent in its immediate vicinity is fed. However, the global distribution of the food remains unknown to the agent.

Left to right: Mahdi Nasiri, Edwin Loran, Professor Benno Liebchen
Left to right: Mahdi Nasiri, Edwin Loran, Professor Benno Liebchen

The neural networks were trained in a wide class of random “food concentration” environments. The agent's resulting movement patterns were then analysed. Interestingly, with the exception of a few striking details, these showed a striking resemblance to the movement patterns of real bacteria and to the movement patterns described by phenomenological models.

What was even more surprising, however, was the result of a comparison of the efficiency of the search for food. This showed a clear superiority of the agents trained by means of neural networks, which were much better at exploiting the structure of their environment than could be described by previous phenomenological models.

The research results could prove useful for programming future microswimmers, nanorobots and smart particles for tasks such as searching for cancer cells, microplastics or for environmental rehabilitation.

At the same time, the results demonstrate the great benefits that new machine learning tools – beyond big data and large language models – can have in physics. They make it possible to investigate problems that are almost impossible to solve with conventional computational and simulation methods.

AG Liebchen/sip

The publication

M. Nasiri, E. Loran, B. Liebchen: Smart Acitve Particles Learn and Transcend Bacterial Foraging Strategies, in Proceedings of the National Academy of Sciences (PNAS)