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, InternationalJournal of Robotics Research, Special Issue on Robotics at theMillennium, 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 betweenclassical 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 sampling-based motion planning, Proc. 8th Int. Symp. on RoboticsResearch (Springer-Verlag, 2004).
  7. [7] S. Carpin & E. Pagello, Exploiting multi-robot geometry forefficient 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 formultiple 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 comparecentralized 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 loopgenerator for planning the motions of closed kinematics chainsusing prm methods, ICRA, 2002, 2141–2146. doi:10.1109/ROBOT.2002.1014856
  11. [11] L. Han & N. Amato, A kinematics-based probabilistic roadmapmethod 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 pathplanning 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, Probabilisticroadmap 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 ofRobotics Research, 20 (3), 2001, 188–208. doi:10.1177/02783640122067354
  15. [15] S. Carpin & E. Pagello, On parallel rrts for multi-robotsystems, Proc. 8th Conf. of the Italian Association for ArtificialIntelligence, 2002, 834–841.
  16. [16] D. Challou, D. Boley, M. Gini, V. Kumar, & C. Olson, Parallelsearch 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 spacesby parallelizable random sampling techniques, in P.M. Pardalos & S. Rajasekaran (Eds.), Advances in randomized parallelcomputing (Boston: Kluwer 1999).
  18. [18] J. Basch, L.J. Guibas, D. Hsu, & A.T. Nguyen, Disconnectionproofs for motion planning, ICRA, 2001, 1765–1772. doi:10.1109/ROBOT.2001.932865
  19. [19] P. Cheng & S.M. LaValle, Resolution complete rapidly-exploring random trees, ICRA, 2002, 267–272. doi:10.1109/ROBOT.2002.1013372
  20. [20] J. Barraquand & J.C. Latombe, Robot motion planning: Adistributed representation approach, International Journal ofRobotics 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 inrobotics, in Handbook of theoretical computer science, Vol. 1,chap. 8 (Elsevier, 1990).
  25. [25] T. Lozano-Pérez, Spatial planning: A configuration spaceapproach, 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 motionplanning, 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 robotsand open chain manipulators, Algorithmica, 14 (6), 1995, 480–530. doi:10.1007/BF01586637
  28. [28] B. Donald & P. Xavier, Provably good approximation algo-rithms 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-dimensionalconfiguration 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 ofconfiguration space for fast path planning, ICRA, 1994, 2138–2145. doi:10.1109/ROBOT.1994.350966
  31. [31] M. Overmars & P. Svestka, A probabilistic learning approachto motion planning, in K. Goldberg et al. (Eds.), Algorithmicfoundations of robotics (A.K. Peters, 1995).
  32. [32] B. Glavina, Solving findpath by combination of goal-girectedand randomized search, ICRA, 1990, 1718–1723. doi:10.1109/ROBOT.1990.126257
  33. [33] E. Mazer, J.M. Ahuactzin, & P. Bessiére, The ariadne’sclew 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, Choosinggood distances metrics and local planners for probabilisticroadmap 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 ofprobabilistic 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 collisionchecking 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 amulti-resolution grid, IROS, 2001, 49–54.
  39. [39] C. Nissoux, T. Siméon, & J.P. Laumond, Visibility basedprobabilistic 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 algorithmicperspective: The 3rd Workshop on the Algorithmic Foundationsof Robotics (A.K. Peters, 1998).
  41. [41] N.M. Amato& Y. Wu, A randomized roadmap method forpath and manipulation planning, ICRA, 1996, 113–120.
  42. [42] J.-M. Lien, S.L. Thomas, & N.M. Amato, A general frameworkfor 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 planningfor a rigid body using random networks on the medial axis of thefree space, Proc. 15th Annual ACM Symp. on ComputationalGeometry, 1999, 173–180. doi:10.1145/304893.304967
  44. [44] S.A. Wilmarth, N.M. Amato, & P.F. Stiller, A probabilisticroadmap planner with sampling on the medial axis of the freespace, 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 algorithmicperspective: The 3rd Workshop on the Algorithmic Foundationsof Robotics (A.K. Peters, 1998).
  46. [46] L.E. Kavraki, M.N. Kolountzakis, & J.C. Latombe, Analysisof probabilistic roadmaps for path planning, IEEE Trans. onRobotics 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 pathplanning, 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, Journalof 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 StateUniversity, 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 trajectorydesign for autonomous automobiles and spacecraft, Archivesof Control Sciences, 11 (3–4), 2001, 167–194.
  53. [53] J.J. Kufner & S.M. LaValle, Rrt-connect: An efficient approachto single-query path planning, ICRA, San Francisco, April2001, 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.), Algorithmicand 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 anddynamic balance constraints, ICRA, 2001, 692–698.
  58. [58] J. Bruce & M. Veloso, Real-time randomized path planningfor robot navigation, IROS, 2002, 2383–2388.
  59. [59] A. Atramentov & S.M. LaValle, Efficient nearest neighborsearching for motion planning, ICRA, 2002, 632–637.
  60. [60] P. Cheng & S.M. LaValle, Reducing metric sensitivity inrandomized 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 roadmapof trees for large-scale motion planning, ICRA, 2005, 3879–3884.
  63. [63] D. Hsu, J.-C. Latombe, & R. Motwani, Path planning andexpansive 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, Kinodynamicmotion planning amidst moving obstacles, ICRA, 2000, 537–543.
  65. [65] D. Hsu, Randomized single-query motion planning in expan-sive spaces, doctoral diss., Department of Computer Science,Stanford University, 2000.
  66. [66] D. Hsu, R. Kindel, J.-C. Latombe, & S. Rock, Randomized kin-odynamic motion planning with moving obstacles, in B. Don-ald et al. (Eds.), Algorithmic and computational robotics: Newdirections (A.K. Peters, 2000).
  67. [67] L.K. Dale & N.M. Amato, Probabilistic roadmaps: Putting itall together, ICRA, Seoul, May 2001, 1940–1947. doi:10.1109/ROBOT.2001.932892

Important Links:

Go Back