page 706

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

	Goal	Trajectory	Manipulator	Motion
	State	Planner	Controller

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

page 707

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

page 708

Figure 3.3 World Modelling Techniques

2D or 3D WorkSpace

Array

Quad-Tree

Block =

Remove

Hole =

Balanced-Tree

CSG (Constructive

Polygons

Solid Geometry)