11re Internztianal Journal of

Int J Adv Manuf Technol (1993) 8:227-234 (~ 1993 Springer-Verlag London Limited

Itdvanced

manufacturino Technologu A Formulation for Collision Identification and Distance Calculation in Motion Planning Using Neural Networks Z. Dong and J. Yuan Department of Mechanical Engineering. University of Victoria, Victoria, Canada

The collision identification and object-to-oblect distance calculation play an important role in the motion planning for robots and manufacturing facilities. A formulation for collision identification and distance calculation in motion planning, using neural networks, is presented. The method calculates the distances between the vertices of an object and the given polyhedral obstacles using the modified Hamming net. This formulation is derived from the homogeneous geometric transformations. The method can be used to identify collision between the vertices of a moving object and the obstacles, to calculate the distance and interference between the moving object and the obstracle, and to find the optimal direction for collision removal. The parallel computation formulation is simple in form, and can be extended to line-to-object and object-to-object collision identification and distance calculation. The method can considerably decrease required computation time, and has the potential for being applied to on-line trajectory planning. Keywords: Collision

identification; Distance Motion planning; Neural networks; Robotics

1.

calculation;

Introduction

In computer automated manufacturing, collision-free trajectory planning is central to programming robots, CNC machine tools, and many other manufacturing facilities. In practice, the collision-free trajectory of a moving object is often generated by identifying a series of collision-free discrete locations of the object in a given workspace with obstacles. Through these discrete locations, a trajectory that connects the given initial and final locations uf the moving object is generated. The trajectory is often specified using a curve function, and satisfies the minimum distance or minimum energy criteria. Generation of the collision-free discrete

Accepted for publication: 14 May 1992 Correspondence and offprint requests to: Dr Zuomin Dong, Department of Mechanical Engineering, University of Victoria, PO Box 3055, Victoria BC V8W 3P6, Canada.

locations requires the identification of possible interferences between the moving object and the obstacles along its moving path, and the calculation of the distances (or amounts of interference) between the moving object and the obstacles at any instance. Without an efficient method for identifying the interferences and for calculating the distances and amounts of interference, generation of a collision-free trajectory becomes impossible. In addition, the collision identification and distance calculation have been recognised as occupying most computation efforts in trajectory planning, and forming the bottleneck for enhancing motion planning strategies [1,

2]. The applications of intelligent robotic and manufacturing systems working in an unstructured and time-varient work environment further require the on-line motion planning capability. The unstructured environment includes workspaces under the ocean and in space. The time variant workspace exists in small batch manufacturing. In these applications, the work environment is either not known beforehand, or keeps changing constantly. The efficient on-line environment perception and on-line motion planning methods become critical. Research on efficient collision identification and distance calculation methods has gained considerable attention in recent years. These approaches can be classified either by the method of distance calculation or by their underlying principles. In terms of the method of distance calculation, existing distance calculation approaches can be characterised as vertexbased approaches [3, 4], surface-based approaches [5], and convex object-based approaches [2, 6-8]. In terms of the underlying principles, the research can be classified into three major categories: forbidden region identification methods [3], swept volume methods [9-12], and constrained distance minimization methods [1, 2, 13}. In this work, a new formulation for collision identification and distance calculation in motion planning, using neural networks, is introduced. The method calculates the distances between the vertices of a 3D moving object and the given 3D polyhedral obstacles using the modified Hamming net formulation. The distance calculation allows a possible collision to be identified and provides a quantitative measure of interference when collision occurs. This formulation is derived

228

Z. Dong and J. Yuan

from the homogeneous geometric transformations of rotation and translation among the local coordinate frames of the obstacle plane boundaries. The formulated calculation is simple in form and can be easily implemented. The modified Hamming net inherits the architecture of neural networks, and supports parallel processing for object-to-obstacle distance calculation. Extension of the formulation to line-to-object and object-to-object collision identification and distance calculation are also discussed. The method can considerably decrease required computation time, and has the potential for being applied to on-line trajectory planning. Combined with the online environment perception research currently conducted at the University of Victoria, the method provides an essential on-line decision-making function for intelligent robotic and manufacturing systems. This work focuses on the collision identification and distances calculation problems of convex polyhedral objects. The method can be easily extended to non-convex polyhedrons, and objects with cylindrical, spherical and sculptured surfaces. The paper first reviews the previous work and advances in developing efficient methods for identifying collision, and for calculating the distances between moving and fixed objects. Three frequently-used methods, including forbidden region identification, swept volume, and constrained distance minimisation, are dicussed. Applications of these methods to collisionfree trajectory planning is briefly summarised. The architecture and applications of Hamming net type neural networks are outlined. The formulation of point-to-polyhedron distance calculation in neural network form, based on the homogeneous geometric transformations of rotation and translation among introduced local coordinate frames of given obstacles, is presented. The formulated point-to-polyhedron distance calculation is later extended to handle the line-to-polyhedron and polyhedron-to-polyhedron distance calculation for robot and manufacturing facility trajectory planning. An example is used to illustrate the proposed approach.

2.

Background

In the early work of trajectory planning, collision-free trajectories of a moving object in a workspace with polyhedral obstacles were generated by identifying the forbidden regions of the workspace [3]. These forbidden regions are generated by growing the boundaries of the given obstacles with the volume of the moving object. In the transformed workspace of forbidden regions, a collision-free path is generated by creating the shortest path around the forbidden region connecting the initial and destination locations. This shortest path is created using a search on the visibility graph, which is built based on the visibility information on each corner of the forbidden regions. The limitation of this approach is the lack of quantitative measure of object-to-obstacle distance as protocol for optimal trajectory generation. Concurrent to the forbidden region identification method, the swept volume approach to collision-free trajectory planning was introduced [9]. In this approach, the 3D volume swept out by the moving object along a proposed trajectory, is generated. Algorithms similar to those used in Boolean

operations are used to identify interference between the swept volume and the obstacles. An alternative path will be proposed when interference is identified. An inherent drawback of this approach is its intensive computation load. On the other hand, a major advantage of this approach is its capability for providing a dynamic interference check over a continuous path, rather than a static interference check over a number of discrete locations (as used by the other two methods). Continuous efforts have been made to improve this approach [10-14]. Recently, the constrained distance minimisation approach for collision identification and distance calculation was introduced. The approach calculates the object-to-obstracle distance by minimising the distance between two free points, one on the object and one on the obstacle. Collision is identified when the object-to-obstacle distance becomes zero. The gradient projection method was first applied to the optimisation [1]. The method was improved by applying the efficient quadratic programming, and by incorporating the quantitative interference calculation using a heuristic approach of m ov e bac k and s hr i nk -r obot [2]. An effort to combine the constrained distance minimisation and the swept volume methods was also made to obtain the advantages of these two methods [13]. The constrained distance minimisation approach showed improvements on computation time requirements over the swept volume approach, and the potential for handling large objects without significantly increasing computation time. However, trajectory planning is normally aimed at minimising travel distance or energy consumption of a robot, and formulated as a constrained optimisation problem with collision avoidance constraints. The collision avoidance constraints are evaluated by calculating the object-to-obstacle distances. A complex nested optimisation problem will be created if the constrained distance minimisation approach is used for collision identification and distance calculation. This drawback of the constrained distance minimisation approach introduces computation complexity, and makes it difficult to apply to real-time trajectory planning.

3. Collision Identification and Distance Calculation In this work, the collision identification and distance calculation between a moving object and obstacles in its workspace are conducted using convex polyhedron object models and neural networks. The collision identification (or interference checking) method, based on the vertices of the moving object, using the point-to-object distance calculation is first introduced. The method is later extended to consider the boundary edges of the moving object, using the line-to-object distance calculation. Further extension of the method to directly handle two polyhedrons is briefly discussed. The discussion on pointto-point distance calculation begins with the mathematical formulation using geometric transformations, and then focuses on the formation of an appropriate neural networks - the modified Hamming net, based upon this formulation.

Motion Planning Using Neural Networks

3.1.

Required Information for Trajectory Planning

When the vertices of the moving object are used to check whether the object interferes with surrounding obstacles, the relative locations of each vertex to these obstacles need to be calculated. Specifically, the following information is required for trajectory planning: Is a point p in the Euclidian space (any vertex of the moving object) inside or outside an obstacle? How far away is the point from the obstacle (boundary), if no interference occurs (or if p is outside the obstacle)? How much interference is there and in what direction should the point p be pushed out, if interference does occur (or p is inside the obstacle)?

3.2 Point-to-Object Distance Calculation Using Geometric Transformations Based upon the convex polyhedron assumption, an obstacle is modelled by the union of the half-spaces that are defined by the boundary planes of the object. A typical convex polyhedron obstacle is shown in Fig. 1. This assumption can be extended to more general objects, since a non-convex object can be considered by constructing combinations of convex polyhedrons. In addition, cylindrical, spherical and sculptured objects can also be modelled based upon the polyhedron assumption, since cylindrical, spherical, and sculptured surfaces can always be represented by many plane surface patches based upon the required resolution. The object of this work is to develop an efficient method for calculating the distance between a point, which represents a vertex of the moving object, and a convex polyhedron, which represents an obstacle (or part of the obstacle) in a workspace. The formulation starts by attaching a local Cartesian coordinate frame to each of the N boundary planes of a

fk-1

fJ~/

f k

J

Z~

polyhedron as illustrated in Fig. 1. Each coordinate frame, {xi, Yi, z~} (i = 1. . . . . N), has the x and y-axes laid within the boundary plane, the z axis along the direction of the surface normal (pointing toward the outside of the object), and the centre of the coordinate frame placed anywhere within the boundary of the plane. On the other hand, the trajectory of a vertex of the moving object or all vertices of the moving object at given trajectory locations can be represented by a group of points f/ = [fx, fy, f ~ ] f ( j = 1 . . . . . K). Each of these points can be represented either in the global Cartesian coordinate {X, Y, Z) or in the local coordinate frames of the obstacle boundary planes {x. Yi, Zi}. In order to examine the relation of point representation between the global and local coordinate frames, we designate L representing a local coordinate frame and G representing the global coordinate frame. A vertex point with the global coordinates { X , Y , Z ) can be represented as c f = c[fx, fy, fz] r with respect to the global coordinate frame G, and Lf = L[fx, f>., fz] r with respect to the local coordinate frame L. According to the theory of geometric transformation, the representation of a point in one coordinate system can be transferred into a representation in a second coordinate system by applying a series of geometric transformations. These transformations actually align the first coordinate frame with the second coordinate frame through a series of translations and rotations, and can be represented as: (1)

L f = L R C;,f + L t or,

fy fz

=

VI

V2

I) 3

