Details

Данная работа посвящена оптимизации маршрута робота-доставщика с учетом динамически изменяющихся условий окружающей среды. Задачи, которые решались в ходе исследования: 1) Изучение особенностей алгоритмов для поиска кратчайшего пути на графе. 2) Сравнительный анализ алгоритмов и выбор подходящего для решения задачи оптимизации маршрута робота-доставщика. 3) Изучение устройства и работы робота-доставщика. 4) Разработка плана расчета весов ребер для графа, характеризующего карту робота-доставщика. 5) Разработка программного модуля, решающего задачу оптимизации маршрута робота-доставщика. Работа проведена на основе открытой информации Яндекса о стеке работы команды разработки ПО для роботов и информации об устройстве и функционировании Роверов. Был проведен анализ существующих алгоритмов для работы с графами для выбора наилучшего решения для задачи оптимизации маршрута робота. Анализ проводился путем практического применения алгоритмов к одинаковым графам. Выбор алгоритма повлиял на дальнейшее проектирование и разработку модуля динамического планирования маршрута на языке Python. Для достижения данных результатов в работе были использованы следующие информационные технологии: PyCharm, Draw.io.

This work is devoted to optimizing the route of the delivery robot, taking into account dynamically changing environmental conditions. Tasks that were solved during the research: 1) Studying the features of algorithms for finding the shortest path on a graph. 2) Comparative analysis of algorithms and selection of a delivery robot suitable for solving the route optimization problem. 3) Study of the device and operation of the delivery robot. 4) Development of a plan for calculating edge weights for the graph characterizing the map of the delivery robot. 5) Development of a software module that solves the problem of optimizing the route of the delivery robot. The work was carried out on the basis of Yandexs open information about the work stack of the robot software development team and information about the device and functioning of Rovers. An analysis of existing algorithms for working with graphs was carried out to select the best solution for the task of optimizing the robots route. The analysis was carried out by practical application of algorithms to identical graphs. The choice of the algorithm influenced the further design and development of the dynamic route planning module in Python. To achieve these results, the following information technologies were used in the work: PyCharm, Draw.io.