Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-25T04:18:55.388Z Has data issue: false hasContentIssue false

A fast algorithm for distance calculation between convex objects using the optimization approach

Published online by Cambridge University Press:  09 March 2009

Summary

This paper describes an efficient and fast algorithm for finding the minimum distance between two convex polyhedrons in a three dimensional space. To obtain the minimal distance, the proposed computational scheme is based on a direct approach to minimizing the distance function which produces a succession of optimal search directions along object boundaries. This algorithm combines the gradient projection method'; and an additional optimal search direction when the gradient projection method leads to a zigzagging phenomenon. In this case, the additional optimal search direction accelerates significantly the convergence of the process. Extensive numerical experiments with convex polyhedra show the performance of this algorithm when compared with that of previous approaches. The proposed algorithm may be very helpful in solving the computation of minimal distance between a pair of convex sets, the collision detection problem or to track the closest points of moving convex objects.

Type
Article
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Rosen, J.B., “The Gradient Projection Method For Nonlinear programmingPart I, S1AM J on Applied Mathematics, 8, 181217 (1960).Google Scholar
Red, W.E., “Minimum distances for robot task simulationRobotica 1,231238(1985).CrossRefGoogle Scholar
Dobkin, D.P. and Kirkpatrick, D.G., “A linear algorithm fordetermining the separation of convex polyhedraJ. Algorithms 6, 381392 (1985).CrossRefGoogle Scholar
Dobkin, D.P. and Kirkpatrick, D.G., “Determining the separation of preprocessed polyhedra-A unified approachProc. of the 17th ICALP, Springer-Verlag Lecture Notes on Computer Science (1990) 443, pp. 400–413.CrossRefGoogle Scholar
Meyer, W, “Distances between boxes: applications to collision detection and clippingProc of the IEEE Int. Conf. on Robotics and Automation (1986) pp. 597602.Google Scholar
Cameron, S.A. and Culley, R.K., “Determine the minimum translational distance between two convex polyhedraProc. of the IEEE Int. Conf. on Robotics and Automation (1986) pp. 591596.Google Scholar
Gilbert, E.G., Johnson, D.W. and Keerthi, S.S., “A fast procedure for computing the distance between complex objects in three-dimensional spaceIEEE Trans on Robotics and Automation 4 (2), 193203 (1988).CrossRefGoogle Scholar
Gilbert, E.G. and Foo, C.P., “Computing the distance between general convex objects in three dimensional spaceIEEE Trans on Robotics and Automation 6 (1). 5361 (1990).CrossRefGoogle Scholar
Hurteau, G. and Stewart, N.F., “Distance calculation for imminent collision indication in a robot system simulationRobotica 6, Part 1, 4751 (1988).CrossRefGoogle Scholar
Bobrow, J.E., “A direct minimization approach for obtaining the distance convex polyhedraInt. J. of Robotics Research, 8 (3), 6576 (1989).CrossRefGoogle Scholar
Lin, M.C. and Canny, J.F., “A fast algorithm for incremental distance calculationProc. of the IEEE Int. Conf. on Robotics and Automation (1991) pp. 1008–1014.Google Scholar
Chang, C., Chung, M.J. and Bein, Z., “Collision-free motion planning for two articulated robot arms using minimum distance functionsRobotica 8, part 2, 137144 (1990).CrossRefGoogle Scholar
Lumelsky, V.J., “On fast computation of distance between line segmentsInform. Process. Lett. 21, 5561 (1985).CrossRefGoogle Scholar
Tornero, J., Hamlin, J. and Kelley, R.B., “Spherical object representation and fast distance computation for robotic applicationsProc. of the IEEE Int. Conf. on Robotics and Automation (1991) pp. 1602–1608.Google Scholar
Hamlin, J.G., Kelley, R.B. and Tornero, J., “Efficient distance calculation using the spherically-extended polytope (S-tope) modelProc. of the IEEE Int. Conf. on Robotics and Automation (1992) pp. 25022507.Google Scholar
Fox, R.L., Optimization Methods for Engineering Design: (Addison-Wesley, Reading, Mass., 1971).Google Scholar
Rao, S.S., Optimization Theory and Applications, 2nd edition Wiley Eastern Limited, New York, 1984).Google Scholar
Zeghloul, S. and Rambeaud, P., “Comment on ”A Direct Minimization Approach for Obtaining the Distance between Convex Polyhedra'; by James E. BobrowInt. J. of Robotics. Research 11 (5), 499501 (1992).CrossRefGoogle Scholar
Zeghloul, S., Rambeaud, P. and Lallemand, J.P., “A fast distance calculation between convex objects by optimization approachProc. of the IEEE Int. Conf. on Robotics and Automation (1992) pp. 25202525.Google Scholar
Zeghloul, S., “Développement d';un systeme de C.A.O. robotique integrant la plantification de taches et la synthese de sites robotisés” Ph.D. Thesis (Poitiers University 1991).Google Scholar
Luenberger, D.G., Introduction to Linear and Nonlinear Programming (Addison-Wesley, Reading, Mass, 1973).Google Scholar