## Geometric Sensing of Known Planar Shapes

Yan-Bin Jia and Michael Erdmann

*International Journal of Robotics Research*, Vol. 15, No. 4, 1996.

* Abstract *

Industrial assembly involves sensing the pose (orientation and
position) of a part. Efficient and reliable sensing strategies can be
developed for an assembly task if the shape of the part is known in
advance. In this paper we investigate two problems of determining the
pose of a polygonal part of known shape, for the cases of a continuum
and a finite number of possible poses respectively.
The first problem, named *sensing by inscription*, involves
determining the pose of a convex *n*-gon from a set of *m*
supporting cones. An algorithm with running time *O*(*nm*)
which almost always reduces to *O*(*n* + *m* log
*n*) is presented to solve for all possible poses of the polygon.
We prove that the number of possible poses cannot exceed 6*n*,
given *m* >= 2 supporting cones with distinct vertices. Simulation
experiments demonstrate that two supporting cones are sufficient to
determine the real pose of the *n*-gon in most cases. Our
results imply that sensing in practice can be carried out by obtaining
viewing angles of a planar part at multiple exterior sites in the
plane.

On many occasions a parts feeder will have reduced the number of
possible poses of a part to a small finite set. Our second problem,
named *sensing by point sampling*, is concerned with a more
general version---finding the minimum number of sensing points
required to distinguish between *n* polygonal shapes with a total
of *m* edges. In practice this can be implemented by embedding a
series of point light detectors in a feeder tray or by using a set of
mechanical probes that touch the feeder at a finite number of
predetermined points. We show that this problem is equivalent to an
NP-complete set-theoretic problem introduced as *Discriminating
Set*, and present an *O*(*n*^2 *m*^2) approximation
algorithm to solve it with a ratio of 2 ln *n*. Furthermore, we
prove that one can use an algorithm for Discriminating Set with ratio
*c* log *n* to construct an algorithm for Set Covering with
ratio *c* log *n* + *O*(log log *n*). Thus the
ratio 2 ln *n* is asymptotically optimal unless NP \subset
DTIME(*n*^{poly log *n*}), a consequence of known results on
approximating Set Covering. The complexity of subproblems of
Discriminating Set is also analyzed, based on their relationship to a
generalization of Independent Set called *3-Independent Set*.
Finally, simulation results suggest that sensing by point sampling is
mostly applicable when poses are densely distributed in the plane.