The construction of analytic diffeomorphisms for exact robot navigation on star worlds

Authors:
Elon Rimon and Daniel E. Koditschek

Journal:
Trans. Amer. Math. Soc. **327** (1991), 71-116

MSC:
Primary 58F40; Secondary 70B15, 70Q05

DOI:
https://doi.org/10.1090/S0002-9947-1991-1012512-X

MathSciNet review:
1012512

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A *Euclidean Sphere World* is a compact connected submanifold of Euclidean -space whose boundary is the disjoint union of a finite number of dimensional Euclidean spheres. A *Star World* is a homeomorph of a Euclidean Sphere World, each of whose boundary components forms the boundary of a star shaped set. We construct a family of analytic diffeomorphisms from any analytic Star World to an appropriate Euclidean Sphere World "model." Since our construction is expressed in closed form using elementary algebraic operations, the family is effectively computable. The need for such a family of diffeomorphisms arises in the setting of robot navigation and control. We conclude by mentioning a topological classification problem whose resolution is critical to the eventual practicability of these results.

**[1]**S. Arimoto and F. Miyazaki,*Asymptotic stability of feedback controls for robot manipulators*, (Proc. 1st IFAC Sympos. on Robot Control), Barcelona, Spain, 1985.**[2]**Marcel Berger,*Geometry. I*, Universitext, Springer-Verlag, Berlin, 1987. Translated from the French by M. Cole and S. Levy. MR**882541****[3]**J. F. Canny,*The complexity of robot motion planning*, Ph.D. dissertation, Dept. of Electrical Engineering and Computer Science, M.I.T., May 1987.**[4]**Morris W. Hirsch,*Differential topology*, Springer-Verlag, New York-Heidelberg, 1976. Graduate Texts in Mathematics, No. 33. MR**0448362****[5]**N. Hogan,*Impedance control*:*An approach to manipulation*, ASME J. Dynamics Systems, Measurement, and Control**107**(1985), 1-7.**[6]**Witold Hurewicz and Henry Wallman,*Dimension Theory*, Princeton Mathematical Series, v. 4, Princeton University Press, Princeton, N. J., 1941. MR**0006493****[7]**John L. Kelley,*General topology*, Springer-Verlag, New York-Berlin, 1975. Reprint of the 1955 edition [Van Nostrand, Toronto, Ont.]; Graduate Texts in Mathematics, No. 27. MR**0370454****[8]**O. Khatib,*Real time obstacle avoidance for manipulators and mobile robots*, Internat. J. Robotics Res.**5**(1986), 90-99.**[9]**D. E. Koditschek,*A strict global lyapunov function for mechanical systems*, Tech. Rep. 8707, Center for Systems Science, Yale Univ., November 1987.**[10]**-,*Robot control systems*, (Stuart Shapiro, ed.), Encyclopedia of Artificial Intelligence, Wiley, 1987, pp. 902-923.**[11]**D. E. Koditschek and E. Rimon,*Exact robot navigation using cost functions*:*The case of distinct spherical boundaries in*, Tech. Rep. 8803, Center for Systems Science, Yale Univ., January 1988.**[12]**Daniel E. Koditschek and Elon Rimon,*Robot navigation functions on manifolds with boundary*, Adv. in Appl. Math.**11**(1990), no. 4, 412–442. MR**1077256**, https://doi.org/10.1016/0196-8858(90)90017-S**[13]**Elon L. Lima,*The Jordan-Brouwer separation theorem for smooth hypersurfaces*, Amer. Math. Monthly**95**(1988), no. 1, 39–42. MR**935429**, https://doi.org/10.2307/2323445**[14]**W. S. Massey,*Introduction to algebraic topology*, Springer-Verlag, New York, 1972.**[15]**William S. Massey,*Singular homology theory*, Graduate Texts in Mathematics, vol. 70, Springer-Verlag, New York-Berlin, 1980. MR**569059****[16]**John W. Milnor,*Topology from the differentiable viewpoint*, Based on notes by David W. Weaver, The University Press of Virginia, Charlottesville, Va., 1965. MR**0226651****[17]**Marston Morse,*The existence of polar non-degenerate functions on differentiable manifolds*, Ann. of Math. (2)**71**(1960), 352–383. MR**0113232**, https://doi.org/10.2307/1970086**[18]**V. V. Pavlov and A. N. Voronin,*The method of potential functions for coding constraints of the external space in an intelligent mobile robot*, Soviet Automat. Control**17**(1984).**[19]**E. Rimon and D. E. Koditschek,*The construction of diffeomorphisms for exact robot navigation on star worlds*, Tech. Rep. 8809, Center for Systems Science, Yale Univ., July 1988.**[20]**Jacob T. Schwartz and Micha Sharir,*On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds*, Adv. in Appl. Math.**4**(1983), no. 3, 298–351. MR**712908**, https://doi.org/10.1016/0196-8858(83)90014-3**[21]**I. M. Singer and J. A. Thorpe,*Lecture notes on elementary topology and geometry*, Springer-Verlag, New York-Heidelberg, 1976. Reprint of the 1967 edition; Undergraduate Texts in Mathematics. MR**0413152****[22]**Stephen Smale,*On gradient dynamical systems*, Ann. of Math. (2)**74**(1961), 199–206. MR**0133139**, https://doi.org/10.2307/1970311**[23]**John A. Thorpe,*Elementary topics in differential geometry*, Springer-Verlag, New York-Heidelberg, 1979. Undergraduate Texts in Mathematics. MR**528129****[24]**Eberhard Zeidler,*Nonlinear functional analysis and its applications. I*, Springer-Verlag, New York, 1986. Fixed-point theorems; Translated from the German by Peter R. Wadsack. MR**816732**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
58F40,
70B15,
70Q05

Retrieve articles in all journals with MSC: 58F40, 70B15, 70Q05

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1991-1012512-X

Article copyright:
© Copyright 1991
American Mathematical Society