Preview

Труды Института системного программирования РАН

Расширенный поиск

Обзор современных методов планирования движения

https://doi.org/10.15514/ISPRAS-2016-28(4)-14

Аннотация

Автоматизация технологически сложных процессов в машиностроении, энергетике, транспорте, медицине, строительстве, а также создание новых продуктов и сервисов невозможны без решения задач планирования движения. В последнее время интерес к ним заметно возрос в связи с развитием средств компьютерного моделирования и становлением таких дисциплин как комплексное планирование индустриальных программ, реалистичная анимация трехмерных сцен, роботизированная хирургия, навигация в динамическом окружении, автоматическая сборка продуктов, организация транспортных потоков в мегаполисах. Данная работа посвящена обзору и сравнительному анализу современных математических методов планирования движения.

Об авторах

К. А. Казаков
Институт системного программирования РАН
Россия


В. А. Семенов
Институт системного программирования РАН
Россия


Список литературы

1. Choset H., Lynch K., Seth H., Kantor G., Burgard W., Kavraki L.E., Thrun S. Principles of Robot Motion-Theory, Algorithms , and Implementation. MIT Press, 2005.

2. Geraerts R., Overmars M.H. Creating High-quality Paths for Motion Planning. Int. J. Rob. Res., vol. 26, № 8, 2007, pp. 845–863.

3. Karaman S., Frazzoli E. Sampling-based algorithms for optimal motion planning. Int. J. Robot., vol. 30, № 7, 2011, pp. 846–894

4. Laumond J.-P. Kineo CAM: A success story of motion planning algorithms. IEEE Robot. Autom. Mag., vol. 13, № 2, 2006, pp. 90–93.

5. Rockel S., Klimentjew D., Zhang L., Zhang J. An hyperreality imagination based reasoning and evaluation system (HIRES). Proc. IEEE Int. Conf. on Robotics and Automation, 2014. pp. 5705–5711.

6. Sucan I., Moll M., Kavraki L.E. The Open Motion Planning Library. IEEE Robot. Autom. Mag. vol. 19, № 4, 2012, pp. 72–82.

7. Diankov R. Automated Construction of Robotic Manipulation Programs. PhD thesis, Carnegie Mellon University, Robotics Institute, August 2010, 263 p.

8. Porta J.M., Ros L., Bohigas O., Manubens M., Rosales C., Jaillet L. The CUIK Suite: Motion Analysis of Closed-chin Multibody Systems. IEEE Robot. Autom. Mag., vol. 21, № 3, 2014, pp. 105–114.

9. Semenov V.A., Kazakov K.A., Zolotov V.A. Effective spatial reasoning in complex 4D modeling environments. eWork Ebus. Archit. Eng. Constr. eds. A.Mahdavi, B. Martens, R. Scherer, CRC Press. Taylor Fr. Group, London, UK. 2015, pp. 181–186.

10. Kazakov K.A., Semenov V.A., Zolotov V.A. Topological Mapping Complex 3D Environments Using Occupancy Octrees. 21st Int. Conf. Comput. Graph. Vision, Sept. 26-30, 2011, Moscow, Russ. 2011, pp. 111–114.

11. Semenov V.A., Kazakov K.A., Morozov S. V., Tarlapan O.A., Zolotov V.A., Dengenis T. 4D modeling of large industrial projects using spatio-temporal decomposition. eWork Ebus. Archit. Eng. Constr. eds. K. Menzel R. Scherer, CRC Press. Taylor Fr. Group,London, UK. 2010, pp. 89–95.

12. Brooks R.A., Lozano-Peres T. A Subdivision Algorithm in Configuration Space For Find Path with Rotation. IEEE Trans. Syst. Man. Cybern., vol. SMC-15, № 2, 1985, pp. 224–233.

13. D. Zhu and J.-C. Latombe. Constraint reformulation in a hierarchical path planner. In Proc. IEEE Int. Conf. on Robotics and Automation, 1990, pp. 1918-1923.

