Asymptotically Near-Optimal Is Good Enough for Motion Planning

详细信息    查看全文

• 刊名：Springer Tracts in Advanced Robotics
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：100
• 期：1
• 页码：419-436
• 全文大小：589 KB
• 参考文献：1.I. Althöfer, G. Das, D. Dobkin, D. Joseph, J. Soares, On sparse spanners of weighted graphs. Discrete Comput. Geom. 9(1), 81–100 (1993)
  2.N.M. Amato, O.B. Bayazit, L.K. Dale, C. Jones, D. Vallejo, OBPRM: an obstacle-based PRM for 3D workspaces, in Workshop on the Algorithmic Foundations of Robotics (WAFR) (1998), pp. 155–168
  3.S. Baswana, S. Sen, A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30(4), 532–563 (2007)MathSciNet CrossRef MATH
  4.K. Bekris, L. Kavraki, Informed and probabilistically complete search for motion planning under differential constraints, in First International Symposium on Search Techniques in Artificial Intelligence and Robotics (STAIR) (Chicago, IL, 2008)
  5.R. Bohlin, L. Kavraki, Path planning using lazy PRM, in IEEE International Conference on Robotics and Automation (ICRA), vol. 1 (San Francisco, CA, 2000), pp. 521–528
  6.D. Ferguson, A. Stentz, Anytime RRTs, in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (Beijing, China, 2006), pp. 5369–5375
  7.J. Gao, L.J. Guibas, A. Nguyen, Deformable spanners and applications. Comput. Geometry Theory Appl. 35(1–2), 2–19 (2006)MathSciNet CrossRef MATH
  8.R. Geraerts, M.H. Overamrs, Creating small graphs for solving motion planning problems, in IEEE International Conference on Methods and Models in Automation and Robotics (MMAR) (2005), pp. 531–536
  9.R. Geraerts, M.H. Overmars, Creating high-quality roadmaps for motion planning in virtual environments, in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (Beijing, China, 2006), pp. 4355–4361
  10.R. Geraerts, M.H. Overmars, Reachability-based analysis for probabilistic roadmap planners. J. Robot. Auton. Syst. (RAS) 55, 824–836 (2007)CrossRef
  11.L.J. Guibas, C. Holleman, L.E. Kavraki, A probabilistic roadmap planner for flexible objects with a workspace medial-axis-based sampling approach, in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), vol. 1 (1999), pp. 254–259
  12.D. Hsu, R. Kindel, J.C. Latombe, S. Rock, Randomized kinodynamic motion planning with moving obstacles. Int. J. Robot. Res. 21(3), 233–255 (2002)CrossRef MATH
  13.L. Jaillet, T. Simeon, Path deformation roadmaps, in Workshop on the Algorithmic Foundations of Robotics (WAFR) (New York City, NY, 2006)
  14.S. Karaman, E. Frazzoli, Sampling-based algorothms for optimal motion planning. Int. J. Robot. Res. 30(7), 846–894 (2011)CrossRef
  15.S. Karaman, M. Walter, A. Perez, E. Frazzoli, S. Teller, Anytime motion planning using the RRT, in IEEE International Conference on Robotics and Automation (ICRA) (Shanghai, China, 2011)
  16.L.E. Kavraki, P. Svestka, J.C. Latombe, M. Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. (TRA) 12(4), 566–580 (1996)CrossRef
  17.J.M. Keil, Approximating the complete Euclidean graph, in 1st Scandinavian Workshop on Algorithm Theory (Springer, London, UK, 1988), pp. 208–213
  18.J. Kim, R.A. Pearce, N.M. Amato, Extracting optimal paths from roadmaps for motion planning, in IEEE International Conference on Robotics and Automation (ICRA), vol. 2 (Taipei, Taiwan, 2003), pp. 2424–2429
  19.S.M. LaValle, J.J. Kuffner, Randomized kinodynamic planning. Int. J. Robot. Res. 20(5), 378–400 (2001)CrossRef
  20.Y. Li, K.E. Bekris, Learning approximate cost-to-go metrics to improve sampling-based motion planning, in IEEE International Conference on Robotics and Automation (ICRA) (Shanghai, China, 2011)
  21.T. Lozano-Perez, Spatial planning: a configuration space approach. IEEE Trans. Comput. 108–120 (1983)
  22.J.D. Marble, K.E. Bekris, Computing spanners of asympotically optimal probabilistic roadmaps, in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (San Francisco, CA, 2011)
  23.M.A. Morales, R. Pearce, N.M. Amato, Metrics for analyzing the evolution of C-space models, in IEEE International Conference on Robotics and Automation (ICRA) (2006), pp. 1268–1273
  24.O. Nechushtan, B. Raveh, D. Halperin, Sampling-diagrams automata: a tool for analyzing path quality in tree planners, in Workshop on the Algorithmic Foundations of Robotics (WAFR) (Singapore, 2010)
  25.D. Nieuwenhuisen, M.H. Overmars, Using cycles in probabilistic roadmap graphs, in IEEE International Conference on Robotics and Automation (ICRA) (2004), pp. 446–452
  26.R. Pearce, M. Morales, N. Amato, Structural improvement filtering strategy for PRM, in Robotics: Science and Systems (RSS) (Zurich, Switzerland, 2008)
  27.D. Peleg, A. Scha¨ffer, Graph spanners. J. Graph Theory 13(1), 99–116 (1989)
  28.E. Plaku, K.E. Bekris, B.Y. Chen, A.M. Ladd, L.E. Kavraki, Sampling-based roadmap of trees for parallel motion planning. IEEE Trans. Robot. Autom. (TRA) 21(4), 587–608 (2005)
  29.B. Raveh, A. Enosh, D. Halperin, a little more, a lot better: improving path quality by a path-merging algorithm. IEEE Trans. Rob. 27(2), 365–370 (2011)CrossRef
  30.G. Sanchez, J.C. Latombe, A single-query, bi-directional probabilistic roadmap planner with lazy collision checking, in International Symposium on Robotics Research (2001), pp. 403–418
  31.E. Schmitzberger, J.L. Bouchet, M. Dufaut, D. Wolf, R. Husson, Capture of homotopy classes with probabilistic roadmap, in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (Switzerland, 2002), pp. 2317–2322
  32.T. Simeon, J.P. Laumond, C. Nissoux, Visibility-based probabilistic roadmaps for motion planning. Adv. Robot. J. 41(6), 477–494 (2000)CrossRef
  33.I.A. Sucan, M. Moll, L.E. Kavraki, The open motion planning library (OMPL) (2010). http://​ompl.​kavrakilab.​org
  34.R. Wein, J. van den Berg, D. Halperin, Planning high-quality paths and corridors amidst obstacles. Int. J. Robot. Res. 27(11–12), 1213–1231 (2008)CrossRef
  35.D. Xie, M. Morales, R. Pearce, S. Thomas, J.L. Lien, N.M. Amato, Incremental map generation (IMG), in Workshop on Algorithmic Foundations of Robotics (WAFR) (New York City, NY, 2006)
  
• 作者单位：James D. Marble (5)
  Kostas E. Bekris (5)
  
  5. Computer Science and Engineering Department, University of Nevada, 1664 N. Virginia St., MS 171, Reno, NV, 89557, USA
  
• 丛书名：Robotics Research
• ISBN：978-3-319-29363-9
• 刊物类别：Engineering
• 刊物主题：Automation and Robotics
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1610-742X
• 卷排序：100

文摘

Asymptotically optimal motion planners guarantee that solutions approach optimal as more iterations are performed. There is a recently proposed roadmap-based method that provides this desirable property, the PRM ∗ approach, which minimizes the computational cost of generating the roadmap. Even for this method, however, the roadmap can be slow to construct and quickly grows too large for storage or fast online query resolution. From graph theory, there are many algorithms that produce sparse subgraphs, known as spanners, which can guarantee near optimal paths. In this work, a method for interleaving an incremental graph spanner algorithm with the asymptotically optimal PRM ∗ algorithm is described. The result is an asymptotically near-optimal motion planning solution. Theoretical analysis and experiments performed on typical, geometric motion planning instances show that large reductions in construction time, roadmap density, and online query resolution time can be achieved with a small sacrifice of path quality. If smoothing is applied, the results are even more favorable for the near-optimal solution.