Preview

Математика и математическое моделирование

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

Методы планирования пути в среде с препятствиями (обзор)

https://doi.org/10.24108/mathm.0118.0000098

Полный текст:

Аннотация

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

Методы планирования пути можно классифицировать по разным признакам. В контексте использования интеллектуальных технологий их можно разделить на традиционные методы и эвристические методы. По характеру окружающей обстановки можно разделить методы планирования на методы планирования в статической окружающей среде и в динамической среде (следует, однако, отметить, что статическая окружающая среда редко встречается на практике). Методы также можно разделить по полноте информации об окружающей среде: методы с полной информацией (в таком случае говорят о глобальном планировании пути) и методы с неполной информацией (обычно речь идет о знании обстановки в непосредственной близости от робота, в этом случае речь идет о локальном планировании пути). Отметим, что неполная информация об окружающей среде может быть следствием меняющейся обстановки, т.е. в условиях динамической среды планирование пути, как правило, локальное.

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

Многие методы планирования пути в качестве результата дают цепь опорных точек (путевых точек), соединяющую начало и конец пути. Это следует рассматривать как промежуточный результат. Возникает задача прокладки пути вдоль построенной цепи опорных точек, называемая задачей сглаживания пути. Этой задаче в обзоре также уделено внимание.

Об авторе

В. Лю
МГТУ им. Н.Э. Баумана, Москва, Россия
Россия

Лю Вей

кафедра ФН-12



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

1. Meng Wang, Liu J.N.K. Fuzzy logic-based real-time robot navigation in unknown environment with dead ends // Robotics and Autonomous Systems. 2008. Vol. 56. No. 7. Pp. 625–643. DOI: 10.1016/j.robot.2007.10.002

2. Муравьиный алгоритм. Википедия: Web-сайт. Режим доступа: https://ru.wikipedia.org/wiki/Муравьиный_алгоритм (дата обращения 05.12.2017).

3. Mohamad M.M., Dunnigan M.W., Taylor N.K. Ant colony robot motion planning // EUROCON 2005: Intern. conf. on computer as a tool (Belgrade, Serbia, November 21-24, 2005): Proc. N.Y.: IEEE, 2005. Vol. 1. pp. 213–216. DOI: 10.1109/EURCON.2005.1629898

4. Искусственная нейронная сеть. Википедия: Web-сайт. Режим доступа: https://ru.wikipedia.org/wiki/Искусственная_нейронная_сеть (дата обращения 05.12.2017).

5. Janet J.A., Luo R.C., Kay M.G. The essential visibility graph: An approach to global motion planning for autonomous mobile robots // IEEE intern. conf. on robotics and automation (Nagoya, Japan, May 21-27, 1995): Proc. Vol. 2. N.Y.: IEEE, 1995. Pp. 1958–1963. DOI: 10.1109/ROBOT.1995.526023

6. Han-Pang Huang, Shu-Yun Chung. Dynamic visibility graph for path planning // IEEE-RSJ intern. conf. on intelligent robots and systems: IROS 2004 (Sendai, Japan, Sept. 28 - Oct. 2, 2004): Proc. N.Y.: IEEE, 2004. Vol. 3. Pp. 2813–2818. DOI: 10.1109/IROS.2004.1389835

7. Habib M.K., Asama H. Efficient method to generate collision free paths for an autonomous mobile robot based on new free space structuring approach // IEEE/RSJ intern. workshop on intelligent robots and systems: IROS'91 (Osaka, Japan, November 3-5, 1991): Proc. Vol. 2. N.Y.: IEEE, 1991. Pp. 563–567. DOI: 10.1109/IROS.1991.174534

8. Wallgrun J. O. Voronoi graph matching for robot localization and mapping // Transactions on computational science IX. B.: Springer, 2010. Pp. 76–108. DOI: 10.1007/978-3-642-16007-3_4