14. Hornung A., Wurm K.M., Bennewitz M., Stachniss C., Burgard W. OctoMap: An efficient probabilistic 3D mapping framework based on octrees. Auton. Robots., vol. 34, № 3, 2013, pp. 189–206.

15. Semenov V.A., Kazakov K.A., Zolotov V.A. Global path planning in 4D environments using topological mapping. eWork Ebus. Archit. Eng. Constr. 2012, pp. 263–269.

16. Chen D.Z., Szczerba R.J., Uhran Jr J.J. Using Framed-Quadtrees to Find Conditional Shortest Paths in an Unknown 2-D Environment. Technical Report #95-2, Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, Indiana, Jan. 1995, 33 p.

17. Chazelle B. Approximation and Decomposition of Shapes. Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics, 1987, pp. 145–185.

18. De Berg M., Cheong O., Van Kreveld M., Overmars M. Computational Geometry: Algorithms and Applications. 3rd Edition. Springer-Verlag, 2008, 386 p.

19. LaValle S.M. Planning Algorithms. Cambridge University Press, 2006, 844 p.

20. Canny J.F., Lin M.C. An opportunistic global path planner. Algorithmica, vol. 10, № 2-4, 1993, pp. 102–120.

21. Huang H.-P.H.H.-P., Chung S.-Y.C.S.-Y. Dynamic visibility graph for path planning. Proc. Int. Conf. Intell. Robot. Syst., vol. 3, 2004, pp. 2813–2818.

22. Kaluder H., Brezak M., Petrovic I. A visibility graph based method for path planning in dynamic environments. MIPRO, 2011, Proceedings of the 34th International Convention, Opatija, Croatia, 2011, pp. 717–721.

23. Aurenhammer F. Voronoi Diagrams – A Survey of a Fundamental Data Structure. ACM Comput. Surv., vol. 23, № 3, 1991, pp. 345–405.

24. Choset H. Sensor based motion planning: The hierarchical generalized voronoi graph. Ph.D. Thesis, California Institute of Technology, 1996, 201 p.

25. Russell S.J., Norvig P. Artificial Intelligence: A Modern Approach. Neurocomputing, vol. 9, № 2, 1995, pp. 215-218.

26. Bell S., An Overview of Optimal Graph Search Algorithms for Robot Path Planning in Dynamic or Uncertain Environments. Oklahoma Christian University, 2010, 9 p.

27. De Filippis L., Guglieri G. Advanced graph search algorithms for path planning of flight vehicles. Recent Adv. Aircr. Technol., 2012, pp. 159–192.

28. Zeng W., Church R.L. Finding shortest paths on real road networks: the case for A*. Int. J. Geogr. Inf. Sci., vol. 23, № 4, 2009, pp. 531–543.

29. Korf R.E. Depth-first iterative-deepening. An optimal admissible tree search. Artif. Intell., vol. 27, № 1, 1985, pp. 97–109.

30. Zhou R., Hansen E.A. Memory-Bounded {A*} Graph Search. The Florida AI Research Society Conference - FLAIRS, 2002, pp. 203–209.

31. Holte R., Perez M., Zimmer R., MacDonald A. Hierarchical A*: Searching abstraction hierarchies efficiently. Proceeding AAAI'96 Proceedings of the thirteenth national conference on Artificial intelligence – Volume 1, 1996, pp. 530–535.

32. Botea A., Muller M., Schaeffer J. Near optimal hierarchical path-finding. Journal of Game Development, vol. 1, issue 1, 2004, pp. 7-28.

33. Kring A., Champandard A., Samarin N. DHPA* and SHPA*: Efficient Hierarchical Pathfinding in Dynamic and Static Game Worlds. Proc. Sixth Artificial Intelligence and Interactive Digital Entertainment Conference, 2010, pp. 39–44.

34. Harabor D., Grastien A. Online Graph Pruning for Pathfinding On Grid Maps. AAAI Conf. Artif. Intell., 2011, pp. 1114–1119.

