Summary:

SQC is an agent whose task is to control a highly specialized robot used for quality control in a factory. The agent has to analyze different pieces of processed material (e.g. spheres, tubes, etc), comparing their properties with the properties of the "ideal" pieces of the same functionality. SQC is equipped with some input devices that are used in the process of gathering information about the object being analyzed (range scanner, etc). For demonstration purposes, the project is focused on one particular aspect of quality inspection: shape and "smoothness" detection. In the previous part I made the assumption that the agent has to deal exclusively with shiny metal spheres.

Description:

In order to be able to take a decision regarding the "quality" of a component, the agent has to find its characteristics, such as the object’s shape, its degree of "smoothness", that is, how smooth the surface of the sphere is, and so on. If it has blobs or cracks in it, it has to be rejected. If the sphere is too big, it also has to be rejected.

The agent uses the range scanner to gather range data (sets of 3D points measured from the sphere’s surface) in order to build an approximate copy of the sphere’s structure. A 3D mesh is constructed, by gathering the data received from the range scanner for four different positions of the component (sphere) – front (a), back (d), left side (c), right side (b). (See figure below).

Such data is usually noisy, and a certain error tolerance has to be taken into account. For example, each range point (mesh vertex, after the first processing phase) is given an error tolerance of say, E=1e-2 of the sphere’s radius.

In order to compute the radius of the sphere as accurately as possible, we can make the theoretical assumption that most of the sphere will be error-free, that is, it will not have (too many) cracks on its surface. Then the center is computed as the average of the vertices in the mesh data, and the radius as the average distance from the center to the surface points, as illustrated below:

Each element in the mesh data is then analyzed and an eventual deviation from the ideal sphere leads to the rejection of the product. This is basically a search problem. The goals represent the states at which some points in the range data correspond to deviations from the ideal (explained below). Therefore, by reaching a goal, the agent finds out that a particular product is bad, or unsuitable for the consumer. If the agent cannot reach a goal, the product is good. To have a search problem, one must give:

• A definition of a potential solution. The analysis of any point in the range data can lead to a possible solution.
• A method for generating the potential solutions. The agent iterates through all the available points in the range data (geometry, more precisely).
• A way to check whether a potential solution is actually a solution. This is done by mathematical computations that involve, at each point, checking the variation of the gradient of a function (described below). The detection of a sudden change on the sphere’s surface generates the conclusion that the local collection of points being analyzed corresponds to an imperfection in the sphere – which leads to a goal state.

When we compute the gradient of f, we get:

f is a function that maps R³ (x,y,z) to R (radius), therefore the gradient computed in a point (x,y,z) = grad(f)(x,y,z) will be a unit vector emanating from (x,y,z) and pointing in the direction of fastest increase of f (radius at a point). Assuming that the sphere does not have imperfections, the function is constant, that is

for all pairs of vectors (x,y,z) and (x’,y’,z’), and in this case the gradient vectors will all "emerge" from the sphere and will be perpendicular to it. When the sphere has imperfections on its surface, the gradient vectors in the area around the crack will tilt toward the crack or away from it (depending on whether the sphere has a bump or a crease), as seen in the figure below. In other words they will tend to "follow" the crack, while remaining orthogonal to its edge (right image).
 
 

Remember, though, that a "sampled" sphere is actually a discrete collection of vertices, not a continuous surface. In order to make the transition from the sampled data to a continuous surface, we use some special 3x3x3 matrices, called "derivative filters". They are carefully chosen filters that approximate the derivatives, typically by blurring locally the discrete set of radii available (the height variation), and finding the coordinate differences among neighboring vertices. The derivative filters are borrowed from the Sobel edge detection for 2D images, and extended to 3D data.

Using these derivative filters, we can approximate the gradient of the function f at some point (x,y,z), as:

where "*" is the convolution operator, given by:

The method used to check whether a possible solution is actually a solution is a particular aspect of the search problem where the domain knowledge is especially important. The agent has to analyze points (from the range data converted into 3d vertices) which are in the immediate vicinity of the point for which the test is being performed. Crack detection is based on the variance of gradient vectors along the sphere’s surface, therefore some important rules are required in order to test whether a region on the surface represents a crack or not. Here are some concrete cases where the domain knowledge must be queried, together with the answers the domain knowledge must provide for those queries:

