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.