We present an algebraic algorithm to generate the boundary of configuration space obstacles arising from the translatory motion of curved convex objects among curved convex obsta cles. Both the boundaries of the objects and obstacles are given by patches of algebraic surfaces. Further, we consider obtaining compliant motion paths where a curved convex object with fixed orientation moves in continuous contact with another curved convex obstacle in three-dimensional space. We also give a method to obtain a piecewise algebraic, ap proximate geodesic path on a curved convex C-space obstacle.
Get full access to this article
View all access options for this article.
References
1.
Abhyankar, S.1983. Desingularization of plane curves. Proc. Symp. in Pure Mathematics40(1):1-45.
2.
Abhyankar, S.1988. Good points on a hypersurface. Advances in Mathematics66(1):1-170.
3.
Abhyankar, S., and Bajaj, C. (1988). Automatic rational parameterization of curves and surfaces III: Algebraic plane curves. Computer Aided Geometric Design.
4.
Bajaj, C.1988. Algorithmic implicitization of rational curves and surfaces . CAPO Research Report CER-88-11, Department of Computer Science, Purdue University.
5.
Bajaj, C., and Kim, M.1989 (North Carolina). Generation of configuration space obstacles: The case of moving algebraic curves. Algorithmica4(2):157-172.
6.
Bajaj, C., and Kim, M.1988a. Algorithms for planar geometric models. Proc. 15th Int. Colloquium on Automata, Languages and Programming (ICALP 88), pp. 67-81.
7.
Bajaj, C., and Kim, M.1988b. Generation of configuration space obstacles: The case of a moving sphere. IEEE J. Robot. Automat.4(1):94-99.
8.
Bajaj, C., and Royappa, A.1988. A note on an efficient implementation of the Sylvester resultant for multivariate polynomials. Computer Science Technical Report CSD-TR-718, Purdue University.
9.
Beck, J., Farouki, R., and Hinds, J.1986. Surface analysis methods. IEEE Computer Graphics and Applications6(12):18-36.
10.
Canny, J.1988. The complexity of robot motion planning. ACM Doctoral Dissertation Series. Cambridge, Mass.: MIT Press.
11.
Chazelle, B.1984. Convex partitions of polyhedra: A lower bound and worst-case optimal algorithm. SIAMJ. on Computing13(3):488-507.
12.
Collins, G.1971. The calculation of multivariate polynomial resultants . J. ACM18(4):515-532.
13.
do Carmo, M.1976. Differential Geometry of Curves and Surfaces. Englewood Cliffs, N.J.: Prentice Hall.
14.
Donald, B.1984. Motion planning with six degrees of freedom. A.I. Technical Report 791, MIT.
15.
Erdmann, M.1984. On motion planning with uncertainty. A.I. Technical Report 810, MIT.
16.
Guibas, L., and Seidel, R.1987. Computing convolutions by reciprocal search. Discrete Comp. Geometry2(2):175 -193.
17.
Hoffmann, C., and Hopcroft, J.1987. Geometric ambiguities in boundary representation . Computer Aided Design19(3):141-147.
18.
Hopcroft, J., and Krafft, D.1987. The challenge of robotics for computer science . In Schwartz, J. T., and Yap, C. K. (eds.): Advances in Robotics: Algorithmic and Geometric Aspects of Robotics. Vol. 1. Hillsdale, N.J.: Lawrence Erlbaum Associates, pp. 7-42.
19.
Horn, B.K.P.1986. Robot Vision. New York: McGraw-Hill Book Co.
20.
Lozano-Pérez, T.1983. Spatial planning: A configuration space approach . IEEE Trans. on ComputersC-32:108-120.
21.
Lozano-Pérez, T., Mason, M., and Taylor, R.1984. Automatic synthesis of fine-motion strategies for robots . Int. J. Robotics Res.3(1):3-24.
22.
Macaulay, F.1902. Some formulae in elimination. Proc. London Math. Society35(1):3-27.
23.
Mitchell, J., Mount, D., and Papadimitriou, C.1987. The discrete geodesic problem. SIAMJ. on Computing16(4):647-668.
24.
Mount, D.1985. On finding shortest paths on convex polyhedra. Technical Report 120, Center for Automation Research, University of Maryland.
25.
O'Rourke, J., Suri, S., and Booth, H.1985. Shortest paths on polyhedral surfaces. Proc. Symp. on Theoretical Aspects ofComputing, pp. 243-254.
26.
Pogorelov, A.V.1978. The Minkowski multidimensional problem. Winston, N.Y.: Halstead Press.
27.
Renegar, J.1987. On the worse case arithmetic complexity of approximating zeros of systems of polynomials. Technical Report, Operations Research and Industrial Engineering, Cornell University.
28.
Requicha, A.1980. Representations of rigid solid objects. Springer Lecture Notes in ComputerScience89:2-78.
29.
Salmon, G.1866. Modern Higher Algebra. ed. 2. Dublin: Hodges, Smith and Co.
30.
Schwartz, J., and Sharir, M.1983. On the piano movers problem: II. General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math.4:298-351.
31.
Sharir, M., and Schorr, A.1984. On shortest paths in polyhedral spaces. SIAMJ. on Computing15(1):193-215.
32.
Udupa, S.1977. Collision detection and avoidance in computer controlled manipulators. Proc. 5th Int. Joint Conf Artificial Intelligence. Cambridge, Mass.: MIT, pp. 737- 748.
33.
van der Waerden, B.1950. Modern Algebra. New York: Frederick Ungar Pub. Co.
34.
Yap, C.1987. Algorithmic motion planning. In Schwartz, J. T., and Yap, C. K. (eds.): Advances in Robotics: Algorithmic and Geometric Aspects of Robotics. Vol. 1. Hillsdale, N.J.: Lawrence Erlbaum Assoc., pp. 95-143.
35.
Zariski, O.1935. Algebraic surfaces. Ergebnisse der Mathematik und Ihre Grenzgebiete, vol. 4. Berlin : Verlag von Julius Springer.
