[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.
