Checking for Fit

The results of the gap finding search include a value in the partial distance ordering which describes the narrowest extent of each gap. When checking whether the moving object will fit through a gap, this narrowest extent must be compared to the width of the moving object.

The ``width'' of the moving object depends on its orientation as it moves
through the gap, and it is necessary to find an expression for the effective
width of the moving object when moving in a given direction. This is done by
finding the extremities of the object at right angles to the direction of
motion, and then comparing the distance between these extremities to the gap
size.^{5.8}

The current method for finding object extremities conducts a search from a given boundary element, evaluating each element encountered to find out how far it will protrude given the specified direction of motion. Candidates for extremities are placed on a candidate list, so that they can be evaluated further at a later stage. As soon as the search procedure has accumulated enough of these candidates, another set of rules is used for pairing extremities which are likely to be furthest apart. Single candidates and paired candidates are pruned from the candidate list if other candidates obviously protrude further.

Once the boundary search is complete, and a pruned set of extremity candidates
is found, qualitative expressions for the distance between the extremities are
derived. These expressions are related to the partial distance ordering, and
can use simple rules in ``qualitative trigonometry'', together with `internal` proximity information about the boundary elements of the moving
object.

The system aims to find an expression for the maximum possible value of this
distance between extremities. This is most easily done using the partial
distance ordering, where an item of the `synthetic` distance type is used
as a place-holder in equidistance lists for the unknown distance (the `synthetic` type distinguishes it from measured distances). In most cases, an
expression for this `synthetic` object extremity can be derived either
from the size of boundary segments which are parallel to the unknown
extremity, or in terms of `internal` proximity.

The width found in this way may simply be equal to a known distance, or it may be derived using operations in qualitative arithmetic. Typical functions include simple binary addition and subtraction of distances in the partial distance ordering.

Where it is not possible to directly assign a value to the extremity, this is
usually because there is no parallel segment, or internal proximity between
perpendicular segments, that can be used to find an appropriate expression. In
these cases an approximation to the value can be found using ``qualitative
trigonometry''. The qualitative trigonometry rules listed in
table 5.1 can be used to find expressions for unknown distances
across the interior of the object in terms of the size of boundary segments,
or `internal` proximities. Such information is always far less
constrained than the measured values explicitly entered in the partial
distance ordering, however, and is not often used as the basis for a final
decision on gap fit.

The last step in establishing effective width in motion is to compare the remaining entries on the extremity candidate list, and find which are the largest possible extremities for the object. In future, some further pruning of the blackboard should be performed before this stage, in order to find and remove impossibly large extremities. Such pruning would operate by comparing the extremity candidates to the proximity of obstacles in the context of the moving object, and checking to ensure the effective width is not larger than the distance between surrounding obstacles.

The final qualitative expression for width of the moving object is compared to the size of the narrowest extent of the gap, and one of three judgements can be made from the partial distance ordering: either the moving object definitely will fit through the gap, it definitely will not fit, or fit has not been established. This last case enables further investigation to be performed when other methods are available. These methods may involve the application of more rigorous geometric reasoning, or physical measurement performed by a robot. This system does not at present regard such gaps as candidates, and simply continues to search for a known ``definite fit'' gap.