% The following LaTeX/BibTeX bibliography file contains all references % cited in Planning Algorithms, Steven M. LaValle, Cambridge University % Press, 2006. The book is available for free downloading at: % % http://planning.cs.uiuc.edu/ % % The original reference list was created by Steve LaValle: % http://msl.cs.uiuc.edu/~lavalle/ % % This file was substantially corrected and reformatted by Jason O'Kane: % http://msl.cs.uiuc.edu/~jokane/ % % 19 March 2006 % % Entry for the book itself @book{Lav06, author = {S. M. LaValle}, title = {Planning Algorithms}, publisher = {Cambridge University Press}, address = {Cambridge, U.K.}, note = {Available at http://planning.cs.uiuc.edu/}, year = {2006} } % References from the book @inproceedings{AarKraChr04, author = {D. Aarno and D. Kragic and H. I. Christensen}, title = {Artificial Potential Biased Probabilistic Roadmap Method}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2004} } @article{Abg96, author = {R. Abgrall}, title = {Numerical discretization of the first-order {Hamilton-Jacobi} equation on triangular meshes}, journal = {Communications on Pure and Applied Mathematics}, volume = {49}, number = {12}, pages = {1339--1373}, month = dec, year = {1996} } @book{AbrMar02, author = {R. Abraham and J. Marsden}, title = {Foundations of Mechanics}, publisher = {Addison-Wesley}, address = {Reading, MA}, year = {2002} } @book{AbrMarRat88, author = {R. Abraham and J. Marsden and T. Ratiu}, title = {Manifolds, Tensor Analysis, and Applications, 2nd Ed.}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1988} } @article{AbrGhr02, author = {A. Abrams and R. Ghrist}, title = {Finding Topology in a Factory: {C}onfiguration Spaces}, journal = {The American Mathematics Monthly}, volume = {109}, pages = {140--150}, month = feb, year = {2002} } @inproceedings{AcaCho01b, author = {E. U. Acar and H. Choset}, title = {Complete Sensor-based Coverage with Extended-range Detectors: A Hierarchical Decomposition in Terms of Critical Points and {Voronoi} Diagrams}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2001} } @inproceedings{AcaCho01a, author = {E. U. Acar and H. Choset}, title = {Robust Sensor-based Coverage of Unstructured Environments}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2001} } @book{Ada94, author = {C. C. Adams}, title = {The Knot Book: {A}n Elementary Introduction to the Mathematical Theory of Knots}, publisher = {W. H. Freeman}, address = {New York}, year = {1994} } @inproceedings{AgaDebHalSha96, author = {P. Agarwal and M. de Berg and D. Halperin and M. Sharir}, title = {Efficient generation of $k$-directional assembly sequences}, booktitle = {ACM Symposium on Discrete Algorithms}, pages = {122--131}, year = {1996} } @incollection{AgaAmeAroSha96, author = {P. K. Agarwal and N. Amenta and B. Aronov and M. Sharir}, title = {Largest placements and motion planning of a convex polygon}, booktitle = {Robotics: The Algorithmic Perspective}, editor = {J.-P. Laumond and M. Overmars}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1996} } @article{AgaAroSha99, author = {P. K. Agarwal and B. Aronov and M. Sharir}, title = {Motion Planning for a Convex Polygon in a Polygonal Environment}, journal = {Discrete and Computational Geometry}, volume = {22}, pages = {201--221}, year = {1999} } @inproceedings{AgaLatMotRag97, author = {P. K. Agarwal and J.-C. Latombe and R. Motwani and P. Raghavan}, title = {Nonholonomic Path Planning for Pushing a Disk Among Obstacles}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {}, year = {1997} } @inproceedings{AgaRagTam95, author = {P. K. Agarwal and P. Raghavan and H.Tamaki}, title = {Motion Planning for a Steering Constrained Robot through Moderate Obstacles}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {}, year = {1995} } @article{AkeHuaLynMas00, author = {S. Akella and W. H. Huang and K. M. Lynch and M. T. Mason}, title = {Parts Feeding on a conveyor with a One Joint Robot}, journal = {Algorithmica}, volume = {26}, number = {3/4}, pages = {313--344}, month = {March/April}, year = {2000} } @inproceedings{AkeHut02, author = {S. Akella and S. Hutchinson}, title = {Coordinating the Motions of Multiple Robots with Specified Trajectories}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {624--631}, year = {2002} } @incollection{AlaLauSim96, author = {R. Alami and J.-P. Laumond and T. Sim\'{e}on}, title = {Two manipulation planning algorithms}, booktitle = {Algorithms for Robotic Motion and Manipulation}, editor = {J.-P. Laumond and M. Overmars}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1997} } @inproceedings{AlaSimLau89, author = {R. Alami and T. Sim\'{e}on and J.-P. Laumond}, title = {A Geometrical Approach to Planning Manipulation Tasks}, booktitle = {Proceedings International Symposium on Robotics Research}, pages = {113--119}, year = {1989} } @book{AllGeo90, author = {G. Allgower and K. Georg}, title = {Numerical Continuation Methods}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1990} } @book{Alp04, author = {E. Alpaydin}, title = {Machine Learning}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {2004} } @inproceedings{AltFleKauMehNahSchUhr90, author = {H. Alt and R. Fleischer and M. Kaufmann and K. Mehlhorn and S. {N\"aher} and S. Schirra and C. Uhrig}, title = {Approximate motion planning and the complexity of the boundary of the union of simple geometric figures}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {281--289}, year = {1990} } @inproceedings{AmaBayDalJonVal98b, author = {N. M. Amato and O. B. Bayazit and L. K. Dale and C. Jones and D. Vallejo}, title = {Choosing Good Distance Metrics and Local Planners for Probabilistic Roadmap Methods}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {630--637}, year = {1998} } @inproceedings{AmaBayDalJonVal98, author = {N. M. Amato and O. B. Bayazit and L. K. Dale and C. Jones and D. Vallejo}, title = {{OBPRM}: An Obstacle-Based {PRM} for {3D} Workspaces}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, pages = {155--168}, year = {1998} } @article{AmaBayDalJonVal00, author = {N. M. Amato and O. B. Bayazit and L. K. Dale and C. Jones and D. Vallejo}, title = {Choosing Good Distance Metrics and Local Planners for Probabilistic Roadmap Methods}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {16}, number = {4}, pages = {442--447}, month = aug, year = {2000} } @inproceedings{AmaDilSon02, author = {N. M. Amato and K. A. Dill and G. Song}, title = {Using Motion Planning to Map Protein Folding Landscapes and Analyze Folding Kinetics of Known Native Structures}, booktitle = {Proceedings 6th ACM International Conference on Computational Molecular Biology (RECOMB)}, pages = {2--11}, year = {2002} } @article{AmaSon02, author = {N. M. Amato and G. Song}, title = {Using Motion Planning to Study Protein Folding Pathways}, journal = {Journal of Computational Biology}, volume = {9}, number = {2}, pages = {149--168}, year = {2002} } @inproceedings{AmaWu96, author = {N. M. Amato and Y. Wu}, title = {A Randomized Roadmap Method for Path and Manipulation Planning}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {113--120}, year = {1996} } @article{AncBre99, author = {F. Ancona and A. Bressan}, title = {Patchy vector fields and asymptotic stabilization}, journal = {ESAIM-Control, Optimisation and Calculus of Variations}, volume = {4}, pages = {445--471}, year = {1999} } @book{AndMoo90, author = {B. D. Anderson and J. B. Moore}, title = {Optimal Control: Linear-Quadratic Methods}, publisher = {Prentice-Hall}, address = {Englewood Cliffs, NJ}, year = {1990} } @book{Ang82, author = {J. Angeles}, title = {Spatial Kinematic Chains. Analysis, Synthesis, and Optimisation}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1982} } @book{Ang03, author = {J. Angeles}, title = {Fundamentals of Robotic Mechanical Systems: {T}heory, Methods, and Algorithms}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2003} } @article{AniHamHu03, author = {D. A. Anisi and J. Hamberg and X. Hu}, title = {Nearly time-optimal paths for a ground vehicle}, journal = {Journal of Control Theory and Applications}, month = nov, year = {2003} } @inproceedings{AnsOweLamKav00, author = {E. Anshelevich and S. Owens and F. Lamiraux and L. E. Kavraki}, title = {Deformable volumes in path planning applications}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2290--2295}, year = {2000} } @article{ApaBruGueHsuLatVar03, author = {M. Apaydin and D. Brutlag and C. Guestrin and D. Hsu J.-C. Latombe and C. Varm}, title = {Stochastic roadmap simulation: {A}n efficient representation and algorithm for analyzing molecular motion}, journal = {Journal of Computational Biology}, volume = {10}, pages = {257--281}, year = {2003} } @incollection{ArdSko91, author = {M. D. Ardema and J. M. Skowronski}, title = {Dynamic Game Applied to Coordination Control of Two Arm Robotic System}, booktitle = {Differential Games -- Developments in Modelling and Computation}, pages = {118--130}, editor = {R. P. {H\"{a}m\"{a}l\"{a}inen} and H. K. Ehtamo}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1991} } @inproceedings{AriFor02, author = {O. Arikan and D. Forsyth}, title = {Interactive Motion Generation from Examples}, booktitle = {Proceedings ACM SIGGRAPH}, year = {2002} } @article{ArkHas94, author = {E. M. Arkin and R. Hassin}, title = {Approximation algorithms for the geometric covering traveling salesman problem}, journal = {Discrete Applied Mathematics}, volume = {55}, pages = {194--218}, year = {1994} } @inproceedings{ArmKhaBur86, author = {B. Armstrong and O. Khatib and J. Burdick}, title = {The explicit dynamic model and inertial parameters of the {Puma} 560 arm}, booktitle = {Proceedings IEEE International Conference on Systems, Man, \& Cyberetics}, pages = {510--518}, year = {1986} } @book{Arm83, author = {M. A. Armstrong}, title = {Basic Topology}, publisher = {Springer-Verlag}, address = {New York}, year = {1983} } @book{Arn89, author = {V. I. Arnold}, title = {Mathematical Methods of Classical Mechanics, 2nd Ed.}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1989} } @article{Arn88, author = {D. S. Arnon}, title = {Geometric Reasoning with Logic and Algebra}, journal = {Artificial Intelligence Journal}, volume = {37}, number = {1-3}, pages = {37--60}, year = {1988} } @article{AroDebVanSveVle99, author = {B. Aronov and M. de Berg and A. F. van der Stappen and P. Svestka and J. Vleugels}, title = {Motion Planning for Multiple Robots}, journal = {Discrete and Computational Geometry}, volume = {22}, pages = {505--525}, year = {1999} } @article{AroSha97, author = {B. Aronov and M. Sharir}, title = {On Translational Motion Planning of a Convex Polyhedron in 3-Space}, journal = {SIAM Journal on Computing}, volume = {26}, number = {6}, pages = {1875--1803}, month = dec, year = {1997} } @article{ArrTomJenSie01, author = {K. Arras and N. Tomatis and B. Jensen and R. Siegwart}, title = {Multisensor on-the-fly localization: {P}recision and reliability for applications}, journal = {Robotics and Autonomous Systems}, volume = {34}, number = {2-3}, pages = {131--143}, year = {2001} } @book{ArrPla92, author = {D. K. Arrowsmith and C. M. Place}, title = {Dynamical Systems: {D}ifferential Equations, Maps, and Chaotic Behaviour}, publisher = {Chapman \& Hall/CRC}, address = {New York}, year = {1992} } @article{AruMasGorCla02, author = {S. Arulampalam and S. Maskell and N. Gordon and T. Clapp}, title = {A tutorial on particle filters for on-line non-linear/non-{G}aussian {B}ayesian tracking}, journal = {IEEE Transactions on Signal Processing}, volume = {50}, number = {2}, pages = {174--188}, year = {2002} } @incollection{Arv92, author = {J. Arvo}, title = {Fast Random Rotation Matrices}, booktitle = {Graphics Gems III}, pages = {117--120}, editor = {D. Kirk}, publisher = {Academic}, address = {New York}, year = {1992} } @inproceedings{AryMou93b, author = {S. Arya and D. M. Mount}, title = {Algorithms for fast vector quantization}, booktitle = {IEEE Data Compression Conference}, pages = {381--390}, month = mar, year = {1993} } @inproceedings{AryMou93, author = {S. Arya and D. M. Mount}, title = {Approximate nearest neighbor queries in fixed dimensions}, booktitle = {Proceedings ACM-SIAM Symposium on Discrete Algorithms}, pages = {271--280}, year = {1993} } @article{AryMouNetSilWu98, author = {S. Arya and D. M. Mount and N. S. Netanyahu and R. Silverman and A. Y. Wu}, title = {An optimal algorithm for approximate nearest neighbor searching}, journal = {Journal of the ACM}, volume = {45}, pages = {891--923}, year = {1998} } @book{Ash65, author = {R. B. Ash}, title = {Information Theory}, publisher = {Dover}, address = {New York}, year = {1990} } @book{AstHag95, author = {K. J. Astrom and T. Hagglund}, title = {PID Controllers: Theory, Design, and Tuning, 2nd Ed.}, publisher = {The Instrument, Systems, and Automation Society}, address = {Research Triangle Park, NC}, year = {1995} } @book{Atk78, author = {K. E. Atkinson}, title = {An Introduction to Numerical Analysis}, publisher = {Wiley}, address = {New York}, year = {1978} } @inproceedings{AtrLav02, author = {A. Atramentov and S. M. LaValle}, title = {Efficient Nearest Neighbor Searching for Motion Planning}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, pages = {632--637}, year = {2002} } @book{AubCel84, author = {J.-P. Aubin and A. Cellina}, title = {Differential Inclusions}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1984} } @article{Aur91, author = {F. Aurenhammer}, title = {Voronoi diagrams -- {A} survey of a fundamental geometric structure}, journal = {ACM Computing Surveys}, volume = {23}, pages = {345--405}, year = {1991} } @inproceedings{AvnBoiFav88, author = {F. Avnaim and J.-D. Boissonnat and B. Faverjon}, title = {A practical exact planning algorithm for polygonal objects amidst polygonal obstacles}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1656--1660}, year = {1988} } @inproceedings{Ban90, author = {J. {Ba\~non}}, title = {Implementation and Extension of the Ladder Algorithm}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1548--1553}, year = {1990} } @incollection{Bas91, author = {T. Ba\c{s}ar}, title = {Game Theory and ${H}^{\infty}$-Optimal Control: The Continuous-Time Case}, booktitle = {Differential Games -- Developments in Modelling and Computation}, pages = {171--186}, editor = {R. P. {H\"{a}m\"{a}l\"{a}inen} and H. K. Ehtamo}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1991} } @article{BasKum87, author = {T. Ba\c{s}ar and P. R. Kumar}, title = {On Worst Case Design Strategies}, journal = {Computers and Mathematics with Applications}, volume = {13}, number = {1-3}, pages = {239--245}, year = {1987} } @book{BasOls95, author = {T. Ba\c{s}ar and G. J. Olsder}, title = {Dynamic Noncooperative Game Theory, 2nd Ed.}, publisher = {Academic}, address = {London}, year = {1995} } @article{BaeCulRaw93, author = {R. A. Baeza and J. C. Culberson and G. J. E. Rawlins}, title = {Searching in the Plane}, journal = {Information and Computation}, volume = {106}, number = {2}, pages = {234--252}, year = {1993} } @inproceedings{Bag96, author = {B. Baginski}, title = {The ${Z}^3$ Method for Fast Path Planning in Dynamic Environments}, booktitle = {Proceedings IASTED Conference on Applications of Control and Robotics}, pages = {47--52}, year = {1996} } @phdthesis{Bag98, author = {B. Baginski}, title = {Motion Planning for Manipulators with Many Degrees of Freedom -- The BB-Method}, school = {Technical University of Munich}, department = {Informatics Department}, year = {1998} } @book{Bak02, author = {A. Baker}, title = {Matrix Groups}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2002} } @article{BalMas02, author = {D. J. Balkcom and M. T. Mason}, title = {Time Optimal Trajectories for Bounded Velocity Differential Drive Vehicles}, journal = {International Journal of Robotics Research}, volume = {21}, number = {3}, pages = {199--217}, year = {2002} } @inproceedings{BalMas04, author = {D. J. Balkcom and M. T. Mason}, title = {Introducing robotic origami folding}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2004} } @inproceedings{BanZhiWanZhaSmiAbi95, author = {J. E. Banta and Y. Zhien and X. Z. Wang and G. Zhang and M. T. Smith and M. A. Abidi}, title = {A ``Best-Next-View'' Algorithm for Three-Dimensional Scene Reconstruction Using Range Images}, booktitle = {Proceedings SPIE, vol. 2588}, pages = {418--29}, year = {1995} } @inproceedings{BarFer94, author = {J. Barraquand and P. Ferbach}, title = {A Penalty Function Method for Constrained Motion Planning}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1235--1242}, year = {1994} } @inproceedings{BarFer95, author = {J. Barraquand and P. Ferbach}, title = {Motion Planning with Uncertainty: {T}he Information Space Approach}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1341--1348}, year = {1995} } @incollection{BarKavLatLiMotRag96, author = {J. Barraquand and L. Kavraki and J.-C. Latombe and T.-Y. Li and R. Motwani and P. Raghavan}, title = {A Random Sampling Scheme for Robot Path Planning}, booktitle = {Proceedings International Symposium on Robotics Research}, pages = {249--264}, editor = {G. Giralt and G. Hirzinger}, publisher = {Springer-Verlag}, address = {New York}, year = {1996} } @inproceedings{BarLat90, author = {J. Barraquand and J.-C. Latombe}, title = {A {Monte-Carlo} Algorithm for Path Planning With Many Degrees of Freedom}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1712--1717}, year = {1990} } @inproceedings{BarLat91, author = {J. Barraquand and J.-C. Latombe}, title = {Nonholonomic Multibody Mobile Robots: Controllability and Motion Planning in the Presence of Obstacles}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2328--2335}, year = {1991} } @article{BarLat91b, author = {J. Barraquand and J.-C. Latombe}, title = {Robot Motion Planning: A Distributed Representation Approach}, journal = {International Journal of Robotics Research}, volume = {10}, number = {6}, pages = {628--649}, month = dec, year = {1991} } @article{BarLat93, author = {J. Barraquand and J.-C. Latombe}, title = {Nonholonomic Multibody Mobile Robots: Controllability and Motion Planning in the Presence of Obstacles}, journal = {Algorithmica}, volume = {10}, pages = {121--155}, year = {1993} } @book{BarSut98, author = {R. S. Sutton and A. G. Barto}, title = {Reinforcement Learning: An Introduction}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {1998} } @incollection{BarSutWat90, author = {A. G. Barto and R. S. Sutton and C. J. C. H. Watkins}, title = {Learning and Sequential Decision Making}, booktitle = {Learning and Computational Neuroscience: Foundations of Adaptive Networks}, pages = {539--602}, editor = {M. Gabriel and J.W. Moore}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {1990} } @inproceedings{BasGuiHsuNgu01, author = {J. Basch and L. J. Guibas and D. Hsu and A. T. Nguyen}, title = {Disconnection proofs for motion planning}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1765--1772}, year = {2001} } @article{BasPolRoy99, author = {S. Basu and R. Pollack and M. F. Roy}, title = {Computing Roadmaps of Semi-Algebraic Sets on a Variety}, journal = {Journal of the American Society of Mathematics}, volume = {3}, number = {1}, pages = {55--82}, year = {1999} } @book{BasPolRoy03, author = {S. Basu and R. Pollack and M.-F. Roy}, title = {Algorithms in Real Algebraic Geometry}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2003} } @incollection{BasDea90, author = {K. Basye and T. Dean}, title = {Map Learning with Indistinguishable Locations}, booktitle = {Uncertainty in Artificial Intelligence 5}, pages = {331--340}, editor = {M. Henrion and L. N. Kanal and J. F. Lemmer}, publisher = {Elsevier Science}, address = {New York}, year = {1990} } @article{BasDeaKirLej92, author = {K. Basye and T. Dean and J. Kirman and M. Lejter}, title = {A Decision-Theoretic Approach to Planning, Perception, and Control}, journal = {IEEE Expert}, volume = {7}, number = {4}, pages = {58--65}, month = aug, year = {1992} } @article{Bay63, author = {T. Bayes}, title = {An Essay Towards Solving a Problem in the Doctrine of Chances}, journal = {Philosophical Transactions of the Royal Society of London}, volume = {53}, year = {1763} } @inproceedings{BecGonLatTom95, author = {C. Becker and H. Gonz\'alez-Ba{\~{n}}os and J.-C. Latombe and C. Tomasi}, title = {An Intelligent Observer}, booktitle = {Preprints of International Symposium on Experimental Robotics}, pages = {94--99}, year = {1995} } @inproceedings{BekCheLadPlaKav03, author = {K. E. Bekris and B. Y. Chen and A. Ladd and E. Plaku and L. E. Kavraki}, title = {Multiple Query Probabilistic Roadmap Planning using Single Query Primitives}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2003} } @incollection{BelJeaRis98, author = {A. Bellaiche and F. Jean and J. J. Risler}, title = {Geometry of Nonholonomic Systems}, booktitle = {Robot Motion Planning and Control}, pages = {55--92}, editor = {J.-P. Laumond}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1998} } @book{Bel57, author = {R. E. Bellman}, title = {Dynamic Programming}, publisher = {Princeton University Press}, address = {Princeton, NJ}, year = {1957} } @book{BelDre62, author = {R. E. Bellman and S. E. Dreyfus}, title = {Applied Dynamic Programming}, publisher = {Princeton University Press}, address = {Princeton, NJ}, year = {1962} } @inproceedings{BelEstLauFer05, author = {I. Belousov and C. Esteves and J.-P. Laumond and E. Ferre}, title = {Motion Planning for Large Space Manipulators with Complicated Dynamics}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2005} } @inproceedings{BenFerRonSahVad98, author = {M. A. Bender and A. Fernandez and D. Ron and A. Sahai and S. Vadhan}, title = {The Power of a Pebble: Exploring and Mapping Directed Graphs}, booktitle = {Proceedings Annual Symposium on Foundations of Computer Science}, year = {1998} } @book{BenMetPro90, author = {A. Benveniste and M. Metivier and P. Prourier}, title = {Adaptive Algorithms and Stochastic Approximations}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1990} } @book{Ber80, author = {J. O. Berger}, title = {Statistical Decision Theory}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1980} } @incollection{Ber04, author = {M. Bern}, title = {Triangulations and Mesh Generation}, booktitle = {Handbook of Discrete and Computational Geometry, 2nd Ed.}, pages = {563--582}, editor = {J. E. Goodman and J. O'Rourke}, publisher = {Chapman and Hall/CRC Press}, address = {New York}, year = {2004} } @inproceedings{BerShaVan89, author = {J. Bernard and J. Shannan and M. Vanderploeg}, title = {Vehicle Rollover on Smooth Surfaces}, booktitle = {Proceedings SAE Passenger Car Meeting and Exposition}, address = {Dearborn, MI}, year = {1989} } @article{Ber75, author = {D. P. Bertsekas}, title = {Convergence in Discretization Procedures in Dynamic Programming}, journal = {IEEE Transactions on Automatic Control}, volume = {20}, number = {3}, pages = {415--419}, month = jun, year = {1975} } @book{Ber87, author = {D. P. Bertsekas}, title = {Dynamic Programming: Deterministic and Stochastic Models}, publisher = {Prentice-Hall}, address = {Englewood Cliffs, NJ}, year = {1987} } @book{Ber99, author = {D. P. Bertsekas}, title = {Nonlinear Programming}, publisher = {Athena Scientific}, address = {Belmont, MA}, year = {1999} } @book{Ber01, author = {D. P. Bertsekas}, title = {Dynamic Programming and Optimal Control, Vol. I, 2nd Ed.}, publisher = {Athena Scientific}, address = {Belmont, MA}, year = {2001} } @book{Ber01b, author = {D. P. Bertsekas}, title = {Dynamic Programming and Optimal Control, Vol. II, 2nd Ed.}, publisher = {Athena Scientific}, address = {Belmont, MA}, year = {2001} } @book{BerTsi96, author = {D. P. Bertsekas and J. N. Tsitsiklis}, title = {Neuro-Dynamic Programming}, publisher = {Athena Scientific}, address = {Belmont, MA}, year = {1996} } @article{Bet98, author = {J. T. Betts}, title = {Survey of Numerical Methods for Trajectory Optimization}, journal = {Journal of Guidance, Control, and Dynamics}, volume = {21}, number = {2}, pages = {193--207}, month = {March-April}, year = {1998} } @misc{BeyKakLan05, author = {A. Beygelzimer and S. M. Kakade and J. Langford}, title = {Cover Trees for Nearest Neighbor}, howpublished = {University of Pennsylvania, Available from {http://www.cis.upenn.edu/$\sim$skakade/papers/ml/cover\_tree.pdf}}, year = {2005} } @incollection{BhaFra04, author = {A. Bhatia and E. Frazzoli}, title = {Incremental Search Methods for Reachability Analysis of Continuous and Hybrid Systems}, booktitle = {Hybrid Systems: Computation and Control}, pages = {67--78}, editor = {R. Alur and G. J. Pappas}, publisher = {Springer-Verlag}, address = {Berlin}, note = {Lecture Notes in Computer Science, 2993}, year = {2004} } @inproceedings{BhaAgr00, author = {S. Bhattacharya and S. K. Agrawal}, title = {Design, Experiments and Motion Planning of a Spherical Rolling Robot}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1207--1212}, year = {2000} } @article{BicMarPic02, author = {A. Bicchi and A. Marigo and B. Piccoli}, title = {On the Reachability of Quantized Control Systems}, journal = {IEEE Transactions on Automatic Control}, volume = {47}, number = {4}, pages = {546--563}, month = apr, year = {2002} } @inproceedings{BicPraSas95, author = {A. Bicchi and D. Prattichizzo and S. Sastry}, title = {Planning motions of rolling surfaces}, booktitle = {Proceedings IEEE Conference Decision \& Control}, year = {1995} } @article{BieLee92, author = {Z. Bien and J. Lee}, title = {A Minimum-Time Trajectory Planning Method for Two Robots}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {8}, number = {3}, pages = {414--418}, month = jun, year = {1992} } @article{BieSey91, author = {D. Bienstock and P. Seymour}, title = {Monotonicity in Graph Searching}, journal = {Journal of Algorithms}, volume = {12}, pages = {239--245}, year = {1991} } @techreport{Bil97, author = {J. Bilmes}, title = {A Gentle Tutorial on the {EM} Algorithm and its Application to Parameter Estimation for {G}aussian Mixture and Hidden {M}arkov Models}, number = {ICSI-TR-97-021}, address = {Berkeley, CA}, institution = {International Computer Science Institute (ICSI)}, year = {1997} } @book{BisGol80, author = {R. L. Bishop and S. I. Goldberg}, title = {Tensor Analysis on Manifolds}, publisher = {Dover}, address = {New York}, year = {1980} } @article{Bla34, author = {H. S. Black}, title = {Stabilized Feedback Amplifiers}, journal = {Bell Systems Technical Journal}, volume = {13}, pages = {1--18}, year = {1934} } @book{BlaGir79, author = {D. Blackwell and M. A. Girshik}, title = {Theory of Games and Statistical Decisions}, publisher = {Dover}, address = {New York}, year = {1979} } @article{BliMccAkePon01, author = {S. Blind and C. McCullough and S. Akella and J. Ponce}, title = {Manipulating Parts with an Array of Pins: {A} Method and a Machine}, journal = {International Journal of Robotics Research}, volume = {20}, number = {10}, pages = {808--818}, month = dec, year = {2001} } @book{Blo77, author = {A. Bloch}, title = {Murphy's Law and Other Reasons Why Things Go Wrong}, publisher = {Price Stern Sloan Adult}, address = {New York}, year = {1977} } @book{Blo03, author = {A. M. Bloch}, title = {Nonholonomic Mechanics and Control}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2003} } @article{BloCro95, author = {A. M. Bloch and P. E. Crouch}, title = {Nonholonomic Control Systems on {R}iemannian Manifolds}, journal = {SIAM Journal on Control \& Optimization}, volume = {33}, pages = {126--148}, year = {1995} } @article{BloTsi00, author = {V. D. Blondel and J. N. Tsitsiklis}, title = {A Survey of Computational Complexity Results in Systems and Control}, journal = {Automatica}, volume = {36}, number = {9}, pages = {1249--1274}, month = sep, year = {2000} } @inproceedings{BluChaKarLanMeyMin03, author = {A. Blum and S. Chawla and D. Karger and T. Lane and A. Meyerson and M. Minkoff}, title = {Approximation Algorithms for Orienteering and Discounted-Reward {TSP}}, booktitle = {Proceedings IEEE Symposium on Foundations of Computer Science}, year = {2003} } @inproceedings{BluRagSch91, author = {A. Blum and P. Raghavan and B. Schieber}, title = {Navigating in Unfamiliar Geometric Terrains}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {494--504}, year = {1991} } @inproceedings{BluFur95, author = {A. L. Blum and M. L. Furst}, title = {Fast Planing Through Planning Graph Analysis}, booktitle = {Proceedings International Joint Conference on Artificial Intelligence}, pages = {1636--1642}, year = {1995} } @book{BluCucShuSma98, author = {L. Blum and F. Cucker and M. Schub abd S. Smale}, title = {Complexity and Real Computation}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1998} } @inproceedings{BluKoz78, author = {M. Blum and D. Kozen}, title = {On the power of the compass (or, why mazes are easier to search than graphs)}, booktitle = {Proceedings Annual Symposium on Foundations of Computer Science}, pages = {132--142}, year = {1978} } @article{Bob88, author = {J. E. Bobrow}, title = {Optimal Robot Path Planning Using the Minimum-Time Criterion}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {4}, number = {4}, pages = {443--450}, month = aug, year = {1988} } @article{BobDubGib85, author = {J. E. Bobrow and S. Dubowsky and J. S. Gibson}, title = {Time-optimal Control of Robotic Manipulators along Specified Paths}, journal = {International Journal of Robotics Research}, volume = {4}, number = {3}, pages = {3--17}, year = {1985} } @incollection{Bod69, author = {H. Bode}, title = {Feedback: The History of an Idea}, booktitle = {Selected Papers on Mathematical Trends in Control Theory}, pages = {106--123}, editor = {R. Bellman and R. Kalaba}, publisher = {Dover}, address = {New York}, year = {1969} } @inproceedings{Boh01, author = {R. Bohlin}, title = {Path Planning in Practice; Lazy Evaluation on a multi-resolution Grid}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2001} } @phdthesis{Boh02, author = {R. Bohlin}, title = {Robot Path Planning}, address = {Gothenburg, Sweden}, school = {Chalmers University}, department = {Industrial Mathematics, Department of Mathematics}, year = {2002} } @inproceedings{BohKav00, author = {R. Bohlin and L. Kavraki}, title = {Path Planning Using {Lazy PRM}}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2000} } @incollection{BohDonMac97, author = {K.-F. {B\"ohringer} and B. R. Donald and N. C. MacDonald}, title = {Upper and Lower Bounds for Programmable Vector Fields with Applications to {MEMS} and Vibratory Plate Parts Feeders}, booktitle = {Algorithms for Robotic Motion and Manipulation}, pages = {}, editor = {J.-P. Laumond and M. Overmars}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1997} } @article{BoiCerLeb94, author = {J.-D. Boissonnat and A. C\'er\'ezo and J. Leblond}, title = {Shortest paths of bounded curvature in the plane}, journal = {Journal of Intelligent and Robotic Systems}, volume = {11}, pages = {5--20}, year = {1994} } @inproceedings{BoiLaz96, author = {J.-D. Boissonnat and S. Lazard}, title = {A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {242--251}, year = {1996} } @book{BoiYvi98, author = {J.-D. Boissonnat and M. Yvinec}, title = {Algorithmic Geometry}, publisher = {Cambridge University Press}, address = {Cambridge, U.K.}, year = {1998} } @article{Bol66, author = {V. G. Boltyanskii}, title = {Sufficient conditions for optimality and the justification of the dynamic programming method}, journal = {SIAM Journal on Control}, volume = {4}, pages = {326--361}, year = {1966} } @misc{BooGol05, author = {G. Boo and K. Goldberg}, title = {Orienting Polygonal Parts without Sensors: {A}n Implementation in {J}ava}, howpublished = {Alpha Lab, UC Berkeley. Available from {http://www.ieor.berkeley.edu/$\sim$goldberg/feeder-S05/}}, year = {2005} } @inproceedings{BooOveVan99, author = {V. Boor and M. H. Overmars and A. F. van der Stappen}, title = {The {Gaussian} Sampling Strategy for Probabilistic Roadmap Planners}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1018--1023}, year = {1999} } @book{Boo03, author = {W. M. Boothby}, title = {An Introduction to Differentiable Manifolds and Riemannian Geometry. Revised 2nd Ed.}, publisher = {Academic}, address = {New York}, year = {2003} } @book{BorEveFen96, author = {J. Borenstein and B. Everett and L. Feng}, title = {Navigating Mobile Robots: {S}ystems and Techniques}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1996} } @article{BorMam02, author = {A. V. Borisov and I .S. Mamaev}, title = {On the History of the Development of Nonholonomic Dynamics}, journal = {Regular and Chaotic Dynamics}, volume = {7}, number = {1}, pages = {43--47}, year = {2002} } @inproceedings{BosLubMun92, author = {P. Bose and A. Lubiv and J. I. Munro}, title = {Efficient Visibility Queries in Simple Polygons}, booktitle = {Proceedings Canadian Conference on Computational Geometry}, pages = {23--28}, year = {1992} } @article{BraBorMit98, author = {M. S. Branicky and V. S. Borkar and S. K. Mitter}, title = {A unified framework for hybrid control: Model and optimal control theory}, journal = {IEEE Transactions on Automatic Control}, volume = {43}, number = {1}, pages = {31--45}, year = {1998} } @inproceedings{BraCurLevMor03, author = {M. S. Branicky and M. M. Curtiss and J. Levine and S. Morgan}, title = {{RRT}s for nonlinear, discrete, and hybrid planning and control}, booktitle = {Proceedings IEEE Conference Decision \& Control}, year = {2003} } @book{BriHae99, author = {M. Bridson and A. Haefliger}, title = {Metric Spaces of Non-Positive Curvature}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1999} } @inproceedings{Bri89, author = {A. Briggs}, title = {An Efficient Algorithm for One-step Compliant Motion Planning with Uncertainty}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, year = {1989} } @incollection{BriDon96, author = {A. J. Briggs and B. R. Donald}, title = {Robust Geometric Algorithms for Sensor Planning}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, editor = {J.-P. Laumond and M. Overmars}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1996} } @incollection{Bro81, author = {R. W. Brockett}, title = {Control theory and singular {R}iemannian geometry}, booktitle = {New Directions in Applied Mathematics}, pages = {11--27}, editor = {P. A. Fuhrman}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1981} } @incollection{Bro83b, author = {R. W. Brockett}, title = {Asymptotic stability and feedback stabilization}, booktitle = {Differential Geometric Control Theory}, pages = {181--191}, editor = {R. W. Brockett and R. S. Millman and H. J. Sussmann}, publisher = {{Birkh\"auser}}, address = {Boston, MA}, year = {1983} } @article{BroLoz85, author = {R. A. Brooks and T. Lozano-P\'erez}, title = {A Subdivision Algorithm in Configuration Space for Findpath with Rotation}, journal = {IEEE Transactions on Systems, Man, \& Cybernetics}, volume = {SMC-15}, number = {2}, pages = {224--233}, year = {1985} } @article{Bro88, author = {R. C. Brost}, title = {Automatic Grasp Planning in the Presence of Uncertainty}, journal = {International Journal of Robotics Research}, volume = {7}, number = {1}, pages = {3--17}, year = {1988} } @phdthesis{Bro91, author = {R. C. Brost}, title = {Analysis and Planning of Planar Manipulation Tasks}, number = {}, address = {Pittsburgh, PA}, school = {Carnegie Mellon University}, department = {Department of Computer Science}, month = {}, year = {1991} } @inproceedings{BroChr93, author = {R. C. Brost and A. D. Christiansen}, title = {Probabilistic Analysis of Manipulation Tasks: A Research Agenda}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, volume = {3}, pages = {549--556}, year = {1993} } @techreport{BroChr94, author = {R. C. Brost and A. D. Christiansen}, title = {Probabilistic Analysis of Manipulation Tasks: A Computational Framework}, number = {SAND92-2033}, institution = {Sandia National Laboratories, Albuquerque, NM}, month = jan, year = {1994} } @article{BroChr96, author = {R. C. Brost and A. D. Christiansen}, title = {Probabilistic Analysis of Manipulation Tasks: A Computational Framework}, journal = {International Journal of Robotics Research}, volume = {15}, number = {1}, pages = {1--23}, month = feb, year = {1996} } @inproceedings{BruVel02, author = {J. Bruce and M. Veloso}, title = {Real-Time Randomized Path Planning for Robot Navigation}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2002} } @book{BryHo75, author = {A. E. Bryson and Y.-C. Ho}, title = {Applied Optimal Control}, publisher = {Hemisphere Publishing Corp.}, address = {New York}, year = {1975} } @book{Buc02, author = {M. Buckland}, title = {AI Techniques for Game Programming}, publisher = {Premier Press}, address = {Portland, OR}, year = {2002} } @inproceedings{Buc89, author = {S. J. Buckley}, title = {Fast motion planning for multiple moving robots}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {322--326}, year = {1989} } @article{Bul01, author = {F. Bullo}, title = {Series Expansions for the Evolution of Mechanical Control Systems}, journal = {SIAM Journal on Control \& Optimization}, volume = {40}, number = {1}, pages = {166--190}, year = {2001} } @article{Bul02, author = {F. Bullo}, title = {Series Expansions for Analytic Systems Linear in Control}, journal = {Automatica}, volume = {38}, number = {9}, pages = {1425--1432}, month = sep, year = {2002} } @book{BulLew04, author = {F. Bullo and A. D. Lewis}, title = {Geometric Control of Mechanical Systems}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2004} } @article{BulLyn01, author = {F. Bullo and K. M. Lynch}, title = {Kinematic controllability for decoupled trajectory planning in underactuated mechanical systems}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {17}, number = {4}, pages = {402--412}, year = {2001} } @phdthesis{Bur88, author = {J. W. Burdick}, title = {Kinematic Analysis and Design of Redundant Manipulators}, address = {Stanford, CA}, school = {Stanford University}, department = {Department of Mechanical Engineering}, year = {1988} } @inproceedings{BurCreFoxHahLakSchSteThr98, author = {W. Burgard and A. B. Cremers and D. Fox and D. {H\"ahnel} and G. Lakemeyer and D. Schulz and W. Steiner and S. Thrun}, title = {The Interactive Museum Tour-Guide Robot}, booktitle = {Proceedings AAAI National Conference on Artificial Intelligence}, pages = {11--18}, year = {1998} } @techreport{BurLuWu99, author = {J. J. Burken and P. Lu and Z. Wu}, title = {Reconfigurable Flight Control Designs With Application to the {X}-33 Vehicle}, number = {TM-1999-206582}, address = {Washington, DC}, institution = {NASA}, year = {1999} } @inproceedings{BurBro05, author = {B. Burns and O. Brock}, title = {Sampling-Based Motion Planning Using Predictive Models}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2005} } @article{BurRizKod99, author = {R. R. Burridge and A. A. Rizzi and D. E. Koditschek}, title = {Sequential Composition of Dynamically Dexterous Robot Behaviors}, journal = {International Journal of Robotics Research}, volume = {18}, number = {6}, pages = {534--555}, year = {1999} } @article{BusTilSas95, author = {L. G. Bushnell and D. M. Tilbury and S. S. Sastry}, title = {Steering three-input nonholonomic systems: the fire truck example}, journal = {International Journal of Robotics Research}, volume = {14}, number = {4}, pages = {366--381}, year = {1995} } @inproceedings{ButRizHol99, author = {Z. J. Butler and A. A. Rizzi and R. L. Hollis}, title = {Contact sensor-based coverage of rectilinear environments}, booktitle = {IEEE Symposium on Intelligent Control}, year = {1999} } @article{ButRus03, author = {Z. J. Butler and D. Rus}, title = {Distributed Motion Planning for Modular Robots with Unit-Compressible Modules}, journal = {International Journal of Robotics Research}, volume = {22}, number = {9}, pages = {699--716}, year = {2003} } @inproceedings{CamGraAla04, author = {S. Cambon and F. Gravot and R. Alami}, title = {A Robot Task Planner and Merges Symbolic and Geometric Reasoning}, booktitle = {Proceedings European Conference on Artificial Intelligence}, year = {2004} } @article{Cam97, author = {S. Cameron}, title = {A Comparison of Two Fast Algorithms for Computing the Distance Between Convex Polyhedra}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {13}, number = {6}, pages = {915--920}, month = dec, year = {1997} } @incollection{CamFal96, author = {F. Camilli and M. Falcone}, title = {Approximation of optimal control problems with state constraints: {E}stimates and applications}, booktitle = {Nonsmooth Analysis and Geometric Methods in Deterministic Optimal Control}, pages = {23--57}, editor = {B. S. Mordukhovich and H. J. Sussmann}, publisher = {Springer-Verlag}, address = {Berlin}, note = {Mathematics and its Applications, Vol. 78}, year = {1996} } @article{Can88b, author = {J. Canny}, title = {Constructing Roadmaps of Semi-Algebraic Sets {I}}, journal = {Artificial Intelligence Journal}, volume = {37}, pages = {203--222}, year = {1988} } @article{Can93, author = {J. Canny}, title = {Computing roadmaps of general semi-algebraic sets}, journal = {The Computer Journal}, volume = {36}, number = {5}, pages = {504--514}, year = {1993} } @article{CanRegRei91, author = {J. Canny and A. Rege and J. Reif}, title = {An Exact Algorithm for Kinodynamic Planning in the Plane}, journal = {Discrete and Computational Geometry}, volume = {6}, pages = {461--484}, year = {1991} } @inproceedings{CanRei87, author = {J. Canny and J. Reif}, title = {New Lower Bound Techniques for Robot Motion Planning Problems}, booktitle = {Proceedings IEEE Symposium on Foundations of Computer Science}, pages = {49--60}, year = {1987} } @book{Can88, author = {J. F. Canny}, title = {The Complexity of Robot Motion Planning}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {1988} } @inproceedings{Can89, author = {J. F. Canny}, title = {On Computability of Fine Motion Plans}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {177--182}, year = {1989} } @inproceedings{CanGol94, author = {J. F. Canny and K. Y. Goldberg}, title = {{``RISC''} industrial robots: {R}ecent results and current trends}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1951--1958}, year = {1994} } @article{CanLin93, author = {J. F. Canny and M. Lin}, title = {An opportunistic global path planner}, journal = {Algorithmica}, volume = {10}, pages = {102--120}, year = {1993} } @inproceedings{CarPag02, author = {S. Carpin and E. Pagello}, title = {On Parallel {RRTs} for Multi-robot Systems}, booktitle = {Proceedings 8th Conference of the Italian Association for Artificial Intelligence}, pages = {834--841}, year = {2002} } @inproceedings{CarPil05, author = {S. Carpin and G. Pillonetto}, title = {Merging the adaptive random walks planner with the randomized potential field planner}, booktitle = {Proceedings IEEE International Workshop on Robot Motion and Control}, pages = {151--156}, year = {2005} } @article{CarPil05b, author = {S. Carpin and G. Pillonetto}, title = {Robot motion planning using adaptive random walks}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {21}, number = {1}, pages = {129--136}, year = {2005} } @phdthesis{Cas02, author = {A. Casal}, title = {Reconfiguration Planning for Modular Self-Reconfigurable Robots}, address = {Stanford, CA}, school = {Stanford University}, year = {2002} } @inproceedings{CasReg00, author = {S. Caselli and M. Reggiani}, title = {{ERPP:} {A}n Experience-based Randomized Path Planner}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2000} } @article{CasMonNeiTar99, author = {J. Castellanos and J. Montiel and J. Neira and J. Tard\'os}, title = {The {SPmap}: {A} probabilistic framework for simultaneous localization and mapping}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {15}, number = {5}, pages = {948--953}, year = {1999} } @inproceedings{ChaBolGinKum95, author = {D. Challou and D. Boley and M. Gini and V. Kumar}, title = {A Parallel Formulation of Informed Randomized Search for Robot Motion Planning Problems}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {709--714}, year = {1995} } @article{Cha83, author = {D. D. Champeaux}, title = {Bidirectional Heuristic Search Again}, journal = {Journal of the ACM}, volume = {30}, number = {1}, pages = {22--32}, month = jan, year = {1983} } @article{ChaSin77, author = {D. D. Champeaux and L. Sint}, title = {An Improved Bidirectional Heuristic Search Algorithm}, journal = {Journal of the ACM}, volume = {24}, number = {2}, pages = {177--191}, month = apr, year = {1977} } @inproceedings{ChaLi95, author = {H. Chang and T. Y. Li}, title = {Assembly Maintainability Study with Motion Planning}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1012--1019}, year = {1995} } @phdthesis{Cha90, author = {S. Charentus}, title = {Modeling and Control of a Robot Manipulator Composed of Several Stewart Platforms}, address = {Toulouse, France}, school = {Universit\'e Paul Sabatier}, note = {In French}, year = {1990} } @phdthesis{Cha05, author = {S. Chawla}, title = {Graph Algorithms for Planning and Partitioning}, address = {Pittsburgh, PA}, school = {Carnegie Mellon University}, department = {Department of Computer Science}, month = jun, year = {2005} } @incollection{Cha87, author = {B. Chazelle}, title = {Approximation and Decomposition of Shapes}, booktitle = {Algorithmic and Geometric Aspects of Robotics}, pages = {145--185}, editor = {J. T. Schwartz and C. K. Yap}, publisher = {Lawrence Erlbaum Associates}, address = {Hillsdale, NJ}, year = {1987} } @article{Cha91, author = {B. Chazelle}, title = {Triangulating a Simple Polygon in Linear Time}, journal = {Discrete and Computational Geometry}, volume = {6}, number = {5}, pages = {485--524}, year = {1991} } @book{Cha00, author = {B. Chazelle}, title = {The Discrepancy Method}, publisher = {Cambridge University Press}, address = {Cambridge, U.K.}, year = {2000} } @book{Che84, author = {C.-T. Chen}, title = {Linear System Theory and Design}, publisher = {Holt, Rinehart, and Winston}, address = {New York}, year = {1984} } @inproceedings{CheHwa92, author = {P. C. Chen and Y. K. Hwang}, title = {{SANDROS}: {A} motion planner with performance proportional to task difficulty}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2346--2353}, year = {1992} } @article{CheHwa98, author = {P. C. Chen and Y. K. Hwang}, title = {{SANDROS}: {A} dynamic search graph algorithm for motion planning}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {14}, number = {3}, pages = {390--403}, year = {1998} } @article{CheIer95, author = {Y.-B. Chen and D. J. Ierardi}, title = {The complexity of oblivious plans for orienting and distinguishing polygonal parts}, journal = {Algorithmica}, volume = {14}, pages = {367--397}, year = {1995} } @phdthesis{Che05, author = {P. Cheng}, title = {Sampling-Based Motion Planning with Differential Constraints}, address = {Urbana, IL}, school = {University of Illinois}, department = {Department of Computer Science}, month = aug, year = {2005} } @inproceedings{CheFraLav03, author = {P. Cheng and E. Frazzoli and S. M. LaValle}, title = {Exploiting Group Symmetries to Improve Precision in Kinodynamic and Nonholonomic Planning}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2003} } @inproceedings{CheFraLav04, author = {P. Cheng and E. Frazzoli and S. M. LaValle}, title = {Improving the Performance of Sampling-Based Planners by Using a Symmetry-Exploiting Gap Reduction Algorithm}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, year = {2004} } @inproceedings{CheLav01, author = {P. Cheng and S. M. LaValle}, title = {Reducing Metric Sensitivity in Randomized Trajectory Design}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {43--48}, year = {2001} } @inproceedings{CheLav02, author = {P. Cheng and S. M. LaValle}, title = {Resolution Complete Rapidly-Exploring Random Trees}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, pages = {267--272}, year = {2002} } @inproceedings{CheSheLav00, author = {P. Cheng and Z. Shen and S. M. LaValle}, title = {Using Randomization to Find and Optimize Feasible Trajectories for Nonlinear Systems}, booktitle = {Proceedings Annual Allerton Conference on Communications, Control, Computing}, pages = {926--935}, year = {2000} } @article{CheSheLav01, author = {P. Cheng and Z. Shen and S. M. LaValle}, title = {{RRT}-Based Trajectory Design for Autonomous Automobiles and Spacecraft}, journal = {Archives of Control Sciences}, volume = {11}, number = {3-4}, pages = {167--194}, year = {2001} } @inproceedings{Che99, author = {M. Cherif}, title = {Kinodynamic Motion Planning for All-Terrain Wheeled Vehicles}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {}, year = {1999} } @book{CheBolGra94, author = {F. L. Chernousko and N. N. Bolotnik and V. G. Gradetsky}, title = {Manipulation Robots}, publisher = {CRC Press}, address = {Boca Raton, FL}, year = {1994} } @article{CheKed93, author = {L. P. Chew and K. Kedem}, title = {A convex polygon among polygonal obstacles: {P}lacement and high-clearance motion}, journal = {Computational Geometry: Theory and Applications}, volume = {3}, pages = {59--89}, year = {1993} } @incollection{ChiMayPan05, author = {D. Chibisov and E. W. Mayr and S. Pankratov}, title = {Spatial planning and geometric optimization: {C}ombining configuration space and energy methods}, booktitle = {Automated Deduction in Geometry - ADG 2004}, editor = {H. Hong and D. Wang}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2006} } @article{ChiSheTraCicManFryTroShuBoy05, author = {S. Chien and R. Sherwood and D. Tran and B. Cichy and D. Mandl and S. Frye and B. Trout and S. Shulman and D. Boyer}, title = {Using Autonomy Flight Software to Improve Science Return on {Earth Observing One}}, journal = {Journal of Aerospace Computing, Information, and Communication}, volume = {2}, pages = {196--216}, month = apr, year = {2005} } @article{ChiNta88, author = {W.-P. Chin and S. Ntafos}, title = {Optimum Watchman Routes}, journal = {Information Processing Letters}, volume = {28}, pages = {39--44}, year = {1988} } @article{ChiPamEbe96, author = {G. Chirikjian and A. Pamecha and I. Ebert-Uphoff}, title = {Evaluating Efficiency of Self-Reconfiguration in a Class of Modular Robots}, journal = {Journal of Robotic Systems}, volume = {13}, number = {5}, pages = {717--338}, year = {1996} } @book{ChiKya01, author = {G. S. Chirikjian and A. B. Kyatkin}, title = {Engineering Applications of Noncommutative Harmonic Analysis}, publisher = {CRC Press}, address = {Boca Raton, FL}, year = {2001} } @inproceedings{ChiLavBalMas06, author = {H. Chitsaz and S. M. LaValle and D. J. Balkcom and M. T. Mason}, title = {Minimum Wheel-Rotation Paths for Differential-Drive Mobile Robots}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, year = {2006} } @inproceedings{ChiOkaLav04, author = {H. Chitsaz and J. M. O'Kane and S. M. LaValle}, title = {Pareto-Optimal Coordination of Two Translating Polygonal Robots on an Acyclic Roadmap}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, year = {2004} } @inproceedings{ChiCheFraKum05, author = {S. Chitta and P. Cheng and E. Frazzoli and V. Kumar}, title = {{RoboTrikke}: {A} Novel Undulatory Locomotion System}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2005} } @inproceedings{ChiKum03, author = {S. Chitta and V. Kumar}, title = {Dynamics and Generation of Gaits for a Planar Rollerblader}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2003} } @inproceedings{ChoSelYap95, author = {J. Choi and J. Sellen and C. K. Yap}, title = {Precision-sensitive {E}uclidean shortest path in 3-space}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {350--359}, year = {1995} } @article{Cho00, author = {H. Choset}, title = {Coverage of Known Spaces: The Boustrophedon Cellular Decomposition}, journal = {Autonomous Robots}, volume = {9}, pages = {247--253}, year = {2000} } @article{Cho01, author = {H. Choset}, title = {Coverage for robotics -- {A} survey of recent results}, journal = {Annals of Mathematics and Artificial Intelligence}, volume = {31}, pages = {113--126}, year = {2001} } @article{ChoBur00, author = {H. Choset and J. Burdick}, title = {Sensor based motion planning: {I}ncremental construction of the hierarchical generalized {Voronoi} graph}, journal = {International Journal of Robotics Research}, volume = {19}, number = {2}, pages = {126--148}, year = {2000} } @article{ChoBur00b, author = {H. Choset and J. Burdick}, title = {Sensor based motion planning: The hierarchical generalized {Voronoi} graph}, journal = {International Journal of Robotics Research}, volume = {19}, number = {2}, pages = {96--125}, year = {2000} } @book{ChoLynHutKanBurKavThr05, author = {H. Choset and K. M. Lynch and S. Hutchinson and G. Kantor and W. Burgard and L. E. Kavraki and S. Thrun}, title = {Principles of Robot Motion: Theory, Algorithms, and Implementations}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {2005} } @article{ChoNag01, author = {H. Choset and K. Nagatani}, title = {Topological simultaneous localization and mapping {(T-SLAM)}}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {17}, number = {2}, pages = {125--137}, year = {2001} } @inproceedings{ChoPig97, author = {H. Choset and P. Pignon}, title = {Cover path planning: {T}he boustrophedron decomposition}, booktitle = {Proceedings International Conference on Field and Service Robotics}, address = {Canberra, Australia}, month = dec, year = {1997} } @inproceedings{ChoLyn02b, author = {P. Choudhury and K. Lynch}, title = {Rolling Manipulation with a Single Control}, booktitle = {Proceedings Conference on Control Applications}, month = sep, year = {2002} } @inproceedings{ChoLyn02, author = {P. Choudhury and K. Lynch}, title = {Trajectory Planning for Second-Order Underactuated Mechanical Systems in Presence of Obstacles}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, year = {2002} } @article{Chu72, author = {K.-C. Chu}, title = {Team Decision Theory and Information Structures in Optimal Control Problems -- {Part II}}, journal = {IEEE Transactions on Automatic Control}, volume = {17}, number = {1}, pages = {22--28}, month = feb, year = {1972} } @book{ChuChe91, author = {C. K. Chui and G. Chen}, title = {Kalman Filtering}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1991} } @inproceedings{ChySusMauVos04, author = {M. Chyba and H. Sussmann and H. Maurer and G. Vossen}, title = {Underwater vehicles: {T}he minimum time problem}, booktitle = {Proceedings IEEE Conference Decision \& Control}, address = {The Bahamas}, month = dec, year = {2004} } @inproceedings{ClaRocLat03, author = {C. M. Clark and S. M. Rock and J.-C. Latombe}, title = {Motion Planning for Multiple Mobile Robots using Dynamic Networks}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2003} } @article{ClaJonWilKenGle94, author = {D. E. Clark and G. Jones and P. Willett P. W. Kenny and R. C. Glen}, title = {Pharmacophoric Pattern Matching in Files of Three-Dimensional Chemical Structures: Comparison of Conformational Searching Algorithms for Flexible Searching}, journal = {Journal Chemical Information and Computational Sciences}, volume = {34}, pages = {197--206}, year = {1994} } @misc{Cla03, author = {K. L. Clarkson}, title = {Nearest neighbor searching in metric spaces: {E}xperimental Results for sb(S)}, howpublished = {Bell Labs. Available from http://cm.bell-labs.com/who/clarkson/Msb/readme.html}, year = {2003} } @article{CohCoo87, author = {F. S. Cohen and D. B. Cooper}, title = {Simple Parallel Hierarchical and Relaxation Algorithms for Segmenting Noncausal {Markovian} Random Fields}, journal = {IEEE Transactions Pattern Analysis Machine Intelligence}, volume = {9}, number = {2}, pages = {195--219}, month = mar, year = {1987} } @inproceedings{Col75, author = {G. E. Collins}, title = {Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition}, booktitle = {Proceedings Second GI Conference on Automata Theory and Formal Languages}, pages = {134--183}, publisher = {Springer-Verlag}, address = {Berlin}, note = {Lecture Notes in Computer Science, 33}, year = {1975} } @incollection{Col98, author = {G. E. Collins}, title = {Quantifier Elimination by Cylindrical Algebraic Decomposition--Twenty Years of Progress}, booktitle = {Quantifier Elimination and Cylindrical Algebraic Decomposition}, pages = {8--23}, editor = {B. F. Caviness and J. R. Johnson}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1998} } @book{Con01, author = {L. Conlon}, title = {Differentiable Manifolds, 2nd Ed.}, publisher = {{Birkh\"auser}}, address = {Boston, MA}, year = {2001} } @inproceedings{ConRizCho03, author = {D. C. Conner and A. A. Rizzi and H. Choset}, title = {Composition of Local Potential Functions for Global Robot Control and Navigation}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {3546--3551}, year = {2003} } @article{ConGru93, author = {C. Connolly and R. Grupen}, title = {The Application of Harmonic Potential Functions to Robotics}, journal = {Journal of Robotic Systems}, volume = {10}, number = {7}, pages = {931--946}, year = {1993} } @inproceedings{ConGruSou95, author = {C. Connolly and R. Grupen and K. Souccar}, title = {A {H}amiltonian Framework for Kinodynamic Planning}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {1995} } @inproceedings{Con85, author = {C. I. Connolly}, title = {The Determination of Next Best Views}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {432--435}, year = {1985} } @inproceedings{Con92, author = {C. I. Connolly}, title = {Applications of harmonic functions to robotics}, booktitle = {IEEE Symposium on Intelligent Control}, pages = {498--502}, year = {1992} } @inproceedings{ConBurWei90, author = {C. I. Connolly and J. B. Burns and R. Weiss}, title = {Path planning using {L}aplace's equation}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2102--2106}, month = may, year = {1990} } @book{ConSlo99, author = {J. H. Conway and N. J. A. Sloane}, title = {Sphere Packings, Lattices, and Groups}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1999} } @article{Cor85, author = {H. W. Corley}, title = {Some Multiple Objective Dynamic Programs}, journal = {IEEE Transactions on Automatic Control}, volume = {30}, number = {12}, pages = {1221--1222}, month = dec, year = {1985} } @book{CorLeiRivSte01, author = {T. H. Cormen and C. E. Leiserson and R. L. Rivest and C. Stein}, title = {Introduction to Algorithms (2nd Ed.)}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {2001} } @phdthesis{Cor03, author = {J. Cort\'es}, title = {Motion Planning Algorithms for General Closed-Chain Mechanisms}, address = {Toulouse, France}, school = {Institut National Polytechnique de Toulouse}, department = {LAAS/CNRS}, year = {2003} } @article{CorSimSimTra04, author = {J. Cort\'es and T. Sim\'eon M. Remaud-Sim\'eon and V. Tran}, title = {Geometric Algorithms for the Conformational Analysis of Long Protein Loops}, journal = {Journal of Computational Chemistry}, volume = {25}, pages = {956--967}, year = {2004} } @inproceedings{CorSimLau02, author = {J. Cort\'es and T. Sim\'eon and J.-P. Laumond}, title = {A Random Loop Generator for planning the motions of closed kinematic chains using {PRM} methods}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2002} } @book{Cou01, author = {M. G. Coutinho}, title = {Dynamic Simulations of Multibody Systems}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2001} } @book{CovTho91, author = {T. M. Cover and J. A. Thomas}, title = {Elements of Information Theory}, publisher = {Wiley}, address = {New York}, year = {1991} } @inproceedings{Cow04, author = {N. Cowan}, title = {Composing Navigation Functions on {Cartesian} Products of Manifolds with Boundary}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, address = {Zeist, The Netherlands}, month = jul, year = {2004} } @book{CoxLitOsh92, author = {D. Cox and J. Little and D. O'Shea}, title = {Ideals, Varieties, and Algorithms}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1992} } @book{Cox73, author = {H. S. M. Coxeter}, title = {Regular Polytopes}, publisher = {Dover}, address = {New York}, year = {1973} } @book{Cra89, author = {J. J. Craig}, title = {Introduction to Robotics}, publisher = {Addison-Wesley}, address = {Reading, MA}, year = {1989} } @article{CraLio83, author = {M. G. Crandall and P.-L. Lions}, title = {Viscosity Solutions of {Hamilton-Jacobi} equations}, journal = {Transactions of the American Mathematical Society}, volume = {277}, number = {1}, pages = {1--42}, year = {1983} } @article{CraSuzYam95, author = {D. Crass and I. Suzuki and M. Yamashita}, title = {Searching for a Mobile Intruder in a Corridor -- {T}he Open Edge Variant of the Polygon Search Problem}, journal = {International Journal Computational Geometry \& Applications}, volume = {5}, number = {4}, pages = {397--412}, year = {1995} } @inproceedings{Cul98, author = {J. C. Culberson}, title = {Sokoban is {PSPACE}-complete}, booktitle = {Proceedings International Conference on Fun with Algorithms (FUN98)}, pages = {65--76}, publisher = {Carleton Scientific}, address = {Waterloo, Ontario, Canada}, month = jun, year = {1998} } @book{Cut85, author = {M. R. Cutkosky}, title = {Robotic Grasping and Fine Manipulation}, publisher = {Kluwer}, address = {Boston, MA}, year = {1985} } @inproceedings{HahFoxBurThr03, author = {{D. H\"ahnel D. Fox and W. Burgard and S. Thrun}}, title = {A highly efficient {FastSLAM} algorithm for generating cyclic maps of large-scale environments from raw laser range measurements}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2003} } @inproceedings{DalAma99, author = {L. K. Dale and N. M. Amato}, title = {Probabilistic Roadmap Methods are Embarrassingly Parallel}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {1999} } @inproceedings{DelFoxBurThr99, author = {F. Dallaert and D. Fox and W. Burgard and S. Thrun}, title = {Monte {C}arlo localization for mobile robots}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {1999} } @book{Dan63, author = {G. B. Dantzig}, title = {Linear Programming and Extensions}, publisher = {Princeton University Press}, address = {Princeton, NJ}, year = {1963} } @incollection{DatHipSch95, author = {A. Datta and C. A. Hipke and S. Schuierer}, title = {Competitive Searching in Polygons--Beyond Generalized Streets}, booktitle = {Algorithms and Computation, ISAAC '95}, pages = {32--41}, editor = {J. Staples and P. Eades and N. Katoh and A. Moffat}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1995} } @inproceedings{Dat03, author = {R. S. Datta}, title = {Using Computer Algebra to Compute {Nash} Equilibria}, booktitle = {Proceedings International Symposium on Symbolic and Algebraic Computation}, year = {2003} } @article{DavHei88, author = {J. Davenport and J. Heintz}, title = {Real quantifier elimination is doubly exponential}, journal = {Journal of Symbolic Computation}, volume = {5}, pages = {29--35}, year = {1988} } @inproceedings{Dav96, author = {S. Davies}, title = {Multidimensional triangulation and interpolation for reinforcement learning}, booktitle = {Proceedings Neural Information Processing Systems}, year = {1996} } @book{DebVanOveSch97, author = {M. de Berg and M. van Kreveld and M. Overmars and O. Schwarzkopf}, title = {Computational Geometry: Algorithms and Applications, 2nd Ed.}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2000} } @phdthesis{Des03, author = {M. J. de Smith}, title = {Distance and Path: The Development, Interpretation and Application of Distance Measurement in Mapping and Modelling}, address = {London}, school = {University College, University of London}, department = {Centre for Advanced Spatial Analysis}, year = {2003} } @incollection{DeaKam97, author = {T. Dean and S. Kambhampati}, title = {Planning and Scheduling}, booktitle = {The CRC Handbook of Computer Science and Engineering}, pages = {614--636}, editor = {A. B. Tucker}, publisher = {CRC Press}, address = {Boca Raton, FL}, year = {1997} } @book{DeaWel91, author = {T. L. Dean and M. P. Wellman}, title = {Planning and Control}, publisher = {Morgan Kaufman}, address = {San Francisco, CA}, year = {1991} } @book{Deg70, author = {M. H. DeGroot}, title = {Optimal Statistical Decisions}, publisher = {McGraw-Hill}, address = {New York}, year = {1970} } @article{DemLaiRub77, author = {A. P. Dempster and N. M. Laird and D. B. Rubin}, title = {Maximum-likelihood from incomplete data via the {EM} algorithm}, journal = {Journal of the Royal Statistical Society, Ser. B.}, volume = {39}, pages = {1--38}, year = {1977} } @misc{DenKamPap97, author = {X. Deng and T. Kameda and C. Papadimitriou}, title = {How to Learn an Unknown Environment {I}: {T}he Rectilinear Case}, howpublished = {Available from {http://www.cs.berkeley.edu/$\sim$christos/}}, year = {1997} } @book{DevKit82, author = {P. A. Devijver and J. Kittler}, title = {Pattern Recognition: A Statistical Approach}, publisher = {Prentice-Hall}, address = {Englewood Cliffs, NJ}, year = {1982} } @article{Dia69, author = {R. Dial}, title = {Algorithm 360: {S}hortest path forest with topological ordering}, journal = {Communications of the ACM}, volume = {12}, pages = {632--633}, year = {1969} } @article{Dij59, author = {E. W. Dijkstra}, title = {A note on two problems in connexion with graphs}, journal = {Numerische Mathematik}, volume = {1}, pages = {269--271}, year = {1959} } @inproceedings{DimZavLoiKyr03, author = {D. V. Dimarogonas and M. M. Zavlanos and S. G. Loizou and K. J. Kyriakopoulos}, title = {Decentralized Motion Control of Multiple Holonomic Agents Under Input Constraints}, booktitle = {Proceedings IEEE Conference Decision \& Control}, year = {2003} } @article{DisNewClaDurCso01, author = {G. Dissanayake and P. Newman and S. Clark and H. F. Durrant-Whyte and M. Csorba}, title = {A solution to the simultaneous localisation and map building ({SLAM}) problem}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {17}, number = {3}, pages = {229--241}, year = {2001} } @inproceedings{DivWen94, author = {A. W. Divelbiss and J. T. Wen}, title = {Nonholonomic path planning with inequality constraints}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {52--57}, year = {1994} } @article{DivWen97, author = {A. W. Divelbiss and J. T. Wen}, title = {A path-space approach to nonholonomic planning in the presence of obstacles}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {13}, number = {3}, pages = {443--451}, year = {1997} } @book{DixBehDawNag03, author = {W. E. Dixon and A. Behal and D. M. Dawson and S. Nagarkatti}, title = {Nonlinear Control of Engineering Systems: A Lyapunov-Based Approach}, publisher = {{Birkh\"auser}}, address = {Boston, MA}, year = {2003} } @book{Doc92, author = {M. P. do Carmo}, title = {Riemannian Geometry}, publisher = {{Birkh\"auser}}, address = {Boston, MA}, year = {1992} } @techreport{Don84, author = {B. R. Donald}, title = {Motion planning with six degrees of freedom}, number = {AI-TR-791}, address = {Cambridge, MA}, institution = {Artificial Intelligence Lab., Massachusetts Institute of Technology}, year = {1984} } @phdthesis{Don87, author = {B. R. Donald}, title = {Error Detection and Recovery for Robot Motion Planning with Uncertainty}, number = {}, address = {Cambridge, MA}, school = {Massachusetts Institute of Technology}, department = {Department of Electrical Engineering and Computer Science}, month = {}, year = {1987} } @article{Don87b, author = {B. R. Donald}, title = {A Search Algorithm for Motion Planning with Six Degrees of Freedom}, journal = {Artificial Intelligence Journal}, volume = {31}, pages = {295--353}, year = {1987} } @inproceedings{Don88b, author = {B. R. Donald}, title = {The Complexity of Planar Compliant Motion Planning Under Uncertainty}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {309--318}, year = {1988} } @article{Don88, author = {B. R. Donald}, title = {A Geometric Approach to Error Detection and Recovery for Robot Motion Planning with Uncertainty}, journal = {Artificial Intelligence Journal}, volume = {37}, pages = {223--271}, year = {1988} } @article{Don90, author = {B. R. Donald}, title = {Planning Multi-Step Error Detection and Recovery Strategies}, journal = {International Journal of Robotics Research}, volume = {9}, number = {1}, pages = {3--60}, year = {1990} } @article{Don95, author = {B. R. Donald}, title = {On Information Invariants in Robotics}, journal = {Artificial Intelligence Journal}, volume = {72}, pages = {217--304}, year = {1995} } @inproceedings{DonJen91, author = {B. R. Donald and J. Jennings}, title = {Sensor Interpretation and Task-Directed Planning Using Perceptual Equivalence Classes}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {190--197}, year = {1991} } @article{DonXav95b, author = {B. R. Donald and P. Xavier}, title = {Provably Good Approximation Algorithms for Optimal Kinodynamic Planning for {Cartesian} Robots and Open Chain Manipulators}, journal = {Algorithmica}, volume = {14}, number = {6}, pages = {480--530}, year = {1995} } @article{DonXav95a, author = {B. R. Donald and P. Xavier}, title = {Provably Good Approximation Algorithms for Optimal Kinodynamic Planning: Robots with Decoupled Dynamics Bounds}, journal = {Algorithmica}, volume = {14}, number = {6}, pages = {443--479}, year = {1995} } @article{DonXavCanRei93, author = {B. R. Donald and P. G. Xavier and J. Canny and J. Reif}, title = {Kinodynamic Planning}, journal = {Journal of the ACM}, volume = {40}, pages = {1048--66}, month = nov, year = {1993} } @article{Don83, author = {S. K. Donaldson}, title = {Self-Dual Connections and the Topology of Smooth 4-Manifold}, journal = {Bulletin of the American Mathematical Society}, volume = {8}, pages = {81--83}, year = {1983} } @incollection{Don96, author = {A. L. Dontchev}, title = {Discrete Approximations in Optimal Control}, booktitle = {Nonsmooth Analysis and Geometric Methods in Deterministic Optimal Control}, pages = {59--80}, editor = {B. S. Mordukhovich and H. J. Sussmann}, publisher = {Springer-Verlag}, address = {Berlin}, note = {Mathematics and Its Applications, Vol. 78}, year = {1996} } @book{DouDefGor01, author = {A. Doucet and N. de Freitas and N. Gordon}, title = {Sequential Monte Carlo Methods in Practice}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2001} } @article{Dub57, author = {L. E. Dubins}, title = {On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents}, journal = {American Journal of Mathematics}, volume = {79}, pages = {497--516}, year = {1957} } @book{DudHarSto00, author = {R. O. Duda and P. E. Hart and D. G. Stork}, title = {Pattern Classification, 2nd Ed.}, publisher = {Wiley}, address = {New York}, year = {2000} } @book{DudJen00, author = {G. Dudek and M. Jenkin}, title = {Computational Principles of Mobile Robotics}, publisher = {Cambridge University Press}, address = {Cambridge, U.K.}, year = {2000} } @inproceedings{DudJenMilWil93, author = {G. Dudek and M. Jenkin and E. Milios and D. Wilkes}, title = {Map Validation and Self-Location in a Graph-like World}, booktitle = {Proceedings AAAI National Conference on Artificial Intelligence}, pages = {1648--1653}, year = {1993} } @article{DudRomWhi98, author = {G. Dudek and K. Romanik and S. Whitesides}, title = {Global Localization: {L}ocalizing a Robot with Minimal Travel}, journal = {SIAM Journal on Computing}, volume = {27}, number = {2}, pages = {583--604}, month = apr, year = {1998} } @book{Dul98, author = {I. Duleba}, title = {Algorithms of Motion Planning for Nonholonomic Robots}, publisher = {Technical University of Wroclaw}, address = {Wroclaw, Poland}, year = {1998} } @article{DulDan04, author = {G. E. Dullerud and R. D'Andrea}, title = {Distributed Control of Heterogeneous Systems}, journal = {IEEE Transactions on Automatic Control}, volume = {49}, number = {12}, pages = {2113--2128}, year = {2004} } @book{DulPag00, author = {G. E. Dullerud and F. Paganini}, title = {A Course in Robust Control Theory}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2000} } @book{Ede87, author = {H. Edelsbrunner}, title = {Algorithms in Combinatorial Geometry}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1987} } @book{EdwSpu98, author = {C. Edwards and S. K. Spurgeon}, title = {Sliding Mode Control: Theory and Applications}, publisher = {CRC Press}, address = {Ann Arbor, MI}, year = {1998} } @inproceedings{EfrGuiLinMitMur00, author = {A. Efrat and L. J. Guibas and S. Har-Peled and D. C. Lin and J. S. B. Mitchell and T. M. Murali}, title = {Sweeping simple polygons with a chain of guards}, booktitle = {Proceedings ACM-SIAM Symposium on Discrete Algorithms}, year = {2000} } @article{EgeHu01, author = {M. Egerstedt and X. Hu}, title = {Formation Constrained Multi-Agent Control}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {17}, number = {6}, pages = {947--951}, month = dec, year = {2001} } @inproceedings{EhmLin01, author = {S. Ehmann and M. C. Lin}, title = {Accurate and Fast Proximity Queries Between Polyhedra Using Convex Surface Decomposition}, booktitle = {Proceedings Eurographics}, year = {2001} } @article{Elf89, author = {A. Elfes}, title = {Using Occupancy Grids for Mobile Robot Perception and Navigation}, journal = {IEEE Computer}, volume = {22}, number = {6}, pages = {46--57}, month = jun, year = {1989} } @book{Ell02, author = {G. Ellis}, title = {Observers in Control Systems}, publisher = {Elsevier}, address = {New York}, year = {2002} } @techreport{EmiMou97, author = {I. Z. Emiris and B. Mourrain}, title = {Computer Algebra Methods for Studying and Computing Molecular Conformations}, address = {Sophia-Antipolis, France}, institution = {INRIA}, year = {1997} } @book{ErdSanKot01, author = {A. G. Erdman and G. N. Sandor and S. Kota}, title = {Mechanism Design: Analysis and Synthesis, 4th Ed., Vol. 1}, publisher = {Prentice Hall}, address = {Englewood Cliffs, NJ}, year = {2001} } @mastersthesis{Erd84, author = {M. A. Erdmann}, title = {On Motion Planning with Uncertainty}, number = {}, address = {Cambridge, MA}, school = {Massachusetts Institute of Technology}, department = {Department of Electrical Engineering and Computer Science}, month = aug, year = {1984} } @article{Erd86, author = {M. A. Erdmann}, title = {Using Backprojections for Fine Motion Planning with Uncertainty}, journal = {International Journal of Robotics Research}, volume = {5}, number = {1}, pages = {19--45}, year = {1986} } @phdthesis{Erd89, author = {M. A. Erdmann}, title = {On Probabilistic Strategies for Robot Tasks}, number = {}, address = {Cambridge, MA}, school = {Massachusetts Institute of Technology}, department = {Department of Electrical Engineering and Computer Science}, month = {}, year = {1989} } @article{Erd92, author = {M. A. Erdmann}, title = {Randomization in Robot Tasks}, journal = {International Journal of Robotics Research}, volume = {11}, number = {5}, pages = {399--436}, month = oct, year = {1992} } @article{Erd93, author = {M. A. Erdmann}, title = {Randomization for Robot Tasks: Using Dynamic Programming in the Space of Knowledge States}, journal = {Algorithmica}, volume = {10}, pages = {248--291}, year = {1993} } @article{Erd94, author = {M. A. Erdmann}, title = {On a Representation of Friction in Configuration Space}, journal = {International Journal of Robotics Research}, volume = {13}, number = {3}, pages = {240--271}, year = {1994} } @article{Erd95, author = {M. A. Erdmann}, title = {Understanding Action and Sensing by Designing Action-Based Sensors}, journal = {International Journal of Robotics Research}, volume = {14}, number = {5}, pages = {483--509}, year = {1995} } @incollection{Erd97, author = {M. A. Erdmann}, title = {An Exploration of Nonprehensile Two-Palm Manipulation Using Two Zebra Robots}, booktitle = {Algorithms for Robotic Motion and Manipulation}, pages = {239--254}, editor = {J.-P. Laumond and M. Overmars}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1997} } @inproceedings{ErdLoz86, author = {M. A. Erdmann and T. Lozano-P\'erez}, title = {On Multiple Moving Objects}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1419--1424}, year = {1986} } @article{ErdLoz87, author = {M. A. Erdmann and T. Lozano-P\'{e}rez}, title = {On Multiple Moving Objects}, journal = {Algorithmica}, volume = {2}, pages = {477--521}, year = {1987} } @article{ErdMas88, author = {M. A. Erdmann and M. T. Mason}, title = {An Exploration of Sensorless Manipulation}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {4}, number = {4}, pages = {369--379}, month = aug, year = {1988} } @article{ErdMasVan93, author = {M. A. Erdmann and M. T. Mason and G. Van\v{e}\v{c}ek}, title = {Mechanical Parts Orienting: The Case of a Polyhedron on a Table}, journal = {Algorithmica}, volume = {10}, pages = {206--247}, year = {1993} } @article{EspChaRiv92, author = {B. Espiau and F. Chaumette and P. Rives}, title = {A New Approach to Visual Servoing in Robotics}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {8}, number = {3}, pages = {313--326}, month = jun, year = {1992} } @inproceedings{EspKimKum04, author = {J. Esposito and J. W. Kim and V. Kumar}, title = {Adaptive {RRTs} for Validating Hybrid Robotic Control Systems}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, address = {Zeist, The Netherlands}, month = jul, year = {2004} } @article{Far03, author = {M. Farber}, title = {Topological complexity of motion planning}, journal = {Discrete and Computational Geometry}, volume = {29}, pages = {211--221}, year = {2003} } @article{FarTabYuz03, author = {M. Farber and S. Tabachnkov and S. Yuzvinsky}, title = {Topological Robotics: Motion Planning in Projective Spaces}, journal = {International Mathematical Research Notices}, volume = {34}, pages = {1853--1870}, year = {2003} } @techreport{FarYuz04, author = {M. Farber and S. Yuzvinsky}, title = {Topological Robotics: Subspace Arrangements and Collision Free Motion Planning}, number = {math.AT/0210115}, institution = {arXiv (on-line)}, year = {2004} } @inproceedings{Fav84, author = {B. Faverjon}, title = {Obstacle Avoidance Using an Octree in the Configuration Space of a Manipulator}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {504--512}, year = {1984} } @inproceedings{Fav89, author = {B. Faverjon}, title = {Hierarchical object models for efficient anti-collision algorithms}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {333--340}, year = {1989} } @inproceedings{FavTou87, author = {B. Faverjon and P. Tournassoud}, title = {A Local Based Method for Path Planning of Manipulators with a High Number of Degrees of Freedom}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1152--1159}, year = {1987} } @book{Fea87, author = {R. Featherstone}, title = {Robot Dynamics Algorithms}, publisher = {Kluwer}, address = {Boston, MA}, year = {1987} } @inproceedings{FekKleNuc04, author = {S. P. Fekete and R. Klein and A. {N\"uchter}}, title = {Online searching with an autonomous robot}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, address = {Zeist, The Netherlands}, month = jul, year = {2004} } @inproceedings{Fer96, author = {P. Ferbach}, title = {A Method of Progressive Constraints for Nonholonomic Motion Planning}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2949--2955}, year = {1996} } @inproceedings{FerGurLi91, author = {C. Fernandes and L. Gurvits and Z. X. Li}, title = {A variational approach to optimal nonholonomic motion planning}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {680--685}, year = {1991} } @article{FerGurLi94, author = {C. Fernandes and L. Gurvits and Z. X. Li}, title = {Near-Optimal nonholonomic motion planning for a system of coupled rigid bodies}, journal = {IEEE Transactions on Automatic Control}, volume = {30}, number = {3}, pages = {450--463}, month = mar, year = {1994} } @inproceedings{FieDasKumOst01, author = {R. Fierro and A. Das and V. Kumar and J. P. Ostrowski}, title = {Hybrid control of formations of robots}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {157--162}, year = {2001} } @article{FikNil71, author = {R. E. Fikes and N. J. Nilsson}, title = {{STRIPS}: {A} New Approach to the Application of Theorem Proving}, journal = {Artificial Intelligence Journal}, volume = {2}, pages = {189--208}, year = {1971} } @article{Fil60, author = {A. F. Filippov}, title = {Differential equations with discontinuous right-hand sides}, journal = {American Mathematical Society Translations, Ser. 2}, volume = {64}, pages = {199--231}, year = {1964} } @incollection{FinHalKavLatMotSheVen96, author = {P. W. Finn and D. Halperin and L. E. Kavraki and J.-C. Latombe and R. Motwani and C. Shelton and S. Venkatasubramanian}, title = {Geometric Manipulation of Flexible Ligands}, booktitle = {Applied Computational Geometry}, pages = {67--78}, editor = {M. C. Lin and D. Manocha}, publisher = {Springer-Verlag}, address = {Berlin}, note = {Lecture Notes in Computer Science, 1148}, year = {1996} } @inproceedings{Fir87, author = {R. J. Firby}, title = {An Investigation into Reactive Planning in Complex Domains}, booktitle = {Proceedings AAAI National Conference on Artificial Intelligence}, year = {1987} } @book{Fis96, author = {G. F. Fishman}, title = {Monte {C}arlo: {C}oncepts, Algorithms, and Applications}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1996} } @article{FleRomSchTri02, author = {R. Fleischer and K. Romanik and S. Schuierer and G. Trippen}, title = {Optimal Localization in Trees}, journal = {Information and Computation}, volume = {171}, number = {2}, pages = {224--247}, year = {2002} } @article{FleSouLauCha95, author = {S. Fleury and P. Sou\`{e}res and J.-P. Laumond and R. Chatila}, title = {Primitives for smoothing mobile robot trajectories}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {11}, number = {3}, pages = {441--448}, year = {1995} } @article{FleLevMarRou95, author = {M. Fliess and J. L\'evine and P. Martin and P. Rouchon}, title = {Flatness and defect of non-linear systems: {I}ntroductory theory and examples}, journal = {International Journal of Control}, volume = {61}, number = {6}, pages = {1327--1361}, year = {1995} } @inproceedings{FloFabAke04, author = {H. Flordal and M. Fabian and K. Akesson}, title = {Automatic Implementation And Verification Of Coordinating {PLC}-Code for RobotCells}, booktitle = {Proceedings IFAC Symposium of Information Control Problems in Manufacturing}, year = {2004} } @book{Fol84, author = {G. B. Folland}, title = {Real Analysis: Modern Techniques and Their Applications}, publisher = {Wiley}, address = {New York}, year = {1984} } @inproceedings{ForWil88, author = {S. Fortune and G. Wilfong}, title = {Planning Constrained Motion}, booktitle = {Proceedings ACM Symposium on Theory of Computing}, pages = {445--459}, year = {1988} } @inproceedings{FosGarLinMan01, author = {M. Foskey and M. Garber and M. Lin and D. Manocha}, title = {A {V}oronoi-based hybrid motion planner}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2001} } @article{FoxHut95, author = {A. Fox and S. Hutchinson}, title = {Exploiting Visual Constraints in the Synthesis of Uncertainty-Tolerant Motion Plans}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {1}, number = {11}, pages = {56--71}, month = feb, year = {1995} } @incollection{FoxThrBurDel01, author = {D. Fox and S. Thrun and W. Burgard and F. Dallaert}, title = {Particle Filters for Mobile Robot Localization}, booktitle = {Sequential Monte Carlo Methods in Practice}, pages = {401--428}, editor = {A. Doucet and N. de Freitas and N. Gordon}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2001} } @book{Fra03, author = {J. Fraden}, title = {Handbook of Modern Sensors: Physics, Designs, and Applications}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2003} } @inproceedings{Fra93, author = {T. Fraichard}, title = {Dynamic trajectory planning with dynamic constraints: A 'state-time space' approach}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {1393--1400}, year = {1993} } @inproceedings{FraAhu01, author = {T. Fraichard and J.-M. Ahuactzin}, title = {Smooth path planning for cars}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {3722--3727}, year = {2001} } @article{FraAsa04, author = {T. Fraichard and H. Asama}, title = {Inevitable collision states - a step towards safer robots?}, journal = {Advanced Robotics}, pages = {1001--1024}, year = {2004} } @inproceedings{FraLau92, author = {T. Fraichard and C. Laugier}, title = {Kinodynamic planning in a structured and time-varying {2D} workspace}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2: 1500--1505}, year = {1992} } @inproceedings{FraSch94, author = {T. Fraichard and A. Scheuer}, title = {Car-Like Robots and Moving Obstacles}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {64--69}, year = {1994} } @article{FraSch04, author = {T. Fraichard and A. Scheuer}, title = {From {Reeds} and {Shepp}'s to continuous-curvature paths}, journal = {IEEE Transactions on Robotics}, volume = {20}, number = {6}, pages = {1025--1035}, month = dec, year = {2004} } @book{Fra04, author = {T. Frankel}, title = {The Geometry of Physics}, publisher = {Cambridge University Press}, address = {Cambridge, U.K.}, year = {2004} } @phdthesis{Fra01, author = {E. Frazzoli}, title = {Robust Hybrid Control of Autonomous Vehicle Motion Planning}, number = {}, address = {Cambridge, MA}, school = {Massachusetts Institute of Technology}, department = {Department of Aeronautics and Astronautics}, month = jun, year = {2001} } @inproceedings{FraBul04, author = {E. Frazzoli and F. Bullo}, title = {Decentralized algorithms for vehicle routing in a stochastic time-varying environment}, booktitle = {Proceedings IEEE Conference Decision \& Control}, pages = {3357--3363}, year = {2004} } @article{FraDahFer02, author = {E. Frazzoli and M. A. Dahleh and E. Feron}, title = {Real-time motion planning for agile autonomous vehicles}, journal = {AIAA Journal of Guidance and Control}, volume = {25}, number = {1}, pages = {116--129}, year = {2002} } @article{FraDahFer05, author = {E. Frazzoli and M. A. Dahleh and E. Feron}, title = {Maneuver-Based Motion Planning for Nonlinear Systems with Symmetries}, journal = {IEEE Transactions on Robotics}, volume = {21}, number = {6}, pages = {1077--1091}, month = dec, year = {2005} } @article{FreHoy88, author = {E. Freund and H. Hoyer}, title = {Path Finding in Multi Robot Systems Including Obstacle Avoidance}, journal = {International Journal of Robotics Research}, volume = {7}, number = {1}, pages = {42--70}, month = feb, year = {1988} } @article{FriBen77, author = {J. H. Friedman and J. L. Bentley and R.A. Finkel}, title = {An algorithm for finding best matches in logarithmic expected time}, journal = {ACM Transactions on Mathematical Software}, volume = {3}, number = {3}, pages = {209--226}, month = sep, year = {1977} } @book{FuGonLee87, author = {K. S. Fu and R. C. Gonzalez and C. S. G. Lee}, title = {Robotics: Control, Sensing, Vision, and Intelligence}, publisher = {McGraw-Hill}, address = {New York}, year = {1987} } @techreport{FujSam86, author = {K. Fujimura and H. Samet}, title = {A Hierarchical Strategy for Path Planning Among Moving Obstacles}, number = {CAR-TR-237}, address = {University of Maryland}, institution = {Center for Automation Research}, month = nov, year = {1986} } @article{FujSam93, author = {K. Fujimura and H. Samet}, title = {Planning a Time-Minimal Motion Among Moving Obstacles}, journal = {Algorithmica}, volume = {10}, pages = {41--63}, year = {1993} } @inproceedings{FukItoOotAraAbeTanTan93, author = {T. Fukuda and S. Ito and N. Oota and F. Arai and Y. Abe and K. Tanake and Y. Tanaka}, title = {Navigation system based on ceiling landmark recognition for autonomous mobile robot}, booktitle = {Proceedings International Conference on Industrial Electronics, Control, and Instrumentation}, pages = {1466--1471}, year = {1993} } @inproceedings{Ful61, author = {A. T. Fuller}, title = {Relay Control Systems Optimized for Various Performance Criteria}, booktitle = {Automatic and Remote Control (Proceedings First World Congress IFAC, Moscow, 1960)}, pages = {510--519}, publisher = {Butterworths, London}, year = {1961} } @book{Fun04, author = {J. Funge}, title = {Artificial Intelligence for Computer Games}, publisher = {A. K. Peters}, address = {Wellesley, MA}, year = {2004} } @techreport{GabRim99, author = {Y. Gabriely and E. Rimon}, title = {Spanning-Tree Based Coverage of Continuous Areas by a Mobile Robot}, address = {Technion, Israel Institute of Technology}, institution = {Dept. of Mechanical Engineering}, month = dec, year = {1999} } @inproceedings{GabRim01, author = {Y. Gabriely and E. Rimon}, title = {Spanning-Tree Based Coverage of Continuous Areas by a Mobile Robot}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1927--1933}, year = {2001} } @article{GabRim03, author = {Y. Gabriely and E. Rimon}, title = {Competitive on-line coverage of grid environments by a mobile robot}, journal = {Computational Geometry: Theory and Applications}, volume = {24}, number = {3}, pages = {197--224}, month = apr, year = {2003} } @inproceedings{GabRim04, author = {Y. Gabriely and E. Rimon}, title = {Competitive Complexity of Mobile Robot On Line Motion Planning Problems}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, pages = {249--264}, year = {2004} } @book{Gal00, author = {J. Gallier}, title = {Curves and Surfaces in Geometric Modeling}, publisher = {Morgan Kaufmann}, address = {San Francisco, CA}, year = {2000} } @article{GemGem84, author = {D. Geman and S. Geman}, title = {Stochastic Relaxation, {Gibbs} Distributions, and the {Bayesian} Restoration of Images}, journal = {IEEE Transactions Pattern Analysis Machine Intelligence}, volume = {6}, number = {6}, pages = {721--741}, month = nov, year = {1984} } @book{GenNil87, author = {M. R. Genesereth and N. Nilsson}, title = {Logical Foundations of Artificial Intelligence}, publisher = {Morgan Kaufmann}, address = {San Francisco, CA}, year = {1987} } @inproceedings{GerOve04, author = {R. Geraerts and M. Overmars}, title = {Sampling Techniques for Probabilistic Roadmap Planners}, booktitle = {Proceedings International Conference on Intelligent Autonomous Systems}, location = {Amsterdam}, year = {2004} } @inproceedings{GerOve02, author = {R. Geraerts and M. H. Overmars}, title = {A Comparative Study of Probabilistic Roadmap Planners}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, pages = {}, month = dec, year = {2002} } @inproceedings{GerThrGor04, author = {B. Gerkey and S. Thrun and G. Gordon}, title = {Clear the building: {P}ursuit-evasion with teams of robots}, booktitle = {Proceedings AAAI National Conference on Artificial Intelligence}, year = {2004} } @book{GhaNauTra04, author = {M. Ghallab and D. Nau and P. Traverso}, title = {Automated Planning: Theory and Practice}, publisher = {Morgan Kaufman}, address = {San Francisco, CA}, year = {2004} } @article{GhoLogTreWanWahTomGowJaeWen95, author = {A. K. Ghose and M. E. Logan and A. M. Treasurywala and H. Wang and R. C. Wahl and B. E. Tomczuk and M. R. Gowravaram and E. P. Jaeger and J. J. Wendoloski}, title = {Determination of Pharmacophoric Geometry for Collagenase Inhibitors Using a Novel Computational Method and Its Verification Using Molecular Dynamics, {NMR}, and {X}-ray Crystallography}, journal = {Journal of the American Chemical Society}, volume = {117}, pages = {4671--4682}, year = {1995} } @article{GhoMou91, author = {S. K. Ghosh and D. M. Mount}, title = {An Output Sensitive Algorithm for Computing Visibility Graphs}, journal = {SIAM Journal on Computing}, volume = {20}, pages = {888--910}, year = {1991} } @inproceedings{Ghr02, author = {R. Ghrist}, title = {Shape complexes for metamorphic robot systems}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, pages = {}, month = dec, year = {2002} } @article{GhrOkaLav05, author = {R. Ghrist and J. M. O'Kane and S. M. LaValle}, title = {{Computing Pareto Optimal Coordinations on Roadmaps}}, journal = {The International Journal of Robotics Research}, volume = {24}, number = {11}, pages = {997--1010}, year = {2005} } @article{GilJoh85, author = {E. G. Gilbert and D. W. Johnson}, title = {Distance Functions and Their Application to Robot Path Planning in the Presence of Obstacles}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {1}, number = {1}, pages = {21--30}, month = mar, year = {1985} } @article{GilJohKee88, author = {E. G. Gilbert and D. W. Johnson and S. S. Keerth}, title = {A fast procedure for computing the distance between complex objects in three-dimensional space}, journal = {IEEE Journal of Robotics \& Automation}, volume = {RA-4}, number = {2}, pages = {193--203}, month = apr, year = {1988} } @book{Gil92, author = {T. N. Gillespie}, title = {Fundamentals of Vehicle Dynamics}, publisher = {Society of Automotive Engineers}, address = {Warrendale, PA}, year = {1992} } @inproceedings{Gla90, author = {B. Glavina}, title = {Solving Findpath by Combination of Goal-Directed and Randomized Search}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1718--1723}, month = may, year = {1990} } @phdthesis{Gla91, author = {B. Glavina}, title = {Planning collision free motions for manipulators through a combination of goal oriented search and the creation of intermediate random subgoals}, school = {Technical University of Munich}, note = {In German}, year = {1991} } @inproceedings{GmyDur91, author = {P. J. Gmytrasiewicz and E. H. Durfee and D. K. Wehe}, title = {A decision-theoretic approach to coordinating multi-agent interactions}, booktitle = {Proceedings International Joint Conference on Artificial Intelligence}, pages = {62--68}, year = {1991} } @inproceedings{GoVuKuf04, author = {J. Go and T. Vu and J. J. Kuffner}, title = {Autonomous behaviors for interactive vehicle animations}, booktitle = {Proceedings SIGGRAPH Symposium on Computer Animation}, year = {2004} } @phdthesis{Gol90, author = {K. Y. Goldberg}, title = {Stochastic Plans for Robotic Manipulation}, number = {CMU-CS-90-161}, address = {Pittsburgh, PA}, school = {Carnegie Mellon University}, department = {Department of Computer Science}, month = aug, year = {1990} } @article{Gol93, author = {K. Y. Goldberg}, title = {Orienting Polygonal Parts Without Sensors}, journal = {Algorithmica}, volume = {10}, pages = {201--225}, year = {1993} } @inproceedings{GolMas90, author = {K. Y. Goldberg and M. T. Mason}, title = {Bayesian Grasping}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {}, year = {1990} } @book{Gol80, author = {H. Goldstein}, title = {Classical Mechanics}, publisher = {Addison-Wesley}, address = {Reading, MA}, year = {1980} } @incollection{GolMot97, author = {M. Goldwasser and R. Motwani}, title = {Intractability of Assembly Sequencing: Unit Disks in the Plane}, booktitle = {{WADS} '97 Algorithms and Data Structures}, pages = {307--320}, editor = {F. Dehne and A. Rau-Chaplin and J.-R. Sack and R. Tamassia}, publisher = {Springer-Verlag}, address = {Berlin}, note = {Lecture Notes in Computer Science, 1272}, year = {1997} } @book{GolVan96, author = {G. H. Golub and C. F. Van Loan}, title = {Matrix Computations (3rd ed)}, publisher = {Johns Hopkins University Press}, address = {Baltimore, MD}, year = {1996} } @incollection{GonGuiLatLavLinMotTom98, author = {H. H. {Gonz\'alez-Ba\~nos} and L. Guibas and J.-C. Latombe and S. M. LaValle and D. Lin and R. Motwani and C. Tomasi}, title = {Motion Planning with Visibility Constraints: Building Autonomous Observers}, booktitle = {Proceedings Eighth International Symposium on Robotics Research}, pages = {95--101}, editor = {Y. Shirai and S. Hirose}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1998} } @inproceedings{GonLeeLat02, author = {H. H. Gonz\'alez-Ba{\~{n}}os and C.-Y. Lee and J.-C. Latombe}, title = {Real-time combinatorial tracking of a target moving unpredictably among obstacles}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2002} } @article{GonRof85, author = {R. Gonzalez and E. Rofman}, title = {On deterministic control problems: {A}n approximation procedure for the optimal cost, parts {I, II}}, journal = {SIAM Journal on Control \& Optimization}, volume = {23}, pages = {242--285}, year = {1985} } @book{GooOro04, author = {J. E. Goodman and J. O'Rourke (eds)}, title = {Handbook of Discrete and Computational Geometry, 2nd Ed.}, publisher = {Chapman and Hall/CRC Press}, address = {New York}, year = {2004} } @book{GooTam02, author = {M. T. Goodrich and R. Tammasia}, title = {Algorithm Design: Foundations, Analysis, and Internet Examples}, publisher = {Wiley}, address = {New York}, year = {2002} } @book{Gos67, author = {B. R. Gossick}, title = {Hamilton's Principle and Physical Systems}, publisher = {Academic}, address = {New York}, year = {1967} } @inproceedings{GotLinMan96, author = {S. Gottschalk and M. C. Lin and D. Manocha}, title = {OBBTREE: A Hierarchical Structure for Rapid Interference Detection}, booktitle = {Proceedings ACM SIGGRAPH}, year = {1996} } @inproceedings{GouWhi62, author = {V. E. Gough and S. G. Whitehall}, title = {Universal Tyre Test Machine}, booktitle = {Proceedings 9th International Technical Congress F.I.S.I.T.A.}, month = may, year = {1962} } @article{GriAke05, author = {E. J. Griffith and S. Akella}, title = {Coordinating Multiple Droplets in Planar Array Digital Microfluidic Systems}, journal = {International Journal of Robotics Research}, volume = {24}, number = {11}, pages = {933--949}, year = {2005} } @book{GroNerRavRis93, author = {R. Grossman and A. Nerode and A. Ravn and H. Rischel (eds)}, title = {Hybrid Systems}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1993} } @inproceedings{GuiSei86, author = {L. Guibas and R. Seidel}, title = {Computing Convolution by Reciprocal Search}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {90--99}, year = {1986} } @article{GuiSto85, author = {L. Guibas and J. Stolfi}, title = {Primitives for the Manipulation of General Subdivisions and the Computation of {V}oronoi Diagrams}, journal = {ACM Transactions on Graphics}, volume = {4}, number = {2}, pages = {74--123}, year = {1985} } @inproceedings{GuiHsuZha99, author = {L. J. Guibas and D. Hsu and L. Zhang}, title = {{H-Walk}: Hierarchical distance computation for moving convex bodies}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {265--273}, year = {1999} } @article{GuiLatLavLinMot99, author = {L. J. Guibas and J.-C. Latombe and S. M. LaValle and D. Lin and R. Motwani}, title = {Visibility-Based Pursuit-Evasion in a Polygonal Environment}, journal = {International Journal of Computational Geometry and Applications}, volume = {9}, number = {5}, pages = {471--494}, year = {1999} } @incollection{GuiMotRag95, author = {L. J. Guibas and R. Motwani and P. Raghavan}, title = {The Robot Localization Problem}, booktitle = {Algorithmic Foundations of Robotics}, pages = {269--282}, editor = {K. Goldberg and D. Halperin and J.-C. Latombe and R. Wilson}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1995} } @inproceedings{GuiTovLav04, author = {L. Guilamo and B. Tovar and S. M. LaValle}, title = {Pursuit-evasion in an Unknown Environment Using Gap Navigation Trees}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2004} } @article{GupGuo95, author = {K. Gupta and Z. Guo}, title = {Motion Planning with many degrees of freedom: {S}equential search with backtracking}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {6}, number = {11}, pages = {897--906}, year = {1995} } @article{GupBouKimKri98, author = {S. K. Gupta and D. A. Bourne and K. Kim and S. S. Krishnan}, title = {Automated Process Planning for Robotic Sheet Metal Bending Operations}, journal = {Journal of Manufacturing Systems}, volume = {17}, number = {5}, pages = {338--360}, year = {1998} } @inproceedings{Gur92, author = {L. Gurvits}, title = {Averaging approach to nonholonomic motion planning}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2541--2546}, year = {1992} } @article{GutWeiNeb01, author = {J.-S. Gutmann and T. Weigel and B. Nebel}, title = {A fast, accurate, and robust method for self-localization in polygonal environments using laser-range-finders}, journal = {Advanced Robotics}, volume = {14}, number = {8}, pages = {651--668}, year = {2001} } @book{Haj75, author = {O. H\'{a}jek}, title = {Pursuit Games}, publisher = {Academic}, address = {New York}, year = {1975} } @article{Haj90, author = {K. Haji-Ghassemi}, title = {On Differential Games of Fixed Duration with Phase Coordinate Restrictions on One Player}, journal = {SIAM Journal on Control \& Optimization}, volume = {28}, number = {3}, pages = {624--652}, month = may, year = {1990} } @incollection{Hal67, author = {H. Halkin}, title = {Mathematical Foundation of System Optimization}, booktitle = {Topics in Optimization}, editor = {G. Leitman}, publisher = {Academic}, address = {New York}, year = {1967} } @book{Hal50, author = {P. R. Halmos}, title = {Measure Theory}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1974} } @incollection{Hal04, author = {D. Halperin}, title = {Arrangements}, booktitle = {Handbook of Discrete and Computational Geometry, 2nd Ed.}, pages = {529--562}, editor = {J. E. Goodman and J. O'Rourke}, publisher = {Chapman and Hall/CRC Press}, address = {New York}, year = {2004} } @inproceedings{HalLatWil98, author = {D. Halperin and J.-C. Latombe and R. H. Wilson}, title = {A general framework for assembly planning: the motion space approach}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {9--18}, year = {1998} } @article{HalSha96, author = {D. Halperin and M. Sharir}, title = {A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment}, journal = {Discrete and Computational Geometry}, volume = {16}, pages = {121--134}, year = {1996} } @inproceedings{HalWil95, author = {D. Halperin and R. Wilson}, title = {Assembly partitioning along simple paths: the case of multiple translations}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1585--1592}, year = {1995} } @article{Hal60, author = {J. H. Halton}, title = {On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals}, journal = {Numerische Mathematik}, volume = {2}, pages = {84--90}, year = {1960} } @article{Ham60, author = {J. M. Hammersley}, title = {{Monte-Carlo} methods for solving multivariable problems}, journal = {Annals of the New York Academy of Science}, volume = {86}, pages = {844--874}, year = {1960} } @incollection{HanAma01, author = {L. Han and N. M. Amato}, title = {A Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems}, booktitle = {Algorithmic and Computational Robotics: {N}ew Directions}, pages = {233--246}, editor = {B. R. Donald and K. M. Lynch and D. Rus}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {2001} } @book{HarNet97, author = {H. Harrison and T. Nettleton}, title = {Advanced Engineering Dynamics}, publisher = {Elsevier}, address = {New York}, year = {1997} } @article{HarDen55, author = {R. S. Hartenberg and J. Denavit}, title = {A kinematic notation for lower pair mechanisms based on matrices}, journal = {Journal of Applied Mechanics}, volume = {77}, pages = {215--221}, year = {1955} } @book{HarDen64, author = {R. S. Hartenberg and J. Denavit}, title = {Kinematic Synthesis of Linkages}, publisher = {McGraw-Hill}, address = {New York}, year = {1964} } @phdthesis{Har05, author = {J. W. Hartmann}, title = {Counter-Intuitive Behavior in Locally Optimal Solar Sail Escape Trajectories}, number = {}, address = {Urbana, IL}, school = {University of Illinois}, department = {Department of Aeronautical and Astronautical Engineering}, month = may, year = {2005} } @inproceedings{HarCovPru04, author = {J. W. Hartmann and V. L. Coverstone and J. E. Prussing}, title = {Optimal Counter-Intuitive Solar Sail Escape Trajectories}, booktitle = {Proceedings AIAA/AAS Space Flight Mechanics Conference}, note = {Paper AAS 04-279}, year = {2004} } @book{Har77, author = {R. Hartshorne}, title = {Algebraic Geometry}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1977} } @book{Hat02, author = {A. Hatcher}, title = {Algebraic Topology}, publisher = {Cambridge University Press}, address = {Cambridge, U.K.}, note = {Available at http://www.math.cornell.edu/$\sim$hatcher/AT/ATpage.html}, year = {2002} } @book{Hea02, author = {M. T. Heath}, title = {Scientific Computing: An Introductory Survey, 2nd Ed.}, publisher = {McGraw-Hill}, address = {New York}, year = {2002} } @inproceedings{HeiJacCanPad90, author = {G. Heinzinger and P. Jacobs and J. Canny and B. Paden}, title = {Time-Optimal Trajectories for a Robotic Manipulator: A Provably Good Approximation Algorithm}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {150--155}, address = {Cincinnati, OH}, year = {1990} } @article{HerLunsul84, author = {H. Hermes and A. Lundell and D. Sullivan}, title = {Nilpotent bases for distributions and control systems}, journal = {Journal of Differential Equations}, volume = {55}, number = {3}, pages = {385--400}, year = {1984} } @inproceedings{HerSur95, author = {J. Hershberger and S. Suri}, title = {Efficient Computation of {E}uclidean shortest paths in the plane}, booktitle = {Proceedings IEEE Symposium on Foundations of Computer Science}, pages = {508--517}, year = {1995} } @article{HerTiwLum96, author = {S. Hert and S. Tiwari and V. Lumelsky}, title = {A Terrain-Covering Algorithm for an {AUV}}, journal = {Autonomous Robots}, volume = {3}, pages = {91--119}, year = {1996} } @incollection{Hic98, author = {F. J. Hickernell}, title = {Lattice Rules: {H}ow Well Do They Measure Up?}, booktitle = {Random and Quasi-Random Point Sets}, pages = {109--166}, editor = {P. Bickel}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1998} } @article{HicHonLecLem00, author = {F. J. Hickernell and H. S. Hong and P. L'Ecuyer and C. Lemieux}, title = {Extensible Lattice Sequences For Quasi-Monte Carlo Quadrature}, journal = {SIAM Journal on Scientific Computing}, volume = {22}, pages = {1117--1138}, year = {2000} } @inproceedings{HinKni88, author = {R. Hinkel and T. Knieriemen}, title = {Environment perception with a laser radar in a fast moving robot}, booktitle = {Proceedings Symposium on Robot Control}, pages = {68.1--68.7}, address = {Karlsruhe, Germany}, year = {1988} } @inproceedings{HirKitYos05, author = {Y. Hirano and K. Kitahama and S. Yoshizawa}, title = {Image-Based Object Recognition and Dextrous Hand/Arm Motion Planning Using {RRT}s for Grasping in Cluttered Scene}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2005} } @book{Hir94, author = {M. W. Hirsch}, title = {Differential Topology}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1994} } @inproceedings{HoChu72, author = {Y.-C. Ho and K.-C. Chu}, title = {Team Decision Theory and Information Structures in Optimal Control Problems-{Part I}}, booktitle = {IEEE Transactions on Automatic Control}, pages = {15--22}, year = {1972} } @book{HocYou61, author = {J. G. Hocking and G. S. Young}, title = {Topology}, publisher = {Dover}, address = {New York}, year = {1988} } @incollection{HodWoo98, author = {J. K. Hodgins and W. L. Wooten}, title = {Animating Human Athletes}, booktitle = {Proceedings International Symposium on Robotics Research}, pages = {356--367}, editor = {Y. Shirai and S. Hirose}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1998} } @inproceedings{Hof89b, author = {R. L. Hoffman}, title = {Automated assembly in a {CSG} domain}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {210--215}, year = {1989} } @book{Hof89, author = {C. M. Hoffmann}, title = {Geometric and Solid Modeling}, publisher = {Morgan Kaufmann}, address = {San Francisco, CA}, year = {1989} } @inproceedings{HolKav00, author = {C. Holleman and L. E. Kavraki}, title = {A framework for using the workspace medial axis in {PRM} planners}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1408--1413}, year = {2000} } @techreport{Hol83a, author = {J. Hollerbach}, title = {Dynamic Scaling of Manipulator Trajectories}, institution = {MIT A.I. Lab Memo 700}, year = {1983} } @inproceedings{Hol83b, author = {J. Hollerbach}, title = {Dynamic scaling of manipulator trajectories}, booktitle = {Proceedings American Control Conference}, pages = {752--756}, year = {1983} } @article{HomSan91b, author = {L. S. {Homem~de~Mello} and A. C. Sanderson}, title = {Representations of Mechanical Assembly Sequences}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {7}, number = {2}, pages = {211--227}, year = {1991} } @book{HooStu04, author = {H. H. Hoos and T. {St\"utzle}}, title = {Stochastic Local Search: Foundations and Applications}, publisher = {Morgan Kaufmann}, address = {San Francisco}, year = {2004} } @incollection{HopJosWhi87, author = {J. Hopcroft and D. Joseph and S. Whitesides}, title = {Movement Problems for 2-Dimensional Linkages}, booktitle = {Planning, Geometry, and Complexity of Robot Motion}, pages = {282--329}, editor = {J .T .Schwartz and M. Sharir and J. Hopcroft}, publisher = {Ablex}, address = {Norwood, NJ}, year = {1987} } @article{HopSchSha84, author = {J. E. Hopcroft and J. T. Schwartz and M. Sharir}, title = {On the complexity of motion planning for multiple independent objects: {PSPACE}-hardness of the ``warehouseman's problem''}, journal = {International Journal of Robotics Research}, volume = {3}, number = {4}, pages = {76--88}, year = {1984} } @book{HopUllMot00, author = {J. E. Hopcroft and J. D. Ullman and R. Motwani}, title = {Introduction to Automata Theory, Languages, and Computation}, publisher = {Addison-Wesley}, address = {Reading, MA}, year = {2000} } @inproceedings{HorSchTol94, author = {T. Horsch and F. Schwarz and H. Tolle}, title = {Motion Planning for Many Degrees of Freedom: Random Reflections at {C}-Space Obstacles}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {3318--3323}, address = {San Diego, CA}, month = apr, year = {1994} } @article{HowDah02, author = {A. E. Howe and E. Dahlman}, title = {A critical assessment of benchmark comparison in planning}, journal = {Journal of Artificial Intelligence Research}, pages = {1--33}, year = {2002} } @inproceedings{HsuJiaReiSun03, author = {D. Hsu and T. Jiang and J. Reif and Z. Sun}, title = {The Bridge Test for Sampling Narrow Passages with Probabilistic Roadmap Planners}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2003} } @incollection{HsuKinLatRoc01, author = {D. Hsu and R. Kindel and J-C. Latombe and S. Rock}, title = {Randomized Kinodynamic Motion Planning with Moving Obstacles}, booktitle = {Algorithmic and Computational Robotics: {N}ew Directions}, editor = {B. R. Donald and K. M. Lynch and D. Rus}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {2001} } @article{HsuLatMot99, author = {D. Hsu and J.-C. Latombe and R. Motwani}, title = {Path Planning in Expansive Configuration Spaces}, journal = {International Journal Computational Geometry \& Applications}, volume = {4}, pages = {495--512}, year = {1999} } @inproceedings{Hua01, author = {W. Huang}, title = {Optimal Line-sweep-based Decompositions for Coverage Algorithms}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {27--32}, year = {2001} } @book{Hun84, author = {T. W. Hungerford}, title = {Algebra}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1984} } @article{HutHagCor96, author = {S. A. Hutchinson and G. D. Hager and P. I. Corke}, title = {A Tutorial on Visual Servo Control}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {12}, number = {5}, pages = {651--670}, month = oct, year = {1996} } @book{Hut05, author = {M. Hutter}, title = {Universal Artificial Intelligence}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2005} } @article{HwaAhu92b, author = {Y. K. Hwang and N. Ahuja}, title = {Gross Motion Planning--{A} Survey}, journal = {ACM Computing Surveys}, volume = {24}, number = {3}, pages = {219--291}, month = sep, year = {1992} } @inproceedings{IanLyn03, author = {S. Iannitti and K. M. Lynch}, title = {Exact minimum control switch motion planning for the snakeboard}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2003} } @article{IckRotWelYap92, author = {C. Icking and G. Rote and E. Welzl and C.-K. Yap}, title = {Shortest paths for line segments}, journal = {Algorithmica}, volume = {10}, pages = {182--200}, year = {1992} } @incollection{Ind04, author = {P. Indyk}, title = {Nearest Neighbors in High-Dimensional Spaces}, booktitle = {Handbook of Discrete and Computational Geometry, 2nd Ed.}, pages = {877--892}, editor = {J. E. Goodman and J. O'Rourke}, publisher = {Chapman and Hall/CRC Press}, address = {New York}, year = {2004} } @inproceedings{IndMot98, author = {P. Indyk and R. Motwani}, title = {Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality}, booktitle = {Proceedings ACM Symposium on Theory of Computing}, pages = {604--613}, year = {1998} } @book{Isa65, author = {R. Isaacs}, title = {Differential Games}, publisher = {Wiley}, address = {New York}, year = {1965} } @book{Isi89, author = {A. Isidori}, title = {Nonlinear Control Systems, 2nd Ed.}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1989} } @inproceedings{Ist02, author = {P. Isto}, title = {Constructing Probabilistic Roadmaps with Powerful Local Planning and Path Optimization}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {2323--2328}, year = {2002} } @inproceedings{Jac91, author = {G. Jacob}, title = {Lyndon discretization and exact motion planning}, booktitle = {Proceedings European Control Conference}, year = {1991} } @inproceedings{JacFedSlo97, author = {H. Jacob and S. Feder and J. Slotine}, title = {Real-Time Path Planning using Harmonic Potential Functions in Dynamic Environment}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {874--881}, year = {1997} } @inproceedings{JacCan89, author = {P. Jacobs and J. Canny}, title = {Planning Smooth Paths for Mobile Robots}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2--7}, year = {1989} } @phdthesis{Jen01, author = {P. Jensfelt}, title = {Approaches to Mobile Robot Localization}, address = {Stockholm, Sweden}, school = {Royal Institute of Technology (KTH)}, department = {Department of Signals, Sensors, and Systems}, year = {2001} } @article{JenChr01, author = {P. Jensfelt and H. I. Christensen}, title = {Pose tracking using laser scanning and minimalistic environmental models}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {17}, number = {2}, pages = {138--147}, year = {2001} } @article{JenKri01, author = {P. Jensfelt and S. Kristensen}, title = {Active global localisation for a mobile robot using multiple hypothesis tracking}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {17}, number = {5}, pages = {748--760}, month = oct, year = {2001} } @article{JiXia01, author = {X. Ji and J. Xiao}, title = {Planning motion compliant to complex contact states}, journal = {International Journal of Robotics Research}, volume = {20}, number = {6}, pages = {446--465}, year = {2001} } @article{Jia04, author = {Y.-B. Jia}, title = {Computation on parametric curves with an application in grasping}, journal = {International Journal of Robotics Research}, volume = {23}, number = {7-8}, pages = {825--855}, year = {2004} } @incollection{JimThoTor98, author = {P. Jim\'enez and F. Thomas and C. Torras}, title = {Collision Detection Algorithms for Motion Planning}, booktitle = {Robot Motion Planning and Control}, pages = {1--53}, editor = {J.-P. Laumond}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1998} } @article{JorSte99, author = {D. Jordan and M. Steiner}, title = {Configuration Spaces of Mechanical Linkages}, journal = {Discrete and Computational Geometry}, volume = {22}, pages = {297--315}, year = {1999} } @inproceedings{JosPla85, author = {D. A. Joseph and W. H. Plantiga}, title = {On the Complexity of Reachability and Motion Planning Questions}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {62--66}, year = {1985} } @article{Jur93, author = {V. Jurdjevic}, title = {The geometry of the plate-ball problem}, journal = {Archives for Rational Mechanics and Analysis}, volume = {124}, pages = {305--328}, year = {1993} } @book{Jur97, author = {V. Jurdjevic}, title = {Geometric Control Theory}, publisher = {Cambridge University Press}, address = {Cambridge, U.K.}, year = {1997} } @article{GupZhu95, author = {K.~Gupta and X.~Zhu}, title = {Practical motion planning for many degrees of freedom: {A} novel approach within sequential framework}, journal = {Journal of Robotic Systems}, volume = {2}, number = {12}, pages = {105--118}, year = {1995} } @inproceedings{KaeCasKur96, author = {L. P. Kaelbling and A. Cassandra and J. Kurien}, title = {Acting under uncertainty: {D}iscrete {B}ayesian models for mobile robot navigation}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {963--972}, year = {1996} } @article{KaeLitCas98, author = {L. P. Kaelbling and M. L. Littman and A. R. Cassandra}, title = {Planning and Acting in Partially Observable Stochastic Domains}, journal = {Artificial Intelligence Journal}, volume = {101}, year = {1998} } @inproceedings{KagKufNisOkaIna03, author = {S. Kagami and J. Kuffner and K. Nishiwaki and K. Okada M. Inaba}, title = {Humanoid Arm Motion Planning using Stereo Vision and {RRT} Search}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2003} } @book{Kah95, author = {D. W. Kahn}, title = {Topology: An Introduction to the Point-Set and Algebraic Areas}, publisher = {Dover}, address = {New York}, year = {1995} } @article{KaiKai97, author = {H. Kaindl and G. Kainz}, title = {Bidirectional Heuristic Search Reconsidered}, journal = {Journal of Artificial Intelligence Research}, pages = {283--317}, month = dec, year = {1997} } @article{KalAubAbaTha03, author = {M. Kallmann and A. Aubel and T. Abaci and D. Thalmann}, title = {Planning Collision-Free Reaching Motions for Interactive Object Manipulation and Grasping}, journal = {Eurographics}, volume = {22}, number = {3}, year = {2003} } @inproceedings{KalMat04, author = {M. Kallmann and M. Mataric}, title = {Motion Planning Using Dynamic Roadmaps}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2004} } @article{Kal60, author = {R. Kalman}, title = {A new approach to linear filtering and prediction problems}, journal = {Transactions of the ASME, Journal of Basic Engineering}, volume = {82}, pages = {35--45}, year = {1960} } @article{KalHoNar63, author = {R. E. Kalman and Y.-C. Ho and K. S. Narendra}, title = {Controllability of Dynamical Systems}, journal = {Contributions to Differential Equations}, volume = {1}, pages = {189--213}, year = {1963} } @book{KalWhi86, author = {M. H. Kalos and P. A. Whitlock}, title = {Monte Carlo Methods}, publisher = {Wiley}, address = {New York}, year = {1986} } @article{KamYamSuz06, author = {T. Kameda and M. Yamashita and I. Suzuki}, title = {On-line polygon search by a seven-state boundary 1-searcher}, journal = {IEEE Transactions on Robotics}, note = {To appear}, year = {2006} } @article{KamRiv97, author = {I. Kamon and E. Rivlin}, title = {Sensory-Based Motion Planning with Global Proofs}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {13}, number = {6}, pages = {814--822}, month = dec, year = {1997} } @inproceedings{KamRivRim99, author = {I. Kamon and E. Rivlin and E. Rimon}, title = {Range-Sensor Based Navigation in Three Dimensions}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {1999} } @article{KanZuc86, author = {K. Kant and S. W. Zucker}, title = {Toward Efficient Trajectory Planning: The Path-Velocity Decomposition}, journal = {International Journal of Robotics Research}, volume = {5}, number = {3}, pages = {72--89}, year = {1986} } @inproceedings{KaoReiTat93, author = {M.-Y. Kao and J. H. Reif and S. R. Tate}, title = {Searching in an unknown environment: {A}n optimal randomized algorithm for the Cow-Path problem}, booktitle = {{SODA}: {ACM}-{SIAM} Symposium on Discrete Algorithms}, pages = {441--447}, year = {1993} } @book{Kap84, author = {W. Kaplan}, title = {Advanced Calculus}, publisher = {Addison-Wesley}, address = {Reading, MA}, year = {1984} } @inproceedings{KarBul01, author = {T. Karatas and F. Bullo}, title = {Randomized Searches and Nonlinear Programming in Trajectory Planning}, booktitle = {IEEE Conference on Decision and Control}, year = {2001} } @inproceedings{Kar92, author = {R. M. Karp}, title = {On-line Algorithms Versus Off-line Algorithms: {H}ow Much is it Worth to Know the Future?}, booktitle = {Proceedings World Computer Congress}, year = {1992} } @book{Kau95, author = {L. Kauffman}, title = {Knots and Applications}, publisher = {World Scientific}, address = {River Edge, NJ}, year = {1995} } @inproceedings{KauMcaSel96, author = {H. Kautz and D. McAllester and B. Selman}, title = {Encoding Plans in Propositional Logic}, booktitle = {Proceedings International Conference on Knowledge Representation and Reasoning}, year = {1996} } @article{Kav95, author = {L. E. Kavraki}, title = {Computation of Configuration-Space Obstacles Using the {F}ast {F}ourier {T}ransform}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {11}, number = {3}, pages = {408--413}, year = {1995} } @incollection{Kav97, author = {L. E. Kavraki}, title = {Geometry and the Discovery of New Ligands}, booktitle = {Algorithms for Robotic Motion and Manipulation}, pages = {435--445}, editor = {J.-P. Laumond and M. H. Overmars}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1997} } @article{KavKol95, author = {L. E. Kavraki and M. Kolountzakis}, title = {Partitioning a Planar Assembly into Two Connected Parts is {NP}-complete}, journal = {Information Processing Letters}, volume = {55}, number = {3}, pages = {159--165}, year = {1995} } @article{KavSveLatOve96, author = {L. E. Kavraki and P. Svestka and J.-C. Latombe and M. H. Overmars}, title = {Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {12}, number = {4}, pages = {566--580}, month = jun, year = {1996} } @article{KeOro88, author = {Y. Ke and J. O'Rourke}, title = {Lower bounds on moving a ladder in two and three dimensions}, journal = {Discrete and Computational Geometry}, volume = {3}, pages = {197--217}, year = {1988} } @article{KedLivPacSha86, author = {K. Kedem and R. Livne and J. Pach and M. Sharir}, title = {On the union of {J}ordan regions and collision-free translational motion amidst polygonal obstacles}, journal = {Discrete and Computational Geometry}, volume = {1}, pages = {59--71}, year = {1986} } @incollection{Kei00, author = {J. M. Keil}, title = {Polygon Decomposition}, booktitle = {Handbook on Computational Geometry}, editor = {J. R. Sack and J. Urrutia}, publisher = {Elsevier}, address = {New York}, year = {2000} } @article{KelNag03, author = {A. Kelly and B. Nagy}, title = {Reactive Nonholonomic Trajectory Generation via Parametric Optimal Control}, journal = {International Journal of Robotics Research}, volume = {22}, number = {7-8}, pages = {583--601}, year = {2003} } @book{KenKee51, author = {J. F. Kenney and E. S. Keeping}, title = {Mathematics of Statistics, Part 2, 2nd ed.}, publisher = {Van Nostrand}, address = {Princeton, NJ}, year = {1951} } @inproceedings{Ket98, author = {L. Kettner}, title = {Designing a data structure for polyhedral surfaces}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {146--154}, year = {1998} } @book{Kha02, author = {H. K. Khalil}, title = {Nonlinear Systems}, publisher = {Macmillan}, address = {New York}, year = {2002} } @inproceedings{KhaKle86, author = {W. Khalil and J. F. Kleinfinger}, title = {A new geometric notation for open and closed-loop robots}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, volume = {3}, pages = {1174--1179}, year = {1986} } @phdthesis{Kha80, author = {O. Khatib}, title = {Commande dynamique dans l'espace op\'{e}rational des robots manipulateurs en pr\'{e}sence d'obstacles}, address = {France}, school = {Ecole Nationale de la Statistique et de l'Administration Economique}, year = {1980} } @article{Kha86, author = {O. Khatib}, title = {Real-Time Obstacle Avoidance for Manipulators and Mobile Robots}, journal = {International Journal of Robotics Research}, volume = {5}, number = {1}, pages = {90--98}, year = {1986} } @article{Kil01, author = {A. A. Kilin}, title = {The Dynamics of {Chaplygin} Ball: {T}he Qualitative and Computer Analysis}, journal = {Regular and Chaotic Dynamics}, volume = {6}, number = {3}, pages = {291--306}, year = {2001} } @inproceedings{KimOst03, author = {J. Kim and J. P. Ostrowski}, title = {Motion Planning of Aerial Robot using Rapidly-exploring Random Trees with Dynamic Constraints}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2003} } @techreport{KimKho90, author = {J.-O. Kim and P. Khosla}, title = {Real-time obstacle avoidance using harmonic potential functions}, address = {Pittsburgh, PA}, institution = {Carnegie Mellon University}, year = {1990} } @book{KimRou87, author = {K. H. Kim and F. W. Roush}, title = {Team Theory}, publisher = {Ellis Horwood Limited}, address = {Chichester, U.K.}, year = {1987} } @book{Kim91, author = {J. T. Kimbrell}, title = {Kinematic Analysis and Synthesis}, publisher = {McGraw-Hill}, address = {New York}, year = {1991} } @article{KimKirBru98, author = {R. Kimmel and N. Kiryati and A. M. Bruckstein}, title = {Multivalued Distance Maps for Motion Planning on Surfaces with Moving Obstacles}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {14}, number = {3}, pages = {427--435}, month = jun, year = {1998} } @article{KimSet98, author = {R. Kimmel and J. Sethian}, title = {Computing geodesic paths on manifolds}, journal = {Proceedings of the National Academy of Sciences, USA}, volume = {95}, number = {15}, pages = {8431--8435}, year = {1998} } @article{KimSet01, author = {R. Kimmel and J. Sethian}, title = {Optimal Algorithm for Shape from Shading and Path Planning}, journal = {Journal of Mathematical Imaging and Vision}, volume = {14}, number = {3}, pages = {234--244}, year = {2001} } @book{Kin93, author = {C. L. Kinsey}, title = {Topology of Surfaces}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1993} } @article{Kit96, author = {G. Kitagawa}, title = {Monte {C}arlo filter and smoother for {non-Gaussian} nonlinear state space models}, journal = {Journal of Computational and Graphical Statistics}, volume = {5}, number = {1}, year = {1996} } @techreport{Kle94, author = {J. M. Kleinberg}, title = {On-Line Algorithms for Robot Navigation and Server Problems}, number = {MIT/LCS/TR-641}, address = {Cambridge, MA}, institution = {MIT}, month = may, year = {1994} } @inproceedings{Kle97, author = {J. M. Kleinberg}, title = {Two algorithms for Nearest-Neighbor Search in High Dimensions}, booktitle = {Proceedings ACM Symposium on Theory of Computing}, pages = {599--608}, month = may, year = {1997} } @book{KluPanWil04, author = {S. A. Klugman and H. H. Panjer and G. E. Willmot}, title = {Loss Models: From Data to Decisions, 2nd Ed.}, publisher = {Wiley}, address = {New York}, year = {2004} } @book{Knu98, author = {D. E. Knuth}, title = {The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Ed.}, publisher = {Addison-Wesley}, address = {Reading, MA}, year = {1998} } @inproceedings{Kod87, author = {D. E. Koditschek}, title = {Exact robot navigation by means of potential functions: Some topological considerations}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1--6}, year = {1987} } @article{Kod94, author = {D. E. Koditschek}, title = {An Approach to Autonomous Robot Assembly}, journal = {Robotica}, volume = {12}, pages = {137--155}, year = {1994} } @inproceedings{KoeLik02, author = {S. Koenig and M. Likhachev}, title = {{$D^*$} Lite}, booktitle = {Proceedings AAAI National Conference on Artificial Intelligence}, pages = {476--483}, year = {2002} } @article{KogKonKufLat94, author = {Y. Koga and K. Kondo and J. Kuffner and J.-C. Latombe}, title = {Planning Motions with Intentions}, journal = {Proceedings ACM SIGGRAPH}, pages = {395--408}, year = {1994}, keywords = {manipulation planning} } @article{KolMegVon96, author = {D. Koller and N. Megiddo and B. von Stengel}, title = {Efficient Computation of Equilibria for Extensive Two-Person Games}, journal = {Games and Economic Behavior}, volume = {14}, pages = {247--259}, year = {1996} } @book{KolFom75, author = {A. N. Kolmogorov and S. V. Fomin}, title = {Introductory Real Analysis}, publisher = {Dover}, address = {New York}, year = {1975} } @inproceedings{Kol05, author = {V. Koltun}, title = {Pianos are not Flat: {R}igid Motion Planning in Three Dimensions}, booktitle = {Proceedings ACM-SIAM Symposium on Discrete Algorithms}, year = {2005} } @article{Kon91, author = {K. Kondo}, title = {Motion Planning with Six Degrees of Freedom by Multistrategic Bidirectional Heuristic Free-Space Enumeration}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {7}, number = {3}, pages = {267--277}, year = {1991} } @inproceedings{Kon99b, author = {K. Konolige}, title = {Markov localization using correlation}, booktitle = {Proceedings International Joint Conference on Artificial Intelligence}, year = {1999} } @incollection{Kor88, author = {R. E. Korf}, title = {Search: {A} Survey of Recent Results}, booktitle = {Exploring Artificial Intelligence: {S}urvey Talks from the National Conference on Artificial Intelligence}, editor = {H. E. Shrobe}, publisher = {Moran Kaufmann}, address = {San Francisco, CA}, year = {1988} } @incollection{Kor99, author = {R. E. Korf}, title = {Artificial Intelligence Search Algorithms}, booktitle = {Algorithms and Theory of Computation Handbook}, publisher = {CRC Press}, address = {Boca Raton, FL}, year = {1999} } @incollection{KotRusVorMcg98, author = {K. Kotay and D. Rus and M. Vora and C. McGray}, title = {The Self-reconfiguring Robotic Molecule: Design and Control Algorithms}, booktitle = {Robotics: The Algorithmic Perspective}, editor = {P. K. Agarwal and L. E. Kavraki and M. T. Mason}, publisher = {A.K. Peters}, address = {Natick, MA}, year = {1998} } @inproceedings{KovGle04, author = {L. Kovar and M. Gleicher}, title = {Automated Extraction and Parameterization of Motions in Large Data Sets}, booktitle = {Proceedings ACM SIGGRAPH}, year = {2004} } @inproceedings{KovGlePig02, author = {L. Kovar and M. Gleicher and F. Pighin}, title = {Motion Graphs}, booktitle = {Proceedings ACM SIGGRAPH}, year = {2002} } @book{KozDutWro03, author = {K. Kozlowski and P. Dutkiewicz and W. Wr\'oblewski}, title = {Modeling and Control of Robots}, publisher = {Wydawnictwo Naukowe PWN}, address = {Warsaw, Poland}, note = {In Polish}, year = {2003} } @techreport{KriTsa98, author = {P. S. Krishnaprasad and D. P. Tsakaris}, title = {Oscillations, {SE(2)}-Snakes and Motion Control: {A} Study of the Roller Racer}, institution = {Center for Dynamics and Control of Smart Structures, University of Maryland}, year = {1998} } @phdthesis{Kuf99, author = {J. J. Kuffner}, title = {Autonomous Agents for Real-time Animation}, address = {Stanford, CA}, school = {Stanford University}, department = {Department of Computer Science}, year = {1999} } @book{Kuf01, author = {J. J. Kuffner}, title = {Some Computed Examples [using RRT-Connect]}, publisher = {[Online]}, note = {Available at http://www.kuffner.org/james/plan/examples.html}, year = {2001} } @inproceedings{Kuf04, author = {J. J. Kuffner}, title = {Effective sampling and distance metrics for {3D} rigid body path planning}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2004} } @techreport{KufLav05, author = {J. J. Kuffner and S. M. LaValle}, title = {An Efficient Approach to Path Planning Using Balanced Bidirectional {RRT} Search}, number = {CMU-RI-TR-05-34}, address = {Pittsburgh, PA}, institution = {Robotics Institute, Carnegie Mellon University}, month = aug, year = {2005} } @inproceedings{KufNisKagInaIno03, author = {J. J. Kuffner and K. Nishiwaki and M. Inaba and H. Inoue}, title = {Motion Planning for Humanoid Robots}, booktitle = {Proceedings International Symposium on Robotics Research}, year = {2003} } @incollection{Kuh53, author = {H. W. Kuhn}, title = {Extensive games and the problem of information}, booktitle = {Contributions to the Theory of Games}, pages = {196--216}, editor = {H. W. Kuhn and A. W. Tucker}, publisher = {Princeton University Press}, address = {Princeton, NJ}, year = {1953} } @book{Kui02, author = {J. B. Kuipers}, title = {Quaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality}, publisher = {Princeton University Press}, address = {Princeton, NJ}, year = {2002} } @book{KumVar86, author = {P. R. Kumar and P. Varaiya}, title = {Stochastic Systems}, publisher = {Prentice-Hall}, address = {Englewood Cliffs, NJ}, year = {1986} } @article{Kus90, author = {H. J. Kushner}, title = {Numerical methods for continuous control problems in continuous time}, journal = {SIAM Journal on Control \& Optimization}, volume = {28}, pages = {999--1048}, year = {1990} } @book{KusCla78, author = {H. J. Kushner and D. S. Clark}, title = {Stochastic Approximation Methods for Constrained and Unconstrained Systems}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1978} } @book{KusDup92, author = {H. J. Kushner and P. G. Dupuis}, title = {Numerical Methods for Stochastic Control Problems in Continuous Time}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1992} } @inproceedings{KutDyeLum94, author = {K. N. Kutulakos and C. R. Dyer and V. J. Lumelsky}, title = {Provable Strategies for Vision-Guided Exploration in Three Dimensions}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1365--1371}, year = {1994} } @article{Kwa89, author = {J. B. H. Kwa}, title = {{BS}*: An Admissible Bidirectional Staged Heuristic Search Algorithm}, journal = {Artificial Intelligence Journal}, volume = {38}, pages = {95--109}, year = {1989} } @book{KwaSiv72, author = {H. Kwakernaak and R. Sivan}, title = {Linear Optimal Control Systems}, publisher = {Wiley}, address = {New York}, year = {1972} } @article{Gru97, author = {{L. Gr\"{u}ne}}, title = {An Adaptive Grid Scheme for the discrete {Hamilton-Jacobi-Bellman} Equation}, journal = {Numerische Mathematik}, volume = {75}, pages = {319--337}, year = {1997} } @inproceedings{LadKav02, author = {A. Ladd and L. E. Kavraki}, title = {Motion Planning for Knot Untangling}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, address = {Nice, France}, month = dec, year = {2002} } @inproceedings{LadKav04, author = {A. Ladd and L. E. Kavraki}, title = {Fast Exploration for Robots with Dynamics}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, address = {Zeist, The Netherlands}, month = jul, year = {2004} } @article{LadKav04b, author = {A. Ladd and L. E. Kavraki}, title = {Measure theoretic analysis of probabilistic path planning}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {20}, number = {2}, pages = {229--242}, year = {2004} } @inproceedings{LafSus91, author = {G. Laffierriere and H. J. Sussmann}, title = {Motion planning for controllable systems without drift}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {1991} } @article{LamBonLef04, author = {F. Lamiraux and D. Bonnafous and O. Lefebvre}, title = {Reactive path deformation for non-holonomic mobile robots}, journal = {IEEE Transactions on Robotics}, volume = {20}, number = {6}, pages = {967--977}, month = dec, year = {2004} } @inproceedings{LamFerVal04, author = {F. Lamiraux and E. Ferre and E. Vallee}, title = {Kinodynamic Motion Planning: Connecting Exploration Trees Using Trajectory Optimization Methods}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {3987--3992}, year = {2004} } @inproceedings{LamKav99, author = {F. Lamiraux and L. Kavraki}, title = {Path Planning for Elastic Plates Under Manipulation Constraints}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {151--156}, year = {1999} } @article{LamLau00, author = {F. Lamiraux and J.-P. Laumond}, title = {Flatness and small-time controllability of multibody mobile robots: {A}pplication to motion planning}, journal = {IEEE Transactions on Automatic Control}, volume = {45}, number = {10}, pages = {1878--1881}, month = apr, year = {2000} } @article{LamSekLau99, author = {F. Lamiraux and S. Sekhavat and J.-P. Laumond}, title = {Motion planning and control for {Hilare} pulling a trailer}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {15}, number = {4}, pages = {640--652}, month = aug, year = {1999} } @article{Lap93, author = {A. S. Lapaugh}, title = {Recontamination Does Not Help to Search a Graph}, journal = {Journal of the ACM}, volume = {40}, number = {2}, pages = {224--245}, month = apr, year = {1993} } @book{Lap12, author = {P.-S. Laplace}, title = {Th\'eorie Analityque des Probabilit\'es}, publisher = {Courceir, Paris}, year = {1812} } @article{Lar67, author = {R. E. Larson}, title = {A Survey of Dynamic Programming Computational Procedures}, journal = {IEEE Transactions on Automatic Control}, volume = {12}, number = {6}, pages = {767--774}, month = dec, year = {1967} } @book{LarCas82, author = {R. E. Larson and J. L. Casti}, title = {Principles of Dynamic Programming, Part {II}}, publisher = {Dekker}, address = {New York}, year = {1982} } @article{LarKec68, author = {R. E. Larson and W. G. Keckler}, title = {Optimum Adaptive Control in an Unknown Environment}, journal = {IEEE Transactions on Automatic Control}, volume = {13}, number = {4}, pages = {438--439}, month = aug, year = {1968} } @article{Las68, author = {J. P. LaSalle}, title = {Stability Theory for Ordinary Differential Equations}, journal = {Journal of Differential Equations}, volume = {4}, pages = {57--65}, year = {1968} } @book{LasMac95, author = {A. Lasota and M. C. Mackey}, title = {Chaos, Fractals, and Noise: {S}tochastic Aspects of Dynamics, 2nd Ed.}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1995} } @inproceedings{Lat91b, author = {J.-C. Latombe}, title = {A Fast Path Planner for a Car-Like Indoor Mobile Robot}, booktitle = {Proceedings AAAI National Conference on Artificial Intelligence}, pages = {659--665}, year = {1991} } @book{Lat91, author = {J.-C. Latombe}, title = {Robot Motion Planning}, publisher = {Kluwer}, address = {Boston, MA}, year = {1991} } @article{Lat99, author = {J.-C. Latombe}, title = {Motion Planning: {A} Journey of Robots, Molecules, Digital Actors, and Other Artifacts}, journal = {International Journal of Robotics Research}, volume = {18}, number = {11}, pages = {1119--1128}, year = {1999} } @article{LatLazShe91, author = {J.-C. Latombe and A. Lazanas and S. Shekhar}, title = {Robot motion planning with uncertainty in control and sensing}, journal = {Artificial Intelligence Journal}, volume = {52}, pages = {1--47}, year = {1991} } @inproceedings{LauKuf05, author = {M. Lau and J. J. Kuffner}, title = {Behavior Planning for Character Animation}, booktitle = {Proceedings Eurographics/SIGGRAPH Symposium on Computer Animation}, year = {2005} } @inproceedings{LauBur99, author = {S. L. Laubach and J. W. Burdick}, title = {An Autonomous Sensor-Based Path-Planning for Planetary Microrovers}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {1999} } @inproceedings{Lau86, author = {J.-P. Laumond}, title = {Trajectories for Mobile Robots with Kinematic and Environment Constraints}, booktitle = {Proceedings International Conference on Intelligent Autonomous Systems}, pages = {346--354}, year = {1986} } @article{Lau93b, author = {J.-P. Laumond}, title = {Controllability of a multibody mobile robot}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {9}, number = {6}, pages = {755--763}, month = dec, year = {1993} } @book{Lau98, author = {J.-P. Laumond}, title = {Robot Motion Planning and Control}, publisher = {Springer-Verlag}, address = {Berlin}, note = {Available online at http://www.laas.fr/$\sim$jpl/book.html}, year = {1998} } @incollection{LauSekLam98, author = {J.-P. Laumond and S. Sekhavat and F. Lamiraux}, title = {Guidelines in Nonholonomic Motion Planning for Mobile Robots}, booktitle = {Robot Motion Planning and Control}, pages = {1--53}, editor = {J.-P. Laumond}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1998} } @phdthesis{Lav95, author = {S. M. LaValle}, title = {A Game-Theoretic Framework for Robot Motion Planning}, number = {}, address = {Urbana, IL}, school = {University of Illinois}, department = {Department of Electrical and Computer Engineering}, month = jul, year = {1995} } @techreport{Lav98c, author = {S. M. LaValle}, title = {Rapidly-Exploring Random Trees: {A} New Tool for Path Planning}, number = {98-11}, institution = {Computer Science Dept., Iowa State University}, month = oct, year = {1998} } @article{Lav00, author = {S. M. LaValle}, title = {Robot Motion Planning: A Game-Theoretic Foundation}, journal = {Algorithmica}, volume = {26}, number = {3}, pages = {430--465}, year = {2000} } @article{LavBraLin04, author = {S. M. LaValle and M. S. Branicky and S. R. Lindemann}, title = {On the relationship between classical grid search and probabilistic roadmaps}, journal = {International Journal of Robotics Research}, volume = {23}, number = {7/8}, pages = {673--692}, month = {July/August}, year = {2004} } @article{LavFinKavLat00, author = {S. M. LaValle and P. Finn and L. Kavraki and J.-C. Latombe}, title = {A Randomized Kinematics-Based Approach to Pharmacophore-Constrained Conformational Search and Database Screening}, journal = {J. Computational Chemistry}, volume = {21}, number = {9}, pages = {731--747}, year = {2000} } @inproceedings{LavGonBecLat97, author = {S. M. LaValle and H. H. {Gonz\'alez-Ba\~{n}os} and C. Becker and J.-C. Latombe}, title = {Motion Strategies for Maintaining Visibility of a Moving Target}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, pages = {731--736}, year = {1997} } @article{LavHin01, author = {S. M. LaValle and J. Hinrichsen}, title = {Visibility-Based Pursuit-Evasion: The Case of Curved Environments}, journal = {IEEE Transactions on Robotics and Automation}, volume = {17}, number = {2}, pages = {196--201}, month = apr, year = {2001} } @inproceedings{LavHut94, author = {S. M. LaValle and S. A. Hutchinson}, title = {An Objective-based Stochastic Framework for Manipulation Planning}, booktitle = {Proceedings IEEE/RSJ/GI International Conference on Intelligent Robots and Systems}, pages = {1772--1779}, month = sep, year = {1994} } @article{LavHut98, author = {S. M. LaValle and S. A. Hutchinson}, title = {An Objective-Based Framework for Motion Planning under Sensing and Control Uncertainties}, journal = {International Journal of Robotics Research}, volume = {17}, number = {1}, pages = {19--42}, month = jan, year = {1998} } @article{LavHut98b, author = {S. M. LaValle and S. A. Hutchinson}, title = {Optimal Motion Planning for Multiple Robots Having Independent Goals}, journal = {IEEE Trans. on Robotics and Automation}, volume = {14}, number = {6}, pages = {912--925}, month = dec, year = {1998} } @article{LavKon01, author = {S. M. LaValle and P. Konkimalla}, title = {Algorithms for Computing Numerical Optimal Feedback Motion Strategies}, journal = {International Journal of Robotics Research}, volume = {20}, number = {9}, pages = {729--752}, month = sep, year = {2001} } @inproceedings{LavKuf99, author = {S. M. LaValle and J. J. Kuffner}, title = {Randomized Kinodynamic Planning}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, pages = {473--479}, year = {1999} } @inproceedings{LavKuf00, author = {S. M. LaValle and J. J. Kuffner}, title = {Rapidly-Exploring Random Trees: Progress and Prospects}, booktitle = {Proceedings Workshop on the Algorithmic Foundations of Robotics}, year = {2000} } @article{LavKuf01b, author = {S. M. LaValle and J. J. Kuffner}, title = {Randomized Kinodynamic Planning}, journal = {International Journal of Robotics Research}, volume = {20}, number = {5}, pages = {378--400}, month = may, year = {2001} } @incollection{LavKuf01, author = {S. M. LaValle and J. J. Kuffner}, title = {Rapidly-Exploring Random Trees: Progress and Prospects}, booktitle = {Algorithmic and Computational Robotics: New Directions}, pages = {293--308}, editor = {B. R. Donald and K. M. Lynch and D. Rus}, publisher = {A K Peters}, address = {Wellesley, MA}, year = {2001} } @inproceedings{LavLinGuiLatMot97, author = {S. M. LaValle and D. Lin and L. J. Guibas and J.-C. Latombe and R. Motwani}, title = {Finding an Unpredictable Target in a Workspace with Obstacles}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, pages = {737--742}, year = {1997} } @article{LavSha97, author = {S. M. LaValle and R. Sharma}, title = {On Motion Planning in Changing, Partially-Predictable Environments}, journal = {International Journal of Robotics Research}, volume = {16}, number = {6}, pages = {775--805}, month = dec, year = {1997} } @techreport{Laz01, author = {S. Lazebnik}, title = {Visibility-Based Pursuit Evasion in Three-Dimensional Environments}, number = {CVR TR 2001-01}, institution = {Beckman Institute, University of Illinois}, year = {2001} } @article{LeaKun92, author = {A. R. Leach and I. D. Kuntz}, title = {Conformational Analysis of Flexible Ligands in Macromolecular Receptor Sites}, journal = {Journal of Computational Chemistry}, volume = {13}, number = {6}, pages = {730--748}, year = {1992} } @article{LeeDry81, author = {D. T. Lee and R. L. Drysdale}, title = {Generalization of {Voronoi} Diagrams in the plane}, journal = {SIAM Journal on Computing}, volume = {10}, pages = {73--87}, year = {1981} } @inproceedings{LeeChaReiHodPol02, author = {J. Lee and J. Chai and P. S. A. Reitsma and J. K. Hodgins and N. S. Pollard}, title = {Interactive Control of Avatars with Human Motion Data}, booktitle = {Proceedings ACM SIGGRAPH}, year = {2002} } @inproceedings{LeeShiChw99, author = {J.-H. Lee and S. Y. Shin and K.-Y. Chwa}, title = {Visibility-based pursuit-evasions in a polygonal room with a door}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, year = {1999} } @inproceedings{Leh51, author = {D. H. Lehmer}, title = {Mathematical Methods in large-scale computing units}, booktitle = {Proceedings 2nd Symposium on Large-Scale Digital Computing Machinery}, pages = {141--146}, publisher = {Harvard University Press}, address = {Cambridge, MA}, year = {1951} } @article{LenReiDonGre90, author = {J. Lengyel and M. Reichert and B. R. Donald and D. P. Greenberg}, title = {Real-Time Robot Motion Planning Using Rasterizing Computer Graphics Hardware}, journal = {Computer Graphics}, volume = {24}, number = {4}, pages = {327--335}, month = aug, year = {1990} } @inproceedings{LenVel00, author = {S. Lenser and M. Veloso}, title = {Sensor resetting localization for poorly modelled mobile robots}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2000} } @article{LeoDurCox92, author = {J. Leonard and H. Durrant-Whyte and I. Cox}, title = {Dynamic Map Building for an Autonomous Mobile Robot}, journal = {International Journal of Robotics Research}, volume = {11}, number = {4}, pages = {89--96}, year = {1992} } @inproceedings{LeoKri93, author = {N. E. Leonard and P. S. Krishnaprasad}, title = {Averaging for Attitude Control and Motion Planning}, booktitle = {Proceedings IEEE Conference Decision \& Control}, pages = {3098--3104}, month = dec, year = {1993} } @article{LeoKri95, author = {N. E. Leonard and P. S. Krishnaprasad}, title = {Motion Control of Drift-Free Left-Invariant Systems on Lie Groups}, journal = {IEEE Transactions on Automatic Control}, volume = {40}, number = {9}, pages = {1539--1554}, year = {1995} } @article{LevSha87, author = {D. Leven and M. Sharir}, title = {An efficient and simple motion planning algorithm for a ladder moving in a 2-dimensional space amidst polygonal barriers}, journal = {Journal of Algorithms}, volume = {8}, pages = {192--215}, year = {1987} } @article{LevSha87b, author = {D. Leven and M. Sharir}, title = {Planning a purely translational motion for a convex object in two-dimensional space using generalized {Voronoi} diagrams}, journal = {Discrete and Computational Geometry}, volume = {2}, pages = {9--31}, year = {1987} } @article{LevHut02, author = {P. Leven and S. A. Hutchinson}, title = {Real-time path planning in changing environments}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {21}, number = {12}, pages = {999--1030}, month = dec, year = {2002} } @article{LevHut03, author = {P. Leven and S. A. Hutchinson}, title = {Using manipulability to bias sampling during the construction of probabilistic roadmaps}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {19}, number = {6}, pages = {1020--1026}, month = dec, year = {2003} } @inproceedings{LewOstBurMur94, author = {A. D. Lewis and J. P. Ostrowski and J. W. Burdick and R. M. Murray}, title = {Nonholonomic mechanics and locomotion: {T}he snakeboard example}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2391--2400}, year = {1994} } @book{LiVit97, author = {M. Li and P. Vitanyi}, title = {An Introduction to {K}olmogorov Complexity and Its Applications}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1997} } @inproceedings{LiShi02, author = {T.-Y. Li and Y.-C. Shie}, title = {An Incremental Learning Approach to Motion Planning with Roadmap Management}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2002} } @article{LiCan90, author = {Z. Li and J. F. Canny}, title = {Motion of two rigid bodies with rolling constraint}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {6}, number = {1}, pages = {62--72}, month = feb, year = {1990} } @book{LiCan93, author = {Z. Li and J. F. Canny}, title = {Nonholonomic Motion Planning}, publisher = {Kluwer}, address = {Boston, MA}, year = {1993} } @book{Lib03, author = {D. Liberzon}, title = {Switching in Systems and Control}, publisher = {{Birkh\"auser}}, address = {Boston, MA}, year = {2003} } @inproceedings{LieThoAma03, author = {J.-M. Lien and S. L. Thomas and N. M. Amato}, title = {A General Framework for Sampling on the Medial Axis of the Free Space}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2003} } @inproceedings{LinCan91, author = {M. C. Lin and J. F. Canny}, title = {Efficient algorithms for incremental distance computation}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {1991} } @incollection{LinMan04, author = {M. C. Lin and D. Manocha}, title = {Collision and Proximity Queries}, booktitle = {Handbook of Discrete and Computational Geometry, 2nd Ed.}, pages = {787--807}, editor = {J. E. Goodman and J. O'Rourke}, publisher = {Chapman and Hall/CRC Press}, address = {New York}, year = {2004} } @incollection{LinManCohGot97, author = {M. C. Lin and D. Manocha and J. Cohen and S. Gottschalk}, title = {Collision Detection: Algorithms and Applications}, booktitle = {Algorithms for Robotic Motion and Manipulation}, pages = {129--142}, editor = {J.-P. Laumond and M. H. Overmars}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1997} } @inproceedings{LinLav03, author = {S. R. Lindemann and S. M. LaValle}, title = {Incremental Low-Discrepancy Lattice Methods for Motion Planning}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, pages = {2920--2927}, year = {2003} } @incollection{LinLav03b, author = {S. R. Lindemann and S. M. LaValle}, title = {Current Issues in Sampling-Based Motion Planning}, booktitle = {Proceedings International Symposium on Robotics Research}, pages = {}, editor = {P. Dario and R. Chatila}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2004} } @inproceedings{LinLav04, author = {S. R. Lindemann and S. M. LaValle}, title = {Incrementally Reducing Dispersion by Increasing {V}oronoi Bias in {RRTs}}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, year = {2004} } @inproceedings{LinLav04b, author = {S. R. Lindemann and S. M. LaValle}, title = {Steps Toward Derandomizing {RRTs}}, booktitle = {IEEE Fourth International Workshop on Robot Motion and Control}, year = {2004} } @inproceedings{LinLav05, author = {S. R. Lindemann and S. M. LaValle}, title = {Smoothly Blending Vector Fields for Global Robot Navigation}, booktitle = {Proceedings IEEE Conference Decision \& Control}, pages = {3353--3559}, year = {2005} } @inproceedings{LinYerLav04, author = {S. R. Lindemann and A. Yershova and S. M. LaValle}, title = {Incremental Grid Sampling Strategies in Robotics}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, pages = {297--312}, year = {2004} } @inproceedings{Lin82, author = {A. Lingas}, title = {The Power of Non-Rectilinear Holes}, booktitle = {Proceedings 9th International Colloquium on Automata, Languange, and Programming}, pages = {369--383}, publisher = {Springer-Verlag}, note = {Lecture Notes in Computer Science, 140}, year = {1982} } @inproceedings{Lin04, author = {F. Lingelbach}, title = {Path planning using probabilistic cell decomposition}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2004} } @techreport{Lit94, author = {M. Littman}, title = {The Witness Algorithm: {S}olving Partially Observable {M}arkov decision processes}, number = {CS-94-40}, address = {Providence, RI}, institution = {Brown University}, year = {1994} } @inproceedings{LitCasKae95, author = {M. L. Littman and A. R. Cassandra and L. P. Kaelbling}, title = {Learning policies for partially-observable environments: {S}caling up}, booktitle = {Proceedings International Conference on Machine Learning}, pages = {362--370}, year = {1995} } @inproceedings{LiuPop02, author = {C. K. Liu and Z. Popovic}, title = {Synthesis of Complex Dynamic Character Motion From Simple Animations}, booktitle = {Proceedings ACM SIGGRAPH}, pages = {408--416}, year = {2002} } @article{LiuAri92, author = {Y. Liu and S. Arimoto}, title = {Path planning using a tangent graph for mobile robots among polygonal and curved obstacles}, journal = {International Journal of Robotics Research}, volume = {11}, number = {4}, pages = {376--382}, year = {1992} } @inproceedings{LoiKyr02, author = {S. G. Loizou and K. J. Kyriakopoulos}, title = {Closed Loop Navigation for Multiple Holonomic Vehicles}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2002} } @inproceedings{LoiKyr03, author = {S. G. Loizou and K. J. Kyriakopoulos}, title = {Closed Loop Navigation for Multiple Non-Holonomic Vehicles}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2003} } @inproceedings{LotSchHalLat02, author = {I. Lotan and F. Schwarzer and D. Halperin and J.-C. Latombe}, title = {Efficient maintenance and self-collision testing for kinematic chains}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {43--52}, year = {2002} } @inproceedings{LotVanDeaLat04, author = {I. Lotan and H. van den Bedem and A. M. Deacon and J.-C. Latombe}, title = {Computing protein structures from electron density maps: {T}he missing loop problem}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, year = {2004} } @article{Lov91, author = {W. S. Lovejoy}, title = {Computationally feasible bounds for partially observed {M}arkov decision processes}, journal = {Operations Research}, volume = {39}, number = {1}, pages = {162--175}, year = {1991} } @article{Loz81, author = {T. Lozano-P\'{e}rez}, title = {Automatic Planning of Manipulator Transfer Movements}, journal = {IEEE Transactions on Systems, Man, \& Cybernetics}, volume = {11}, number = {10}, pages = {681--698}, month = {}, year = {1981} } @article{Loz83, author = {T. Lozano-P\'{e}rez}, title = {Spatial Planning: A Configuration Space Approach}, journal = {IEEE Transactions on Computing}, volume = {C-32}, number = {2}, pages = {108--120}, month = {}, year = {1983} } @article{Loz87, author = {T. Lozano-P\'erez}, title = {A Simple Motion-Planning Algorithm for General Robot Manipulators}, journal = {IEEE Journal of Robotics \& Automation}, volume = {RA-3}, number = {3}, pages = {224--238}, month = jun, year = {1987} } @article{LozMasTay84, author = {T. Lozano-P\'{e}rez and M. T. Mason and R. H. Taylor}, title = {Automatic Synthesis of Fine-Motion Strategies for Robots}, journal = {International Journal of Robotics Research}, volume = {3}, number = {1}, pages = {3--24}, year = {1984} } @article{LozWes79, author = {T. Lozano-P\'{e}rez and M. A. Wesley}, title = {An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles}, journal = {Communications of the ACM}, volume = {22}, number = {10}, pages = {560--570}, year = {1979} } @article{LuAke00, author = {L. Lu and S. Akella}, title = {Folding Cartons with Fixtures: {A} Motion Planning Approach}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {16}, number = {4}, pages = {346--356}, month = aug, year = {2000} } @article{LuHan98, author = {P. Lu and J. M. Hanson}, title = {Entry Guidance for the {X-33} Vehicle}, journal = {Journal of Spacecraft and Rockets}, volume = {35}, number = {3}, pages = {342--349}, year = {1998} } @incollection{DelOriSam98, author = {A. De Luca and G. Oriolo and C. Samson}, title = {Feedback Control of a Nonholonomic Car-Like Robot}, booktitle = {Robot Motion Planning and Control}, pages = {171--253}, editor = {J.-P. Laumond}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1998} } @book{Lue73, author = {D. G. Luenberger}, title = {Introduction to Linear and Nonlinear Programming}, publisher = {Wiley}, address = {New York}, year = {1973} } @article{LumHar97, author = {V. J. Lumelsky and K. R. Harinarayan}, title = {Decentralized Motion Planning for Multiple Mobile Robots: {T}he Cocktail Party Model}, journal = {Autonomous Robots}, volume = {4}, number = {1}, pages = {121--135}, year = {1997} } @article{LumSke90, author = {V. J. Lumelsky and T. Skewis}, title = {Incorporating Range Sensing in the Robot Navigation Function}, journal = {IEEE Transactions on Systems, Man, \& Cybernetics}, volume = {20}, number = {5}, pages = {1058--1069}, year = {1990} } @article{LumSte87, author = {V. J. Lumelsky and A. A. Stepanov}, title = {Path Planning Strategies for a Point Mobile Automaton Moving Amidst Unknown Obstacles of Arbitrary Shape}, journal = {Algorithmica}, volume = {2}, pages = {403--430}, year = {1987} } @inproceedings{LumTiw94, author = {V. J. Lumelsky and S. Tiwari}, title = {An Algorithm for Maze Searching with Azimuth Input}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {111--116}, year = {1994} } @article{Lyn99, author = {K. M. Lynch}, title = {Controllability of a planar body with unilateral thrusters}, journal = {IEEE Transactions on Automatic Control}, volume = {44}, number = {6}, pages = {1206--1211}, year = {1999} } @article{LynMas95, author = {K. M. Lynch and M. T. Mason}, title = {Pulling by Pushing, Slip with Infinite Friction, and Perfectly Rough Surfaces}, journal = {International Journal of Robotics Research}, volume = {14}, number = {2}, pages = {174--183}, year = {1995} } @article{LynMas96, author = {K. M. Lynch and M. T. Mason}, title = {Stable pushing: Mechanics, controllability, and planning}, journal = {International Journal of Robotics Research}, volume = {15}, number = {6}, pages = {533--556}, year = {1996} } @article{LynShiAraTan00, author = {K. M. Lynch and N. Shiroma and H. Arai and K. Tanie}, title = {Collision free trajectory planning for a 3-dof robot with a passive joint}, journal = {International Journal of Robotics Research}, volume = {19}, number = {12}, pages = {1171--1184}, year = {2000} } @phdthesis{Yim94, author = {M.~Yim}, title = {Locomotion with a Unit-Modular Reconfigurable Robot}, address = {Stanford, CA}, school = {Stanford University}, note = {Stanford Technical Report STAN-CS-94-1536}, month = dec, year = {1994} } @book{MakVinRubSok87, author = {I. M. Makarov and T. M. Vinogradskaya and A. A. Rubchinsky and V. B. Sokolov}, title = {The Theory of Choice and Decision Making}, publisher = {Mir Publishers}, address = {Moscow}, year = {1987} } @inproceedings{ManMcgSle88, author = {M. S. Manasse and L. A. McGeoch and D. D. Sleator}, title = {Competitive algorithms for on-line problems}, booktitle = {Proceedings ACM Symposium on Theory of Computing}, pages = {322--333}, year = {1988} } @inproceedings{ManCan92, author = {D. Manocha and J. Canny}, title = {Real Time Inverse Kinematics of General {6R} Manipulators}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {383--389}, address = {Nice}, month = may, year = {1992} } @article{MarBic00, author = {A. Marigo and A. Bicchi}, title = {Rolling Bodies with Regular Surface: Controllability Theory and Applications}, journal = {IEEE Transactions on Automatic Control}, volume = {45}, number = {9}, pages = {1586--1599}, year = {2000} } @book{MarRat99, author = {J. E. Marsden and T. S. Ratiu}, title = {Introduction to Mechanics and Symmetry}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1999} } @incollection{Mas82, author = {M. T. Mason}, title = {Compliance and Force Control for Computer Controlled Manipulators}, booktitle = {Robot Motion: Planning and Control}, pages = {373--404}, editor = {M. Brady {\em et al.}}, publisher = {{MIT} Press}, address = {Cambridge, MA}, year = {1982} } @inproceedings{Mas85, author = {M. T. Mason}, title = {The Mechanics of Manipulation}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {544--548}, year = {1985} } @article{Mas86, author = {M. T. Mason}, title = {Mechanics and Planning of Manipulator Pushing Operations}, journal = {International Journal of Robotics Research}, volume = {5}, number = {3}, pages = {53--71}, year = {1986} } @book{Mas01, author = {M. T. Mason}, title = {Mechanics of Robotic Manipulation}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {2001} } @book{Mat99, author = {J. Matousek}, title = {Geometric Discrepancy}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1999} } @book{MatNes98, author = {J. Matousek and J. Nesetril}, title = {Invitation to Discrete Mathematics}, publisher = {Oxford University Press}, address = {Oxford, U.K.}, year = {1998} } @article{MatNis98, author = {M. Matsumoto and T. Nishimura}, title = {Mersenne Twister: {A} 623-Dimensionally equidistributed uniform pseudo-random number generator}, journal = {ACM Transactions on Modeling and Computer Simulation}, volume = {8}, number = {1}, pages = {3--30}, month = jan, year = {1998} } @inproceedings{MatElf88, author = {L. Matthies and A. Elfes}, title = {Integration of Sonar and Stereo Range Data Using a Grid-Based Representation}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {727--733}, year = {1988} } @book{May70, author = {O. Mayr}, title = {The Origins of Feedback Control}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {1970} } @article{MazAhuBes98, author = {E. Mazer and J. M. Ahuactzin and P. Bessi\`ere}, title = {The {A}riadne's Clew Algorithm}, journal = {Journal of Artificial Intelligence Research}, volume = {9}, pages = {295--316}, month = nov, year = {1998} } @inproceedings{MazTalAhuBes92, author = {E. Mazer and G. Talbi and J. M. Ahuactzin and P. Bessi\`ere}, title = {The {A}riadne's Clew algorithm}, booktitle = {Proceedings International Conference of Society of Adaptive Behavior}, address = {Honolulu}, year = {1992} } @book{Mcc00, author = {J. M. McCarthy}, title = {Geometric Design of Linkages}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2000} } @book{McgKin95, author = {D. J. McGill and W. W. King}, title = {An Introduction to Dynamics}, publisher = {PWS}, address = {Boston, MA}, year = {1995} } @incollection{MckMcl96, author = {R. McKelvey and A. McLennan}, title = {Computation of Equilibria in Finite Games}, booktitle = {The Handbook of Computational Economics}, pages = {87--142}, editor = {H. Amman and D. A. Kendrick and J .Rust}, publisher = {Elsevier}, address = {New York}, year = {1996} } @article{MegHakGarJohPap88, author = {N. Megiddo and S. L. Hakimi and M. R. Garey and D. S. Johnson and C. H. Papadimitriou}, title = {The Complexity of Searching a Graph}, journal = {Journal of the ACM}, volume = {35}, number = {1}, pages = {18--44}, month = jan, year = {1988} } @book{Mer00, author = {J.-P. Merlet}, title = {Parallel Robots}, publisher = {Kluwer}, address = {Boston, MA}, year = {2000} } @article{Mer72, author = {A. W. Merz}, title = {The Game of Two Identical Cars}, journal = {Journal of Optimization Theory \& Applications}, volume = {9}, number = {5}, pages = {324--343}, year = {1972} } @article{MetUla49, author = {N. C. Metropolis and S. M. Ulam}, title = {The {Monte-Carlo} Method}, journal = {Journal of the American Statistical Association}, volume = {44}, pages = {335--341}, year = {1949} } @book{MicHer93, author = {A. N. Michel and C. J. Herget}, title = {Applied Algebra and Functional Analysis}, publisher = {Dover}, address = {New York}, year = {1993} } @article{MilTri02, author = {R. J. Milgram and J. C. Trinkle}, title = {Complete Path Planning for Closed Kinematic Chains with Spherical Joints}, journal = {International Journal of Robotics Research}, volume = {21}, number = {9}, pages = {773--789}, year = {2002} } @article{MilTri04, author = {R. J. Milgram and J. C. Trinkle}, title = {The Geometry of Configuration Spaces for Closed Chains in Two and Three Dimensions}, journal = {Homology, Homotopy, and Applications}, volume = {6}, number = {1}, pages = {237--267}, year = {2004} } @article{MilZuc91, author = {D. A. Miller and S. W. Zucker}, title = {Copositive-plus {Lemke} Algorithm Solves Polymatrix Games}, journal = {Operations Research Letters}, volume = {10}, pages = {285--290}, year = {1991} } @article{MilTenThuVav97, author = {G. L. Miller and S.-H. Teng and W. Thurston and S. A. Vavasis}, title = {Separators for Sphere-Packings and Nearest Neighbor Graphs}, journal = {Journal of the ACM}, volume = {44}, number = {1}, pages = {1--29}, month = jan, year = {1997} } @book{Mil63, author = {J. W. Milnor}, title = {Morse Theory}, publisher = {Princeton University Press}, address = {Princeton, NJ}, year = {1963} } @techreport{Mir97, author = {B. Mirtich}, title = {{V-Clip}: Fast and Robust Polyhedral Collision Detection}, number = {TR97-05}, institution = {Mitsubishi Electronics Research Laboratory}, year = {1997} } @incollection{Mir98, author = {B. Mirtich}, title = {Efficient Algorithms for Two-Phase Collision Detection}, booktitle = {Practical Motion Planning in Robotics: Current Approaches and Future Directions}, pages = {203--223}, editor = {K. Gupta and A.P. del Pobil}, publisher = {Wiley}, address = {New York}, year = {1998} } @book{Mis93, author = {B. Mishra}, title = {Algorithmic Algebra}, publisher = {Springer-Verlag}, address = {New York}, year = {1993} } @incollection{Mis97, author = {B. Mishra}, title = {Computational Real Algebraic Geometry}, booktitle = {Handbook of Discrete and Computational Geometry}, pages = {537--556}, editor = {J. E. Goodman and J. O'Rourke}, publisher = {CRC Press}, address = {New York}, year = {1997} } @article{MitBayTom03, author = {I. Mitchell and A. Bayen and C. Tomlin}, title = {Computing Reachable Sets for Continuous Dynamic Games using Level Set Methods}, journal = {IEEE Transactions on Automatic Control}, note = {Submitted}, year = {2003} } @article{MitTom03, author = {I. Mitchell and C. J. Tomlin}, title = {Overapproximating Reachable Sets by {Hamilton-Jacobi} Projections}, journal = {Journal of Scientific Computation}, volume = {19}, number = {1}, pages = {323--346}, year = {2003} } @article{Mit96, author = {J. S. B. Mitchell}, title = {Shortest Paths Among Obstacles in the Plane}, journal = {International Journal Computational Geometry \& Applications}, volume = {6}, number = {3}, pages = {309--332}, year = {1996} } @incollection{Mit04, author = {J. S. B. Mitchell}, title = {Shortest Paths and Networks}, booktitle = {Handbook of Discrete and Computational Geometry, 2nd Ed.}, pages = {607--641}, editor = {J. E. Goodman and J. O'Rourke}, publisher = {Chapman and Hall/CRC Press}, address = {New York}, year = {2004} } @article{MitPap91, author = {J. S. B. Mitchell and C. H. Papadimitriou}, title = {The Weighted Region Problem}, journal = {Journal of the ACM}, volume = {38}, pages = {18--73}, year = {1991} } @book{Mit97b, author = {T. M. Mitchell}, title = {Machine Learning}, publisher = {McGraw-Hill}, address = {New York}, year = {1997} } @inproceedings{MolHil00, author = {L. Molina-Tanco and A. Hilton}, title = {Realistic Synthesis of Novel Human Movements from a Database of Motion Capture Examples}, booktitle = {Proceedings IEEE Workshop on Human Motion}, year = {2000} } @inproceedings{MonNor92, author = {S. Monaco and D. Normand-Cyrot}, title = {An introduction to motion planning under multirate digital control}, booktitle = {Proceedings IEEE Conference Decision \& Control}, pages = {1780--1785}, year = {1992} } @article{Mon82, author = {G. Monahan}, title = {A survey of partially observable {M}arkov decision processes}, journal = {Management Science}, volume = {101}, number = {1}, pages = {1--16}, year = {1982} } @article{MonSud88, author = {B. Monien and I. H. Sudborough}, title = {{Min} Cut is {NP}-Complete for Edge Weighted Graphs}, journal = {Theoretical Computer Science}, volume = {58}, pages = {209--229}, year = {1988} } @article{Mon88, author = {D. J. Montana}, title = {The Kinematics of Contact and Grasp}, journal = {International Journal of Robotics Research}, volume = {7}, number = {3}, pages = {17--32}, year = {1988} } @inproceedings{MonThrKolWeg99, author = {M. Montemerlo and S. Thrun and D. Koller and B. Wegbreit}, title = {{FastSLAM: A} factored solution to the simultaneous localization and mapping problem}, booktitle = {Proceedings AAAI National Conference on Artificial Intelligence}, year = {1999} } @book{Mor97, author = {M. E. Mortenson}, title = {Geometric Modeling, 2nd Ed.}, publisher = {Wiley}, address = {New York}, year = {1997} } @book{MotRag95, author = {R. Motwani and P. Raghavan}, title = {Randomized Algorithms}, publisher = {Cambridge University Press}, address = {Cambridge, U.K.}, year = {1995} } @inproceedings{Mun05, author = {R. Munos}, title = {Error Bounds for Approximate Value Iteration}, booktitle = {Proceedings AAAI National Conference on Artificial Intelligence}, year = {2005} } @inproceedings{MunMoo98, author = {R. Munos and A. Moore}, title = {Barycentric Interpolator for Continuous Space \& Time Reinforcement Learning}, booktitle = {Proceedings Neural Information Processing Systems}, year = {1998} } @article{MunMoo01, author = {R. Munos and A. Moore}, title = {Variable Resolution Discretization in Optimal Control}, journal = {Machine Learning}, volume = {49}, pages = {291--323}, year = {2001} } @inproceedings{MupMurHut05, author = {T. Muppirala and R. Murrieta-Cid and S. Hutchinson}, title = {Optimal Motion Strategies Based on Critical Events to Maintain Visibility of a Moving Target}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {3837--3842}, year = {2005} } @phdthesis{Mur02, author = {T. Murphey}, title = {Control of Multiple Model Systems}, school = {California Institute of Technology}, month = may, year = {2002} } @book{MurLiSas94, author = {R. M. Murray and Z. Li and S. Sastry}, title = {A Mathematical Introduction to Robotic Manipulation}, publisher = {CRC Press}, address = {Boca Raton, FL}, year = {1994} } @inproceedings{MurRatSlu95, author = {R. M. Murray and M. Rathinam and W. M. Sluis}, title = {Differential Flatness of mechanical control systems}, booktitle = {Proceedings ASME International Congress and Exposition}, year = {1995} } @article{MurSas93, author = {R. M. Murray and S. Sastry}, title = {Nonholonomic Motion Planning: Steering Using Sinusoids}, journal = {IEEE Transactions on Automatic Control}, volume = {38}, number = {5}, pages = {700--716}, year = {1993} } @inproceedings{MurSarBhaHut04, author = {R. Murrieta-Cid and A. Sarmiento and S. Bhattacharya and S. Hutchinson}, title = {Maintaining Visibility of a Moving Target at a Fixed Distance: {T}he Case of Observer Bounded Speed}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {479--484}, year = {2004} } @article{NakSuzKoi97, author = {Y. Nakamura and T. Suzuki and M. Koinuma}, title = {Nonlinear behavior and control of a nonholonomic free-joint manipulator}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {13}, number = {6}, pages = {853--862}, year = {1997} } @article{Nas51, author = {J. Nash}, title = {Noncooperative games}, journal = {Annals of Mathematics}, volume = {54}, number = {2}, pages = {286--295}, year = {1951} } @book{NasSof96, author = {S. G. Nash and A. Sofer}, title = {Linear and Nonlinear Programming}, publisher = {McGraw-Hill}, address = {New York}, year = {1996} } @article{Nat88, author = {B. K. Natarajan}, title = {The Complexity of Fine Motion Planning}, journal = {International Journal of Robotics Research}, volume = {7}, number = {2}, pages = {36--42}, year = {1988} } @inproceedings{Nat88b, author = {B. K. Natarajan}, title = {On Planning Assemblies}, booktitle = {Proceedings ACM Symposium on Computational Geometry}, pages = {299--308}, year = {1988} } @misc{New05, author = {{New York University}}, title = {{MathMol Library}}, howpublished = {Scientific Visualization Center. Available from {http://www.nyu.edu/pages/mathmol/library/}}, year = {2005} } @incollection{NewSim63, author = {A. Newell and H. Simon}, title = {{GPS}: A program that simulates human thought.}, booktitle = {Computers and Thought}, editor = {E. A. Feigenbaum and J. Feldman}, publisher = {McGraw-Hill}, address = {New York}, year = {1963} } @article{NewBra91, author = {W. S. Newman and M. S. Branicky}, title = {Real-time configuration space transforms for obstacle avoidance}, journal = {International Journal of Robotics Research}, volume = {10}, number = {6}, pages = {650--667}, year = {1991} } @inproceedings{NgJor00, author = {A. Y. Ng and M. Jordan}, title = {{PEGASUS: A} policy search method for large {MDPs} and {POMDPs}}, booktitle = {Proceedings Conference on Uncertainty in Artificial Intelligence}, year = {2000} } @book{Nie92, author = {H. Niederreiter}, title = {Random Number Generation and Quasi-{M}onte-{C}arlo Methods}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia}, year = {1992} } @incollection{NieXin98, author = {H. Niederreiter and C. P. Xing}, title = {Nets, (t,s)-sequences, and algebraic geometry}, booktitle = {Random and Quasi-Random Point Sets}, pages = {267--302}, editor = {P. Hellekalek and G. Larcher}, publisher = {Springer-Verlag}, address = {Berlin}, note = {Lecture Notes in Statistics, 138}, year = {1998} } @inproceedings{NieOve04, author = {D. Nieuwenhuisen and M. H. Overmars}, title = {Useful cycles in probabilistic roadmap graphs}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {446--452}, year = {2004} } @book{NijVan90, author = {H. Nijmeijer and A. J. van der Schaft}, title = {Nonlinear Dynamical Control Systems}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1990} } @inproceedings{Nil69, author = {N. J. Nilsson}, title = {A mobile automaton: {A}n application of artificial intelligence techniques}, booktitle = {1st International Conference on Artificial Intelligence}, pages = {509--520}, year = {1969} } @book{Nil80, author = {N. J. Nilsson}, title = {Principles of Artificial Intelligence}, publisher = {Tioga Publishing Company}, address = {Wellsboro, PA}, year = {1980} } @book{Nil98, author = {N. J. Nilsson}, title = {Artificial Intelligence: A New Synthesis}, publisher = {Morgan Kaufmann}, address = {San Francisco, CA}, year = {1998} } @article{Nta92, author = {S. Ntafos}, title = {Watchman Routes under Limited Visibility}, journal = {Computational Geometry: Theory and Applications}, volume = {1}, pages = {149--170}, year = {1992} } @inproceedings{OdoLoz89, author = {P. A. O'Donnell and T. Lozano-P\'{e}rez}, title = {Deadlock-Free and Collision-Free Coordination of Two Robot Manipulators}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {484--489}, year = {1989} } @article{Odu87, author = {C. O'Dunlaing}, title = {Motion Planning with Inertial Constraints}, journal = {Algorithmica}, volume = {2}, number = {4}, pages = {431--475}, year = {1987} } @incollection{OduShaYap87, author = {C. O'Dunlaing and M. Sharir and C. K. Yap}, title = {Retraction: {A} New Approach to Motion Planning}, booktitle = {Planning, Geometry, and Complexity of Robot Motion}, pages = {193--213}, editor = {J .T .Schwartz and M. Sharir and J. Hopcroft}, publisher = {Ablex}, address = {Norwood, NJ}, year = {1987} } @article{OduYap82, author = {C. O'Dunlaing and C. K. Yap}, title = {A retraction method for planning the motion of a disc}, journal = {Journal of Algorithms}, volume = {6}, pages = {104--111}, year = {1982} } @phdthesis{Ogr03, author = {P. {\"Ogren}}, title = {Formations and Obstacle Avoidance in Mobile Robot Control}, address = {Stockholm, Sweden}, school = {Royal Institute of Technology (KTH)}, department = {Optimization and Systems Theory, Department of Mathematics}, year = {2003} } @inproceedings{Oka06, author = {J. M. O'Kane}, title = {Global Localization Using Odometry}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, year = {2005} } @inproceedings{OkaLav05, author = {J. M. O'Kane and S. M. LaValle}, title = {Almost-Sensorless Localization}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, year = {2005} } @book{One66, author = {B. O'Neill}, title = {Elementary Differential Geometry}, publisher = {Academic}, address = {New York}, year = {1966} } @article{OorHinDud97, author = {S. Oore and G. E. Hinton and G. Dudek}, title = {A mobile robot that learns its place}, journal = {Neural Computation}, volume = {9}, pages = {683--699}, year = {1997} } @book{Oro87, author = {J. O'Rourke}, title = {Art Gallery Theorems and Algorithms}, publisher = {Oxford University Press}, address = {New York}, year = {1987} } @incollection{Oro04, author = {J. O'Rourke}, title = {Visibility}, booktitle = {Handbook of Discrete and Computational Geometry, 2nd Ed.}, pages = {643--663}, editor = {J. E. Goodman and J. O'Rourke}, publisher = {Chapman and Hall/CRC Press}, address = {New York}, year = {2004} } @incollection{OroSur04, author = {J. O'Rourke and S. Suri}, title = {Polygons}, booktitle = {Handbook of Discrete and Computational Geometry, 2nd Ed.}, pages = {583--606}, editor = {J. E. Goodman and J. O'Rourke}, publisher = {Chapman and Hall/CRC Press}, address = {New York}, year = {2004} } @article{OveVan82, author = {M. H. Overmars and J. van Leeuwen}, title = {Dynamic Multidimensional Data Structures Based on {Q}uad- and {K-D} Trees}, journal = {Acta Informatica}, volume = {17}, pages = {267--285}, year = {1982} } @book{Owe82, author = {G. Owen}, title = {Game Theory}, publisher = {Academic}, address = {New York}, year = {1982} } @inproceedings{PadMesFis89, author = {B. Paden and A. Mees and M. Fisher}, title = {Path planning using a {J}acobian-based freespace generation algorithm}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1732--1737}, year = {1989} } @article{PaiRei98, author = {D. K. Pai and L. M. Reissell}, title = {Multiresolution rough terrain motion planning}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {14}, number = {5}, pages = {709--717}, year = {1998} } @inproceedings{PanPalSalBic04, author = {S. Pancanti and L. Pallottino and D. Salvadorini and A. Bicchi}, title = {Motion Planning through Symbols and Lattices}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {3914--3919}, year = {2004} } @article{Pap85b, author = {C. H. Papadimitriou}, title = {An Algorithm for Shortest-Path Planning in Three Dimensions}, journal = {Information Processing Letters}, volume = {20}, number = {5}, pages = {259--263}, year = {1985} } @article{Pap85, author = {C. H. Papadimitriou}, title = {Games Against Nature}, journal = {Journal of Computer and System Sciences}, volume = {31}, pages = {288--301}, year = {1985} } @book{PapSte82, author = {C. H. Papadimitriou and K. J. Steiglitz}, title = {Combinatorial Optimization: {A}lgorithms and Complexity}, publisher = {Prentice Hall}, address = {Englewood Cliffs, NJ}, year = {1982} } @article{PapTsi86, author = {C. H. Papadimitriou and J. N. Tsitsiklis}, title = {Intractable Problems in Control Theory}, journal = {SIAM Journal of Control \& Optimization}, volume = {24}, number = {4}, pages = {639--654}, month = jul, year = {1986} } @article{PapTsi87, author = {C. H. Papadimitriou and J. N. Tsitsiklis}, title = {The Complexity of {M}arkov Decision Processes}, journal = {Mathematics of Operations Research}, volume = {12}, number = {3}, pages = {441--450}, month = aug, year = {1987} } @article{PapYan91, author = {C. H. Papadimitriou and M. Yannakakis}, title = {Shortest Paths without a Map}, journal = {Theoretical Computer Science}, volume = {84}, pages = {127--150}, year = {1991} } @book{Pap02, author = {A. Papantonopoulou}, title = {Algebra: {P}ure and Applied}, publisher = {Prentice Hall}, address = {Englewood Cliffs, NJ}, year = {2002} } @techreport{ParLeeChw01, author = {S.-M. Park and J.-H. Lee and K.-Y. Chwa}, title = {Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher}, number = {CS/TR-2001-161}, address = {Seoul, South Korea}, institution = {Dept. of Computer Science, KAIST}, month = jan, year = {2001} } @inproceedings{ParEli03, author = {R. Parr and A. Eliazar}, title = {{DP-SLAM: Fast,} robust simultaneous localization and mapping without predetermined landmarks}, booktitle = {Proceedings International Joint Conference on Artificial Intelligence}, year = {2003} } @inproceedings{ParRus95, author = {R. Parr and S. Russell}, title = {Approximating optimal policies for partially observable stochastic domains}, booktitle = {Proceedings International Joint Conference on Artificial Intelligence}, year = {1995} } @incollection{Par76, author = {T. D. Parsons}, title = {Pursuit-Evasion in a Graph}, booktitle = {Theory and Application of Graphs}, pages = {426--441}, editor = {Y. Alavi and D. R. Lick}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1976} } @incollection{ParSte77, author = {T. Parthasarathy and M. Stern}, title = {Markov Games: A Survey}, booktitle = {Differential Games and Control Theory II}, pages = {1--46}, publisher = {Marcel Dekker}, address = {New York}, year = {1977} } @book{Pau81, author = {R. P. Paul}, title = {Robot Manipulators: Mathematics, Programming, and Control}, publisher = {MIT Press, Cambridge, MA}, year = {1981} } @inproceedings{PauShi76, author = {R. P. Paul and B. Shimano}, title = {Compliance and Control}, booktitle = {Proceedings of the Joint American Automatic Control Conference}, pages = {1694--1699}, year = {1976} } @book{Pea84, author = {J. Pearl}, title = {Heuristics}, publisher = {Addison-Wesley}, address = {Reading, MA}, year = {1984} } @book{Pea88, author = {J. Pearl}, title = {Probabilistic Reasoning in Intelligent Systems: {N}etworks of Plausible Inference}, publisher = {Morgan Kaufmann}, address = {San Francisco, CA}, year = {1988} } @book{PelSud03, author = {B. Peleg and P. {Sudl\"olter}}, title = {Introduction to the Theory of Cooperative Games}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2003} } @incollection{PenAke02, author = {J. Peng and S. Akella}, title = {Coordinating Multiple Robots with Kinodynamic Constraints Along Specified Paths}, booktitle = {Algorithmic Foundations of Robotics {V} (WAFR 2002)}, pages = {221--237}, editor = {J.-D. Boissonnat and J. Burdick and K. Goldberg and S. Hutchinson}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2002} } @incollection{Per89, author = {J. Pertin-Troccaz}, title = {Grasping: {A} State of the Art}, booktitle = {The Robotics Review 1}, editor = {O. Khatib and J. J. Craig and T. Lozano-P\'{e}rez}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {1989} } @article{PetKriPon92, author = {S. Petitjean and D. Kriegman and J. Ponce}, title = {Computing exact aspect graphs of curved objects: algebraic surfaces}, journal = {International Journal of Computer Vision}, volume = {9}, pages = {231--255}, month = dec, year = {1992} } @book{Pet93, author = {L. A. Petrosjan}, title = {Differential Games of Pursuit}, publisher = {World Scientific}, address = {Singapore}, year = {1993} } @inproceedings{PetLauSim03, author = {J. Pettr\'e and J.-P. Laumond and T. Sim\'eon}, title = {A 2-Stages Locomotion Planner for Digital Actors}, booktitle = {Proceedings Eurographics/SIGGRAPH Symposium on Computer Animation}, pages = {258--264}, year = {2003} } @article{PfeJoh87, author = {F. Pfeiffer and R. Johanni}, title = {A Concept for Manipulator Trajectory Planning}, journal = {IEEE Journal of Robotics \& Automation}, volume = {RA-3}, number = {2}, pages = {115--123}, year = {1987} } @inproceedings{PhiBedKav03, author = {J. M. Phillips and N. Bedrosian and L. E. Kavraki}, title = {Spacecraft Rendezvous and Docking With Real-Time Randomized Optimization}, booktitle = {Proceedings AIAA Guidance, Navigation and Control Conference}, year = {2003} } @inproceedings{PiaRomBia03, author = {A. Piazzi and M. Romano and C. G. Lo Bianco}, title = {{$G^3$} splines for the path planning of wheeled mobile robots}, booktitle = {Proceedings European Control Conference}, year = {2003} } @article{Pie91, author = {L. Piegl}, title = {On {NURBS}: {A} Survey}, journal = {IEEE Transactions on Computer Graphics \& Applications}, volume = {11}, number = {1}, pages = {55--71}, month = jan, year = {1991} } @book{Pie86, author = {D. A. Pierre}, title = {Optimization Theory with Applications}, publisher = {Dover}, address = {New York}, year = {1986} } @book{Pik01, author = {R. W. Pike}, title = {Optimization for Engineering Systems}, publisher = {[Online]}, note = {Available at http://www.mpri.lsu.edu/bookindex.html}, year = {2001} } @inproceedings{PinGorThr03, author = {J. Pineau and G. Gordon and S. Thrun}, title = {Point-based value iteration}, booktitle = {Proceedings International Joint Conference on Artificial Intelligence}, pages = {1025--1032}, year = {2003} } @inproceedings{PisHofLinMan00, author = {C. Pisula and K. Hoff and M. Lin and D. Manocha}, title = {Randomized Path Planning for a Rigid Body Based on Hardware Accelerated {V}oronoi Sampling}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, year = {2000} } @inproceedings{Pit96, author = {R. Pito}, title = {A Sensor Based Solution to the Next Best View Problem}, booktitle = {International Conference Pattern Recognition}, year = {1996} } @inproceedings{PivKel05, author = {M. Pivtoraiko and A. Kelly}, title = {Generating Near Minimal Spanning Control Sets for Constrained Motion Planning in Discrete State Spaces}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2005} } @inproceedings{PlaKav05, author = {E. Plaku and L. E. Kavraki}, title = {Distributed sampling-based roadmap of trees for large-scale motion planning}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {2005} } @article{PocVeg96, author = {M. Pocchiola and G. Vegter}, title = {The Visibility Complex}, journal = {International Journal Computational Geometry \& Applications}, volume = {6}, number = {3}, pages = {279--308}, year = {1996} } @techreport{Poh69, author = {I. Pohl}, title = {Bi-directional and heuristic search in path problems}, address = {Stanford, CA}, institution = {Stanford Linear Accelerator Center}, year = {1969} } @incollection{Poh71, author = {I. Pohl}, title = {Bi-Directional Search}, booktitle = {Machine Intelligence}, pages = {127--140}, editor = {B. Meltzer and D. Michie}, publisher = {Elsevier}, address = {New York}, year = {1971} } @article{PonFav95, author = {J. Ponce and B. Faverjon}, title = {On Computing Three-Finger Force-Closure Grasps of Polygonal Objects}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {11}, number = {6}, pages = {868--881}, year = {1995} } @article{PonSulSudBoiMer97, author = {J. Ponce and S. Sullivan and A. Sudsang and J.-D. Boissonnat and J.-P. Merlet}, title = {On Computing Four-Finger Equilibrium and Force-Closure Grasps of Polyhedral Objects}, journal = {International Journal of Robotics Research}, volume = {16}, number = {1}, pages = {11--35}, month = feb, year = {1997} } @book{PonBolGamMis86, author = {L. S. Pontryagin and V. G. Boltyanskii and R. V. Gamkrelidze and E. F. Mishchenko}, title = {L. S. Pontryagin Selected Works, Volume 4: The Mathematical Theory of Optimal Processes}, publisher = {Gordon and Breach}, address = {Montreux, Switzerland}, year = {1986} } @inproceedings{PopSeiErdPopWik02, author = {J. Popovic and S. M. Seitz and M. A. Erdmann and Z. Popovic A. P. Wiktin}, title = {Interactive manipulation of rigid body simulations}, booktitle = {Proceedings ACM SIGGRAPH}, pages = {209--217}, year = {2002} } @inproceedings{PorSpaVla05, author = {J. M. Porta and M. T. J. Spaan and N. Vlassis}, title = {Robot planning in partially observable continuous domains}, booktitle = {Proceedings Robotics: Science and Systems}, year = {2005} } @book{PotWal01, author = {H. Pottman and J. Wallner}, title = {Computational Line Geometry}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2001} } @inproceedings{PouBou03, author = {P. Poupart and C. Boutilier}, title = {Value-directed compression of {POMDPs}}, booktitle = {Proceedings Neural Information Processing Systems}, year = {2003} } @book{PreSha85, author = {F. P. Preparata and M. I. Shamos}, title = {Computational Geometry}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1985} } @inproceedings{Qui94, author = {S. Quinlan}, title = {Efficient Distance Computation between Nonconvex Objects}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {3324--3329}, year = {1994} } @article{Rab83, author = {M. Rabin}, title = {Transaction protection by beacons}, journal = {Journal of Computation Systems Science}, volume = {27}, number = {2}, pages = {256--267}, year = {1983} } @inproceedings{RajLav01, author = {S. Rajko and S. M. LaValle}, title = {A Pursuit-Evasion Bug Algorithm}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, pages = {1954--1960}, year = {2001} } @article{RaoGol95, author = {A. Rao and K. Goldberg}, title = {Manipulating algebraic parts in the plane}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {11}, number = {4}, pages = {598--602}, year = {1995} } @techreport{RaoKarShiIye93, author = {N. Rao and S. Kareti and W. Shi and S. Iyenagar}, title = {Robot Navigation in Unknown Terrains: Introductory Survey of Non-Heuristic Algorithms}, number = {ORNL/TM-12410:1--58}, institution = {Oak Ridge National Laboratory}, month = jul, year = {1993} } @inproceedings{RatGin93, author = {S. Ratering and M. Gini}, title = {Robot Navigation in a Known Environment with Unknown Moving Obstacles}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {25--30}, year = {1993} } @article{RatMur98, author = {M. Rathinam and R. M. Murray}, title = {Configuration flatness of {Lagrangian} systems underactuated by one control}, journal = {SIAM Journal of Control \& Optimization}, volume = {36}, number = {1}, pages = {164--179}, year = {1998} } @article{ReeShe90, author = {J. A. Reeds and L. A. Shepp}, title = {Optimal paths for a car that goes both forwards and backwards}, journal = {Pacific Journal of Mathematics}, volume = {145}, number = {2}, pages = {367--393}, year = {1990} } @article{ReiSun03, author = {J. Reif and Z. Sun}, title = {On Frictional Mechanical Systems and Their Computational Power}, journal = {SIAM Journal on Computing}, volume = {32}, number = {6}, pages = {1449--1474}, year = {2003} } @incollection{ReiWan97, author = {J. Reif and H. Wang}, title = {Non-Uniform Discretization Approximations for Kinodynamic Motion Planning}, booktitle = {Algorithms for Robotic Motion and Manipulation}, pages = {97--112}, editor = {J.-P. Laumond and M. H. Overmars}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1997} } @inproceedings{Rei79, author = {J. H. Reif}, title = {Complexity of the Mover's Problem and Generalizations}, booktitle = {Proceedings IEEE Symposium on Foundations of Computer Science}, pages = {421--427}, year = {1979} } @inproceedings{ReiSha85, author = {J. H. Reif and M. Sharir}, title = {Motion Planning in the Presence of Moving Obstacles}, booktitle = {Proceedings IEEE Symposium on Foundations of Computer Science}, pages = {144--154}, year = {1985} } @article{ReiSha94, author = {J. H. Reif and M. Sharir}, title = {Motion Planning in the Presence of Moving Obstacles}, journal = {Journal of the ACM}, volume = {41}, pages = {764--790}, year = {1994} } @incollection{ReiSun01, author = {J. H. Reif and Z. Sun}, title = {An efficient approximation algorithm for weighted region shortest path problem}, booktitle = {Algorithmic and Computational Robotics: {N}ew Directions}, pages = {191--203}, editor = {B. R. Donald and K. M. Lynch and D. Rus}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {2001} } @article{ReiTat93, author = {J. H. Reif and S. R. Tate}, title = {Continuous Alternation: The Complexity of Pursuit in Continuous Domains}, journal = {Algorithmica}, volume = {10}, pages = {157--181}, year = {1993} } @book{ReiStoBet01, author = {J. Reimpell and H. Stoll and J. W. Betzler}, title = {The Automotive Chassis: Engineering Principles}, publisher = {Society of Automotive Engineers}, address = {Troy, MI}, year = {2001} } @book{ReiNieDeo77, author = {E. M. Reingold and J. Nievergelt and N. Deo}, title = {Combinatorial Algorithms}, publisher = {Prentice Hall}, address = {Englewood Cliffs, NJ}, year = {1977} } @article{RemKui04, author = {E. Remolina and B. Kuipers}, title = {Towards a general theory of topological maps}, journal = {Artificial Intelligence Journal}, volume = {152}, number = {1}, pages = {47--104}, year = {2004} } @inproceedings{Ren93, author = {W. Rencken}, title = {Concurrent localisation and map building for mobile robots using ultrasonic sensors}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {2192--2197}, year = {1993} } @article{RimBur98, author = {E. Rimon and J. W. Burdick}, title = {Mobility of Bodies in Contact--{I}: {A} 2nd Order Mobility Index for Multiple-Finger Grasps}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {14}, number = {5}, pages = {696--708}, year = {1998} } @article{RimBur98b, author = {E. Rimon and J. W. Burdick}, title = {Mobility of Bodies in Contact--{II}: {H}ow forces are generated by curvature effects}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {14}, number = {5}, pages = {709--717}, year = {1998} } @inproceedings{RimCan94, author = {E. Rimon and J. Canny}, title = {Construction of {C}-space roadmaps using local sensory data -- {W}hat should the sensors look for?}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {117--124}, year = {1994} } @article{RimKod92, author = {E. Rimon and D. E. Koditschek}, title = {Exact Robot Navigation Using Artificial Potential Fields}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {8}, number = {5}, pages = {501--518}, month = oct, year = {1992} } @inproceedings{Riz98, author = {A. A. Rizzi}, title = {Hybrid Control as a Method for Robot Motion Programming}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {832--837}, year = {1998} } @book{Rob01, author = {C. P. Robert}, title = {The Bayesian Choice, 2nd. Ed.}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2001} } @article{Roh86, author = {H. Rohnert}, title = {Shortest Paths in the Plane with Convex Polygonal Obstacles}, journal = {Information Processing Letters}, volume = {23}, pages = {71--76}, year = {1986} } @article{RosFah04, author = {I. M. Ross and F. Fahroo}, title = {Pseudospectral methods for optimal motion planning of differentially flat systems}, journal = {IEEE Transactions on Automatic Control}, volume = {49}, number = {8}, pages = {1410--1413}, year = {2004} } @book{Rot88, author = {J. J. Rotman}, title = {Introduction to Algebraic Topology}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1988} } @inproceedings{RoyGor03, author = {N. Roy and G. Gordon}, title = {Exponential family {PCA} for belief compression in {POMDPs}}, booktitle = {Proceedings Neural Information Processing Systems}, year = {2003} } @book{Roy88, author = {H. L. Royden}, title = {Real Analysis}, publisher = {MacMillan}, address = {New York}, year = {1988} } @book{Rud87, author = {W. Rudin}, title = {Real Analysis}, publisher = {McGraw-Hill}, address = {New York}, year = {1987} } @book{Rud91, author = {W. Rudin}, title = {Functional Analysis, 2nd Ed.}, publisher = {McGraw-Hill}, address = {New York}, year = {1991} } @book{RusNor03, author = {S. Russell and P. Norvig}, title = {Artificial Intelligence: A Modern Approach, 2nd Edition}, publisher = {Prentice-Hall}, address = {Englewood Cliffs, NJ}, year = {2003} } @article{SacRajLav04, author = {S. Sachs and S. Rajko and S. M. LaValle}, title = {Visibility-Based Pursuit-Evasion in an Unknown Planar Environment}, journal = {International Journal of Robotics Research}, volume = {23}, number = {1}, pages = {3--26}, month = jan, year = {2004} } @book{Sag92, author = {H. Sagan}, title = {Introduction to the Calculus of Variations}, publisher = {Dover}, address = {New York}, year = {1992} } @book{Sag94, author = {H. Sagan}, title = {Space-Filling Curves}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1994} } @article{SahHol86, author = {G. Sahar and J. M. Hollerbach}, title = {Planning Minimum-Time Trajectories for Robot Arms}, journal = {International Journal of Robotics Research}, volume = {5}, number = {3}, pages = {97--140}, year = {1986} } @inproceedings{SanLat01, author = {G. S\'anchez and J.-C. Latombe}, title = {A Single-Query Bi-Directional Probabilistic Roadmap Planner with Lazy Collision Checking}, booktitle = {Proceedings International Symposium on Robotics Research}, year = {2001} } @article{SanLat02, author = {G. S\'anchez and J.-C. Latombe}, title = {On delaying collision checking in {PRM} planning: {A}pplication to multi-robot coordination}, journal = {International Journal of Robotics Research}, volume = {21}, number = {1}, pages = {5--26}, year = {2002} } @book{Sas99, author = {S. Sastry}, title = {Nonlinear Systems: Analysis, Stability, and Control}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1999} } @book{SawNakTan85, author = {Y. Sawaragi and H. Nakayama and T. Tanino}, title = {Theory of Multiobjective Optimization}, publisher = {Academic}, address = {New York}, year = {1985} } @inproceedings{SchFra97, author = {A. Scheuer and T. Fraichard}, title = {Collision-free and continuous-curvature path planning for car-like robots}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {867--873}, year = {1997} } @inproceedings{SchLau98, author = {A. Scheuer and C. Laugier}, title = {Planning Sub-Optimal and Continuous-Curvature Paths for Car-Like Robots}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {25--31}, year = {1998} } @inproceedings{SchCro94, author = {B. Schiele and J. Crowley}, title = {A comparison of position estimation techniques using occupancy grids}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {1994} } @article{SchSha83b, author = {J. T. Schwartz and M. Sharir}, title = {On the {Piano Movers' Problem}: {I}. {The} Case of a Two-Dimensional Rigid Polygonal Body Moving Amidst Polygonal Barriers}, journal = {Communications on Pure and Applied Mathematics}, volume = {36}, pages = {345--398}, year = {1983} } @article{SchSha83c, author = {J. T. Schwartz and M. Sharir}, title = {On the {Piano Movers' Problem}: {II}. {General} Techniques for Computing Topological Properties of Algebraic Manifolds}, journal = {Advances in Applied Mathematics}, volume = {12}, pages = {298--351}, year = {1983} } @article{SchSha83, author = {J. T. Schwartz and M. Sharir}, title = {On the {Piano Movers' Problem}: {III}. {Coordinating} the Motion of Several Independent Bodies}, journal = {International Journal of Robotics Research}, volume = {2}, number = {3}, pages = {97--140}, year = {1983} } @book{SchShaHop87, author = {J. T. Schwartz and M. Sharir and J. Hopcroft}, title = {Planning, Geometry, and Complexity of Robot Motion}, publisher = {Ablex}, address = {Norwood, NJ}, year = {1987} } @incollection{SchSahLat02, author = {F. Schwarzer and M. Saha and J.-C. Latombe}, title = {Exact Collision Checking of Robot Paths}, booktitle = {Algorithmic Foundations of Robotics {V} (WAFR 2002)}, editor = {J.-D. Boissonnat and J. Burdick and K. Goldberg and S. Hutchinson}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2002} } @book{SciSic96, author = {L. Sciavicco and B. Siciliano}, title = {Modelling and Control of Robot Manipulators}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1996} } @book{Sed02, author = {R. Sedgewick}, title = {Algorithms in C++, 2nd Ed.}, publisher = {Addison-Wesley}, address = {Reading, MA}, year = {2002} } @article{SekLau98, author = {S. Sekhavat and J.-P. Laumond}, title = {Topological property for collision-free nonholonomic motion planning: {T}he case of sinusoidal inputs for chained-form systems}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {14}, number = {5}, pages = {671--680}, year = {1998} } @article{SekSveLauOve98, author = {S. Sekhavat and P. Svestka and J.-P. Laumond and M. H. Overmars}, title = {Multilevel path planning for nonholonomic robots using semiholonomic subsystems}, journal = {International Journal of Robotics Research}, volume = {17}, pages = {840--857}, year = {1998} } @article{SepKrcStaWadLamLeb95, author = {N. F. Sepetov and V. Krchnak and M. Stankova and S. Wade and K. S. Lam and M. Lebl}, title = {Library of Libraries: Approach to Synthetic Combinatorial Library Design and Screening of ``Pharmacophore'' Motifs}, journal = {Proceedings of the National Academy of Sciences, USA}, volume = {92}, pages = {5426--5430}, month = jun, year = {1995} } @book{Ser92, author = {J.-P. Serre}, title = {Lie Algebras and Lie Groups}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1992} } @book{Set96, author = {J. A. Sethian}, title = {Level set methods : {E}volving interfaces in geometry, fluid mechanics, computer vision, and materials science}, publisher = {Cambridge University Press}, address = {Cambridge, U.K.}, year = {1996} } @book{Sha01, author = {A. A. Shabana}, title = {Computational Dynamics}, publisher = {Wiley}, address = {New York}, year = {2001} } @article{Sha48, author = {C. E. Shannon}, title = {A Mathematical Theory of Communication}, journal = {Bell Systems Technical Journal}, volume = {27}, pages = {379--423}, year = {1948} } @incollection{Sha04, author = {M. Sharir}, title = {Algorithmic Motion Planning}, booktitle = {Handbook of Discrete and Computational Geometry, 2nd Ed.}, pages = {1037--1064}, editor = {J. E. Goodman and J. O'Rourke}, publisher = {Chapman and Hall/CRC Press}, address = {New York}, year = {2004} } @book{ShaAga95, author = {M. Sharir and P. K. Agarwal}, title = {Davenport-{S}chinzel Sequences and Their Geometric Applications}, publisher = {Cambridge University Press}, address = {Cambridge, U.K.}, year = {1995} } @article{Sha92, author = {R. Sharma}, title = {Locally Efficient Path Planning in an Uncertain, Dynamic Environment Using a Probabilistic Model}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {8}, number = {1}, pages = {105--110}, month = feb, year = {1992} } @inproceedings{Sha92b, author = {R. Sharma}, title = {A Probabilistic Framework for Dynamic Motion Planning in Partially Known Environments}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2459--2464}, address = {Nice, France}, month = may, year = {1992} } @inproceedings{ShaHerCuc92, author = {R. Sharma and J.-Y. Herv\'e and P. Cucka}, title = {Dynamic Robot Manipulation Using Visual Tracking}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1844--1849}, year = {1992} } @article{ShaLavHut96, author = {R. Sharma and S. M. LaValle and S. A. Hutchinson}, title = {Optimizing Robot Motion Strategies for Assembly with Stochastic Models of the Assembly Process}, journal = {IEEE Trans. on Robotics and Automation}, volume = {12}, number = {2}, pages = {160--174}, month = apr, year = {1996} } @article{ShaMouAlo93, author = {R. Sharma and D. M. Mount and Y. Aloimonos}, title = {Probabilistic Analysis of Some Navigation Strategies in a Dynamic Environment}, journal = {IEEE Transactions on Systems, Man, \& Cybernetics}, volume = {23}, number = {5}, pages = {1465--1474}, month = sep, year = {1993} } @book{Sha97b, author = {R. W. Sharpe}, title = {Differential Geometry}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1997} } @inproceedings{ShaKae97, author = {H. Shatkay and L. P. Kaelbling}, title = {Learning topological maps with weak local odometric information}, booktitle = {Proceedings International Joint Conference on Artificial Intelligence}, year = {1997} } @article{She92, author = {T. Shermer}, title = {Recent Results in Art Galleries}, journal = {Proceedings of the IEEE}, volume = {80}, number = {9}, pages = {1384--1399}, month = sep, year = {1992} } @article{ShiLeeGru90, author = {C. L. Shih and T.-T. Lee and W. A. Gruver}, title = {A Unified Approach for Robot Motion Planning with Moving Polyhedral Obstacles}, journal = {IEEE Transactions on Systems, Man, \& Cybernetics}, volume = {20}, pages = {903--915}, year = {1990} } @inproceedings{ShiDub85, author = {Z. Shiller and S. Dubowsky}, title = {On the optimal control of robotic manipulators with actuator and end-effector constraints}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {614--620}, year = {1985} } @article{ShiDub91, author = {Z. Shiller and S. Dubowsky}, title = {On Computing Global Time-Optimal Motions of Robotic Manipulators in the Presence of Obstacles}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {7}, number = {6}, pages = {785--797}, month = dec, year = {1991} } @article{ShiLu92, author = {Z. Shiller and H.-H. Lu}, title = {Computation of Path Constrained Time-Optimal Motions with Dynamic Singularities}, journal = {Transactions of the ASME, Journal of Dynamical Systems, Measurement, \& Control}, volume = {114}, pages = {34--40}, year = {1992} } @article{ShiMck85, author = {K. G. Shin and N. D. McKay}, title = {Minimum-time Control of Robot Manipulators with Geometric Path Constraints}, journal = {IEEE Transactions on Automatic Control}, volume = {30}, number = {6}, pages = {531--541}, year = {1985} } @article{ShiMck86, author = {K. G. Shin and N. D. McKay}, title = {A Dynamic Programming Approach to Trajectory Planning of Robotic Manipulators}, journal = {IEEE Transactions on Automatic Control}, volume = {31}, number = {6}, pages = {491--500}, year = {1986} } @article{ShiZhe92, author = {K. G. Shin and Q. Zheng}, title = {Minimum-time collision-free trajectory planning for dual-robot systems}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {8}, number = {5}, pages = {641--644}, month = oct, year = {1992} } @article{ShkLum97, author = {A. M. Shkel and V. J. Lumelsky}, title = {Incorporating Body Dynamics Into Sensor-Based Motion Planning: The Maximum Turn Strategy}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {13}, number = {6}, pages = {873--880}, month = dec, year = {1997} } @inproceedings{SinDud01, author = {R. Sim and G. Dudek}, title = {Learning generative models of scene features}, booktitle = {Proceedings IEEE Conference on Computer Vision and Pattern Recognition}, pages = {920--929}, year = {2001} } @article{SimLauNis00, author = {T. Sim\'eon and J.-P. Laumond and C. Nissoux}, title = {Visibility based probabilistic roadmaps for motion planning}, journal = {Advanced Robotics}, volume = {14}, number = {6}, year = {2000} } @article{SimLerLau02, author = {T. Sim\'eon and S. Leroy and J.-P. Laumond}, title = {Path coordination for multiple mobile robots: {A} resolution complete algorithm}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {18}, number = {1}, month = feb, year = {2002} } @inproceedings{SimGooHaiKoeOsu97, author = {R. Simmons and R. Goodwin and K. Haigh and S. Koenig and J. O'Sullivan}, title = {A layered architecture for office delivery robots}, booktitle = {Proceedings First International Conference on Autonomous Agents}, address = {Marina del Rey, CA}, year = {1997} } @inproceedings{SimKoe95, author = {R. Simmons and S. Koenig}, title = {Probabilistic robot navigation in partially observable environments}, booktitle = {Proceedings International Joint Conference on Artificial Intelligence}, pages = {1080--1087}, year = {1995} } @inproceedings{SimLavSlu02, author = {B. Simov and S. M. LaValle and G. Slutzki}, title = {A Complete Pursuit-Evasion Algorithm for Two Pursuers Using Beam Detection}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, pages = {618--623}, year = {2002} } @inproceedings{SimSluLav00, author = {B. Simov and G. Slutzki and S. M. LaValle}, title = {Pursuit-Evasion Using Beam Detection}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, year = {2000} } @book{Sip97, author = {M. Sipser}, title = {Introduction to the Theory of Computation}, publisher = {PWS}, address = {Boston, MA}, year = {1997} } @article{SleTar85, author = {D. Sleator and R. Tarjan}, title = {Amortized efficiency of list update and paging rules}, journal = {Communications of the ACM}, volume = {28}, number = {2}, pages = {202--208}, month = {}, year = {1985} } @book{SloJoe94, author = {I. H. Sloan and S. Joe}, title = {Lattice Methods for Multiple Integration}, publisher = {Oxford Science}, address = {Englewood Cliffs, NJ}, year = {1994} } @article{SloYan89, author = {J.-J. E. Slotine and H. S. Yang}, title = {Improving the Efficiency of Time-Optimal Path-Following Algorithms}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {5}, number = {1}, pages = {118--124}, year = {1989} } @inproceedings{SmaPac00, author = {W. D. Smart and L. P. Kaelbling}, title = {Practical Reinforcement Learning in Continuous Spaces}, booktitle = {Proceedings International Conference on Machine Learning}, year = {2000} } @article{SmiFraJon00, author = {D. Smith and J. Frank and A. J\'onsson}, title = {Bridging the Gap Between Planning and Scheduling}, journal = {Knowledge Engineering Review}, volume = {15}, number = {1}, pages = {47--83}, year = {2000} } @article{SmiChe86, author = {R. C. Smith and P. Cheeseman}, title = {On the Representation and Estimation of Spatial Uncertainty}, journal = {International Journal of Robotics Research}, volume = {5}, number = {4}, pages = {56--68}, year = {1986} } @article{SmiNauThr98, author = {S. J. J. Smith and D. S. Nau and T. Throop}, title = {Computer Bridge: {A} Big Win for {AI} Planning}, journal = {AI Magazine}, volume = {19}, number = {2}, pages = {93--105}, year = {1998} } @article{Son78, author = {E. J. Sondik}, title = {The optimal control of partially observable {M}arkov processes over the infinite horizon: {D}iscounted costs}, journal = {Operations Research}, volume = {9}, number = {2}, pages = {149--168}, year = {1978} } @article{SonAma02, author = {G. Song and N. M. Amato}, title = {Using Motion Planning to Study Protein Folding Pathways}, journal = {Journal of Computational Biology}, volume = {26}, number = {2}, pages = {282--304}, year = {2002} } @inproceedings{Son93, author = {E. Sontag}, title = {Gradient technique for systems with no drift: {A} classical idea revisited}, booktitle = {Proceedings IEEE Conference Decision \& Control}, pages = {2706--2711}, month = dec, year = {1993} } @inproceedings{Sor93, author = {O. J. Sordalen}, title = {Conversion of a car with $n$ trailers into a chained form}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1382--1387}, year = {1993} } @incollection{SouBoi98, author = {P. Sou\`eres and J.-D. Boissonnat}, title = {Optimal Trajectories for Nonholonomic Mobile Robots}, booktitle = {Robot Motion Planning and Control}, pages = {93--169}, editor = {J.-P. Laumond}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1998} } @inproceedings{SouLau96, author = {P. Sou\`{e}res and J.-P. Laumond}, title = {Shortest Paths Synthesis for a Car-Like Robot}, booktitle = {IEEE Transactions on Automatic Control}, pages = {672--688}, year = {1996} } @inproceedings{SpeHut92, author = {R. Spence and S. A. Hutchinson}, title = {Dealing with Unexpected Moving Obstacles by Integrating Potential Field Planning with Inverse Dynamics Control}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {1485--1490}, year = {1992} } @book{Spi79, author = {M. Spivak}, title = {Differential Geometry}, publisher = {Publish or Perish}, address = {Houston, TX}, year = {1979} } @book{SpoHutVid05, author = {M. W. Spong and S. Hutchinson and M. Vidyasagar}, title = {Robot Modeling and Control}, publisher = {Wiley}, address = {New York}, year = {2005} } @article{Spr91, author = {R. L Sproull}, title = {Refinements to nearest-neighbor searching in k-dimensional trees}, journal = {Algorithmica}, volume = {6}, pages = {579--589}, year = {1991} } @incollection{Sta88, author = {W. Stadler}, title = {Fundamentals of Multicriteria Optimization}, booktitle = {Multicriteria Optimization in Engineering and in the Sciences}, pages = {1--25}, editor = {W. Stadler}, publisher = {Plenum Press}, address = {New York}, year = {1988} } @book{StaWoo86, author = {H. Stark and J. W. Woods}, title = {Probability, Random Processes, and Estimation Theory for Engineers}, publisher = {Prentice-Hall}, address = {Englewood Cliffs, NJ}, year = {1986} } @book{SteSte96, author = {L. A. Steen and J. A. Seebach Jr.}, title = {Counterexamples in Topology}, publisher = {Dover}, address = {New York}, year = {1996} } @book{Ste94b, author = {R. F. Stengel}, title = {Optimal Control and Estimation}, publisher = {Dover}, address = {New York}, year = {1994} } @inproceedings{Ste94, author = {A. Stentz}, title = {Optimal and Efficient Path Planning for Partially-Known Environments}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {3310--3317}, year = {1994} } @inproceedings{Ste66, author = {D. Stewart}, title = {A Platform with Six Degrees of Freedom}, booktitle = {Institution of Mechanical Engineers, Proceedings 1965-66, 180 Part 1}, pages = {371--386}, year = {1966} } @inproceedings{StiKuf04, author = {M. Stilman and J. J. Kuffner}, title = {Navigation Among Movable Obstacles: {R}eal-time Reasoning in Complex Environments}, booktitle = {Proceedings 2004 IEEE International Conference on Humanoid Robotics (Humanoids'04)}, year = {2004} } @article{StiHwaTom04, author = {D. Stipanovic and I. Hwang and C. J. Tomlin}, title = {Computation of an Overapproximation of the Backward Reachable Set using Subsystem Level Set Functions, Dynamics of Continuous, Discrete, and Impulsive Systems}, journal = {Series A: Mathematical Analysis}, volume = {11}, pages = {399--411}, year = {2004} } @book{Str93, author = {P. D. Straffin}, title = {Game Theory and Strategy}, publisher = {Mathematical Association of America}, address = {Washington, DC}, year = {1993} } @inproceedings{Str04, author = {M. Strandberg}, title = {Augmenting {RRT}-planners with local trees}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {3258--3262}, year = {2004} } @phdthesis{Str04b, author = {M. Strandberg}, title = {Robot Path Planning: {An} Object-Oriented Approach}, address = {Stockholm, Sweden}, school = {Royal Institute of Technology (KTH)}, department = {Department of Signals, Sensors, and Systems}, year = {2004} } @article{SudPonSri00, author = {A. Sudsang and J. Ponce and N. Srinivasa}, title = {Grasping and In-Hand Manipulation: Geometry and Algorithms}, journal = {Algorithmica}, volume = {26}, pages = {466--493}, year = {2000} } @article{SudRotPon02, author = {A. Sudsang and F. Rothganger and J. Ponce}, title = {Motion Planning for Disc-Shaped Robots Pushing a Polygonal Object in the Plane}, journal = {IEEE Transactions on Robotics \& Automation}, volume = {18}, number = {4}, pages = {550--562}, year = {2002} } @article{Suk71, author = {A. G. Sukharev}, title = {Optimal Strategies of the Search for an Extremum}, journal = {U.S.S.R. Computational Mathematics and Mathematical Physics}, volume = {11}, number = {4}, note = {Translated from Russian, {\it Zh. Vychisl. Mat. i Mat. Fiz.}, 11, 4, 910-924, 1971}, year = {1971} } @techreport{SusTan91, author = {H. Sussmann and G. Tang}, title = {Shortest paths for the {Reeds-Shepp} car: {A} worked out example of the use of geometric techniques in nonlinear optimal control}, number = {SYNCON 91-10}, address = {Piscataway, NJ}, institution = {Dept. of Mathematics, Rutgers University}, year = {1991} } @article{Sus78, author = {H. J. Sussmann}, title = {A Sufficient Condition for Local Controllability}, journal = {SIAM Journal on Control \& Optimization}, volume = {16}, number = {5}, pages = {790--802}, year = {1978} } @article{Sus87, author = {H. J. Sussmann}, title = {A general theorem on local controllability}, journal = {SIAM Journal on Control \& Optimization}, volume = {25}, number = {1}, pages = {158--194}, year = {1987} } @inproceedings{Sus93, author = {H. J. Sussmann}, title = {A Continuation method for nonholonomic path-finding problems}, booktitle = {Proceedings IEEE Conference Decision \& Control}, pages = {2717--2723}, month = dec, year = {1993} } @inproceedings{Sus05, author = {H. J. Sussmann}, title = {A Very Non-Smooth Maximum Principle with State Constraints}, booktitle = {Proceedings IEEE Conference Decision \& Control}, pages = {917--922}, month = dec, year = {2005} } @article{SutMaa88, author = {K. Sutner and W. Maass}, title = {Motion Planning Among Time Dependent Obstacles}, journal = {Acta Informatica}, volume = {26}, pages = {93--122}, year = {1988} } @article{Sut88, author = {R. S. Sutton}, title = {Learning to Predict by the Methods of Temporal Differences}, journal = {Machine Learning}, volume = {3}, pages = {9--44}, year = {1988} } @article{SuzTazYamKam01, author = {I. Suzuki and Y. Tazoe and M. Yamashita and T. Kameda}, title = {Searching a Polygonal Region from the Boundary}, journal = {International Journal on Computational Geometry \& Applications}, volume = {11}, number = {5}, pages = {529--553}, year = {2001} } @article{SuzYam92, author = {I. Suzuki and M. Yamashita}, title = {Searching for a Mobile Intruder in a Polygonal Region}, journal = {SIAM Journal on Computing}, volume = {21}, number = {5}, pages = {863--888}, month = oct, year = {1992} } @article{SuzYamUmeKam98, author = {I. Suzuki and M. Yamashita and H. Umemoto and T. Kameda}, title = {Bushiness and a Tight Worst-Case Upper Bound on the Search Number of a Simple Polygon}, journal = {Information Processing Letters}, volume = {66}, pages = {49--52}, year = {1998} } @inproceedings{SveOve95, author = {P. Svestka and M. H. Overmars}, title = {Coordinated motion planning for multiple car-like robots using probabilistic roadmaps}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1631--1636}, year = {1995} } @article{TakFacLat94, author = {H. Takeda and C. Facchinetti and J.-C. Latombe}, title = {Planning the Motions of a Mobile Robot in a Sensory Uncertainty Field}, journal = {IEEE Transactions Pattern Analysis Machine Intelligence}, volume = {16}, number = {10}, pages = {1002--1017}, month = oct, year = {1994} } @inproceedings{TakLat92, author = {H. Takeda and J.-C. Latombe}, title = {Sensory Uncertainty Field for Mobile Robot Navigation}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {2465--2472}, address = {Nice, France}, month = may, year = {1992} } @book{Tez95, author = {S. Tezuka}, title = {Uniform Random Numbers: {T}heory and Practice}, publisher = {Kluwer}, address = {Boston, MA}, year = {1995} } @incollection{Tez02, author = {S. Tezuka}, title = {{Quasi-Monte Carlo}: The Discrepancy Between Theory and Practice}, booktitle = {Monte Carlo and Quasi-Monte Carlo Methods 2000}, pages = {124--140}, editor = {K.-T. Fang and F. J. Hickernell and H. Niederreiter}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2002} } @inproceedings{Tho97, author = {M. Thorup}, title = {Undirected Single Source Shortest Paths in Linear Time}, booktitle = {Proceedings IEEE Symposium on Foundations of Computer Science}, pages = {12--21}, year = {1997} } @article{Thr00, author = {S. Thrun}, title = {Probabilistic Algorithms in Robotics}, journal = {AI Magazine}, volume = {21}, number = {4}, pages = {93--109}, year = {2000} } @article{ThrBurFox98, author = {S. Thrun and W. Burgard and D. Fox}, title = {A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots}, journal = {Machine Learning}, volume = {31}, number = {5}, pages = {1--25}, month = apr, year = {1998} } @book{ThrBurFox05, author = {S. Thrun and W. Burgard and D. Fox}, title = {Probabilistic Robotics}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {2005} } @inproceedings{TovGuiLav04, author = {B. Tovar and L. Guilamo and S. M. LaValle}, title = {Gap Navigation Trees: {A} Minimal Representation for Visibility-Based Tasks}, booktitle = {Proceedings Workshop on Algorithmic Foundations of Robotics}, pages = {11--26}, year = {2004} } @inproceedings{TovLavMur03b, author = {B. Tovar and S. M. LaValle and R. Murrieta}, title = {Locally-Optimal Navigation in Multiply-Connected Environments without Geometric Maps}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2003} } @inproceedings{TovLavMur03, author = {B. Tovar and S. M. LaValle and R. Murrieta}, title = {Optimal Navigation and Object Finding without Geometric Maps or Localization}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, pages = {464--470}, year = {2003} } @article{Tsi95, author = {J. N. Tsitsiklis}, title = {Efficient Algorithms for Globally Optimal Trajectories}, journal = {IEEE Transactions on Automatic Control}, volume = {40}, number = {9}, pages = {1528--1538}, month = sep, year = {1995} } @phdthesis{Udu77, author = {S. Udupa}, title = {Collision Detection and Avoidance in Computer Controlled Manipulators}, school = {Dept. of Electrical Engineering, California Institute of Technology}, year = {1977} } @misc{Uni99, author = {{University of North Carolina}}, title = {{PQP}: {A} Proximity Query Package}, howpublished = {GAMMA Research Group, Available from {http://www.cs.unc.edu/$\sim$geom/SSV/}}, year = {2005} } @inproceedings{UrmSim03, author = {C. Urmson and R. Simmons}, title = {Approaches for Heuristically Biasing {RRT} Growth}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, year = {2003} } @inproceedings{VanOve04, author = {J. van den Berg and M. Overmars}, title = {Roadmap-based Motion Planing in Dynamic Environments}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {1598--1605}, year = {2004} } @inproceedings{VanOve05, author = {J. van den Berg and M. Overmars}, title = {Prioritized Motion Planning for Multiple Robots}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {2217--2222}, year = {2005} } @article{Van35, author = {J. G. van der Corput}, title = {Verteilungsfunktionen {I}}, journal = {Akademie van Wetenschappen}, volume = {38}, pages = {813--821}, year = {1935} } @incollection{Van90, author = {D. Vanderpooten}, title = {Multiobjective Programming: Basic Concepts and Approaches}, booktitle = {Stochastic vs. Fuzzy Approaches to Multiobjective Mathematical Programming under Uncertainty}, pages = {7--22}, editor = {R. Slowinski and J. Teghem}, publisher = {Kluwer}, address = {Boston, MA}, year = {1990} } @incollection{Veg04, author = {G. Vegter}, title = {Computational Topology}, booktitle = {Handbook of Discrete and Computational Geometry, 2nd Ed.}, pages = {719--742}, editor = {J. E. Goodman and J. O'Rourke}, publisher = {Chapman and Hall/CRC Press}, address = {New York}, year = {2004} } @incollection{VenLau97, author = {M. Vendittelli and J.-P. Laumond}, title = {Visible Positions for a Car-Like Robot amidst Obstacles}, booktitle = {Algorithms for Robotic Motion and Manipulation}, pages = {213--228}, editor = {J.-P. Laumond and M. H. Overmars}, publisher = {A.K. Peters}, address = {Wellesley, MA}, year = {1997} } @article{Von28, author = {J. von Neumann}, title = {Zur {T}heorie der {G}esellschaftsspiele}, journal = {Mathematische Annalen}, volume = {100}, pages = {295--320}, year = {1928} } @book{VonMor44, author = {J. von Neumann and O. Morgenstern}, title = {Theory of Games and Economic Behavior}, publisher = {Princeton University Press}, address = {Princeton, NJ}, year = {1944} } @book{WalWal04, author = {G. Walker and D. Walker}, title = {The Official Rock Paper Scissors Strategy Guide}, publisher = {Fireside}, year = {2004} } @incollection{WanHic02, author = {X. Wang and F. J. Hickernell}, title = {An Historical Overview of Lattice Point Sets}, booktitle = {Monte Carlo and Quasi-Monte Carlo Methods 2000}, pages = {158--167}, editor = {K.-T. Fang and F. J. Hickernell and H. Niederreiter}, publisher = {Springer-Verlag}, address = {Berlin}, year = {2002} } @book{War83, author = {F. W. Warner}, title = {Foundations of Differentiable Manifolds and Lie Groups}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1983} } @book{Wat02, author = {D. S. Watkins}, title = {Fundamentals of Matrix Computations, 2nd Ed.}, publisher = {Wiley}, address = {New York}, year = {2002} } @inproceedings{WeiWetVon94, author = {G. Weiss and C. Wetzler and E. von Puttkamer}, title = {Keeping track of position and orientation of moving indoor systems by correlation of range-finder scans}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {595--601}, year = {1994} } @article{Wel99, author = {D. Weld}, title = {Recent Advances in {AI} Planning}, journal = {AI Magazine}, volume = {20}, number = {2}, year = {1999} } @incollection{Wen96, author = {J. T. Wen}, title = {Control of nonholonomic systems}, booktitle = {The Control Handbook}, pages = {1359--1368}, editor = {W. S. Levine}, publisher = {CRC Press}, address = {Boca Raton, FL}, year = {1996} } @article{Wey16, author = {H. Weyl}, title = {{\"Uber die {G}leichverteilung von {Z}ahlen mod Eins}}, journal = {Mathematische Annalen}, volume = {77}, pages = {313--352}, year = {1916} } @article{Whi77, author = {D. Whitney}, title = {Force Feedback Control of Manipulator Fine Motions}, journal = {Transactions of the ASME, Journal of Dynamical Systems, Measurement, \& Control}, volume = {99}, pages = {91--97}, year = {1977} } @inproceedings{Whi86, author = {D. E. Whitney}, title = {Real Robots Don't Need Jigs}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {1986} } @incollection{Whi65, author = {H. Whitney}, title = {Local properties of analytic varieties}, booktitle = {Differential and Combinatorial Topology}, pages = {205--244}, editor = {S. Cairns}, publisher = {Princeton University Press}, address = {Princeton, NJ}, year = {1965} } @inproceedings{WieGolPesBro96, author = {J. Wiegley and K. Goldberg and M. Peshkin and M. Brokowski}, title = {A complete algorithm for designing passive fences to orient parts}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1133--1139}, year = {1996} } @phdthesis{Wij01, author = {O. Wijk}, title = {Triangulation-Based Fusion of Sonar Data with Application in Mobile Robot Mapping and Localization}, address = {Stockholm, Sweden}, school = {Royal Institute of Technology (KTH)}, department = {Department of Signals, Sensors, and Systems}, year = {2001} } @inproceedings{WilAmaSti99, author = {S. A. Wilmarth and N. M. Amato and P. F. Stiller}, title = {{MAPRM}: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1024--1031}, year = {1999} } @article{WilKavLatLoz95, author = {R. Wilson and L. Kavraki and J.-C. Latombe and T. Lozano-P\'erez}, title = {Two-Handed Assembly Sequencing}, journal = {International Journal of Robotics Research}, volume = {14}, number = {4}, pages = {335--350}, year = {1995} } @phdthesis{Wil92, author = {R. H. Wilson}, title = {On Geometric Assembly Planning}, address = {Stanford, CA}, school = {Stanford University}, department = {Department of Computer Science}, month = mar, year = {1992} } @article{WilLat94, author = {R. H. Wilson and J.-C. Latombe}, title = {Geometric Reasoning about Mechanical Assembly}, journal = {Artificial Intelligence Journal}, volume = {71}, number = {2}, pages = {371--396}, year = {1994} } @book{Win92, author = {P. H. Winston}, title = {Artificial Intelligence}, publisher = {Addison-Wesley}, address = {Reading, MA}, year = {1992} } @inproceedings{WonMidMac02, author = {S. C. Wong and L. Middleton and B. A. MacDonald}, title = {Performance Metrics for Robot Coverage Tasks}, booktitle = {Proceedings Australasian Conference on Robotics and Automation}, year = {2002} } @article{Wu83, author = {C. F. J. Wu}, title = {On the convergence properties of the {EM} algorithm}, journal = {The Annals of Statistics}, volume = {11}, number = {1}, pages = {95--103}, year = {1983} } @article{XuJor96, author = {L. Xu and M. I. Jordan}, title = {On convergence properties of the {EM} algorithm for {G}aussian mixtures}, journal = {Neural Computation}, volume = {8}, pages = {129--151}, year = {1996} } @article{YakLavKav01, author = {J. Yakey and S. M. LaValle and L. E. Kavraki}, title = {Randomized Path Planning for Linkages with Closed Kinematic Chains}, journal = {IEEE Transactions on Robotics and Automation}, volume = {17}, number = {6}, pages = {951--958}, month = dec, year = {2001} } @inproceedings{YamKufHod04, author = {K. Yamane and J. J. Kuffner and J. K. Hodgins}, title = {Synthesizing animations of human manipulation tasks}, booktitle = {Proceedings ACM SIGGRAPH}, year = {2004} } @article{YamUmeSuzKam01, author = {M. Yamashita and H. Umemoto and I. Suzuki and T. Kameda}, title = {Searching for a Mobile Intruder in a Polygonal Region by a Group of Mobile Searchers}, journal = {Algorithmica}, volume = {31}, pages = {208--236}, year = {2001} } @inproceedings{YamSchAda02, author = {B. Yamauchi and A. Schultz and W. Adams}, title = {Mobile Robot Exploration and Map-Building with Continuous Localization}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {3715--3720}, year = {2002} } @article{YanLav04, author = {L. Yang and S. M. LaValle}, title = {The Sampling-Based Neighborhood Graph: A Framework for Planning and Executing Feedback Motion Strategies}, journal = {IEEE Transactions on Robotics and Automation}, volume = {20}, number = {3}, pages = {419--432}, month = jun, year = {2004} } @book{Yan97, author = {Q. Yang}, title = {Intelligent Planning}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1997} } @book{YavPac87, author = {Y. Yavin and M. Pachter}, title = {Pursuit-Evasion Differential Games}, publisher = {Pergamon}, address = {Oxford, U.K.}, year = {1987} } @inproceedings{YerJaiSimLav05, author = {A. Yershova and L. Jaillet and T. Simeon and S. M. LaValle}, title = {Dynamic-Domain {RRTs}: {E}fficient Exploration by Controlling the Sampling Domain}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, year = {2005} } @inproceedings{YerLav04, author = {A. Yershova and S. M. LaValle}, title = {Deterministic Sampling Methods for Spheres and {SO(3)}}, booktitle = {Proceedings IEEE International Conference on Robotics and Automation}, year = {2004} } @inproceedings{YerTovGhrLav05, author = {A. Yershova and B. Tovar and R. Ghrist and S. M. LaValle}, title = {Bitbots: {Simple} Robots Solving Complex Tasks}, booktitle = {AAAI National Conference on Artificial Intelligence}, year = {2005} } @inproceedings{Yia93, author = {P. N. Yianilos}, title = {Data Structures and Algorithms for Nearest Neighbor Search in General Metric spaces}, booktitle = {ACM-SIAM Symposium on Discrete Algorithms}, pages = {311--321}, year = {1993} } @article{Yon88, author = {J. Yong}, title = {On Differential Evasion Games}, journal = {SIAM Journal on Control \& Optimization}, volume = {26}, number = {1}, pages = {1--22}, month = jan, year = {1988} } @article{Yon88b, author = {J. Yong}, title = {On Differential Pursuit Games}, journal = {SIAM Journal on Control \& Optimization}, volume = {26}, number = {2}, pages = {478--495}, month = mar, year = {1988} } @article{Yon90, author = {J. Yong}, title = {A Zero-Sum Differential Game in a Finite Duration with Switching Strategies}, journal = {SIAM Journal on Control \& Optimization}, volume = {28}, number = {5}, pages = {1234--1250}, month = sep, year = {1990} } @book{Yos90, author = {T. Yoshikawa}, title = {Foundations of Robotics: Analysis and Control}, publisher = {MIT Press}, address = {Cambridge, MA}, year = {1990} } @inproceedings{YuGup98, author = {Y. Yu and K. Gupta}, title = {On Sensor-based Roadmap: A Framework for Motion Planning for a Manipulator Arm in Unknown Environments}, booktitle = {Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems}, pages = {1919--1924}, year = {1998} } @article{Zab89, author = {J. Zabczyk}, title = {Some comments on stabilizability}, journal = {Applied Mathematics and Optimization}, volume = {19}, number = {1}, pages = {1--9}, year = {1989} } @inproceedings{Zar89, author = {L. S. Zaremba}, title = {Differential Games Reducible to Optimal Control Problems}, booktitle = {Proceedings IEEE Conference Decision \& Control}, pages = {2449--2450}, address = {Tampa, FL}, month = dec, year = {1989} } @inproceedings{ZefBur98, author = {M. Zefran and J. Burdick}, title = {Stabilization of systems with changing dynamics by means of switching}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1090--1095}, year = {1998} } @inproceedings{ZefDesKum96, author = {M. Zefran and J. Desai and V. Kumar}, title = {Continuous Motion Plans for Robotic Systems with Changing Dynamic Behavior}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, year = {1996} } @book{ZelBor94, author = {M. I. Zelikin and V. F. Borisov}, title = {Theory of Chattering Control}, publisher = {{Birkh\"auser}}, address = {Boston, MA}, year = {1994} } @article{ZhaWhiWanGolKavHas05, author = {M. Zhang and R. A. White and L. Wang and R. N. Goldman and L. E. Kavraki and B. Hassett}, title = {Improving conformational searches by geometric screening}, journal = {Bioinformatics}, volume = {21}, number = {5}, pages = {624--630}, year = {2005} } @article{ZhaZha01, author = {N. L. Zhang and W. Zhang}, title = {Speeding up the convergence of value iteration in partially observable {M}arkov decision processes}, journal = {Journal of Artificial Intelligence Research}, volume = {14}, pages = {29--51}, year = {2001} } @inproceedings{ZhoHan01, author = {R. Zhou and E. A. Hansen}, title = {An improved grid-based approximation algorithm for {POMDPs}}, booktitle = {Proceedings International Joint Conference on Artificial Intelligence}, year = {2001} } @inproceedings{ZhoChi03, author = {Y. Zhou and G. S. Chirikjian}, title = {Probabilistic models of dead-reckoning error in nonholonomic mobile robots}, booktitle = {Proceedings IEEE International Conference on Robotics \& Automation}, pages = {1594--1599}, year = {2003} } @incollection{Zio85, author = {S. Zionts}, title = {Multiple Criteria Mathematical Programming: An Overview and Several Approaches}, booktitle = {Mathematics of Multi-Objective Optimization}, pages = {227--273}, editor = {P. Serafini}, publisher = {Springer-Verlag}, address = {Berlin}, year = {1985} }