Enhancing Population-based Search with Active Inference

Hello and welcome. It's December 13th, 2024. We're in Active Inference Guest Stream 93.1 with Nassim Dehoush. We're going to be discussing a paper we wrote together, Enhancing Population-Based Search with Active Inference. So thank you, Nassim, for joining. Looking forward to your presentation and the discussion. My pleasure. Thank you, Daniel. Very happy to be here and to share this joint work we did together a few months ago. Perhaps I could give a brief background information about how this work came to be. We did a podcast together and we had a few chats on Discord about Active Inference. And it was actually a way you used to explain Active Inference. You said that it's like the sense of touch, for example, wouldn't be really active unless you move your hand to really discover the texture. And it's the idea that indeed perception is not a passive process where you're just receiving data and processing it. It's that agents have an intent. And this is something that meditators can also experience. It's that even seeing, sight. If you are really empty inside, wouldn't you really be active unless you have some intent. So I thought about this in the context of a class of multi-agent systems that are used for optimization problems. So perhaps I'll give an overview of our work. So this is a kind of meta-heuristic methods that are used to solve all sorts of optimization problems. But we mainly focus on combinatorial optimization, so problems in graphs typically. And they use a population of agents to explore different solution paths. And one common feature, as I will highlight later, of these methods is that they, just like the naive perception we have of how even humans perceive, is that they consider that these agents have only reactive responses to the data they discover in the environment. We'll see it in more details later when I do a brief literature review. And so we try to incorporate predictive modeling, giving these agents an intent, which is to reduce their surprise and also update their belief. We'll talk about that as well. So the idea is to minimize the difference between the outcomes they observe and what they expect. And we try to integrate this to this class of methods known as population-based search methods with an instantiation on one method called the ant colony optimization. That's also inspired by you, Daniel, and your background working with ants. And so this would be applied to a problem which I think is famous enough, so I don't have to give a very detailed explanation of it, but perhaps for people who are not familiar with the traveling salesman problem. I will briefly explain it with this little app we put together for the paper. So it's a problem in graphs where you have typically a set of cities or locations. The problem consists in finding a route that visits all cities and goes back to your initial point. Okay. Now, with this kind of problems, there are two classes typically. Problems in P, which can be solved in polynomial time. One example would be finding the shortest route from one point to the other. That is very easy to solve, and it remains easy even for very large-scale graphs, very large numbers of cities. But this problem, the traveling salesman problem, the idea of visiting all cities and going back to your initial point, happens to be in a different class, NP-hard. So it is as hard as any computational problem you can think of. And here again, the difficulty comes with scale. It's that we don't have... Pretty much we don't have a better method than exhaustively listing all parts. So there are approximate solution methods known as heuristics and meta-heuristics. A very simple one, a very intuitive one, could be to visit the nearest city from your starting point and repeat this process until you go back to your initial point. So this is known as the nearest neighbor heuristic. So here I would start, for example, from this one, go to the next one, next one, next one, next one. And then…