Bibliography

1
D. Aarno, D. Kragic, and H. I. Christensen.
Artificial potential biased probabilistic roadmap method.
In Proceedings IEEE International Conference on Robotics & Automation, 2004.

2
R. Abgrall.
Numerical discretization of the first-order Hamilton-Jacobi equation on triangular meshes.
Communications on Pure and Applied Mathematics, 49(12):1339-1373, December 1996.

3
R. Abraham and J. Marsden.
Foundations of Mechanics.
Addison-Wesley, Reading, MA, 2002.

4
R. Abraham, J. Marsden, and T. Ratiu.
Manifolds, Tensor Analysis, and Applications, 2nd Ed.
Springer-Verlag, Berlin, 1988.

5
A. Abrams and R. Ghrist.
Finding topology in a factory: Configuration spaces.
The American Mathematics Monthly, 109:140-150, February 2002.

6
E. U. Acar and H. Choset.
Complete sensor-based coverage with extended-range detectors: A hierarchical decomposition in terms of critical points and Voronoi diagrams.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2001.

7
E. U. Acar and H. Choset.
Robust sensor-based coverage of unstructured environments.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2001.

8
C. C. Adams.
The Knot Book: An Elementary Introduction to the Mathematical Theory of Knots.
W. H. Freeman, New York, 1994.

9
P. Agarwal, M. de Berg, D. Halperin, and M. Sharir.
Efficient generation of $ k$-directional assembly sequences.
In ACM Symposium on Discrete Algorithms, pages 122-131, 1996.

10
P. K. Agarwal, N. Amenta, B. Aronov, and M. Sharir.
Largest placements and motion planning of a convex polygon.
In J.-P. Laumond and M. Overmars, editors, Robotics: The Algorithmic Perspective. A.K. Peters, Wellesley, MA, 1996.

11
P. K. Agarwal, B. Aronov, and M. Sharir.
Motion planning for a convex polygon in a polygonal environment.
Discrete and Computational Geometry, 22:201-221, 1999.

12
P. K. Agarwal, J.-C. Latombe, R. Motwani, and P. Raghavan.
Nonholonomic path planning for pushing a disk among obstacles.
In Proceedings IEEE International Conference on Robotics & Automation, 1997.

13
P. K. Agarwal, P. Raghavan, and H.Tamaki.
Motion planning for a steering constrained robot through moderate obstacles.
In Proceedings ACM Symposium on Computational Geometry, 1995.

14
S. Akella, W. H. Huang, K. M. Lynch, and M. T. Mason.
Parts feeding on a conveyor with a one joint robot.
Algorithmica, 26(3/4):313-344, March/April 2000.

15
S. Akella and S. Hutchinson.
Coordinating the motions of multiple robots with specified trajectories.
In Proceedings IEEE International Conference on Robotics & Automation, pages 624-631, 2002.

16
R. Alami, J.-P. Laumond, and T. Siméon.
Two manipulation planning algorithms.
In J.-P. Laumond and M. Overmars, editors, Algorithms for Robotic Motion and Manipulation. A.K. Peters, Wellesley, MA, 1997.

17
R. Alami, T. Siméon, and J.-P. Laumond.
A geometrical approach to planning manipulation tasks.
In Proceedings International Symposium on Robotics Research, pages 113-119, 1989.

18
G. Allgower and K. Georg.
Numerical Continuation Methods.
Springer-Verlag, Berlin, 1990.

19
E. Alpaydin.
Machine Learning.
MIT Press, Cambridge, MA, 2004.

20
H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. Näher, S. Schirra, and C. Uhrig.
Approximate motion planning and the complexity of the boundary of the union of simple geometric figures.
In Proceedings ACM Symposium on Computational Geometry, pages 281-289, 1990.

21
N. M. Amato, O. B. Bayazit, L. K. Dale, C. Jones, and D. Vallejo.
Choosing good distance metrics and local planners for probabilistic roadmap methods.
In Proceedings IEEE International Conference on Robotics & Automation, pages 630-637, 1998.

22
N. M. Amato, O. B. Bayazit, L. K. Dale, C. Jones, and D. Vallejo.
OBPRM: An obstacle-based PRM for 3D workspaces.
In Proceedings Workshop on Algorithmic Foundations of Robotics, pages 155-168, 1998.

23
N. M. Amato, O. B. Bayazit, L. K. Dale, C. Jones, and D. Vallejo.
Choosing good distance metrics and local planners for probabilistic roadmap methods.
IEEE Transactions on Robotics & Automation, 16(4):442-447, Aug 2000.

24
N. M. Amato, K. A. Dill, and G. Song.
Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures.
In Proceedings 6th ACM International Conference on Computational Molecular Biology (RECOMB), pages 2-11, 2002.

25
N. M. Amato and G. Song.
Using motion planning to study protein folding pathways.
Journal of Computational Biology, 9(2):149-168, 2002.

26
N. M. Amato and Y. Wu.
A randomized roadmap method for path and manipulation planning.
In Proceedings IEEE International Conference on Robotics & Automation, pages 113-120, 1996.

27
F. Ancona and A. Bressan.
Patchy vector fields and asymptotic stabilization.
ESAIM-Control, Optimisation and Calculus of Variations, 4:445-471, 1999.

28
B. D. Anderson and J. B. Moore.
Optimal Control: Linear-Quadratic Methods.
Prentice-Hall, Englewood Cliffs, NJ, 1990.

29
J. Angeles.
Spatial Kinematic Chains. Analysis, Synthesis, and Optimisation.
Springer-Verlag, Berlin, 1982.

30
J. Angeles.
Fundamentals of Robotic Mechanical Systems: Theory, Methods, and Algorithms.
Springer-Verlag, Berlin, 2003.

31
D. A. Anisi, J. Hamberg, and X. Hu.
Nearly time-optimal paths for a ground vehicle.
Journal of Control Theory and Applications, November 2003.

32
E. Anshelevich, S. Owens, F. Lamiraux, and L. E. Kavraki.
Deformable volumes in path planning applications.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2290-2295, 2000.

33
M. Apaydin, D. Brutlag, C. Guestrin, D. Hsu J.-C. Latombe, and C. Varm.
Stochastic roadmap simulation: An efficient representation and algorithm for analyzing molecular motion.
Journal of Computational Biology, 10:257-281, 2003.

34
M. D. Ardema and J. M. Skowronski.
Dynamic game applied to coordination control of two arm robotic system.
In R. P. Hämäläinen and H. K. Ehtamo, editors, Differential Games - Developments in Modelling and Computation, pages 118-130. Springer-Verlag, Berlin, 1991.

35
O. Arikan and D. Forsyth.
Interactive motion generation from examples.
In Proceedings ACM SIGGRAPH, 2002.

36
E. M. Arkin and R. Hassin.
Approximation algorithms for the geometric covering traveling salesman problem.
Discrete Applied Mathematics, 55:194-218, 1994.

37
B. Armstrong, O. Khatib, and J. Burdick.
The explicit dynamic model and inertial parameters of the Puma 560 arm.
In Proceedings IEEE International Conference on Systems, Man, & Cyberetics, pages 510-518, 1986.

38
M. A. Armstrong.
Basic Topology.
Springer-Verlag, New York, 1983.

39
V. I. Arnold.
Mathematical Methods of Classical Mechanics, 2nd Ed.
Springer-Verlag, Berlin, 1989.

40
D. S. Arnon.
Geometric reasoning with logic and algebra.
Artificial Intelligence Journal, 37(1-3):37-60, 1988.

41
B. Aronov, M. de Berg, A. F. van der Stappen, P. Svestka, and J. Vleugels.
Motion planning for multiple robots.
Discrete and Computational Geometry, 22:505-525, 1999.

42
B. Aronov and M. Sharir.
On translational motion planning of a convex polyhedron in 3-space.
SIAM Journal on Computing, 26(6):1875-1803, December 1997.

43
K. Arras, N. Tomatis, B. Jensen, and R. Siegwart.
Multisensor on-the-fly localization: Precision and reliability for applications.
Robotics and Autonomous Systems, 34(2-3):131-143, 2001.

44
D. K. Arrowsmith and C. M. Place.
Dynamical Systems: Differential Equations, Maps, and Chaotic Behaviour.
Chapman & Hall/CRC, New York, 1992.

45
S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp.
A tutorial on particle filters for on-line non-linear/non-Gaussian Bayesian tracking.
IEEE Transactions on Signal Processing, 50(2):174-188, 2002.

46
S. Arya and D. M. Mount.
Algorithms for fast vector quantization.
In IEEE Data Compression Conference, pages 381-390, March 1993.

47
S. Arya and D. M. Mount.
Approximate nearest neighbor queries in fixed dimensions.
In Proceedings ACM-SIAM Symposium on Discrete Algorithms, pages 271-280, 1993.

48
S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu.
An optimal algorithm for approximate nearest neighbor searching.
Journal of the ACM, 45:891-923, 1998.

49
R. B. Ash.
Information Theory.
Dover, New York, 1990.

50
K. J. Astrom and T. Hagglund.
PID Controllers: Theory, Design, and Tuning, 2nd Ed.
The Instrument, Systems, and Automation Society, Research Triangle Park, NC, 1995.

51
K. E. Atkinson.
An Introduction to Numerical Analysis.
Wiley, New York, 1978.

52
A. Atramentov and S. M. LaValle.
Efficient nearest neighbor searching for motion planning.
In Proceedings IEEE International Conference on Robotics and Automation, pages 632-637, 2002.

53
J.-P. Aubin and A. Cellina.
Differential Inclusions.
Springer-Verlag, Berlin, 1984.

54
F. Aurenhammer.
Voronoi diagrams - A survey of a fundamental geometric structure.
ACM Computing Surveys, 23:345-405, 1991.

55
F. Avnaim, J.-D. Boissonnat, and B. Faverjon.
A practical exact planning algorithm for polygonal objects amidst polygonal obstacles.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1656-1660, 1988.

56
J. Bañon.
Implementation and extension of the ladder algorithm.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1548-1553, 1990.

57
T. Basar.
Game theory and $ {H}^{\infty}$-optimal control: The continuous-time case.
In R. P. Hämäläinen and H. K. Ehtamo, editors, Differential Games - Developments in Modelling and Computation, pages 171-186. Springer-Verlag, Berlin, 1991.

58
T. Basar and P. R. Kumar.
On worst case design strategies.
Computers and Mathematics with Applications, 13(1-3):239-245, 1987.

59
T. Basar and G. J. Olsder.
Dynamic Noncooperative Game Theory, 2nd Ed.
Academic, London, 1995.

60
R. A. Baeza, J. C. Culberson, and G. J. E. Rawlins.
Searching in the plane.
Information and Computation, 106(2):234-252, 1993.

61
B. Baginski.
The $ {Z}^3$ method for fast path planning in dynamic environments.
In Proceedings IASTED Conference on Applications of Control and Robotics, pages 47-52, 1996.

62
B. Baginski.
Motion Planning for Manipulators with Many Degrees of Freedom - The BB-Method.
PhD thesis, Technical University of Munich, 1998.

63
A. Baker.
Matrix Groups.
Springer-Verlag, Berlin, 2002.

64
D. J. Balkcom and M. T. Mason.
Time optimal trajectories for bounded velocity differential drive vehicles.
International Journal of Robotics Research, 21(3):199-217, 2002.

65
D. J. Balkcom and M. T. Mason.
Introducing robotic origami folding.
In Proceedings IEEE International Conference on Robotics & Automation, 2004.

66
J. E. Banta, Y. Zhien, X. Z. Wang, G. Zhang, M. T. Smith, and M. A. Abidi.
A ``best-next-view'' algorithm for three-dimensional scene reconstruction using range images.
In Proceedings SPIE, vol. 2588, pages 418-29, 1995.

67
J. Barraquand and P. Ferbach.
A penalty function method for constrained motion planning.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1235-1242, 1994.

68
J. Barraquand and P. Ferbach.
Motion planning with uncertainty: The information space approach.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1341-1348, 1995.

69
J. Barraquand, L. Kavraki, J.-C. Latombe, T.-Y. Li, R. Motwani, and P. Raghavan.
A random sampling scheme for robot path planning.
In G. Giralt and G. Hirzinger, editors, Proceedings International Symposium on Robotics Research, pages 249-264. Springer-Verlag, New York, 1996.

70
J. Barraquand and J.-C. Latombe.
A Monte-Carlo algorithm for path planning with many degrees of freedom.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1712-1717, 1990.

71
J. Barraquand and J.-C. Latombe.
Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2328-2335, 1991.

72
J. Barraquand and J.-C. Latombe.
Robot motion planning: A distributed representation approach.
International Journal of Robotics Research, 10(6):628-649, December 1991.

73
J. Barraquand and J.-C. Latombe.
Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles.
Algorithmica, 10:121-155, 1993.

74
A. G. Barto, R. S. Sutton, and C. J. C. H. Watkins.
Learning and sequential decision making.
In M. Gabriel and J.W. Moore, editors, Learning and Computational Neuroscience: Foundations of Adaptive Networks, pages 539-602. MIT Press, Cambridge, MA, 1990.

75
J. Basch, L. J. Guibas, D. Hsu, and A. T. Nguyen.
Disconnection proofs for motion planning.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1765-1772, 2001.

76
S. Basu, R. Pollack, and M. F. Roy.
Computing roadmaps of semi-algebraic sets on a variety.
Journal of the American Society of Mathematics, 3(1):55-82, 1999.

77
S. Basu, R. Pollack, and M.-F. Roy.
Algorithms in Real Algebraic Geometry.
Springer-Verlag, Berlin, 2003.

78
K. Basye and T. Dean.
Map learning with indistinguishable locations.
In M. Henrion, L. N. Kanal, and J. F. Lemmer, editors, Uncertainty in Artificial Intelligence 5, pages 331-340. Elsevier Science, New York, 1990.

79
K. Basye, T. Dean, J. Kirman, and M. Lejter.
A decision-theoretic approach to planning, perception, and control.
IEEE Expert, 7(4):58-65, August 1992.

80
T. Bayes.
An essay towards solving a problem in the doctrine of chances.
Philosophical Transactions of the Royal Society of London, 53, 1763.

81
C. Becker, H. González-Baños, J.-C. Latombe, and C. Tomasi.
An intelligent observer.
In Preprints of International Symposium on Experimental Robotics, pages 94-99, 1995.

82
K. E. Bekris, B. Y. Chen, A. Ladd, E. Plaku, and L. E. Kavraki.
Multiple query probabilistic roadmap planning using single query primitives.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.

83
A. Bellaiche, F. Jean, and J. J. Risler.
Geometry of nonholonomic systems.
In J.-P. Laumond, editor, Robot Motion Planning and Control, pages 55-92. Springer-Verlag, Berlin, 1998.

84
R. E. Bellman.
Dynamic Programming.
Princeton University Press, Princeton, NJ, 1957.

85
R. E. Bellman and S. E. Dreyfus.
Applied Dynamic Programming.
Princeton University Press, Princeton, NJ, 1962.

86
I. Belousov, C. Esteves, J.-P. Laumond, and E. Ferre.
Motion planning for large space manipulators with complicated dynamics.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005.

87
M. A. Bender, A. Fernandez, D. Ron, A. Sahai, and S. Vadhan.
The power of a pebble: Exploring and mapping directed graphs.
In Proceedings Annual Symposium on Foundations of Computer Science, 1998.

88
A. Benveniste, M. Metivier, and P. Prourier.
Adaptive Algorithms and Stochastic Approximations.
Springer-Verlag, Berlin, 1990.

89
J. O. Berger.
Statistical Decision Theory.
Springer-Verlag, Berlin, 1980.

90
M. Bern.
Triangulations and mesh generation.
In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, 2nd Ed., pages 563-582. Chapman and Hall/CRC Press, New York, 2004.

91
J. Bernard, J. Shannan, and M. Vanderploeg.
Vehicle rollover on smooth surfaces.
In Proceedings SAE Passenger Car Meeting and Exposition, Dearborn, MI, 1989.

92
D. P. Bertsekas.
Convergence in discretization procedures in dynamic programming.
IEEE Transactions on Automatic Control, 20(3):415-419, June 1975.

93
D. P. Bertsekas.
Dynamic Programming: Deterministic and Stochastic Models.
Prentice-Hall, Englewood Cliffs, NJ, 1987.

94
D. P. Bertsekas.
Nonlinear Programming.
Athena Scientific, Belmont, MA, 1999.

95
D. P. Bertsekas.
Dynamic Programming and Optimal Control, Vol. I, 2nd Ed.
Athena Scientific, Belmont, MA, 2001.

96
D. P. Bertsekas.
Dynamic Programming and Optimal Control, Vol. II, 2nd Ed.
Athena Scientific, Belmont, MA, 2001.

97
D. P. Bertsekas and J. N. Tsitsiklis.
Neuro-Dynamic Programming.
Athena Scientific, Belmont, MA, 1996.

98
J. T. Betts.
Survey of numerical methods for trajectory optimization.
Journal of Guidance, Control, and Dynamics, 21(2):193-207, March-April 1998.

99
A. Beygelzimer, S. M. Kakade, and J. Langford.
Cover trees for nearest neighbor.
University of Pennsylvania, Available from http://www.cis.upenn.edu/$ \sim$skakade/papers/ml/cover_tree.pdf, 2005.

100
A. Bhatia and E. Frazzoli.
Incremental search methods for reachability analysis of continuous and hybrid systems.
In R. Alur and G. J. Pappas, editors, Hybrid Systems: Computation and Control, pages 67-78. Springer-Verlag, Berlin, 2004.
Lecture Notes in Computer Science, 2993.

101
S. Bhattacharya and S. K. Agrawal.
Design, experiments and motion planning of a spherical rolling robot.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1207-1212, 2000.

102
A. Bicchi, A. Marigo, and B. Piccoli.
On the reachability of quantized control systems.
IEEE Transactions on Automatic Control, 47(4):546-563, April 2002.

103
A. Bicchi, D. Prattichizzo, and S. Sastry.
Planning motions of rolling surfaces.
In Proceedings IEEE Conference Decision & Control, 1995.

104
Z. Bien and J. Lee.
A minimum-time trajectory planning method for two robots.
IEEE Transactions on Robotics & Automation, 8(3):414-418, June 1992.

105
D. Bienstock and P. Seymour.
Monotonicity in graph searching.
Journal of Algorithms, 12:239-245, 1991.

106
J. Bilmes.
A gentle tutorial on the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models.
Technical Report ICSI-TR-97-021, International Computer Science Institute (ICSI), Berkeley, CA, 1997.

107
R. L. Bishop and S. I. Goldberg.
Tensor Analysis on Manifolds.
Dover, New York, 1980.

108
H. S. Black.
Stabilized feedback amplifiers.
Bell Systems Technical Journal, 13:1-18, 1934.

109
D. Blackwell and M. A. Girshik.
Theory of Games and Statistical Decisions.
Dover, New York, 1979.

110
S. Blind, C. McCullough, S. Akella, and J. Ponce.
Manipulating parts with an array of pins: A method and a machine.
International Journal of Robotics Research, 20(10):808-818, December 2001.

111
A. Bloch.
Murphy's Law and Other Reasons Why Things Go Wrong.
Price Stern Sloan Adult, New York, 1977.

112
A. M. Bloch.
Nonholonomic Mechanics and Control.
Springer-Verlag, Berlin, 2003.

113
A. M. Bloch and P. E. Crouch.
Nonholonomic control systems on Riemannian manifolds.
SIAM Journal on Control & Optimization, 33:126-148, 1995.

114
V. D. Blondel and J. N. Tsitsiklis.
A survey of computational complexity results in systems and control.
Automatica, 36(9):1249-1274, September 2000.

115
A. Blum, S. Chawla, D. Karger, T. Lane, A. Meyerson, and M. Minkoff.
Approximation algorithms for orienteering and discounted-reward TSP.
In Proceedings IEEE Symposium on Foundations of Computer Science, 2003.

116
A. Blum, P. Raghavan, and B. Schieber.
Navigating in unfamiliar geometric terrains.
In Proceedings ACM Symposium on Computational Geometry, pages 494-504, 1991.

117
A. L. Blum and M. L. Furst.
Fast planing through planning graph analysis.
In Proceedings International Joint Conference on Artificial Intelligence, pages 1636-1642, 1995.

118
L. Blum, F. Cucker, and M. Schub abd S. Smale.
Complexity and Real Computation.
Springer-Verlag, Berlin, 1998.

119
M. Blum and D. Kozen.
On the power of the compass (or, why mazes are easier to search than graphs).
In Proceedings Annual Symposium on Foundations of Computer Science, pages 132-142, 1978.

120
J. E. Bobrow.
Optimal robot path planning using the minimum-time criterion.
IEEE Transactions on Robotics & Automation, 4(4):443-450, August 1988.

121
J. E. Bobrow, S. Dubowsky, and J. S. Gibson.
Time-optimal control of robotic manipulators along specified paths.
International Journal of Robotics Research, 4(3):3-17, 1985.

122
H. Bode.
Feedback: The history of an idea.
In R. Bellman and R. Kalaba, editors, Selected Papers on Mathematical Trends in Control Theory, pages 106-123. Dover, New York, 1969.

123
R. Bohlin.
Path planning in practice; lazy evaluation on a multi-resolution grid.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2001.

124
R. Bohlin.
Robot Path Planning.
PhD thesis, Chalmers University, Gothenburg, Sweden, 2002.