35. Koenig S., Likhachev M., Furcy D. Lifelong Planning A*. Artif. Intell., vol. 155, № 1-2, 2004, pp. 93–146.

36. Stentz A. The Focussed D* Algorithm for Real-Time Replanning. Proceeding IJCAI'95 Proceedings of the 14th international joint conference on Artificial intelligence - Volume 2, 1995, pp. 1652-1659.

37. Koenig S., Likhachev M. D* Lite. Proceedings of the AAAI Conference of Artificial Intelligence (AAAI), 2002, pp. 476–483.

38. Koenig S., Likhachev M. Fast Replanning for Navigation in Unknown Terrain. IEEE Trans. Robot., vol. 21, issue 3, 2005, pp. 354-363..

39. Khatib O. Real time obstacle avoidance for manipulators and mobile robots. International Journal of Robotics and Research, vol. 5, № 1, 1986, pp. 90–98.

40. Barraquand J., Latombe J.C. A Monte-Carlo algorithm for path planning with many degrees of freedom. Proceedings 1990 IEEE International Conference on Robotics and Automation, vol.3, 1990, pp. 1712–1717.

41. Barraquand J., Latombe J.C. Robot motion planning: A distributed representation approach. International Journal of Robotics Research, vol. 10, issue 6, 1991. pp. 628 - 649

42. Kavraki L.E., Svestka P., Latombe J.C., Overmars M.H. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom., vol. 12, № 4, 1996, pp. 566–580.

43. Hsu D., Latombe J.C., Motwani R. Path Planning in Expansive Configuration Spaces. Proceedings 1997 IEEE International Conference on Robotics and Automation, vol. 3, 1997, pp. 2719–2726.

44. LaValle S.M., Kuffner J.J. Rapidly-exploring random trees: Progress and prospects. 2000 Workshop on the Algorithmic Foundations of Robotics, 2000, pp. 293–308.

45. Ferre E., Laumond J.-P. An iterative diffusion algorithm for part disassembly. Proceedings 2004 IEEE International Conference on Robotics and Automation, vol. 3, 2004, pp. 3149–3154.

46. Bayazit O.B., Lien J.-M., Amato N.M. Probabilistic Roadmap Motion Planning for Deformable Objects. Proceedings 2002 IEEE International Conference on Robotics and Automation, vol. 2, 2002, pp. 2126–2133.

47. Guibas L.J., Holleman C., Kavraki L.E. A Probabilistic Roadmap Planner for Flexible Objects with aWorkspace Medial-Axis-Based Sampling Approach. IEEE/RSJ Int. Conf. Intelligent Robot. Syst., 1999, pp. 254–260.

48. Berenson D., Srinivasa S., Kuffner J.J. Task Space Regions: A framework for pose-constrained manipulation planning. Int. J. Rob. Res., vol. 30, № 12, 2011, pp. 1435–1460.

49. Yakey J.H., LaValle S.M., Kavraki L.E. Randomized path planning for linkages with closed kinematic chains. IEEE Trans. Robot. Autom., vol. 17, № 6, 2001, pp. 951–958.

50. LaValle S.M., Kuffner J.J. Randomized Kinodynamic Planning. Int. J. Rob. Res., vol. 20, № 5, 2001, pp. 378–400.

51. Niederreiter H. Random number generation and Quasi-Monte Carlo methods. Society for Industrial and Applied Mathematics, 1992, 241 p.

52. Дмитриев К.А. От Монте-Карло к Квази Монте-Карло. Труды 12-ой международной конференции по компьютерной графике и машинному зрению ГрафиКон'2002, 2002, стр. 53-58

53. Соболь И.М. Многомерные квадратурные формулы и функции Хаара. М.: Главная редакция физико-математической литературы изд-ва «Наука», 1969, 288 стр.

54. Соболь И. М. Численные методы Монте-Карло. М.: Главная редакция физико-математической литературы изд-ва «Наука», 1973, 312 стр.