• Is this area on the surface a crack? The answer is "yes" if most of the surrounding gradient vectors are tilted toward the analyzed area, or away from it.
• Is the size of the sphere appropriate? The answer is "yes" if the computed radius is the standard one (described by a fact in the knowledge base), with a certain error tolerance.

% Although this program resembles the Prolog style, it is not truly a
% Prolog program; it still has some parts written in some sort of
% pseudo-code, that can (eventually) be translated into Prolog.
% (Note especially the use of operators: +, -, *, /, <, >)
% define the standard radius of the spheres being analyzed

rad(144).

% define some math functions and logical operators

abs(X, R) :- X < 0, R is (-X).
abs(X, X).
equal(X,X).
not(X) :- X,!,fail.
not(_).
false(_) :- not(equal(0,0)).

% define an error tolerance

% (error() is true when | X – Y | > epsilon = 0.01)

error(X,Y) :- abs(X-Y, R), R > 0.01.

% each component / sphere is represented internally as follows:
%
% Sphere = [Center,Radius,Nr,Vertices,Edges]
% Center = the center of the sphere (vector)
% Radius = the radius of the sphere (number)
% Nr = number of vertices
% Vertices = list of vertices (vectors)
% Edges = list of connecting edges ( [Vector,Vector] pairs )
%
% All vectors are represented as [X,Y,Z], triples of Cartesian coords
% center(S) is true when C is the center of the sphere S

center( [C,_,N,V,_] ) :-
    sumv(V, Y, N),
    C is (Y/N).

% sumv(A,B,C) is true when the sum of vertices in list A
% is equal to B, and the number of vertices in list is C

sumv([], [0,0,0], 0).
sumv([V|T], Sum, Number) :-
    sumv(T, Sum, N),
    Sum is (Sum + V),
    Number is N.

% radius(S) is true when R is equal to the radius of S (sphere)

radius([C,R,N,V,_]) :-
    sumd(V,C,Y),
    R is (Y/N).

% sumd(VertexList, Center, Sum) is true when Sum is equal to
% the sum of distances from the center Center to the vertices in
% VertexList

sumd([], C, [0,0,0]).
sumd([V|T], C, Sum) :-
    sumd(T, C, Sum),
    distance(C,V,D),
    Sum is (Sum + D).

% distance(V1,V2,D) is true when D is the distance between vertices
% V1 and V2
% (note the ugly pseudo-code)

distance(Vertex1, Vertex2, D) :-
    D is (sqrt( (Vertex2[0] – Vertex1[0])^2 + …)).

% reject (S)
% true when the sphere S has cracks or other anomalies on its surface, or
% when it has an inappropriate size.
%
% First: a component (sphere) is rejected when it is too small

reject( [Center,Radius,Nr,Vertices,Edges] ) :-
    get_range_data(Data),
    convert_to_vertices(Data, [Center, Radius, Nr, Vertices, Edges]),
    center([Center,Radius,Nr,Vertices,Edges]),
    radius([Center,Radius,Nr,Vertices,Edges]),
    not(rad(Radius)),
    writeln([‘Object rejected: inappropriate size.’]).

% Second: a component is also rejected when it has cracks or bumps on
% its surface

reject(Component) :-
    cracks_in(Component),
    writeln([‘Object rejected: crack detected.’]).

% get_range_data(Data)
% this predicate presumably interacts with the range scanner, and
% collects the range data (relative distances from the scanner to particular
% points on the object) in a list whose internal structure is quite unclear at
% this moment.
% This is one of the predicates in the program that still has to be worked on.

get_range_data(Data) :-
    % true if Data is a list of distances returned by the range scanner
    % This predicate is not implemented.

% convert_to_vertices(D, C)
% this predicate is true if the vertex list and edge list of the component C
% is the representation in 3D of the range data stored in D
% This is another unimplemented predicate in the program.

convert_to_vertices(D, C) :-
    % true if C is the three dimensional representation of the range data
    % stored in D
    % This predicate is not implemented.

% The following part is basically the search problem. The goal states
% are those for which the gradient vectors in certain areas of the sphere
% tend to tilt away from the normal vectors and to point to the direction of
% radius increase or away from the direction of radius decrease.
% At peaks, the gradient has quick shifts in direction (that is quite plausible,
% because once it gets to the "top of the hill", it then has to descend again
% on the other side, so it flips its orientation in order to indicate the new relative
% direction of fastest radius increase)