125
R. Bohlin and L. Kavraki.
Path planning using Lazy PRM.
In Proceedings IEEE International Conference on Robotics & Automation, 2000.

126
K.-F. Böhringer, B. R. Donald, and N. C. MacDonald.
Upper and lower bounds for programmable vector fields with applications to MEMS and vibratory plate parts feeders.
In J.-P. Laumond and M. Overmars, editors, Algorithms for Robotic Motion and Manipulation. A.K. Peters, Wellesley, MA, 1997.

127
J.-D. Boissonnat, A. Cérézo, and J. Leblond.
Shortest paths of bounded curvature in the plane.
Journal of Intelligent and Robotic Systems, 11:5-20, 1994.

128
J.-D. Boissonnat and S. Lazard.
A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles.
In Proceedings ACM Symposium on Computational Geometry, pages 242-251, 1996.

129
J.-D. Boissonnat and M. Yvinec.
Algorithmic Geometry.
Cambridge University Press, Cambridge, U.K., 1998.

130
V. G. Boltyanskii.
Sufficient conditions for optimality and the justification of the dynamic programming method.
SIAM Journal on Control, 4:326-361, 1966.

131
G. Boo and K. Goldberg.
Orienting polygonal parts without sensors: An implementation in Java.
Alpha Lab, UC Berkeley. Available from http://www.ieor.berkeley.edu/$ \sim$goldberg/feeder-S05/, 2005.

132
V. Boor, M. H. Overmars, and A. F. van der Stappen.
The Gaussian sampling strategy for probabilistic roadmap planners.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1018-1023, 1999.

133
W. M. Boothby.
An Introduction to Differentiable Manifolds and Riemannian Geometry. Revised 2nd Ed.
Academic, New York, 2003.

134
J. Borenstein, B. Everett, and L. Feng.
Navigating Mobile Robots: Systems and Techniques.
A.K. Peters, Wellesley, MA, 1996.

135
A. V. Borisov and I .S. Mamaev.
On the history of the development of nonholonomic dynamics.
Regular and Chaotic Dynamics, 7(1):43-47, 2002.

136
P. Bose, A. Lubiv, and J. I. Munro.
Efficient visibility queries in simple polygons.
In Proceedings Canadian Conference on Computational Geometry, pages 23-28, 1992.

137
M. S. Branicky, V. S. Borkar, and S. K. Mitter.
A unified framework for hybrid control: Model and optimal control theory.
IEEE Transactions on Automatic Control, 43(1):31-45, 1998.

138
M. S. Branicky, M. M. Curtiss, J. Levine, and S. Morgan.
RRTs for nonlinear, discrete, and hybrid planning and control.
In Proceedings IEEE Conference Decision & Control, 2003.

139
M. Bridson and A. Haefliger.
Metric Spaces of Non-Positive Curvature.
Springer-Verlag, Berlin, 1999.

140
A. Briggs.
An efficient algorithm for one-step compliant motion planning with uncertainty.
In Proceedings ACM Symposium on Computational Geometry, 1989.

141
A. J. Briggs and B. R. Donald.
Robust geometric algorithms for sensor planning.
In J.-P. Laumond and M. Overmars, editors, Proceedings Workshop on Algorithmic Foundations of Robotics. A.K. Peters, Wellesley, MA, 1996.

142
R. W. Brockett.
Control theory and singular Riemannian geometry.
In P. A. Fuhrman, editor, New Directions in Applied Mathematics, pages 11-27. Springer-Verlag, Berlin, 1981.

143
R. W. Brockett.
Asymptotic stability and feedback stabilization.
In R. W. Brockett, R. S. Millman, and H. J. Sussmann, editors, Differential Geometric Control Theory, pages 181-191. Birkhäuser, Boston, MA, 1983.

144
R. A. Brooks and T. Lozano-Pérez.
A subdivision algorithm in configuration space for findpath with rotation.
IEEE Transactions on Systems, Man, & Cybernetics, SMC-15(2):224-233, 1985.

145
R. C. Brost.
Automatic grasp planning in the presence of uncertainty.
International Journal of Robotics Research, 7(1):3-17, 1988.

146
R. C. Brost.
Analysis and Planning of Planar Manipulation Tasks.
PhD thesis, Carnegie Mellon University, Pittsburgh, PA, 1991.

147
R. C. Brost and A. D. Christiansen.
Probabilistic analysis of manipulation tasks: A research agenda.
In Proceedings IEEE International Conference on Robotics & Automation, volume 3, pages 549-556, 1993.

148
R. C. Brost and A. D. Christiansen.
Probabilistic analysis of manipulation tasks: A computational framework.
Technical Report SAND92-2033, Sandia National Laboratories, Albuquerque, NM, January 1994.

149
R. C. Brost and A. D. Christiansen.
Probabilistic analysis of manipulation tasks: A computational framework.
International Journal of Robotics Research, 15(1):1-23, February 1996.

150
J. Bruce and M. Veloso.
Real-time randomized path planning for robot navigation.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2002.

151
A. E. Bryson and Y.-C. Ho.
Applied Optimal Control.
Hemisphere Publishing Corp., New York, 1975.

152
M. Buckland.
AI Techniques for Game Programming.
Premier Press, Portland, OR, 2002.

153
S. J. Buckley.
Fast motion planning for multiple moving robots.
In Proceedings IEEE International Conference on Robotics & Automation, pages 322-326, 1989.

154
F. Bullo.
Series expansions for the evolution of mechanical control systems.
SIAM Journal on Control & Optimization, 40(1):166-190, 2001.

155
F. Bullo.
Series expansions for analytic systems linear in control.
Automatica, 38(9):1425-1432, September 2002.

156
F. Bullo and A. D. Lewis.
Geometric Control of Mechanical Systems.
Springer-Verlag, Berlin, 2004.

157
F. Bullo and K. M. Lynch.
Kinematic controllability for decoupled trajectory planning in underactuated mechanical systems.
IEEE Transactions on Robotics & Automation, 17(4):402-412, 2001.

158
J. W. Burdick.
Kinematic Analysis and Design of Redundant Manipulators.
PhD thesis, Stanford University, Stanford, CA, 1988.

159
W. Burgard, A. B. Cremers, D. Fox, D. Hähnel, G. Lakemeyer, D. Schulz, W. Steiner, and S. Thrun.
The interactive museum tour-guide robot.
In Proceedings AAAI National Conference on Artificial Intelligence, pages 11-18, 1998.

160
J. J. Burken, P. Lu, and Z. Wu.
Reconfigurable flight control designs with application to the X-33 vehicle.
Technical Report TM-1999-206582, NASA, Washington, DC, 1999.

161
B. Burns and O. Brock.
Sampling-based motion planning using predictive models.
In Proceedings IEEE International Conference on Robotics & Automation, 2005.

162
R. R. Burridge, A. A. Rizzi, and D. E. Koditschek.
Sequential composition of dynamically dexterous robot behaviors.
International Journal of Robotics Research, 18(6):534-555, 1999.

163
L. G. Bushnell, D. M. Tilbury, and S. S. Sastry.
Steering three-input nonholonomic systems: the fire truck example.
International Journal of Robotics Research, 14(4):366-381, 1995.

164
Z. J. Butler, A. A. Rizzi, and R. L. Hollis.
Contact sensor-based coverage of rectilinear environments.
In IEEE Symposium on Intelligent Control, 1999.

165
Z. J. Butler and D. Rus.
Distributed motion planning for modular robots with unit-compressible modules.
International Journal of Robotics Research, 22(9):699-716, 2003.

166
S. Cambon, F. Gravot, and R. Alami.
A robot task planner and merges symbolic and geometric reasoning.
In Proceedings European Conference on Artificial Intelligence, 2004.

167
S. Cameron.
A comparison of two fast algorithms for computing the distance between convex polyhedra.
IEEE Transactions on Robotics & Automation, 13(6):915-920, December 1997.

168
F. Camilli and M. Falcone.
Approximation of optimal control problems with state constraints: Estimates and applications.
In B. S. Mordukhovich and H. J. Sussmann, editors, Nonsmooth Analysis and Geometric Methods in Deterministic Optimal Control, pages 23-57. Springer-Verlag, Berlin, 1996.
Mathematics and its Applications, Vol. 78.

169
J. Canny.
Constructing roadmaps of semi-algebraic sets I.
Artificial Intelligence Journal, 37:203-222, 1988.

170
J. Canny.
Computing roadmaps of general semi-algebraic sets.
The Computer Journal, 36(5):504-514, 1993.

171
J. Canny, A. Rege, and J. Reif.
An exact algorithm for kinodynamic planning in the plane.
Discrete and Computational Geometry, 6:461-484, 1991.

172
J. Canny and J. Reif.
New lower bound techniques for robot motion planning problems.
In Proceedings IEEE Symposium on Foundations of Computer Science, pages 49-60, 1987.

173
J. F. Canny.
The Complexity of Robot Motion Planning.
MIT Press, Cambridge, MA, 1988.

174
J. F. Canny.
On computability of fine motion plans.
In Proceedings IEEE International Conference on Robotics & Automation, pages 177-182, 1989.

175
J. F. Canny and K. Y. Goldberg.
``RISC'' industrial robots: Recent results and current trends.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1951-1958, 1994.

176
J. F. Canny and M. Lin.
An opportunistic global path planner.
Algorithmica, 10:102-120, 1993.

177
S. Carpin and E. Pagello.
On parallel RRTs for multi-robot systems.
In Proceedings 8th Conference of the Italian Association for Artificial Intelligence, pages 834-841, 2002.

178
S. Carpin and G. Pillonetto.
Merging the adaptive random walks planner with the randomized potential field planner.
In Proceedings IEEE International Workshop on Robot Motion and Control, pages 151-156, 2005.

179
S. Carpin and G. Pillonetto.
Robot motion planning using adaptive random walks.
IEEE Transactions on Robotics & Automation, 21(1):129-136, 2005.

180
A. Casal.
Reconfiguration Planning for Modular Self-Reconfigurable Robots.
PhD thesis, Stanford University, Stanford, CA, 2002.

181
S. Caselli and M. Reggiani.
ERPP: An experience-based randomized path planner.
In Proceedings IEEE International Conference on Robotics & Automation, 2000.

182
J. Castellanos, J. Montiel, J. Neira, and J. Tardós.
The SPmap: A probabilistic framework for simultaneous localization and mapping.
IEEE Transactions on Robotics & Automation, 15(5):948-953, 1999.

183
D. Challou, D. Boley, M. Gini, and V. Kumar.
A parallel formulation of informed randomized search for robot motion planning problems.
In Proceedings IEEE International Conference on Robotics & Automation, pages 709-714, 1995.

184
D. D. Champeaux.
Bidirectional heuristic search again.
Journal of the ACM, 30(1):22-32, January 1983.

185
D. D. Champeaux and L. Sint.
An improved bidirectional heuristic search algorithm.
Journal of the ACM, 24(2):177-191, April 1977.

186
H. Chang and T. Y. Li.
Assembly maintainability study with motion planning.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1012-1019, 1995.

187
S. Charentus.
Modeling and Control of a Robot Manipulator Composed of Several Stewart Platforms.
PhD thesis, Université Paul Sabatier, Toulouse, France, 1990.
In French.

188
S. Chawla.
Graph Algorithms for Planning and Partitioning.
PhD thesis, Carnegie Mellon University, Pittsburgh, PA, June 2005.

189
B. Chazelle.
Approximation and decomposition of shapes.
In J. T. Schwartz and C. K. Yap, editors, Algorithmic and Geometric Aspects of Robotics, pages 145-185. Lawrence Erlbaum Associates, Hillsdale, NJ, 1987.

190
B. Chazelle.
Triangulating a simple polygon in linear time.
Discrete and Computational Geometry, 6(5):485-524, 1991.

191
B. Chazelle.
The Discrepancy Method.
Cambridge University Press, Cambridge, U.K., 2000.

192
C.-T. Chen.
Linear System Theory and Design.
Holt, Rinehart, and Winston, New York, 1984.

193
P. C. Chen and Y. K. Hwang.
SANDROS: A motion planner with performance proportional to task difficulty.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2346-2353, 1992.

194
P. C. Chen and Y. K. Hwang.
SANDROS: A dynamic search graph algorithm for motion planning.
IEEE Transactions on Robotics & Automation, 14(3):390-403, 1998.

195
Y.-B. Chen and D. J. Ierardi.
The complexity of oblivious plans for orienting and distinguishing polygonal parts.
Algorithmica, 14:367-397, 1995.

196
P. Cheng.
Sampling-Based Motion Planning with Differential Constraints.
PhD thesis, University of Illinois, Urbana, IL, August 2005.

197
P. Cheng, E. Frazzoli, and S. M. LaValle.
Exploiting group symmetries to improve precision in kinodynamic and nonholonomic planning.
In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.

198
P. Cheng, E. Frazzoli, and S. M. LaValle.
Improving the performance of sampling-based planners by using a symmetry-exploiting gap reduction algorithm.
In Proceedings IEEE International Conference on Robotics and Automation, 2004.

199
P. Cheng and S. M. LaValle.
Reducing metric sensitivity in randomized trajectory design.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 43-48, 2001.

200
P. Cheng and S. M. LaValle.
Resolution complete rapidly-exploring random trees.
In Proceedings IEEE International Conference on Robotics and Automation, pages 267-272, 2002.

201
P. Cheng, Z. Shen, and S. M. LaValle.
Using randomization to find and optimize feasible trajectories for nonlinear systems.
In Proceedings Annual Allerton Conference on Communications, Control, Computing, pages 926-935, 2000.

202
P. Cheng, Z. Shen, and S. M. LaValle.
RRT-based trajectory design for autonomous automobiles and spacecraft.
Archives of Control Sciences, 11(3-4):167-194, 2001.

203
M. Cherif.
Kinodynamic motion planning for all-terrain wheeled vehicles.
In Proceedings IEEE International Conference on Robotics & Automation, 1999.

204
F. L. Chernousko, N. N. Bolotnik, and V. G. Gradetsky.
Manipulation Robots.
CRC Press, Boca Raton, FL, 1994.

205
L. P. Chew and K. Kedem.
A convex polygon among polygonal obstacles: Placement and high-clearance motion.
Computational Geometry: Theory and Applications, 3:59-89, 1993.

206
D. Chibisov, E. W. Mayr, and S. Pankratov.
Spatial planning and geometric optimization: Combining configuration space and energy methods.
In H. Hong and D. Wang, editors, Automated Deduction in Geometry - ADG 2004. Springer-Verlag, Berlin, 2006.

207
S. Chien, R. Sherwood, D. Tran, B. Cichy, D. Mandl, S. Frye, B. Trout, S. Shulman, and D. Boyer.
Using autonomy flight software to improve science return on Earth Observing One.
Journal of Aerospace Computing, Information, and Communication, 2:196-216, April 2005.

208
W.-P. Chin and S. Ntafos.
Optimum watchman routes.
Information Processing Letters, 28:39-44, 1988.

209
G. Chirikjian, A. Pamecha, and I. Ebert-Uphoff.
Evaluating efficiency of self-reconfiguration in a class of modular robots.
Journal of Robotic Systems, 13(5):717-338, 1996.

210
G. S. Chirikjian and A. B. Kyatkin.
Engineering Applications of Noncommutative Harmonic Analysis.
CRC Press, Boca Raton, FL, 2001.

211
H. Chitsaz, S. M. LaValle, D. J. Balkcom, and M. T. Mason.
Minimum wheel-rotation paths for differential-drive mobile robots.
In Proceedings IEEE International Conference on Robotics and Automation, 2006.

212
H. Chitsaz, J. M. O'Kane, and S. M. LaValle.
Pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap.
In Proceedings IEEE International Conference on Robotics and Automation, 2004.

213
S. Chitta, P. Cheng, E. Frazzoli, and V. Kumar.
RoboTrikke: A novel undulatory locomotion system.
In Proceedings IEEE International Conference on Robotics & Automation, 2005.

214
S. Chitta and V. Kumar.
Dynamics and generation of gaits for a planar rollerblader.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.

215
J. Choi, J. Sellen, and C. K. Yap.
Precision-sensitive Euclidean shortest path in 3-space.
In Proceedings ACM Symposium on Computational Geometry, pages 350-359, 1995.

216
H. Choset.
Coverage of known spaces: The boustrophedon cellular decomposition.
Autonomous Robots, 9:247-253, 2000.

217
H. Choset.
Coverage for robotics - A survey of recent results.
Annals of Mathematics and Artificial Intelligence, 31:113-126, 2001.

218
H. Choset and J. Burdick.
Sensor based motion planning: Incremental construction of the hierarchical generalized Voronoi graph.
International Journal of Robotics Research, 19(2):126-148, 2000.

219
H. Choset and J. Burdick.
Sensor based motion planning: The hierarchical generalized Voronoi graph.
International Journal of Robotics Research, 19(2):96-125, 2000.

220
H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki, and S. Thrun.
Principles of Robot Motion: Theory, Algorithms, and Implementations.
MIT Press, Cambridge, MA, 2005.

221
H. Choset and K. Nagatani.
Topological simultaneous localization and mapping (T-SLAM).
IEEE Transactions on Robotics & Automation, 17(2):125-137, 2001.

222
H. Choset and P. Pignon.
Cover path planning: The boustrophedron decomposition.
In Proceedings International Conference on Field and Service Robotics, Canberra, Australia, December 1997.

223
P. Choudhury and K. Lynch.
Rolling manipulation with a single control.
In Proceedings Conference on Control Applications, September 2002.

224
P. Choudhury and K. Lynch.
Trajectory planning for second-order underactuated mechanical systems in presence of obstacles.
In Proceedings Workshop on Algorithmic Foundations of Robotics, 2002.

225
K.-C. Chu.
Team decision theory and information structures in optimal control problems - Part II.
IEEE Transactions on Automatic Control, 17(1):22-28, February 1972.

226
C. K. Chui and G. Chen.
Kalman Filtering.
Springer-Verlag, Berlin, 1991.

227
M. Chyba, H. Sussmann, H. Maurer, and G. Vossen.
Underwater vehicles: The minimum time problem.
In Proceedings IEEE Conference Decision & Control, The Bahamas, December 2004.

228
C. M. Clark, S. M. Rock, and J.-C. Latombe.
Motion planning for multiple mobile robots using dynamic networks.
In Proceedings IEEE International Conference on Robotics & Automation, 2003.

229
D. E. Clark, G. Jones, P. Willett P. W. Kenny, and R. C. Glen.
Pharmacophoric pattern matching in files of three-dimensional chemical structures: Comparison of conformational searching algorithms for flexible searching.
Journal Chemical Information and Computational Sciences, 34:197-206, 1994.

230
K. L. Clarkson.
Nearest neighbor searching in metric spaces: Experimental results for sb(s).
Bell Labs. Available from http://cm.bell-labs.com/who/clarkson/Msb/readme.html, 2003.

231
F. S. Cohen and D. B. Cooper.
Simple parallel hierarchical and relaxation algorithms for segmenting noncausal Markovian random fields.
IEEE Transactions Pattern Analysis Machine Intelligence, 9(2):195-219, March 1987.

232
G. E. Collins.
Quantifier elimination for real closed fields by cylindrical algebraic decomposition.
In Proceedings Second GI Conference on Automata Theory and Formal Languages, pages 134-183, Berlin, 1975. Springer-Verlag.
Lecture Notes in Computer Science, 33.

233
G. E. Collins.
Quantifier elimination by cylindrical algebraic decomposition-twenty years of progress.
In B. F. Caviness and J. R. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, pages 8-23. Springer-Verlag, Berlin, 1998.

234
L. Conlon.
Differentiable Manifolds, 2nd Ed.
Birkhäuser, Boston, MA, 2001.

235
D. C. Conner, A. A. Rizzi, and H. Choset.
Composition of local potential functions for global robot control and navigation.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3546-3551, 2003.

236
C. Connolly and R. Grupen.
The application of harmonic potential functions to robotics.
Journal of Robotic Systems, 10(7):931-946, 1993.

237
C. Connolly, R. Grupen, and K. Souccar.
A Hamiltonian framework for kinodynamic planning.
In Proceedings IEEE International Conference on Robotics & Automation, 1995.

238
C. I. Connolly.
The determination of next best views.
In Proceedings IEEE International Conference on Robotics & Automation, pages 432-435, 1985.

239
C. I. Connolly.
Applications of harmonic functions to robotics.
In IEEE Symposium on Intelligent Control, pages 498-502, 1992.

240
C. I. Connolly, J. B. Burns, and R. Weiss.
Path planning using Laplace's equation.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2102-2106, May 1990.

241
J. H. Conway and N. J. A. Sloane.
Sphere Packings, Lattices, and Groups.
Springer-Verlag, Berlin, 1999.

242
H. W. Corley.
Some multiple objective dynamic programs.
IEEE Transactions on Automatic Control, 30(12):1221-1222, December 1985.

243
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.
Introduction to Algorithms (2nd Ed.).
MIT Press, Cambridge, MA, 2001.

244
J. Cortés.
Motion Planning Algorithms for General Closed-Chain Mechanisms.
PhD thesis, Institut National Polytechnique de Toulouse, Toulouse, France, 2003.

245
J. Cortés, T. Siméon M. Remaud-Siméon, and V. Tran.
Geometric algorithms for the conformational analysis of long protein loops.
Journal of Computational Chemistry, 25:956-967, 2004.

