0:00

So, in the previous lecture, we saw that eigenvalues play a fundamentally important

Â role when you want to understand stability properties of linear systems. We saw that

Â if all eigenvalues have strictly negative real part, the systems are asymptotically

Â stable. If one eigenvalue is positive, then we have positive real part. Then,

Â we're screwed and the system blows up. Now, today, I'm going to use some of these

Â ideas to solve a fundamental problem in swarm robotics. And this is known as the

Â Rendezvous Problem. And, in fact, what it is, is you have a collection of mobile

Â robots that can only measure the relative displacements of their neighbors. Meaning,

Â they don't know where they are, but they know where they are relative to the

Â neighbors. So here, here we have agent i, and it can measure xi minus xj, which is

Â actually this vector. So, it knows where agent j is relative to it. And this is

Â typically what you get when you have an censor skirt, right? Because, you can see

Â agents that are within a certain distance od you. And, as we saw, you know, where

Â they are relative to you. If you don't have global positioning information, you

Â don't know where you are so there's no way you're going to know, globally, where this

Â thing is, but you know where your neighbors are locally. And the Rendezvous

Â Problem is the problem where having all the agents meet at the same position. You

Â don't want to specify in advance where they going to meet because since they

Â don't know where they are, they don't know where they going to meet. They can say,

Â oh, we're going to meet in, at the origin. But I don't know where the origin is. Is

Â it in, in Atlanta, Georgia? Or is it in Belgium, or is it India? What do I know,

Â right? So, the point is, we're going to meet somewhere, but we don't know where.

Â Okay. So, we have actually solved this problem

Â before. We sold it for the 2 robot case, where we had 2 robots. and we could

Â control the velocities right away. What we did is we simply had the agents aim

Â towards each other. So, u1 was x2 minus x1. And u2 was x1 minus x2. This simply

Â means that they're aiming towards each other. Well, if we do that, we can

Â actually write down the following the following system. This is the closed loop

Â system now, where we have picked that controller. So, x dot is this matrix times

Â x. Okay, let's see if this works now. Well, how do we do that? Well, we check

Â the eigenvalues of the A matrix to see what's going on. Alright. Here is my A

Â matrix, type eig in MATLAB or whatever software you're using, and you get that

Â lambda 1 is 0, lambda 2 is negative 2. Okay, this is a little annoying, right?

Â Because we said asymptotic stability means that both eigenvalues need negative real

Â part, this doesn't have that. But asymptotically stable, so asymptotic

Â stability also means that the state goes to the origin and, like we said, we don't

Â know where the origin is, so why should we expect that? We should not expect it. We

Â also know that one positive eigenvalue or eigenvalue with positive real part makes a

Â system go unstable. We don't have that either. In fact, what we have is this

Â in-between case that we called critical stability. We have one 0 eigenvalue and

Â the remaining eigenvalues have negative real part. So, this is critically stable.

Â And, in fact, here is a fact that I'm not going to show but this is a very useful

Â fact. So, that if you have one eigenvalue be zero and all the others have negative

Â real part, then in, in a certain sense, you're acting like asymptotic stability.

Â Meaning, you go, in this case, not to zero but you go into a special space called the

Â null space of A. And the null space of A is given by the set of all x, so such that

Â when you multiply A by x, you get zero out. That's where your going to end up.

Â So, your going to end up inside this thing called the null space of A, in this case,

Â because you have one 0 eigenvalue and all others having strictly negative real part.

Â And if you type null(A) in MATLAB, you find that the null space for this

Â particular A is given by x is equal to alpha, alpha where alpha is any real

Â number and why is that? Well, if I take negative 1, 1, 1, negative 1, this is my A

Â matrix, and I multiply this by alpha, alpha, what do I get? Well, ll' get minus

Â alpha plus alpha here, and then I get plus alpha minus alpha there, which is clearly

Â equal to 0. So, this is the null space. Okay, what does this mean for me? Well, it

Â means that x is, x1 is going to go to alpha and x2 is going to go to alpha. x1

Â goes to alpha, x2 goes to alpha, which means that x1 minus x2 goes to 0 because

Â they go to the same thing. Which means, that we have, ta-da, achieved rendevous.

Â They end up on top of each other. In fact, they end, end up at alpha. We don't know

Â what alpha is but We know that they end up there. Okay.

Â Now, if you have more than two agents, we simply do the same thing. In this case, we

Â aim towards what's called the centroid of the neighbors. And, in fact, if we write

Â this down, we write down the same thing for more than one agent, we get that x dot

