Geometric Sensing of Known Planar Shapes

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. In the first problem, the part has a continuum of possible poses, while in the second problem, it has a finite number of possible poses. More specifically, the first problem involves determining the pose of a convex n -gon from a set of m supporting cones, that is, cones with both sides supporting the polygon. An algorithm with running time O (nm) which almost always reduces to O(n+m logn) is presented to solve for all possible poses of the polygon. As a consequence, the polygon inscription problem of finding all possible poses for a convex n -gon inscribed in another convex m -gon, can be solved within the same asymptotic time bound. We prove that the number of possible poses cannot exceed 6n, given m >2 supporting cones with distinct vertices. 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. As a conclusion, we generalize this and other sensing methods into a scheme named sensing by inscription . On many occasions a parts feeder will have reduced the number of possible poses of a part to a small finite set. In order to distinguish between the remaining poses of the part some simple sensing or probing operation may be used. Our second problem, called sensing by point sampling, is concerned with finding the minimum number of sensing points required to distinguish between a finite set of polygonal shapes. In practice this can be carried out 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. Intuitively, each sensing point can be regarded as a binary bit that has two values 'contained' and 'not contained'. So the robot senses a shape by reading out the binary representation of the shape, that is, by checking which points are contained in the shape and which are not. The formalized sensing problem: Given n polygons with a total of m edges in the plane, locate the fewest points such that each polygon contains a distinct subset of points in its interior. We show that this problem is equivalent to an NP-complete set-theoretic problem introduced as Discriminating Set.. By a reduction to Hitting Set (and hence to Set Covering), an O (n2m2) approximation algorithm is presented to solve the sensing problem with a ratio c logn to construct an algorithm for Set Covering with ratio c logn + O (log logn ). Thus approximating Discriminating Set exhibits the same hardness as that of approximating Set Covering recently shown in [44] and [7]; this result implies that the ratio 2ln n is asymptotically optimal unless NP C DTIME(n poly log n ). We also analyze the complexity of subproblems of Discriminating Set, based on their relationship to a generalization of Independent Set called 3-Independent Set. Finally, we present experimental results showing that sensing by point sampling is mostly applicable when poses are densely distributed in the plane.