0:00

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.

Â