246
J. Cortés, T. Siméon, and J.-P. Laumond.
A random loop generator for planning the motions of closed kinematic chains using PRM methods.
In Proceedings IEEE International Conference on Robotics & Automation, 2002.

247
M. G. Coutinho.
Dynamic Simulations of Multibody Systems.
Springer-Verlag, Berlin, 2001.

248
T. M. Cover and J. A. Thomas.
Elements of Information Theory.
Wiley, New York, 1991.

249
N. Cowan.
Composing navigation functions on Cartesian products of manifolds with boundary.
In Proceedings Workshop on Algorithmic Foundations of Robotics, Zeist, The Netherlands, July 2004.

250
D. Cox, J. Little, and D. O'Shea.
Ideals, Varieties, and Algorithms.
Springer-Verlag, Berlin, 1992.

251
H. S. M. Coxeter.
Regular Polytopes.
Dover, New York, 1973.

252
J. J. Craig.
Introduction to Robotics.
Addison-Wesley, Reading, MA, 1989.

253
M. G. Crandall and P.-L. Lions.
Viscosity solutions of Hamilton-Jacobi equations.
Transactions of the American Mathematical Society, 277(1):1-42, 1983.

254
D. Crass, I. Suzuki, and M. Yamashita.
Searching for a mobile intruder in a corridor - The open edge variant of the polygon search problem.
International Journal Computational Geometry & Applications, 5(4):397-412, 1995.

255
J. C. Culberson.
Sokoban is PSPACE-complete.
In Proceedings International Conference on Fun with Algorithms (FUN98), pages 65-76, Waterloo, Ontario, Canada, June 1998. Carleton Scientific.

256
M. R. Cutkosky.
Robotic Grasping and Fine Manipulation.
Kluwer, Boston, MA, 1985.

257
L. K. Dale and N. M. Amato.
Probabilistic roadmap methods are embarrassingly parallel.
In Proceedings IEEE International Conference on Robotics & Automation, 1999.

258
F. Dallaert, D. Fox, W. Burgard, and S. Thrun.
Monte Carlo localization for mobile robots.
In Proceedings IEEE International Conference on Robotics & Automation, 1999.

259
G. B. Dantzig.
Linear Programming and Extensions.
Princeton University Press, Princeton, NJ, 1963.

260
A. Datta, C. A. Hipke, and S. Schuierer.
Competitive searching in polygons-beyond generalized streets.
In J. Staples, P. Eades, N. Katoh, and A. Moffat, editors, Algorithms and Computation, ISAAC '95, pages 32-41. Springer-Verlag, Berlin, 1995.

261
R. S. Datta.
Using computer algebra to compute Nash equilibria.
In Proceedings International Symposium on Symbolic and Algebraic Computation, 2003.

262
J. Davenport and J. Heintz.
Real quantifier elimination is doubly exponential.
Journal of Symbolic Computation, 5:29-35, 1988.

263
S. Davies.
Multidimensional triangulation and interpolation for reinforcement learning.
In Proceedings Neural Information Processing Systems, 1996.

264
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf.
Computational Geometry: Algorithms and Applications, 2nd Ed.
Springer-Verlag, Berlin, 2000.

265
M. J. de Smith.
Distance and Path: The Development, Interpretation and Application of Distance Measurement in Mapping and Modelling.
PhD thesis, University College, University of London, London, 2003.

266
T. Dean and S. Kambhampati.
Planning and scheduling.
In A. B. Tucker, editor, The CRC Handbook of Computer Science and Engineering, pages 614-636. CRC Press, Boca Raton, FL, 1997.

267
T. L. Dean and M. P. Wellman.
Planning and Control.
Morgan Kaufman, San Francisco, CA, 1991.

268
M. H. DeGroot.
Optimal Statistical Decisions.
McGraw-Hill, New York, 1970.

269
A. P. Dempster, N. M. Laird, and D. B. Rubin.
Maximum-likelihood from incomplete data via the EM algorithm.
Journal of the Royal Statistical Society, Ser. B., 39:1-38, 1977.

270
X. Deng, T. Kameda, and C. Papadimitriou.
How to learn an unknown environment I: The rectilinear case.
Available from http://www.cs.berkeley.edu/$ \sim$christos/, 1997.

271
P. A. Devijver and J. Kittler.
Pattern Recognition: A Statistical Approach.
Prentice-Hall, Englewood Cliffs, NJ, 1982.

272
R. Dial.
Algorithm 360: Shortest path forest with topological ordering.
Communications of the ACM, 12:632-633, 1969.

273
E. W. Dijkstra.
A note on two problems in connexion with graphs.
Numerische Mathematik, 1:269-271, 1959.

274
D. V. Dimarogonas, M. M. Zavlanos, S. G. Loizou, and K. J. Kyriakopoulos.
Decentralized motion control of multiple holonomic agents under input constraints.
In Proceedings IEEE Conference Decision & Control, 2003.

275
G. Dissanayake, P. Newman, S. Clark, H. F. Durrant-Whyte, and M. Csorba.
A solution to the simultaneous localisation and map building (SLAM) problem.
IEEE Transactions on Robotics & Automation, 17(3):229-241, 2001.

276
A. W. Divelbiss and J. T. Wen.
Nonholonomic path planning with inequality constraints.
In Proceedings IEEE International Conference on Robotics & Automation, pages 52-57, 1994.

277
A. W. Divelbiss and J. T. Wen.
A path-space approach to nonholonomic planning in the presence of obstacles.
IEEE Transactions on Robotics & Automation, 13(3):443-451, 1997.

278
W. E. Dixon, A. Behal, D. M. Dawson, and S. Nagarkatti.
Nonlinear Control of Engineering Systems: A Lyapunov-Based Approach.
Birkhäuser, Boston, MA, 2003.

279
M. P. do Carmo.
Riemannian Geometry.
Birkhäuser, Boston, MA, 1992.

280
B. R. Donald.
Motion planning with six degrees of freedom.
Technical Report AI-TR-791, Artificial Intelligence Lab., Massachusetts Institute of Technology, Cambridge, MA, 1984.

281
B. R. Donald.
Error Detection and Recovery for Robot Motion Planning with Uncertainty.
PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1987.

282
B. R. Donald.
A search algorithm for motion planning with six degrees of freedom.
Artificial Intelligence Journal, 31:295-353, 1987.

283
B. R. Donald.
The complexity of planar compliant motion planning under uncertainty.
In Proceedings ACM Symposium on Computational Geometry, pages 309-318, 1988.

284
B. R. Donald.
A geometric approach to error detection and recovery for robot motion planning with uncertainty.
Artificial Intelligence Journal, 37:223-271, 1988.

285
B. R. Donald.
Planning multi-step error detection and recovery strategies.
International Journal of Robotics Research, 9(1):3-60, 1990.

286
B. R. Donald.
On information invariants in robotics.
Artificial Intelligence Journal, 72:217-304, 1995.

287
B. R. Donald and J. Jennings.
Sensor interpretation and task-directed planning using perceptual equivalence classes.
In Proceedings IEEE International Conference on Robotics & Automation, pages 190-197, 1991.

288
B. R. Donald and P. Xavier.
Provably good approximation algorithms for optimal kinodynamic planning for Cartesian robots and open chain manipulators.
Algorithmica, 14(6):480-530, 1995.

289
B. R. Donald and P. Xavier.
Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds.
Algorithmica, 14(6):443-479, 1995.

290
B. R. Donald, P. G. Xavier, J. Canny, and J. Reif.
Kinodynamic planning.
Journal of the ACM, 40:1048-66, November 1993.

291
S. K. Donaldson.
Self-dual connections and the topology of smooth 4-manifold.
Bulletin of the American Mathematical Society, 8:81-83, 1983.

292
A. L. Dontchev.
Discrete approximations in optimal control.
In B. S. Mordukhovich and H. J. Sussmann, editors, Nonsmooth Analysis and Geometric Methods in Deterministic Optimal Control, pages 59-80. Springer-Verlag, Berlin, 1996.
Mathematics and Its Applications, Vol. 78.

293
A. Doucet, N. de Freitas, and N. Gordon.
Sequential Monte Carlo Methods in Practice.
Springer-Verlag, Berlin, 2001.

294
L. E. Dubins.
On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents.
American Journal of Mathematics, 79:497-516, 1957.

295
R. O. Duda, P. E. Hart, and D. G. Stork.
Pattern Classification, 2nd Ed.
Wiley, New York, 2000.

296
G. Dudek and M. Jenkin.
Computational Principles of Mobile Robotics.
Cambridge University Press, Cambridge, U.K., 2000.

297
G. Dudek, M. Jenkin, E. Milios, and D. Wilkes.
Map validation and self-location in a graph-like world.
In Proceedings AAAI National Conference on Artificial Intelligence, pages 1648-1653, 1993.

298
G. Dudek, K. Romanik, and S. Whitesides.
Global localization: Localizing a robot with minimal travel.
SIAM Journal on Computing, 27(2):583-604, April 1998.

299
I. Duleba.
Algorithms of Motion Planning for Nonholonomic Robots.
Technical University of Wroclaw, Wroclaw, Poland, 1998.

300
G. E. Dullerud and R. D'Andrea.
Distributed control of heterogeneous systems.
IEEE Transactions on Automatic Control, 49(12):2113-2128, 2004.

301
G. E. Dullerud and F. Paganini.
A Course in Robust Control Theory.
Springer-Verlag, Berlin, 2000.

302
H. Edelsbrunner.
Algorithms in Combinatorial Geometry.
Springer-Verlag, Berlin, 1987.

303
C. Edwards and S. K. Spurgeon.
Sliding Mode Control: Theory and Applications.
CRC Press, Ann Arbor, MI, 1998.

304
A. Efrat, L. J. Guibas, S. Har-Peled, D. C. Lin, J. S. B. Mitchell, and T. M. Murali.
Sweeping simple polygons with a chain of guards.
In Proceedings ACM-SIAM Symposium on Discrete Algorithms, 2000.

305
M. Egerstedt and X. Hu.
Formation constrained multi-agent control.
IEEE Transactions on Robotics & Automation, 17(6):947-951, December 2001.

306
S. Ehmann and M. C. Lin.
Accurate and fast proximity queries between polyhedra using convex surface decomposition.
In Proceedings Eurographics, 2001.

307
A. Elfes.
Using occupancy grids for mobile robot perception and navigation.
IEEE Computer, 22(6):46-57, June 1989.

308
G. Ellis.
Observers in Control Systems.
Elsevier, New York, 2002.

309
I. Z. Emiris and B. Mourrain.
Computer algebra methods for studying and computing molecular conformations.
Technical report, INRIA, Sophia-Antipolis, France, 1997.

310
A. G. Erdman, G. N. Sandor, and S. Kota.
Mechanism Design: Analysis and Synthesis, 4th Ed., Vol. 1.
Prentice Hall, Englewood Cliffs, NJ, 2001.

311
M. A. Erdmann.
On motion planning with uncertainty.
Master's thesis, Massachusetts Institute of Technology, Cambridge, MA, August 1984.

312
M. A. Erdmann.
Using backprojections for fine motion planning with uncertainty.
International Journal of Robotics Research, 5(1):19-45, 1986.

313
M. A. Erdmann.
On Probabilistic Strategies for Robot Tasks.
PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1989.

314
M. A. Erdmann.
Randomization in robot tasks.
International Journal of Robotics Research, 11(5):399-436, October 1992.

315
M. A. Erdmann.
Randomization for robot tasks: Using dynamic programming in the space of knowledge states.
Algorithmica, 10:248-291, 1993.

316
M. A. Erdmann.
On a representation of friction in configuration space.
International Journal of Robotics Research, 13(3):240-271, 1994.

317
M. A. Erdmann.
Understanding action and sensing by designing action-based sensors.
International Journal of Robotics Research, 14(5):483-509, 1995.

318
M. A. Erdmann.
An exploration of nonprehensile two-palm manipulation using two zebra robots.
In J.-P. Laumond and M. Overmars, editors, Algorithms for Robotic Motion and Manipulation, pages 239-254. A.K. Peters, Wellesley, MA, 1997.

319
M. A. Erdmann and T. Lozano-Pérez.
On multiple moving objects.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1419-1424, 1986.

320
M. A. Erdmann and T. Lozano-Pérez.
On multiple moving objects.
Algorithmica, 2:477-521, 1987.

321
M. A. Erdmann and M. T. Mason.
An exploration of sensorless manipulation.
IEEE Transactions on Robotics & Automation, 4(4):369-379, August 1988.

322
M. A. Erdmann, M. T. Mason, and G. Vanecek.
Mechanical parts orienting: The case of a polyhedron on a table.
Algorithmica, 10:206-247, 1993.

323
B. Espiau, F. Chaumette, and P. Rives.
A new approach to visual servoing in robotics.
IEEE Transactions on Robotics & Automation, 8(3):313-326, June 1992.

324
J. Esposito, J. W. Kim, and V. Kumar.
Adaptive RRTs for validating hybrid robotic control systems.
In Proceedings Workshop on Algorithmic Foundations of Robotics, Zeist, The Netherlands, July 2004.

325
M. Farber.
Topological complexity of motion planning.
Discrete and Computational Geometry, 29:211-221, 2003.

326
M. Farber, S. Tabachnkov, and S. Yuzvinsky.
Topological robotics: Motion planning in projective spaces.
International Mathematical Research Notices, 34:1853-1870, 2003.

327
M. Farber and S. Yuzvinsky.
Topological robotics: Subspace arrangements and collision free motion planning.
Technical Report math.AT/0210115, arXiv (on-line), 2004.

328
B. Faverjon.
Obstacle avoidance using an octree in the configuration space of a manipulator.
In Proceedings IEEE International Conference on Robotics & Automation, pages 504-512, 1984.

329
B. Faverjon.
Hierarchical object models for efficient anti-collision algorithms.
In Proceedings IEEE International Conference on Robotics & Automation, pages 333-340, 1989.

330
B. Faverjon and P. Tournassoud.
A local based method for path planning of manipulators with a high number of degrees of freedom.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1152-1159, 1987.

331
R. Featherstone.
Robot Dynamics Algorithms.
Kluwer, Boston, MA, 1987.

332
S. P. Fekete, R. Klein, and A. Nüchter.
Online searching with an autonomous robot.
In Proceedings Workshop on Algorithmic Foundations of Robotics, Zeist, The Netherlands, July 2004.

333
P. Ferbach.
A method of progressive constraints for nonholonomic motion planning.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2949-2955, 1996.

334
C. Fernandes, L. Gurvits, and Z. X. Li.
A variational approach to optimal nonholonomic motion planning.
In Proceedings IEEE International Conference on Robotics & Automation, pages 680-685, 1991.

335
C. Fernandes, L. Gurvits, and Z. X. Li.
Near-optimal nonholonomic motion planning for a system of coupled rigid bodies.
IEEE Transactions on Automatic Control, 30(3):450-463, March 1994.

336
R. Fierro, A. Das, V. Kumar, and J. P. Ostrowski.
Hybrid control of formations of robots.
In Proceedings IEEE International Conference on Robotics & Automation, pages 157-162, 2001.

337
R. E. Fikes and N. J. Nilsson.
STRIPS: A new approach to the application of theorem proving.
Artificial Intelligence Journal, 2:189-208, 1971.

338
A. F. Filippov.
Differential equations with discontinuous right-hand sides.
American Mathematical Society Translations, Ser. 2, 64:199-231, 1964.

339
P. W. Finn, D. Halperin, L. E. Kavraki, J.-C. Latombe, R. Motwani, C. Shelton, and S. Venkatasubramanian.
Geometric manipulation of flexible ligands.
In M. C. Lin and D. Manocha, editors, Applied Computational Geometry, pages 67-78. Springer-Verlag, Berlin, 1996.
Lecture Notes in Computer Science, 1148.

340
R. J. Firby.
An investigation into reactive planning in complex domains.
In Proceedings AAAI National Conference on Artificial Intelligence, 1987.

341
G. F. Fishman.
Monte Carlo: Concepts, Algorithms, and Applications.
Springer-Verlag, Berlin, 1996.

342
R. Fleischer, K. Romanik, S. Schuierer, and G. Trippen.
Optimal localization in trees.
Information and Computation, 171(2):224-247, 2002.

343
S. Fleury, P. Souères, J.-P. Laumond, and R. Chatila.
Primitives for smoothing mobile robot trajectories.
IEEE Transactions on Robotics & Automation, 11(3):441-448, 1995.

344
M. Fliess, J. Lévine, P. Martin, and P. Rouchon.
Flatness and defect of non-linear systems: Introductory theory and examples.
International Journal of Control, 61(6):1327-1361, 1995.

345
H. Flordal, M. Fabian, and K. Akesson.
Automatic implementation and verification of coordinating PLC-code for robotcells.
In Proceedings IFAC Symposium of Information Control Problems in Manufacturing, 2004.

346
G. B. Folland.
Real Analysis: Modern Techniques and Their Applications.
Wiley, New York, 1984.

347
S. Fortune and G. Wilfong.
Planning constrained motion.
In Proceedings ACM Symposium on Theory of Computing, pages 445-459, 1988.

348
M. Foskey, M. Garber, M. Lin, and D. Manocha.
A Voronoi-based hybrid motion planner.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2001.

349
A. Fox and S. Hutchinson.
Exploiting visual constraints in the synthesis of uncertainty-tolerant motion plans.
IEEE Transactions on Robotics & Automation, 1(11):56-71, February 1995.

350
D. Fox, S. Thrun, W. Burgard, and F. Dallaert.
Particle filters for mobile robot localization.
In A. Doucet, N. de Freitas, and N. Gordon, editors, Sequential Monte Carlo Methods in Practice, pages 401-428. Springer-Verlag, Berlin, 2001.

351
D. Hähnel D. Fox, W. Burgard, and S. Thrun.
A highly efficient FastSLAM algorithm for generating cyclic maps of large-scale environments from raw laser range measurements.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.

352
J. Fraden.
Handbook of Modern Sensors: Physics, Designs, and Applications.
Springer-Verlag, Berlin, 2003.

353
T. Fraichard.
Dynamic trajectory planning with dynamic constraints: A 'state-time space' approach.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1393-1400, 1993.

354
T. Fraichard and J.-M. Ahuactzin.
Smooth path planning for cars.
In Proceedings IEEE International Conference on Robotics & Automation, pages 3722-3727, 2001.

355
T. Fraichard and H. Asama.
Inevitable collision states - a step towards safer robots?
Advanced Robotics, pages 1001-1024, 2004.

356
T. Fraichard and C. Laugier.
Kinodynamic planning in a structured and time-varying 2D workspace.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2: 1500-1505, 1992.

357
T. Fraichard and A. Scheuer.
Car-like robots and moving obstacles.
In Proceedings IEEE International Conference on Robotics & Automation, pages 64-69, 1994.

358
T. Fraichard and A. Scheuer.
From Reeds and Shepp's to continuous-curvature paths.
IEEE Transactions on Robotics, 20(6):1025-1035, December 2004.

359
T. Frankel.
The Geometry of Physics.
Cambridge University Press, Cambridge, U.K., 2004.

360
E. Frazzoli.
Robust Hybrid Control of Autonomous Vehicle Motion Planning.
PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, June 2001.

361
E. Frazzoli and F. Bullo.
Decentralized algorithms for vehicle routing in a stochastic time-varying environment.
In Proceedings IEEE Conference Decision & Control, pages 3357-3363, 2004.

362
E. Frazzoli, M. A. Dahleh, and E. Feron.
Real-time motion planning for agile autonomous vehicles.
AIAA Journal of Guidance and Control, 25(1):116-129, 2002.

363
E. Frazzoli, M. A. Dahleh, and E. Feron.
Maneuver-based motion planning for nonlinear systems with symmetries.
IEEE Transactions on Robotics, 21(6):1077-1091, December 2005.

364
E. Freund and H. Hoyer.
Path finding in multi robot systems including obstacle avoidance.
International Journal of Robotics Research, 7(1):42-70, February 1988.

365
J. H. Friedman, J. L. Bentley, and R.A. Finkel.
An algorithm for finding best matches in logarithmic expected time.
ACM Transactions on Mathematical Software, 3(3):209-226, September 1977.

366
K. S. Fu, R. C. Gonzalez, and C. S. G. Lee.
Robotics: Control, Sensing, Vision, and Intelligence.
McGraw-Hill, New York, 1987.

367
K. Fujimura and H. Samet.
A hierarchical strategy for path planning among moving obstacles.
Technical Report CAR-TR-237, Center for Automation Research, University of Maryland, November 1986.

368
K. Fujimura and H. Samet.
Planning a time-minimal motion among moving obstacles.
Algorithmica, 10:41-63, 1993.

369
T. Fukuda, S. Ito, N. Oota, F. Arai, Y. Abe, K. Tanake, and Y. Tanaka.
Navigation system based on ceiling landmark recognition for autonomous mobile robot.
In Proceedings International Conference on Industrial Electronics, Control, and Instrumentation, pages 1466-1471, 1993.

370
A. T. Fuller.
Relay control systems optimized for various performance criteria.
In Automatic and Remote Control (Proceedings First World Congress IFAC, Moscow, 1960), pages 510-519. Butterworths, London, 1961.

371
J. Funge.
Artificial Intelligence for Computer Games.
A. K. Peters, Wellesley, MA, 2004.