9. Amato N.M., Wu Y. A randomized roadmap method for path and manipulation planning // IEEE intern. conf. on robotics and automation (Minneapolis, USA, April 22-28, 1996): Proc. Vol. 1. N.Y.: IEEE, 1996. Pp. 113–120. DOI: 10.1109/ROBOT.1996.503582

10. Ladd A.M., Kavraki L.E. Measure theoretic analysis of probabilistic path planning // IEEE Trans. on Robotics and Automation. 2004. Vol. 20. No. 2. Pp. 229–242. DOI: 10.1109/TRA.2004.824649

11. Geraerts R., Overmars M.H. A comparative study of probabilistic roadmap planners // Algorithmic foundations of robotics B.: Springer, 2004. Pp. 43–57. DOI: 10.1007/978-3-540-45058-0_4

12. LaValle S.M. Planning algorithms. Camb.; N.Y.: Camb. Univ. Press, 2006. 826 p.

13. Yang K., Sukkarieh S. 3D smooth path planning for a UAV in cluttered natural environments // IEEE/RSJ intern. conf. on intelligent robots and systems: IROS 2008 (Nice, France, Sept. 22-26, 2008): Proc. N.Y.: IEEE, 2008. Pp. 794–800. DOI: 10.1109/IROS.2008.4650637

14. Kuffner J.J., LaValle S.M. RRT-connect: An efficient approach to to single-query path planning // IEEE intern. conf. on robotics and automation: ICRA’2000 (San Francisco, CA, USA, April 24-28, 2000): Proc. N.Y.: IEEE, 2000. Vol. 2. Pp. 995–1001. DOI: 10.1109/ROBOT.2000.844730

15. Sleumer N.H., Tschichold-Gurman N. Exact cell decomposition of arrangements used for path planning in robotics. Zurich: Inst. of Theoretical Computer Science, 1999. DOI: 10.3929/ethz-a-006653440

16. Elfes A. Using occupancy grids for mobile robot perception and navigation // Computer. 1989. Vol. 22. No. 6. Pp. 46–57. DOI: 10.1109/2.30720

17. Yahja A., Stentz A., Singh S., Brumitt B.L. Framed-quadtree path planning for mobile robots operating in sparse environments // IEEE intern. conf. on robotics and automation (Leuven, Belgium, May 20, 1998): Proc. N.Y.: IEEE, 1998. Vol. 1. Pp. 650–655. DOI: 10.1109/ROBOT.1998.677046

18. Kitamura Y., Tanaka T., Kishino F., Yachida M. 3-D path planning in a dynamic environment using an octree and an artificial potential field // IEEE-RSJ intern. conf. on intelligent robots and systems: IROS’95 (Pittsburgh, PA, USA, Aug. 5-9, 1995): Proc. N.Y.: IEEE, 1995. Vol. 2. Pp. 474–481. DOI: 10.1109/IROS.1995.526259

19. Redding J., Amin J., Boskovic J., Kang Y., Hedrick K., Howlett J., Poll S. A real-time obstacle detection and reactive path planning system for autonomous small-scale helicopters // AIAA Guidance, navigation and control conf. and exhibit (Hilton Head, USA, Aug. 20–23, 2007): Proc. Wash.: AIAA, 2007. Pp. 989–1010. DOI: 10.2514/6.2007-6413

20. Chazelle B., Palios L. Triangulating a nonconvex polytope // Discrete and Computational Geometry. 1990. Vol. 5. No. 5. Pp. 505–526. DOI: 10.1007/BF02187807

21. Russell S.J., Norvig P. Artificial intelligence: A modern approach. 3rd ed. Upper Saddle River: Prentice Hall, 2010. 1132 pp.

22. Ferguson D., Stentz A. Using interpolation to improve path planning: The field D* algorithm // J. of Field Robotics. 2006. Vol. 23. No. 2. Pp. 79–101. DOI: 10.1002/rob.20109

23. Daniel K., Nash A., Koenig S., Felner A. Theta*: Any-angle path planning on grids // J. of Artificial Intelligence Research. 2010. Vol. 39. Pp. 533–579. DOI: 10.1613/jair.2994

