Optimal Probing Strategies

Probing is a common operation employed to reduce the position uncertainty of objects. This paper demonstrates a technique for constructing provably near-optimal probing strategies for precisely localizing polygonal parts. This problem is shown to be dual to the well-studied grasping problem of computing optimal finger placements as defined by B. Mishra and others. A useful quality metric of any given probing strategy can easily be computed from simple geometric constructions in the displacement space of the polygon. The approach will always find a minimal set of probes that is guaranteed to be near optimal for constraining the position of the polygon. The size of the resulting set of probes is within O(1) of the optimal number of probes and can be computed in O(n log 2 n) time, whereas the exact optimal solution is in NP-hard. The result of this work is a probing strategy useful in practice for refining part poses.