372
Y. Gabriely and E. Rimon.
Spanning-tree based coverage of continuous areas by a mobile robot.
Technical report, Dept. of Mechanical Engineering, Technion, Israel Institute of Technology, December 1999.

373
Y. Gabriely and E. Rimon.
Spanning-tree based coverage of continuous areas by a mobile robot.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1927-1933, 2001.

374
Y. Gabriely and E. Rimon.
Competitive on-line coverage of grid environments by a mobile robot.
Computational Geometry: Theory and Applications, 24(3):197-224, April 2003.

375
Y. Gabriely and E. Rimon.
Competitive complexity of mobile robot on line motion planning problems.
In Proceedings Workshop on Algorithmic Foundations of Robotics, pages 249-264, 2004.

376
J. Gallier.
Curves and Surfaces in Geometric Modeling.
Morgan Kaufmann, San Francisco, CA, 2000.

377
D. Geman and S. Geman.
Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images.
IEEE Transactions Pattern Analysis Machine Intelligence, 6(6):721-741, November 1984.

378
M. R. Genesereth and N. Nilsson.
Logical Foundations of Artificial Intelligence.
Morgan Kaufmann, San Francisco, CA, 1987.

379
R. Geraerts and M. Overmars.
Sampling techniques for probabilistic roadmap planners.
In Proceedings International Conference on Intelligent Autonomous Systems, 2004.

380
R. Geraerts and M. H. Overmars.
A comparative study of probabilistic roadmap planners.
In Proceedings Workshop on Algorithmic Foundations of Robotics, December 2002.

381
B. Gerkey, S. Thrun, and G. Gordon.
Clear the building: Pursuit-evasion with teams of robots.
In Proceedings AAAI National Conference on Artificial Intelligence, 2004.

382
M. Ghallab, D. Nau, and P. Traverso.
Automated Planning: Theory and Practice.
Morgan Kaufman, San Francisco, CA, 2004.

383
A. K. Ghose, M. E. Logan, A. M. Treasurywala, H. Wang, R. C. Wahl, B. E. Tomczuk, M. R. Gowravaram, E. P. Jaeger, and J. J. Wendoloski.
Determination of pharmacophoric geometry for collagenase inhibitors using a novel computational method and its verification using molecular dynamics, NMR, and X-ray crystallography.
Journal of the American Chemical Society, 117:4671-4682, 1995.

384
S. K. Ghosh and D. M. Mount.
An output sensitive algorithm for computing visibility graphs.
SIAM Journal on Computing, 20:888-910, 1991.

385
R. Ghrist.
Shape complexes for metamorphic robot systems.
In Proceedings Workshop on Algorithmic Foundations of Robotics, December 2002.

386
R. Ghrist, J. M. O'Kane, and S. M. LaValle.
Computing Pareto Optimal Coordinations on Roadmaps.
The International Journal of Robotics Research, 24(11):997-1010, 2005.

387
E. G. Gilbert and D. W. Johnson.
Distance functions and their application to robot path planning in the presence of obstacles.
IEEE Transactions on Robotics & Automation, 1(1):21-30, March 1985.

388
E. G. Gilbert, D. W. Johnson, and S. S. Keerth.
A fast procedure for computing the distance between complex objects in three-dimensional space.
IEEE Journal of Robotics & Automation, RA-4(2):193-203, Apr 1988.

389
T. N. Gillespie.
Fundamentals of Vehicle Dynamics.
Society of Automotive Engineers, Warrendale, PA, 1992.

390
B. Glavina.
Solving findpath by combination of goal-directed and randomized search.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1718-1723, May 1990.

391
B. Glavina.
Planning collision free motions for manipulators through a combination of goal oriented search and the creation of intermediate random subgoals.
PhD thesis, Technical University of Munich, 1991.
In German.

392
P. J. Gmytrasiewicz, E. H. Durfee, and D. K. Wehe.
A decision-theoretic approach to coordinating multi-agent interactions.
In Proceedings International Joint Conference on Artificial Intelligence, pages 62-68, 1991.

393
J. Go, T. Vu, and J. J. Kuffner.
Autonomous behaviors for interactive vehicle animations.
In Proceedings SIGGRAPH Symposium on Computer Animation, 2004.

394
K. Y. Goldberg.
Stochastic Plans for Robotic Manipulation.
PhD thesis, Carnegie Mellon University, Pittsburgh, PA, August 1990.

395
K. Y. Goldberg.
Orienting polygonal parts without sensors.
Algorithmica, 10:201-225, 1993.

396
K. Y. Goldberg and M. T. Mason.
Bayesian grasping.
In Proceedings IEEE International Conference on Robotics & Automation, 1990.

397
H. Goldstein.
Classical Mechanics.
Addison-Wesley, Reading, MA, 1980.

398
M. Goldwasser and R. Motwani.
Intractability of assembly sequencing: Unit disks in the plane.
In F. Dehne, A. Rau-Chaplin, J.-R. Sack, and R. Tamassia, editors, WADS '97 Algorithms and Data Structures, pages 307-320. Springer-Verlag, Berlin, 1997.
Lecture Notes in Computer Science, 1272.

399
G. H. Golub and C. F. Van Loan.
Matrix Computations (3rd ed).
Johns Hopkins University Press, Baltimore, MD, 1996.

400
R. Gonzalez and E. Rofman.
On deterministic control problems: An approximation procedure for the optimal cost, parts I, II.
SIAM Journal on Control & Optimization, 23:242-285, 1985.

401
H. H. González-Baños, L. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, R. Motwani, and C. Tomasi.
Motion planning with visibility constraints: Building autonomous observers.
In Y. Shirai and S. Hirose, editors, Proceedings Eighth International Symposium on Robotics Research, pages 95-101. Springer-Verlag, Berlin, 1998.

402
H. H. González-Baños, C.-Y. Lee, and J.-C. Latombe.
Real-time combinatorial tracking of a target moving unpredictably among obstacles.
In Proceedings IEEE International Conference on Robotics & Automation, 2002.

403
J. E. Goodman and J. O'Rourke (eds).
Handbook of Discrete and Computational Geometry, 2nd Ed.
Chapman and Hall/CRC Press, New York, 2004.

404
M. T. Goodrich and R. Tammasia.
Algorithm Design: Foundations, Analysis, and Internet Examples.
Wiley, New York, 2002.

405
B. R. Gossick.
Hamilton's Principle and Physical Systems.
Academic, New York, 1967.

406
S. Gottschalk, M. C. Lin, and D. Manocha.
Obbtree: A hierarchical structure for rapid interference detection.
In Proceedings ACM SIGGRAPH, 1996.

407
V. E. Gough and S. G. Whitehall.
Universal tyre test machine.
In Proceedings 9th International Technical Congress F.I.S.I.T.A., May 1962.

408
E. J. Griffith and S. Akella.
Coordinating multiple droplets in planar array digital microfluidic systems.
International Journal of Robotics Research, 24(11):933-949, 2005.

409
R. Grossman, A. Nerode, A. Ravn, and H. Rischel (eds).
Hybrid Systems.
Springer-Verlag, Berlin, 1993.

410
L. Grüne.
An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation.
Numerische Mathematik, 75:319-337, 1997.

411
L. Guibas and R. Seidel.
Computing convolution by reciprocal search.
In Proceedings ACM Symposium on Computational Geometry, pages 90-99, 1986.

412
L. Guibas and J. Stolfi.
Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.
ACM Transactions on Graphics, 4(2):74-123, 1985.

413
L. J. Guibas, D. Hsu, and L. Zhang.
H-Walk: Hierarchical distance computation for moving convex bodies.
In Proceedings ACM Symposium on Computational Geometry, pages 265-273, 1999.

414
L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani.
Visibility-based pursuit-evasion in a polygonal environment.
International Journal of Computational Geometry and Applications, 9(5):471-494, 1999.

415
L. J. Guibas, R. Motwani, and P. Raghavan.
The robot localization problem.
In K. Goldberg, D. Halperin, J.-C. Latombe, and R. Wilson, editors, Algorithmic Foundations of Robotics, pages 269-282. A.K. Peters, Wellesley, MA, 1995.

416
L. Guilamo, B. Tovar, and S. M. LaValle.
Pursuit-evasion in an unknown environment using gap navigation trees.
In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2004.

417
K. Gupta and Z. Guo.
Motion planning with many degrees of freedom: Sequential search with backtracking.
IEEE Transactions on Robotics & Automation, 6(11):897-906, 1995.

418
K. Gupta and X. Zhu.
Practical motion planning for many degrees of freedom: A novel approach within sequential framework.
Journal of Robotic Systems, 2(12):105-118, 1995.

419
S. K. Gupta, D. A. Bourne, K. Kim, and S. S. Krishnan.
Automated process planning for robotic sheet metal bending operations.
Journal of Manufacturing Systems, 17(5):338-360, 1998.

420
L. Gurvits.
Averaging approach to nonholonomic motion planning.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2541-2546, 1992.

421
J.-S. Gutmann, T. Weigel, and B. Nebel.
A fast, accurate, and robust method for self-localization in polygonal environments using laser-range-finders.
Advanced Robotics, 14(8):651-668, 2001.

422
O. Hájek.
Pursuit Games.
Academic, New York, 1975.

423
K. Haji-Ghassemi.
On differential games of fixed duration with phase coordinate restrictions on one player.
SIAM Journal on Control & Optimization, 28(3):624-652, May 1990.

424
H. Halkin.
Mathematical foundation of system optimization.
In G. Leitman, editor, Topics in Optimization. Academic, New York, 1967.

425
P. R. Halmos.
Measure Theory.
Springer-Verlag, Berlin, 1974.

426
D. Halperin.
Arrangements.
In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, 2nd Ed., pages 529-562. Chapman and Hall/CRC Press, New York, 2004.

427
D. Halperin, J.-C. Latombe, and R. H. Wilson.
A general framework for assembly planning: the motion space approach.
In Proceedings ACM Symposium on Computational Geometry, pages 9-18, 1998.

428
D. Halperin and M. Sharir.
A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment.
Discrete and Computational Geometry, 16:121-134, 1996.

429
D. Halperin and R. Wilson.
Assembly partitioning along simple paths: the case of multiple translations.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1585-1592, 1995.

430
J. H. Halton.
On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals.
Numerische Mathematik, 2:84-90, 1960.

431
J. M. Hammersley.
Monte-Carlo methods for solving multivariable problems.
Annals of the New York Academy of Science, 86:844-874, 1960.

432
L. Han and N. M. Amato.
A kinematics-based probabilistic roadmap method for closed chain systems.
In B. R. Donald, K. M. Lynch, and D. Rus, editors, Algorithmic and Computational Robotics: New Directions, pages 233-246. A.K. Peters, Wellesley, MA, 2001.

433
H. Harrison and T. Nettleton.
Advanced Engineering Dynamics.
Elsevier, New York, 1997.

434
R. S. Hartenberg and J. Denavit.
A kinematic notation for lower pair mechanisms based on matrices.
Journal of Applied Mechanics, 77:215-221, 1955.

435
R. S. Hartenberg and J. Denavit.
Kinematic Synthesis of Linkages.
McGraw-Hill, New York, 1964.

436
J. W. Hartmann.
Counter-Intuitive Behavior in Locally Optimal Solar Sail Escape Trajectories.
PhD thesis, University of Illinois, Urbana, IL, May 2005.

437
J. W. Hartmann, V. L. Coverstone, and J. E. Prussing.
Optimal counter-intuitive solar sail escape trajectories.
In Proceedings AIAA/AAS Space Flight Mechanics Conference, 2004.
Paper AAS 04-279.

438
R. Hartshorne.
Algebraic Geometry.
Springer-Verlag, Berlin, 1977.

439
A. Hatcher.
Algebraic Topology.
Cambridge University Press, Cambridge, U.K., 2002.
Available at http://www.math.cornell.edu/$ \sim$hatcher/AT/ATpage.html.

440
M. T. Heath.
Scientific Computing: An Introductory Survey, 2nd Ed.
McGraw-Hill, New York, 2002.

441
G. Heinzinger, P. Jacobs, J. Canny, and B. Paden.
Time-optimal trajectories for a robotic manipulator: A provably good approximation algorithm.
In Proceedings IEEE International Conference on Robotics & Automation, pages 150-155, Cincinnati, OH, 1990.

442
H. Hermes, A. Lundell, and D. Sullivan.
Nilpotent bases for distributions and control systems.
Journal of Differential Equations, 55(3):385-400, 1984.

443
J. Hershberger and S. Suri.
Efficient computation of Euclidean shortest paths in the plane.
In Proceedings IEEE Symposium on Foundations of Computer Science, pages 508-517, 1995.

444
S. Hert, S. Tiwari, and V. Lumelsky.
A terrain-covering algorithm for an AUV.
Autonomous Robots, 3:91-119, 1996.

445
F. J. Hickernell.
Lattice rules: How well do they measure up?
In P. Bickel, editor, Random and Quasi-Random Point Sets, pages 109-166. Springer-Verlag, Berlin, 1998.

446
F. J. Hickernell, H. S. Hong, P. L'Ecuyer, and C. Lemieux.
Extensible lattice sequences for quasi-monte carlo quadrature.
SIAM Journal on Scientific Computing, 22:1117-1138, 2000.

447
R. Hinkel and T. Knieriemen.
Environment perception with a laser radar in a fast moving robot.
In Proceedings Symposium on Robot Control, pages 68.1-68.7, Karlsruhe, Germany, 1988.

448
Y. Hirano, K. Kitahama, and S. Yoshizawa.
Image-based object recognition and dextrous hand/arm motion planning using RRTs for grasping in cluttered scene.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005.

449
M. W. Hirsch.
Differential Topology.
Springer-Verlag, Berlin, 1994.

450
Y.-C. Ho and K.-C. Chu.
Team decision theory and information structures in optimal control problems-Part I.
In IEEE Transactions on Automatic Control, pages 15-22, 1972.

451
J. G. Hocking and G. S. Young.
Topology.
Dover, New York, 1988.

452
J. K. Hodgins and W. L. Wooten.
Animating human athletes.
In Y. Shirai and S. Hirose, editors, Proceedings International Symposium on Robotics Research, pages 356-367. Springer-Verlag, Berlin, 1998.

453
R. L. Hoffman.
Automated assembly in a CSG domain.
In Proceedings IEEE International Conference on Robotics & Automation, pages 210-215, 1989.

454
C. M. Hoffmann.
Geometric and Solid Modeling.
Morgan Kaufmann, San Francisco, CA, 1989.

455
C. Holleman and L. E. Kavraki.
A framework for using the workspace medial axis in PRM planners.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1408-1413, 2000.

456
J. Hollerbach.
Dynamic scaling of manipulator trajectories.
Technical report, MIT A.I. Lab Memo 700, 1983.

457
J. Hollerbach.
Dynamic scaling of manipulator trajectories.
In Proceedings American Control Conference, pages 752-756, 1983.

458
L. S. Homem de Mello and A. C. Sanderson.
Representations of mechanical assembly sequences.
IEEE Transactions on Robotics & Automation, 7(2):211-227, 1991.

459
H. H. Hoos and T. Stützle.
Stochastic Local Search: Foundations and Applications.
Morgan Kaufmann, San Francisco, 2004.

460
J. Hopcroft, D. Joseph, and S. Whitesides.
Movement problems for 2-dimensional linkages.
In J .T .Schwartz, M. Sharir, and J. Hopcroft, editors, Planning, Geometry, and Complexity of Robot Motion, pages 282-329. Ablex, Norwood, NJ, 1987.

461
J. E. Hopcroft, J. T. Schwartz, and M. Sharir.
On the complexity of motion planning for multiple independent objects: PSPACE-hardness of the ``warehouseman's problem''.
International Journal of Robotics Research, 3(4):76-88, 1984.

462
J. E. Hopcroft, J. D. Ullman, and R. Motwani.
Introduction to Automata Theory, Languages, and Computation.
Addison-Wesley, Reading, MA, 2000.

463
T. Horsch, F. Schwarz, and H. Tolle.
Motion planning for many degrees of freedom: Random reflections at C-space obstacles.
In Proceedings IEEE International Conference on Robotics & Automation, pages 3318-3323, San Diego, CA, April 1994.

464
A. E. Howe and E. Dahlman.
A critical assessment of benchmark comparison in planning.
Journal of Artificial Intelligence Research, pages 1-33, 2002.

465
D. Hsu, T. Jiang, J. Reif, and Z. Sun.
The bridge test for sampling narrow passages with probabilistic roadmap planners.
In Proceedings IEEE International Conference on Robotics & Automation, 2003.

466
D. Hsu, R. Kindel, J-C. Latombe, and S. Rock.
Randomized kinodynamic motion planning with moving obstacles.
In B. R. Donald, K. M. Lynch, and D. Rus, editors, Algorithmic and Computational Robotics: New Directions. A.K. Peters, Wellesley, MA, 2001.

467
D. Hsu, J.-C. Latombe, and R. Motwani.
Path planning in expansive configuration spaces.
International Journal Computational Geometry & Applications, 4:495-512, 1999.

468
W. Huang.
Optimal line-sweep-based decompositions for coverage algorithms.
In Proceedings IEEE International Conference on Robotics & Automation, pages 27-32, 2001.

469
T. W. Hungerford.
Algebra.
Springer-Verlag, Berlin, 1984.

470
S. A. Hutchinson, G. D. Hager, and P. I. Corke.
A tutorial on visual servo control.
IEEE Transactions on Robotics & Automation, 12(5):651-670, October 1996.

471
M. Hutter.
Universal Artificial Intelligence.
Springer-Verlag, Berlin, 2005.

472
Y. K. Hwang and N. Ahuja.
Gross motion planning-A survey.
ACM Computing Surveys, 24(3):219-291, September 1992.

473
S. Iannitti and K. M. Lynch.
Exact minimum control switch motion planning for the snakeboard.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.

474
C. Icking, G. Rote, E. Welzl, and C.-K. Yap.
Shortest paths for line segments.
Algorithmica, 10:182-200, 1992.

475
P. Indyk.
Nearest neighbors in high-dimensional spaces.
In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, 2nd Ed., pages 877-892. Chapman and Hall/CRC Press, New York, 2004.

476
P. Indyk and R. Motwani.
Approximate nearest neighbors: Towards removing the curse of dimensionality.
In Proceedings ACM Symposium on Theory of Computing, pages 604-613, 1998.

477
R. Isaacs.
Differential Games.
Wiley, New York, 1965.

478
A. Isidori.
Nonlinear Control Systems, 2nd Ed.
Springer-Verlag, Berlin, 1989.

479
P. Isto.
Constructing probabilistic roadmaps with powerful local planning and path optimization.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2323-2328, 2002.

480
G. Jacob.
Lyndon discretization and exact motion planning.
In Proceedings European Control Conference, 1991.

481
H. Jacob, S. Feder, and J. Slotine.
Real-time path planning using harmonic potential functions in dynamic environment.
In Proceedings IEEE International Conference on Robotics & Automation, pages 874-881, 1997.

482
P. Jacobs and J. Canny.
Planning smooth paths for mobile robots.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2-7, 1989.

483
P. Jensfelt.
Approaches to Mobile Robot Localization.
PhD thesis, Royal Institute of Technology (KTH), Stockholm, Sweden, 2001.

484
P. Jensfelt and H. I. Christensen.
Pose tracking using laser scanning and minimalistic environmental models.
IEEE Transactions on Robotics & Automation, 17(2):138-147, 2001.

485
P. Jensfelt and S. Kristensen.
Active global localisation for a mobile robot using multiple hypothesis tracking.
IEEE Transactions on Robotics & Automation, 17(5):748-760, October 2001.

486
X. Ji and J. Xiao.
Planning motion compliant to complex contact states.
International Journal of Robotics Research, 20(6):446-465, 2001.

487
Y.-B. Jia.
Computation on parametric curves with an application in grasping.
International Journal of Robotics Research, 23(7-8):825-855, 2004.

488
P. Jiménez, F. Thomas, and C. Torras.
Collision detection algorithms for motion planning.
In J.-P. Laumond, editor, Robot Motion Planning and Control, pages 1-53. Springer-Verlag, Berlin, 1998.

489
D. Jordan and M. Steiner.
Configuration spaces of mechanical linkages.
Discrete and Computational Geometry, 22:297-315, 1999.

490
D. A. Joseph and W. H. Plantiga.
On the complexity of reachability and motion planning questions.
In Proceedings ACM Symposium on Computational Geometry, pages 62-66, 1985.

491
V. Jurdjevic.
The geometry of the plate-ball problem.
Archives for Rational Mechanics and Analysis, 124:305-328, 1993.

492
V. Jurdjevic.
Geometric Control Theory.
Cambridge University Press, Cambridge, U.K., 1997.

493
L. P. Kaelbling, A. Cassandra, and J. Kurien.
Acting under uncertainty: Discrete Bayesian models for mobile robot navigation.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 963-972, 1996.

494
L. P. Kaelbling, M. L. Littman, and A. R. Cassandra.
Planning and acting in partially observable stochastic domains.
Artificial Intelligence Journal, 101, 1998.

495
S. Kagami, J. Kuffner, K. Nishiwaki, and K. Okada M. Inaba.
Humanoid arm motion planning using stereo vision and RRT search.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.

496
D. W. Kahn.
Topology: An Introduction to the Point-Set and Algebraic Areas.
Dover, New York, 1995.

497
H. Kaindl and G. Kainz.
Bidirectional heuristic search reconsidered.
Journal of Artificial Intelligence Research, pages 283-317, December 1997.

