Lecture 20: Optimization in Motion Planning

IIT Kanpur July 201
20 followers
2 Video Views·Dec 1, 2023
Hello and welcome to lecture number 20. So, this is the last lecture in the course Robot
Motion Planning. So, we started this course by looking at the very introduction of robot
motion planning, why your motion planning is required, where it is used for serial arms
and mobile robots. Then we started off with bug algorithms, bug 1, bug 2, then we looked
at configuration space that is we saw that when the robot is a point robot and the robot
can move in any direction, we do the planning in C space or configuration space and from
that we moved on to the various roadmap methods. So, in roadmap methods we looked at the Voronoi
diagram, we looked at visibility graph methods, then from there we moved on to cell decomposition
and then potential field methods, right. Now, we also saw that normally when you look
for a path or rather when you generate a network of paths, you get a large number of
paths to go from the start point to the end point. For example, in sampling based methods
you can get a very large number of paths which will take you from the start point to the
goal point if of course there are large number of paths.
So, in cases where there are very large number of paths we have to find which path is the
optimal path in terms of in terms of path length or in terms of energy consumed, ok.
So, what you notice or what you understand by now is that some kind of optimization is
required. So, today's class basically we will look at this concept of optimization that
why is optimization required in robot motion planning and when we are trying to optimize
how do we particular try and get a particular solution, ok.
So, today's class is we will look at multi-agents where we have multiple mobile robots which
are for example, capturing object and pushing it somewhere. We can look at multi-finger
robot hands, it is almost like the multi-fingers of the robot hand are like multiple serial
robot arms which are manipulating an object, ok.
Then from there we will move on to biped locomotion, again we will see that when we are using our
path planning methods then what happens is we end up with a large number of solutions
and some kind of optimization is required. So, today's lecture is mainly to do with optimization
in motion planning and with this lecture we will be ending the course on robot motion
planning.
So, let us start off with the last lecture. So, optimization in motion planning that is
the topic of our last lecture that is lecture number 20. Now, when you have multiple agents
doing a particular task for example, multi-agents like mobile robots, manipulators, multi-finger
grasping they are all can be looked upon as multiple robots doing a particular task, ok.
For example, moving an object constraining an object.
Now, the idea of multi-agents has been borrowed from nature because if you if you you must
have seen this that in ant colonies or bees basically, it is like multiple bees are together
performing a particular task or if you look at an object say for example, this is a piece
of food and there are ants who are carrying this object. So, these are ants. So, you can
see multiple ants who are actually carrying this last object. So, they are cooperating
with each other through a particular task. Say for example, there are many ants and these
ants are lifting this object and taking it in some with some trajectory or taking it
in that direction, ok.
Now, that can be a case of multi-agent system where you have multiple agents doing a particular
task and hence they can be ants, many ants doing a task, they can be bees, multiple bees
are flying in formation, collecting honey and doing a particular task, ok. Now, so this
idea of multi-agents or what we also call swarm robotics is basically borrowed from
nature.
Another example is multi-finger manipulation. So, we have an object like this. So, let us
say I have a cube, this is a cube and the cube is held by fingers, multiple fingers,
we have multi-finger hand which is holding this cube and I want to move this object in
a particular orientation, ok. So, I basically want to manipulate this object. So, I am going
to rotate or translate this object in a particular way.
So, it is like there are multiple robots, each of these fingers can be looked upon as
a robot, a serial arm robot. So, this is 2 and that is 3. So, these 3 robots are together
performing a task to manipulate this object in a particular desired way, ok. Now, again,
so the basic idea here is to be able to perform a cooperative task that cannot be performed
by one individual robot. So, in the case of the bees or the ants, so in the case of the
ants that we are seeing here, now one ant cannot lift this object and take it somewhere.
So, there are multiple ants which are actually catching it and taking it somewhere, ok. So,
the very basic idea is cooperation, when one individual robot cannot do this task, then
multiple robots can actually come together and do this task.
In the case of multi-finger manipulation also, we have the same concept, we have multiple
fingers which are actually applying a force or motion to the object and is manipulating
the object in some way. Now, something that you note here is that there can be multiple
solutions, ok, multiple solutions. So, this basically means that if the ants want to catch
this object and lift it and take it somewhere, there are multiple ways of doing this task.
Similarly, in multi-finger manipulation, if you want to manipulate the object in a particular
way, then there can be very many solutions to this problem. That means, the fingertips
can apply different forces, ok, or different motions to orient the object in a particular
way, ok. Now, these are some examples of small experiments
which are done by using mobile robots as multi-agents. So, this is a very small mobile robot. Now,
you might have made this kind of robots in robotics club and things like that. So, inside
this robot, there are two DC motors. There is a DC motor there and a DC motor there.
It is driven by a microcontroller and it can move in a particular direction, ok. So, this
is basically what we call a differential drive robot. So, I have two wheels, one wheel here,
one wheel here. This has omega 1, that has omega 2 and there is a castor wheel in front.
So, the ratio omega 1 by omega 2, this ratio I control for the robot to go straight, to
turn right or to turn left, ok. And if you have one robot, for example, I want this robot
to pick up an object or push it somewhere, it may not be able to do it, ok. It may not
have enough torque or power to do that. So, suppose as shown in this figure on the
right side, so we have this black object and we want to push this object and take it to
some location, ok. So, one robot may not be able to push. So, I am using two robots. There
is one robot here, another robot there, ok. This is an example of multi-robots doing a
particular task. Now, this black object could be a moving object also. Say for example,
I leave the black object itself, suppose it is moving, having a particular trajectory
and I have mobile robots which want to capture this object, ok, first go and catch it and
then maybe push it somewhere. So, these are examples of multi-agent kind
of applications. Now, multi-agents can be extended to many-many applications. For example,
two humanoid robots, one robot which is a wheel-mounted humanoid robot. So, this robot
is mounted on a mobile, is mounted on a, on a mobile base and there are two robots
which are supposed to do a particular task. For example, both the robots you can see are
shaking hands here or they could be carrying an object. For example, this is a very heavy
object which one robot cannot do, one robot cannot carry, then both the robots will come
together and carry an object. For example, here you could also have a human
who is cooperating with a robot, ok. Say for example, here there is a human on one side,
there is a human here and the robot on the other side is carrying this block of wood
in some direction, ok. Here we come up with the concept of what we call leader-follower,
ok. So, in this case the human is the leader, the human pushes or pulls the object in a
particular direction and the robot just follows. So, the idea here is that the robot is cooperating
with the human in doing a particular task. Now, obviously this has to be moved in a particular
way. So, this is motion planning or path planning.
Now this is another example shown on the right hand side where it is a human being
who is actually sitting on this legged robot, ok and this legged robot is going in a particular
direction. So, this is a robot who is cooperating with a human in carrying the human from one
location to another location by following a particular path, ok. So, this is a case
of robot-human cooperation, there can be cases of robot-robot cooperation also.
See for example, here we have a concept of robot and robot cooperation. There are two
human robots, one robot here, another robot here who is and these two robots are carrying
this very heavy brick, ok and taking it in some direction. Again the concept of leader-follower
has to come here, ok. Why leader-follower? Because suppose this robot pulls in this direction
and that robot also pulls in that direction, then the task is going to fail, they will
drop the object, right. So, there has to be a leader who is doing the task and there has
to be a follower who is simply following. So, this is an example of two robots doing
a particular task. Now, each of this can be called an agent, ok. So, each robot here can
be called an agent. Now, this is a biped robot agent, ok. Here it is a mobile robot agent,
but essentially they are doing the same job, they are having some task plan and they are
doing some particular task, ok. So, we can see that this agents can be of
different kinds, they can be bipedal agent, they can be torso which is mounted on a mobile
robot or they can be mobile robots itself who are doing a particular task, ok. So, now
what we are seeing here is that again to do this task, if I am talking about a path plan,
if I want to carry the object in a particular direction, there has to be a path. So, these
robots also have to follow a particular path and they must have some motion plan.
Now, if there are multiple ways of doing the task, there is a need for optimization. For
example, we looked at cases of form closure and force closure. In the last two classes
I think we looked at the concept of force closure and form closure, where the object
is in closure by using three fingers with friction or we have four fingers or more without
friction. So, suppose this three fingertips are holding
an object like this, ok and I want to rotate this object in a particular way, then this
fingers have to apply forces, ok. Now, there can be different combination of forces which
can give you the same motion, ok which basically means that first of all I need to ensure that
there is a closure, force closure or form closure, so the object does not fall off.
Then I have to optimize it, optimize the motion, ok. So, this means I need to have some kind
of optimization which is going to optimize the motion.
For example, I have an object here, this object. I have three fingers as shown in this figure.
Where do I place the fingers? Do I place them here, here and here or do I place the fingers
in some other way, ok? Suppose I can place the fingers here, I can place the fingers
let us say here, ok here, here and here also, ok. So, this is one way of placing fingers
that is the other way of placing fingers. So, there are multiple solutions here now,
ok. So, to get form closure or force closure which is the optimal way and hence the question
of optimization comes into picture. Now, when we are choosing in the case of roadmap
methods when we are making a network of paths, ok. So, we are made network of paths from
the start point to the goal point. We were choosing the path by means of algorithms like
D star, ok or A star algorithms, ok which give us the length of the path. Now, that
is not enough here because we also have to ensure form closure or force closures.
For example, if the object is moving I have to catch it and then I have to do something.
So, this is another example where we have multiple mobile robots. So, these small black
dots that you are seeing here these are mobile robots, ok like the one I showed you and this
is a moving object, this object can move, ok. Now, I want to go and catch this moving object,
there are so many robots you can see there are set of robots here and a set of robots here.
Now, the function of these sets of robots is to go and capture this object,
this is a moving object, right. So, it has to go and capture the object and then maybe
push and take it somewhere, ok that is the objective of this path learning with multiagents.
Now, this object is moving. So, if this robot tries and goes and sits here what will happen
is this object is going to hit the robot, ok. So, it does not go and sit on the object straight
away it has an expanded boundary like this, ok. So, there is an expanded boundary like this on
which the robot goes and sits, ok that is what we are seeing here. So, what the robot will do
is it will first go and sit on the boundary then it will go and capture the object and
stop it from moving, otherwise the object is going to hit the object, the object is
going to hit the robots, ok. So, here there are a couple of questions number 1,
what is the minimum number of robots required, ok, what is the minimum force to be applied,
ok to do this task. So, that is where the question of optimization comes in.
Let us look at this video. So, you can see that the object is moving and the robots are
going and positioning themselves on the boundary, the expanded boundary on the blue line and then
once all of them go and put themselves on the boundary then they go and try and capture the
object, ok. Because this is a moving object what will happen is otherwise it will get hit,
the robots will get hit. Even then you see that it has caught the object and there are
some robots which are still trying to position, ok. So, the question that we are trying to use
here, let us look at the video again, you can see multiple robots are going, sitting on the
expanded boundary of the object then they will jump and go and capture the object, ok.
So, now what is the question we are asking here, the question we are asking here is how
many minimum robots are required, where should we go and capture the object, ok. Is it in force
closure, is it in form closure, these are two terms that we used in the last couple of classes,
ok. So, that is something which we will look at in this lecture, ok. So, first we will start
off with form closure. Also in the case of potential field methods we have seen that
when you are using an attractive potential and a repulsive potential then this constant zeta and
eta are there, ok. So, these are constants and you have to put numerical values.
So, how do you put the numerical values of these two constants, that is also one need
for optimization in potential field methods. Now, let us start off here by looking at this
case where we are trying to grasp an object using three fingers or four fingers for closure,
either for form closure or force closure, ok. This is an industrial gripper, we said that
all industrial grippers or most industrial grippers have three fingers, ok, because of
which they can have force closure grasps. So, suppose you have four fingers, in the
left hand side we are seeing four finger case. Now, how this gripper works is this finger can
rotate about this axis, ok. Now, if the finger rotates about this axis, so it can rotate. So,
the finger can place itself, this finger can come this side, ok. So, if I see the top view,
if this is the top view of the hand, if this is my finger, these fingers can move in this direction,
that means they can go and place their fingertips in any location, ok.
So, in the figure on the left hand side, we have four fingers, a gripper having four fingers and
we want to place the fingers, these are four fingers, let us say 1, 2, 3, 4 fingers and this
is showing the top view, this is the top view and this is the front view, let us say. So,
there are four fingers, front view and top view. Now, these fingers can move in this direction,
so I can place them in different points in the, in, on that circle, ok.
So, the question being asked here is, in order to have form closure of this object,
how would you place your fingers, where would you place your fingers, what is the motion plan? Now,
there are four fingers, point contact without friction, so we can obtain form closure,
for form closure we can obtain four fingers, ok. Now, on the right hand side, we have point
contact with friction, so point contact plus friction, ok. So, in this case, three fingers
is enough, so three fingers can be used to obtain force closure, ok. So, this is we are looking at
force closure, this we are looking at form closure. So, the question being asked is,
where would you place these fingertips such that the object is in closure?
Now, now let us look at this as an optimization problem now. Now, this object let us say is,
can have any shape, ok. So, this object that is shown here, this is my object and this object
can have any shape. So, what we do first of all is that we segment the boundary. Now,
this is a continuous object, right. Now, in order to be able to check where the fingertip can be
placed, that is discrete. So, if I say that I take this side and I divide it into these points,
now these points the fingertip can be placed, ok. For example, here the finger cannot be placed,
ok, on a corner. So, what I do first of all is I segment the boundary, ok. So, given an object
with n points on its boundary, we are required to find the optimal grasp points for satisfying
form closure or force closure, ok. So, that is the problem, this is the object of some shape.
Now, I want to convert this into a digital problem, ok. So, what I do is I segment the
boundary of this object, I segment the boundaries by putting these points, ok. So, when I put this,
I break up the boundary into number of points where the fingertip can be placed,
ok. And then what I do is, I convert this into a binary string. Now, wherever the fingertip is
present is 1, wherever there is no fingertip it is 0, ok. So, finger present means 1, finger absent
means 0, ok. So, there is a finger sitting here, ok. So, I start from here, let me start from this
point. So, there is a finger sitting there, so this is 1, ok. And if you are going clockwise
direction, then it is 1, 2, 3, 4 are there, so there is 0, 0, 0, 0, again there is a 1,
then it is 0, 0, 0, 0, 0, 0, then there is a 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0.
So, if I start counting from here in a clockwise direction, then it is 0,
sorry 1, 0, 0, 0, 1, 0, 0, 0, 1, that way. So, I have converted this analog problem into a digital
problem now. So, this binary string is actually telling me on that object where the fingertips
are present. So, wherever there is a 1, the fingertips are there, there are 4, 1, 2, 3, 4,
there should be 4, ok, 4, I think there is a mistake somewhere, anyway there should be 4
fingers. So, wherever it is finger is there, it is 1, where it is not there, it is 0.
Now, this is a binary string, now we can, a computer program can very easily handle this
binary string. So, you can guess that now suppose I want to change the position of the fingers,
what will I do, I will simply change 0s and 1s, if I change that 0 to make it 1,
the finger has come there now. Suppose this finger from here goes here, what will happen,
this will become 0, that will become 1. So, what I can do is I can use optimization like
genetic algorithm for example, what it does, it takes this binary string and changes those bits,
it will make some of them 1, some of them 0s, ensuring that there are 4 total 1s,
because this is a 4 finger gripper. So, there is going to be 4 robots present always,
now if there is more than 4, it can be 1, you can make it 1s, it does not matter.
So, what GA would do essentially is, it is going to switch those bits and that essentially means
in the physical system that that is where the fingertip is present now. So, that is equivalent
to saying that I am placing my fingertip in different points on that object. Now,
how do you satisfy form closure? So, we are saying that we are keeping the fingertip
at different locations, but we have to satisfy form closure. So, what is the optimal way of
satisfying form closure with 4 fingers? So, one way is the fingertip contact is without friction,
so it is point contact without friction, so you can apply only one force.
So, one way would be to maximize the clockwise and anticlockwise moments,
let us look at this case, suppose I have a rectangle and I have 4 point contact,
I can place my 4 fingers like this or what I could do is I could place the finger such that
the, I place 2 fingers here, 2 fingers here, 2 fingers here and 2 fingers here,
in that case what would happen is I can maximize the moments, why? In this case,
this fingertip is going through the CG, so it is not generating any moment,
so it cannot resist moments. Whereas, if I put my fingers here,
it is not only resisting the forces, but it is also resisting the moments now.
So, suppose there is a moment in this direction, this force and this force will resist that moment.
Okay, so we can place the fingers such that you maximize the clockwise and the anticlockwise
moments, okay. So, for example, in this particular case I gave, if you have a very long object,
it is a good way of catching it here and here and here and here, why? From statics point of view,
you are maximizing the moments, that means you have to apply less force to take care of any
moment disturbance that is coming, okay. So, this is the first one, maximizing clockwise
and counterclockwise moments, okay. So, these are the objectives.
Now, we are doing GABS optimization, so we need to have objectives. Now, the objective can be
single objective, which you can maximize or minimize, it can be multi objective. In this
case, it is multi objective, there are two objectives, so we are maximizing this and we
are minimizing this one. Now, what is the minimization problem? Minimization is,
we are minimizing the total angle subtended in the center, okay. For example, if I have fingertip
here and this pointing in this direction, so the fingertip force is going to be normal to the
surface, right. And this is the line connecting the fingertip contact to the CG, then what I am
saying is that is my angle theta and I want to minimize it. Why do I want to minimize? Because
if you know that if you have an object like this and you are placing fingertips, all of which pass
through the CG, then the system is going to be in static equilibrium, okay. That means,
the fingertip contact, just let me give an example like this, if this is my CG and the fingertip is
pointing in this direction, so what is happening is it is generating a moment, whereas if the
fingertip, if the fingertip is pointing in this direction through the CG, then it is not generating
a moment, okay. So, we are maximizing this clockwise, anticlockwise and we are minimizing
that angle theta, so that the object is in static equilibrium. So, we have two objectives, maximize
clockwise, anticlockwise moments and minimize the angle subtended in the center.
Now, we need to worry about the, we need to worry about the accessibility angle, okay. So,
the first constraint we saw is that the robot should be creating moments in both the directions,
clockwise and anticlockwise, okay. So, in order to balance the external torques, external disturbance
torques that may come on the system. Now, the second thing is, other constraints is,
so this is one constraint, the other constraint is the finger should not overlap, okay, the total
number of fingers should be 4, because we know that for form closure of a 2D object, so form
closure of a 2D object, okay, you need 4 fingers that we have seen before, okay. Now, the area
formed by the fingertip contact is not 0 and the number of finger producing clockwise and
anticlockwise moments are equal and the accessibility angle is 0, okay.
Now, what is this last one, which is very important for us here? Now, suppose I have
an object like this and I place all the fingers here, what will happen? The object can go this
side, can go this side, the object can go that side, it can, it is not constraint,
okay, it is not in form closure, okay. So, simply maximizing and minimizing the
moments may not give you the solution, okay. So, what we need to do is we need to also look
at the accessibility angle. Now, accessibility angle essentially means that if you have caught
an object by 4 fingers, it should not be able to escape in any direction. So, what this means
is that if I put 4 fingers here, here, here and here, this object, if it is a moving object,
it should not be able to escape or move in any direction, it should be constraint,
then it is in form closure, okay. So, how do I get, how do I ensure form closure?
So, what we, what we check is what we call the accessibility angle or the freedom angles.
Now, the concept is very, very simple and this is also used in jigs and fixtures, okay. For example,
if you are looking at an object, this is my object and I put my finger here, this is my finger.
Now, if I put my finger there, it means, it is, there is, I am applying a force F in that
direction. So, the object cannot move in this direction, it cannot move, okay. But the object
is still free to move that side, this side and this side. There is no, there is no mu there,
so this mu is 0. So, the object is free to move in the other direction, okay.
So, this is like saying, if I have a fingertip here, this is my fingertip,
this is my freedom angle, the object is still free to move 180 degrees from here to here,
any in that, any direction it can move, okay. Similarly, if I put my finger here,
then the object is free to move in any direction like this, okay. So, this is called my freedom
angle. So, if I put one finger and, if I put one finger here, one finger here, one finger here,
the object is still free to move in this direction. Now, how can I check that? That is actually very
easy, because please remember that this is a computer program which is doing this.
As I said many times during this course that we have eyes, so we can see. So, I can guess,
okay, there are three fingers here, this side is still free, so the object can go that side.
But the computer program does not have eyes, it needs to figure this out geometrically.
So, how does it geometrically figure this out, okay. So, what it does is, basically it does a
sum of the accelerator angles, okay. So, what this means is, suppose this is my, so let us see,
this is my, let us say coordinates, this is my x and y, this x and the y, this side is here,
this side is here, and this angle, angle 2 is like this, okay, the same direction.
So, wherever direction the force is, opposite to that force, this is the freedom angle which
is on the other side. So, if I have a flat surface like this, there is a force here,
this is my freedom angle, because it can move in that direction. Now, so that is the first one,
so this 2, so you can see it here, I am saying 2 is here, that is my number 2, okay.
Next what I do is, I look at 1, so where is 1, it has this inclination. So, 1 has this inclination,
this surface, so I draw this here. Now, where is the freedom angle, freedom angle is here,
that means the object can move in that direction, assuming that only this fingertip is there.
So, this is my fingertip freedom angle, like that for 1. Now, there is another one, there is 3,
so for number 3, what we can say is, this is my freedom angle, so number 3 freedom angle is here.
Now, if I take the sum of all these angles, okay, sum of all angles, okay, then what I do get is,
this part is still free, you can see here that this part is free, okay, this part is not covered,
okay. So, if I sum all the angles, I see that this part is still free, that means,
what this means is, the object can escape in this direction, okay.
And which direction is this, it is this direction, so it is here, so the object can actually go
that side. So, if you have 3 fingers, 3 point contacts, the object is still free to go this
side. Now, the robot can very, the program can very easily find this out, okay. How this find,
how the program can find it out is, at every point, now how does it know at which point the
finger is there, basically it goes back to the string, the binary string actually tells us
that at which point on the boundary the fingertip is there, for example, one finger is here.
So, what it basically does, it takes, it knows this is the first point, this is the second point
and these are vectors, right. So, what it does is, it does,
it finds this angle, it can find that angle very easily and now it knows that what is that angle
and converts it into the total diagram, okay. So, it is very easy to find the accessibility
angle geometrically. All the program has to do is, at every point, it has to find the normals.
So, at this point, it finds the normal and then finds this angle, okay. So, if this is a point
here, this is another point here, this is a point here, you know the corners of these points.
So, this is a vector, this is a line, this is another line, so you can find the angle between
those lines, okay. So, you can find this angle geometrically, okay. Then from here, we come here
and what we do is, we find the accessibility angle. So, if 360 degrees is fully covered,
for example, if you look at this case here and you look at the case at the bottom.
So, in the top case, this location is free. In the bottom case, one finger is put there.
So, the moment you put a finger there, this freedom angle is on this side now. So,
what has happened is, this freedom angle, this angle, okay, has come this side now.
So, this is my angle number 4. So, this angle which was free before here, that is covered now.
So, if you look at this one now, there is no angle free. This means the object cannot go
in any direction, okay. That means the fingertips have been placed in such a way that all the
directions of escape of the object are covered, okay. Now, how does this work? For example,
we are using genetic algorithm. What genetic algorithm does is basically, it takes that pool.
So, we had this binary string, okay, that we saw. So, what GA will do is basically,
it will switch some of this. It will make this one, make this 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, okay. So, it generates another one by doing crossover and mutation, okay.
So, that is what it does. Then what it does, it evaluates the objective functions with the
constraints. So, suppose it violates any constraint. For example, what is the constraint?
If the accessibility angle is not 0, that means the object can still can escape,
then it will reject that solution, okay. Now, if it is not violating any constraint,
then what it will do is it will evaluate, evaluate the objective functions.
So, we have shown the two objective functions, which it is going to evaluate. One was the
moments. So, clockwise sum of clockwise moments, counterclockwise moment plus clockwise moment,
so mod of this and mod of that. So, it was maximizing this. And the other was,
it was minimizing the angle norm theta. So, what it will do is it will evaluate this function and
then give a particular value to that, okay. This is how GA basically works. It is very simple to
understand that genetic algorithms basically look at this digital string and keep changing the bits
in the string. Seeing solutions which satisfy, which do not violate any constraint, find the
objective and then proceed, okay. So, by doing that, these are some examples. For example,
an object of, the red one is an object and you are placing fingers at different positions. So,
this is one finger, another one, another one, another one. So, in each of this, you can see
that those fingers are at different locations and the objectives are being evaluated.
And if you plot them, the sum of angle versus sum of moments, then these are some of the solutions
that we are getting. This is multi-objective. So, multi-objective will get multiple solutions,
okay. Then from one of this, you can choose one of the solutions. For example, I can choose this
solution, okay. So, this means solution number four is this one. I place my fingers here, here,
here and there. So, this is the case of multi-objective optimization, how we can find
where the finger should go to catch the object. Now, in the case of mobile robot, we can say this
is where the finger should be placed, sorry, where the mobile robot should go and catch the object.
So, suppose this object is moving like that and I want to go and capture it,
then the mobile robot should go and sit in these places for form closure,
okay. So, that is what this is telling us. Now, this is another example, star kind of an object.
Again, you can see the sum of angles are here and the sum of moments is there and these are
locations of the fingertips. Wherever the fingertip is going and sitting, this is for number one. So,
this is the solution, where the location of fingertip is. So, again, this is multi-objective,
so there are multiple solutions. So, you can choose a solution somewhere here,
which is giving equal weight to both the objectives, okay. So, 8 and 9, where is 8 and 9?
So, 8 and 9 are here, 9 is here and 8 is here. So, this would be good solutions,
which gives equal weightage to both of them. So, this is how we can find where a multi-fingered
robot hand can place its fingers or a mobile robot can go and capture an object, is the same thing.
Now, for three-fingered hand, it is force closure, not form closure, okay. So, in force closure,
we know that it is point contact with friction. In the previous case, there was no friction.
And in this case, we need three fingers that we have seen before. So, in this case, again,
the question is the same, I have three fingers, I want to catch this object, where should I place
my fingertips, okay. And we say, to obtain force closure from statics point of view,
that the objectives are three of them, maximum area of triangle. So, the fingertip should be
placed such that this triangle is maximized. Why? You can guess again, so that your grasp
is going to be stable. So, when you catch an object, if you catch it on the boundaries,
what will happen, you have most stable grasp. So, that is one, the second is minimum force focus.
So, suppose my finger is here, finger is there, finger is there. Now, because this has friction,
there is a friction cone, which is there. So, these are friction cones, because there
is friction there now, okay. So, this intersection of the friction cones gives us this area.
And what we can do is, we can say minimum force focus. So, what we can do is, I can take the CG
of this area and the CG of the object, I can take the distance d and try and minimize that.
The second, the third is force line, which is same as the previous case. So, this object is here,
it is pointing in this direction. So, it is making an angle theta there. So, we should
place the fingers at locations where the normal at that point goes through the CG. That means,
this theta should be minimized, okay. So, in this case, for force closure,
we have three objectives, maximum area of triangle, minimum force focus and force line,
minimum theta, okay. Now, what are the constraints? The constraint are that there should be three
fingers. And why is this required? For example, I will use the same string again. So, it is 1,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0. There are three fingers now.
So, when I am using GA here, and GA is changing those bits, okay. Any case where there is more
than three ones, it will get rejected, that is not a solution, okay. It is violating a constraint.
And number two, the friction cone should be satisfied. So, if I have a friction cone here,
like that, okay, then the normal force should be inside the friction cone,
otherwise it will slip there, okay. So, these are the two constraints that are kept.
Now, accessibility angle also is used, okay. So, accessibility, how this presents is,
essentially, we do boundary segmentation. Exactly the same way, I divide the boundary
into discrete points, make my binary string, check for accessibility angle, the freedom angle,
and ensure that the freedom angle covers 360 degrees in space. That means,
there is no free direction in which it can go. So, no free direction of escape.
So, after placing the fingertips, we see that the object cannot go in any direction,
okay, cannot escape, okay. So, that is a constraint. So, what GA will do is,
it is going to change the strings, it is going to change the binary string,
and then place the fingertip at locations where constraints are not satisfied, and it will evaluate
the function, it will evaluate the objectives. Now, there are three objectives. One is force
focus, force line, and area of triangle. So, we get multiple solutions. This is actually a surface
of solutions. So, you can choose a solution. For example, in this particular case, A has,
A, D and theta has this particular value, fingertips are here, here and here.
So, depending on what you want, you want to give weightage, more weightage to which part,
to force focus or to force line or to area, depending on that, we can place our fingers
accordingly, okay. This is another, another two cases, where if you want to catch this object,
where is the best place to place your fingers, probably here, here and here, okay. So, here,
here, here is for this object, for this object is here, okay. So, this is basically giving you an
idea that if you want to do optimization, here you have multiple solutions. And for each of
these multiple solutions, you need to find, you need to evaluate the objectives and then come up
with which is it that grasp that you want, okay. Now, I am using the word grasp, but this can also
be done by multiple mobile robots. For example, if this is a moving object, and these are mobile
robots, then essentially it is going there and catching the object, okay. If you want to do
single objective optimization, we can still do single objective. In single objective optimization,
what we have done is we have used clockwise moment plus anticlockwise moment divided by
n raise to k, where n is the number of robots. Suppose, we are looking at a case where we do
not know how many robots are required to capture the object, then I say n is the number of robots.
Now, I want to minimize the number of robots used and I want to also satisfy this objective
function. Now, this objective function is a sum of the moments here, number of robots come on
the denominator, okay. So, what GA will be doing is basically it will be switching the number of
robots also. So, it can start off maybe with 50 robots and start coming down and seeing what is
the minimum, and the minimum is going to be 4, because we know that for force closure,
form closure, we need 4 robots. So, you can have multi, you can have single objective,
you can have multi objective optimization. Now, this is an example, okay, of object
capture, where you can see that the object is. So, these are the robots, 4 robots, this object
is moving, the green object is the obstacle which is moving and it is moving in a circle,
you can see it here, it is moving in a circle. So, these robots move, okay, by using a path
plan basically. So, basically what the question is here, capture this object, capture this object
by mobile robots. So, the first thing it has to do, it has to find out on the expanded boundary
where it will go and sit first, then where it will go and catch the object by using what we
just discussed, optimization. So, from the optimization, the answer would be that
you, the robots need to go and sit on the boundary first here, here, here and here,
and then on the object itself, these are the points where the robot should go and sit,
okay, to satisfy form closure, then it is caught, okay.
So, this is the first, you can see the robots are here, then the robots start moving there,
then the object is moving, then the object, then it goes here and then finally it goes and captures
the object, okay. So, this basically shows us the four stages in which the robot is going and
capturing the object. Now, after capturing the object, the robot is expected to go and
push the object and take it at some point. Now, to push the object, say for example,
I have an object like this, a rectangle and I have four robots, okay. So, after capture,
the robot is supposed to go and push the objects in a particular direction.
So, let us say that we have an object like this, shown in blue on the top, sorry, shown in red
color, so this is my object and what I want to do is, I want to push it in some direction. So,
if I want to push it to capture it, please understand that I have to place my robots like
this. Now, suppose I want to push it in that direction, what I must do is, I have to reposition
this robot such that the robot pushes in this direction now, okay, otherwise it will not go
in that direction. So, the robot has to change its position again and have a new path plan to
push it somewhere else, okay. So, for example, in the object here, the robot sits here and pushes
it and applies a force in this direction, okay. So, what we need to do is now, we need to
reposition the robots and after repositioning it, then we can push in some direction. Say for
example, after capture, we had four robots which are positioned like this. Now, it has been
captured. Now, I want to push in some direction. So, these robots will have to move away and then
allow this fellow to push it and take it in this direction. So, I have to reposition the robots
again. And how can we reposition the robots? Essentially, we can do optimization again,
where we can maximize this. Suppose, this is the direction, some robots are going to push in that
direction and some robots are going to be passive. So, it is a game between active
and passive robots, okay. So, when this robot is pushing, the object will move in this direction.
When this robot is pushing, the object will move in that direction. So, by making a combination of
these two motions, the robot can be taken towards in a particular direction, okay.
So, the, what we are optimizing is this basic function where d is the, this direction,
the vector d dot f1 plus f2 plus f3, okay. So, again, we do exactly in the same way,
okay. So, basically, we use this, the binary string which indicates where the robot is sitting
and then we make the robots active and passive. For example, this robot is active means it will
push in that direction, so the object will go that side. Next, this robot will push, so the
object will go this side now. So, by doing this kind of motion, you will get, end up with this
kind of motion, but there is no other way, okay, because you will never get the resultant in this
direction. Suppose, I want to move an object like this, so I will not get the resultant of forces
in this direction by placing robots like this. So, I can make some of them active,
some of them passive and then push them accordingly. For example, in this, in this case,
okay, what the GA is doing, it is first using this robot to push. So, what is happening is
when these two push, the resultant force will be in this direction,
then these two will push, the resultant force will be in this direction now,
okay. So, what kind of motion would you get? The object will have this kind of motion
depending on which two robots are active at which time, okay.
So, this is the way an object is pushed and taken to some other position. So, this is basically
multiple agents guiding an object and taking it some, some place. We had looked at the case of
the potential field method in 3D, where we said that or even in 2D that there are constraints,
this is a constant, this is also a constant. So, again we have to do optimization of some kind,
which means that in case of 3D, this is something I had explained in a couple of classes back,
that if you are going from 2D to 3D, what we can do is we can put the gradient force also.
So, f grad is there. Now, this W1, W2, W3, W4 are weights or constants.
So, what we can do by GA again, we can use genetic algorithms here. What GA will do,
it will have, it will have W1, W2, W3 and W4 and it will randomly switch these values,
numerical values and then it is going to evaluate some objective function.
For example, the objective could be in this particular case, the objective function that
is being evaluated is the ratio of the wheel velocities. So, you can imagine that if the
robot is like this and there is a wheel here and there is a wheel there, then this is omega 1,
this is omega 2. Now, if it is on flat ground, then omega 1 will be equal to omega 2, omega 1
by omega 2 will be equal to 1. The moment it is on in plane ground, what will happen is,
one, the velocities will change now. So, if you want the robot to be in flat ground,
then what we can do is I can take the ratio of the velocities. So, this velocity, left side
velocity divided by the right side velocities and L1 is the length. So, I am going to minimize this
now. That is one objective function. You can also have objective functions like
minimizing torque, torque, the ratio of the traction force to the normal force.
So, when this vehicle is moving in uneven terrain, basically what we want to do is,
we want to minimize the ratio of the traction force to normal force.
You could have another objective like minimum power consumption. So, this is the torque at
the wheels. So, torque square is the total power that is being consumed, I want to minimize that
or you could minimize the length of the path itself. So, when we, when we are doing A star
or D star or the D star algorithms, we are basically minimizing the length of the path.
So, you can use that also as an objective here. So, what GA is doing is, it is switching this
values of the weights. So, there are this weights W1, W2, W3, W4. So, it is switching this value,
it says 0.5, this is 1, this is 2, this is 5, randomly keeps switching them,
evaluates the objective and finds which one gives you the best value.
Now, this is an example that gives us some idea. Now, it is saying that W1 which is the attractive
force is the highest value that is expected. So, on this 3D terrain, when we ran the GA
algorithm to find the weights, we found that the weight W1 has the maximum weightage,
okay, just because it has to attract the force. And the next is the gradient force,
then the third is the lowest is the, the lowest value is the repulsive force and then it is the
tangential force. So, in all the cases, for all the objectives, you can see that the value is the
same, I mean the trend is the same. So, W1 attractive is always the highest
and then followed by the gradient force. So, this gives us an example or tells us
an idea that when you are doing a potential field method, what should be the values of
the numerical constants that you are putting? The attractive one should be at least 10 times
that of the, the repulsive force, okay. So, the robot is always going towards the
attractive force. This is an example of, a very famous example of Boston Dynamics,
the bipedal walking robot, okay, Atlas. So, this robot can walk around, okay, it can go outside,
it can walk in uneven terrain, okay. Now, this is the case of path planning and motion planning.
And this is probably the most complex in the world today, okay. So, we see this concept of
path planning and it is also doing different tasks. It can pick up objects and put it somewhere,
okay, very, very interesting example. It can pick up objects and for example here,
it is resistance to, it has, it can reject disturbance. Now, it is even more unkind,
it is the most unkind thing to do to a robot probably. So, the robot is being pushed and it
goes and falls down. The next question is how do you get up? So, getting up in terms of motion
planning is, what is the motion plan a robot should have to get up, okay. So, there is also
motion planning problem. We did not come this far because we did not discuss such complex systems.
But today research in motion planning is in this direction, that if the robot has to go outside,
open a door, if the robot falls down, it has to get up. How do you do this kind of tasks, okay?
Now, optimization is required because there are multiple solutions.
I will very quickly explain what is done here. So, what we basically do is,
when a biped robot walks, you can see that it walks in two planes. One is the frontal plane,
it moves from side to side and in the side plane, it goes forward. So, what we do basically is,
we assign, so this is in 3D, a biped robot is walking or balancing. Now, what is balance?
The balance is the constraint here. So, it basically means the robot should not fall down.
What is the meaning of falling down? It basically means when it is standing on one foot,
there should be no resultant moment here. So, no resultant moment. If there is a resultant
moment anywhere, it will fall in that direction, okay. And how does the robot ensure that? It
bends on one side. So, when the robot bends on one side, when we walk, we bend on one side.
That is essentially ensuring that this point called the zero moment point is inside the foot,
so we do not fall. Now, that is the constraint. So, what is the way we solve this problem?
Basically, we assign frames, a global frame and a local frame to each of the joints.
Then what we do is, we find that if the robot has to move forward, there is a hip trajectory here
and there is a leg trajectory for the robot to go forward. And you can have infinite trajectories.
So, if it is going on 3D, what would happen is, we have to vary this trajectory
for different trajectories. For example, it is going up a hill or it is going down a hill.
What will happen is, these trajectories will vary. So, what we can do is, we can make a database,
okay. We can make a database by making the robot walk in different conditions.
And this is the database basically, which is saying what is the inclination of terrain,
what was the variation of angles, okay. And this is going to be a very, very large database.
And once you make the database, we have to learn it, okay. Now, to make the database
for each gate, we have to optimize. How do we optimize? We optimize by minimizing the energy.
So, we do energy minimization by doing the integral of torque into d theta. So, this is
energy minimum, okay. So, what I am saying here is that, what GA will do here again is,
suppose it is a flag down, it is very easy to understand. Let us look at this figure.
It is extremely easy to understand here. So, what GA will do is, it will fit different
trajectories, okay. So, GA will fit different trajectories and will compute torques at joints
by using dynamics, okay. Then it will say that this trajectory, it gives you the minimum torque.
That means, that is the energy optimal trajectory for this walk, okay. So, by doing that for
different terrain conditions, for example, going upstairs, going downstairs, going upside,
going downside, GA can find what are the optimal hip and foot trajectories,
energy optimal. Using that, it basically makes a database. This is the database,
okay, which is showing the turning angle, going up, going down, what is the various,
the various parameters of the leg trajectory and the hip trajectory.
Once it makes this database, it has to learn it, okay. So, it learns this database by using
some machine learning algorithms like neural net is example, deep learning is another one,
okay, support vector machine. So, this can all be used to just learn the database.
And once you learn the database, next you have to go. So, this is an example of where we have used
the wavefront planners. You have studied wavefront planners, it is like dropping a stone on a lake,
on the surface of a lake. What will happen? Waves will be formed and it is going to go out like
that. So, it is like saying the robot is starting from here and is following the waves which are
propagating in this direction. Now, we can say that the propagation of the waves can be a function
of the gradient. In the case of a surface like this, if there is a high gradient here, so we are
saying there is a gradient here. So, it is very high, the wave will not go in that direction,
it will go this side, that is expected. So, by making this kind of a graph or making
this kind of a surface, we can make the walk, make the robot walk using a wavefront propagator.
Say for example here, this is my wavefront arrival time, this is obstacles. So, in this case,
there is a ditch here, you can see there is a ditch. So, this ditch is coming up in the form
of a high potential here. That means the robot cannot, the wave will not go that side because
it is high. So, the wave which is propagating from here, this is my start point of the robot,
the wave is propagating this way. So, it will always try and keep at a low ground.
So, you can see here that by using the wavefront planner, the robot is walking.
So, here you can see the robot is walking from one point to another point,
simply by trying to follow the flat ground. It is exactly same as the wavefront planner that
we studied. So, the waves try to keep to a flat ground, they do not try to climb gradients.
So, this is a case of a biped robot walking on 3D terrain. Now, you can have a biped robot,
suppose this is a ditch. So, this place is a ditch. So, it should not go inside the ditch.
So, the ditch manifests itself by a very high gradient. So, the robot avoids that high gradient
and tries to find a location where it can cross by using the wavefront planner and then crosses
at that point and goes on the other side. So, this was the last class of the course
about motion planning. I hope that you have got an idea of robot motion planning,
especially if you are looking at applications of robots. And I would encourage you to take
other courses in robotics also, introduction to robotics to give you an introduction,
then AI and robotics. Now, I hope that you will be able to apply whatever you have learned in
this course and then either do research or if you are in industry to be able to use it in industry.
I hope this course has been useful. So, see you again in later courses. Thank you.
