Проектирование оптимальной траектории проведения мониторинга объектов

Мохамед Саллам, Татьяна Анатольевна Макаровских

Аннотация


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

Ключевые слова


маршрутизация; плоский граф; алгоритм; оптимизация; ограничения; задача о дроне и грузовике; точное земледелие; мониторинг

Полный текст:

PDF

Литература


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 K. S., P. R. Springer, 2023. P. 161–172. Lecture Notes in Computer Science. DOI: 10.1007/978-3-031-44084-7_16.

Chentsov A.G. A bottleneck routing problem with a system of priority tasks. Izvestiya IMI UdGU. 2023. Vol. 61. P. 156–186. (in Russian) DOI: 10.35634/2226-3594-2023-61-09.

Chentsov A.G., Chentsov P.A. An extremal two-stage routing problem and procedures based on dynamic programming. Trudy Instituta Matematiki i Mekhaniki UrO RAN. 2022. Vol. 28, no. 2. P. 215–248. (in Russian) DOI: 10.21538/0134-4889-2022-28-2-215-248.

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.

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.

Petunin A.A., Chentsov A.G., Chentsov P.A. Optimal routing in problems of sequential traversal of megapolises in the presence of constraints. Chelyab. Phys.-Math. Journal. 2022. Vol. 7, no. 2. P. 209–233. (in Russian) DOI: 10.47475/2500-0101-2022-17205.

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. Jacimovic, et al. Springer International Publishing, 2024. P. 228–240. Communications in Computer and Information Science. DOI: 10.1007/978-3-031-48751-4_17.

Gimadi E.K., Khachai M.Y. Extreme Tasks on Sets of Permutations. Ekaterinburg: Izdatelstvo UMC UPI, 2016. 220 p. (in Russian).




DOI: http://dx.doi.org/10.14529/cmse240302