Okay, we continue studying the properties of networks. What we've seen in the previous lectures is that the degree distribution is actually very important. This is what we observed. In other words, there is no hub. I'm sure you're not surprised to see that again, the man in the street. There is no reason why we should have a hub in a school of fish. There is no leader. All the fish are biologically the same, physiologically the same. They don't have superpowers, there is no superhero. We do not have hubs. We have the homogeneous degree distribution, and the level of clustering is actually pretty high. The clustering measures how much your neighbors are connected themselves, you look at your nearest neighbor and your nearest neighbor connected to other nearest neighbors. Now we went on to study the controllability, I'm going to use everything that Justin said. He talked about the structural controllability and the exact controllability. Now that we have the network, what we want to say, well, let's say that I can take control of one agent, one fish, or one bird. Can I actually get the swarm or the flock to go into one direction? Having access in our case, we have a network, which is not that big here. We have all the properties we need. We've been able to apply the two theories. What we have observed again is that to gain access to be able to control the entire swarm, you need to have a certain number of connections. The parameter k here, again, it's the number of neighbors that the agents are looking at. If you take 10 agents, meaning that you have only a very small swarm, well, with four neighbors, you will reach a complete controllability. Here, what you have on the y-axis. It's the fraction of agents that you need to drive. That's essentially connected to the rank of the matrix that you've seen this morning. Here it tells us that when we hear that one agent can control everyone, if you look at this, this is 2,000 agents, that's the size of the flocks by Cabagnow. When you have seven neighbors. Well now, one bird should be able to control all the other birds. As I said before, if you increase the size of your flock, you need to have more connections for that. Controllability is guaranteed in this case, It's essential because we all know that even though there is no leader, the argument here is that when there is specific information, one fish or one bird will have access to privilege information and then will stop behaving like the others. If there is a shark attacking, it's very likely that the fish is not going to look at the neighbors and say, well, I'm going to do the average of my neighbors instead. These fish is going to stop collectively acting and it's going to move in the opposite direction. That change in behavior propagates and controls the swarm. Now, based on what I said, we could actually design the swarm by designing that network. What I've shown before was just using one specific SSN, the swarm signaling network, which is the network of interaction based on the topological interaction. But as we said before, we have the ability to design this interaction. How do we want to do that? Designing something is nice, but you need to have an objective or maybe a market, I don't know. In our case, the variable that we are interested in is how fast the system will reach consensus. What we want, as we said, we want a system that is capable of really moving fast and adapting to changing circumstances. When we study consensus reaching, there is a property is called Lambda 2. This is an eigenvalue of a matrix, the matrix L that Justin shown this morning. What we did is we studied how we could increase Lambda 2 so that we can get the system to reach consensus faster. Imagine if you have a huge school of fish and it takes them an hour to decide shall we go to the right or shall we go to the left? Then there is a shark coming while there would be a feast for the shark, but not so good for the school of fish. We want to maximize that. We've been doing some work on trying to design the swarm from the standpoint of designing networks in order to maximize and optimize the speed to consensus. I'd like to now some words of caution because when you hear that you say, well, I think I have all the elements I can make my swarm back home tonight. Well, having just a network, as we know, is not sufficient. The network is important, gives you a bird's eye view of the entire system. But the swarms are dynamic and they need information, as we said. The network serves as a communication channel. We cannot just focus and design the network. What we have to do is we also need to have information theoretic approach. We need to use information theory to balance a bit of some of the decisions we make by just looking at network. We need information and we need control as well. If we want to make something that we want to control. In control theory, we have feedback loops, some of them are positive, some are negative. In swarming systems, what you have is a very fine balance between a negative feedback loops and positive feedback loops, the negative one are good. They are stabilizing the system. But the positive one can be good in a sense that they are amplifying the signal. But if they are too strong, they can destabilize the system. You need to do some control theory to be able to maintain a balance between those feedback loops. Now, let's move on to the part on information theory. Rick, paved the way on this. Now, you-all like kings in information theory. Information is power and that is true for swarms as well. What we know is that swarms are so effective because essentially they have augmented sensory capabilities. If you take one fish by itself well, it's limited by just the range of things that it can sense. But when you have one fish within a school, all the fish can benefit from all the senses from all the other agents. This is the so-called many eyes theory. A school of fish doesn't have, is more than any times the pair of eyes that we have from the individuals. This really improves the responsiveness to threats and dangers and also augments collected surveillance. In terms of information now, for the next five minutes we'll talk about information theory. From the standpoint of swarms all of these is acquired locally. As we said, the threat is at one given location. So it's acquired locally and this has to be spread throughout the entire swarm, so it has to be shared globally. These can only happen if all the agents are interconnected. Essentially if you have a network underneath. Then this information, well, it's not just there, it's used by the swarm. It's being processed in a completely decentralized and collective way. This is decentralized computing essentially. Those of you doing high-performance computing, this is centralized parallel computing. The swarm is doing decentralized parallel computing at the same time. Now, this has been studied for flock of birds and school of fish. This are data from, this is again by a Tallahassee and Kibana and that's by the group by Herbert read. The references are here. They are in my book as well. What this is showing, let's look at the flock of birds. This is an event of collective turning. You have a flock of birds made off 176 birds and at a given point in time they start turning. Actually, at a given point in time, one bird starts turning and then all the others are collectively turning. What they had been doing, they have like an amazing set of different cameras and they are able to track in real time each and every bird. This is bird number 1. Each dot represents one of the 176 birds. This is the bird that decides to turn. We say that this is time t equals to zero and this is when the others are starting to turn. You can see that it takes less than half a second for the entire flock of birds to decide to follow that guy here. Underlying this, there is a very fast and effective information transfer. What was amazing about that work that was published in Nature Physics, is the fact that the transfer of information is not damped. There is no dispersion. In general, like word of mouth and things get distorted. You want friends to tell you something and then when you reach the other end of the room is completely distorted. It seems like flock of birds have a way of sharing information in a very effective way, with very little damping and very little distortion. This is about the same results for a school of fish. In that work what they have in red, you have essentially the response of the first individual, the first fish that decides to turn. In blue, you have what they call the escape wave which is the collective response. You see that the collective response is almost as good as the first respondents. Again, that is possible because all the fish can share information in a very, very effective way. That is interesting if we want to mimic information transfer, probably you want to look into the system. What we have been doing, well, we went back to information theory 101. You have a communication channel. You have our birds. Our birds are essentially routers for information. Just like you have wireless router, so the information goes through the swarm signaling network. Each red dot reaches a router and this bird will decide what to do and share that information. When you have a network like this, we know that there is a certain amount of information that the network can actually carry. This is given by the capacity of the communication channel called C. The Shannon Hartley theorem gives you that C is related to the bandwidth. The signal to know is ratio. Essentially to the bandwidth tells you how much information you can really transfer. The noise affects that. There are two ways of reducing the capacity of a communication channel. One is by reducing the bandwidth. Essentially how often you are updating the system. The other one is due to the noise. If you have too much noise, while even if you update the system very frequently, your capacity will be close to zero. When you analyze a system like this what you can do if first, you want to identify the potential bottlenecks. You see, well information has to flow from, say, that guy to this guy. What will be the bottleneck? Well, if we use the min-flow, max-cut theorem, we can say that there are four possible bottlenecks that are going to be related to, well, the minimum capacity through a blue link like this or reduced capacity by the agents. What I mean by that is, well, imagine that your agent has some delay in responding or imagine that your agent is slow in processing the information. Well, in this case, one agent may become the bottleneck in the information transfer process. Another possibility is that you have noise in the environment, in between two fish, two birds in this case, they are like flocking and then you have, the weather gets bad or it gets dark. Then you have more noise. By the way, birds and fish they don't school at night. Whenever you know, the sun is going down, the fish they go and hide and the birds, they also go and hide. They need light to be able to share information. You can have a low capacity in the edge or you can have a low capacity at the node level. Based on that, you have four possible scenarios. One is you won't be able to swarm because your bandwidth in the edge is too small or your noise is too high. Or again, your bandwidth at the node level is too low or the noise is too high. Given that, we again use the SPP model. We still use the same simple model that we introduced in the physical part. We use this. This is exactly the same as the equation that's just been shown this morning when you had the consensus system. This is for one agent and this is for the group of agents. One agent, I will look at a given set of neighbors J, and we'll try to reach consensus in the presence of noise. Of course, this T_n is related to the bandwidth. Now, we're saying that you only update a system every now and then. We all understand that if you increase the time of update, your system is going to have a very hard time coordinating, essentially. The beauty of this now from the control theory standpoint is that we can analyze that system, analytically we can use linear algebra. We you obtain a theorem, so I spare you the mathematics. It's not even in the book. It's in one of our papers. But what we obtain is a sufficient condition for swarming. What we have proved is that to be able to swarm, you need to have a minimum bandwidth which makes complete sense. Essentially you need to have a frequency of update of the system that is large enough. The minimum bandwidth that we have obtained is given here. It's actually connected to the structure of the network. The Lambda here is what we call an eigenvalue. Essentially, just think of this as being related to the structure of the network. Now we see that we have this connection between information theory and network theory. The minimum bandwidth is given connected to the properties of the network. After that, what we did, well, it became a bit more complex because then, if you want to study the effect of capacity, you need to have bandwidth and you need to have noise as well. What we did, we studied again the ability of the system to be in an ordered phase in the presence of decreasing bandwidth. This is B_n and different values of noise, Eta n. What we observe, let's look at this graph. They're all showing the same thing. They're all showing these Phi. Remember Phi is a measure of the order of the system. If phi is one, it means that all the agents are all going in the same direction. We have an ordered phase. If Phi is zero, the system has reached complete chaos, you can say. At high bandwidth in all cases, these are for 1,024 agents. This is like here, 1,024 and 128. In all cases when you have a high bandwidth, well essentially your system can swarm. You have plenty of information, and you update the system frequently enough. Now, the effect of noise, of course, is going to reduce this a bit. We know that when you increase the noise, you will get a second order phase transition. What we observed here that was very interesting is that when you decrease B_n, suddenly, your system goes from an ordered state to a disordered one. You have a collapse of swarming here. Then you can study again from the standpoint of statistical physics and you can prove that this is a second order phase transition again. That is for a given value of noise and a given density. The conclusion here. You have a question? Yeah. I'm not following completely but do you need a minimum n [inaudible]. No. I don't need a minimum n. But the value of n will affect the results. You always get [inaudible]. Yes. If you have n equals to 10, you can actually get some swarming. As long as you have enough connections, you can actually easily get swarming. But the value of the bandwidth here, the critical bandwidth will change. Essentially, you can look at these here. The more agents you have, the higher the minimum bandwidth has to be. Which makes sense because it's much harder to essentially get a larger group to reach consensus and to stay working collectively. These B_n zero, if you decrease and you go to say, 10 agents, it will become very small and it's actually very easy to get the system to swarm. Now in terms of designing those systems, what we said before is true. To be able to design the network is good, but we have to take into account that information theory is important. Now, we can say the same. We have seen that, well, we can design the bandwidth. We can find which value of the bandwidth, that this value depends on the network. There is this profound connection between information theory and network theory here. Again, we need to maintain the right balance between positive loop and negative loops. This is a schematic of essentially different agents. What we observe is, well, if you take these agents, it will take cues from several other agents. Some of the links that are denoted as I, J, K, and H. These are going to be positive feedback loops and others are going to be negative feedback loops. How you design the structure of your network will actually affect the balance between these loops. I don't have so much time, but this is another movie, I'm not going to say this is not from my group and maybe you've seen that online. This is very nice. These are quadcopters that are doing different patterns. If you go on YouTube, you'll find this. This is very nice, but it's actually not swarming. This is advertised as being swarming, but it's not swarming. What I'm saying here is that you can have a multi-robot system, but it's not because you have many robots that you have a swarm. This system is not a swarm because they actually use cameras to track the position of the agents. This is entirely controlled by one computer. This is not decentralized. To have a swarm, you need to have many robots, but you need to ensure that they are operating in a completely decentralized way in terms of sensing, in terms of communication, in terms of computation, and response. That work was amazing. I'm not criticizing. All I'm saying is that when people use the word swarm for swarm of robotics, more often than not, the system they have is not a true swarm. At some point, they may have cameras that are looking to position, all the information goes through central computer and so on. How can we make a system truly a swarm? What we argue here is that now is a fantastic time, I'm not a roboticist by the way, but there are all sensors, communication devices, microcomputers like the Raspberry Pi zero and 3. The Raspberry Pi 3, which is just now in the market, it's $35. It's almost as powerful as any computer you had like three years ago, 64-bit and so on. Extremely cheap. Communication devices like the XV system can make a mesh network very powerful, completely independent. You have plenty of sensors, they cost like 50 cents. You can put all of these together and you can really make a robotic system that will be a real swarm. Where everything will be computed on both using the Raspberry Pi, where the communication will be through these networks. What we have been doing in my group, we have been working on platform agnostic swarming technology essentially. We're not making robots, but a system that you put onto another robot such that you can make them swarm together. We have been doing that with two platforms right now, but we argue that we can actually do that with any platform. That's an eBot, okay, this is a commercial robot that you can buy from a company Edge robotics. On the top of it, we have added this swarm enabling technology, which is made of a Raspberry Pi, a system that will make its own ad-hoc communication network, sensors and using that, we have been able to get a system that will perform collective surveillance and monitoring. I'll show you a movie in a minute. But we also went onto doing that with buoys. These are floating platforms and inside here, you have the exact same technology to get them to swarm. We put this onto some of the reservoirs in Singapore, they measure the environment, they share information that they move in order to find the right information. Well, Peter, you introduced that when you said that essentially can we control complex systems? Well, it's also an oxymoron to say that can we design swarms? This came about through natural evolution. The question is, can we really do that? Now coming at the end of this lecture after all I said giving you design principles, this can seem a bit weird; but there are actually two answers to that question. The first one is, we can definitely do that. I hope that some of the examples I've shown, with the robots showing that we can actually take very simple robots then we can put them together and they can perform collective behaviors, so that we have autonomy, we have emergence, they solve problems in a collective way, and of course we want to do that again to have robustness. During the demo, for instance, with the robots, we had two of them failing but the system continue to operate. Even if the one that finds the lights, has a problem, they will continue to operate. You have robustness, you have flexibility, as I said. You can be within the arena, you can interact with the swarm and you have scalability. When I was trying to get more money so that we can have more robots. The drawback of this is, if you look at nature, there are many interesting collective behaviors. I'm not sure that this is exactly what we need for a given problem. That's often the question. Somebody will come and say, "My company is doing that, and I'd like you to design a swarming algorithm that will do this." I'm going to turn to my fish and my birds, and they are not doing that. They are doing their own behavior because they have their own problem to solve. Now trying to find a way to solve these very stiff inverse problem of finding the right collective behavior or if you want the right interaction rules such that I get exactly the behavior I want, I think we have many years of research before we get there. Just to conclude, maybe the solution is self-design for like self-organized systems like this. Thank you very much for your attention.
