Designing the Optimal Trajectory for Monitoring Objects
DOI:
https://doi.org/10.14529/cmse240302Keywords:
routing, plane graph, algorithm, optimization, constraints, drone and truck problem, precision farming, monitoringAbstract
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.References
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).
