There are a number of different ways to classify the robotics problems. Various features of a problem may determine which type of path planning strategy will work best. Two fundamental classifications suggested by Fu, Gonzalez, and Lee [1987, Pg.150] are Obstacle Constraint and Path Constraint. Obstacle Constraints indicate that there are some points in space which are already occupied, and are not free for the robot to pass through. Path Constraints are usually provided as points on a path which the robot must follow. From these two suggestions there is a control strategy diagram which may be drawn,
Figure 1.1 Control Strategies for Manipulators [Fu,Gonzalez & Lee,1987]
These basic strategies form the basis for most approaches to robotic path planning. Positional Control is a simple motion controller using joint interpolated motion, or point to point motion. Path Tracking is moving through a prespecified set of points on a path. All of the strategies in this diagram affect the methods used to plan paths, thus from this point it is best to discuss some requirements of the system.
Many authors suggest, in their papers, that there are a set of tasks to which a robot may be applied. The earlier work in Artificial Intelligence suggested many approaches to solving problems, which involves splitting them into tasks. It is relatively easy to list a few ’commonly expected’ path planning tasks for a robot.
- Grasping and Releasing objects.
- Following prespecified paths.
- Working with other manipulators.
- Exerting Forces (i.e.. pushing, pulling and holding).
Items on this list have been approached by various authors. A paper describing the integrated approach of all these items is yet to be seen, although some combinations have been documented. The ideal situation would be a good general method which incorporates all of these features.
Robots are machines, and as machines they are subject to all of the constraints of mechanics. Thus when dealing with many joints (prismatic or revolute) the physical limits of manipulator motion become evident. For the best solution, the limits of joint and actuator positions, velocity, acceleration, and jerk must be considered. The physical nature of the device also means that there are dimensions which must be considered, thus kinematics and collision avoidance come into play. When a robot makes any move, it expends energy to accelerate, hold and brake. This also means that the energy efficiency of the manipulator should be optimized, by reducing unnecessary expenditures of energy. Most importantly, if robots are to be cost effective, then their speed is of concern. In a high production situation, a cycle time that is 10% faster could save millions of dollars. Thus, time of path traversal can most often be the most important path planning factor.
- Velocity of Manipulator Links or joints.
- Joint Positions, Velocities, Accelerations and Jerks.
- Actuator Forces and Dynamics.
- Kinematics (this includes singularities).
- Time, when moving obstacles are involved.
Considering these factors, the problem may be formulated as a classical optimization problem, as many authors have done. These approaches usually produce good results, at the expense of computation time. Other methods are being found which trade off some of the completeness of the optimization to find solutions quickly.
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,
COST = Measurement of Performance + Motion Constraint + Torque Constraint
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.
It is valuable to have a number of criteria to determine the value of a path planning method. These values should reflect the information required, the time (and complexity) of the method, the type of results, and the level of abstraction from the manipulator.
GENERAL REQUIREMENTS EVALUATION CRITERIA:
- Dimensions of Space (2D, 2.5D, 3D)
- Collision Avoidance (None, Contact Detection, Proximity Calculation)
INFORMATION SETUP EVALUATION CRITERIA:
- Information Source (Knowledge Based, Sensor Based)
- Path Planning Strategies, for information passing (eg. Hierarchical)
- Path Planning Methods (algorithms used for path planning)
- Minimization (Which Costs are minimized?)
- Limits (Which limits are considered?)
- Solution type (Robot, Joint Space, Cartesian Space, Straight Line,
Via Points with Rotations, Splines, etc.)
IMPLEMENTATION EVALUATION CRITERIA:
- Execution (Time, Machine, Language)
- Testing (What are the experimental results?)
Most of these categories are quite basic, but some are not so clearly defined. All of these areas will be discussed in the subsequent sections.