498
M. Kallmann, A. Aubel, T. Abaci, and D. Thalmann.
Planning collision-free reaching motions for interactive object manipulation and grasping.
Eurographics, 22(3), 2003.

499
M. Kallmann and M. Mataric.
Motion planning using dynamic roadmaps.
In Proceedings IEEE International Conference on Robotics & Automation, 2004.

500
R. Kalman.
A new approach to linear filtering and prediction problems.
Transactions of the ASME, Journal of Basic Engineering, 82:35-45, 1960.

501
R. E. Kalman, Y.-C. Ho, and K. S. Narendra.
Controllability of dynamical systems.
Contributions to Differential Equations, 1:189-213, 1963.

502
M. H. Kalos and P. A. Whitlock.
Monte Carlo Methods.
Wiley, New York, 1986.

503
T. Kameda, M. Yamashita, and I. Suzuki.
On-line polygon search by a seven-state boundary 1-searcher.
IEEE Transactions on Robotics, 2006.
To appear.

504
I. Kamon and E. Rivlin.
Sensory-based motion planning with global proofs.
IEEE Transactions on Robotics & Automation, 13(6):814-822, December 1997.

505
I. Kamon, E. Rivlin, and E. Rimon.
Range-sensor based navigation in three dimensions.
In Proceedings IEEE International Conference on Robotics & Automation, 1999.

506
K. Kant and S. W. Zucker.
Toward efficient trajectory planning: The path-velocity decomposition.
International Journal of Robotics Research, 5(3):72-89, 1986.

507
M.-Y. Kao, J. H. Reif, and S. R. Tate.
Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem.
In SODA: ACM-SIAM Symposium on Discrete Algorithms, pages 441-447, 1993.

508
W. Kaplan.
Advanced Calculus.
Addison-Wesley, Reading, MA, 1984.

509
T. Karatas and F. Bullo.
Randomized searches and nonlinear programming in trajectory planning.
In IEEE Conference on Decision and Control, 2001.

510
R. M. Karp.
On-line algorithms versus off-line algorithms: How much is it worth to know the future?
In Proceedings World Computer Congress, 1992.

511
L. Kauffman.
Knots and Applications.
World Scientific, River Edge, NJ, 1995.

512
H. Kautz, D. McAllester, and B. Selman.
Encoding plans in propositional logic.
In Proceedings International Conference on Knowledge Representation and Reasoning, 1996.

513
L. E. Kavraki.
Computation of configuration-space obstacles using the Fast Fourier Transform.
IEEE Transactions on Robotics & Automation, 11(3):408-413, 1995.

514
L. E. Kavraki.
Geometry and the discovery of new ligands.
In J.-P. Laumond and M. H. Overmars, editors, Algorithms for Robotic Motion and Manipulation, pages 435-445. A.K. Peters, Wellesley, MA, 1997.

515
L. E. Kavraki and M. Kolountzakis.
Partitioning a planar assembly into two connected parts is NP-complete.
Information Processing Letters, 55(3):159-165, 1995.

516
L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars.
Probabilistic roadmaps for path planning in high-dimensional configuration spaces.
IEEE Transactions on Robotics & Automation, 12(4):566-580, June 1996.

517
Y. Ke and J. O'Rourke.
Lower bounds on moving a ladder in two and three dimensions.
Discrete and Computational Geometry, 3:197-217, 1988.

518
K. Kedem, R. Livne, J. Pach, and M. Sharir.
On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles.
Discrete and Computational Geometry, 1:59-71, 1986.

519
J. M. Keil.
Polygon decomposition.
In J. R. Sack and J. Urrutia, editors, Handbook on Computational Geometry. Elsevier, New York, 2000.

520
A. Kelly and B. Nagy.
Reactive nonholonomic trajectory generation via parametric optimal control.
International Journal of Robotics Research, 22(7-8):583-601, 2003.

521
J. F. Kenney and E. S. Keeping.
Mathematics of Statistics, Part 2, 2nd ed.
Van Nostrand, Princeton, NJ, 1951.

522
L. Kettner.
Designing a data structure for polyhedral surfaces.
In Proceedings ACM Symposium on Computational Geometry, pages 146-154, 1998.

523
H. K. Khalil.
Nonlinear Systems.
Macmillan, New York, 2002.

524
W. Khalil and J. F. Kleinfinger.
A new geometric notation for open and closed-loop robots.
In Proceedings IEEE International Conference on Robotics & Automation, volume 3, pages 1174-1179, 1986.

525
O. Khatib.
Commande dynamique dans l'espace opérational des robots manipulateurs en présence d'obstacles.
PhD thesis, Ecole Nationale de la Statistique et de l'Administration Economique, France, 1980.

526
O. Khatib.
Real-time obstacle avoidance for manipulators and mobile robots.
International Journal of Robotics Research, 5(1):90-98, 1986.

527
A. A. Kilin.
The dynamics of Chaplygin ball: The qualitative and computer analysis.
Regular and Chaotic Dynamics, 6(3):291-306, 2001.

528
J. Kim and J. P. Ostrowski.
Motion planning of aerial robot using rapidly-exploring random trees with dynamic constraints.
In Proceedings IEEE International Conference on Robotics & Automation, 2003.

529
J.-O. Kim and P. Khosla.
Real-time obstacle avoidance using harmonic potential functions.
Technical report, Carnegie Mellon University, Pittsburgh, PA, 1990.

530
K. H. Kim and F. W. Roush.
Team Theory.
Ellis Horwood Limited, Chichester, U.K., 1987.

531
J. T. Kimbrell.
Kinematic Analysis and Synthesis.
McGraw-Hill, New York, 1991.

532
R. Kimmel, N. Kiryati, and A. M. Bruckstein.
Multivalued distance maps for motion planning on surfaces with moving obstacles.
IEEE Transactions on Robotics & Automation, 14(3):427-435, June 1998.

533
R. Kimmel and J. Sethian.
Computing geodesic paths on manifolds.
Proceedings of the National Academy of Sciences, USA, 95(15):8431-8435, 1998.

534
R. Kimmel and J. Sethian.
Optimal algorithm for shape from shading and path planning.
Journal of Mathematical Imaging and Vision, 14(3):234-244, 2001.

535
C. L. Kinsey.
Topology of Surfaces.
Springer-Verlag, Berlin, 1993.

536
G. Kitagawa.
Monte Carlo filter and smoother for non-Gaussian nonlinear state space models.
Journal of Computational and Graphical Statistics, 5(1), 1996.

537
J. M. Kleinberg.
On-line algorithms for robot navigation and server problems.
Technical Report MIT/LCS/TR-641, MIT, Cambridge, MA, May 1994.

538
J. M. Kleinberg.
Two algorithms for nearest-neighbor search in high dimensions.
In Proceedings ACM Symposium on Theory of Computing, pages 599-608, May 1997.

539
S. A. Klugman, H. H. Panjer, and G. E. Willmot.
Loss Models: From Data to Decisions, 2nd Ed.
Wiley, New York, 2004.

540
D. E. Knuth.
The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Ed.
Addison-Wesley, Reading, MA, 1998.

541
D. E. Koditschek.
Exact robot navigation by means of potential functions: Some topological considerations.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1-6, 1987.

542
D. E. Koditschek.
An approach to autonomous robot assembly.
Robotica, 12:137-155, 1994.

543
S. Koenig and M. Likhachev.
$ D^*$ lite.
In Proceedings AAAI National Conference on Artificial Intelligence, pages 476-483, 2002.

544
Y. Koga, K. Kondo, J. Kuffner, and J.-C. Latombe.
Planning motions with intentions.
Proceedings ACM SIGGRAPH, pages 395-408, 1994.

545
D. Koller, N. Megiddo, and B. von Stengel.
Efficient computation of equilibria for extensive two-person games.
Games and Economic Behavior, 14:247-259, 1996.

546
A. N. Kolmogorov and S. V. Fomin.
Introductory Real Analysis.
Dover, New York, 1975.

547
V. Koltun.
Pianos are not flat: Rigid motion planning in three dimensions.
In Proceedings ACM-SIAM Symposium on Discrete Algorithms, 2005.

548
K. Kondo.
Motion planning with six degrees of freedom by multistrategic bidirectional heuristic free-space enumeration.
IEEE Transactions on Robotics & Automation, 7(3):267-277, 1991.

549
K. Konolige.
Markov localization using correlation.
In Proceedings International Joint Conference on Artificial Intelligence, 1999.

550
R. E. Korf.
Search: A survey of recent results.
In H. E. Shrobe, editor, Exploring Artificial Intelligence: Survey Talks from the National Conference on Artificial Intelligence. Moran Kaufmann, San Francisco, CA, 1988.

551
R. E. Korf.
Artificial intelligence search algorithms.
In Algorithms and Theory of Computation Handbook. CRC Press, Boca Raton, FL, 1999.

552
K. Kotay, D. Rus, M. Vora, and C. McGray.
The self-reconfiguring robotic molecule: Design and control algorithms.
In P. K. Agarwal, L. E. Kavraki, and M. T. Mason, editors, Robotics: The Algorithmic Perspective. A.K. Peters, Natick, MA, 1998.

553
L. Kovar and M. Gleicher.
Automated extraction and parameterization of motions in large data sets.
In Proceedings ACM SIGGRAPH, 2004.

554
L. Kovar, M. Gleicher, and F. Pighin.
Motion graphs.
In Proceedings ACM SIGGRAPH, 2002.

555
K. Kozlowski, P. Dutkiewicz, and W. Wróblewski.
Modeling and Control of Robots.
Wydawnictwo Naukowe PWN, Warsaw, Poland, 2003.
In Polish.

556
P. S. Krishnaprasad and D. P. Tsakaris.
Oscillations, SE(2)-snakes and motion control: A study of the roller racer.
Technical report, Center for Dynamics and Control of Smart Structures, University of Maryland, 1998.

557
J. J. Kuffner.
Autonomous Agents for Real-time Animation.
PhD thesis, Stanford University, Stanford, CA, 1999.

558
J. J. Kuffner.
Some Computed Examples [using RRT-Connect].
[Online], 2001.
Available at http://www.kuffner.org/james/plan/examples.html.

559
J. J. Kuffner.
Effective sampling and distance metrics for 3D rigid body path planning.
In Proceedings IEEE International Conference on Robotics & Automation, 2004.

560
J. J. Kuffner and S. M. LaValle.
An efficient approach to path planning using balanced bidirectional RRT search.
Technical Report CMU-RI-TR-05-34, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, August 2005.

561
J. J. Kuffner, K. Nishiwaki, M. Inaba, and H. Inoue.
Motion planning for humanoid robots.
In Proceedings International Symposium on Robotics Research, 2003.

562
H. W. Kuhn.
Extensive games and the problem of information.
In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, pages 196-216. Princeton University Press, Princeton, NJ, 1953.

563
J. B. Kuipers.
Quaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality.
Princeton University Press, Princeton, NJ, 2002.

564
P. R. Kumar and P. Varaiya.
Stochastic Systems.
Prentice-Hall, Englewood Cliffs, NJ, 1986.

565
H. J. Kushner.
Numerical methods for continuous control problems in continuous time.
SIAM Journal on Control & Optimization, 28:999-1048, 1990.

566
H. J. Kushner and D. S. Clark.
Stochastic Approximation Methods for Constrained and Unconstrained Systems.
Springer-Verlag, Berlin, 1978.

567
H. J. Kushner and P. G. Dupuis.
Numerical Methods for Stochastic Control Problems in Continuous Time.
Springer-Verlag, Berlin, 1992.

568
K. N. Kutulakos, C. R. Dyer, and V. J. Lumelsky.
Provable strategies for vision-guided exploration in three dimensions.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1365-1371, 1994.

569
J. B. H. Kwa.
BS*: An admissible bidirectional staged heuristic search algorithm.
Artificial Intelligence Journal, 38:95-109, 1989.

570
H. Kwakernaak and R. Sivan.
Linear Optimal Control Systems.
Wiley, New York, 1972.

571
A. Ladd and L. E. Kavraki.
Motion planning for knot untangling.
In Proceedings Workshop on Algorithmic Foundations of Robotics, Nice, France, December 2002.

572
A. Ladd and L. E. Kavraki.
Fast exploration for robots with dynamics.
In Proceedings Workshop on Algorithmic Foundations of Robotics, Zeist, The Netherlands, July 2004.

573
A. Ladd and L. E. Kavraki.
Measure theoretic analysis of probabilistic path planning.
IEEE Transactions on Robotics & Automation, 20(2):229-242, 2004.

574
G. Laffierriere and H. J. Sussmann.
Motion planning for controllable systems without drift.
In Proceedings IEEE International Conference on Robotics & Automation, 1991.

575
F. Lamiraux, D. Bonnafous, and O. Lefebvre.
Reactive path deformation for non-holonomic mobile robots.
IEEE Transactions on Robotics, 20(6):967-977, December 2004.

576
F. Lamiraux, E. Ferre, and E. Vallee.
Kinodynamic motion planning: Connecting exploration trees using trajectory optimization methods.
In Proceedings IEEE International Conference on Robotics & Automation, pages 3987-3992, 2004.

577
F. Lamiraux and L. Kavraki.
Path planning for elastic plates under manipulation constraints.
In Proceedings IEEE International Conference on Robotics & Automation, pages 151-156, 1999.

578
F. Lamiraux and J.-P. Laumond.
Flatness and small-time controllability of multibody mobile robots: Application to motion planning.
IEEE Transactions on Automatic Control, 45(10):1878-1881, April 2000.

579
F. Lamiraux, S. Sekhavat, and J.-P. Laumond.
Motion planning and control for Hilare pulling a trailer.
IEEE Transactions on Robotics & Automation, 15(4):640-652, August 1999.

580
A. S. Lapaugh.
Recontamination does not help to search a graph.
Journal of the ACM, 40(2):224-245, April 1993.

581
P.-S. Laplace.
Théorie Analityque des Probabilités.
Courceir, Paris, 1812.

582
R. E. Larson.
A survey of dynamic programming computational procedures.
IEEE Transactions on Automatic Control, 12(6):767-774, December 1967.

583
R. E. Larson and J. L. Casti.
Principles of Dynamic Programming, Part II.
Dekker, New York, 1982.

584
R. E. Larson and W. G. Keckler.
Optimum adaptive control in an unknown environment.
IEEE Transactions on Automatic Control, 13(4):438-439, August 1968.

585
J. P. LaSalle.
Stability theory for ordinary differential equations.
Journal of Differential Equations, 4:57-65, 1968.

586
A. Lasota and M. C. Mackey.
Chaos, Fractals, and Noise: Stochastic Aspects of Dynamics, 2nd Ed.
Springer-Verlag, Berlin, 1995.

587
J.-C. Latombe.
A fast path planner for a car-like indoor mobile robot.
In Proceedings AAAI National Conference on Artificial Intelligence, pages 659-665, 1991.

588
J.-C. Latombe.
Robot Motion Planning.
Kluwer, Boston, MA, 1991.

589
J.-C. Latombe.
Motion planning: A journey of robots, molecules, digital actors, and other artifacts.
International Journal of Robotics Research, 18(11):1119-1128, 1999.

590
J.-C. Latombe, A. Lazanas, and S. Shekhar.
Robot motion planning with uncertainty in control and sensing.
Artificial Intelligence Journal, 52:1-47, 1991.

591
M. Lau and J. J. Kuffner.
Behavior planning for character animation.
In Proceedings Eurographics/SIGGRAPH Symposium on Computer Animation, 2005.

592
S. L. Laubach and J. W. Burdick.
An autonomous sensor-based path-planning for planetary microrovers.
In Proceedings IEEE International Conference on Robotics & Automation, 1999.

593
J.-P. Laumond.
Trajectories for mobile robots with kinematic and environment constraints.
In Proceedings International Conference on Intelligent Autonomous Systems, pages 346-354, 1986.

594
J.-P. Laumond.
Controllability of a multibody mobile robot.
IEEE Transactions on Robotics & Automation, 9(6):755-763, December 1993.

595
J.-P. Laumond.
Robot Motion Planning and Control.
Springer-Verlag, Berlin, 1998.
Available online at http://www.laas.fr/$ \sim$jpl/book.html.

596
J.-P. Laumond, S. Sekhavat, and F. Lamiraux.
Guidelines in nonholonomic motion planning for mobile robots.
In J.-P. Laumond, editor, Robot Motion Planning and Control, pages 1-53. Springer-Verlag, Berlin, 1998.

597
S. M. LaValle.
A Game-Theoretic Framework for Robot Motion Planning.
PhD thesis, University of Illinois, Urbana, IL, July 1995.

598
S. M. LaValle.
Rapidly-exploring random trees: A new tool for path planning.
Technical Report 98-11, Computer Science Dept., Iowa State University, Oct. 1998.

599
S. M. LaValle.
Robot motion planning: A game-theoretic foundation.
Algorithmica, 26(3):430-465, 2000.

600
S. M. LaValle, M. S. Branicky, and S. R. Lindemann.
On the relationship between classical grid search and probabilistic roadmaps.
International Journal of Robotics Research, 23(7/8):673-692, July/August 2004.

601
S. M. LaValle, P. Finn, L. Kavraki, and J.-C. Latombe.
A randomized kinematics-based approach to pharmacophore-constrained conformational search and database screening.
J. Computational Chemistry, 21(9):731-747, 2000.

602
S. M. LaValle, H. H. González-Baños, C. Becker, and J.-C. Latombe.
Motion strategies for maintaining visibility of a moving target.
In Proceedings IEEE International Conference on Robotics and Automation, pages 731-736, 1997.

603
S. M. LaValle and J. Hinrichsen.
Visibility-based pursuit-evasion: The case of curved environments.
IEEE Transactions on Robotics and Automation, 17(2):196-201, April 2001.

604
S. M. LaValle and S. A. Hutchinson.
An objective-based stochastic framework for manipulation planning.
In Proceedings IEEE/RSJ/GI International Conference on Intelligent Robots and Systems, pages 1772-1779, September 1994.

605
S. M. LaValle and S. A. Hutchinson.
An objective-based framework for motion planning under sensing and control uncertainties.
International Journal of Robotics Research, 17(1):19-42, January 1998.

606
S. M. LaValle and S. A. Hutchinson.
Optimal motion planning for multiple robots having independent goals.
IEEE Trans. on Robotics and Automation, 14(6):912-925, December 1998.

607
S. M. LaValle and P. Konkimalla.
Algorithms for computing numerical optimal feedback motion strategies.
International Journal of Robotics Research, 20(9):729-752, September 2001.

608
S. M. LaValle and J. J. Kuffner.
Randomized kinodynamic planning.
In Proceedings IEEE International Conference on Robotics and Automation, pages 473-479, 1999.

609
S. M. LaValle and J. J. Kuffner.
Rapidly-exploring random trees: Progress and prospects.
In Proceedings Workshop on the Algorithmic Foundations of Robotics, 2000.

610
S. M. LaValle and J. J. Kuffner.
Randomized kinodynamic planning.
International Journal of Robotics Research, 20(5):378-400, May 2001.

611
S. M. LaValle and J. J. Kuffner.
Rapidly-exploring random trees: Progress and prospects.
In B. R. Donald, K. M. Lynch, and D. Rus, editors, Algorithmic and Computational Robotics: New Directions, pages 293-308. A K Peters, Wellesley, MA, 2001.

612
S. M. LaValle, D. Lin, L. J. Guibas, J.-C. Latombe, and R. Motwani.
Finding an unpredictable target in a workspace with obstacles.
In Proceedings IEEE International Conference on Robotics and Automation, pages 737-742, 1997.

613
S. M. LaValle and R. Sharma.
On motion planning in changing, partially-predictable environments.
International Journal of Robotics Research, 16(6):775-805, December 1997.

614
S. Lazebnik.
Visibility-based pursuit evasion in three-dimensional environments.
Technical Report CVR TR 2001-01, Beckman Institute, University of Illinois, 2001.

615
A. R. Leach and I. D. Kuntz.
Conformational analysis of flexible ligands in macromolecular receptor sites.
Journal of Computational Chemistry, 13(6):730-748, 1992.

616
D. T. Lee and R. L. Drysdale.
Generalization of Voronoi diagrams in the plane.
SIAM Journal on Computing, 10:73-87, 1981.

617
J. Lee, J. Chai, P. S. A. Reitsma, J. K. Hodgins, and N. S. Pollard.
Interactive control of avatars with human motion data.
In Proceedings ACM SIGGRAPH, 2002.

618
J.-H. Lee, S. Y. Shin, and K.-Y. Chwa.
Visibility-based pursuit-evasions in a polygonal room with a door.
In Proceedings ACM Symposium on Computational Geometry, 1999.

619
D. H. Lehmer.
Mathematical methods in large-scale computing units.
In Proceedings 2nd Symposium on Large-Scale Digital Computing Machinery, pages 141-146, Cambridge, MA, 1951. Harvard University Press.

620
J. Lengyel, M. Reichert, B. R. Donald, and D. P. Greenberg.
Real-time robot motion planning using rasterizing computer graphics hardware.
Computer Graphics, 24(4):327-335, August 1990.

621
S. Lenser and M. Veloso.
Sensor resetting localization for poorly modelled mobile robots.
In Proceedings IEEE International Conference on Robotics & Automation, 2000.

622
J. Leonard, H. Durrant-Whyte, and I. Cox.
Dynamic map building for an autonomous mobile robot.
International Journal of Robotics Research, 11(4):89-96, 1992.