24. Stentz A. Optimal and efficient path planning for unknown and dynamic environments. Pittsburgh: The Robotics Inst.; Carnegie Mellon Univ., 1993. 38 p.

25. Stentz A. The focussed D* algorithm for real-time replanning // 14th intern. joint conf. on artificial intelligence: IJCAI’95 (Montreal, Canada, Aug. 20-25, 1995): Proc. Vol. 2. San Francisco: Morgan Kaufmann Publ., 1995. Pp. 1652–1659.

26. Koenig S., Likhachev M., Furcy D. Lifelong planning A* // Artificial Intelligence. 2004. Vol. 155. No. 1-¬2. Pp. 93–146. DOI: 10.1016/j.artint.2003.12.001

27. Koenig S., Likhachev M. D* lite // 18th national conf. on artificial intelligence (Edmonton, Alberta, Canada, July 28–August 1, 2002): Proc. Menlo Park: AAAI Press, 2002. Pp. 476–483.

28. De Filippis L., Guglieri G., Quagliotti F. A minimum risk approach for path planning of UAVs // J. of Intelligent and Robotic Systems. 2011. Vol. 61. No. 1–4. Pp. 203-219. DOI: 10.1007/s10846-010-9493-9

29. De Filippis L., Guglieri G., Quagliotti F. Path planning strategies for UAVs in 3D environments // J. of Intelligent and Robotic Systems. 2012. Vol. 65. No.1–4. Pp. 247–264. DOI: 10.1007/s10846-011-9568-2

30. De Filippis L. Advanced path planning and collision avoidance algorithms for UAVs: Doct. diss. Torino: Ist. Politecnico di Torino, 2012. 142 p.

31. Alvarez D., Gomez J.V., Garrido S., Moreno L. 3D robot formations path planning with fast marching square // J. of Intelligent and Robotic Systems. 2015. Vol. 80. No. 3-4. Pp. 507–523. DOI: 10.1007/s10846-015-0187-1

32. Osher S., Sethian J.A. Fronts propagating with curvature-dependent speed:algorithms based on Hamilton-Jacobi formulations // J. of Computational Physics. 1988. Vol. 79. No. 1. Pp. 12–49. DOI: 10.1016/0021-9991(88)90002-2

33. Ge S.S., Cui Y.J. New potential functions for mobile robot path planning // IEEE Trans. on Robotics and Automation. 2000. Vol. 16. No. 5. Pp. 615–620. DOI: 10.1109/70.880813

34. Jing R., McIsaac K.A., Patel R.V. Modified Newton's method applied to potential field-based navigation for mobile robots // IEEE Trans. on Robotics. 2006. Vol. 22. No. 2. Pp. 384–391. DOI: 10.1109/TRO.2006.870668

35. Ferrara A., Rubagotti M. Second-order sliding-mode control of a mobile robot based on a harmonic potential field // IET Control Theory and Applications. 2008. Vol. 2. No. 9. Pp. 807–818. DOI: 10.1049/iet-cta:20070424

36. Khatib O. Real-time obstacle avoidance for manipulators and mobile robots // Intern. J. of Robotics Research. 1986. Vol. 5. No. 1. pp. 90–98. DOI: 10.1177/027836498600500106

37. Fujimura K., Samet H. A hierarchical strategy for path planning among moving obstacles (mobile robot) // IEEE Trans. on Robotics and Automation. 1989. Vol. 5. No. 1. Pp. 61–69. DOI: 10.1109/70.88018

38. Conn R.A., Kam M. Robot motion planning on N-dimensional star worlds among moving obstacles // IEEE Trans. on Robotics and Automation. 1998. Vol. 14. No. 2. Pp. 320–325. DOI: 10.1109/70.681250

39. Mabrouk M.H., McInnes C.R. Solving the potential field local minimum problem using internal agent states // Robotics and Autonomous Systems. 2008. Vol. 56. No. 12. Pp. 1050–1060. DOI: 10.1016/j.robot.2008.09.006