55. Khaksar W., Hong T.S., Khaksar M., Motlagh O. A low dispersion probabilistic roadmaps (LD-PRM) algorithm for fast and efficient sampling-based motion planning. Int. J. Adv. Robot. Syst.vol. 10, № 397, 2013, pp. 1-10.

56. LaValle S.M., Branicky M.S. On the Relationship Between Classical Grid Search and Probabilistic Roadmaps. In Algorithmic Foundations of Robotics V. Springer Tracts in Advanced Robotics, vol. 7, 2004, pp. 59-75

57. Zhang L., Kim Y.J., Manocha D. C-DIST: efficient distance computation for rigid and articulated models in configuration space. Proc. 2007 ACM Symp. Solid Phys. Model. - SPM ’07, 2007, pp. 159-169.

58. Lin M.C. Efficient Collision Detection for Animation and Robotics. Ph.D. thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley, USA, 1993, 159 p.

59. Christer Ericson. Real-time Collision Detection. The Morgan Kaufmann Series in Interactive 3-D Technology. CRC Press, 2004, 632 p.

60. Andersen K. A., Bay C. A survey of algorithms for construction of optimal Heterogeneous Bounding Volume Hierarchies. Technical Report. Copenhague, Denmark: Department of Computer Science, University of Copenhagen, 2006, 32 p.

61. Золотов В.А., Семенов В.А. Современные методы поиска и индексации многомерных данных в приложениях моделирования больших динамических сцен. Труды ИСП РАН, том 24, 2013, стр. 381-416. DOI: 10.15514/ISPRAS-2013-24-17.

62. Золотов В.А., Семенов В.А. Перспективные схемы пространственно-временной индексации для визуального моделирования масштабных индустриальных проектов. Труды ИСП РАН, том 26, вып. 2, 2014, стр. 197-230. DOI: 10.15514/ISPRAS-2014-26(2)-9.

63. Золотов В.А., Петрищев К.С., Семенов В.А. Исследование методов пространственного индексирования динамических сцен на основе регулярных октодеревьев. Труды 25-й международной конференции GraphiCon2015, 2015, pp. 115-122.

64. Pungotra H. Collision Detection and Merging of Deformable B-spline Surfaces in Virtual Reality Environment. Ph. D. thesis, The Univeristy of Western Ontario, Canada, 2010, 180 p.

65. Sandqvist J., Collision detection using boundary representation, BREP. Master thesis, Umeå University, Sweden, 2015, 54 p.

66. Su C.J., Lin F., Ye L. New collision detection method for CSG-represented objects in virtual manufacturing. Computers in Industry, vol. 40, № 1, 1999, pp. 1–13.

67. Klein J., Zachmann G. Point cloud collision detection. Proc. Eurographics 2004, 2004, pp. 567–576.

68. Schwarzer F., Saha M., Latombe J.C. Exact Collision Checking of Robot Paths. In Algorithmic Foundations of Robotics V. Springer Tracts in Advanced Robotics, vol. 7, 2004, pp. 25–41.

69. Yershova A., LaValle S.M. Improving Motion Planning Alorithms by Efficient Nearest-Neighbor Searching. IEEE Transactions on Robotics, vol. 23, issue 1, 2007, pp. 151–157.

70. Yershova A., LaValle S.M. Planning for closed chains without inverse kinematics. Department of Computer Science, University of Illinois, Urbana, USA, 2007, 7 p. Available at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.7831&rep=rep1&type=pdf.

71. Brown R.A. Building a Balanced k-d Tree in O ( kn log n ) Time. J. Comput. Graph. Tech, vol. 4, № 1, 2015, pp. 50–68.

72. Ciaccia P., Patella M., Rabitti F., Zezula P. Indexing Metric Spaces with M-Tree. Proc. Atti del Quinto Convegno Nazionale SEBD, 1997, pp. 67–86.