623
N. E. Leonard and P. S. Krishnaprasad.
Averaging for attitude control and motion planning.
In Proceedings IEEE Conference Decision & Control, pages 3098-3104, December 1993.

624
N. E. Leonard and P. S. Krishnaprasad.
Motion control of drift-free left-invariant systems on lie groups.
IEEE Transactions on Automatic Control, 40(9):1539-1554, 1995.

625
D. Leven and M. Sharir.
An efficient and simple motion planning algorithm for a ladder moving in a 2-dimensional space amidst polygonal barriers.
Journal of Algorithms, 8:192-215, 1987.

626
D. Leven and M. Sharir.
Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams.
Discrete and Computational Geometry, 2:9-31, 1987.

627
P. Leven and S. A. Hutchinson.
Real-time path planning in changing environments.
IEEE Transactions on Robotics & Automation, 21(12):999-1030, December 2002.

628
P. Leven and S. A. Hutchinson.
Using manipulability to bias sampling during the construction of probabilistic roadmaps.
IEEE Transactions on Robotics & Automation, 19(6):1020-1026, December 2003.

629
A. D. Lewis, J. P. Ostrowski, J. W. Burdick, and R. M. Murray.
Nonholonomic mechanics and locomotion: The snakeboard example.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2391-2400, 1994.

630
M. Li and P. Vitanyi.
An Introduction to Kolmogorov Complexity and Its Applications.
Springer-Verlag, Berlin, 1997.

631
T.-Y. Li and Y.-C. Shie.
An incremental learning approach to motion planning with roadmap management.
In Proceedings IEEE International Conference on Robotics & Automation, 2002.

632
Z. Li and J. F. Canny.
Motion of two rigid bodies with rolling constraint.
IEEE Transactions on Robotics & Automation, 6(1):62-72, February 1990.

633
Z. Li and J. F. Canny.
Nonholonomic Motion Planning.
Kluwer, Boston, MA, 1993.

634
D. Liberzon.
Switching in Systems and Control.
Birkhäuser, Boston, MA, 2003.

635
J.-M. Lien, S. L. Thomas, and N. M. Amato.
A general framework for sampling on the medial axis of the free space.
In Proceedings IEEE International Conference on Robotics & Automation, 2003.

636
M. C. Lin and J. F. Canny.
Efficient algorithms for incremental distance computation.
In Proceedings IEEE International Conference on Robotics & Automation, 1991.

637
M. C. Lin and D. Manocha.
Collision and proximity queries.
In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, 2nd Ed., pages 787-807. Chapman and Hall/CRC Press, New York, 2004.

638
M. C. Lin, D. Manocha, J. Cohen, and S. Gottschalk.
Collision detection: Algorithms and applications.
In J.-P. Laumond and M. H. Overmars, editors, Algorithms for Robotic Motion and Manipulation, pages 129-142. A.K. Peters, Wellesley, MA, 1997.

639
S. R. Lindemann and S. M. LaValle.
Incremental low-discrepancy lattice methods for motion planning.
In Proceedings IEEE International Conference on Robotics and Automation, pages 2920-2927, 2003.

640
S. R. Lindemann and S. M. LaValle.
Current issues in sampling-based motion planning.
In P. Dario and R. Chatila, editors, Proceedings International Symposium on Robotics Research. Springer-Verlag, Berlin, 2004.

641
S. R. Lindemann and S. M. LaValle.
Incrementally reducing dispersion by increasing Voronoi bias in RRTs.
In Proceedings IEEE International Conference on Robotics and Automation, 2004.

642
S. R. Lindemann and S. M. LaValle.
Steps toward derandomizing RRTs.
In IEEE Fourth International Workshop on Robot Motion and Control, 2004.

643
S. R. Lindemann and S. M. LaValle.
Smoothly blending vector fields for global robot navigation.
In Proceedings IEEE Conference Decision & Control, pages 3353-3559, 2005.

644
S. R. Lindemann, A. Yershova, and S. M. LaValle.
Incremental grid sampling strategies in robotics.
In Proceedings Workshop on Algorithmic Foundations of Robotics, pages 297-312, 2004.

645
A. Lingas.
The power of non-rectilinear holes.
In Proceedings 9th International Colloquium on Automata, Languange, and Programming, pages 369-383. Springer-Verlag, 1982.
Lecture Notes in Computer Science, 140.

646
F. Lingelbach.
Path planning using probabilistic cell decomposition.
In Proceedings IEEE International Conference on Robotics & Automation, 2004.

647
M. Littman.
The witness algorithm: Solving partially observable Markov decision processes.
Technical Report CS-94-40, Brown University, Providence, RI, 1994.

648
M. L. Littman, A. R. Cassandra, and L. P. Kaelbling.
Learning policies for partially-observable environments: Scaling up.
In Proceedings International Conference on Machine Learning, pages 362-370, 1995.

649
C. K. Liu and Z. Popovic.
Synthesis of complex dynamic character motion from simple animations.
In Proceedings ACM SIGGRAPH, pages 408-416, 2002.

650
Y. Liu and S. Arimoto.
Path planning using a tangent graph for mobile robots among polygonal and curved obstacles.
International Journal of Robotics Research, 11(4):376-382, 1992.

651
S. G. Loizou and K. J. Kyriakopoulos.
Closed loop navigation for multiple holonomic vehicles.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2002.

652
S. G. Loizou and K. J. Kyriakopoulos.
Closed loop navigation for multiple non-holonomic vehicles.
In Proceedings IEEE International Conference on Robotics & Automation, 2003.

653
I. Lotan, F. Schwarzer, D. Halperin, and J.-C. Latombe.
Efficient maintenance and self-collision testing for kinematic chains.
In Proceedings ACM Symposium on Computational Geometry, pages 43-52, 2002.

654
I. Lotan, H. van den Bedem, A. M. Deacon, and J.-C. Latombe.
Computing protein structures from electron density maps: The missing loop problem.
In Proceedings Workshop on Algorithmic Foundations of Robotics, 2004.

655
W. S. Lovejoy.
Computationally feasible bounds for partially observed Markov decision processes.
Operations Research, 39(1):162-175, 1991.

656
T. Lozano-Pérez.
Automatic planning of manipulator transfer movements.
IEEE Transactions on Systems, Man, & Cybernetics, 11(10):681-698, 1981.

657
T. Lozano-Pérez.
Spatial planning: A configuration space approach.
IEEE Transactions on Computing, C-32(2):108-120, 1983.

658
T. Lozano-Pérez.
A simple motion-planning algorithm for general robot manipulators.
IEEE Journal of Robotics & Automation, RA-3(3):224-238, Jun 1987.

659
T. Lozano-Pérez, M. T. Mason, and R. H. Taylor.
Automatic synthesis of fine-motion strategies for robots.
International Journal of Robotics Research, 3(1):3-24, 1984.

660
T. Lozano-Pérez and M. A. Wesley.
An algorithm for planning collision-free paths among polyhedral obstacles.
Communications of the ACM, 22(10):560-570, 1979.

661
L. Lu and S. Akella.
Folding cartons with fixtures: A motion planning approach.
IEEE Transactions on Robotics & Automation, 16(4):346-356, Aug 2000.

662
P. Lu and J. M. Hanson.
Entry guidance for the X-33 vehicle.
Journal of Spacecraft and Rockets, 35(3):342-349, 1998.

663
A. De Luca, G. Oriolo, and C. Samson.
Feedback control of a nonholonomic car-like robot.
In J.-P. Laumond, editor, Robot Motion Planning and Control, pages 171-253. Springer-Verlag, Berlin, 1998.

664
D. G. Luenberger.
Introduction to Linear and Nonlinear Programming.
Wiley, New York, 1973.

665
V. J. Lumelsky and K. R. Harinarayan.
Decentralized motion planning for multiple mobile robots: The cocktail party model.
Autonomous Robots, 4(1):121-135, 1997.

666
V. J. Lumelsky and T. Skewis.
Incorporating range sensing in the robot navigation function.
IEEE Transactions on Systems, Man, & Cybernetics, 20(5):1058-1069, 1990.

667
V. J. Lumelsky and A. A. Stepanov.
Path planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape.
Algorithmica, 2:403-430, 1987.

668
V. J. Lumelsky and S. Tiwari.
An algorithm for maze searching with azimuth input.
In Proceedings IEEE International Conference on Robotics & Automation, pages 111-116, 1994.

669
K. M. Lynch.
Controllability of a planar body with unilateral thrusters.
IEEE Transactions on Automatic Control, 44(6):1206-1211, 1999.

670
K. M. Lynch and M. T. Mason.
Pulling by pushing, slip with infinite friction, and perfectly rough surfaces.
International Journal of Robotics Research, 14(2):174-183, 1995.

671
K. M. Lynch and M. T. Mason.
Stable pushing: Mechanics, controllability, and planning.
International Journal of Robotics Research, 15(6):533-556, 1996.

672
K. M. Lynch, N. Shiroma, H. Arai, and K. Tanie.
Collision free trajectory planning for a 3-dof robot with a passive joint.
International Journal of Robotics Research, 19(12):1171-1184, 2000.

673
I. M. Makarov, T. M. Vinogradskaya, A. A. Rubchinsky, and V. B. Sokolov.
The Theory of Choice and Decision Making.
Mir Publishers, Moscow, 1987.

674
M. S. Manasse, L. A. McGeoch, and D. D. Sleator.
Competitive algorithms for on-line problems.
In Proceedings ACM Symposium on Theory of Computing, pages 322-333, 1988.

675
D. Manocha and J. Canny.
Real time inverse kinematics of general 6R manipulators.
In Proceedings IEEE International Conference on Robotics & Automation, pages 383-389, Nice, May 1992.

676
A. Marigo and A. Bicchi.
Rolling bodies with regular surface: Controllability theory and applications.
IEEE Transactions on Automatic Control, 45(9):1586-1599, 2000.

677
J. E. Marsden and T. S. Ratiu.
Introduction to Mechanics and Symmetry.
Springer-Verlag, Berlin, 1999.

678
M. T. Mason.
Compliance and force control for computer controlled manipulators.
In M. Brady et al., editor, Robot Motion: Planning and Control, pages 373-404. MIT Press, Cambridge, MA, 1982.

679
M. T. Mason.
The mechanics of manipulation.
In Proceedings IEEE International Conference on Robotics & Automation, pages 544-548, 1985.

680
M. T. Mason.
Mechanics and planning of manipulator pushing operations.
International Journal of Robotics Research, 5(3):53-71, 1986.

681
M. T. Mason.
Mechanics of Robotic Manipulation.
MIT Press, Cambridge, MA, 2001.

682
J. Matousek.
Geometric Discrepancy.
Springer-Verlag, Berlin, 1999.

683
J. Matousek and J. Nesetril.
Invitation to Discrete Mathematics.
Oxford University Press, Oxford, U.K., 1998.

684
M. Matsumoto and T. Nishimura.
Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator.
ACM Transactions on Modeling and Computer Simulation, 8(1):3-30, January 1998.

685
L. Matthies and A. Elfes.
Integration of sonar and stereo range data using a grid-based representation.
In Proceedings IEEE International Conference on Robotics & Automation, pages 727-733, 1988.

686
O. Mayr.
The Origins of Feedback Control.
MIT Press, Cambridge, MA, 1970.

687
E. Mazer, J. M. Ahuactzin, and P. Bessière.
The Ariadne's clew algorithm.
Journal of Artificial Intelligence Research, 9:295-316, November 1998.

688
E. Mazer, G. Talbi, J. M. Ahuactzin, and P. Bessière.
The Ariadne's clew algorithm.
In Proceedings International Conference of Society of Adaptive Behavior, Honolulu, 1992.

689
J. M. McCarthy.
Geometric Design of Linkages.
Springer-Verlag, Berlin, 2000.

690
D. J. McGill and W. W. King.
An Introduction to Dynamics.
PWS, Boston, MA, 1995.

691
R. McKelvey and A. McLennan.
Computation of equilibria in finite games.
In H. Amman, D. A. Kendrick, and J .Rust, editors, The Handbook of Computational Economics, pages 87-142. Elsevier, New York, 1996.

692
N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou.
The complexity of searching a graph.
Journal of the ACM, 35(1):18-44, January 1988.

693
J.-P. Merlet.
Parallel Robots.
Kluwer, Boston, MA, 2000.

694
A. W. Merz.
The game of two identical cars.
Journal of Optimization Theory & Applications, 9(5):324-343, 1972.

695
N. C. Metropolis and S. M. Ulam.
The Monte-Carlo method.
Journal of the American Statistical Association, 44:335-341, 1949.

696
A. N. Michel and C. J. Herget.
Applied Algebra and Functional Analysis.
Dover, New York, 1993.

697
R. J. Milgram and J. C. Trinkle.
Complete path planning for closed kinematic chains with spherical joints.
International Journal of Robotics Research, 21(9):773-789, 2002.

698
R. J. Milgram and J. C. Trinkle.
The geometry of configuration spaces for closed chains in two and three dimensions.
Homology, Homotopy, and Applications, 6(1):237-267, 2004.

699
D. A. Miller and S. W. Zucker.
Copositive-plus Lemke algorithm solves polymatrix games.
Operations Research Letters, 10:285-290, 1991.

700
G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis.
Separators for sphere-packings and nearest neighbor graphs.
Journal of the ACM, 44(1):1-29, January 1997.

701
J. W. Milnor.
Morse Theory.
Princeton University Press, Princeton, NJ, 1963.

702
B. Mirtich.
V-Clip: Fast and robust polyhedral collision detection.
Technical Report TR97-05, Mitsubishi Electronics Research Laboratory, 1997.

703
B. Mirtich.
Efficient algorithms for two-phase collision detection.
In K. Gupta and A.P. del Pobil, editors, Practical Motion Planning in Robotics: Current Approaches and Future Directions, pages 203-223. Wiley, New York, 1998.

704
B. Mishra.
Algorithmic Algebra.
Springer-Verlag, New York, 1993.

705
B. Mishra.
Computational real algebraic geometry.
In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, pages 537-556. CRC Press, New York, 1997.

706
I. Mitchell, A. Bayen, and C. Tomlin.
Computing reachable sets for continuous dynamic games using level set methods.
IEEE Transactions on Automatic Control, 2003.
Submitted.

707
I. Mitchell and C. J. Tomlin.
Overapproximating reachable sets by Hamilton-Jacobi projections.
Journal of Scientific Computation, 19(1):323-346, 2003.

708
J. S. B. Mitchell.
Shortest paths among obstacles in the plane.
International Journal Computational Geometry & Applications, 6(3):309-332, 1996.

709
J. S. B. Mitchell.
Shortest paths and networks.
In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, 2nd Ed., pages 607-641. Chapman and Hall/CRC Press, New York, 2004.

710
J. S. B. Mitchell and C. H. Papadimitriou.
The weighted region problem.
Journal of the ACM, 38:18-73, 1991.

711
T. M. Mitchell.
Machine Learning.
McGraw-Hill, New York, 1997.

712
L. Molina-Tanco and A. Hilton.
Realistic synthesis of novel human movements from a database of motion capture examples.
In Proceedings IEEE Workshop on Human Motion, 2000.

713
S. Monaco and D. Normand-Cyrot.
An introduction to motion planning under multirate digital control.
In Proceedings IEEE Conference Decision & Control, pages 1780-1785, 1992.

714
G. Monahan.
A survey of partially observable Markov decision processes.
Management Science, 101(1):1-16, 1982.

715
B. Monien and I. H. Sudborough.
Min cut is NP-complete for edge weighted graphs.
Theoretical Computer Science, 58:209-229, 1988.

716
D. J. Montana.
The kinematics of contact and grasp.
International Journal of Robotics Research, 7(3):17-32, 1988.

717
M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit.
FastSLAM: A factored solution to the simultaneous localization and mapping problem.
In Proceedings AAAI National Conference on Artificial Intelligence, 1999.

718
M. E. Mortenson.
Geometric Modeling, 2nd Ed.
Wiley, New York, 1997.

719
R. Motwani and P. Raghavan.
Randomized Algorithms.
Cambridge University Press, Cambridge, U.K., 1995.

720
R. Munos.
Error bounds for approximate value iteration.
In Proceedings AAAI National Conference on Artificial Intelligence, 2005.

721
R. Munos and A. Moore.
Barycentric interpolator for continuous space & time reinforcement learning.
In Proceedings Neural Information Processing Systems, 1998.

722
R. Munos and A. Moore.
Variable resolution discretization in optimal control.
Machine Learning, 49:291-323, 2001.

723
T. Muppirala, R. Murrieta-Cid, and S. Hutchinson.
Optimal motion strategies based on critical events to maintain visibility of a moving target.
In Proceedings IEEE International Conference on Robotics & Automation, pages 3837-3842, 2005.

724
T. Murphey.
Control of Multiple Model Systems.
PhD thesis, California Institute of Technology, May 2002.

725
R. M. Murray, Z. Li, and S. Sastry.
A Mathematical Introduction to Robotic Manipulation.
CRC Press, Boca Raton, FL, 1994.

726
R. M. Murray, M. Rathinam, and W. M. Sluis.
Differential flatness of mechanical control systems.
In Proceedings ASME International Congress and Exposition, 1995.

727
R. M. Murray and S. Sastry.
Nonholonomic motion planning: Steering using sinusoids.
IEEE Transactions on Automatic Control, 38(5):700-716, 1993.

728
R. Murrieta-Cid, A. Sarmiento, S. Bhattacharya, and S. Hutchinson.
Maintaining visibility of a moving target at a fixed distance: The case of observer bounded speed.
In Proceedings IEEE International Conference on Robotics & Automation, pages 479-484, 2004.

729
Y. Nakamura, T. Suzuki, and M. Koinuma.
Nonlinear behavior and control of a nonholonomic free-joint manipulator.
IEEE Transactions on Robotics & Automation, 13(6):853-862, 1997.

730
J. Nash.
Noncooperative games.
Annals of Mathematics, 54(2):286-295, 1951.

731
S. G. Nash and A. Sofer.
Linear and Nonlinear Programming.
McGraw-Hill, New York, 1996.

732
B. K. Natarajan.
The complexity of fine motion planning.
International Journal of Robotics Research, 7(2):36-42, 1988.

733
B. K. Natarajan.
On planning assemblies.
In Proceedings ACM Symposium on Computational Geometry, pages 299-308, 1988.

734
New York University.
MathMol Library.
Scientific Visualization Center. Available from http://www.nyu.edu/pages/mathmol/library/, 2005.

735
A. Newell and H. Simon.
GPS: A program that simulates human thought.
In E. A. Feigenbaum and J. Feldman, editors, Computers and Thought. McGraw-Hill, New York, 1963.

736
W. S. Newman and M. S. Branicky.
Real-time configuration space transforms for obstacle avoidance.
International Journal of Robotics Research, 10(6):650-667, 1991.

737
A. Y. Ng and M. Jordan.
PEGASUS: A policy search method for large MDPs and POMDPs.
In Proceedings Conference on Uncertainty in Artificial Intelligence, 2000.

738
H. Niederreiter.
Random Number Generation and Quasi-Monte-Carlo Methods.
Society for Industrial and Applied Mathematics, Philadelphia, 1992.

739
H. Niederreiter and C. P. Xing.
Nets, (t,s)-sequences, and algebraic geometry.
In P. Hellekalek and G. Larcher, editors, Random and Quasi-Random Point Sets, pages 267-302. Springer-Verlag, Berlin, 1998.
Lecture Notes in Statistics, 138.

740
D. Nieuwenhuisen and M. H. Overmars.
Useful cycles in probabilistic roadmap graphs.
In Proceedings IEEE International Conference on Robotics & Automation, pages 446-452, 2004.

741
H. Nijmeijer and A. J. van der Schaft.
Nonlinear Dynamical Control Systems.
Springer-Verlag, Berlin, 1990.

742
N. J. Nilsson.
A mobile automaton: An application of artificial intelligence techniques.
In 1st International Conference on Artificial Intelligence, pages 509-520, 1969.

743
N. J. Nilsson.
Principles of Artificial Intelligence.
Tioga Publishing Company, Wellsboro, PA, 1980.

744
N. J. Nilsson.
Artificial Intelligence: A New Synthesis.
Morgan Kaufmann, San Francisco, CA, 1998.

745
S. Ntafos.
Watchman routes under limited visibility.
Computational Geometry: Theory and Applications, 1:149-170, 1992.

746
P. A. O'Donnell and T. Lozano-Pérez.
Deadlock-free and collision-free coordination of two robot manipulators.
In Proceedings IEEE International Conference on Robotics & Automation, pages 484-489, 1989.

747
C. O'Dunlaing.
Motion planning with inertial constraints.
Algorithmica, 2(4):431-475, 1987.

748
C. O'Dunlaing, M. Sharir, and C. K. Yap.
Retraction: A new approach to motion planning.
In J .T .Schwartz, M. Sharir, and J. Hopcroft, editors, Planning, Geometry, and Complexity of Robot Motion, pages 193-213. Ablex, Norwood, NJ, 1987.

749
C. O'Dunlaing and C. K. Yap.
A retraction method for planning the motion of a disc.
Journal of Algorithms, 6:104-111, 1982.

750
P. Ögren.
Formations and Obstacle Avoidance in Mobile Robot Control.
PhD thesis, Royal Institute of Technology (KTH), Stockholm, Sweden, 2003.

