Lecture 1 : Introduction

Hello, and welcome to this course on Robot Motion Planning. This course will focus on the two aspects of path planning and motion planning. Path planning, as the name indicates, is basically finding a path from a initial point to a goal point, maybe avoiding obstacles. And after the path is found, then we have to find, then the robot has to actually traverse on the path. Okay. So the path could be the same for, for example, a mobile robot and a humanoid robot, a biped robot, but the actual motion plan could be different. So path planning is essentially finding the path from an initial point to a goal point and motion planning is traversing on the path or how are we controlling the various actuators that is actually taking the robot along the path from the initial point to the goal point. Now we'll briefly go through aspects of serial arms and mobile robots. We'll look at transformations. When we study robotics, we assign frames to all the joints, right? And then we try and find the relation between the frames. So when the robot is moving in space, we can find the relation between the moving frame and a fixed frame. So we have to study the, the area of transformations. That is when you're transforming the position orientation from one frame to another frame, what are the various matrices involved? Then we look at homogeneous transformation matrices. Then we'll start off by looking at serial arms and then we'll move on to mobile robots. Now the path planning is basically done in configuration space. It is not done in the Cartesian space. Cartesian space means the X, Y, Z that you are familiar with, whereas the actual planning is done in C space and we will look at what is C space, how to go from Cartesian space to C space and then what is the topology of C space because we need to understand the topology of C space so that we understand that when you're moving in between spaces, when can you move and when you, when you cannot move in between spaces, okay? The various methods that are there for path planning, for example, given a set of obstacles, how can you find a path from one point to another point without hitting the obstacles? There are several methods now which are there, which we'll look at. Then we'll look at planning with kinematic constraints. Sometimes your, your robot might be subjected to kinematic constraints. For example, a car, the car, normal car that you are familiar with that goes on the roads, okay? The car cannot go sideways, right? It can go straight, it can turn at a particular angle, but it cannot go sideways. So if there are kinematic constraints on a car, for example, there are velocity constraints that the robot cannot go sideways, then the algorithms have to be tuned or they're a little bit different, okay? Then we'll look at applications of multi-agent systems, swarm robotics, optimization in robotics. We'll also look at robotic grasping or multi-fingered manipulation and that also comes under motion planning. Now, the way the course has been designed is that we have eight weeks of classes in which we have about two and a half hours of lecture every week and there will be one assignment. And for your doubts, there is, you can send me your questions and things which are not clear by Gmail and I'll be answering to most of your queries, okay? So as we complete the theory also, I will try and go in for, I will try and have a practice session where we can solve problems and then it becomes more clear. Things like transformations. It's very, very important that you understand transformations correctly in order to be able to do forward kinematics, inverse kinematics that is required for path planning, okay? So with this background, I will start the course. So I'll just switch off the camera. So we are looking at the topic of robot motion planning and my name is Ashish Dutta and I'm a professor in the Department of Mechanical Engineering at IIT Kanpur. Now it's very interesting question. The first question that is put up here is that when you first think about a robot, what comes to your mind? This is the course on robot motion planning. So the first thing we need to talk about is what is a robot in the first place, right? So it's very interesting that when you first hear the word robot, what comes to your mind? For some people, when they think about a robot, what comes to their mind is that a robot is an industrial machine for doing tasks in industries. For example, in automobile industries, it does spot welding and spray painting. For the younger or younger friends or younger kids basically, a robot can be a pet, it can be a toy, it can also be companions, friends. And in advanced countries, a robot also helps in the homes and they can be helpers, service robots are there today or with lot of movies and on TVs, you see robots which are actually going into warfare. So there can also be dangerous machines, okay? Now it's very interesting that when you ask somebody what he or she thinks of a robot, they would normally say one of this or maybe more than one of this. But it's very interesting that they will at least have something or it is not that they would have never heard about a robot, okay? So this also shows how robots have permeated into society and this is true not only for cities and towns but also in villages. If you ask a person in a village if they have ever heard about a robot, I am sure that you will get some answer, okay? It's not like they have never heard about it. So depending on your educational background, depending on where you are from, depending on how much of movies you see, you will basically have some idea of, something will come to your mind. For example, here we have an industrial robot which is doing spot welding or spray painting, okay? Now there is, here is a service robot or this is a teacher robot which is used in teaching kids in kindergartens. Then we have pet robots that are shown here, okay? And also there are robots which are, where we try and emulate human behavior. We try and understand human behavior, why we do things in a particular way. For example, when you are wiping this table as shown here, okay, human beings wipe in a particular way. Now if the robot has to behave like a human, then the robot also must emulate or try and copy human motions. Why that's important? Because a lot of robots are living in society today, okay? So these are called social robots and they are expected to behave like humans. So please think about what comes to your mind when you first hear the word robot. Now those of you who have been into robotics clubs in your schools or colleges, there are a lot of this mobile robots which are being sold today, okay? So robotics clubs, normally students make this kind of mobile robots and you can also buy them off in malls, various mall sells different kinds of toy robots. Now because of the, the lowering of cost of electronic components, okay, it is very easy and very cheap to make this kind of mobile robots. Say for example, a microcontroller like this, Arduino microcontroller would be very cheap about 500, 600 rupees and you can do very good programming using this kind of robot or this kind of microcontrollers. Again sensors like ultrasonic sensors here, DC motors, they are very cheap these days. So robotics has also become very, very popular in school, in schools and colleges as a mode of learning programming, as a mode of learning sensors, actuators, controllers, okay? And it helps students develop various aspects of ability to write good programs, ability to connect a physical hardware with a program and things like that, okay? We are talking about robotics and robot motion planning. So a robot basically or robotics, the subject of robotics consists of mechanical systems that have sensing, actuation and computational capabilities and can perform different tasks. So it can be a group of robots, it can be one robot, individual robot, okay? Now, mobile robots avoiding obstacles, robotic arms doing welding, UAVs taking photos, unmanned aerial vehicles, they are all under the area of robotics, okay? So robotics today is not only a multifunctional manipulator or industrial robotic arm but you have all kinds of devices which are called robots, okay? Like from flying, underwater, then in industries, okay? There can also be software which is not really a physical robot but that is also called a bot, okay? There can also be, for example, we have chat bots today. Now in the area of robotics, today the most significant present challenges in autonomous robotics lies in automatic motion planning. Now these are some terms I am using, I will go, I will explain them as we go along, okay? So the biggest challenge in robotics today is that robots are supposed to be autonomous. Now what is autonomous? Autonomous means that they should operate by themselves with minimum human intervention, okay? So if that be the case and the robot has to move around, then it should be able to automatically generate its own motion, okay? So this is probably the biggest challenge in the area of robotics today, autonomous motion planning or automatic motion planning. Now the goal of automatic motion planning is to have algorithms, okay, that can convert high level specifications of tasks from humans into low level descriptions of how to move. What does this mean? Algorithms are programs. Now the input to that program could be task specifications from humans. For example, if you say we have a mobile robot here and this mobile robot is placed inside a room. Say for example, I have a room and there are tables and maybe there are chairs put somewhere, okay? And the robot is here. I want it to go from this point to this point, point A to point B, okay? So for example, the human can tell the robot that go from point A to point B, it knows what is point A and point B, avoiding obstacles. So the robot should automatically be able to generate its path. That means it should be able to generate a path like that and then follow the path. This very simply is what we mean by it should be able to convert high level specifications from humans into low level descriptions of how to move, okay? So the whole objective of robot motion planning is to be able to design algorithms that can enable a robot to automatically generate a path or to satisfy some desired task and to go on the path or do the task by itself. So this is what we mean by automatic motion planning. Now the simplest case is this one, the simplest case of path planning. Now this figure shows you an obstacle which is shown like a triangle, which is shown here. So this is an obstacle and this is a circular mobile robot, okay? Now the circular mobile robot can have two wheels on the sides like this. Let us say it has two wheels and there is a castor wheel in front, it is a differential drive robot, okay? Now this robot is required to go from the start point to the goal point, that is the task. So the simplest case of path planning would be find a path that will take you from the start point to the goal point without hitting the obstacle, okay? Now in terms of English it is very clear. Now for us it is very easy to say, for us it is extremely easy to just look at the picture and see. Why? Because we have eyes, okay? So I can see where is the obstacle, I can see where is the start, where is the goal. Now this poor robot does not have eyes and there is no vision data, okay? So at most it has geometrical input data which will say this is the start point, what is my x, y coordinates, this is my x coordinate, that is my y coordinate and in this x, y my start point is having some x, y coordinate, some position and the goal is having some x dashed, y dashed position. So and the object has vertices which are given by these, let us say these are the vertices which are input. So the input to the program would be this geometrical data, start point is here, end point is there. The radius of the robot is also required, say r, okay? And the obstacle vertices are given here, let us say v1, v2, v3, v4 and the program or the algorithm should automatically be able to find out a path that will take the robot from the start point to the goal point. Now as I was saying that we have eyes, so for us it is very easy, just look and you know that wherever is the free space you can simply take a path in the free space and go from the start to the goal, okay? Now there are some interesting questions here that if you look at this, how many paths are there? You can go like this, you can go like this, okay? You can go like this, can you go like this, can you go from that side, okay? So if there are large number of paths, the first question we need to ask is whether there is a path or no path, that is the first question. If there is no path, the algorithm should also be able to tell you that there is no path. Now if there is a path, then which is the shortest path for example, okay? So the simplest case of path planning is as shown in this figure that the mobile robot which is circular has two drives, two drive wheels, it has to go from the start point to the goal point, okay? So what are the paths? Now once you have found a path, for example, we have found a path that this is the path, next the robot will have to go on the path, so it will have to traverse the path, so the robot has to follow the path like this, like this, like this, like this, like this and then go to the goal point, okay? Now to traverse on the path or to go on the path what it has to do, it has the wheel velocities omega 1, omega 2 there, so it has to use differential wheel velocities and steer the robot to take it along the path to the goal point, okay? So finding the path is basically what we call path planning, that is you are finding a path from an initial point to a goal point without hitting an obstacle. Now once you have found the path, the next thing that comes into picture is the motion planning, that is now I want to move the robot along the path and take it to the goal point. Now to move the robot along the path what I should do? I should, we should actuate the wheels suitably giving suitable velocities so that it will follow the path and that is basically what is called motion planning. So these are actually two different things, path planning and motion planning. Path planning is to find the path and motion planning is basically to go along the path by actuating the actuators. So this is basically gives us the simplest case of path planning and it also explains the concept of motion planning. Now historically the study of motion planning started off with the piano movers problem. So this is a piano, the black one, you are all familiar with what a piano looks like. So the black one here is a piano, right, so that is a piano. Now the piano is kept in a room which has four legs, okay, it is kept in a room. Now you want to move this piano from one room to another room, okay, the piano has to be moved from one room to another room without hitting obstacles. This the left side is shown, the top is showing the side view, isometric view, so this can be looked upon as an isometric view and this is a top view. So now the motion planning problem essentially considers what are the various motions that have to be imparted. First of all, you need to find a path that will take the piano from one room to another room without hitting the obstacles. Now this piano is a free flying object which basically means that it can rotate and translate in any direction, okay. And once you have found the path, then you have to move the piano along the path and take it to the other room. The motion of the piano may be given by means of this mobile robots which are carrying the piano. So this black ones here are called mobile robots which are lifting the piano and can take it there. So this is basically giving us the idea of or historically where motion planning started from. So what are the definitions of a path and a motion plan? So path plan is essentially, it gives a continuous path, okay, it has to be continuous from initial point to goal point. The path plan for a mobile robot and a humanoid robot could be the same, as I said that a mobile robot and a biped robot could have the same path but their motion plan could be different. So it gives a continuous path or function, so it has to be continuous, it cannot be discontinuous, okay. So it gives a continuous path from the initial point to the goal point. The motion plan, it gives the actuator or the joint trajectory to traverse the path. That means you have to control the joint actuators in order to move the robot along the path. For a humanoid robot, it will have many degrees of freedom, say the motion of the legs and the hands, they have to be actuated to move the robot along the path. That is the motion plan, whereas the actual path is the path plan, okay. So motion planning gives the joint or actuator trajectory to traverse the path and hence the motion plan of a mobile robot and a humanoid robot could be very different. Now what is the trajectory? Trajectory is a time history of position, velocity and acceleration, okay. So when you are actuating the joints, it will have a particular trajectory. So the joints, for example, if I have a serial robot, let us take the example of a serial robot here. This is my serial robot, 2 degrees of freedom, theta 1 and theta 2. Suppose I want to go from this point where it is now to another point. Let me use a different color and take it to some other point, it has gone to that point now, okay. That means theta 1 has gone this much and theta 2 also has moved by some angle, okay. So that means when the theta 1 moves, you should, the joint trajectory should have theta 1, theta 1 dot and theta 1 double dot. So position, velocity, acceleration are all required and that with respect to time and that is what we call as a trajectory. So when the robot is moving, it is a time history of the position, velocity and acceleration. This is what we mean by a trajectory. So I have used three terms and I hope they are clear. One is a path plan, number two is a motion plan and number three is a trajectory. Now at the simplest level, a mobile robot avoiding obstacles is as I just explained and as shown in this figure, we have a start point and we have a goal point and the robot has to go from the start to the goal. The robot has two mobile, it has two wheels, which is driven by motors, there is a caster wheel in front, okay. So the whole objective of this path planning is to find out a path, could be the least energy path, could be the shortest path, okay, which will take the robot from here to here without hitting this obstacle which is shown here. So this is my obstacle, okay. So this is my obstacle. Now again, we have eyes, so you can very easily see and say, okay, it goes from here to here. But a computer does not have eyes, a computer is a program. So you need to write a program which will actually give you the output as a path. What is the input to the program? The input to the program is the start point, means coordinates, the goal point coordinates, what is the vertices of this obstacle and then the program should be able to figure out that it will go, how it will go from the start point to the goal point without hitting the obstacle, okay. So a path exists, it should be able to give the path. If there is no path, it should be able to say that there is no path. Now let us ask, just for asking sake, let us say that suppose I want to find out if this path is possible, okay, is this path possible? Now this is the boundary of the workspace, so the robot cannot go outside that, okay. So this end of the white, this white part, that is a boundary. So the robot cannot go and hit that, it cannot go this side, okay. So simply by looking at this object, at this picture, it is actually not very easy to say, can this robot go here? It cannot because this side is coming outside the work area, so it cannot go, okay. Again, I have eyes, so it is very easy to see and say. But suppose the robot does not have eyes, how will the program figure out whether the robot can go or the robot cannot go in this area? So what we do the planning, the path planning, we do not do it in Cartesian space. This is my Cartesian space, okay, this is x, y, I am talking in terms of, so we have a coordinate system, this is my coordinate system x and this is my coordinate system y. And in this, we are giving coordinates of a point by x and y, that is my Cartesian space. So path planning is not done in Cartesian space, but it is done in configuration space, okay. As we go along, we will see why. Because answering questions like this, can the robot go here, okay, becomes difficult actually at times, okay. For example, if the robot is just fitting there, is that okay or is it not okay? How would you say, okay? So to look at all this, we normally go to configuration space. So we have got a path, this is my path and when the robot is traversing on that, that is my motion. So the motion plan will be, motion plan, if there are two motors, omega 1 and omega 2, okay, then these are the two motors that will be actuated, okay. So the motor velocities will have to be controlled to take the robot along that path and that is basically my motion plan. I just said that a path plan and a motion plan are different, okay, or a path plan for a biped robot and a humanoid and a mobile robot could be same, but the motion plan would be very different. Now what that means is, for example, this is a path, okay. Now if this path were to be traversed by a humanoid biped robot, then the motion control of that, of the joints of the humanoid robot would be very different. That is easy to understand, right? Suppose this mobile robot only has two motors here, so there is one motor here, one motor here, it has two wheels only, whereas a biped robot like this could have very large number of motors. When this robot is walking or a mobile robot is going on this terrain, what can happen? The path can be something like that, I have found the path. But in order to go on the path, the motion planning would be very different. For a mobile robot, it is just controlling the wheel motors, for a humanoid robot, it is controlling all the joints, okay, and there are very large number of joints here. So let us have a look at this video and you can see that there are very large number of joints and it has all kinds of additional problems like balancing, it can tend to fall down, okay. So it is not a very easy problem. So here the robot is avoiding obstacles and going from one point to another point, it is having a path and it is also having a motion plan. So this is what we mean by saying that the paths of a mobile robot and a biped robot could be same, but the motion plan could be different, okay. Now, we also have more interesting problems, for example, non-holonomic systems, we talked about a car, a car cannot go sideways as shown here, in this figure on the side, on the left side. So you have a car and you want to park this car in this area, so this is the area for example. Now this car has two wheels, it has drive at the back and it has the steering in the front, okay, that we know. So the wheel can go, the rear wheels can rotate front or back, it can go forward or backward and there is a steering in the front by which you can steer the car. Now this car cannot go sideways, you know that, right, and this is basically called non-holonomic systems. Now if you look at this picture and we are trying to figure out if the robot, if this car, let us say it is an autonomous car, can it go and park in the green area, okay, it is not very easy to say, okay. And if it can park, then what are the various motion, in one shot it cannot go. So it will probably have to do some kind of maneuvers in order to be able to, for example it comes like this, then it goes like this, then like this, like this, it does all kinds of maneuvers and then maybe it is able to go and park there, okay. Now look at another problem here, the right side, this is called the tractor-trailer problem, tractor and trailer problem. You would have seen these tractors and trailers on the highways in India, okay, or overseas. So even large trucks are like this, these larger trucks which carry containers. So they are actuated by the engine which is in front and these wheels which are there at the back, these are passive wheels basically, there is no actuation there and there is a revolute joint, so it can rotate about this. So this is also called the tractor-trailer problem, okay. So it is like a tractor in front which is pulling a trailer at the back. The trailer is not actuated, okay, and the actuation is only on the tractor and the tractor can pull it forward or it can rotate, okay, but based on that because there is no actuation on the trailer, the trailer can freely move about this joint only. So in such situations, can you go and park the trailer here, suppose I say I want to park the tractor-trailer here, is that possible, okay, how can you say, okay, and if it is possible, what are the various motions, okay, interesting problem again. This is not very easy. So what I am trying to say is that if you look at this problem, this problem, it appears that the problem is very easy, that you have a mobile robot, it has to go from one point to another point without hitting obstacles. So what is so great about it, okay, you have to write a program, okay, but then you just find out the intersection between this circle and this object, if it is intersecting means it is hitting, if it is not intersecting means it is free, so it is not a very difficult problem to solve geometrically. But the moment I come here, this is not a very easy problem, why, because you can find a path which will take you from one point to another point, but walking on the path itself could add, could be difficult. For example, there are very large number of degrees of freedom, okay, you might have to activate the hands, legs, body, torso, neck, head, everything, plus there is a chance of falling down, okay, so you have to talk about stability. So this is a difficult problem, this is a simpler problem and this is also a difficult problem, it is not a very simple problem, because you need, the program needs to figure out what are the various motions that have to be executed in order to be able for the car to go and park sideways or for this tractor to go and park there, okay. And this is a non-holonomic system or we call it motion planning with kinematic constraints, when there are kinematic constraints, we will come to this towards the end of the course. This is what is a very interesting problem here, suppose this car has to go and park here, the blue car has to go and park at the red one, okay. So what are the various motions that are required to enable the blue car to go and, to go and park on the red car, again it is a trailer, the back one is a trailer, you can see it is not actuated, it can only rotate and can be pulled. So, this is not a very easy problem and we have to solve it geometrically and a program has to solve it, it has to tell how many paths are there, if a path is there and out of those paths which path will be the least energy or will be the, or will take the shortest distance. So, these are some examples of path planning problem that we talked about. So a path planning problem involves some planning, if you want to go from here to here, let us come back to this one again, I want to go from the start point to the goal point, there has to be some plan. What is the plan? For example, I want to go from here to here, there has to be some plan, the program must be able to execute some plan. What is the kind of plan? For example, the robot should go in this direction, it should go towards the goal, it can turn at a particular angle, okay. So, there has to be a plan which will say that the robot should go to the goal and to reach the goal, it should move towards the goal, okay and if it is moving towards the goal, it should be able to turn left or right and it should avoid this obstacle, avoid hitting that one. So, if the robot comes very close here, it should not, it should not go and try and touch the obstacle or it should not go and hit the obstacle. So, the plan should ensure that the robot moves towards the goal, okay, it should not hit the obstacle and it should move forward and simply turn left or right, okay, so that is a plan now. So, the program is actually a plan in a way. So, what is a plan is the first thing that we need to see. So, this program must be having a plan, how to get you from one point to another point. Next is how is the plan represented, okay. Now, it is going to be represented as a computer program. So, robot motion planning or path planning is basically writing computer programs in which the input is going to be the geometrical data and the output is going to be the plan, if there is a plan. How is it computed? There would be some computation involved, okay. What is this supposed to achieve? How is quality being evaluated? For example, what is this supposed to achieve? This plan is supposed to achieve that the mobile robot will go and reach the goal satisfactorily or safely without hitting the obstacle. How is quality evaluated? For example, quality can be evaluated by means of the length of the path, length of path. If the path length is very high, we can say it is a bad quality. If the path length is low, we can say it is good quality, okay. Energy can be another one. So, if it takes too much energy, it is a bad, it is a bad plan. If it takes less energy, it is a good plan. Who or what is going to use it is the other aspect of plan. So, a plan actually involves all these aspects. What is a plan? How is the plan represented? How is it computed? What is it supposed to achieve? How is its quality being evaluated? And who or what is going to use it? Now, a plan proposes a specific strategy or behavior on a decision maker, okay. So, a plan may simply specify a sequence of actions to be taken. However, it could be more complicated. So, by definition of a plan, we mean it basically imposes a specific strategy or behavior on a decision maker. What is the strategy? Go towards the goal, move towards the goal, do not hit, do not hit the obstacle or it may simply specify a sequence of actions. The main focus is on designing algorithms that generate more useful motions by processing complicated geometric information of the robot environment. So, the main focus is on designing algorithms, this is what I said. So, motion planning and path planning is basically designing algorithms that generate useful motions by processing complicated geometric models, okay. For example, what kind of geometric models? For example, the shape of the robot, the shape of the objects, what is the shape of the workspace? What is the geometrical information that is there? And the algorithm will process this information and give you a path. So, the algorithm would take geometrical models as input and give a plan as output. In case there is no plan, if there is no path is possible, then it should indicate that. There should be path, if there is no path, in case no path is possible, then it should indicate so. Okay. So, now you understand that what is this plan, what does it do? So, this is basically path plan, okay. Now, problem solving is the area where they look at in terms of artificial intelligence more in computer science, okay. In computer science also they use this word planning, okay, path planning. So, in artificial intelligence, the term planning and AI planning takes on a more discrete flavor of problem solving by an algorithm. So, this is also planning for solving a problem by an algorithm, this is also an algorithm, but it has a more discrete flavor, okay, unlike in the robot motion planning case, okay. So, problem solving and motion planning are different. So, when we say problem solving or planning in AI, basically it is also an algorithm, but it has a little bit more discrete flavor. For example, in Rubik's cube, okay, you can move only by discrete, discrete steps, right, all the blue colors and they have to be aligned or on the right side you have to match the numbers. So, these are discrete steps in which you can move or discrete states, okay. So, that is what I mean by a more discrete flavor, okay. This is basically solving this problem of putting all the numbers in a proper order by moving them, moving the squares one at a time. So, it has a more discrete flavor. Whereas, the robot motion planning problem is more continuous. We said that we need to find a continuous path that will take me from here to here without hitting the obstacle. So, they are fundamentally different when we say problem solving in AI and path planning, they are a little bit different. So, what is motion planning or path planning? It is determining where to go without hitting obstacles. So, as shown here, human beings when you want to go to some place, you look at markers or in the map. You look at Google map these days, the Google map will tell you go like this, like this to reach this place or there can be markers on roads, okay. The name of the road could be written here and it is pointing in that direction, name of the road is or name of a place is written in there, it is pointing on that direction. So, these are markers by which you can go from one place to another place without hitting obstacles. For example, this rat has to go from here to there without hitting obstacles. So, it can go something like this, okay. This is fundamentally what is motion planning and, and path planning. Now, in order to do path planning at the simplest level, segregate the world into obstacles and free space. What are obstacles? They are occupied spaces of the world. In other words, the robot cannot go there, it is very simple. So, here I have a workspace, I am just drawing, there is a mobile robot here and there is, there is a obstacle here, it is a triangle. I want to go from this point to that point, okay. Now, what we do is basically we define free space, okay. Free space is this area, this is free, the robot can go there. This is obstacle space and this is my obstacle space. Obviously, the robot cannot go inside the obstacle. So, we are dividing the, the world into obstacles and free space and then I am finding a path in the free space, okay. So, I have divided my, the environment into free space and obstacle space and then I find a path. What are the applications and the, and the places where path planning is required? Now, in the first course that is introduction to robotics, those of you who have taken the first course, it is basically looking at transformation, doing forward kinematics, inverse kinematics. But when you want to use a robot in the real world, mobile robot or serial arm, then we have to do path planning and motion planning, okay. And hence, all applications of robotics have to do some kind of, must have some kind of path plan or motion plan to take it from one point to another point or to do a task from to a, for example, pick up an object and place it at some other location. All applications of robotics involve path planning and motion planning. Examples of applications, manufacturing, robot programming, robot placement, design of part feeders, design for manufacturing and servicing, design of pipe layout, cable harness, autonomous mobile robot, planetary exploration, okay. Now, it is not only limited to manufacturing and engineering and industry, also things like digital actors, animations, movies, they all have to do some kind of motion planning. As I go along, I will be giving examples, okay. Then virtual walkthroughs in buildings, medical surgery, generation of molecular motion in biology, okay, then building verification code, this all require motion planning. Let us look at them in little bit more detail, so it will become clear what are the applications of motion planning. At the simplest level, it is this, a mobile robot, maybe it can be one mobile robot, can be two mobile robots, it has to go from, maybe these are obstacles, it has to avoid this obstacle, this is a mobile robot, it has to avoid all these obstacles and go like this and come here. So motion planning of a mobile robot, avoiding obstacles. This is flat ground, so this is my free space, this is obstacle space, so it is very, it is not a very difficult problem. What is the plan here? The plan would be, the robot can move towards the goal, if this is my goal, the robot can try and move towards the goal, whenever it is coming near an obstacle, it can avoid the obstacle like this, like this and go here, okay. So this path will probably be the shortest path. Next motion planning for robotic arm, for example, in automobile industries, all the spot weldings that are done on cars, okay, on the automobiles, cars, trucks, all this, the spot welding is done by robots. So this robot has to go inside the car and do spot welding, for example, if there is a weld here, then the robot will have to go like this, like this, go inside and then go to the weld. So this is not a very simple kind of space, where we can say that this is my free space and that is occupied space, because this is a serial arm and the arm can go in different places, the arm must not hit the vehicle. And you can see on the figure on the right, so this may, this kind of a plan could be pretty complicated, it may not be a very easy plan, okay. Even when we can visualize, it does not look like it is very easy. So for example, should the robot go in from this window, should it go in from this window, when it goes inside, it should not hit any part, it should not get stuck. Even when you can visually see it, even then it is a difficult problem, okay. So this is a challenging problem in robotic spot welding, robotic spot welding, okay, for a serial arm. This is a case of map building, for example, exploration, a mobile robot like this, which has ultrasonic sensors in front, so these ultrasonic sensors, which can sense the distance and this is a LIDAR, so it is a line laser. So when it is going along, it can, it can, this one, this one can rotate about this axis by 360 degrees, okay. So when it is traversing, it can see where are the walls and as it is moving, it can build its map. So for example, map building inside a, inside a, inside a building, okay. So suppose the robot has been kept here and the robot does not know the map of the building, okay. So it has to build the map as it is going and it has to go from this point to this point. So as it is traversing, it can check the sides, if there is any, wherever there is an obstacle and as it is going, it can build the map and finally go from this point to this point finding a free path, go here, go here and go there, okay. So this is not only finding a free path, it is also generating a map of the building. Next is non-holonomic we have seen, under activated and non-holonomic systems. As we go along, we will come to this in more detail, okay. For example, this is a free link manipulator, this is a three degree of freedom arm. Now this arm has to go from this side, so this is my fixed base, okay, this is my fixed base, let us say it is fixed. So this arm has to go from this configuration to this configuration, how will it go? So this is not a very simple problem, it is a challenging problem for an arm robot having three degrees of freedom, okay. So now in those three degrees of freedom, there might also be joints which are not actuated, they are under actuated systems. Now that becomes an even more challenging problem. For example, I have a three degree of freedom system like this, so there is one degree of freedom here, two here, three here. Now suppose there is no actuator on joint number three, no motor is there, it is free. If you are wondering how it will move, simply by moving this, because of the dynamics I can move that one, okay. If I start swinging this, what will happen is theta, it will have angular velocity, angular acceleration, okay. So this angular velocity, angular acceleration will travel in the forward direction. So although this, there is no actuator, link three does not have an actuator, it will still have some angular velocity acceleration because of the acceleration coming from the previous link, okay. So by moving the previous joint, I can still make this fellow go from this side to this side, okay. These are called under actuated systems. Assembly, so in assembly when you are putting different parts together, you are assembling different parts, so there has to be some sequence and that sequence is basically what we call by assembly planning. So when you are assembling a product like this, they will have some particular sequence. First the red part goes, then the black, then the maroon part in that order. So that order is also a plan and it is basically a motion plan because these things are being moved and assembled together. Cable harness, pipe harness, okay. So when you are putting wiring on a building, what is the lines through which the wire is going to go? That is wiring, wire harness, piping, pipe design, when piping is going into a building or into your houses, okay, they must follow particular routes, right. So that is basically what is required. So this is the path of the pipe, okay and this is very, very important because it should not interfere with other equipment and it should not interfere with one another, the length should be less and all that, okay. So pipe design, cable harness, wiring, all of this requires path planning. Motion planning for humanoid robot with many degrees of freedom in real world, for example this is showing a biped robot, a humanoid robot having two legs, then it has a body, it has a torso, it has a head. Suppose it has to bend down and pick up a part from under the table. So because it has many degrees of freedom, this could probably have 50 degrees of freedom. We will come to what is degrees of freedom and things like that as we go along. So what should be the way by which this robot should actually sit down and pick up the part? How many ways are there? There could be infinite ways, okay. The robot may be able to pick up the part without sitting down, just by bending down, okay. The robot may be able to even just bend at the hip and then pick up the part. So these are all questions that come up. If there is a path, how many paths are there? And after you get the path, what is the motion plan? This is what I was talking about digital actors, okay. Now these are cartoons, movies, I am sure you have seen this, even there are computer games and nowadays it is all over in terms of games, movies, cartoons, TVs, movies, it is all there, okay. Now when you observe these cartoons, they also behave like humans. I talked about behavior sometime back. So you can see that these cartoons also behave like humans. So for example, this is probably toy story, okay. So when this gentleman walks or when this character walks, it has to walk like a human being. Similarly, when the, when the person is, when this character is pointing the hand or is trying to walk, it should not go through the other person, okay. Because in the real world, the hand does not go through a solid object, right. So that is what I mean by it has to be realistic and it must behave like the real world, okay. So this is, I think is Ant's story. Then when you see these cartoons walking around, moving, doing tasks, talking, it is almost human being like, okay. So they have to behave naturally and this is what requires a lot of path planning and motion planning. Motion planning for digital actors, for example, if this person has to walk from here and go there, okay, so you have to find a path and these are called digital actors, the person has to walk from this point and go to that point and do a particular task. For example, for example, open the door. So this is a digital actor which has a path plan and also it requires a motion plan. For example, the one shown on the left hand side here, it is basically a person trying to wear say dark glasses. What are the various motions that the person would do to wear these dark glasses? This is a digital actor. Digital actor means it is not real, it is, it is simulation or virtual reality, okay. So the person is going to pick up the sunglasses, orient it properly and then wear it, as you can see on the last slide there. So all this sequence is a path plan. Navigation through virtual environments. So before building a building, before actually constructing a building, they would actually make this kind of virtual walkthroughs to see whether human beings can walk everywhere, if there is a problem of falling down somewhere, every place is accessible or there are some places which are not accessible, okay. So this is basically which is called virtual environments or virtual walkthroughs. Playing games, okay, learning skills. So playing involves hitting in a particular sequence. For example, when you are playing tennis or badminton, you are moving the racket in a particular fashion, okay, and that is basically a path. So this is basically called path planning or learning from playing or game, playing skills, okay, learning, game playing skills by learning the path in which human beings do a particular task. This is again learning from human behavior, for example, wiping, wiping the table using a sponge, okay, how would a human do it? Now the robot has to copy the human and do exactly like that, okay. So it has to, if it is wiping this, it has to have a path like this, like this, like this, like this, like this, like this and then like this on the table, okay. On the right hand side, this is a human being handing over a bottle to a robot. Now the robot should be able to take the bottle like a human being only. This requires path planning like a human. Building code verification, this is very important these days, in which after a building is made, the building should be accessible to people using wheelchairs, for example, okay. So before you actually do the construction of the building, they have to check it in virtual reality that wheelchairs can be moved in all places. Surgical planning, what is surgical planning? Surgical planning is, for example, in radiosurgery. Suppose there is a, on the right side figure, this is a, is the CT scan or MRI image of the brain. Suppose there is a tumor there and the tumor has to be operated on, then the tumor can be accessed in different directions. It can go this way, this way, this way. The surgeon's knife can move in different directions, right, or can approach the tumor from different directions. Now which will be the direction in which the least amount of damage will be caused to the brain cells? That also basically is what we basically call by, what we call is a topic of path planning. The other is radiotherapy. So in radiotherapy, they have to, they have to give therapy or they have to irradiate this tumor in order to kill the tumor, for example, cancerous tumor is there. So what is done is the therapy has to be given in a particular direction, so that least damage is done and it is focused onto the, the critical tissue or the tumor only. So in that case, they have to figure out from which direction to go, which is again getting a path. Study of motion planning in biomolecules. So the biological molecules or the cells in our body also, they move in a particular way, okay, the proteins move in a particular way and the motion of the proteins are basically what they study in terms of motion of biomolecules, okay, like proteins and what is basically called protein folding is one of them. Also in case of drug delivery, so drug delivery, when you take a medicine, this medicine moves through your body and moving through your body basically means it has a path and then it goes to the area where it is supposed to go. So is it going correctly, is it not going correctly? These things are studied in terms of drug delivery, biomolecules, protein folding, etcetera. Now is this problem easy, this problem of motion planning and path planning? If you just look at a mobile robot, avoid obstacle, go from here to there, it is not very difficult, but as you go up, you, you tend to see that it is becoming more and more difficult. For example, look at these two rings, the red one and the brown one or the red one and the yellow one, they are entwined, okay. Can you remove the red ring and the brown ring without bending them, okay? So this is, can you disassemble them, can you disassemble this, can you remove, remove the red and yellow one without bending, can you do that? Now if you just look at this figure on the left hand side, it is very difficult actually to say, even if you have eyes and you have all the intelligence and all that, but even then it is extremely difficult to say what is the sequence of motion or what is the path by which you will be able to remove the yellow one and the red ring without bending either of them. First of all, is it possible and if it is possible, then what are the paths and if it is possible, then how many paths are there? So simply by looking at this figure, it is actually very difficult to say, whether it is possible or not. Whereas if you look at this figure, this is actually showing that it is possible and what is the sequence of motions. So it is showing the path by which the yellow, the yellow wire has to be rotated and translated so as to disassemble both of these two parts, okay? So this is what I mean by path planning is not very easy, okay? So there are cases where it is extremely difficult and this is the example of robotic arm path planning. So this is a robotic arm, it has to go and go inside there. Let us say the robotic arm has to go and position itself such that the gripper is inside there, okay? So what are the different paths that it can follow, it has to follow? So obviously there will be many paths, okay? And then once it has done, got the path, there should be a motion plan which will activate the joints. So let us look at the, the motion plan. So there is a program which is running, which is actually doing the kinematics of this robot and then trying to move the end effector or the gripper into that hole there, into that T kind of a section, not T, it is inverted U kind of section. So you can see that the program is basically moving the joints such that it can take the end effector or the gripper and put it inside that, put it into that U section. So the way, the path that was being followed by the end effector is the path plan. At the joint, the actuation that was going on, that is the motion plan. So you can see that it is going into the hole there, okay? And the path that it followed is basically what we call the path plan. So it came like this and then it went in there, okay? So that is basically what is the path plan, robot arm path planning. Now finding a path from a start point to a goal point, let us have a look at this one. This is a biped robot. So this is a biped robot or a humanoid robot which has two legs, arms, body. Now the path of the feet, let us just, is given on the ground here, okay? So the path is given onto the, on the ground and the robot is following the path on the ground, avoiding those holes. And as it is moving, it has to balance its body also by using the legs. So the red one is the feet's path of the two feet and the green one is the CG. So from different kinds of terrain or ground conditions, there are holes you can see. So it should not fall inside. It is able to navigate and go from one point to another point by first finding a path and then going on the path by doing the motion plan. This is a more difficult one in which there are all kinds of inclinations, okay? And you can see there are all shapes of ditches. So it should not fall down somewhere inside. So find a path and then follow the path to go from one point to another point. So this was for the case of a staircase also, it is able to do that, okay? So this is a staircase, where it is going up a staircase. Dynamic obstacle avoidance, there is a lot of talk of autonomous cars, okay? Autonomous vehicles. You talk about the Google car, the Apple car, even in India, there are a lot of companies which are trying to do like Mahindra RISE, the Mahindra RISE challenge is there. Tata Motors, they are trying to make autonomous vehicles. Autonomous means they can drive by themselves. This is an example which is showing an autonomous vehicle. So the one on the right is showing the vehicle which is moving automatically. The top figure is showing, the top figure is showing the car coming from behind and there is a car in front, okay? So you can see the car which was coming from behind is not hitting the car which is there and it is moving. So this car is using probably lidars and cameras which are mounted to check for obstacles in front and if there are obstacles, it can immediately stop and take another route. For example, there is a person in front now. So it stops and changes its path. So it avoids the person and then goes back again. So this is autonomous cars and you also understand what is meaning of path planning. So this is following a person. So the person is walking slowly in front, okay? So today what I explained is basically an introduction to the topic of path planning or motion planning and I explained what is the difference between path plan, a path and motion plan, okay? So as we go along from tomorrow, we will start off with basic introduction of automation, okay? What is automation and in, because the larger subject is automation and robotics is a small part of automation. So what is automation? What is robotics? Then we look at serial arms, serial robotic arms, we look at different transformations. How do you go from one frame to another frame when a robot is moving in space? And once we have finished with the very basics, the first few classes will only be basics, okay, of mobile robots and serial arms because without knowing the mathematics that is required, there is no point in studying either robotics, either motion planning or robotics at all. So in the next class, we will start off with automation and then we will proceed in that order and once we have finished the introductory classes, then we will go on to actually how do you write the algorithms to be able to implement it in real, in the real world in case of a real robot, okay, to find the path and how the robot can go on the path, okay? So we will stop here today. Thank you.