40. Zou Xi-yong, Zhu Jing. Virtual local target method for avoiding local minimum in potential field based robot navigation // J. of Zhejiang Univ. - Science A. 2003. Vol. 4. No. 3. Pp. 264–269. DOI: 10.1631/jzus.2003.0264

41. Masoud A.A. Solving the narrow corridor problem in potential field-guided autonomous robots // IEEE intern. conf. on robotics and automation: ICRA 2005 (Barcelona, Spain, April 18-22, 2005): Proc. N.Y.: IEEE, 2005. Pp. 2909–2914. DOI: 10.1109/ROBOT.2005.1570555

42. Fan Xiao-ping, Li Shuang-yan, Chen Te-fang. Dynamic obstacle-avoiding path plan for robots based on a new artificial potential field function // Control Theory and Applications. 2005. Vol. 22. No. 5. Pp. 703–707. Режим доступа: http://en.cnki.com.cn/Article_en/CJFDTOTAL-KZLY200505005.htm (дата обращения 05.12.2017).

43. Borenstein J., Koren Y. Real-time obstacle avoidance for fast mobile robots // IEEE Trans. on Systems, Man, and Cybernetics. 1989. Vol. 19. No. 5. Pp. 1179–1187. DOI: 10.1109/21.44033

44. Borenstein J., Koren Y. The vector field histogram-fast obstacle avoidance for mobile robots // IEEE Trans. on Robotics and Automation. 1991. Vol. 7. No. 3. Pp. 278–288. DOI: 10.1109/70.88137

45. Ulrich I., Borenstein J. VFH+: Reliable obstacle avoidance for fast mobile robots // IEEE intern. conf. on robotics and automation (Leuven, Belgium, May 20, 1998): Proc. N.Y.: IEEE, 1998. Vol. 2. Pp. 1572–1577. DOI: 10.1109/ROBOT.1998.677362

46. Ulrich I., Borenstein J. VFH*: Local obstacle avoidance with look-ahead verification // IEEE intern. conf. on robotics and automation: ICRA’00 (San Francisco, CA, USA, April 24-28, 2000): Proc. N.Y.: IEEE, 2000. Vol. 3. Pp. 2505–2511. DOI: 10.1109/ROBOT.2000.846405

47. Betts J.T. Survey of numerical methods for trajectory optimization // J. of Guidance, Control and Dynamics. 1998. Vol. 21. No. 2. Pp. 193–207. DOI: 10.2514/2.4231

48. Ross I.M., Fahroo F. A perspective on methods for trajectory optimization // AIAA/AAS Astrodynamics specialist conf. and exhibit (Monterey, CA, USA, August 5-8, 2002): Proc. Wash.: AIAA, 2002. Pp. 1–7. DOI: 10.2514/6.2002-4727

49. Fliess M., Levine J., Martin P., Rouchon P. Flatness and defect of non-linear systems: introductory theory and examples // Intern. J. of Control. 1995. Vol. 61. No. 6. Pp. 1327–1361. DOI: 10.1080/00207179508921959

50. Gill P.E., Murray W., Saunders M.A. User’s guide for SNOPT Version 7: software for large scale nonlinear programming. Stanford: Stanford Univ. Publ., 2006. 116 p.

51. Gill P.E., Murray W., Saunders M.A., Wright M.H. User’s guide for NPSOL (version 4.0): a Fortran package for nonlinear programming. Stanfod: Stanford Univ., 1986.

52. Culligan K., Valenti M., Kuwata Y., How J.P. Three-dimensional flight experiments using on-line mixed-integer linear programming trajectory optimization // Amer. control conf.: ACC’2007 (New York, NY, USA, July 9-13, 2007): Proc. N.Y.: IEEE, 2007. Pp. 5322–5327. DOI: 10.1109/ACC.2007.4283101