73. Gipson B., Moll M., Kavraki L.E. Resolution Independent Density Estimation for motion planning in high-dimensional spaces. Proc. 2003 IEEE International Conference on Robotics and Automation, 2013, pp. 2437–2443.

74. Fredriksson K. Geometric Near-neighbor Access Tree (GNAT) revisited. arXiv:1605.05944v2, 2016, 7 p.

75. Yu C., Ooi B.C., Tan K.-L. Indexing the Distance: An Efficient Method to KNN Processing. Proceedings of the 27th International Conference on Very Large Data Bases, 2001, pp. 421-430.

76. Beygelzimer A., Kakade S., Langford J. Cover trees for nearest neighbor. ICML ’06, Proc. 23rd Int. Conf. Mach. Learn., 2006, pp. 97–104.

77. Ichnowski J., Alterovitz R. Fast Nearest Neighbor Search in SE (3) for Sampling-Based Motion Planning. Algorithmic Foundations of Robotics XI, Volume 107 of the series Springer Tracts in Advanced Robotics, 2015, pp 197-214.

78. Amato N.M., Bayazit O.B., Dale L.K., Jones C., Vallejo D. Choosing good distance metrics and local planners for probabilistic roadmap methods. IEEE Trans. Robot. Autom., vol. 16, № 4, 2000, pp. 442–447.

79. Nissoux C., Simeon T., Laumond J.-P. Visibility based probabilistic roadmaps. 1999 IEEE/RSJ Int. Conf. Intell. Robot. Syst., vol. 3, 1999, pp. 1316–1321.

80. Amato N.M., Wu Y. A randomized roadmap method for path and manipulation planning. Proc. 1996 IEEE International Conference on Robotics and Automation, vol. 1, 1996, pp. 113–120.

81. Amato N.M., Bayazit O.B., Dale L.K., Jones C., Vallejo D. OBPRM: An Obstacle-Based PRM for 3D Workspaces. Proceeding WAFR '98 Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective, 1998, pp. 155–168.

82. Yeh H.Y., Thomas S., Eppstein D., Amato N.M. UOBPRM: A uniformly distributed obstacle-based PRM. IEEE Int. Conf. Intell. Robot. Syst., 2012, pp. 2655–2662.

83. Hsu D., Jiang T., Reif J., Sun Z. The bridge test for sampling narrow passages with probabilistic roadmap planners. Proc. 2003 IEEE International Conference on Robotics and Automation, vol. 3, 2003, pp. 4420–4426.

84. Boor V., Overmars M.H., Stappen a. F. Van Der. The Gaussian sampling strategy for probabilistic roadmap planners. Proc. 1999 IEEE International Conference on Robotics and Automation, vol 2, 1999, pp. 1018–1023.

85. Lien J.-M., Thomas S., Amato N.M. A general framework for sampling on the medial axis of the free space. Proc. 2003 IEEE International Conference on Robotics and Automation, vol. 3, 2003, pp. 4439–4444.

86. Wilmarth S. a., Amato N.M., Stiller P.F. MAPRM: a probabilistic roadmap planner with sampling on the medialnaxis of the free space. Proc. 1999 IEEE International Conference on Robotics and Automation, vol 2, 1999, pp. 1024–1031.

87. Holleman C., Kavraki L.E. A framework for using the workspace medial axis in PRM planners. Proc. 2000 IEEE International Conference on Robotics and Automation, vol 2, 2000, pp. 1408–1413.

88. Nielsen C.L.L., Kavraki L.E. A two level fuzzy PRM for manipulation planning. 2000 IEEE/RSJ Int. Conf. Intell. Robot. Syst., vol. 3, 2000, pp. 1716–1721.

89. Bohlin R., Kavraki L.E. Path planning using lazy PRM. Proc. 2000 ICRA Millenn. Proc. 2000 IEEE International Conference on Robotics and Automation, vol 1, 2000, pp. 521–528.

