On the Hybrid Localization/Envelopment Problem

Abstract

The problem of aligning the CAD model of a workpiece such that all points measured on the finished surfaces of the workpiece match closely to corresponding surfaces on the model while all unmachined surfaces lie outside the model is referred to as the hybrid localization/envelopment problem. The hybrid problem has important applications in setting up for machining of partially finished workpieces. This paper gives a formulation of the hybrid localization/envelopment problem, and presents a simple algorithm for computing its solutions. First, we show that when the finished surfaces of a workpiece are inadequate to fully constrain the rigid motions of the workpiece, then the set of free motions remaining must form a subgroup G0 of the Euclidean group SE(3). This allows us to decompose the hybrid problem into a (symmetric) localization problem on the homogeneous space SE(3)/G0 and an envelopment problem on G0. While the symmetric localization problem is solved using the fast symmetric localization (FSL) algorithm developed in one of our earlier papers, the envelopment problem is solved by computing the solutions of a sequence of linear programming (LP) problems. We derive explicitly the LP problems, and apply standard linear programming techniques to solve the LP problems. We present simulation results to demonstrate the effectiveness of our method for the hybrid problem.

Get full access to this article

View all access options for this article.

References

Boothby, W. 1975. An Introduction to Differentiable Manifolds and Riemannian Geometry. New York: Academic .

Chu, Y., Gou, J., and Li, Z. 1997. Performance analysis of localization algorithms. Proc. of the IEEE Intl. Conf. on Robot. and Automat. Washington, DC: IEEE , pp. 1247–1252.

Gou, J., Chu, Y., and Li, Z. 1998. On the symmetric localization problem . IEEE Trans. Robot. Automat. 14(4): 533–540 .

Gou, J., Chu, Y., and Li, Z. Forthcoming. A geometric theory of form, profile, and orientation tolerances. Precision Engineering.

Gunnarsson, K., and Prinz, F. 1987. CAD model-based localization of parts in manufacturing . Computer 20(8): 66–74 .

Hong, J., and Tan, X. 1990. Method and apparatus for determining position and orientation of mechanical objects. US patent 5208762.

Li, Z., Gou, J., and Chu, Y. 1998. Geometrical algorithms for workpiece localization . IEEE Trans. Robot. Automat. 14(6): 864–878 .

Menq, C., Yau, H., and Lai, G. 1992. Automated precision measurement of surface profile in CAD-directed inspection . IEEE Trans. Robot. Automat. 8(2): 268–278 .

Murray, R., Li, Z., and Sastry, S. 1994. A Mathematical Introduction to Robotic Manipulation. Boca Raton, FL: CRC Press .

10.

Poppestone, R. 1984. Group theory and robotics. In Brady, M. and Paul, R. (eds.) Proc. of the First Intl. Symp. on Robot. Res. Cambridge, MA: MIT Press .