53. Schouwenaars T., De Moor B., Feron E., How J. Mixed integer programming for multi-vehicle path planning // Eur. control conf.: ECC 2001 (Porto, Portugal, Sept. 4-7, 2001): Proc. N.Y.: IEEE, 2001. Pp. 2603–2608.

54. Earl M.G., D’Andrea R. Iterative MILP methods for vehicle-control problems // IEEE Trans. on Robotics. 2005. Vol. 21. No. 6. Pp. 1158–1167. DOI: 10.1109/TRO.2005.853499

55. Kuwata Y. Real-time trajectory design for unmanned aerial vehicles using receding horizon control: Doct. diss. Camb., MA: Massachusetts Inst. of Technology, 2003. 151 p.

56. Habibi G., Masehian E., Beheshti M.T.H. Binary integer programming model of point robot path planning // 33rd annual conf. of the IEEE Industrial Electronics Soc.: IECON 2007 (Taipei, Taiwan, Nov. 5-8, 2007): Proc. N.Y.: IEEE, 2007. Pp. 2841–2845. DOI: 10.1109/IECON.2007.4460315

57. Masehian E., Habibi G. Robot path planning in 3D space using binary integer programming // Intern. J. of Computer, Information, Systems and Control Engineering. 2007. Vol. 1. No. 5. Pp. 1240-1245.

58. Masehian E., Habibi G. Motion planning and control of mobile robot using Linear Matrix Inequalities (LMIs) // IEEE/RSJ intern. conf. on intelligent robots and systems: IROS 2007 (San Diego, CA, USA, Oct. 29 - Nov. 2, 2007): Proc. N.Y. IEEE, 2007. Pp. 4277–4282. DOI: 10.1109/IROS.2007.4399641

59. Dorigo M., Birattari M., Stutzle T. Ant colony optimization // IEEE Computational Intelligence Magazine. 2006. Vol. 1. No. 4. Pp. 28–39. DOI: 10.1109/MCI.2006.329691

60. Mohamad M.M., Dunnigan M.W., Taylor N.K. Ant colony robot motion planning // Intern. conf. on “Computer as a tool”: EUROCON 2005 (Belgrade, Serbia, Nov. 21-24, 2005): Proc. N.Y.: IEEE, 2005. Vol. 1. Pp. 213–216. DOI: 10.1109/EURCON.2005.1629898

61. Гэн K.K., Тань Лиго, Чулин Н.А., Хэ Юн. Планирование маршрута для квадрокоптера в неизвестной среде на основе монокулярного компьютерного зрения // Автоматизация. Современные технологии. 2015. № 12. С. 14–19.

62. Мак-Каллок У.C., Питтс B. Логическое исчисление идей, относящихся к нервной активности // Автоматы: Сб. / Под ред. К.Э. Шеннона, Дж. МакКарти. М.: Изд-во иностр. лит., 1956. С. 363–384.

63. Glasius R., Komoda A., Stan C.A.M. Gielen. Neural network dynamics for path planning and obstacle avoidance // Neural Networks. 1995. Vol. 8. No. 1. Pp. 125–133. DOI: 10.1016/0893-6080(94)E0045-M

64. Moreno J.A., Castro M. Heuristic algorithm for robot path planning based on a growing elastic net // Progress in artificial intelligence: 12th Portuguese conf. on artificial intelligence: EPIA 2005 (Covilhã, Portugal, December 5-¬8, 2005): Proc. B.: Springer, 2005. Pp. 447-454. DOI: 10.1007/11595014_44

65. Fu X., Gao X., Chen D. A Bayesian optimization algorithm for UAV path planning // Intelligent information processing II: Intern. conf. on intelligent information processing: IIP 2004 (Beijing, China, Oct. 21-23, 2004): Proc. Boston: Springer, 2005. Pp. 227–232. DOI: 10.1007/0-387-23152-8_29

66. Eberhart R., Kennedy J. A new optimizer using particle swarm theory // 6th intern. symp. on micromachine and human science: MHS’95 (Nagoya, Japan, Oct. 4-6, 1995): Proc. N.Y.: IEEE, 1995. Pp. 39–43. DOI: 10.1109/MHS.1995.494215