751
J. M. O'Kane.
Global localization using odometry.
In Proceedings IEEE International Conference on Robotics and Automation, 2005.

752
J. M. O'Kane and S. M. LaValle.
Almost-sensorless localization.
In Proceedings IEEE International Conference on Robotics and Automation, 2005.

753
B. O'Neill.
Elementary Differential Geometry.
Academic, New York, 1966.

754
S. Oore, G. E. Hinton, and G. Dudek.
A mobile robot that learns its place.
Neural Computation, 9:683-699, 1997.

755
J. O'Rourke.
Art Gallery Theorems and Algorithms.
Oxford University Press, New York, 1987.

756
J. O'Rourke.
Visibility.
In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, 2nd Ed., pages 643-663. Chapman and Hall/CRC Press, New York, 2004.

757
J. O'Rourke and S. Suri.
Polygons.
In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, 2nd Ed., pages 583-606. Chapman and Hall/CRC Press, New York, 2004.

758
M. H. Overmars and J. van Leeuwen.
Dynamic multidimensional data structures based on Quad- and K-D trees.
Acta Informatica, 17:267-285, 1982.

759
G. Owen.
Game Theory.
Academic, New York, 1982.

760
B. Paden, A. Mees, and M. Fisher.
Path planning using a Jacobian-based freespace generation algorithm.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1732-1737, 1989.

761
D. K. Pai and L. M. Reissell.
Multiresolution rough terrain motion planning.
IEEE Transactions on Robotics & Automation, 14(5):709-717, 1998.

762
S. Pancanti, L. Pallottino, D. Salvadorini, and A. Bicchi.
Motion planning through symbols and lattices.
In Proceedings IEEE International Conference on Robotics & Automation, pages 3914-3919, 2004.

763
C. H. Papadimitriou.
An algorithm for shortest-path planning in three dimensions.
Information Processing Letters, 20(5):259-263, 1985.

764
C. H. Papadimitriou.
Games against nature.
Journal of Computer and System Sciences, 31:288-301, 1985.

765
C. H. Papadimitriou and K. J. Steiglitz.
Combinatorial Optimization: Algorithms and Complexity.
Prentice Hall, Englewood Cliffs, NJ, 1982.

766
C. H. Papadimitriou and J. N. Tsitsiklis.
Intractable problems in control theory.
SIAM Journal of Control & Optimization, 24(4):639-654, July 1986.

767
C. H. Papadimitriou and J. N. Tsitsiklis.
The complexity of Markov decision processes.
Mathematics of Operations Research, 12(3):441-450, August 1987.

768
C. H. Papadimitriou and M. Yannakakis.
Shortest paths without a map.
Theoretical Computer Science, 84:127-150, 1991.

769
A. Papantonopoulou.
Algebra: Pure and Applied.
Prentice Hall, Englewood Cliffs, NJ, 2002.

770
S.-M. Park, J.-H. Lee, and K.-Y. Chwa.
Visibility-based pursuit-evasion in a polygonal region by a searcher.
Technical Report CS/TR-2001-161, Dept. of Computer Science, KAIST, Seoul, South Korea, January 2001.

771
R. Parr and A. Eliazar.
DP-SLAM: Fast, robust simultaneous localization and mapping without predetermined landmarks.
In Proceedings International Joint Conference on Artificial Intelligence, 2003.

772
R. Parr and S. Russell.
Approximating optimal policies for partially observable stochastic domains.
In Proceedings International Joint Conference on Artificial Intelligence, 1995.

773
T. D. Parsons.
Pursuit-evasion in a graph.
In Y. Alavi and D. R. Lick, editors, Theory and Application of Graphs, pages 426-441. Springer-Verlag, Berlin, 1976.

774
T. Parthasarathy and M. Stern.
Markov games: A survey.
In Differential Games and Control Theory II, pages 1-46. Marcel Dekker, New York, 1977.

775
R. P. Paul.
Robot Manipulators: Mathematics, Programming, and Control.
MIT Press, Cambridge, MA, 1981.

776
R. P. Paul and B. Shimano.
Compliance and control.
In Proceedings of the Joint American Automatic Control Conference, pages 1694-1699, 1976.

777
J. Pearl.
Heuristics.
Addison-Wesley, Reading, MA, 1984.

778
J. Pearl.
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.
Morgan Kaufmann, San Francisco, CA, 1988.

779
B. Peleg and P. Sudlölter.
Introduction to the Theory of Cooperative Games.
Springer-Verlag, Berlin, 2003.

780
J. Peng and S. Akella.
Coordinating multiple robots with kinodynamic constraints along specified paths.
In J.-D. Boissonnat, J. Burdick, K. Goldberg, and S. Hutchinson, editors, Algorithmic Foundations of Robotics V (WAFR 2002), pages 221-237. Springer-Verlag, Berlin, 2002.

781
J. Pertin-Troccaz.
Grasping: A state of the art.
In O. Khatib, J. J. Craig, and T. Lozano-Pérez, editors, The Robotics Review 1. MIT Press, Cambridge, MA, 1989.

782
S. Petitjean, D. Kriegman, and J. Ponce.
Computing exact aspect graphs of curved objects: algebraic surfaces.
International Journal of Computer Vision, 9:231-255, Dec 1992.

783
L. A. Petrosjan.
Differential Games of Pursuit.
World Scientific, Singapore, 1993.

784
J. Pettré, J.-P. Laumond, and T. Siméon.
A 2-stages locomotion planner for digital actors.
In Proceedings Eurographics/SIGGRAPH Symposium on Computer Animation, pages 258-264, 2003.

785
F. Pfeiffer and R. Johanni.
A concept for manipulator trajectory planning.
IEEE Journal of Robotics & Automation, RA-3(2):115-123, 1987.

786
J. M. Phillips, N. Bedrosian, and L. E. Kavraki.
Spacecraft rendezvous and docking with real-time randomized optimization.
In Proceedings AIAA Guidance, Navigation and Control Conference, 2003.

787
A. Piazzi, M. Romano, and C. G. Lo Bianco.
$ G^3$ splines for the path planning of wheeled mobile robots.
In Proceedings European Control Conference, 2003.

788
L. Piegl.
On NURBS: A survey.
IEEE Transactions on Computer Graphics & Applications, 11(1):55-71, Jan 1991.

789
D. A. Pierre.
Optimization Theory with Applications.
Dover, New York, 1986.

790
R. W. Pike.
Optimization for Engineering Systems.
[Online], 2001.
Available at http://www.mpri.lsu.edu/bookindex.html.

791
J. Pineau, G. Gordon, and S. Thrun.
Point-based value iteration.
In Proceedings International Joint Conference on Artificial Intelligence, pages 1025-1032, 2003.

792
C. Pisula, K. Hoff, M. Lin, and D. Manocha.
Randomized path planning for a rigid body based on hardware accelerated Voronoi sampling.
In Proceedings Workshop on Algorithmic Foundations of Robotics, 2000.

793
R. Pito.
A sensor based solution to the next best view problem.
In International Conference Pattern Recognition, 1996.

794
M. Pivtoraiko and A. Kelly.
Generating near minimal spanning control sets for constrained motion planning in discrete state spaces.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005.

795
E. Plaku and L. E. Kavraki.
Distributed sampling-based roadmap of trees for large-scale motion planning.
In Proceedings IEEE International Conference on Robotics & Automation, 2005.

796
M. Pocchiola and G. Vegter.
The visibility complex.
International Journal Computational Geometry & Applications, 6(3):279-308, 1996.

797
I. Pohl.
Bi-directional and heuristic search in path problems.
Technical report, Stanford Linear Accelerator Center, Stanford, CA, 1969.

798
I. Pohl.
Bi-directional search.
In B. Meltzer and D. Michie, editors, Machine Intelligence, pages 127-140. Elsevier, New York, 1971.

799
J. Ponce and B. Faverjon.
On computing three-finger force-closure grasps of polygonal objects.
IEEE Transactions on Robotics & Automation, 11(6):868-881, 1995.

800
J. Ponce, S. Sullivan, A. Sudsang, J.-D. Boissonnat, and J.-P. Merlet.
On computing four-finger equilibrium and force-closure grasps of polyhedral objects.
International Journal of Robotics Research, 16(1):11-35, February 1997.

801
L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze, and E. F. Mishchenko.
L. S. Pontryagin Selected Works, Volume 4: The Mathematical Theory of Optimal Processes.
Gordon and Breach, Montreux, Switzerland, 1986.

802
J. Popovic, S. M. Seitz, M. A. Erdmann, and Z. Popovic A. P. Wiktin.
Interactive manipulation of rigid body simulations.
In Proceedings ACM SIGGRAPH, pages 209-217, 2002.

803
J. M. Porta, M. T. J. Spaan, and N. Vlassis.
Robot planning in partially observable continuous domains.
In Proceedings Robotics: Science and Systems, 2005.

804
H. Pottman and J. Wallner.
Computational Line Geometry.
Springer-Verlag, Berlin, 2001.

805
P. Poupart and C. Boutilier.
Value-directed compression of POMDPs.
In Proceedings Neural Information Processing Systems, 2003.

806
F. P. Preparata and M. I. Shamos.
Computational Geometry.
Springer-Verlag, Berlin, 1985.

807
S. Quinlan.
Efficient distance computation between nonconvex objects.
In Proceedings IEEE International Conference on Robotics & Automation, pages 3324-3329, 1994.

808
M. Rabin.
Transaction protection by beacons.
Journal of Computation Systems Science, 27(2):256-267, 1983.

809
S. Rajko and S. M. LaValle.
A pursuit-evasion bug algorithm.
In Proceedings IEEE International Conference on Robotics and Automation, pages 1954-1960, 2001.

810
A. Rao and K. Goldberg.
Manipulating algebraic parts in the plane.
IEEE Transactions on Robotics & Automation, 11(4):598-602, 1995.

811
N. Rao, S. Kareti, W. Shi, and S. Iyenagar.
Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms.
Technical Report ORNL/TM-12410:1-58, Oak Ridge National Laboratory, July 1993.

812
S. Ratering and M. Gini.
Robot navigation in a known environment with unknown moving obstacles.
In Proceedings IEEE International Conference on Robotics & Automation, pages 25-30, 1993.

813
M. Rathinam and R. M. Murray.
Configuration flatness of Lagrangian systems underactuated by one control.
SIAM Journal of Control & Optimization, 36(1):164-179, 1998.

814
J. A. Reeds and L. A. Shepp.
Optimal paths for a car that goes both forwards and backwards.
Pacific Journal of Mathematics, 145(2):367-393, 1990.

815
J. Reif and Z. Sun.
On frictional mechanical systems and their computational power.
SIAM Journal on Computing, 32(6):1449-1474, 2003.

816
J. Reif and H. Wang.
Non-uniform discretization approximations for kinodynamic motion planning.
In J.-P. Laumond and M. H. Overmars, editors, Algorithms for Robotic Motion and Manipulation, pages 97-112. A.K. Peters, Wellesley, MA, 1997.

817
J. H. Reif.
Complexity of the mover's problem and generalizations.
In Proceedings IEEE Symposium on Foundations of Computer Science, pages 421-427, 1979.

818
J. H. Reif and M. Sharir.
Motion planning in the presence of moving obstacles.
In Proceedings IEEE Symposium on Foundations of Computer Science, pages 144-154, 1985.

819
J. H. Reif and M. Sharir.
Motion planning in the presence of moving obstacles.
Journal of the ACM, 41:764-790, 1994.

820
J. H. Reif and Z. Sun.
An efficient approximation algorithm for weighted region shortest path problem.
In B. R. Donald, K. M. Lynch, and D. Rus, editors, Algorithmic and Computational Robotics: New Directions, pages 191-203. A.K. Peters, Wellesley, MA, 2001.

821
J. H. Reif and S. R. Tate.
Continuous alternation: The complexity of pursuit in continuous domains.
Algorithmica, 10:157-181, 1993.

822
J. Reimpell, H. Stoll, and J. W. Betzler.
The Automotive Chassis: Engineering Principles.
Society of Automotive Engineers, Troy, MI, 2001.

823
E. M. Reingold, J. Nievergelt, and N. Deo.
Combinatorial Algorithms.
Prentice Hall, Englewood Cliffs, NJ, 1977.

824
E. Remolina and B. Kuipers.
Towards a general theory of topological maps.
Artificial Intelligence Journal, 152(1):47-104, 2004.

825
W. Rencken.
Concurrent localisation and map building for mobile robots using ultrasonic sensors.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2192-2197, 1993.

826
E. Rimon and J. W. Burdick.
Mobility of bodies in contact-I: A 2nd order mobility index for multiple-finger grasps.
IEEE Transactions on Robotics & Automation, 14(5):696-708, 1998.

827
E. Rimon and J. W. Burdick.
Mobility of bodies in contact-II: How forces are generated by curvature effects.
IEEE Transactions on Robotics & Automation, 14(5):709-717, 1998.

828
E. Rimon and J. Canny.
Construction of C-space roadmaps using local sensory data - What should the sensors look for?
In Proceedings IEEE International Conference on Robotics & Automation, pages 117-124, 1994.

829
E. Rimon and D. E. Koditschek.
Exact robot navigation using artificial potential fields.
IEEE Transactions on Robotics & Automation, 8(5):501-518, October 1992.

830
A. A. Rizzi.
Hybrid control as a method for robot motion programming.
In Proceedings IEEE International Conference on Robotics & Automation, pages 832-837, 1998.

831
C. P. Robert.
The Bayesian Choice, 2nd. Ed.
Springer-Verlag, Berlin, 2001.

832
H. Rohnert.
Shortest paths in the plane with convex polygonal obstacles.
Information Processing Letters, 23:71-76, 1986.

833
I. M. Ross and F. Fahroo.
Pseudospectral methods for optimal motion planning of differentially flat systems.
IEEE Transactions on Automatic Control, 49(8):1410-1413, 2004.

834
J. J. Rotman.
Introduction to Algebraic Topology.
Springer-Verlag, Berlin, 1988.

835
N. Roy and G. Gordon.
Exponential family PCA for belief compression in POMDPs.
In Proceedings Neural Information Processing Systems, 2003.

836
H. L. Royden.
Real Analysis.
MacMillan, New York, 1988.

837
W. Rudin.
Real Analysis.
McGraw-Hill, New York, 1987.

838
W. Rudin.
Functional Analysis, 2nd Ed.
McGraw-Hill, New York, 1991.

839
S. Russell and P. Norvig.
Artificial Intelligence: A Modern Approach, 2nd Edition.
Prentice-Hall, Englewood Cliffs, NJ, 2003.

840
S. Sachs, S. Rajko, and S. M. LaValle.
Visibility-based pursuit-evasion in an unknown planar environment.
International Journal of Robotics Research, 23(1):3-26, January 2004.

841
H. Sagan.
Introduction to the Calculus of Variations.
Dover, New York, 1992.

842
H. Sagan.
Space-Filling Curves.
Springer-Verlag, Berlin, 1994.

843
G. Sahar and J. M. Hollerbach.
Planning minimum-time trajectories for robot arms.
International Journal of Robotics Research, 5(3):97-140, 1986.

844
G. Sánchez and J.-C. Latombe.
A single-query bi-directional probabilistic roadmap planner with lazy collision checking.
In Proceedings International Symposium on Robotics Research, 2001.

845
G. Sánchez and J.-C. Latombe.
On delaying collision checking in PRM planning: Application to multi-robot coordination.
International Journal of Robotics Research, 21(1):5-26, 2002.

846
S. Sastry.
Nonlinear Systems: Analysis, Stability, and Control.
Springer-Verlag, Berlin, 1999.

847
Y. Sawaragi, H. Nakayama, and T. Tanino.
Theory of Multiobjective Optimization.
Academic, New York, 1985.

848
A. Scheuer and T. Fraichard.
Collision-free and continuous-curvature path planning for car-like robots.
In Proceedings IEEE International Conference on Robotics & Automation, pages 867-873, 1997.

849
A. Scheuer and C. Laugier.
Planning sub-optimal and continuous-curvature paths for car-like robots.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 25-31, 1998.

850
B. Schiele and J. Crowley.
A comparison of position estimation techniques using occupancy grids.
In Proceedings IEEE International Conference on Robotics & Automation, 1994.

851
J. T. Schwartz and M. Sharir.
On the Piano Movers' Problem: I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers.
Communications on Pure and Applied Mathematics, 36:345-398, 1983.

852
J. T. Schwartz and M. Sharir.
On the Piano Movers' Problem: II. General techniques for computing topological properties of algebraic manifolds.
Communications on Pure and Applied Mathematics, 36:345-398, 1983.

853
J. T. Schwartz and M. Sharir.
On the Piano Movers' Problem: III. Coordinating the motion of several independent bodies.
International Journal of Robotics Research, 2(3):97-140, 1983.

854
J. T. Schwartz, M. Sharir, and J. Hopcroft.
Planning, Geometry, and Complexity of Robot Motion.
Ablex, Norwood, NJ, 1987.

855
F. Schwarzer, M. Saha, and J.-C. Latombe.
Exact collision checking of robot paths.
In J.-D. Boissonnat, J. Burdick, K. Goldberg, and S. Hutchinson, editors, Algorithmic Foundations of Robotics V (WAFR 2002). Springer-Verlag, Berlin, 2002.

856
L. Sciavicco and B. Siciliano.
Modelling and Control of Robot Manipulators.
Springer-Verlag, Berlin, 1996.

857
R. Sedgewick.
Algorithms in C++, 2nd Ed.
Addison-Wesley, Reading, MA, 2002.

858
S. Sekhavat and J.-P. Laumond.
Topological property for collision-free nonholonomic motion planning: The case of sinusoidal inputs for chained-form systems.
IEEE Transactions on Robotics & Automation, 14(5):671-680, 1998.

859
S. Sekhavat, P. Svestka, J.-P. Laumond, and M. H. Overmars.
Multilevel path planning for nonholonomic robots using semiholonomic subsystems.
International Journal of Robotics Research, 17:840-857, 1998.

860
N. F. Sepetov, V. Krchnak, M. Stankova, S. Wade, K. S. Lam, and M. Lebl.
Library of libraries: Approach to synthetic combinatorial library design and screening of ``pharmacophore'' motifs.
Proceedings of the National Academy of Sciences, USA, 92:5426-5430, June 1995.

861
J.-P. Serre.
Lie Algebras and Lie Groups.
Springer-Verlag, Berlin, 1992.

862
J. A. Sethian.
Level set methods : Evolving interfaces in geometry, fluid mechanics, computer vision, and materials science.
Cambridge University Press, Cambridge, U.K., 1996.

863
A. A. Shabana.
Computational Dynamics.
Wiley, New York, 2001.

864
C. E. Shannon.
A mathematical theory of communication.
Bell Systems Technical Journal, 27:379-423, 1948.

865
M. Sharir.
Algorithmic motion planning.
In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, 2nd Ed., pages 1037-1064. Chapman and Hall/CRC Press, New York, 2004.

866
M. Sharir and P. K. Agarwal.
Davenport-Schinzel Sequences and Their Geometric Applications.
Cambridge University Press, Cambridge, U.K., 1995.

867
R. Sharma.
Locally efficient path planning in an uncertain, dynamic environment using a probabilistic model.
IEEE Transactions on Robotics & Automation, 8(1):105-110, February 1992.

868
R. Sharma.
A probabilistic framework for dynamic motion planning in partially known environments.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2459-2464, Nice, France, May 1992.

869
R. Sharma, J.-Y. Hervé, and P. Cucka.
Dynamic robot manipulation using visual tracking.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1844-1849, 1992.

870
R. Sharma, S. M. LaValle, and S. A. Hutchinson.
Optimizing robot motion strategies for assembly with stochastic models of the assembly process.
IEEE Trans. on Robotics and Automation, 12(2):160-174, April 1996.

871
R. Sharma, D. M. Mount, and Y. Aloimonos.
Probabilistic analysis of some navigation strategies in a dynamic environment.
IEEE Transactions on Systems, Man, & Cybernetics, 23(5):1465-1474, September 1993.

872
R. W. Sharpe.
Differential Geometry.
Springer-Verlag, Berlin, 1997.

873
H. Shatkay and L. P. Kaelbling.
Learning topological maps with weak local odometric information.
In Proceedings International Joint Conference on Artificial Intelligence, 1997.

874
T. Shermer.
Recent results in art galleries.
Proceedings of the IEEE, 80(9):1384-1399, September 1992.

875
C. L. Shih, T.-T. Lee, and W. A. Gruver.
A unified approach for robot motion planning with moving polyhedral obstacles.
IEEE Transactions on Systems, Man, & Cybernetics, 20:903-915, 1990.

876
Z. Shiller and S. Dubowsky.
On the optimal control of robotic manipulators with actuator and end-effector constraints.
In Proceedings IEEE International Conference on Robotics & Automation, pages 614-620, 1985.

877
Z. Shiller and S. Dubowsky.
On computing global time-optimal motions of robotic manipulators in the presence of obstacles.
IEEE Transactions on Robotics & Automation, 7(6):785-797, Dec 1991.

878
Z. Shiller and H.-H. Lu.
Computation of path constrained time-optimal motions with dynamic singularities.
Transactions of the ASME, Journal of Dynamical Systems, Measurement, & Control, 114:34-40, 1992.

879
K. G. Shin and N. D. McKay.
Minimum-time control of robot manipulators with geometric path constraints.
IEEE Transactions on Automatic Control, 30(6):531-541, 1985.