Â i, before it was just xj minus xi, there were 2 agents. Now, I'm summing over all

Â of agents i's neighbors. That is doing the same thing if you have more than one

Â agent. And, in fact, if you do that and you stack all the x's together then you

Â can write this as x. is negative lx. And this is just some bookkeeping. And the

Â interesting thing here, here is that l it, it's known as the Laplacian of the

Â underlying graph. Meaning, who can talk to whom. that's not so important. The

Â important thing though is that we know a lot about this matrix L and, again, and

Â it's called the graph Laplacian. And the fact is that if the undergrinding,

Â underlying graph is connected, then L has one 0 eigenvalue, and the rest of the

Â eigenvalues are positive. But look here, we have negative L here, which means that

Â negative L is one 0 eigenvalue and the rest of the eigenvalues are negative.

Â That means that this system here, the general multiagent system here is actually

Â critically stable. And we know that it goes int o the null space of L. And it

Â turns out, and this is a fact from something called algebraic graph theory.

Â We don't need to worry too much about it. We just know that clever graph

Â theoreticians have figured out that the null space to L, if the graph is connected

Â which means that there is some path with, through this network between any two

Â agents is given by not alpha, alpha but alpha, alpha, alpha, alpha, alpha, a bunch

Â of alphas. So, just like before, if I have this thing and, in fact, it doesn't have

Â to be scalar agents, what I do have is that all the agents go to the same alpha

Â or in other words, the difference between the agents will actually disappear. And

Â when we did this, we design a controller. We actually designed this thing here. And

Â this thing is so useful that it actually has its own name. It's known as the

Â consensus equation because it makes agents agree. In this case, they were agreeing on

Â position. But this equation actually will solve the rendezvous problem because of

Â the fact that the corresponding system matrix you get is negative L at the right

Â eigenvalues which means that the system is critically stable so we can solve

Â rendezvous in the multirobot case. And again, you've seen this video. Now, you

Â know what it was I was running to generate this video. In fact, you can go beyond

Â rendezvous So, here is actually a course that I'm teaching at Georgia Tech, where

Â you want to do a bunch of different things. And again, all I'm doing is really

Â the rendezvous equation with a bunch of weights on top of it. And we're going to

Â learn how to do this. I just want to show you this video, because I think it's quite

Â spectacular. You have robots that have to navigate an environment. They're running

Â these, basically the conses equation and they have to avoid slamming into

Â obstacles, so I should point out that this was the final project, project in this

Â course, it's called network control systems. And I just wanted to show you

Â that you can take this very simple algorithm that we just dev eloped, make

Â some minor tweaks to it, which we're going to learn how to do, to solve rather

Â complicated, multiagent robotics problems. So here, the robots have to split into

Â different subgroups and avoid things, they have to get information, they have to

Â discover missing agents and so forth. And we will learn how to do all of that in

Â this course. Now, having said that, talk is cheap, right? And simulation is maybe

Â not cheap, but let's do it for real. In this case, we're going to have two Khepera

Â mobile robots, and what we're going to do is we're going to use the same PID

Â go-to-go controllers and we're going to let the consensus equation flop down

Â intermediary goal points. And what we're going to do is we're going to keep track

Â of our position using odometry, meaning our, our real encoders. And what the

Â robots are going to do, is they're actually going to tell each other where

Â they are rather than sense where they are because we haven't talked yet about how

Â the design sensing links. So, what we're doing is we're faking the sensing and

Â telling, they're telling each other where they are. And they're using a PID

Â regulator to go in the direction that the consensus equation is telling them to go

Â in. And now, let's switch to the actual robots running and solving the rendezvous

Â problem. So, now that we have designed a closed looped controller for achieving

Â rendezvous we're going to deploy it on our old friends, to Khepera mobile robots. so,

Â what we will see now are these two robots actually executing this algorithm. and we

Â will be using the same go to goal controller as we designed earlier to

Â achieve this. And, as always, I have J P.. De la Croix here to conduct the affairs

Â and practically, we're going to see two robots crashing into each other which is

Â exciting in its own right. But intellectually, what we're going to see,

Â is the state of the system asymptotically driving into the null space of our new A

Â matrix. And the reason for that is, as we've seen this matrix has 0, 0

Â eigenvalue, which means that the system is critically stable and the states approach

Â the null space. So, J.P., without further ado, let's see a robotic crash. So, we see

Â they're immediately turning towards each other and . Pretty exciting stuff, if I

Â may say so myself.

Â