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