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

Главная

Статья в Elpub

РУС ENG

Математика и математическое моделирование. 2018; : 15-58

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

Лю В.

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

Аннотация

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

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

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

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

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

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).

Mathematics and Mathematical Modeling. 2018; : 15-58

Path Planning Methods in an Environment with Obstacles (A Review)

Liu W.

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

Abstract

Planning the path is the most important task in the mobile robot navigation. This task involves basically three aspects. First, the planned path must run from a given starting point to a given endpoint. Secondly, it should ensure robot’s collision-free movement. Thirdly, among all the possible paths that meet the first two requirements it must be, in a certain sense, optimal.

Methods of path planning can be classified according to different characteristics. In the context of using intelligent technologies, they can be divided into traditional methods and heuristic ones. By the nature of the environment, it is possible to divide planning methods into planning methods in a static environment and in a dynamic one (it should be noted, however, that a static environment is rare). Methods can also be divided according to the completeness of information about the environment, namely methods with complete information (in this case the issue is a global path planning) and methods with incomplete information (usually, this refers to the situational awareness in the immediate vicinity of the robot, in this case it is a local path planning). Note that incomplete information about the environment can be a consequence of the changing environment, i.e. in a dynamic environment, there is, usually, a local path planning.

Literature offers a great deal of methods for path planning where various heuristic techniques are used, which, as a rule, result from the denotative meaning of the problem being solved. This review discusses the main approaches to the problem solution. Here we can distinguish five classes of basic methods: graph-based methods, methods based on cell decomposition, use of potential fields, optimization methods, фтв methods based on intelligent technologies.

Many methods of path planning, as a result, give a chain of reference points (waypoints) connecting the beginning and end of the path. This should be seen as an intermediate result. The problem to route the reference points along the constructed chain arises. It is called the task of smoothing the path, and the review addresses this problem as well.

References

2. Murav'inyi algoritm. Vikipediya: Web-sait. Rezhim dostupa: https://ru.wikipedia.org/wiki/Murav'inyi_algoritm (data obrashcheniya 05.12.2017).

4. Iskusstvennaya neironnaya set'. Vikipediya: Web-sait. Rezhim dostupa: https://ru.wikipedia.org/wiki/Iskusstvennaya_neironnaya_set' (data obrashcheniya 05.12.2017).