X

-]-

tv

W1 W2 W3

where, Lt is the offset vector representing the translation required for overlapping the centres of the two coordinate frames, and LR is the rotation matrix representing the rotations required for aligning the coordinate axes. In this work, we are only concerned with which side the point is located in the halfspace, and the distance from the point to the boundary of the halfspace. In other words, only the z-values in the N local coordinate frames are of interest. Equation (1) can thus be simplified to: Lfz = C'f.~w, + Cfyw2 + c'f~w 3 + t~

f l "/

Z2

3

x2

u

t

229

(2)

In this simplified equation, the leading superscript L and leading subscript G of Wk and tz have been dropped for clarity of expression. Using this equation, the relative position of the vertex point to the obstacle plane boundary can be calculated.

x3

4. Collision Identification and Distance Calculation Using the Modified Hamming Net X Fig. l. A polyhedron obstacle and global/local coordinate frames.

This section illustrates why the point-to-object calculation fits the Hamming net mechanism, and shows the method of programming the modified Hamming net for a given work-

230

Z. Dong and J. Yuan

space. The working principle of the modified Hamming net is explained mathematically and graphically. The mathematical formulation is introduced for a general 3D obstacle. Further illustrations using a simple 2D example are presented in the following section.

4.1 The Architecture and Application of a Hamming Net As an alternative form of information processing neural networks is fast becoming an established discipline [15, 16]. Neural networks are particularly good at solving complex pattern-recognition problems such as speech understanding and handwritten character identification. A major advantage of neural networks over traditional information methods is its capability for parallel-processing immense quantities of information. With the introduction of the Neurocomputers hardware on which neural networks can be implemented efficiently - this advantage of the neural networks can be fully utilised. The unique capability of neural networks make it an ideal tool for handling the large quantity of interference checks in the collision-free trajectory planning. With the parallel implementation, required computation time for interference checks is expected to drop considerably. This, in turn, makes the on-line collision-free trajectory planning feasible. An N-neuron Hamming net is a two-layer neural networks. The architecture and application of a Hamming net is well described by Lippmann [17]. A Hamming net can be viewed as a Hopfield N-flop [18] with an additional input layer that performs preliminary inner product processing. A typical application of a Hamming net is pattern recognition in a proper inner product space. A Hamming net for pattern classification in a 3D Euclidian space is given in Fig. 2, excluding the part inside the dashed-

