Optimal probing strategies

Probing is a common operation employed to reduce the position uncertainty o f objects. This paper demonstrates a technique for constructing provably ne ar-optimal probing strategies for precisely localizing polygonal parts. Thi s problem is shown to be dual to the well-studied grasping problem of compu ting 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. Th e approach will always find a minimal set of probes that is guaranteed to b e near optimal for constraining the position of the polygon. The size of th e resulting set of probes is within O (1) of the optimal number of probes a nd can be computed in O (n log(2) n) time, whereas the exact optimal soluti on is in NP-hard. The result of this work is a probing strategy useful in p ractice for refining part poses.