1.3.1 INFORMATION SOURCE

The sources of information, which a path planner uses, will have a fundamental effect upon how a path is planned. This is a problem, in how the information is collected. Data may be collected before or during the execution of a path. This means data may be presented in the form of an known obstacle (and position), or by a simple indication of contact. These tend to draw distinctions between methods which have Collision Detection (Local or Trajectory Path Planners) and those which have obstacle information (Global Path Planners).

1.3.1.1 - KNOWLEDGE BASED PLANNING (A PRIORI)

It is much easier to solve a problem if all the information is available at the beginning of the solution. In robotics we may plan paths before their execution, if we have some knowledge of the environment. This is strictly a ’blindly generate’ type of strategy that trusts the knowledge of the environment provided. Planning paths before execution allows efforts to get a shorter path time, more efficient dynamics, and absolute collision avoidance. When working in this mode a priori knowledge (i.e. Known before) is used. Techniques are available to solve a variety of problems, when given the a priori information. Some of the knowledge which we use for a priori path planning may come from vision systems, engineering specifications, or CAD programs.

A Priori Knowledge may be applicable to moving objects, if they have a predictable frequency or motion. A Priori knowledge may not be used for unpredictable or random motion, there is no detection method allowed by its definition.

A Priori Knowledge may be derived from modelling packages or High Level Sensors. These sensors are slow and typically drive a World Modeller in an Off-line programmer. The best example of this type of sensor is the vision systems. This system is the most desired information collector for robotics in the future. This system would provide a complete means of world modelling for the path planner. Another common detection system currently in use is the Range Imaging System, which use stripes of LASER light to determine geometry of objects. One example of this is the use of the system to recognize objects and use the geometrical information to determine how to grasp the object [K.Rao, G.Medioni, H.Liu, G.A.Bekey, 1989]. Some of these sensors require knowledge from the world modeller for object recognition purposes. In general these sensors are slower because of their need to interpret low level data, before providing high level descriptions.

 

Figure 3.1 A Priori Path Planning

 

1.3.1.2 - SENSOR BASED PLANNING (A POSTIERI)

Sometimes information is not available when we begin to solve a problem, thus we must solve the problem in stages as the A Postieri information becomes available. Sensor based planning is an indispensable function when environments change with time, are unknown, or there are inaccuracies in the robotic equipment. A Postieri Knowledge may be used to find the next trajectory in a path (by collecting information about the outcome of the previous trajectory) or even be used strictly to guide the robot in a random sense when exploring an environment. These techniques correspond to an execute and evaluate strategy.

This information feedback is acquired through a set of different sensors. The sensors used may range from vision systems to contact switches. These low level sensors are not very sophisticated, but their low cost makes them very popular. These sensors will typically detect various, expected, conditions. Good examples of these sensors are Position Encoders and Contact Switches. The Sensors can return a signal when contact is made with obstacles, or measure a force being applied. When used in a feedback loop, they may provide actual joint position for a position control algorithm. High level sensors also have the ability to provide low level data, and may be used to detect events. Such Low Level information from this system could also be used to check for collisions while in motion, and detect moving objects. Quite naturally the extent to which this information is collected, determines how the path planner will work.

The ultimate robot would use these sensors to gather information about the environment, and then plan paths and verify information during execution. But this raises the point that a mixture of both of the a priori and a postieri methods must be mixed to make a more dynamic planner. This especially critical when dealing with motion, either to coordinate with regular motion, or to detect and deal with un-predicted motion. Some good papers have already been written on path planning in the A Postieri mode.

 

Figure 3.2 A Postieri Path Planning

 

1.3.2 WORLD MODELLING

How the world is modelled can make a big difference to the path planning strategy. Some of the assumptions about the world are that all obstacles are solid and rigid. Solid is assumed so that collisions will occur on contact. Rigid is assumed so that deformations do not occur on contact. The objects must be represented with some sort of method. Some of the various methods are Polygons, Polyhedra (constructed with 3D polygons), Ellipsoids, sets of points, analytic surfaces, Arrays, Oct-trees, Quad-trees, Constructive Solid Geometry (CSG), and Balanced Trees. The method chosen can limit the use of complex shapes. Some methods are very receptive to data acquired through sensors and CAD systems.

The most common method of representing objects (in all dimensions) is with convex polygons. These are ideal when working with flat surfaces in the real world. Curved surfaces use flat polygons to approximate their surfaces. One factor that makes the polygons an excellent representation is that if a point is found to lie outside one wall of a polygon, then it may be declared to be outside the entire polygon. Most methods do not allow for concave polygons, because they are much more difficult to deal with, in computation. The way to over come this is to use overlapping convex polygons, to represent a concave polygon. These types of representations can typically be derived from most CAD systems. This form allows easy use of existing facilities.

Arrays are good when fast recall of information from a map is required. The set up time for an array is long, the memory required is large, and algorithms are slow. This is a more intuitive approach, but it is also not very practical with present equipment. Quad-trees (for 2D) and Oct-trees (for 3D) are excellent representations for the work space. These allow the workspace resolution to vary, so that empty space in the work cell does not waste space in the representation. The disadvantage to these techniques is their complexity can slow down access times. An enhancement to the Quad-tree and Oct-Tree structures which represent space with blocks and cubes, is a balanced tree which will use non-square rectangles to represent space. This could potentially save even more memory than the other methods, but the routines would again make the access time even slower.

The most powerful method of representation available is CSG (Constructive Solid Geometry). This allows objects to be created by performing boolean operations with geometrical primitives. The original design is done quickly, the object is very space efficient, represents complex surfaces easily, but it is very quite complicated to use. One method discussed is the use of bounding boxes for the different levels of an object’s design tree. A discussion was given by A.P.Ambler [1985] about using Solids Modelling with robotics. The thrust of this paper was the different operations, communications, and information which a solids modeller would have to handle to drive a robotic system. This paper proposes a good setup for an Off-Line Programming Package.

It should be noted that sometimes information is given to the world modeller in an awkward form. This information may be represented in another way, or interpreted to make sense of the information. Spatial Planes can be used to establish spatial orientation. Bounding Boxes and Bounding Polyhedra may be used to approximate complex surfaces so that they may be stored in a smaller space, and be easy to use by most algorithms.

Figure 3.3 World Modelling Techniques

Figure 3.4 Modelling Approximation Techniques