1.2 GENERAL REQUIREMENTS
The general requirements of a path planner are discussed in this section. Some of the factors involved in the application, and for evaluating their performance, are described. These factors do not include all the essential parts of a path planner, nor all of the possible requirements, but they provide a good idea of what the current requirements are.
1.2.1 PROBLEM DIMENSIONALITY
A problem may be represented in one of a number of different dimensions. The fewer the dimensions in the problem, the simpler the solution. A 2D problem is relatively simple, and good solutions already exist for finding paths in this representation. When height is added to the 2D obstacles, it becomes a 2.5D problem. This 2.5D problem is also within the grasp of current problem solving routines. When we try a 3D problem the problem starts to push the current limits of researched techniques and computational ability.
Figure 2.1 Dimensionality of Obstacles
1.2.2 2D MOBILITY PROBLEM
When a simple mobile robot has to navigate across a factory floor, it must solve the classic ’piano movers’ problem. This representation is easily done with convex polygons, and it runs quickly. This problem is referred to as the piano movers problem, because it involves having to move a very large object (like a piano) through a cluttered environment, without picking it up. The perspective is that, the obstacles can be seen from directly above, but they are assumed infinite in height. This method may be adapted for a robotic manipulator, if it is working in a clear workspace, and is performing pick and place operations. The use of this method will save time, in all applicable cases.
As a result of the speed benefit of the 2D path finding solutions, they may be used as analytical tools. A special property can make the 2D methods applicable to 3D problems. If a 2D view of a 3D work space shows a path, then the same path will also exist in the 3D workspace. This has been used in some path planning methods, and can provide a ’trick’ to avoid extensive 3D calculations. Another trick which may be used, is to represent the moving object with a box or a circle. This result in a simple technique for maintaining a minimum obstacle clearance, for collision avoidance.
Figure 2.2 Simplification of 3D Problem
1.2.2.1 - 2.5D HEIGHT PROBLEM
When height is added to 2D objects, it is no longer necessary to assume that they have an infinite height. It is equivalent to changing the view from looking straight down on the workspace to looking at it from an angle. This can allow some very simple path plans in which the manipulator is now allowed to move over and around objects. With pick and place tasks this can be the basis for a method which guarantees that the payload, and manipulator links, are above collision height. This is a very practical approximation that is similar to the manipulations which humans tend to favour (i.e. Gravity fed obstacles and objects).
This method is faster than 3D solutions, while still allowing depth in obstacles. Any object in the real world that does not have a vertical orientation will be very difficult to model. Despite this problem, this is still a very good representation for solving most pick and place problems (in an uncluttered workspace).
1.2.2.2 - 3D SPACE PROBLEM
When we have a cluttered 3D space problem, it may not be possible to resort to the use of 2D and 2.5D representations, if obstacles have irregular surfaces which may not be represented in 2D or 2.5D. This is the most frustrating problem. This problem has fewer simplifying restrictions, and as a result the dimensions grow quickly for every new factor.
The most devastating setback to the 3D methods occurs when a multilink manipulator is added, without any limiting assumptions. The addition of each manipulator link will increase the problem complexity geometrically. This method may be simplified when spheres are used to represent moving obstacles.
The most successful attempts at solving this problem have been the optimization attempts. Optimization methods are typically slow, and thus the three dimensional path planning problem will have to be solved off line for now. If a good fast solution is discovered for this problem, it will eliminate the need for the 2D and 2.5D problems.
1.2.3 COLLISION AVOIDANCE
Collision detection is the most important factor of Path Planning. Without automatic collision avoidance, the robotic workcell must be engineered to be collision free, or sub-optimal paths must be chosen by a human programmer. Local Collsion Detection is important when moving through an unknown, or uncertain environment. These allow for feedback to the planner, for halting paths which contain collisions. Global Collision Avoidance may be done for planning paths which should avoid objects by a certain margin of safety. The actual detail of the method may vary, but moving close to obstacles is avoided by these methods.
Figure 2.3 Collision Avoidance
1.2.4 MULTILINK
One problem that tends to paralyse most methods is the expansion to multilink systems. The first implementation of most techniques is made with a simple mobile robot. When the method is increased by adding oddly sized links, and then a payload, the complexity grows at a more than exponential rate.
The number of degrees of freedom also play in the applications of the robot. If a manipulator has 6 degrees of freedom, then it can obtain any position or orientation in space. Some specific cases of problems require only 3 or 4 degrees of freedom. This can be a great time saver. When an environment becomes cluttered then it may be desirable to have a higher number of degrees of freedom than six, so that the redundancy of the robot can move through the environment. The complexity of most routines increases exponentially with the number of degrees of freedom, thus it is best to match the manipulator degrees of freedom to the complexity of the task to be done.
One assumption that helps reduce the problem complexity is the approximation of motion in a single plane. The net result of this effort is that the robot is reduced to 2 or 3 degrees of freedom. The payload may also be neglected, or fixed, and thus the degrees of freedom are reduced. A second approach is to approximate the volume of the links swept out over a small volume in space. This volume is then checked against obstacles for collisions. A payload on a manipulator may sometimes be approximated as part of the robot if, it is small, or it is symmetrical. This means that the number of degrees of freedom for a manipulator may be reduced, and thus the problem simplified in some cases.
Figure 2.4 Multi-Link Approaches
Multilink manipulators also come in a variety of configurations. These configurations lend themselves to different simplifications, which may sometime provide good fast solutions in path planning.
- Cartesian (i.e. X, Y, Z motions)
- Cylindrical
- Spherical (Stanford Manipulator)
- Revolute (Like Human arm)
- Scara
The various robot configurations are fundamentally different. Many approaches have tried to create general solutions for all configurations, or alternate solutions for different specific manipulators. The fastest solutions are the ones which have been made manipulator specific. With a manipulator it is also possible to describe motions in both Joint Space (Manipulator Space), and Cartesian Space (Task Space). There are approaches which use one, or both of these.
1.2.5 ROTATIONS
Rotations are another problem for some path planners. It can be difficult to rotate during motion, thus some will not rotate, some will rotate only at certain ’safe’ points, and some will rotate along a complete path. The best scenario is when rotations may be performed to avoid collisions, and not just to meet the orientation of the goal state.
Figure 2.5 Payload Rotation
1.2.6 OBSTACLE MOTION PROBLEM
Motion of obstacles can cause significant path planning problems. Motion occurs in the form of rotation, and translation. In most path planners the only motions considered are for the payload and manipulator. In most cases an obstacle in the environment will experience both rotation and translation. This has devastating effects on all of the path planning methods, because some tough new requirements are added. The path planning systems must now incorporate a time scale factor, and keep an object description which includes a position, a velocity vector, and rotation vector. The method must also do the calculations to detect collisions and status at every instant of time as the system changes. With simplifications the problem may be reduced to a more manageable level. Obstacles may be categorized into motion categories; Static (un-moving), Deterministic (has predictable occurrence and positions), and Random (Freely moving, with no regular occurrence). All of these are of interest because most parts fixed in a workcell are Static, workpieces from feeders and conveyors are Deterministic, and human intruders are Random. Random obstacle motion usually occurs so quickly that path planning may only be able to escape the path of the obstacle, not compensate it. These motion strategies are often considered in the static and cyclic states, but the Random solutions are not implemented widely, except as safety measures.
Figure 2.6 Obstacle Motion Types
1.2.7 ROBOT COORDINATION
If only a single robot may be used in a workcell, then bottlenecks will soon arise. When two robots are placed in close proximity, they can produce more bottlenecks, thus they must be given some scheme for avoiding each other. If these robots are to cooperate then a complete and integrated cooperation strategy is required. These strategies require some sort of status link between both manipulators. To make sense of the status of the other robot, it is also necessary to have algorithms for path planning in the Deterministic environment. This algorithm relies upon a proper moving obstacle path planning scheme being developed first. It is possible to use assumptions, or an engineered environment to allow robot coordinations, without the extensiveness of a complete coordination algorithm.
Figure 2.7 Multi-Robot WorkSpaces
1.2.8 INTERACTIVE PROGRAMMING
One factor that is now available for all commercial robots is the ability for the human user to plan the path. This may be done with a special graphical program, or by moving the robot and setting points, or by entering sets of points. These methods are proven, and do work, but they are very inefficient, inflexible, and prone to errors. Thus the thrust of this paper will be to ignore the interactive approach, because automated path planning is much more desirable. The interactive approach will almost guarantee that an operator will not find an optimal approach. Finding a good path is not possible without having to stop the robot and lose production time.
