Version 1.0, August 31, 2001, Copyright, Hugh Jack 1993-2001
To aid the description of the path planning problem, a generalized statement of the optimization criteria will be given. This will be presented for both the Measure of Performance and Constraints. The first most important Measure of Performance is time for the path. To find this, and other factors, a number of relations will be derived. First assume that the path is made up of a number of discrete segments (trajectories). These segments are linked together to form the path of motion. Motion along the path will then have a few characteristics, and these provide the basis for some equations.
where: si = the ith segment of the path (i = 0 to n), (a vector trajectory)
P = the total path of n linked segments
vi = the velocity on the ith segment.
ti = the time to travel the ith path segment.
ei = the energy for the ith path segment
E = the total path energy cost (including kinetic, potential, friction).
Local Path Time: ti =~ si~ /~ vi~
Global Path Time: T = S ~ si~ /~ vi~
Global Path Length: D = S ~ si~
Feasible is defined as D, P, T, E are all non-infinite.
Local Optimization involves optimizing some function of si, vi & ei.
Global Optimization involves optimizing some function of T, D and E.
Collision avoidance involves altering si so that the path segments avoid obstacles. vi is used to produce the best velocity through a path segment. ei is a factor which is determined from energy input, less energy output (including friction loses). One, or any, of si, vi, ei, or n may be altered when attempting to find an alternate path. These are the only factors describing the path, and they may be found in various ways by themselves. The other factors involving forces, torques, and obstacle proximity must be determined in a similar way that is specific to the manipulator.
An example of how to derive, and apply, optimization techniques to an actual system is in order. To find a value for these parameters for a single link manipulator we would have to define a few variables
Figure 1.2 An Example Singe Link Manipulator
This is now a measure of performance for the path described by a set of angular velocities i (i = 0 to n). This is a global optimization setup for minimum energy input and minimum time (their exact weightings are determined by Pt & Pe). We could also express the path by a set of joint torques using the value ei. This leads to the problem of what do we do with limits on the system.
The limits on a system are a bit more arbitrary. In this case the manipulator may have a torque limit, and it has a definite position limit. To account for these, equality and inequality constraints may be used. It is best to use Equality Constraints for the motion limits here, so that the rotation may get very close, but not touch the ground. If the motion does violate this constraint, then the function will turn on and make the overall cost very high.
P∅ = Motion Penalty Coefficient
Motion Constraint = 0 (if 0° <= ∅ <=180°)
To compensate for the maximum torque here, an Inequalitry Constraint will be used, so that the torque avoids approaching the maximum torque value.
PΤ = Torque Penalty Coefficient
Torque Constraint = PΤ ∑(ei / Tmax)2
Every torque value is considered and if the torque approaches a maximum, then the torque constraint will grow considerably, and make the overall cost high.
To complete the description the optimization process will be described. The path could be split into 2 segments (n = 2), the first segment goes from 0° to 90°, the second segment goes from 90° to 180°. The process is simple, we choose start values for ∅′1 and ∅′2 (these will both be of the same magnitude, but opposite sign in this example). The next step is to calculate the value for cost,
We would continue choosing new values for ∅′1 and ∅′2 until COST has obtained a minimum value. This would provide an optimal path plan. The next factor of importance is to be able to express the difference between various path planning methods.