880
K. G. Shin and N. D. McKay.
A dynamic programming approach to trajectory planning of robotic manipulators.
IEEE Transactions on Automatic Control, 31(6):491-500, 1986.

881
K. G. Shin and Q. Zheng.
Minimum-time collision-free trajectory planning for dual-robot systems.
IEEE Transactions on Robotics & Automation, 8(5):641-644, October 1992.

882
A. M. Shkel and V. J. Lumelsky.
Incorporating body dynamics into sensor-based motion planning: The maximum turn strategy.
IEEE Transactions on Robotics & Automation, 13(6):873-880, December 1997.

883
K. Shoemake.
Uniform random rotations.
In D. Kirk, editor, Graphics Gems III, pages 124-132. Academic, New York, 1992.

884
R. Sim and G. Dudek.
Learning generative models of scene features.
In Proceedings IEEE Conference on Computer Vision and Pattern Recognition, pages 920-929, 2001.

885
T. Siméon, J.-P. Laumond, and C. Nissoux.
Visibility based probabilistic roadmaps for motion planning.
Advanced Robotics, 14(6), 2000.

886
T. Siméon, S. Leroy, and J.-P. Laumond.
Path coordination for multiple mobile robots: A resolution complete algorithm.
IEEE Transactions on Robotics & Automation, 18(1), February 2002.

887
R. Simmons, R. Goodwin, K. Haigh, S. Koenig, and J. O'Sullivan.
A layered architecture for office delivery robots.
In Proceedings First International Conference on Autonomous Agents, Marina del Rey, CA, 1997.

888
R. Simmons and S. Koenig.
Probabilistic robot navigation in partially observable environments.
In Proceedings International Joint Conference on Artificial Intelligence, pages 1080-1087, 1995.

889
B. Simov, S. M. LaValle, and G. Slutzki.
A complete pursuit-evasion algorithm for two pursuers using beam detection.
In Proceedings IEEE International Conference on Robotics and Automation, pages 618-623, 2002.

890
B. Simov, G. Slutzki, and S. M. LaValle.
Pursuit-evasion using beam detection.
In Proceedings IEEE International Conference on Robotics and Automation, 2000.

891
M. Sipser.
Introduction to the Theory of Computation.
PWS, Boston, MA, 1997.

892
D. Sleator and R. Tarjan.
Amortized efficiency of list update and paging rules.
Communications of the ACM, 28(2):202-208, 1985.

893
I. H. Sloan and S. Joe.
Lattice Methods for Multiple Integration.
Oxford Science, Englewood Cliffs, NJ, 1994.

894
J.-J. E. Slotine and H. S. Yang.
Improving the efficiency of time-optimal path-following algorithms.
IEEE Transactions on Robotics & Automation, 5(1):118-124, 1989.

895
W. D. Smart and L. P. Kaelbling.
Practical reinforcement learning in continuous spaces.
In Proceedings International Conference on Machine Learning, 2000.

896
D. Smith, J. Frank, and A. Jónsson.
Bridging the gap between planning and scheduling.
Knowledge Engineering Review, 15(1):47-83, 2000.

897
R. C. Smith and P. Cheeseman.
On the representation and estimation of spatial uncertainty.
International Journal of Robotics Research, 5(4):56-68, 1986.

898
S. J. J. Smith, D. S. Nau, and T. Throop.
Computer bridge: A big win for AI planning.
AI Magazine, 19(2):93-105, 1998.

899
E. J. Sondik.
The optimal control of partially observable Markov processes over the infinite horizon: Discounted costs.
Operations Research, 9(2):149-168, 1978.

900
G. Song and N. M. Amato.
Using motion planning to study protein folding pathways.
Journal of Computational Biology, 26(2):282-304, 2002.

901
E. Sontag.
Gradient technique for systems with no drift: A classical idea revisited.
In Proceedings IEEE Conference Decision & Control, pages 2706-2711, December 1993.

902
O. J. Sordalen.
Conversion of a car with $ n$ trailers into a chained form.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1382-1387, 1993.

903
P. Souères and J.-D. Boissonnat.
Optimal trajectories for nonholonomic mobile robots.
In J.-P. Laumond, editor, Robot Motion Planning and Control, pages 93-169. Springer-Verlag, Berlin, 1998.

904
P. Souères and J.-P. Laumond.
Shortest paths synthesis for a car-like robot.
In IEEE Transactions on Automatic Control, pages 672-688, 1996.

905
R. Spence and S. A. Hutchinson.
Dealing with unexpected moving obstacles by integrating potential field planning with inverse dynamics control.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1485-1490, 1992.

906
M. Spivak.
Differential Geometry.
Publish or Perish, Houston, TX, 1979.

907
M. W. Spong, S. Hutchinson, and M. Vidyasagar.
Robot Modeling and Control.
Wiley, New York, 2005.

908
R. L Sproull.
Refinements to nearest-neighbor searching in k-dimensional trees.
Algorithmica, 6:579-589, 1991.

909
W. Stadler.
Fundamentals of multicriteria optimization.
In W. Stadler, editor, Multicriteria Optimization in Engineering and in the Sciences, pages 1-25. Plenum Press, New York, 1988.

910
H. Stark and J. W. Woods.
Probability, Random Processes, and Estimation Theory for Engineers.
Prentice-Hall, Englewood Cliffs, NJ, 1986.

911
L. A. Steen and J. A. Seebach Jr.
Counterexamples in Topology.
Dover, New York, 1996.

912
R. F. Stengel.
Optimal Control and Estimation.
Dover, New York, 1994.

913
A. Stentz.
Optimal and efficient path planning for partially-known environments.
In Proceedings IEEE International Conference on Robotics & Automation, pages 3310-3317, 1994.

914
D. Stewart.
A platform with six degrees of freedom.
In Institution of Mechanical Engineers, Proceedings 1965-66, 180 Part 1, pages 371-386, 1966.

915
M. Stilman and J. J. Kuffner.
Navigation among movable obstacles: Real-time reasoning in complex environments.
In Proceedings 2004 IEEE International Conference on Humanoid Robotics (Humanoids'04), 2004.

916
D. Stipanovic, I. Hwang, and C. J. Tomlin.
Computation of an overapproximation of the backward reachable set using subsystem level set functions, dynamics of continuous, discrete, and impulsive systems.
Series A: Mathematical Analysis, 11:399-411, 2004.

917
P. D. Straffin.
Game Theory and Strategy.
Mathematical Association of America, Washington, DC, 1993.

918
M. Strandberg.
Augmenting RRT-planners with local trees.
In Proceedings IEEE International Conference on Robotics & Automation, pages 3258-3262, 2004.

919
M. Strandberg.
Robot Path Planning: An Object-Oriented Approach.
PhD thesis, Royal Institute of Technology (KTH), Stockholm, Sweden, 2004.

920
A. Sudsang, J. Ponce, and N. Srinivasa.
Grasping and in-hand manipulation: Geometry and algorithms.
Algorithmica, 26:466-493, 2000.

921
A. Sudsang, F. Rothganger, and J. Ponce.
Motion planning for disc-shaped robots pushing a polygonal object in the plane.
IEEE Transactions on Robotics & Automation, 18(4):550-562, 2002.

922
A. G. Sukharev.
Optimal strategies of the search for an extremum.
U.S.S.R. Computational Mathematics and Mathematical Physics, 11(4), 1971.
Translated from Russian, Zh. Vychisl. Mat. i Mat. Fiz., 11, 4, 910-924, 1971.

923
H. Sussmann and G. Tang.
Shortest paths for the Reeds-Shepp car: A worked out example of the use of geometric techniques in nonlinear optimal control.
Technical Report SYNCON 91-10, Dept. of Mathematics, Rutgers University, Piscataway, NJ, 1991.

924
H. J. Sussmann.
A sufficient condition for local controllability.
SIAM Journal on Control & Optimization, 16(5):790-802, 1978.

925
H. J. Sussmann.
A general theorem on local controllability.
SIAM Journal on Control & Optimization, 25(1):158-194, 1987.

926
H. J. Sussmann.
A continuation method for nonholonomic path-finding problems.
In Proceedings IEEE Conference Decision & Control, pages 2717-2723, December 1993.

927
H. J. Sussmann.
A very non-smooth maximum principle with state constraints.
In Proceedings IEEE Conference Decision & Control, pages 917-922, December 2005.

928
K. Sutner and W. Maass.
Motion planning among time dependent obstacles.
Acta Informatica, 26:93-122, 1988.

929
R. S. Sutton.
Learning to predict by the methods of temporal differences.
Machine Learning, 3:9-44, 1988.

930
R. S. Sutton and A. G. Barto.
Reinforcement Learning: An Introduction.
MIT Press, Cambridge, MA, 1998.

931
I. Suzuki, Y. Tazoe, M. Yamashita, and T. Kameda.
Searching a polygonal region from the boundary.
International Journal on Computational Geometry & Applications, 11(5):529-553, 2001.

932
I. Suzuki and M. Yamashita.
Searching for a mobile intruder in a polygonal region.
SIAM Journal on Computing, 21(5):863-888, October 1992.

933
I. Suzuki, M. Yamashita, H. Umemoto, and T. Kameda.
Bushiness and a tight worst-case upper bound on the search number of a simple polygon.
Information Processing Letters, 66:49-52, 1998.

934
P. Svestka and M. H. Overmars.
Coordinated motion planning for multiple car-like robots using probabilistic roadmaps.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1631-1636, 1995.

935
H. Takeda, C. Facchinetti, and J.-C. Latombe.
Planning the motions of a mobile robot in a sensory uncertainty field.
IEEE Transactions Pattern Analysis Machine Intelligence, 16(10):1002-1017, October 1994.

936
H. Takeda and J.-C. Latombe.
Sensory uncertainty field for mobile robot navigation.
In Proceedings IEEE International Conference on Robotics & Automation, pages 2465-2472, Nice, France, May 1992.

937
S. Tezuka.
Uniform Random Numbers: Theory and Practice.
Kluwer, Boston, MA, 1995.

938
S. Tezuka.
Quasi-Monte Carlo: The discrepancy between theory and practice.
In K.-T. Fang, F. J. Hickernell, and H. Niederreiter, editors, Monte Carlo and Quasi-Monte Carlo Methods 2000, pages 124-140. Springer-Verlag, Berlin, 2002.

939
M. Thorup.
Undirected single source shortest paths in linear time.
In Proceedings IEEE Symposium on Foundations of Computer Science, pages 12-21, 1997.

940
S. Thrun.
Probabilistic algorithms in robotics.
AI Magazine, 21(4):93-109, 2000.

941
S. Thrun, W. Burgard, and D. Fox.
A probabilistic approach to concurrent mapping and localization for mobile robots.
Machine Learning, 31(5):1-25, April 1998.

942
S. Thrun, W. Burgard, and D. Fox.
Probabilistic Robotics.
MIT Press, Cambridge, MA, 2005.

943
B. Tovar, L. Guilamo, and S. M. LaValle.
Gap navigation trees: A minimal representation for visibility-based tasks.
In Proceedings Workshop on Algorithmic Foundations of Robotics, pages 11-26, 2004.

944
B. Tovar, S. M. LaValle, and R. Murrieta.
Locally-optimal navigation in multiply-connected environments without geometric maps.
In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.

945
B. Tovar, S. M. LaValle, and R. Murrieta.
Optimal navigation and object finding without geometric maps or localization.
In Proceedings IEEE International Conference on Robotics and Automation, pages 464-470, 2003.

946
J. N. Tsitsiklis.
Efficient algorithms for globally optimal trajectories.
IEEE Transactions on Automatic Control, 40(9):1528-1538, September 1995.

947
S. Udupa.
Collision Detection and Avoidance in Computer Controlled Manipulators.
PhD thesis, Dept. of Electrical Engineering, California Institute of Technology, 1977.

948
University of North Carolina.
PQP: A proximity query package.
GAMMA Research Group, Available from http://www.cs.unc.edu/$ \sim$geom/SSV/, 2005.

949
C. Urmson and R. Simmons.
Approaches for heuristically biasing RRT growth.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.

950
J. van den Berg and M. Overmars.
Roadmap-based motion planing in dynamic environments.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1598-1605, 2004.

951
J. van den Berg and M. Overmars.
Prioritized motion planning for multiple robots.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2217-2222, 2005.

952
J. G. van der Corput.
Verteilungsfunktionen I.
Akademie van Wetenschappen, 38:813-821, 1935.

953
D. Vanderpooten.
Multiobjective programming: Basic concepts and approaches.
In R. Slowinski and J. Teghem, editors, Stochastic vs. Fuzzy Approaches to Multiobjective Mathematical Programming under Uncertainty, pages 7-22. Kluwer, Boston, MA, 1990.

954
G. Vegter.
Computational topology.
In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, 2nd Ed., pages 719-742. Chapman and Hall/CRC Press, New York, 2004.

955
M. Vendittelli and J.-P. Laumond.
Visible positions for a car-like robot amidst obstacles.
In J.-P. Laumond and M. H. Overmars, editors, Algorithms for Robotic Motion and Manipulation, pages 213-228. A.K. Peters, Wellesley, MA, 1997.

956
J. von Neumann.
Zur Theorie der Gesellschaftsspiele.
Mathematische Annalen, 100:295-320, 1928.

957
J. von Neumann and O. Morgenstern.
Theory of Games and Economic Behavior.
Princeton University Press, Princeton, NJ, 1944.

958
G. Walker and D. Walker.
The Official Rock Paper Scissors Strategy Guide.
Fireside, 2004.

959
X. Wang and F. J. Hickernell.
An historical overview of lattice point sets.
In K.-T. Fang, F. J. Hickernell, and H. Niederreiter, editors, Monte Carlo and Quasi-Monte Carlo Methods 2000, pages 158-167. Springer-Verlag, Berlin, 2002.

960
F. W. Warner.
Foundations of Differentiable Manifolds and Lie Groups.
Springer-Verlag, Berlin, 1983.

961
D. S. Watkins.
Fundamentals of Matrix Computations, 2nd Ed.
Wiley, New York, 2002.

962
G. Weiss, C. Wetzler, and E. von Puttkamer.
Keeping track of position and orientation of moving indoor systems by correlation of range-finder scans.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 595-601, 1994.

963
D. Weld.
Recent advances in AI planning.
AI Magazine, 20(2), 1999.

964
J. T. Wen.
Control of nonholonomic systems.
In W. S. Levine, editor, The Control Handbook, pages 1359-1368. CRC Press, Boca Raton, FL, 1996.

965
H. Weyl.
Über die Gleichverteilung von Zahlen mod Eins.
Mathematische Annalen, 77:313-352, 1916.

966
D. Whitney.
Force feedback control of manipulator fine motions.
Transactions of the ASME, Journal of Dynamical Systems, Measurement, & Control, 99:91-97, 1977.

967
D. E. Whitney.
Real robots don't need jigs.
In Proceedings IEEE International Conference on Robotics & Automation, 1986.

968
H. Whitney.
Local properties of analytic varieties.
In S. Cairns, editor, Differential and Combinatorial Topology, pages 205-244. Princeton University Press, Princeton, NJ, 1965.

969
J. Wiegley, K. Goldberg, M. Peshkin, and M. Brokowski.
A complete algorithm for designing passive fences to orient parts.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1133-1139, 1996.

970
O. Wijk.
Triangulation-Based Fusion of Sonar Data with Application in Mobile Robot Mapping and Localization.
PhD thesis, Royal Institute of Technology (KTH), Stockholm, Sweden, 2001.

971
S. A. Wilmarth, N. M. Amato, and P. F. Stiller.
MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1024-1031, 1999.

972
R. Wilson, L. Kavraki, J.-C. Latombe, and T. Lozano-Pérez.
Two-handed assembly sequencing.
International Journal of Robotics Research, 14(4):335-350, 1995.

973
R. H. Wilson.
On Geometric Assembly Planning.
PhD thesis, Stanford University, Stanford, CA, March 1992.

974
R. H. Wilson and J.-C. Latombe.
Geometric reasoning about mechanical assembly.
Artificial Intelligence Journal, 71(2):371-396, 1994.

975
P. H. Winston.
Artificial Intelligence.
Addison-Wesley, Reading, MA, 1992.

976
S. C. Wong, L. Middleton, and B. A. MacDonald.
Performance metrics for robot coverage tasks.
In Proceedings Australasian Conference on Robotics and Automation, 2002.

977
C. F. J. Wu.
On the convergence properties of the EM algorithm.
The Annals of Statistics, 11(1):95-103, 1983.

978
L. Xu and M. I. Jordan.
On convergence properties of the EM algorithm for Gaussian mixtures.
Neural Computation, 8:129-151, 1996.

979
J. Yakey, S. M. LaValle, and L. E. Kavraki.
Randomized path planning for linkages with closed kinematic chains.
IEEE Transactions on Robotics and Automation, 17(6):951-958, December 2001.

980
K. Yamane, J. J. Kuffner, and J. K. Hodgins.
Synthesizing animations of human manipulation tasks.
In Proceedings ACM SIGGRAPH, 2004.

981
M. Yamashita, H. Umemoto, I. Suzuki, and T. Kameda.
Searching for a mobile intruder in a polygonal region by a group of mobile searchers.
Algorithmica, 31:208-236, 2001.

982
B. Yamauchi, A. Schultz, and W. Adams.
Mobile robot exploration and map-building with continuous localization.
In Proceedings IEEE International Conference on Robotics & Automation, pages 3715-3720, 2002.

983
L. Yang and S. M. LaValle.
The sampling-based neighborhood graph: A framework for planning and executing feedback motion strategies.
IEEE Transactions on Robotics and Automation, 20(3):419-432, June 2004.

984
Q. Yang.
Intelligent Planning.
Springer-Verlag, Berlin, 1997.

985
Y. Yavin and M. Pachter.
Pursuit-Evasion Differential Games.
Pergamon, Oxford, U.K., 1987.

986
A. Yershova, L. Jaillet, T. Simeon, and S. M. LaValle.
Dynamic-domain RRTs: Efficient exploration by controlling the sampling domain.
In Proceedings IEEE International Conference on Robotics and Automation, 2005.

987
A. Yershova and S. M. LaValle.
Deterministic sampling methods for spheres and SO(3).
In Proceedings IEEE International Conference on Robotics and Automation, 2004.

988
A. Yershova, B. Tovar, R. Ghrist, and S. M. LaValle.
Bitbots: Simple robots solving complex tasks.
In AAAI National Conference on Artificial Intelligence, 2005.

989
P. N. Yianilos.
Data structures and algorithms for nearest neighbor search in general metric spaces.
In ACM-SIAM Symposium on Discrete Algorithms, pages 311-321, 1993.

990
M. Yim.
Locomotion with a Unit-Modular Reconfigurable Robot.
PhD thesis, Stanford University, Stanford, CA, December 1994.
Stanford Technical Report STAN-CS-94-1536.

991
J. Yong.
On differential evasion games.
SIAM Journal on Control & Optimization, 26(1):1-22, January 1988.

992
J. Yong.
On differential pursuit games.
SIAM Journal on Control & Optimization, 26(2):478-495, March 1988.

993
J. Yong.
A zero-sum differential game in a finite duration with switching strategies.
SIAM Journal on Control & Optimization, 28(5):1234-1250, September 1990.

994
T. Yoshikawa.
Foundations of Robotics: Analysis and Control.
MIT Press, Cambridge, MA, 1990.

995
Y. Yu and K. Gupta.
On sensor-based roadmap: A framework for motion planning for a manipulator arm in unknown environments.
In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1919-1924, 1998.

996
J. Zabczyk.
Some comments on stabilizability.
Applied Mathematics and Optimization, 19(1):1-9, 1989.

997
L. S. Zaremba.
Differential games reducible to optimal control problems.
In Proceedings IEEE Conference Decision & Control, pages 2449-2450, Tampa, FL, December 1989.

998
M. Zefran and J. Burdick.
Stabilization of systems with changing dynamics by means of switching.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1090-1095, 1998.

999
M. Zefran, J. Desai, and V. Kumar.
Continuous motion plans for robotic systems with changing dynamic behavior.
In Proceedings IEEE International Conference on Robotics & Automation, 1996.

1000
M. I. Zelikin and V. F. Borisov.
Theory of Chattering Control.
Birkhäuser, Boston, MA, 1994.

1001
M. Zhang, R. A. White, L. Wang, R. N. Goldman, L. E. Kavraki, and B. Hassett.
Improving conformational searches by geometric screening.
Bioinformatics, 21(5):624-630, 2005.

1002
N. L. Zhang and W. Zhang.
Speeding up the convergence of value iteration in partially observable Markov decision processes.
Journal of Artificial Intelligence Research, 14:29-51, 2001.

1003
R. Zhou and E. A. Hansen.
An improved grid-based approximation algorithm for POMDPs.
In Proceedings International Joint Conference on Artificial Intelligence, 2001.

1004
Y. Zhou and G. S. Chirikjian.
Probabilistic models of dead-reckoning error in nonholonomic mobile robots.
In Proceedings IEEE International Conference on Robotics & Automation, pages 1594-1599, 2003.

1005
S. Zionts.
Multiple criteria mathematical programming: An overview and several approaches.
In P. Serafini, editor, Mathematics of Multi-Objective Optimization, pages 227-273. Springer-Verlag, Berlin, 1985.



Steven M LaValle 2012-04-20