Проектирование оптимальной траектории проведения мониторинга объектов
Автор: Саллам М., Макаровских Т.А.
Статья в выпуске: 3 т.13, 2024 года.
Бесплатный доступ
В статье рассматривается задача разработки системы для моделирования траекторий движения робота, проводящего мониторинг в замкнутой области с земли: осмотр помещений, съемка промышленных объектов, оценка состояния фруктовых деревьев и т.д. Во время мониторинга на пути робота могут возникнуть некоторые препятствия: временно возникшие и устранимые (люди, небольшая мебель, бытовая техника, зона чрезвычайной ситуации) или постоянные (стены, постоянно установленное оборудование, зафиксированная мебель). Управление роботом осуществляется с помощью разработанной авторами программы, в которой хранится база данных маршрутов, успешно преодоленных роботом ранее, для наиболее точного определения траектории движения робота с учетом препятствий, встречающихся вдоль построенного пути. В статье рассматривается алгоритм построения графовой модели области проведения мониторинга для последующего поиска кратчайшего маршрута робота, заключающийся в дискретизации исследуемой области, выявлении возможных путей перемещения робота, анализе имеющихся препятствий и задании расстояний между объектами исследования. Показано, что после построения такого графа возможно применить один из алгоритмов поиска гамильтонова пути. Он соединяет вершины графа, соответствующие точкам проведения мониторинга. Результатом применения алгоритма будет кратчайший маршрут робота, либо сообщение о невозможности проведения мониторинга (частичной или полной неразрешимости задачи), если ряд возникших препятствий не позволяет проложить маршрут, проходящий через некоторые (либо через все) вершины. Выбор наиболее подходящего алгоритма, а также использование методов искусственного интеллекта для классификации препятствий и внесения корректировок в маршруты являются направлениями дальнейших исследований.
Маршрутизация, плоский граф, алгоритм, оптимизация, ограничения, задача о дроне и грузовике, точное земледелие, мониторинг
Короткий адрес: https://sciup.org/147244890
IDR: 147244890 | УДК: 51.77 | DOI: 10.14529/cmse240302
Designing the optimal trajectory for monitoring objects
The article considers the task of developing a system for modeling the trajectories of a robot monitoring in a closed area from the ground: inspection of premises, survey of industrial facilities, assessment of the condition of fruit trees, etc. During monitoring, some obstacles may arise in the robot’s path: temporary and removable (people, small furniture, household appliances, emergency zone) or permanent (walls, permanently installed equipment, fixed furniture). The robot is controlled using a program developed by the authors, which stores a database of routes successfully overcome by the robot earlier, for the most accurate determination of the trajectory of the robot, taking into account obstacles encountered along the constructed path. The article considers an algorithm for constructing a graph model of the monitoring area for the subsequent search for the shortest route of the robot, which consists in discretization the area, identifying possible ways to move the robot, analyzing existing obstacles and setting distances between the objects of study. It is shown that after obtaining such a graph, it is possible to apply one of the algorithms for finding the Hamiltonian path in a graph. It connects the vertices of the graph corresponding to the monitoring points. The result of applying the algorithm is the shortest route of the robot, or a message about the impossibility of monitoring (partial or complete insolubility of the problem) if a number of obstacles do not allow you to plot a route passing through some (or all) vertices.
Список литературы Проектирование оптимальной траектории проведения мониторинга объектов
- Sundarrajan M., Jothi A., Prabakar D., Kadry S. The Smart Coverage Path Planner for Autonomous Drones Using TSP and Tree Selection // Mining Intelligence and Knowledge Exploration. MIKE 2023. Vol. 13924 / ed. by S. Kadry, R. Prasath. Springer, 2023. P. 161-172. Lecture Notes in Computer Science. DOI: 10.1007/978-3-031-44084-7_16
- Ченцов А.Г. Задача маршрутизации на узкие места с системой первоочередных заданий // Известия Института математики и информатики Удмуртского государственного университета. 2023. Т. 61. C. 156-186. DOI: 10.35634/2226-3594-2023-61-09 EDN: QQUDUB
- Ченцов А.Г., Ченцов П.А. Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования // Труды Института математики и механики УрО РАН. 2022. Т. 28, № 2. C. 215-248. DOI: 10.21538/0134-4889-2022-28-2-215-248 EDN: DPDBQQ
- Wu J., Li M., Gao C., et al. Research on Deployment Scheme and Routing Optimization Algorithm of Distribution Cable Condition Monitoring Devices // Energies. 2023. Vol. 16. P. 852-879. DOI: 10.3390/en16196930 EDN: BTMUSE
- Chung S.H., Sah B., Lee J. Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions // Computers & Operations Research. 2020. Vol. 123. DOI: 10.1016/j.cor.2020.105004
- Петунин А.А., Ченцов А.Г., Ченцов П.А. Оптимальная маршрутизация в задачах последовательного обхода мегаполисов при наличии ограничений // Челябинский физико-математический журнал. 2022. Т. 7, № 2. C. 209-233. DOI: 10.47475/2500-0101-2022-17205 EDN: QLFGFW
- Makarovskikh T., Panyukov A., Abotaleb M., et al. Optimal Route for Drone for Monitoring of Crop Yields // Advances in Optimization and Applications. OPTIMA 2023. Vol. 1913 / ed. by N. Olenev, Y. Evtushenko, M. Jaćimović, et al. Springer International Publishing, 2024. P. 228-240. Communications in Computer and Information Science. DOI: 10.1007/978-3-031-48751-4_17
- Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: Издательство УМЦ УПИ, 2016. 220 с.
