The missing piece of the navigation puzzle was follow walls.

And now we have it, in the sense that we know how to move along boundaries of

obstacles. We also know which direction to go in and

that was given by this sliding condition. the one thing we don't know though is

when to stop, because take a look here. First of all, this is how follow wall, or

go to goal is taking me. Sliding tells me that, you know what, I

should move up in this direction. Let's look at this point.

Go to goal wants me to go there. Avoid obstacle wants me to go there.

And if I draw this again a little better, they are pointing in completely opposite

directions. And if I'm just sliding, I no longer have

anywhere to go. If I'm, instead using, in this case, r

negative pi over 2 times u avoid obstacle,

then that's just going to keep me going in a counterclockwise,

sorry, in a clockwise manner. so that's why this is the better behavior

to use, even though sliding is useful to go, to know which direction to start in.

Now, if I do that, then I'm happily going like this,

but check out at this point. Go to goal wants to go there.

Avoid obstacle wants to go there. We are no longer in conflict when it

comes to the switching conditions so any kind of sliding condition is going to

fail because here. I'm simply going to return to go to goal

and then I'm going to just keep doing this over and over again and I'm going to

get stuck in this corner. So, sliding is not answering when to stop

sliding or when to stop following walls. Instead, we need some other condition for

this. And here is what needs to happen.

First of all, we need to [COUGH] excuse me, have made enough progress.

What does that means? It means that if I'm switching here I'm

kind of, I don't want to stop here, here, here because in fact,

I should stop when I'm closer to the goal than where I was when I started sliding.

Because otherwise, you can indeed end up in a situation where you're moving

successively further and further way from the goal and basically you're switching

your way away from where you want to be. So, you want to insure that you're closer

to the goal at the end of the maneuver than you were when you began it.

The other is that you have a clear shot to the goal in some sense.

Meaning that you can actually move towards it.

[COUGH] Excuse me. Clear shot doesn't necessarily mean that

there are no obstacles. Becuase, let's say that the goal is there

and here's a giant obstacle that I haven't seen yet.

I don't know about that, but from any practical purpose, I somehow have a clear

shot to, to the goal. So, what we need to do is understand what

these conditions mean. Okay, let's say, that I started following

walls at time tau. So, let's say that I'm here, x at time

tau, that's where I am. Well, then progress, sufficient progress

can simply say that the current position, this is the current position x current,

it needs to be closer to the goal than where I was when I started my follow

wall. So, if I draw a circle here, at this

distance around the, the goal, let's pretend that this was a perfect

circle, then, any point here is going to be closer to the goal than where I

started. So, here are positions where I'm allowed

to stop following walls. But that's not enough.

We needed this notion of clear shot also. And the clear shot simply is this

condition here, where if I'm sitting here, then follow

wall, sorry, go to goal wants to take me in that direction.

Avoid obstacle wants to take me in this direction.

And we already know how to check whether or not they are somehow in agreement.

What that means simply is that this angle, the absolute value of this angle

should be less than pi/2, which we can simply encode by this inner

product condition, which simply take and compute u avoid obstacle transpose u go

to goal and check if that's positive, then we have a clear shot.

We don't really know about other obstacles but at least we have some

notion of a, a clear shot. So, these are the two pieces we need to

determine when its time to no longer move along the boundary.

Okay. Now, we have everything.

Here's my robot. It's very happily going towards a goal,

right, that's, that's all it's doing. And then, you know what, it encounters an

obstacle. So now, xo Sorry, x-xo is equal to delta.

So, I'm delta apart from it. And I have this directionality condition,

right? So, I'm going to check if this inner

product is positive. If it is, I should go clockwise.

Similarly I have a counterclockwise check.

So, if this condition is satisfied, I should go counterclockwise.

So now, I know when it's time for me to move either in a clockwise or

counterclockwise direction. Well, it's conceivable because the real

world isn't the same as the theoretical world that, as I'm sliding, I end up

closer to the obstacle that I wanted to be.

Let's say that the distance of the obstacle is now strictly less than delta,

then I shouldn't slide anymore. I should let my dedicated, custom-built

avoid obstacle behavior just make sure we don't slam, we don't slam into things.

So, you always wrap a pure avoid obstacle behavouir in there for safety reasons, in

order to guarantee that you don't hit things.

Remember that we're actually looking for both guarantees and a smooth ride.

And this is our way of having the cake and eating it, which very rarely works,

but in this case, you actually can do it. Okay, the one thing we need to remember

though is, we needed to know how close we were to the wall, or the obstacle at the

time we started following it. So, we had this thing that we said, let

tau be the time of the next switch. Well, I'm going to have something that I call d

sub tau, which is just the distance when I switch.

And I'm going to reset, remember we talked about resets, I'm going to reset d

sub tau to be the distance to the goal at the time I started to follow walls.

So, here are resets, right? Now, I'm going to stop sliding or stop following

walls, well I wrote it as one guard, because it's the same condition no matter

where we're coming from. And this condition says, we should have

had or made enough progress. So, this needs to happen and we need to

have a clear shot, which is this condition, okay?

Is it beginning to look a little a little messy to be honest, but regardless of

which, we are able to write it down and we know what all of these things are.

Now, this isn't quite work yet because right now, it's possible to avoid

obstacles forever so we need some way of stopping this thing and the way to stop

is, you know what, now this looks like a huge mess, right?

But this simply is the sliding condition for following walls in a clockwise

direction so it's the same condition as up here.

But now, since I'm running out of space, I have to write it right on top of the

arrow. I also need the same resets that I had

here so it's the same condition. And similarly, if, well, first of all,

this condition is satisfied, I do counterclockwise and I need to reset this

distance again. So, it's the same condition and the same

reset as before. so now, I basically have everything.

I just want to add one more thing and that's this.

If the distance to the actual goal is less than or equal to some epsilon, then

I'm done and then I'm going to stop. So, here is a rather messy looking hybrid

automaton, but it is quite glorious in its mess because it allows us to get

smooth performance, or guarantee the performance out while running in the

smooth way. And even though it looks hard, all of the things are inherently

computable and it's actually not that complicated.

So, what I'm going to do is I'm going to take this thing that looks messy, shrink

it down, and make it look even more messy, and say, this is our complete

navigation system. I think it is quite elegant, to be

completely honest. and now, its time to ask you know what,

its elegant, we've done some math, we know that it works, so this we think so,

does it really? And here is the unfortunate answer to the question, does

this work? Nope, it doesn't,

which is why you're now getting a little annoyed with me because I've spent all

this time developing this framework and now I'm claiming it doesn't work.

the reason it doesn't work as is is there are all these practical considerations to

take into account. And what I'm going to do in the next

lecture is actually, make it work so that it was worthwhile and we can take this

little messy-looking hybrid automaton and print it out and turn it into a badge

that we can put it on our clothes or wherever so we can be really proud of the

fact that it does work. but that is the topic of next lecture.

A Complete Navigation System

Control of Mobile Robots

Meet the Instructors