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), 71116
MSC:
Primary 58F40; Secondary 70B15, 70Q05
MathSciNet review:
1012512
Fulltext PDF Free Access
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, SpringerVerlag, Berlin,
1987. Translated from the French by M. Cole and S. Levy. 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]
Morris
W. Hirsch, Differential topology, SpringerVerlag, New York,
1976. Graduate Texts in Mathematics, No. 33. MR 0448362
(56 #6669)
 [5]
N. Hogan, Impedance control: An approach to manipulation, ASME J. Dynamics Systems, Measurement, and Control 107 (1985), 17.
 [6]
Witold
Hurewicz and Henry
Wallman, Dimension Theory, Princeton Mathematical Series, v.
4, Princeton University Press, Princeton, N. J., 1941. MR 0006493
(3,312b)
 [7]
John
L. Kelley, General topology, SpringerVerlag, New York, 1975.
Reprint of the 1955 edition [Van Nostrand, Toronto, Ont.]; Graduate Texts
in Mathematics, No. 27. MR 0370454
(51 #6681)
 [8]
O. Khatib, Real time obstacle avoidance for manipulators and mobile robots, Internat. J. Robotics Res. 5 (1986), 9099.
 [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. 902923.
 [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 (92b:58035), http://dx.doi.org/10.1016/01968858(90)90017S
 [13]
Elon
L. Lima, The JordanBrouwer separation theorem for smooth
hypersurfaces, Amer. Math. Monthly 95 (1988),
no. 1, 39–42. MR 935429
(89i:53007), http://dx.doi.org/10.2307/2323445
 [14]
W. S. Massey, Introduction to algebraic topology, SpringerVerlag, New York, 1972.
 [15]
William
S. Massey, Singular homology theory, Graduate Texts in
Mathematics, vol. 70, SpringerVerlag, New York, 1980. MR 569059
(81g:55002)
 [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
(37 #2239)
 [17]
Marston
Morse, The existence of polar nondegenerate 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]
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 (85h:52014), http://dx.doi.org/10.1016/01968858(83)900143
 [21]
I.
M. Singer and J.
A. Thorpe, Lecture notes on elementary topology and geometry,
SpringerVerlag, New York, 1976. Reprint of the 1967 edition; Undergraduate
Texts in Mathematics. MR 0413152
(54 #1273)
 [22]
Stephen
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,
SpringerVerlag, New York, 1979. Undergraduate Texts in Mathematics. MR 528129
(80e:53001)
 [24]
Eberhard
Zeidler, Nonlinear functional analysis and its applications.
I, SpringerVerlag, New York, 1986. Fixedpoint theorems; Translated
from the German by Peter R. Wadsack. MR 816732
(87f:47083)
 [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, SpringerVerlag, 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, SpringerVerlag, 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), 17.
 [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, SpringerVerlag, 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), 9099.
 [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. 902923.
 [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 JordanBrouwer separation theorem for smooth hypersurfaces. Amer. Math. Monthly 71 (2) (1988), 3942. MR 935429 (89i:53007)
 [14]
 W. S. Massey, Introduction to algebraic topology, SpringerVerlag, New York, 1972.
 [15]
 , Singular homology theory, SpringerVerlag, 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 nondegenerate functions on differentiable manifolds, Ann. of Math. (2) 71 (1960), 352383. 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), 298351. MR 712908 (85h:52014)
 [21]
 I. M. Singer and J. A. Thorpe, Lecture notes on elementary topology and geometry, SpringerVerlag, New York, 1976. MR 0413152 (54:1273)
 [22]
 S. Smale, On gradient dynamical systems, Ann. of Math. (2) 74 (1961), 199206. MR 0133139 (24:A2973)
 [23]
 John A. Thorpe, Elementary topics in differential geometry, SpringerVerlag, New York, 1979. MR 528129 (80e:53001)
 [24]
 E. Zeidler, Nonlinear functional analysis and its applications. I, SpringerVerlag, New York, 1984. MR 816732 (87f:47083)
Similar Articles
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:
http://dx.doi.org/10.1090/S0002994719911012512X
PII:
S 00029947(1991)1012512X
Article copyright:
© Copyright 1991 American Mathematical Society
