ДОСЛІДЖЕННЯ МЕТОДУ ВИБОРУ НАЙКОРОТШОГО МАРШРУТУ ПРИ ПЕРЕМІЩЕННІ ОБ’ЄКТА У ПРИМІЩЕННІ

Автор(и)

  • Тетяна Олександрівна Левицька ДВНЗ «ПДТУ»
  • Едуард Володимирович Бєлан ДВНЗ «ПДТУ»

DOI:

https://doi.org/10.31498/2522-9990222020197883

Ключові слова:

пошук, граф, маршрут, алгоритм, шлях

Анотація

Дана робота присвячена дослідженню проблем побудови маршрутів переміщення автономних об’єктів (роботів) в приміщеннях. Розглянуті методи пошуку оптимальних маршрутів на графах, реалізовуються три алгоритми та порівнюються результати їх роботи. Алгоритми пошуку найкоротших шляхів поділяються на два типи: пошук шляху на дискретному робочому полі (лабіринті), пошук шляху на графі. Обидва класи алгоритмів мають свої переваги і недоліки, а так само свою вузьку сферу застосування. З розвитком робототехніки актуальним завданням є оптимальне переміщення автономного мобільного робота в приміщенні. Вважаємо, що приміщення складається з залів, які з'єднуються коридорами. У залах можуть перебувати перешкоди, які необхідно обходити. Зазначимо, що в кожному прохідному залі побудовані найкоротші внутрішні
маршрути, що з'єднують різні входи в приміщення. Дане завдання може вирішуватися за допомогою хвильового алгоритму або інших відомих алгоритмів, наприклад, методу графа видимості (visibility graphs) або методу декомпозиції на комірки (cell  decomposition). Дослідження полягало в порівнянні алгоритмів Дейкстри, А* і Contraction hierarchies для невеликого приміщення. Для порівняння роботи алгоритмів пошуку запускали процедури
пошуку на різних маршрутах. Причому маршрути в вибірці були як короткі так і довгі, оскільки реалізовані алгоритми по-різному показали себе на маршрутах різної довжини. В тестових випробуваннях найкращим виявився алгоритм Contraction hierarchies, незначною мірою йому уступив алгоритм А*, але беручи до уваги складність попередньої побудови графу приміщення, вважаємо найкращим алгоритм А*. Отримані результати можуть
бути використані при розробці системи вибору та візуалізації найкоротшого маршруту при переміщенні об’єкта у приміщенні, яка стане основою логіки роботи мобільного автономного пристрою – роботу, або ігрового об’єкту в комп’ютерній грі. Метою даної
статті є публікація результатів порівняльного аналізу алгоритмів пошуку найкоротшого  шляху (Дейкстри, А*, Contraction hierarchies) для відносно невеликого приміщення з безліччю перешкод.

Біографії авторів

Тетяна Олександрівна Левицька, ДВНЗ «ПДТУ»

к.т.н., доцент кафедри «Комп`ютерні науки»

Едуард Володимирович Бєлан, ДВНЗ «ПДТУ»

кафедри «Комп`ютерні науки»

Посилання

Рассел С. Искусственный интеллект: современный подход / С. Рассел, П. Норвиг. – М.: «Вильямс», 2007. – 1408 с.

Siegwart R. Introduction to Autonomous Mobile Robots / Siegwart R., Nourbakhsh I. R. Massachusetts: Bradford Book, 2004. 340 p.

LaValle S. M. Planning Algorithms. Cambridge. / LaValle S. M. U. K.: Cambridge

University Press, 2006. 1007 p.

Coenen S. A. M. Motion Planning for Mobile Robots: a Guide. / Coenen S. A. M.,

Steinbuch M., van de Molengraft M. J. G., Lunenburg J. J. M., Maus G. J. L. Eindhoven, Eindhoven

University of Technology. 2012. 79 p.

Parker L. E. Path Planning and Motion Coordination in Multiple Mobile Robot Teams.

/ Parker L. E. Encyclopedia of Complexity and System Science. R. A. Meyers (ed.). Springer

Verlag, 2009. P. 5783–5800. 6. Desaraju V. R. Decentralized Path Planning for Multi-Agent Teams with Complex

Constraints / Desaraju V. R., How J. P. // Autonomous Robots. January 2012. P. 1–19.

Alonso-Mora J. Collaborative Motion Planning for Multi Agent Systems. / Alonso-

Mora J. Eidgenossische Technische Hochschule ETH Zurich. No 21705. 2014. 176 p.

Кормен Т. Х. Алгоритмы: построение и анализ. / Кормен Т. Х., Лейзерсон Ч. И.,

Ривест Р. Л., Штайн К М.: Вильямс, 2013. 1328 с.

Rubin F. The Lee path connection algorithm / Rubin F. // IEEE Transactions on

Computers. 1974. Vol. C-23, Iss. 9. P. 907–914.

Алдошкин Д. Н. Поиск пути мобильного робота в условиях наличия препятствий и

неполноты информации о среде / Алдошкин Д. Н., Царев Р. Ю // Мехатроника,

автоматизация, управление. 2016. № 7. С. 465–470.

##submission.downloads##

Опубліковано

2020-02-20

Номер

Розділ

Інформаційні технології