As a result of the numerous approaches to the path planning problem that have arisen, a basic knowledge is critical to an overview of the field. The best way to start this section is with a brief definition of strategies, and then a brief explanation of the popular approaches (some specific methods are detailed in the appendices). Even though the system design strategies are not a direct part of path planning, they have a profound impact on the operation of the path planner.

40.4.1 PATH PLANNING STRATEGIES

40.4.1.1 - BASIC PATH PLANNERS (A PRIORI)

Path planners typically use environmental information, and initial and goal conditions. Through algorithmic approaches, the path planners suggest a number of intermediate steps required to move from the initial to the goal state. The path may be described by discrete points, splines, path segments, etc.. Each of the path segments describe a location (or configuration) and rotation of the manipulator and payload. These can be furnished in a number of ways, as joint angles, cartesian locations of joints, location of payload, as a series of relative motions.

40.4.1.2 - HYBRID PATH PLANNERS (A PRIORI)

A newer development is the possibility of hybrid path planning. In this mode a combination of path planning methods would be used to first find a general path (or set of paths) and then a second method to optimize the path. This method is more complex, but has the potential for higher speed, and better results than a single step method.

This strategy may use methods based on alternate representations (like those in figure 3.4). Some common methods in use are Separation Planes, Bounding Boxes, Bounding Polyhedra, 2D views of 3D workspaces, tight corner heuristics, backup heuristics, etc. These are some of the techniques that may be used to refine and produce better paths.

40.4.1.3 - TRAJECTORY PATH PLANNING (A POSTIERI)

The amount of knowledge which a path planner has may be very limited. If the robot has no previous knowledge of the environment, then information must be gathered while the robot is in motion. Trajectory planners rely on feedback for finding new trajectories and detecting poor results. Contact or distance sensors are used to detect an obstacle and the manipulator trajectory is altered to avoid collision. This method will typically guarantee a solution (if it exists or if it does not encounter a blind alley), but at a much higher time cost, and a longer path. The collection of current data becomes critical when dealing with moving obstacles, that do not have a periodic cycle. This method may also be tested by simulation as suggested by K.Sun and V.Lumelsky [1987], who developed a simulator for a sensor based robots.

For the purpose of clarifying this subject a special distinction will be drawn between a path and a trajectory. When discussing a path, it will refer to the complete route traced from the start to the goal node. The path is made up of a number of segments and each of these path segments is continuous (no stop points, or sharp corners). Another name for a path segment could be a trajectory. This distinction is presented as being significant, by the author, when considering a trajectory planner, which basically chooses the locally optimum direction, as opposed to a complete path. Only some path planners use trajectory based planning, which is easier and faster to compute, but generally produces sub-optimal paths.

40.4.1.4 - HIERARCHICAL PLANNERS (A PRIORI & A POSTIERI)

If the best of both controllers are desired in a single system, it is possible to use a high level A Priori planner to produce rough paths, and then use a low level A Postieri planner when executing the path. This would make the planner able to deal with complex situations , and the ability to deal with the unexpected. This also has the ability to do rough path planning in the A Priori level, and let the A Postieri level smooth the corners.

40.4.1.5 - DYNAMIC PLANNERS (A PRIORI & A POSTIERI)

Dynamic Planners are a special mixture of an A Priori Path Planner and A Postieri Motion controller for a manipulator. The A Priori Path Planner could plan a path with limited or inaccurate information. If during the execution of this path, a sensor detects a collision, the the A Priori Path Planner is informed, and it updates its World Model, then finds a new path. To be more formal, the dynamic Planner is characterized by separate path planning and execution modules, in which the execution module may give feedback to the planning module. This is definitely a preferred path planner for truly intelligent robotic systems. Some dynamic planners have been suggested which would allow motion on a path, while the path is still being planned, to overcome the path planning bottle neck of computation time.

40.4.1.6 - OFF-LINE PROGRAMMING

One strategy that has become popular is the Off-Line Programmming approach. When using Off-Line Programming we will take an environmental model, which allows human interaction and graphical simulation to model the robot. Via the tools, the human may produce optimal paths in a combination of human intelligence and algorithmic tools. This is best compared to a CAD package that allows modelling of the robot and the work cell. Once the modelling has been completed, a various assortment of tools are available to plan manipulator motions inside the workcell. This allows rearrangements of obstacles in the workcell, and optimization of robot motions and layout. This sort of software package may be used in a number of modes. The Off-Line Program may interactively calculate, and download, a path which directly drives the robot. The Off-Line Program may also create a path for the manipulator, which includes programming like directions (J.C.Latombe, C.Laugier, J.M.Lefebvre, E.Mazer [1985]). In the Off-line programming mode the results are usually slower, in the order of minutes for near optimal path generation. This time is acceptable when doing batch work, and setups for large production runs. If the Off-line program cannot find an optimal path before the previous tasks have completed, the workcell will have to halt. The most important aspects of the Off-line programmer is the World Modeller and Graphical Interface.

An Off-line programmer was discussed by A.Liegeois, P.Borrel, E.Dombre [1985]. The authors approach was to use a CAD based approach with graphical representation and collision detection, then convert the results to actual cartesian or joint coordinates.

40.4.1.7 - ON-LINE PROGRAMMING

