RANDOMIZED MOTION PLANNING: A TUTORIAL

S. Carpin

References

  1. [1] J.C. Latombe, Motion planning: A journey of robots, molecules, digital actors, and other artifacts, International Journal of Robotics Research, Special Issue on Robotics at the Millennium, 18 (11), 1999, 1119–1128.
  2. [2] J. Canny, Some algebraic and geometric computations in space, Proc. of FOCS, 1988, 460–467.
  3. [3] J.H. Reif, Complexity of the mover’s problem and generalization, Proc. of FOCS, 1979, 421–427.
  4. [4] J. Canny, The complexity of robot motion planning (Cambridge, MA: MIT Press, 1988).
  5. [5] S.M. LaValle & M.S. Branicky, On the relationship between classical grid search and probabilistic roadmaps, in J.-D. Boissonat et al. (Eds.), Algorithmic foundations of robotics (Berlin: Springer-Verlag, 2003).
  6. [6] S.R. Lindemann & S.M. LaValle, Current issues in samplingbased motion planning, Proc. 8th Int. Symp. on Robotics Research (Springer-Verlag, 2004).
  7. [7] S. Carpin & E. Pagello, Exploiting multi-robot geometry for efficient randomized motion planning, Maria Gini et al. (Eds.), Intelligent autonomous systems 7 (IOS Press, 2002).
  8. [8] P. Svestka & M.H. Overmars, Coordinated path planning for multiple robots, Robotics and Autonomous Systems, 23 (3), 1998, 125–152. doi:10.1016/S0921-8890(97)00033-X
  9. [9] G. Sánchez & J.C Latombe, Using a prm planner to compare centralized and decoupled planning for multi-robot systems, ICRA, 2002, 2112–2119. doi:10.1109/ROBOT.2002.1014852
  10. [10] J. Cortes, T. Simeon, & J.P. Laumond, A random loop generator for planning the motions of closed kinematics chains using prm methods, ICRA, 2002, 2141–2146. doi:10.1109/ROBOT.2002.1014856
  11. [11] L. Han & N. Amato, A kinematics-based probabilistic roadmap method for closed chain systems, in B. Donald et al. (Eds.), Algorithmic and computational robotics: New directions (A.K. Peters, 2000).
  12. [12] J.H. Yakey, S.M. LaValle, & L.E. Kavraki, Randomized path planning for linkages with closed kinematic chains, IEEE Trans. on Robotics and Automation, 17 (6), 2001, 951–958. doi:10.1109/70.976030
  13. [13] O. Burchan Bayazit, J-.M. Lien, & N.M. Amato, Probabilistic roadmap motion planning for deformable objects, ICRA, 2002, 2126–2133.
  14. [14] F. Lamiraux & L.E. Kavraki, Planning paths for elastic objects under manipulation constraints, International Journal of Robotics Research, 20 (3), 2001, 188–208. doi:10.1177/02783640122067354
  15. [15] S. Carpin & E. Pagello, On parallel rrts for multi-robot systems, Proc. 8th Conf. of the Italian Association for Artificial Intelligence, 2002, 834–841.
  16. [16] D. Challou, D. Boley, M. Gini, V. Kumar, & C. Olson, Parallel search algorithms for robot motion planning, in K. Gupta & A.P. del Pobil (Eds.), Practical motion planning (John Wiley & Sons, 1998). 194
  17. [17] D. Hsu, L.E. Kavraki, J-C. Latombe, & R. Motwani, Capturing the connectivity of high-dimensional geometric spaces by parallelizable random sampling techniques, in P.M. Pardalos & S. Rajasekaran (Eds.), Advances in randomized parallel computing (Boston: Kluwer 1999).
  18. [18] J. Basch, L.J. Guibas, D. Hsu, & A.T. Nguyen, Disconnection proofs for motion planning, ICRA, 2001, 1765–1772. doi:10.1109/ROBOT.2001.932865
  19. [19] P. Cheng & S.M. LaValle, Resolution complete rapidlyexploring random trees, ICRA, 2002, 267–272. doi:10.1109/ROBOT.2002.1013372
  20. [20] J. Barraquand & J.C. Latombe, Robot motion planning: A distributed representation approach, International Journal of Robotics Research, 10 (6), 1991, 628–649. doi:10.1177/027836499101000604
  21. [21] Y.K. Hwang & N. Ahuja, Gross motion planning: A survey, ACM Computational Surveys, 24 (3), 1992, 219–290. doi:10.1145/136035.136037
  22. [22] J.C. Latombe, Robot motion planning (Kluver, 1990).
  23. [23] S.M. LaValle, Planning algorithms, available online.
  24. [24] J.T. Schwartz & M. Sharir, Algorithmic motion planning in robotics, in Handbook of theoretical computer science, Vol. 1, chap. 8 (Elsevier, 1990).
  25. [25] T. Lozano-Pérez, Spatial planning: A configuration space approach, IEEE Trans. on Computers, C-32 (2), 1983, 108–120. doi:10.1109/TC.1983.1676196
  26. [26] B. Donald, P. Xavier, J. Canny, & J. Reif, Kinodynamic motion planning, Journal of the ACM, 40 (5), 1993, 1048–1066. doi:10.1145/174147.174150
  27. [27] B. Donald & P. Xavier, Provably good approximation algorithms for optimal kinodynamic planning for cartesian robots and open chain manipulators, Algorithmica, 14 (6), 1995, 480– 530. doi:10.1007/BF01586637
  28. [28] B. Donald & P. Xavier, Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamic bounds, Algorithmica, 14 (6), 1995, 443–479. doi:10.1007/BF01586636
  29. [29] L.E. Kavraki, P. Svestka, J.C. Latombe, & M.H. Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Trans. on Robotics and Automation, 12 (4), 1996, 566–580. doi:10.1109/70.508439
  30. [30] L. Kavraki & J.-C. Latombe, Randomized preprocessing of configuration space for fast path planning, ICRA, 1994, 2138– 2145. doi:10.1109/ROBOT.1994.350966
  31. [31] M. Overmars & P. Svestka, A probabilistic learning approach to motion planning, in K. Goldberg et al. (Eds.), Algorithmic foundations of robotics (A.K. Peters, 1995).
  32. [32] B. Glavina, Solving findpath by combination of goal-girected and randomized search, ICRA, 1990, 1718–1723. doi:10.1109/ROBOT.1990.126257
  33. [33] E. Mazer, J.M. Ahuactzin, & P. Bessiére, The ariadne’s clew algorithm, Journal of Artificial Intelligence Research, 9, Natick-MA, 1998, 295–316.
  34. [34] N.M. Amato, O.B. Bayazit, L.K. Dale, & C. Jone, Choosing good distances metrics and local planners for probabilistic roadmap methods, IEEE Trans. on Robotics and Automation, 16 (4), 2000, 442–447. doi:10.1109/70.864240
  35. [35] R. Geraerters & M.H. Overmars, A comparative study of probabilistic roadmap planners, in J.D. Boissonat et al. (Eds.), Workshop on algorithmic foundations of robotics (Springer, 2002).
  36. [36] F. Schwarzer, M. Saha, & J.C. Latombe, Exact collision checking of robot paths, in J.D. Boissonat et al. (Eds.), Workshop on algorithmic foundations of robotics (Springer, 2002).
  37. [37] N.M. Amato & L.K. Dale, Probabilistic roadmaps are embarrassingly parallel, ICRA, 1999, 688–694.
  38. [38] R. Bohlin, Path planning in practice: Lazy evaluation on a multi-resolution grid, IROS, 2001, 49–54.
  39. [39] C. Nissoux, T. Siméon, & J.P. Laumond, Visibility based probabilistic roadmaps, IROS, 1999, 1316–1321.
  40. [40] N.M. Amato, O. Burchand Bayazit, L.K. Dale, H. Jones, & D. Vallejo, Obprm: An obstacle-based prm for 3d workspaces, in P.K. Agarwal et al. (Eds.), Robotics: The algorithmic perspective: The 3rd Workshop on the Algorithmic Foundations of Robotics (A.K. Peters, 1998).
  41. [41] N.M. Amato& Y. Wu, A randomized roadmap method for path and manipulation planning, ICRA, 1996, 113–120.
  42. [42] J.-M. Lien, S.L. Thomas, & N.M. Amato, A general framework for sampling on the medial axis of the free space, ICRA, 2003. doi:10.1109/ROBOT.2003.1242288
  43. [43] S.A. Wilmarth, N.M. Amato, & P.F. Stiller, Motion planning for a rigid body using random networks on the medial axis of the free space, Proc. 15th Annual ACM Symp. on Computational Geometry, 1999, 173–180. doi:10.1145/304893.304967
  44. [44] S.A. Wilmarth, N.M. Amato, & P.F. Stiller, A probabilistic roadmap planner with sampling on the medial axis of the free space, ICRA, 1999, 1024–1031. doi:10.1109/ROBOT.1999.772448
  45. [45] D. Hsu, L.E. Kavraki, J.C. Latombe, R. Motwani, & S. Sorkin, On finding narrow passages with probabilistic roadmap planners, in P.K. Agarwal et al. (Eds.), Robotics: The algorithmic perspective: The 3rd Workshop on the Algorithmic Foundations of Robotics (A.K. Peters, 1998).
  46. [46] L.E. Kavraki, M.N. Kolountzakis, & J.C. Latombe, Analysis of probabilistic roadmaps for path planning, IEEE Trans. on Robotics and Automation, 14(1), 1998, 166–171. doi:10.1109/70.660866
  47. [47] J. Barraquand, L. Kavraki, J. Latombe, T. Li, R. Motwani, & P. Raghavan, A random sampling scheme for robot path planning, International Journal of Robotics Research, 15(6), 1997, 759–774.
  48. [48] L.E. Kavraki, J.C. Latombe, R. Motwani, & P. Raghavan, Randomized query processing in robot path planning, Journal of Computer and Systems Science, 57(1), 1998, 50–60. doi:10.1006/jcss.1998.1578
  49. [49] A. Ladd & L. Kavraki, Generalizing the analysis of prm, ICRA, 2002, 2120–2125. doi:10.1109/ROBOT.2002.1014853
  50. [50] S.M. LaValle, Rapidly-exploring random trees, Technical Report TR 98-11, Computer Science Department, Iowa State University, October 1998.
  51. [51] S.M. LaValle & J.J. Kuffner, Randomized kinodynamic planning, ICRA, 1999, 473–479.
  52. [52] P. Cheng, Z. Shen, & S.M. LaValle, RRT-based trajectory design for autonomous automobiles and spacecraft, Archives of Control Sciences, 11 (3–4), 2001, 167–194.
  53. [53] J.J. Kufner & S.M. LaValle, Rrt-connect: An efficient approach to single-query path planning, ICRA, San Francisco, April 2001, 995–1001.
  54. [54] S.M. LaValle &J.J. Kufner, Randomized kinodynamic planning, International Journal of Robotics Research, 20 (5), 2001, 378–400. doi:10.1177/02783640122067453
  55. [55] S.M. LaValle & J.J. Kufner, Rapidly-exploring random trees: Progress and prospects, in B. Donald et al. (Eds.), Algorithmic and computational robotics: New directions (A.K. Peters, 2001).
  56. [56] S. M. LaValle, From dynamic programming to RRTs: Algorithmic design of feasible trajectories, in A. Bicchi et al. (Eds.), Control problems in robotics (Berlin: Springer-Verlag, 2002).
  57. [57] J. Kufner, K. Nishiwaki, S. Kagami, M. Inaba, & H. Inoue, Motion planning for humanoid robots under obstacle and dynamic balance constraints, ICRA, 2001, 692–698.
  58. [58] J. Bruce & M. Veloso, Real-time randomized path planning for robot navigation, IROS, 2002, 2383–2388.
  59. [59] A. Atramentov & S.M. LaValle, Efficient nearest neighbor searching for motion planning, ICRA, 2002, 632–637.
  60. [60] P. Cheng & S.M. LaValle, Reducing metric sensitivity in randomized trajectory design, IROS, 2001.
  61. [61] M. Strandberg, Augmenting RRT-planners with local trees, ICRA, 2004, 3258–3262. doi:10.1109/ROBOT.2004.1308756
  62. [62] E. Plaku & L.E. Kavraki, Distributed sampling-based roadmap of trees for large-scale motion planning, ICRA, 2005, 3879– 3884.
  63. [63] D. Hsu, J.-C. Latombe, & R. Motwani, Path planning and expansive configuration spaces, International Journal of Computational Geometry and Applications, 9, 1999, 495–512. doi:10.1142/S0218195999000285
  64. [64] R. Kindel, D. Hsu, J.C. Latombe, & S. Rock, Kinodynamic motion planning amidst moving obstacles, ICRA, 2000, 537– 543.
  65. [65] D. Hsu, Randomized single-query motion planning in expansive spaces, doctoral diss., Department of Computer Science, Stanford University, 2000.
  66. [66] D. Hsu, R. Kindel, J.-C. Latombe, & S. Rock, Randomized kinodynamic motion planning with moving obstacles, in B. Donald et al. (Eds.), Algorithmic and computational robotics: New directions (A.K. Peters, 2000).
  67. [67] L.K. Dale & N.M. Amato, Probabilistic roadmaps: Putting it all together, ICRA, Seoul, May 2001, 1940–1947. doi:10.1109/ROBOT.2001.932892

Important Links:

Go Back