next up previous contents
Next: Specifying Motion Up: Reasoning About Path-Planning with Previous: Gap Finding

   
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.


 
Table 5.1: A Qualitative ``Trig Table''.
Qualitative Properties of Triangles
Triangle Angles Properties
  A B C  

\begin{picture}(40,16)
\put(15,0){\line(1,0){10}}
\put(15,0){\line(1,2){5}}
\...
...24,4){$a$ }
\put(12,-2){$A$ } \put(19,11){$B$ } \put(26,-2){$C$ }
\end{picture}
acute acute acute a<b+c*
b<a+c*
c<a+b*

\begin{picture}(40,12)
\put(15,0){\line(1,0){10}}
\put(15,0){\line(0,0){10}}
...
...ine(1,-1){10}}
\put(12,3){$c$ } \put(17,1){$b$ } \put(21,5){$a$ }
\end{picture}
right acute acute a>c
a>b

\begin{picture}(40,12)
\put(17,0){\line(1,0){10}}
\put(12,10){\line(1,-2){5}}
...
...ine(3,-2){15}}
\put(11,3){$c$ } \put(18,1){$b$ } \put(20,6){$a$ }
\end{picture}
obtuse acute acute a>c
a>b

\begin{picture}(40,12)
\put(5,0){\line(1,0){32}}
\put(5,0){\line(1,5){2}}
\pu...
...line(3,-1){30}}
\put(2,5){$c$ } \put(10,1){$b$ } \put(20,7){$a$ }
\end{picture}
acute acute very-acute $a\simeq b$
c<<a
c<<b

\begin{picture}(40,12)
\put(5,0){\line(1,0){30}}
\put(5,0){\line(0,0){10}}
\p...
...line(3,-1){30}}
\put(2,4){$c$ } \put(10,1){$b$ } \put(20,7){$a$ }
\end{picture}
right acute very-acute $a\simeq b$
c<<a
c<<b
a>b

\begin{picture}(40,12)
\put(5,0){\line(1,0){28}}
\put(3,10){\line(1,-5){2}}
\...
...line(3,-1){30}}
\put(1,3){$c$ } \put(10,1){$b$ } \put(20,6){$a$ }
\end{picture}
obtuse acute very-acute c<<a
c<<b
a>b

\begin{picture}(40,12)
\put(5,10){\line(3,-2){15}}
\put(20,0){\line(1,0){15}}...
...ine(3,-1){30}}
\put(10,2){$c$ } \put(20,6){$a$ } \put(20,1){$b$ }
\end{picture}
obtuse very-acute very-acute a>b
a>c
* Note that these properties hold for all triangles.
 

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.


next up previous contents
Next: Specifying Motion Up: Reasoning About Path-Planning with Previous: Gap Finding
Alan Blackwell
2000-11-17