67. Jung L.F., Knutzon J.S., Oliver J.H., Winer E.H. Three-dimensional path planning of unmanned aerial vehicles using particle swarm optimization // 11th AIAA/ISSMO multidisciplinary analysis and optimization conf. (Portsmouth, Virginia, USA, September 6–8, 2006): Proc. Wash.: AIAA, 2006. Pp. 992–1001. DOI: 10.2514/6.2006-6995

68. Huq R., Mann G.K.I., Gosine R.G. Mobile robot navigation using motor schema and fuzzy context dependent behavior modulation // Applied Soft Computing. 2008. Vol. 8. No. 1. Pp. 422–436. DOI: 10.1016/j.asoc.2007.02.006

69. Egerstedt M. Behavior based robotics using hybrid automata // Hybrid systems: Computation and control: 3rd intern. workshop on hybrid systems: HSCC 2000 (Pittsburgh, PA, USA, March 23-25, 2000): Proc. B.: Springer, 2000. Pp. 103–116. DOI: 10.1007/3-540-46430-1_12

70. Ma J.-C., Zhang Q., Ma L.-Y., Xie W. Multi-behavior fusion-based path planning for mobile robot // Beijing Ligong Daxue Xuebao / Trans. of Beijing Inst. of Technology. 2014. Vol. 34. No. 6. Pp. 576–581.

71. Motlagh O.R.E., Hong T.S., Ismail N. Development of a new minimum avoidance system for a behavior-based mobile robot // Fuzzy Sets and Systems. 2009. Vol. 160. No. 13. Pp. 1929–1946. DOI: 10.1016/j.fss.2008.09.015

72. Бекасов Д.Е. Применение аппарата нечеткой логики при решении задачи поиска пути в неизвестном окружении // Молодежный науч.-техн. вестник. МГТУ им. Н.Э. Баумана: электрон. журн. 2012. No. 5. С. 40.

73. Keke G., Wei L., Liguo T. A fuzzy controller: Using monocular computer vision to see and avoid obstacle for quadcopter // 5th intern. workshop on computer science and engineering: Information processing and control engineering: WCSE 2015-IPSE (Moscow, Russia, April 15-17, 2015): Proc. Chenghu: Science and Engineering Inst., 2015.

74. Ng J., Braunl T. Performance comparison of bug navigation algorithms // J. of Intelligent and Robotic Systems. 2007. Vol. 50. No. 1. Pp. 73–84. DOI: 10.1007/s10846-007-9157-6

75. Lumelsky V., Stepanov A. Dynamic path planning for a mobile automaton with limited information on the environment // IEEE Trans. on Automatic Control. 1986. Vol. 31. No. 11. Pp. 1058–1063. DOI: 10.1109/TAC.1986.1104175

76. Yufka A., Parlaktuna O. Performance comparison of the BUG’s algorithms for mobile robots // Intern. symp. on INnovations in intelligent SYSTems and applications: INISTA 2009 (Trabzon, Turkey, June 29–July 1, 2009): Proc. N.Y.: IEEE, 2009. Pp. 416–421.

77. Shi C., Bu Y., Liu J. Mobile robot path planning in three-dimensional environment based on ACO-PSO hybrid algorithm // IEEE/ASME intern. conf. on advanced intelligent mechatronics: AIM 2008 (Xian, China, July 2-5, 2008): Proc. N.Y.: IEEE, 2008. Pp. 252–256. DOI: 10.1109/AIM.2008.4601668

78. Mettler B., Toupet O. Receding horizon trajectory planning with an environ-ment-based cost-to-go function // 44th IEEE conf. on decision and control and the European control conf.: CDC-ECC'05 (Seville, Spain, Dec. 15, 2005): Proc. N.Y.: IEEE, 2005. Pp. 4071–4076. DOI: 10.1109/CDC.2005.1582799

