Маршрутизация автономных устройств в трёхмерном пространстве

Аннотация

Статья посвящена решению проблемы маршрутизации автономных устройств в трёхмерном пространстве, что является актуальной задачей в области интеллектуального управления. Трёхмерное пространство отличается высокой степенью свободы, сложной топологией и динамическими изменениями среды, что значительно усложняет задачу эффективного планирования траекторий. Разработка методов маршрутизации, обеспечивающих безопасность, энерго и вычислительную эффективность, имеет ключевое значение для повышения производительности автономных систем. В работе рассматривается комплексная система маршрутизации, основанная на гибридном подходе, объединяющем высокоуровневое моделирование рабочего пространства с метаэвристическими методами оптимизации. Для представления трёхмерной среды используются иерархические структуры данных, такие как октодеревья, что обеспечивает компактность и гибкость пространственных моделей. Эти модели преобразуются в графовые структуры, что позволяет описать маршрутизацию в виде оптимизационной задачи на графах. Предложен модифицированный метаэвристический муравьиный алгоритм, относящийся к классу роевых методов оптимизации. Алгоритм ориентирован на построение безопасных и энергоэффективных маршрутов, а также на решение задач поиска кратчайших гамельтоновых циклов и динамической перенастройки маршрута в условиях изменяющейся внешней среды. В работе представлены результаты вычислительного эксперимента, включающие тестирование алгоритма в условиях трёхмерного пространства, и сравнительный анализ с другими алгоритмами маршрутизации. Вычислительный эксперимент подтвердил эффективность разработанного алгоритма маршрутизации, включая сокращение времени вычислений и повышение энергоэффективности автономных устройств. Перспективы дальнейших исследований включают интеграцию предложенной системы в широкий спектр приложений для автономных устройств, направленных на оптимизацию процессов управления и повышение эффективности в динамически изменяющейся внешней среде. Отметим, что разработанный алгоритм может быть адаптирован для решения комплексных задач, в которых маршрутизация и размещение ветрогенераторов на плоскости взаимосвязаны. Задача размещения напрямую связана с построением маршрутов для обслуживания этих объектов, что требует комплексного подхода для эффективного решения этих задач. Это станет частью системы поддержки принятия решений, предназначенной для планирования и обслуживания ветрогенераторных комплексов, обеспечивая их эффективное функционирование и управление ресурсами.

Abstract

The article addresses the problem of routing autonomous devices in three-dimensional space, which is a relevant task for intelligent control. The three-dimensional space is characterized by a high degree of freedom, complex topology, and dynamic environmental changes, which significantly complicate the task of effective trajectory planning. The development of routing methods that ensure safety, energy efficiency, and computational efficiency is crucial for improving the performance of autonomous systems. The paper presents a comprehensive routing system based on a hybrid approach that combines high-level modeling of the working space with metaheuristic optimization methods. Hierarchical data structures, such as octrees, are used to represent the three-dimensional environment, providing compactness and flexibility for spatial models. These models are transformed into graph structures, allowing the routing problem to be described as an optimization problem on graphs. A modified metaheuristic ant colony optimization algorithm, belonging to the class of swarm optimization methods, is proposed. The algorithm is designed to build safe and energy-efficient routes, as well as to solve problems related to finding the shortest Hamiltonian cycles and dynamically reconfiguring routes in a changing external environment. The paper presents the results of computational experiments, including algorithm testing in three-dimensional space and a comparative analysis with other routing algorithms. The computational experiment confirmed the effectiveness of the developed routing algorithm, including reduced computation time and improved energy efficiency of autonomous devices. The prospects for further research include integrating the proposed system into a wide range of applications for autonomous devices aimed at optimizing control processes and enhancing performance in a dynamically changing external environment. It is worth noting that the developed algorithm can be adapted to solve complex tasks where routing and wind generator placement on a plane are interrelated. The placement problem is directly connected to route construction for servicing these objects, which requires a comprehensive approach for an efficient solution. This will be part of a decision support system designed for the planning and servicing of wind power complexes, ensuring their effective operation and resource management.