:

~

Wlj

Sign

T, II

i l

Ou'tput i

Multiplexer

xpEII ~ i ..........

W33

"~'~

wN.~ ~ WN-,:;

"

WN3

.......

IIII Hopfield

wN,3---'~.,

WNI ~ WN2

iP, I

,p~, I I

~N-I "

~_~ .

~' ~

IPN

T~

(1-
(3)

ip,. = max{ip k}

k

(4)

The input patterns, f = [ f x , f y , f y ] r (k = 1 . . . . . N), are automatically classified by the N-neuron Hamming net, according to their inner products with the N set of given weights and thresholds. The detailed structure of the Hopfield N-flop component is not given in Fig. 2, and is beyond the scope of this publication. Instead the function of this Hopfield N-flop component is briefly discussed. The name "N-flop" indicates that the component is an extension of a flip-flop. The function of this Hopfield N-flop is very similar to a R - S flip-flop in the analogue circuits. An R - S flip-flop consists of two amplifiers. Each of these amplifiers tries to shut down the other by feeding its negated output to the input terminal of the competitor. If equal connection weights are used, a fair competition between these two amplifiers is introduced. When two external voltage signals are fed to these interconnected amplifiers, the amplifier with the higher external input will eventually win the competition. In a Hopfield Nflop, N artificial neurons (acting as N amplifiers) are involved in the competition. In the end, only one neuron will emerge as the winner by shutting down all competitors. Since the internal competition is guaranteed to be fair by using strictly equal connection weights, the outcome is only determined by the external inputs which sometimes make a marginal difference.

:

I

N-Flop

4.2 Point-to-Object Distance Calculation Using the Modified Hamming Net

i

W22 ~

%3~?

ipk=fxWklq-fyWk2+fzWk3--Tk

The resulting N inner products {ipk}k (k = 1. . . . . N) are then fed into the second layer of the Hamming net (or the Hopfield N-flop). This layer makes the final classification by:

i

%2 ~

w2

line box. The N patterns are prestored in the Hamming net in terms of N sets of connection weights {Wkl, Wk2, Wk3}k (k = 1 . . . . . N) and N thresholds { T k } , (k = 1 . . . . . N). Given an input feature vector f = [fx, f,., .(~]Z, the first layer (or the input layer) of the Hamming net will match this input with N patterns through N parallel inner product operations:

l~k*

'

Fig. 2. A modifiedl N-neuron Hamming net.

,,

Based upon the resemblance of equation (2) and equation (3), one can find that the calculations of the z-coordinates of a vertex point f represented in the N local coordinate frames of a polyhedron obstacle (with N plane boundaries) are identical to the inner product operations of a Hamming net. If the leading subscript G for the global coordinates is dropped for clarity of expression, the rotation matrix between the global coordinate system and the ith local coordinate frame, (i = 1 . . . . . N), can thus be denoted as iR. The third row of 'R can be written as ~ = [w,, w~2, w~3] and the z-component of the offset vector between the origins of the global coordinate system and the ith local frame attached to the ith plane can be dnoted as T~. The computations of all z-coordinates of the vertex point fwith respect to all local frames (plane boundaries) of a polyhedron obstacle can thus be represented as:

ifz :fxWil q'-fywi2 "l- fzWi3 "F Ti (1 -< i -< N)

Motion Planning Using Neural Networks

The expression has an identical form to the equation (3), and thus can be carried out by the N neurons oY the first layer of a Hamming net, through the inner product operations of a Hamming net. The N boundary planes of a convex polyhedron, each of which defines a halfspace, separate the 3D space into two parts - the inside portion and the outside portion of an obstacle. Since the z-axes of all local coordinate frames that are attached to the boundary planes are pointed toward the outside of the obstacle, a positive z-value indicates that the point (a vertex of the moving object) is outside a boundary plane of the obstacle. Thus if sgn (~f=) > O, for any 1 -< i -< N, the point f is definitely outside the obstacle. This criterion can be written as either max {sgn(%)} > 0

or

sgn (max{%}) > 0 ,

i

4.3

231

Extension of the Formulation

In the previous sections, the modified Hamming net is programmed to calculate the point-to-object distance. If this method is applied to every vertex of the moving object at the discrete trajectory control points in the workspace, a collisionfree optimal trajectory can be generated using the present optimisation approach for robot and manufacturing facility motion planning. The proposed point-to-object distance calculation scheme using neural networks provides a simple and computation-efficient method for evaluating the collisionavoidance constraints. However, it would be ideal to handle the geometric information at a higher level, either using the edges or the volumes of the moving object. This section provides suggestions to these extensions.

i

whichever is easier to implement. The second layer of the Hamming net is designed to select maxi('fz} as equation (4) indicates. This mechanism is kept unchanged in the modified Hamming net. A few additional connections are incorporated into the modified Hamming net to obtain the sign of if= for verifying sgn (maxi(ifz}) > O. The new circuit connections are enclosed in the dashed-line box of Fig. 2, as sign multiplexer. The function of the sign multiplexer is to change the original output of the Hopfield N-flop - an address k* that points to the winning inner product ipk. - to the sign of ipk. -- sgn(ipk.) for collision identification. When collision occurs, or when a point f is inside an Nplane convex polyhedron obstacle, no matter in which local coordinate frame the point is expressed, its z-coordinate will always be negative. That is: sgn ( r f , ) = sgn (max {%}) -< 0 i

Since rfz is the winning maximum inner product and has the minimum absolute value, the ith* plane of the object is the nearest boundary of the obstacle to the point f. The shortest way to push the point f out of the obstacle is to move along the z-direction in the nth* plane-frame. This direction is given by [w,-l, w,.2, w,.3] in the global coordinate frame, and is referred to as the optimal direction for collision removal. In short, the first layer of the Hamming net computes the inner product o f f with respect to N sets of weights/thresholds to calculate the N sets of z-values in the N local coordinate frames. The second layer of the Hamming net and the additional sign multiplexer determine the maximum inner product, to identify whether f is inside the given polyhedron and to find the optimal direction for collision removal. The judgement and the optimal direction are obtained based upon the acquired sign sgn(ipk.). If sgn (ipk') > 0, the point f is outside the polyhedron. Otherwise, a set of weights Wk.~, wk-2 and Wk-3 is pointed by k*. This set of weights represents the ideal direction, in which the point can be pushed out of the object with a minimum distance. In addition, the pointto-object distance or the amount of interference is given by i-i,.

4.3.1 Line-to-Object Collision Identification and Distance Calculation To illustrate the method for extending the proposed formulation of neural networks for line-to-object distance calculation, a simple 2D example, shown in Fig. 3, is used. The principle works on more general 3D cases. The "line" is an abstraction of the edges of the moving object, and the "object" refers to any convex polyhedral obstacles in workspace. Two lines, I - I and II-II, which represent two locations of an edge of the moving object, and a polygon obstacle with nine line boundaries, 11 /9, are shown in Fig. 3. The line I - I has no contact with the obstacle, and the line II-II cuts through the obstacle. These two lines intersect the obstacle boundary at Pl, P2, P3 and P4- Using the scheme presented in the previous sections, the modified Hamming net can easily identify that point Pa and P4 "touch" the boundary of the obstacle (zero point-to-object distance). This, in turn, suggests that the corresponding line segment I I - I I either intrudes or cuts through the obstacle. On the other hand, the modified Hamming net can also find the intersecting points p~ and P2 located outside the obstacle (positive point-to-object distance). This, in turn, indicates that the corresponding line I - I has no interference with the obstacle. .....

!

Fig. 3. Line-to-object interference identification.

232

Z. Dong and J. Yuan

When the line-to-object inteference is identified, the optimal direction for removing the collision can also be suggested by the modified Hamming net. This direction is the vector sum of the surface normals of the surfaces through which the line cuts. The method for finding this direction can also be illustrated using the 2D example. Since line II-II cuts through the obstacle at point P3 on boundary line /9 and at point P4 on boundary /3, the sum of the unit normal vectors of the two boundary lines (or surfaces), z~ + 1,9, provide an ideal direction for removing the line-to-object interference. With a modest effort of intersection point calculation, the modified Hamming net scheme can be used to detect whether a boundary edge of the moving object interferes with an obstacle. When interference does occur, the direction for removing the line-to-object interference can also be found. 4.3.2 Object-to-Object Collision Identification and Distance Calculation The collision identification and distance calculation, directly using the volume of a convex polyhedron (for the moving object), is a more challenging task. In the forbidden region identification approach [3], the equivalent workspace mapping method is used to convert an object-to-object collision identification problem into a point-to-object collision identification problem. The transformation is carried out by growing the boundaries of all given obstacles with the volume of the moving object and shrinking the moving object into a moving point. A combination of the equivalent workspace mapping method with the modified Hamming net based point-to-object and line-to-object collision identification schemes leads to an efficient method for directly handling solid objects. Basically, a cube-like moving object can be modelled by a moving point and the new surrounding obstacles, of which the volumes are expanded at all boundaries. The amount of outward boundary movements of the volume expansion is equal to the radius of the circumscribed sphere to the moving object, as illustrated in Fig. 4(a). On the other hand, a beam-like moving object can be modelled by a moving line of the length of the beam, and the new surrounding obstacles, of which the volumes are

(a)

(b)

Fig. 4. Object-to-object interference identification. (a) Object-topoint conversion. (b) Object-to-line conversion.

expended at all boundaries. The amount of outward boundary movements of the volume expansion is equal to the radius of the circumscribed circle of the beam cross-section, as illustrated in Fig. 4(b). With these two new equivalent workspace mapping methods, most of the components of robots and manufacturing facilities can be easily modelled. Detailed presentation of the method is beyond the scope of this publication. 4.4

Implementation of the Neural Network

The modified Hamming net can be built using two types of basic blocks: the inner product computing block and the Hopfield N-flops block. Both can be implemented either in digital form using very large scale integrated (VLSI) circuits, or in analogue form using the simple operational-amplifier (opam). The analogue implementation of the Hopfield network was discussed in [18]. Detailed discussion of the implementation is beyond the scope of this paper.

5. On-Line Acquisition of Workspace Geometry The on-line acquisition of workspace geometry is currently under study at the University of Victoria. As a project supported by the Institute of Robotic and Intelligent Systems, the work focuses on object/workspace scanning, using a 3D range-finding device and geometric model generation from multiple range images [19, 20]. A range-finding device is an active 3D vision sensor that emits a laser beam onto the object surface, and measures the distance between the sensor and the object surface using time-of-flight or triangulation measurement. The range data produced by the scanning is a rectangular array of numbers. If the parameters and location of a range sensor are known, the coordinates of surface points in the global Cartesian coordinate can be calculated. The mechanism of range-finding devices was studied, and a simulation program was developed I19]. Since the 3D range data is discrete and massive, a 3D sensor alone cannot provide a concise and meaningful workspace description, suitable for robotic and manufacturing applications. Further study of the project is being focused on the geometric model generation from multiple range images [20]. A cross-section based representation, which is compatible with both discrete range data and high-level surface-based geometric models, was introduced. Methods supporting the cross-section model generation were investigated. This work can provide workspace geometry in the form of boundary ~rfaces (without recognising the objects). The result is lequate for many robotic and manufacturing applications, ach as motion planning. The collision identification and distance calculation method introduced in this paper can be used in tandem with the online workspace geometry acquisition using range scanning and geometric model generation. The coordinates of the objects in workspace can be generated by scanning and modelling,

Motion Planning Using Neural Networks

and used for motion planning. The detailed on-line workspace geometry acquisition method was fully discussed in [19, 20].

6. Advantage of the Approach The new collision identification and distance calculation method has two major advantages over previous approaches. The advantage of using neural network operations to replace optimisation-based distance calculations, thus avoiding the complex nested optimisation problem, is obvious. The advantage in computational efficiency by introducing parallel processing is illustrated in this section. For a general motion planning problem with a J vertex moving object, K discrete trajectory locations, and M polyhedral obstacles, each of which has Ni boundary planes, a total of J • K vertex-locations (or points) and ~ Ni boundary planes will be involved in the interference check. The problem can be handled in parallel by J x K identical Hamming nets, of which each has E ~ N~ sets of weights and thresholds representing the needed homogeneous transformations. Through this parallel processing process, using a neurocomputer, the extensive (lengthy) computations, required for the enormous amount of interference checks, can be dramatically decreased. For example, given a moving cube, a workspace with five cube obstacles lying on a flat surface, and ten discrete trajectory locations of the moving cube, a total of 6 object-to-object interference checks, or 8 x 10 x 6 = 480 point-to-object interference checks, or 8 • 10 (5 x 6 + 1) = 2480 point-at-plane side checks, will be required for each step of the motion planning optimisation search. If the interference checks are implemented on a neurocomputer, using 8 x 10 = 80 identical Hamming nets, of which each has 5 x 6 + 1 = 31 sets of weights and thresholds, an optimisation search can be completed in two steps through the two layers of simple artificial neurons. This is particularly promising for the on-line motion planning of intelligent robotic and manufacturing systems.

7.

quantity and large variety. Programming the geometry of various parts, which are batched through production, into the production control computer is time-consuming and errorprone. An alternative approach is to make the robot and manufacturing system "see" what is coming on the production line and plan adequate motions, accordingly. With the progress of intelligent system development, the on-line decision making will become an essential function of robots and manufacturing facilities. The on-line environment perception and on-line motion planning technique will have more applications.

8. An Example This section illustrates the method of programming a set of modified Hamming nets for a given workspace. For ease of presentation, a simple 2D example is used. The obstacle is represented by a convex polygon, shown in Fig. 5. The boundary of the polygon consists of nine intersecting lines. The moving object, which may be a robot arm (or a cutter), is represented by another dashed-line polygon with eight vertices. To identify possible collisions and to calculate the polygon (moving object) to polygon (obstacle) distance, eight identical modified Hamming nets can be programmed to work simultaneously. Each modified Hamming net stores nine sets of weights and thresholds, representing the homogeneous transformations of the nine coordinate frames attached to the boundaries of the obstacle. The eight vertices of the moving polygon can be fed to the eight modified Hamming nets in parallel, and can be ;imultaneously processed by the networks to identify possible collision. Specifically, the simultaneous processing is carried out in each of the modified Hamming nets, using a parallel implementation of the nine similar

Y

Potential Applications of the Approach

On-line motion planning is an essential function for intelligent robotic and manufacturing systems. In present robotic and manufacturing applications, the work environment is often unstructured and time-varient. This type of work environment requires the on-line environment perception and on-line motion planning. Examples of unstructured environments include workspaces under the ocean, in space, and inside a ruined building. These workspaces cannot be known beforehand. The on-line surrounding perception and motion planning become critical for the search and rescue work conducted in these workspaces. Even for the tele-operated robots, the automatic pilot function can assist the human operator tremendously and decrease human errors. The time-variant workspace is often met in today's manufacturing. Modern industry requires batch production of small

233

Obstacle

p

I

P

I1

P

II!

IV

Fig. 5. A 2D motion planning example.

234

Z. Dong and J. Yuan

operations (i.e. rotations and translations) via the simple artificial neurons and their collective computing structure. As illustrated in Fig. 5, the vertex P of the moving polygon at the location III is found inside the obstacle polygon. The corresponding modified Hamming net (one among the eight) will return a normal vector, zl, pointing towards the optimal direction for pushing this vertex out of the obstacle (with a calculated minimum travel distance I z, I). The motion planning program can thus modify the trajectory, based upon the information provided by the modified Hamming net. The new trajectory will be evaluated and may be modified again, until eventually a collision-free trajectory is generated.

9. Summary In this paper, previous work and advances in collision identification and object-to-object distance calculation for motion planning are reviewed. Three frequently used methods: forbidden region identification, swept volume and constrained distance minimisation, as well as their limitations, are discussed. A new formulation for collision identification and distance calculation in motion planning, using neural networks, is introduced. The method calculates the distances between the vertices of a 3D moving object and the given 3D polyhedral obstacles using the modified Hamming net. This formulation is derived from the homogeneous geometric transformations of rotation and translation among the local coordinate frames of the obstacle plane boundaries. The method can be used to identify collisions between the moving object and the obstacle; to calculate the distance between the vertices of the moving object and the obstacle; to measure the interference; and, to find the optimal direction for removing the collision. The formulated calculation is simple in form and supports parallel processing for object-to-obstacle distance calculation. The method can considerably decrease required computation time, and has the potential for being applied to on-line trajectory planning. The method can be extended easily to more general objects, including non-convex polyhedrons, and objects with cylindrical, spherical and sculptured surfaces. The formulated point-to-polyhedron distance calculation can also be extended to handle the line-to-polyhedron and polyhedron-to-polyhedron distance calculation for robot and manufacturing facility trajectory planning.

Acknowledgements The financial supports from the National Science and Engineering Research Council (NSERC) of Canada, and the Institute of Robotic and Intelligent Systems (IRIS), Centre of Excellence of Canada, are gratefully acknowledged.

References 1. J. E. Bobrow, "A direct minimization approach for obtaining the distance between convex polyhedrons", The International Journal of Robotics Research, $ (3), pp. 65-76, June 1989. 2. C. Y. Liu and R. W. Mayne, "Distance calculations in motion planning problems with interference situations", Proceedings of the 1990 ASME Design and Technology Conference DE-Vol 23-1, pp. 145-152, 1990. 3. T. Lozano-Perez and M. A. Wesley, "An algorithm for planning collision-free paths among polyhedral obstacles", Communications of the ACM, 22 (10), pp. 560--570, October 1979. 4. C. Y. Liu and R. W. Mayne, "Nonlinear optimization in collision free trajectory planning and geometric design", SME Transactions on Robotics Research, V.1, pp. 6.11-6.48, 1990. 5. W. E. Red, "'Minimum distance for robot task simulation", Robotica, V.I, pp. 231-238, 1983. 6. E. G. Gilbert and D. W. John, "Distance functions and their application to robot path planning in the presence of obstacles", IEEE Journal of Robotics and Automation, RA-I (1), pp. 21-30, 1985. 7. C. E. Buckley, "A foundation for the "flexible-trajectory' approach to numeric path planning", The International Journal of Robotics Research, 8 (3), pp. 44-64, 1989. 8. R. O. Buchal, D. B. Cherchas, F. Sassani and J. P. Duncan, 1989, "Simulated off-line programming of welding robots", The International Journal of Robotics Research 8 (3), pp. 31-43, 1979. 9. J. W. Boyse, "Interference detection among solid and surfaces", Communications of A CM, 22 (1), pp. 3-9, January 1979. I0. M. A. Ganter and J. J. Uicker, "Dynamic collision detection using swept solid", Journal of Mechanisms, Transmissions, and Automation in Design, 108, pp. 549-555, 1986. 11. M. C. Leu, S. H. Park and K. K. Wang, "Geometric representation of translational swept volumes and its applications", Journal of Engineering for Industry, 108, pp. 113-119, 1986. 12. W. P. Wang and K. K. Wang, "Geometric modeling for swept volume of moving solids", IEEE Computer Graphics and Applications, pp. 8-17, 1986. 13. C. Y. Liu, W. R. Chen and R. W. Mayne, "An approach to dynamic distance calculations for obstacle avoidance problems", Proceedings of the 1991 ASME Design and Technology Conference DE 33-3, pp. 1-7, 1991. 14. J. D. Weld and M. C. Leu, "Geometric respresentation of swept volumes with application to polyhedral objects", The International Journal of Robotics Research, 9 (5), pp. 105-117, October 1990. 15. D. E. Rumelhart, G. E. Hinton and R. J. Williams, "Learning internal representations by error propagation", Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Vol. 1: Foundations, MIT Press, 1986. 16. B. Widrow and R. Winter, "Neural net for adaptive filtering and adaptive pattern recognition", IEEE Computer Magazine, pp. 25-39, March 1988. 17. R. P. Lippmann, "An introduction to computing with neural net", IEEE ASSP Magazine, pp. 4-22, April 1987. 18. J. J. Hopfield, "Neural networks and physical systems with emergent collective computational abilities", Proceedings of the National Academy of Sciences, USA, 79, pp. 2554-2558, April 1982. 19. H. Yao, Z. Dong and R. Podhorodeski, "Simulation of range finding devices by geometric modelling", Computers in Enginering 1991, vol. 1, ASME, pp. 327-332, 1991. 20. H. Yao, R. Podhorodeski and Z. Dong, "An approach to generate geometric models for multiple range images", Technical Paper 92-4-1, University of Victoria, 1992.