page 710

40.4.1 PATH PLANNING STRATEGIES

A path may be planned and executed in a number of different ways. The most obvious is the direct method of planning a path and then excuting it. This section will attempt to introduce some of the abstracts behind the strategies of path planners.

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.

Figure 4.1 Basic Operation of a Hybrid Path Planner

goal	goal
start	start
First Pass (General Path)	Second Pass (Optimal Path)

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

page 711

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.

page 712

Figure 4.2 A Hierarchical Planner (and an Example)

Goal			Motion
State	Path	Trajectory
			Manipulator
	Planner	Planner	Controller
	World
	Modeller	A Priori Path	A Postieri Path
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.

page 713

Figure 4.3 Dynamic Path Planning

	Goal	Path	Manipulator	Motion
		Planner	Controller
	State
		World
		Modeller

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.

At present Off-Line programmers are possible, and there are many good graphical and path planning methods available in construction of these packages.

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