Part 5: Visibility
Chapter List
- Fast Construction of Near Optimal Probing Strategies
- Robust Geometric Algorithms for Sensor Planning
- Visible Positions for a Car-Like Robot Amidst Obstacles
Eric Paulos, University of California, Berkeley, CA, USA
John Canny, University of California, Berkeley, CA, USA
We address the problem of defining and constructing optimal probing strategies for precisely localizing polygonal parts whose pose is approximately known. We demonstrate that this problem is dual to the well studied grasping problem of computing optimal finger placements as defined by Mishra et al. [17] and others [10, 16]. In addition we develop a quality measure for any given probing strategy based on a simple geometric construction in the displacement space of the polygon. Furthermore, we can determine 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. The result is a probing strategy useful in practice for refining part poses.
1 Introduction
In industrial manufacturing and automated assembly accuracy is money. Attaining and maintaining high precision can increase the cost of fixturing and feeding several fold [18]. The meaning of high verses low precision depends on the application, but for typical mechanical assembly, low precision tooling might provide accuracies in the tens of mils, while high precision would be around one mil or less (One mil = 10 -3