1.1.1 ROBOT APPLICATIONS

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.

- Moving from place to place.

- Following prespecified paths.

- Following moving objects.

- Working with other manipulators.

- Exerting Forces (i.e.. pushing, pulling and holding).

- Exert Torques.

- Collecting Data.

- Using tools.

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.

 

1.1.2 ROBOTIC CONSTRAINTS

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.

 

MEASURES OF PERFORMANCE:

- Time for Path Traversal.

- Velocity of Manipulator Links or joints.

- Energy.

- Actuator Forces.

- Proximity to Obstacles.

CONSTRAINTS:

- Joint Positions, Velocities, Accelerations and Jerks.

- Actuator Forces and Dynamics.

- Kinematics (this includes singularities).

- Collisions with Obstacles.

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

 

1.1.3 THE OPTIMIZATION PROBLEM OF PATH PLANNERS

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

D = the total path distance

vi = the velocity on the ith segment.

ti = the time to travel the ith path segment.

T = the total path time.

ei = the energy for the ith path segment

E = the total path energy cost (including kinetic, potential, friction).

 

Local Path Time: ti =˜ si˜ /˜ vi˜

 

n

Global Path Time: T = S ˜ si˜ /˜ vi˜

i=1

 

Local Path Length = ˜ si˜

 

n

Global Path Length: D = S ˜ si˜

i=1

 

Local Energy Input = ei

 

n

Global Energy Input: E = Σ ei

i=1

 

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°)

= P∅ (if 180° <= ∅ <= 0°)

 

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

n

Torque Constraint = PΤ ∑(ei / Tmax)2

i=1

 

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.

 

1.1.4 EVALUATION OF PATH PLANNERS

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)

- Multilink Manipulators

- Rotations of Payload

- Moving Workspace Obstacles

- Multi Robot Coordination

- Degree of Automation

INFORMATION SETUP EVALUATION CRITERIA:

- Information Source (Knowledge Based, Sensor Based)

- World Modelling

METHOD EVALUATION CRITERIA:

- Path Planning Strategies, for information passing (eg. Hierarchical)

- Path Planning Methods (algorithms used for path planning)

- Internal Representations

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