All language subtitles for 01_1-1-introduction-to-computational-motion-planning.en

[MUSIC]

Hi, my name is CJ Taylor.

I'm going to be your instructor for this
section on Computational Motion Planning.

I thought I'd begin by talking a little
bit about the kinds of problems you're

going to be solving in this module.

Motion planning is actually
a specialized version with

more general AI planning problem.

The goal of a general
purpose planning problem

is to come up with a sequence of
actions that accomplish a given goal.

Consider for example the problem that
we would be facing if we were trying to

design a robot that was
supposed to do our laundry.

We would love for that robot to be able
to come up with the entire sequence of

actions that needed to be
performed on it's own.

From finding laundry,
taking it downstairs,

putting it in the washing machine,
taking it out; folding it; etc., etc.

The Motion Planning Problem
is actually more specifically

concerned with coming up with plans to
move a robot from one location to another.

To get it from Point A to Point B.

In many cases, this boils down
to a kind of geometry problem.

Where the goal is to guide the robot
through a particular trajectory that

avoids all the obstacles that we
know about in the environment.

This basic approach can be applied
to a wide variety of robotic systems

including relatively simple robots that
roll around on the ground, to robotic

arms with multiple degrees of freedom, to
systems like these quadrotors shown here.

Let's begin our explanation
with a simple example, PacMan.

I'm betting that many of you've played
this game once or twice in your life.

And you remember that when your noble
PacMan eats one of those computer

generated ghosts, those ghosts would
automatically run back to their lair

to regenerate and then come back and
hunt you down again.

I was never very good at this time, so
the end always came quickly for me.

But I was always impressed by how quickly
and efficiently the computer was able to

guide the ghosts back from wherever
they got eaten to the goal.

So this is a problem that we're going
to consider in the next set of slides.

On this slide, we see a simple
depiction of a Pac-Man problem.

In this picture the robots are constrained
to move around on a grid of cells.

At any point in time,
our ghost can move north, south, east or

west to any adjacent cell.

The limitations are that it cannot
go outside the playing area or

enter any of the black grid cells.

These correspond to
obstacles in our world.

Our goal then is to come up with a
sequence of steps that will take the robot

from the starting location, the green
cell, to the goal location, the red cell.

Now, if we think each of
the unoccupied grid cells as a node,

and draw lines between
adjacent nodes as shown here,

we end up with a mathematical
structure called a graph.

A graph is composed of a set of nodes
typically denoted by the letter V and

a set of edges denoted by the letter E,
which link those nodes together.

Graphs are a mathematical contract
which are actually very useful for

modeling a wide variety of
maps in the real world.

For instance, this transit map can be
thought of as a graph where the nodes

corresponds to stations and

the edges correspond to rail
links between those stations.

Next figure shows a form of a mileage
chart where the nodes correspond to cities

and the edges correspond
to toll roads between them.

Here we may be interested
in finding a path

from one city to the other that minimizes
the amount of money that we have to pay.

The world wide web is
actually a form of a graph.

Where the nodes are web pages and
the edges are links between them.

In many situations,

we may choose to associate numbers
with the edges in the graph.

For example, in the Toll Chart example
that we were talking about previously,

we chose to associate numerical
values with each of those

edges which corresponded to
the tolls that we would have to pay.

We're going to be doing this quite a bit
in our various motion planning problems

where these edge-awaits,

we'll refer to costs or distances that
we might be interested in minimizing.

If we go back to our pacman problem,
we can implicitly associate

a unit distance or cost with each of the
edges between adjacent nodes in our graph.

Now that we've abstracted our
PacMan problem to a graph,

our problem is one of finding
a path from one node in the graph,

the start node to another node,
the end node.

In this setting a path is simply
a sequence of consecutive edges

that lead from one node to another.

Immediately, you'll notice that there
may be many different paths that would

solve this problem.

Often we are interested in finding
a path that minimizes some cost or

distance metric.

So, for instance, we may be interested in
finding the path from the start node to

the end node that uses
the minimum number of edges.