The previous Off-line Programming method allowed a mix of human interaction and A Priori path planning in a modelled environment. The same concept is possible, with human interaction and the A Postieri path planning. This is On-Line programming, because there are no graphical simulations in this strategy, the actual robot is used. On line programming allows the user to directly enter robot motions and directly verify their safety and use tools to optimize the path. This is not desirable for path planning because it is time consuming and inflexible, this is similar to the original method of robot programming with set via points.

40.4.2 PATH PLANNING METHODS

The most complete approach to path planning is Optimization. Optimization techniques may be done on a local and global basis. Through the calculation of costs, constraints, and application of optimization techniques, an optimal solution may be determined. Some of the mathematical methods used for the optimization technique are Calculus of Variations, Trajectory optimization (hit or miss shoot for the goal state) and dynamic programming. The most noticable difference between Local and Global optimization is that Local optimization is concerned with avoiding collisions (it will come very close), and global optimization will avoid objects (make a wide path around, when possible).

The most intuitive approach is the Spatial Relationships between Robot and Obstacles. This approach uses direct examination of the actual orientations to find distances and free paths which may be traversed. It was suggested by Lozano-Perez (1983) that spatial planning "involves placing an object among other objects or moving it without colliding with nearby objects". There are quite a few methods already in existence.

The Transformed Space solutions are often based on Spatial Planning problems, they are actually attempts to reduce the complexity of the spatial planning problems by fixing the orientations of objects. These problems diverge quickly from spatial planning when they use tranformed maps of space. When space is transformed, it is usually mapped so as to negate the geometry of a manipulator. The best known approach is the Cartesian Configuration Space Approach as discussed by Lozano-Perez [1983]. These techniques have different approaches to representing the environment, but in effect are only interested in avoiding objects, by generating a mapped representation of 'free space' and then determining free paths with a FindPath algorithm.

An alternative to the previous methods are the Field methods. These methods impose some distributed values over space. The Potential Field method is a technique similar to Spatial Planning representations. This involves representing the environment as potential sources and sinks and then following the potential gradient. This technique is slow and tends to get caught in Cul-de-sacs. The Gradient method is very similar to the Potential field method. It uses distance functions to represent the proximity of the next best point. This method is faster than the Potential field method, and it gets caught in Cul-de-sacs.

An approach which is beginning to gain popularity is the use of Controls Theory for path planning. This was done, very sucessfully, by E.Freund and H.Hoyer [1988]. This approach allows the non-linear control of a robot, which includes the collision avoidance for many moving objects, mobile robots, manipulator arms, and objects that may have a variable size. This approach seems to have great potential for use in low level control, in the A Postieri sense.

To be complete, there are some techniques that are uncommon (like path planning with simulated anealing S.Kirkpatrick, C.D.Gelatt, M.P.Vecchi [1983]), or are still in their infancy (like the controls approaches). To cover these there will have to be a New and Advanced Topics classification. This does not indicate a shortcoming in the representations, but a lack of definition in the areas included.

40.4.3 OPTIMIZATION TECHNIQUES

40.4.3.1 - SPATIAL PLANNING

40.4.3.2 - TRANSFORMED SPACE

40.4.3.3 - FIELD METHODS

40.4.3.4 - NEW AND ADVANCED TOPICS

40.4.4 INTERNAL REPRESENTATIONS

Most problem solving techniques need some internal method of dealing with the problem. These methods all have their various advantages. Most of these internal representations depend upon the method of world modelling used in the setup. These may be converted inside the program. There are factors to consider when choosing between various internal representations. For example if arrays are used they are very large and, the updating procedure is very slow, but the lookup is very swift. This technique is of best use when, the obstacles do not move, and the arrays are set up off-line to be used on line. With the current advances in computer hardware (i.e.. Vector Processing and Memory) special hardware may become available that will make the arrays based methods very fast, thus they should not be discarded, but shelved.

The next technique of interest is lists. These are mainly an efficient way to store linked data. This may vary from an oct-tree representation of some object to a simple list of boxes in space. These are efficient with space, but there is storage overhead, and lookups are slower than the array.

Functions are very space efficient, but they are subject to inflexibility. Functions may represent a variety of execution speeds from quite fast for a simple problem to very slow for a complex problem. It should be noted that functions may grow exponentially with increased environment complexity. This function should be used with discretion.

40.4.5 MINIMIZATION OF PATH COSTS

Each path has some features which affect the cost. As was described earlier the costs are time, velocity, dynamics, energy, and proximity to obstacles. A basic statement of the goal is given, and this should be used when formulating a complete Measure of Performance function or algorithm.

"The manipulator should traverse the path in the least amount of time, with reasonable forces on the manipulator, using a reasonable amount of energy, and not approachnig obstacles too closely."

40.4.6 LIMITATIONS IN PATH PLANNING

"The Kinematic, Dynamic and Actuator constraints of the manipulator should not be exceeded, and obstacles should not be touched."

This is worded arbitrarily, because of the variations in different manipulators. If this statement is followed in essence, then the limits will be observed. Consideration of this statement will aid when creating a Constraint function or algorithm for a robot path planner.

40.4.7 RESULTS FROM PATH PLANNERS

The results from path planners tend to come in one of a number of simple forms. The actual numbers may represent joint or cartesian locations. These may be used in various ways to describe a path; Splines, Functions, Locations, Trajectories, and Forces. This area is not of great importance because the problems have been researched, and it is easy to convert between the path planner results. The only relevence of this area is that results are ussually expressed in a form preferred by the path planning method.

40.4 METHOD EVALUATION CRITERIA