Page 147 - Mechatronics for Safety, Security and Dependability in a New Era

Ch27-I044963.fm Page 131 Monday, August 7, 2006 11:26 AM
11:26 AM
Monday, August 7,2006
Page 131
Ch27-I044963.fm
131 - & •
131
GENERATION OF PRECEDENCE GRAPH BY K-NEAREST-NEIGHBOR RULE
Generation of Initial Labeled Samples
To generate the heuristic precedence graph by using the k-nearest-neighbor rule, we collect in advance
initial labeled samples obtained from products whose assembly sequences are known. In this study,
each sample is an ordered set of three parts, </?,, p j} p k>, among which there is a relationship that
Pi is connected with pj and p h. The class label of each sample is either of the followings:
• Class P expressing the case that p t and p. are joined together before p k is joined to them.
• Class N expressing the other cases.
We generate all the combinations of parts for the products, and then give the class label to every
combination, <p l, p f, p t>, according to their known assembly sequences.
Assigning a Class Label to an Vnlabeled Sample

By using the labeled samples, the k-nearest-neighbor rule assigns a class label to every unlabeled
sample, x=<xp n xp n xp k>, obtained from a given product whose assembly sequence is unknown
and needs to be planned. The algorithm of the k-nearest-neighbor rule is as follows.

Step 1: Fix k, which is the number of the closest neighbors ofx. Let the labeled samples beyi,)>2, •••,
yt,, •••,y n, where n is the number of the labeled samples.
Step 2: Set h=\ and E=(j> (i.e., null set).
Step 3: Calculate the distance fromxto alabeled sample^/,, d(x,yi,).
Step 4: If h<k, addyi, in the set E and go to Step 6. Otherwise go to Step 5.
Step 5: \fyn is closer to x than any member in E, delete the farthest in the set E and include yt, in E.
Step 6: If h=n, go to Step 7. Otherwise set h=h+\ and go to Step 3.
Step 7: Determine the majority class represented in the set E and classify x in the majority class.

If Class P is assigned to the sample x=< xp s, xpj, xp k >, a heuristic precedence relation is generated,
which represents that a connective relation between xp t and xp t precedes a connective relation
between xp, and xp k. By applying this method to all the combinations of parts included in the given
product whose assembly sequence is unknown, we can generate a heuristic precedence graph for the
product.

Calculation of Distance
In Step 3, the distance from x to a labeled sample^/,, d(x,y>,), is calculated by:

d(x, yt,)=d p( xp t, ypi )+d p( xp f, yp f )+d p( xp k ,yp k) (1)
=<
where yp t, ypj, and yp k are the parts included in//, (i.e., y>, yPj, yPj, yp^X an d d p(*,*) is the
degree of similarity between two parts. To calculate d p(*,*), we use is-a hierarchy of part types, which
is a relationship among super- and sub-classes of parts.

Addition of Labeled Samples
Additional labeled samples are made from the information on the assembly sequences planned newly
by the assembly planning method (Murayama & Oba, 1993) incorporated with the method described
in this paper. As the assembly sequence planning and the addition of the labeled samples are executed
more times, the assembly sequences can be generated more efficiently.

- &