file.pdf (527.34 kB)

Download file# Geometric Sensing of Known Planar Shapes

journal contribution

posted on 01.01.1996, 00:00 authored by Yan-Bin Jia, Michael ErdmannIndustrial 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 article 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)
that 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 6n, 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&#; m&#;) approximation algorithm to solve it with a ratio of 2ln 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 &#; DTIME&#;npoly 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.