ОБ ОДНОМ ПОДХОДЕ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА ДЛЯ ПЛАНИРОВАНИЯ АВТОНОМНЫМ БЕСПИЛОТНЫМ ЛЕТАТЕЛЬНЫМ АППАРАТОМ МАРШРУТОВ ОБЛЕТА ЦЕЛЕЙ

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

Objective. Develop a principle of constructing tools and procedures for optimal routing of targets by an autonomous uncrewed aerial vehicle, which have an acceptable complexity for implementation on an onboard computer. Methods. The rules for optimizing the terrain map with the located targets, creating a penalty matrix that considers the disturbing factors of the unstable air environment in the planning process, and building a reference tree for finding the minimum route for the accepted cost of flying around the targets. Results. A principle is proposed to develop effective procedures for planning minimum cost-effective routes to fly around targets in an unstable air environment. The basis for behavior planning is the optimization of the formal description of a given terrain map, which leads to a significant reduction in the number of alternatives compared in the process of searching for a minimum route to fly around targets. This, in turn, makes it possible to implement planning procedures on the onboard computer system of an autonomous uncrewed aerial vehicle. A statement is proved to justify the existence of a minimum route for the accepted cost of overflying targets in the formal description of the terrain map obtained as a result of converting its original representation based on the developed optimization rules. Conclusion. The considered approach effectively solves various types of issues reduced to the traveling salesman problem, including planning the minimum route of flying around targets by an autonomous uncrewed aerial vehicle in an unstable air environment under uncertainty conditions.