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.