0:00
In the last lecture, we saw that we have really two choices when it comes to
combining behaviors. We can either switch between them or we
can blend them. And what I want to do in this lecture is
really discuss a little bit further this issue of, of maybe not how we should
combine them but if we need to introduce something more than just our dynamic duel
of behaviors in order to deal with the navigation problem.
And as a hinted act at the end of last lecture, was the induced mode,
the sliding mode is somehow going to be important.
But what I want to do today is start by discussing different kinds of worlds or
environments. And I'm going to start simple with worlds
where everything is a point, the obstacles are all points.
And then, I'm going to start building up more and more complex scenarios to see
when do we actually need to introduce another mode or another behavior in order
to be able to act well in the world. So, I'm going to start with points then
I'm going to add a little bit of spatial dimension to these points so they're
going to be circular obstacles. Then, we're going to generalize that to
something called convex obstacles. we're going to make it harder than by
making them nonconvex. And finally, we're going to look at
labyrinths. So, basically the maze problem. If you're
a, if you're a rat, a lab rat trying to get to the cheese,
what kind of behaviors do you need to actually find, find the cheese? So, let's
start like this and what I'm going to do now is basically discuss the different
worlds at the rather high level by drawing cartoons of what's going on.
And then, in the next lectures, we're going to be a little bit more precise
about what's going on. But let's start with point worlds.
As always, blue means the robot, here's the robot.
Green means go and red means obstacle. And this little disk around the obstacle
is simply me saying, this is the distance when it's unsafe to, to travel towards
the obstacle and just switch, somehow, to avoiding obstacle.
Either with a hard switch or a bland and in this case, it really doesn't matter
too much which one we do. So, the robot, well, it's simply going to
start [SOUND] so here is go to goal. Start moving towards the goal and then
here, right? We're now hitting the, the bad region.
Well, we know that the obstacle avoidance is going to push us away like this
somehow so, you know, we do, we're going to do something like this and we got
away. Let's say, there's a little epsilon disk
around it. So, here's avoid obstacle and then, now,
we're going to switch back and start [SOUND] going towards the goal.
So, this seemed like a slam dunk, we did well somewhat at least.
so, maybe we can declare successful point worlds.
in fact, I want to show you another situation where I move the point a little
bit. Now, [SOUND] I'm going towards the goal and here,
go to goal, we want to move in this direction and avoid obstacle, you want to
move in exactly the same direction. So, what could potentially happen in this
set up is when you answer here, the robot just keeps oscillating back and forth and
it's never really finding a way around itself.
There is a really, really, really unlikely scenario that could happen if
you have this bilinear line up where everything is on the same line, where you
just end up switching back and forth without really making, making any
progress. Now, that is extremely unlikely when an
actual robot is out in the world. That ain't going to happen because the
world is always a little bit noisy, the sensors are always a little bit noisy and
even the slightest amount of noise is going to push you out, away from this
situation. So, the punch line, when we look at point
worlds, is these two behaviors seem to be enough unless we're super unlucky.
And I call this some kind of mild Zeno. basically you may end up trasitioning
back and forth with no progress but like I said.
in the real world, we're going to have noise, so points we don't really worry
too much about. Well, let's go up in complexity.
Let's look at circles. Well again, let me draw a cartoon on
what's going on. Now, the red dot is big but I'm going
towards the goal. [SOUND] Here, I'm going to start avoiding
the goal and then let's say here, I'm going to start maybe, maybe I end up
switching back and forth a couple times and then
save. So, circular obstacles here seem pretty
reasonable. it seems like our two behaviors are, are
basically doing the same thing. Now, if the circular obstacle was moved
down, again, so the center of mass of the obstacle was bilinear, on the same line
as the goal and the robot, the again, we would get stuck in this highly unlikely,
never-gonna-happen-in-real-life scenario. But basically, circular obstacles are
point obstacles, just larger. But philosophically, and complexity-wise,
we can deal with them. Now, the next level up in complexity is
convexity versus non-convexity. So, on the left here, you see what's
called a convex obstacle. It's basically a, it looks like a circle
or a disk that's being squished a little bit.
what makes it convex is that if I take any two points inside this obstacle and I
draw a line in between them, that line lays entirely inside the obstacles,
right? If I take the right obstacle, which is in
fact, not convex then, you know what, if I take two points, we'll find this line
lies entirely with in the obstacle. But if I take a point here and a point
there, then this line actually falls outside of the obstacle.
So, an obstacle or a set is convex if every line in between two points in the
set lies entirely inside that set itself. So, we're going to start with convex
obstacles as the first step up from circles or disks and then we're going to
look at non obstacles. So, I have a nonconvex obstacle, right?
It's not a circle anymore and what I have here is, well, now my red marker doesn't
show up, but any line I can draw here, of course, is entirely within this this
disk. So, let's see what's happening here.
the robot starts moving. [SOUND] A straight line.
And then here gets, let's say that they, they now want to starts avoiding the
obstacles so maybe avoid obstacle is going to push it there, it may be pushed
back. What's going to happen is there is a
point when avoid obstacle is going to point straight away from go to goal and
now and we've ended up in this situation that was super unlucky and unlikely when
we had a point. But in the convex with noncircular
obstacle situation, that situation is no longer super unlucky because we ended up
in it. Let me again point out what's happening
is that we're getting here, let's say, here is actually the point
where avoid obstacle wants to go in this direction,
go to goal wants to go in this direction and by switching, we're ending up there,
which is the unlucky point, but in this case, it's actually not unlucky.
So, these two behaviors themselves, no matter, no matter if we blend them or
switch between them, we actually get stuck.
7:13
So, we need someway of you know what, getting around the obstacle and somehow
we need to follow the boundary of this obstacle and not just switch back
absent-mindedly between going into goal and avoiding obstacles.
So, here is a situation where we clearly need to introduce another behavior in
order to be able to navigate this obstacle.
Well, if you have a nonconvex obstacle, this is known as a robotic flytrap.
what it is, it's, it's a nonconvex obstacle.
It's a cul-de-sac. And you know what, this robot is going to
get down here. First of all, it's going to get stuck
here right, right, because here, we have this go to goal and avoid obstacle
pointing in different directions but even if we were able to continue here, well,
now all of a sudden, we're going away from the obstacle and, no, sorry, from
the goal. Clearly, we need something more than just
go to goal and avoid obstacles to do this.
we need some clever way not only of following the boundary of this obstacle
but following it in such a way that we actually progress towards the goal
globally even though we're locally in the short run and getting further away.
So, nonconvex obstacles, it's even worse than convex obstacles.
Two, two behaviors certainly aren't going to work.
Well, what if you have a labyrinth? So this is, you know, you have a bunch of
different things. You may have something extra here.
You may have something here. You have a bunch of things.
And the robot needs to figure out that it's supposed to do this, right? Which.,
I mean, [SOUND] now I'm going to sound, try to
sound like I'm from New Jersey, forget about it. That was probably not so close
with my Swedish accent. But anyway, it ain't going to happen with
just two behaviors. Clearly, no way of dealing with that with
only avoid obstacle and go to goal so what we need is really at least one more
behavior that allows us to deal with worlds that aren't just circular
obstacles or point obstacles. That are, in fact, convex or nonconvex or
even, you know, labyrinths. We want to be able to solve this problem,
we want our robotic rat to get the, the cheese.
And that is going to be the topic of the next lecture.