% cracks_in(C)
% true when the component C has small cracks on its surface

cracks_in(C) :-
    cracks(C,C).

% auxiliary predicates that actually do the job

cracks([C,R,N,[],E], Component) :-
    false(_).

cracks([C,R,N,[A|_],E], Component) :-
    is_crack(A, Component).

cracks([C,R,N,[A|B],E], Component) :-
    cracks([C,R,N,B,E], Component).

% is_crack(P,C)
% is true when vertex P is a point in a crack of component C

is_crack(Point, Component) :-
    neighbors(Point, Component, Points),
    normals(Points, Normals),
    gradients(Points, Gradients),
    local_deviation(Gradients, Normals).

% neighbors(P,C,Ps)
% is true when Ps is the list of vertices adjacent to P. The list is compiled
% from the edge list stored in C.
% For any entry in the edge list, call it entry A, if A = [P,X] or A = [X,P],
% then X is a neighbor of P. This predicate compiles a list with all the
% neighbors.

neighbor(P,[_,_,_,_,[[P,X]|T]]).
neighbor(P,[_,_,_,_,[[X,P]|T]]).

neighbors(Point, Sphere, [Point|T]) :-
    neighbor(Point, Sphere),
    neighbors(Point, Sphere, T).

neighbors(Point, [C,R,N,V,[[_,_]|T]], Points) :-
    neighbors(Point, [C,R,N,V,T], Points).

neighbors(Point, [_,_,_,_,[]], []).

% normals(Ps, Ns)
% true when Ns is the list of normals at the points given in the list Ps

normals([P|T], [N,Q]) :-
    normal(P, N, [P|T]),
    normals(T, Q).

normal(P, N, Points) :-
    % compute the normal N at this point P as the average of
    % the cross products of vectors V(k) = P1-P2, for adjacent
    % P1 and P2 (in the given list of points = Points)
    % This predicate is not implemented.

% gradients(Points, Gradv)
% this predicate is true when Gradv is the list of gradient vectors at each
% point in the list Points.

gradients([], []).

gradients([P|X], [G|Y]) :-
    grad(P, G, [P|X]]),
    gradients(X, Y).

% grad(P,G,N)
% this predicate is true when G is the gradient vector at point P, given
% that the list N contains the neighbors of P

grad(Point, Gradient, Neighbors) :-
    % Computes the gradient. Computationally intensive.
    % See above (comment) for details about a way of actually
    % computing this vector.
    % This method is not implemented.

% local_deviation(Gs,Ns)
% this predicate is true when the gradient vectors in the list Gs tend to
% tilt away from the corresponding normal vectors (at the same points
% on the surface) in the list Ns. This can be done in a number of ways,
% one of which is actually fairly simple and computationally inexpensive:
%
% On a smooth area of the sphere the sum of all the gradient vectors on
% that area is approximately equal to the sum of the normal vectors on
% that area. At a crease or bump, the normal vectors remain orthogonal
% on the surface and their sum will be a vector pointing in a direction
% roughly perpendicular to the surface. Instead, the gradient vectors tend
% to tilt away from the normals, and their local sum is a vector pointing
% in a direction roughly perpendicular to the sum of the normals.
%
% To test whether there is a crack on the surface or not, one must
% compute both these sums, and compare them. If they are roughly
% equal (with an error tollerance), everything’s good. If they seem
% to be too distant from each other, this is most probably a crease.
%
% sumv() and error() are both declared above.

local_deviation(Gs,Ns) :-
    sumv(Gs, SumG, N),
    sumv(Ns, SumN, M),
    SumG is (SumG / N),
    SumN is (SumN / M),
    error(SumG, SumN).

That should do it J

Unfortunately there are some things which cannot be done easily nor elegantly in Prolog.

While "grad" and "normal" can eventually be written in Prolog with more or less effort, it is virtually impossible to write the other two unimplemented predicates (get_range_data and convert_to_vertices) in such a language. Moreover, a hypothetical implementation of them in Prolog would not add much to the general idea and feeling of this project.

A sample trace of the program:

?- reject(X).

X = [ [0,0,0], 144, 1000, [...], […] ]
Object rejected: crack detected.
yes

?- reject(X).

X = [ [0,0,0], 144.001, 1021, [...], […] ]
no

?- reject(X).

X = [ [0,0,0], 200.2, 1216, [...], […] ]
Object rejected: inappropriate size.
yes