90. Bohlin R., Kavraki L.E. A Randomized Approach to Robot Path Planning Based on Lazy Evaluation. In Handbook of Randomized Computing, volume I/II, Springer, 2001, pp. 221–253.

91. Leven P., Seth H. Toward Real-Time Path Planning in Changing Environments. Proceedings of the Fourth International Workshop on the Algorithmic Foundations of Robotics, 2000, pp. 363-376.

92. Nieuwenhuisen D., Van Den Berg J., Overmars M.H. Efficient path planning in changing environments. 2007 IEEE/RSJ Int. Conf. Intell. Robot. Syst., 2007, pp. 3295–3301.

93. Jaillet L., Simeon T. A PRM-based motion planner for dynamically changing environments. 2004 IEEE/RSJ Int. Conf. Intell. Robot. Syst., vol. 2, 2004, pp. 1606–1611.

94. Bessiere P., Ahuactzin J.M., Talbi E.-G., Mazer E. The Ariadne’s Clew Algorithm: Global Planning With Local Methods. Proceeding of the Workshop on Algorithmic Foundations of Robotics, 1995, pp. 39-49.

95. Mazer E., Ahuactzin J.M., Bessiere P. The Ariadne ’ s Clew Algorithm. Journal of Artifical Intelligence Research, vol. 9, 1998, pp. 295–316.

96. Carpin S., Pillonetto G. Motion planning using adaptive random walks. IEEE Trans. Robot., vol. 21, № 1, 2005, pp. 543–548.

97. Carpin S., Pillonetto G. Merging the adaptive random walks planner with the randomized potential field planner. Proc. Fifth Int. Work. Robot Motion Control, 2005, pp. 151–156.

98. Sanchez G., Latombe J.C. A single-query bi-directional probabilistic roadmap planner with lazy collision checking. In Robotics Research, Volume 6 of the series Springer Tracts in Advanced Robotics, Springer, 2003, pp 403-417.

99. Hsu D. Randomized Single-query Motion Planning in Expansive Spaces. Ph. D. thesis, Stanford University, USA, 2000, 118 p.

100. Sagan H. Space-Filling Curves. Springer-Verlag, New York, 1994, 193 p.

101. Kuffner J.J., LaValle S.M. RRT-connect: An efficient approach to single-query path planning. Proc. 2000 IEEE International Conference on Robotics and Automation, vol 2, 2000, pp. 995–1001.

102. Bekris K.E., Chen B.Y., Ladd A.M., Plaku E., Kavraki L.E. Multiple Query Motion Planning using Single Query Primitives. IEEE/RSJ Int. Conf. Intell. Robot. Syst., 2003, pp. 656–661.

103. Plaku E., Kavraki L.E. Distributed Sampling-Based Roadmap of Trees for Large-Scale Motion Planning. Proc. 2005 IEEE International Conference on Robotics and Automation, 2005, pp. 3879–3884.

104. Strandberg M. Robot Path Planning : An Object-Oriented Approach. Ph.D.thesis, Automatic and Control Departmentof, Signals, Sensors and Systems Royal Institute of Technology (KTH), Stockholm, Sweden, 2004, 244 p.

105. Bruce J.R., Veloso M. Real-time multi-robot motion planning with safe dynamics. Multi-Robot Systems. From Swarms to Intelligent Automata, Volume III. Proceedings from the 2005 International Workshop on Multi-Robot Systems, Springer, 2005, pp. 1–12.

106. Bruce J.R. Real-time motion planning and safe navigation in dynamic multi-robot environments. PhD. Thesis, Carnegie Mellon University, Pittsburgh, USA, 2006, 204 p.

107. Yershova A., Jaillet L., Siméon T., LaValle S.M. Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain. Proc. 2005 IEEE International Conference on Robotics and Automation, 2005, pp. 3856–3861.

108. Raveh B., Enosh A., Halperin D. A little more, a lot better: Improving path quality by a path-merging algorithm. IEEE Trans. Robot., vol. 27, № 2, 2011, pp. 365–371.

