ДОСЛІДЖЕННЯ МЕТОДУ ВИБОРУ НАЙКОРОТШОГО МАРШРУТУ ПРИ ПЕРЕМІЩЕННІ ОБ’ЄКТА У ПРИМІЩЕННІ
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.
