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]**M. Berger,*Geometry*. I, Springer-Verlag, New York, 1980. MR**882541 (88a:51001a)****[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]**M. W. Hirsch,*Differential topology*, Springer-Verlag, New York, 1976. MR**0448362 (56:6669)****[5]**N. Hogan,*Impedance control*:*An approach to manipulation*, ASME J. Dynamics Systems, Measurement, and Control**107**(1985), 1-7.**[6]**W. Hurewicz and H. Wallman,*Dimension theory*, Princeton Univ. Press, Princeton, N.J., 1962. MR**0006493 (3:312b)****[7]**J. L. Kelley,*General topology*, Springer-Verlag, New York, 1985. MR**0370454 (51:6681)****[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]**-,*Robot navigation functions on manifolds with boundary*, Adv. in Appl. Math, (to appear). MR**1077256 (92b:58035)****[13]**E. L. Lima,*The Jordan-Brouwer separation theorem for smooth hypersurfaces*. Amer. Math. Monthly**71**(2) (1988), 39-42. MR**935429 (89i:53007)****[14]**W. S. Massey,*Introduction to algebraic topology*, Springer-Verlag, New York, 1972.**[15]**-,*Singular homology theory*, Springer-Verlag, New York, 1980. MR**569059 (81g:55002)****[16]**J. W. Milnor,*Topology from the differentiable viewpoint*, The University Press of Virginia, Charlottesville, Va., 1965. MR**0226651 (37:2239)****[17]**M. Morse,*The existence of polar non-degenerate functions on differentiable manifolds*, Ann. of Math. (2)**71**(1960), 352-383. MR**0113232 (22:4070)****[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]**J. T. Schwartz and M. Sharir,*On the "piano movers" problem*. II.*general techniques for computing topological properties of real algebraic manifolds*, Adv. in Appl. Math.**4**(1983), 298-351. MR**712908 (85h:52014)****[21]**I. M. Singer and J. A. Thorpe,*Lecture notes on elementary topology and geometry*, Springer-Verlag, New York, 1976. MR**0413152 (54:1273)****[22]**S. Smale,*On gradient dynamical systems*, Ann. of Math. (2)**74**(1961), 199-206. MR**0133139 (24:A2973)****[23]**John A. Thorpe,*Elementary topics in differential geometry*, Springer-Verlag, New York, 1979. MR**528129 (80e:53001)****[24]**E. Zeidler,*Nonlinear functional analysis and its applications*. I, Springer-Verlag, New York, 1984. MR**816732 (87f:47083)**

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