Abstract:
An algorithm for computing the Euclidean distance between a pair of convex sets in R/sup m/ is described. Extensive numerical experience with a broad family of polytopes ...Show MoreMetadata
Abstract:
An algorithm for computing the Euclidean distance between a pair of convex sets in R/sup m/ is described. Extensive numerical experience with a broad family of polytopes in R/sup 3/ shows that the computational cost is approximately linear in the total number of vertices specifying the two polytopes. The algorithm has special features which makes its application in a variety of robotics problems attractive. These features are discussed and an example of collision detection is given.<>
Published in: IEEE Journal on Robotics and Automation ( Volume: 4, Issue: 2, April 1988)
DOI: 10.1109/56.2083
References is not available for this document.
Select All
1.
R. O. Barr, "An efficient computational procedure for a generalized quadratic programming problem", SIAM J. Contr., vol. 7, pp. 415-429, 1969.
2.
R. O. Barr and E. G. Gilbert, "Some efficient algorithms for a class of abstract optimization problems arising in optimal control", IEEE Trans. Automat. Contr., vol. AC-14, pp. 640-652, 1969.
3.
J. W. Boyse, "Interference detection among solids and surfaces", Commun. ACM, vol. 22, pp. 3-9, 1979.
4.
R. A. Brooks and T. Lozano-Perez, "A subdivision algorithm in configuration space for findpath with rotation", IEEE Trans. Syst. Man Cybern., vol. SMC-J5, pp. 224-233, 1985.
5.
C. E. Buckley and L. J. Leifer, "A proximity metric for continuum path planning", Proc. 9th Int. Joint Conf.on Artificial Intelligence, pp. 1096-1102, 1985.
6.
S. A. Cameron, "A study of the clash detection problem in robotics", Proc. IEEE Int. Con/ on Robotics and Automation, pp. 488-493, 1985.
7.
S. A. Cameron and R. K. Culley, "Determining the minimum translational distance between two convex polyhedra", Proc. IEEE Int. Conf. on Robotics and Automation, pp. 591-596, 1986.
8.
J. Canny, Collision detection for moving polyhedra, 1984.
9.
F. Chin and C. A. Wang, "Optimal algorithms for the intersection and minimum distance problems between planar polygons", IEEE Trans. Compute, vol. C-32, pp. 1203-1207, 1983.
10.
R. K. Culley and K. G. Kempf, "A collision detection algorithm based on velocity and distance bounds", Proc. IEEE Int. Conf. on Robotics and Automation, pp. 1064-1069, 1986.
11.
D. P. Dobkin and D. G. Kirkpatrick, "A Linear algorithm for determining the separation of convex polyhedra", J. Algorithms, vol. 6, pp. 381-392, 1985.
12.
B. R. Donald, "On motion planning with six degrees of freedom: solving the intersection problems in configuralion space", Proc. IEEE Int. Conf. on Robotics and Automation, pp. 536-541, 1985.
13.
H. Edelsbrunner, "On computing the extreme distances between two convex polygons", J. Algorithms, vol. 6, pp. 515-542, 1985.
14.
E. G. Gilbert, "An iterative procedure for computing the minimum of a quadratic form on a convex set", SIAM J. Contr., vol. 4, pp. 61-80, 1966.
15.
E. G. Gilbert and D. W. Johnson, "Distance functions and their application to robot path planning in the presence of obstacles", IEEE J. Robotics Automata., vol. RA-1, pp. 21-30, 1985.
16.
E. G. Gilbert, D. W. Johnson and S. S. Keerthi, "A fast procedure for computing the distance between complex objects in three space", Proc. IEEE Int. Conf. on Robotics and Automation, pp. 1883-1889, 1987.
17.
D. W. Johnson, The optimization of robot motion in the presence of obstacles, 1987.
18.
D. W. Johnson and E. G. Gilbert, "Minimum time robot path planning in the presence of obstacles", Proc. IEEE Conf. on Decision and Control, pp. 1748-1753, 1985.
19.
O. Khatib, "Real-time obstacle avoidance for manipulators and mobile robots", Int. J. Robotics Res., vol. 5, pp. 90-98, 1986.
20.
D. T. Lee and F. P. Preparata, "Computational geometry—A survey", IEEE Trans. Comput., vol. C-33, pp. 1072-1101, 1984.
21.
T. Lozano-Perez, "Spacial planning: A configuration space approach", IEEE Trans. Comput., vol. C-32, pp. 108-120, 1983.
22.
V. J. Lumelsky, "On fast computation of distance between line segments", Inform. Proc. Letters, vol. 21, pp. 55-61, 1985.
23.
W. Meyer, "Distances between boxes: Applications to collision detection and clipping", IEEE Int. Conf. on Robotics and Automation, pp. 597-602, 1986.
24.
M. Orlowski, "The computation of the distance between polyhedra in 3-space", SIAM Conf. on Geometric Modeling and Robotics, 1985-July.
25.
W. E. Red, "Minimum distances for robot task simulation", Robot ica, vol. 1, pp. 231-238, 1983.
26.
R. T. Rockafellar, Convex Analysis, NJ, Princeton:Princeton Univ. Press, 1970.
27.
J. T. Schwartz, "Finding the minimum distance between two convex polygons", Inform. Process. Lett., vol. 13, pp. 168-170, 1981.
28.
J. T. Schwartz and M. Sharir, "On the piano movers problem I the special case of a rigid polygonal body moving amidst polygonal barriers", Commun. Pure Appl. Math., vol. 36, pp. 345-398, 1983.
29.
P. Wolfe, "Finding the nearest point in a polytope", Math. Programming, vol. 11, pp. 128-149, 1976.
