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