priborИзвестия высших учебных заведений. ПриборостроениеJournal of Instrument Engineering0021-34542500-0381Национальный исследовательский университет ИТМО10.17586/0021-3454-2022-65-3-185-193pribor-230Research ArticleКОМПЬЮТЕРНОЕ ЗРЕНИЕ И ПЛАНИРОВАНИЕ ДВИЖЕНИЯ РОБОТОВ В ЗАДАЧАХ МАНИПУЛИРОВАНИЯCOMPUTER VISION AND ROBOT MOVEMENT PLANNING IN MANIPULATION TASKSАлгоритм модифицированного интеллектуального двунаправленного случайного дерева для планирования движения антропоморфных манипуляторовModified intelligent bidirectional random tree algorithm for planning the movement of anthropomorphic manipulatorsДовгополикИ. С.DovgopolikI. S.

Довгополик Илья Сергеевич — магистр; факультет систем управления и робототехники, лаборатория биомехатроники и энергоэффективной робототехники; инженер.

Санкт-Петербург

Ilya S. Dovgopolik — MSc; ITMO University, Faculty of Control Systems and Robotics, International Laboratory of Biomechatronics and Energy-Efficient Robotics; Engineer.

St. Petersburg

isdovgopolik@itmo.ruАртемовК.ArtemovK.

Артемов Кирилл — аспирант; факультет систем управления и робототехники, лаборатория биомехатроники и энергоэффективной робототехники; инженер-исследователь.

Санкт-Петербург

Kirill Artemov — Post-Graduate Student; ITMO University, Faculty of Control Systems and Robotics, International Laboratory of Biomechatronics and Energy-Efficient Robotics; Engineer-Researcher.

St. Petersburg

kaartemov@itmo.ruБорисовО. И.BorisovO. I.

Борисов Олег Игоревич — канд. техн. наук; факультет систем управления и робототехники, лаборатория биомехатроники и энергоэффективной робототехники; доцент.

Санкт-Петербург

Oleg I. Borisov — PhD; ITMO University, Faculty of Control Systems and Robotics, International Laboratory of Biomechatronics and Energy-Efficient Robotics; Associate Professor.

St. Petersburg

borisov@itmo.ruЗабихифарС.ZabihifarS.

Забихифар СейедХассан — канд. техн. наук; лаборатория робототехники; инженер-разработчик.

Москва

Seyedhassan Zabihifar — PhD; Sberbank, Robotics Laboratory; Engineer-Designer.

Moscow

zabikhifar.s@sberbank.ruСемочкинА. Н.SemochkinA. N.

Семочкин Александр Николаевич — канд. физ.-мат. наук, доцент; лаборатория робототехники; гл. инженер-разработчик.

Москва

Aleksandr N. Semochkin — PhD, Associate Professor; Sberbank, Robotics Laboratory; Сhief Engineer-Designer.

Moscow

Semochkin.A.N@sberbank.ruУниверситет ИТМОITMO UniversityСбербанкSberbank202201122024653185193Copyright © Национальный исследовательский университет ИТМО, 20242024Национальный исследовательский университет ИТМОНациональный исследовательский университет ИТМОhttps://pribor.ifmo.ru/jour/about/submissions#copyrightNoticehttps://pribor.ifmo.ru/jour/article/view/230

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

An algorithm for planning the movement of a multi-link robotic system in an environment with obstacles is considered. The main requirements for this task are high performance and efficient memory usage during operation. An algorithm for path planning based on the method of a bidirectional fast-investigating random tree is presented. An approach is used which excludes addition of new vertices to the tree if their location in space can unambiguously conclude that it is inappropriate to use them in the path construction. This modification makes it possible to speed up movement planning and reduce the amount of memory needed to store the environment analysis data.

планирование путибыстроисследующие случайные деревьяисключение неиспользуемых вершинiCubpath planningrapidly-exploring random treesexclusion of unused verticesiCubReferencesЛю В. Методы планирования пути в среде с препятствиями (обзор) // Математика и математическое моделирование. 2018. № 1. С. 15—58. DOI: 10.24108/mathm.0118.0000098.Liu W. Mathematics and Mathematical Modelling, 2018, no. 01, pp. 15–58, DOI: 10.24108/mathm.0118.0000098.LaValle S. М. Rapidly-exploring random trees : A new tool for path planning // The Annual Research Report. Iowa State University, 1998. October.LaValle S. TR 98-11, Computer Science Dept., Iowa State University, October 1998.Karaman S., Frazzoli E. Sampling-based algorithms for optimal motion planning // Intern. Journal of Robotics Research. 2011. Vol. 30. P. 846—894.Karaman S. and Frazzoli E. The International Journal of Robotics Research, 2011, vol. 30, pp. 846–894.Левин Б. Р. Теоретические основы статической радиотехники. М.: Радио и связь, 1989. 656 с.Levin B.R. Teoreticheskiye osnovy staticheskoy radiotekhniki (Theoretical Foundations of Static Radio Engineering), Moscow, 1989, 656 р. (in Russ.)Jordan M., Perez A. Optimal bidirectional rapidly-exploring random trees // Tech. Rep. MITCSAIL-TR-2013-021. Massachusetts Institute of Technology, Cambridge, MA. 2013. August.Jordan M. and Perez A. Tech. Rep. MITCSAIL-TR-2013-021, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, August 2013.Qureshi A. H., Ayaz Y. Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments // ArXiv. 2015. Vol. abs/1703.08944.Qureshi A.H. and Ayaz Y. ArXiv, 2015, vol. abs/1703.08944.Tahir Z., Qureshi A. H., Ayaz Y., Nawaz R. Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments // Robotics Auton. Syst. 2018. Vol. 108. P. 13—27.Tahir Z., Qureshi A.H., Ayaz Y., and Nawaz R. Robotics Auton. Syst., 2018, vol. 108, pp. 13–27.Gammell J., Srinivasa S., Barfoot T. Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic // IEEE/RSJ Intern. Conf. on Intelligent Robots and Systems. 2014. P. 2997—3004.Gammell J., Srinivasa S., and Barfoot T. 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014, pp. 2997–3004.Burget F., Bennewitz M., Burgard W. Bi2RRT*: An efficient sampling-based path planning framework for task-constrained mobile manipulation // IEEE/RSJ Intern. Conf. on Intelligent Robots and Systems (IROS). 2016. P. 3714—3721.Burget F., Bennewitz M., and Burgard W. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2016, pp. 3714–3721.Kingston Z., Moll M., Kavraki L. Exploring implicit spaces for constrained sampling-based planning // Intern. Journal of Robotics Research. 2019. Vol. 38. P. 1151—1178.Kingston Z., Moll M., and Kavraki L. The International Journal of Robotics Research, 2019, vol. 38, pp. 1151–1178.Hauser K. Motion and Path Planning. Berlin, Heidelberg: Springer, 2020. P. 1—11.Hauser K. Motion and Path Planning, Berlin, Heidelberg, Springer, 2020, pp. 1–11.

The authors declare that there are no conflicts of interest present.