109. Urmson C., Simmons R. Approaches for heuristically biasing RRT growth. Proc. 2003 IEEE/RSJ Int. Conf. Intell. Robot. Syst., vol.2, 2003, pp. 1178–1183.

110. Jaillet L., Cortes J., Simeon T. Sampling-Based Path Planning on Costmaps Configuration-space. Ieee Trans. Robot., vol. 26, № 4, 2010, pp. 635–646.

111. Hauser K. Lazy collision checking in asymptotically-optimal motion planning. Proc. 2015 IEEE International Conference on Robotics and Automation, 2015, pp. 2951–2957.

112. Luo J., Hauser K. An Empirical Study of Optimal Motion Planning. IEEE/RSJ Conf. Intell. Robot. Syst., 2014, pp. 1761–1768.

113. Marble J.D., Bekris K.E. Asymptotically Near-Optimal is Good Enough for Motion Planning. 15th Int. Symp. Robot. Res., 2011, pp. 419-436.

114. Marble J.D., Bekris K.E. Computing spanners of asymptotically optimal probabilistic roadmaps. IEEE/RSJ Int. Conf. Intell. Robot. Syst., 2011, pp. 4292–4298.

115. Marble J.D., Bekris K.E. Towards small asymptotically near-optimal roadmaps. Proc. 2012 IEEE International Conference on Robotics and Automation, 2012, pp. 2557–2562.

116. Dobson A., Bekris K.E. Improving Sparse Roadmap Spanners. Proc. 2013 IEEE International Conference on Robotics and Automation, 2013, pp. 4106–4111.

117. Dobson A., Bekris K.E. Sparse roadmap spanners for asymptotically near-optimal motion planning. Int. J. Rob. Res., vol. 33, № 1, 2014, pp. 18–47.

118. Nasir J., Islam F., Malik U., Ayaz Y., Hasan O., Khan M., Muhammad M.S. RRT*-SMART: A rapid convergence implementation of RRT*. Int. J. Adv. Robot. Syst., vol. 10, 2013, pp. 1-12.

119. Arslan O., Tsiotras P. Use of relaxation methods in sampling-based algorithms for optimal motion planning. Proc. 2013 IEEE International Conference on Robotics and Automation, 2013, pp. 2421–2428.

120. Janson L., Pavone M. Fast Marching Trees : a Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions – Extended Version, arXiv:1306.3532v4, 2013, pp. 1–60.

121. Salzman O., Halperin D. Asymptotically near-optimal RRT for fast, high-quality, motion planning. Proc. 2014 IEEE International Conference on Robotics and Automation, 2014, pp. 4680–4685.

122. Devaurs D., Simeon T., Cortes J. Optimal Path Planning in Complex Cost Spaces with Sampling-Based Algorithms. IEEE Trans. Autom. Sci. Eng., vol. 13, № 2, 2016, pp. 415–424.

123. Klemm S., Oberlander J., Hermann A., Roennau A., Schamm T., Zollner J.M., Dillmann R. RRT∗-Connect: Faster, asymptotically optimal motion planning. 2015 IEEE Int. Conf. Robot. Biomimetics, 2015, pp. 1670–1677.

124. Starek J.A., Gomez J. V, Schmerling E., Janson L., Moreno Luis, Pavone M. An Asymptotically-Optimal Sampling-Based Algorithm for Bi-directional Motion Planning. IEEE/RSJ Int. Conf. Intell. Robot. Syst., 2015, pp. 2072 – 2078.


Рецензия

Для цитирования:


Казаков К.А., Семенов В.А. Обзор современных методов планирования движения. Труды Института системного программирования РАН. 2016;28(4):241-294. https://doi.org/10.15514/ISPRAS-2016-28(4)-14

For citation:


Kazakov K.A., Semenov V.A. An overview of modern methods for motion planning. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2016;28(4):241-294. (In Russ.) https://doi.org/10.15514/ISPRAS-2016-28(4)-14



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)