79. Gilimyanov R.F., Pesterev A.V., Rapoport L.B. Smoothing curvature of trajectories constructed by noisy measurements in path planning problems for wheeled robots // J. of Computer and Systems Sciences International. 2008. Vol. 47. No. 5. Pp. 812–819. DOI: 10.1134/S1064230708050158

80. Lutterkort D., Peters J. Smooth paths in a polygonal channel // 15th annual symp. on computational geometry: SCG'99 (Miami Beach, FLA, USA, June 13-16, 1999): Proc. N.Y.: ACM Press, 1999. Pp. 316–321. DOI: 10.1145/304893.304985

81. Jung D., Tsiotras P. On-line path generation for unmanned aerial vehicles using B-spline path templates // J. of Guidance, Control, and Dynamics. 2013. Vol. 36. No. 6. Pp. 1642–1653. DOI: 10.2514/1.60780

82. Zhao Y., Tsiotras P. A quadratic programming approach to path smoothing // Amer. control conf.: ACC 2011 (San Francisco, CA, USA, June 29 – July 1, 2011): Proc. N.Y.: IEEE, 2011. Pp. 5324–5329. DOI: 10.1109/ACC.2011.5990880

83. Гилимьянов Р.Ф., Рапопорт Л.Б. Метод деформации пути в задачах планирования движения роботов при наличии препятствий // Проблемы управления. 2012. № 1. С. 70–76.

84. Dubins L.E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents // Amer. J. of Mathematics. 1957. Vol. 79. No. 3. Pp. 497–516. DOI: 10.2307/2372560

85. Nelson W. Continuous-curvature paths for autonomous vehicles // IEEE intern. conf. on robotics and automation (Scottsdale, AZ, USA, May 14-19, 1989): Proc. N.Y.: IEEE, 1989. Vol. 3. Pp. 1260–1264. DOI: 10.1109/ROBOT.1989.100153

86. Van der Molen G.M. Trajectory generation for mobile robots with clothoids // Robotic systems: Advanced techniques and applications. Dordrecht: Springer, 1992. Pp. 399–406. DOI: 10.1007/978-94-011-2526-0_46

87. Walton D.J., Meek D.S., Ali J.M. Planar G2 transition curves composed of cubic Bézier spiral segments // J. of Computational and Applied Mathematics. 2003. Vol. 157. No. 2. Pp. 453–476. DOI: 10.1016/S0377-0427(03)00435-7

88. Komoriya K., Tanie K. Trajectory design and control of a wheel-type mobile robot using B-spline curve // IEEE/RSJ intern. workshop on intelligent robots and systems: IROS’89 (Tsukuba, Japan, Sept. 4-6, 1989): Proc. N.Y.: IEEE, 1989. Pp. 398–405. DOI: 10.1109/IROS.1989.637937

89. Berglund T., Jonsson H., Soderkvist I. An obstacle-avoiding minimum variation B-spline problem // Intern. conf. on geometric modeling and graphics (London, UK, July 16–18, 2003): Proc. N.Y.: IEEE, 2003. Pp. 156–161. DOI: 10.1109/GMAG.2003.1219681

90. Wang Z., Zhang W., Li G., Mu X. G2 path smoothing using non-uniform B-spline // Systems Engineering and E1ectronics. 2011. No. 7. Pp. 1539–1543. Режим доступа: http://en.cnki.com.cn/Article_en/CJFDTOTAL-XTYD201107021.htm (дата обращения 05.12.2017).


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


Лю В. Методы планирования пути в среде с препятствиями (обзор). Математика и математическое моделирование. 2018;(1):15-58. https://doi.org/10.24108/mathm.0118.0000098

For citation:


Liu W. Path Planning Methods in an Environment with Obstacles (A Review). Mathematics and Mathematical Modeling. 2018;(1):15-58. (In Russ.) https://doi.org/10.24108/mathm.0118.0000098

Просмотров: 375


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


ISSN 2412-5911 (Online)