Interference-Free Insertion of a Solid Body Into a Cavity: An Algorithm and a Medical Application

Abstract

This article presents a novel algorithm for efficiently computing an interference-free insertion path of a body into a cavity and shows its practical use in the insertability analysis of custom orthopedic hip implants. The algorithm is designed to handle tightly fit, very complex three-dimensional bodies requiring fine, complex, coupled six-degree-of-freedom motions in a preferred direction. It provides a practical method for efficiently handling the geometric complexity of tight-fit insertions. The algorithm computes an insertion path consisting of small interference-free body motion steps. It formulates local, linearized configuration space constraints derived from the shapes and computes suc cessive motion steps by solving a series of linear optimization problems whose solution corresponds to the maximum allowed displacement in a preferred direction satisfying the constraints. It either finds a successful insertion path or a stuck conftgura tion. We demonstrate the algorithm with EXTRACT, a program for analyzing the insertability of cementless custom orthopedic hip implants. EXTRACT computes interference-free insertion paths for tightly fit implant and canal shapes described with 10,000 facets to an accuracy of 0.01 inch in 30 minutes on a workstation. It has been successfully tested on 30 real cases provided by a medical equipment manufacturer.

Get full access to this article

View all access options for this article.

References

Barraquand, J. , and Latombe, J.C. 1991. Robot motion planning: A distributed representation approach . Int. J. Robot. Res. 10(6):628-649.

Barraquand, J. , Langlois, B. , and Latombe, J.C. 1992. Numerical potential fields techniques for robot path planning . IEEE Trans. Sys. Man and Cybernet. 22.

Brooks, R.A. , and Lozano-Pérez, T. 1983. (Karlsruhe, Germany). A subdivision algorithm in configuration space for find-path with rotation. Proc. 8th Int. Joint Conf. on Artificial Intelligence. Los Altos, NM: Morgan Kaufmann.

Buckley, S.J. 1990 (Scottsdale, AZ). Fast motion planning for multiple moving robots. Proc. IEEE Int. Conf. on Robotics and Automation. New York: IEEE. Donald, B. 1987. A search algorithm for motion planning with six degrees of freedom. Art. Intell. 31(3):295-353.

Erdmann, M. 1994. On a representation of friction in configuration space . Int. J. of Robot. Res. 13(3):240-271.

Faverjon, B. 1984 (Atlanta). Obstacle avoidance using an octree in the configuration space of the manipulator. Proc. IEEE Int. Conf on Robotics and Automation New York : IEEE.

Faverjon, B. , and Tournassoud, P. 1987 (Raleigh, NC). A local-based approach for path planning of manipulators with a high number of degrees of freedom . Proc. IEEE Int. Conf. on Robotics and Automation New York: IEEE.

Giraud, A. , and Sidobre, D. 1987 (Raleigh, NC). A heuristic motion planner using contact for assembly. Proc. IEEE Int. Conf. on Robotics and Automation New York: IEEE.

Gupta, K.K. , and Zhu, X. 1994 (San Diego). Practical global motion planning for many degrees of freedom: A novel approach within a sequential framework. Proc. IEEE Int. Conf. on Robotics and Automation New York: IEEE.

10.

Kavraki, L. , and Latombe, J.C. 1994 (San Diego). Randomized preprocessing of configuration space for fast path planning. Proc. IEEE Int. Canf. on Robotics and Automation, New York : IEEE.

11.

Latombe J.C. 1991. Robot Motion Planning. Dordrecht; The Netherlands: Kluwer Academic Publishers.

12.

Paul, H.A. , Mittelstadt, B. , Barger, W. , Taylor, R. , Kazanzides, P. , Zohars, J. , Williamson, B. , and Hanson, W. 1992 (Nice, France). A surgical robot for total hip replacement surgery. Proc. IEEE Int. Conf. on Robotics and Automation New York: IEEE.

13.

Stulberg, S.D. 1989. Custom-made primary total hip replacements. Orthopedics 15(5):1245-1252.

14.

Taylor, R.H. , Paul, H.A. , Kazanzides, P. , Mittelstadt, B. , Hanson, W. , Zohars, H. , Williamson, B. , Musits, B. , Glassman, E. , and Bargar, W. 1994. An image-directed robotic system for precise orthopedic surgery. IEEE Trans. Robot. Automation 10(3):260-275 .