Способ автоматического группового целераспределения истребителей с учетом приоритета целей
METHOD OF AUTOMATIC GROUP TARGET ALLOCATION OF FIGHTERS BASED ON PRIORITY OF TARGETS

Изобретение относится к системам управления летательными аппаратами (ЛА) и может быть использовано в комплексе функциональных программ управления и наведения ЛА авиационных комплексов для назначения целей перехватчикам при противостоянии групп ЛА.
Анализ особенностей ведения боевых действий в рамках стратегии бесконтактных сетецентрических войн [1] свидетельствует о том, что основным видом воздушно-космического противоборства является групповое применение как средств нападения, так и защиты. В связи с этим оценка возможностей группы ЛА по решению задач группового боестолкновения является весьма актуальной.
ij
В аналогах [2, 3] предлагаемого изобретения в основном рассматривается выбор целей, наилучших для перехвата, исходя из решения очень сложной задачи нелинейного целочисленного программирования на основе расчета вероятностей поражения отдельных целей отдельными объектами. Способ назначения различных i-х типов оружия  на j-е цели , изложенный в [2], основан на задании вероятностей поражения каждой цели каждым типом оружия. Для всякого возможного назначения типов оружия на цели определяют вероятность их выживания. Выбирают такое назначение x, которое минимизирует ожидаемую суммарную опасность
непораженных целей, где
j
V - коэффициент опасности j-й цели,
ij
q - вероятность выживания j-й цели при использовании i-го типа оружия,
ij
x - количество экземпляров i-го типа оружия, назначенных на j-ю цель.
С математической точки зрения такая задача представляет собой сложную задачу нелинейного целочисленного программирования. Нахождение ее точного решения практически невозможно уже при рассмотрении двух десятков объектов [2].
При целераспределении по маневрирующим целям необходимо знать время жизни гипотез изменения скорости цели (обычно несколько секунд). По истечении этого интервала необходимо снова решить задачу целераспределения и сформулировать сопутствующий закон управления.
Кроме того, среди целей некоторые могут быть очень важными, их требуется уничтожить с достаточно высокой степенью вероятности.
Целью предлагаемого изобретения является разработка более простого способа целераспределения в групповом противоборстве, эффективность которого определяется с учетом выполнения реальных ограничений на перехват в процессе полета на выбранную для поражения цель. Этот способ должен учитывать возможность наличия важных целей, которые необходимо перехватить с высокой степенью вероятности.
В качестве прототипа был выбран способ целераспределения, изложенный в работе [4], в котором все цели предполагаются равнозначными.
Специфика решаемой задачи предопределяет необходимость учета как временных, так и энергетических затрат на выполнение перехвата.
Предлагаемый в прототипе подход к формированию предполагаемой траектории перехвата, учитывающий эти требования, основан на использовании функционала
временных и энергетических затрат на перехват для каждой пары перехватчика с номером n и цели с номером m, где
Т - полное время полета перехватчика по траектории,
K - постоянный коэффициент, выбираемый из соображений баланса между временем перехвата и затратами на полет с ускорением,
J - вектор ускорения перехватчика,
t - время действия ускорения.
В (2) второе слагаемое учитывает затраты на формирование управляющего сигнала перехватчика.
По минимуму этого функционала, найденному среди определенного класса траекторий, строится матрица эффективности перехвата, процедура построения которой приведена ниже. На основе полученной матрицы при помощи известного алгоритма находится оптимальное распределение, обеспечивающее минимум суммарного функционала качества
среди всех возможных назначений m(n) целей перехватчикам.
Технический результат, который может быть получен от использования предлагаемого изобретения, заключается в возможности автоматического оптимального назначения целей перехватчикам с учетом приоритета целей, что снижает информационную нагрузку на операторов (штурманов наведения).
Заявленный технический результат, который может быть получен от реализации предлагаемого технического решения, достигается тем, что решается задача поиска оптимального значения суммарного функционала качества, основанного на временных и энергетических затратах с учетом реальных ограничений на возможности перехватчиков.
Возможность достижения технического результата обусловлена следующими причинами:
- индивидуальный функционал эффективности перехвата (2) для каждой пары перехватчик-цель основывается на рассмотрении временных и энергетических затрат с учетом реальных ограничений на возможности перехватчиков;
- задача поиска минимального значения функционала перехвата (2) сводится к задаче поиска корней многочлена, способ решения которой известен [5];
- в зависимости от соотношения количеств целей и перехватчиков, а также от требований в вероятностям перехвата важных целей, задача поиска минимума суммарного функционала эффективности перехвата (3) сводится либо «задаче о назначениях» [6], которая эффективно решается «венгерским алгоритмом» [6], либо к более сложной задаче о нахождении минимального потока в сети [7, 8], которая может быть решена при умеренном количестве целей.
Сущность предлагаемого изобретения заключается в разработке принципиально нового способа автоматического назначения группы целей группе перехватчиков, при котором заранее выбранный функционал качества (2), учитывающий как временные, так и энергетические затраты на выполнение перехвата, вычисляют для каждой пары перехватчик-цель, затем ищут его минимум среди заданного класса траекторий с учетом заданных ограничений на скорости и ускорения перехватчиков, после чего целераспределение определяется решением «задачи о назначениях» [6] или решением задачи о нахождении минимального потока в сети [7, 8].
n,m
m
m
m
В решаемой задаче для группы, состоящей из N произвольно расположенных перехватчиков и М целей, необходимо назначить n-му  перехватчику m-ю  цель, наилучшую по минимуму суммарного функционала эффективности перехвата (3), в котором I представляет собой функционал, соответствующий траектории перехвата n-м перехватчиком m-й цели. Минимизация функционала (3) производится по всем возможным назначениям m(n) n-го перехватчика на m-ю цель, удовлетворяющим определенным условиям. Эти условия позволяют учесть важность целей следующим образом. Будем рассматривать один из самых простых способов, когда для важной цели с номером m задается требуемая вероятность ее поражения Q. Также для важной цели с номером m предполагается известной вероятность P ее поражения отдельным перехватчиком, определяемая соотношение ЛТХ самолетов и оружия противоборствующих сторон [9, 10]. Будем считать, что вероятности перехвата цели отдельными перехватчиками независимы друг от друга. Тогда размер k группы перехватчиков, реализующих общую вероятность поражения не менее требуемой, определяется из условия
m
В соответствии с этими условиями, требуется, чтобы в искомом назначении m(n) на важную цель с номером m было назначено k перехватчиков. Предполагается, что общее число перехватчиков достаточно для обеспечения требуемой вероятности поражения для всех важных целей. Для оставшихся обычных целей требуется назначить по одному перехватчику для каждой цели, если имеется достаточное для этого количество перехватчиком, если же перехватчиков недостаточно, то каждому оставшемуся перехватчику назначается цель, при этом для некоторых целей перехватчики не будут назначены.
Задача будет решаться при условии, что выполняются следующие допущения:
- цели и перехватчики расположены в пространстве произвольно, имеют различные начальные скорости и направления полета;
- перехватчики являются равнозначными;
- некоторые цели могут являться важными и должны быть уничтожены с вероятностью, не меньшей требуемой;
- для важных целей заданы вероятности перехвата отдельными перехватчиками;
- цели не маневрируют и летят с постоянными скоростями;
- все перехватчики обладают достаточным запасом топлива;
- траектория каждого перехватчика состоит из двух участков: на первом выполняется доворот на цель до требуемого угла упреждения с постоянным ускорением, а на втором - прямолинейный полет в упрежденную точку встречи;
- заданы максимально допустимые значения скоростей и ускорений перехватчиков.
Решение задачи будет состоять из следующих этапов.
1. На первом этапе выбирают класс траекторий, с помощью которых перехватчики должны перехватывать цели. На основе этого вычисляют индивидуальный функционал качества (2) перехвата для каждой пары «перехватчик-цель» с учетом заданных максимально допустимых значений скоростей и ускорений перехватчиков.
2. На втором этапе решение задачи поиска минимума индивидуального функционала качества (2) сводят к решению нескольких задач минимизации с ограничениями типа равенств.
3. На третьем этапе в зависимости от количества целей и перехватчиков, а также от наличия важных целей, определяется тип задачи оптимизации и способ ее решения. Ее решение определяет назначение целей перехватчикам, обеспечивающее минимум суммарного функционала (3) в соответствии с видом поставленной задачи.
0
Первый этап проиллюстрирован фигурой 1. Выберем определенный перехватчик и определенную цель. В начальный момент перехватчик находится в точке А и летит со скоростью V, а цель находится в точке В и летит со скоростью V. Предполагаемую траекторию перехвата, состоящую из двух участков, строят следующим образом: на первом участке перехватчик летит с постоянным ускорением J, выполняя доворот на цель, до момента t, когда перехватчик находится в точке С, а цель - в точке D, затем на втором участке перехватчик летит с постоянной скоростью до момента Т.
t
t
t
Условие перехвата в случае, когда перехватчик и цель летят с постоянными скоростями, заключается в том, что относительная скорость полета перехватчика направлена по линии визирования цели. Это означает, что в момент t окончания действия ускорения относительная скорость полета должна быть направлена по вектору  (фиг. 1). Тогда перехватчик и цель встретятся в точке Е. Если обозначить в момент t относительное положение цели  и относительную скорость перехватчика V, то из условия перехвата следует, что для некоторого τ≥0 выполнено r = τV.
t
t
Здесь τ является интервалом времени между моментом окончания действия ускорения и моментом перехвата. Обозначив положение цели относительно перехватчика в начальный момент времени , после выражения r, V через начальные величины получим:
Преобразовав (5), получим
Сумма t+τ представляет собой полное время полета T. Тогда
t
0
max
max
max
Согласно принятым допущениям, скорость перехватчика V = V+Jt в момент окончания действия ускорения не может превышать V, а его ускорение - J. Из (6) следует, что ограничение |J|≤J определяет неравенство
t
max
а ограничение |V|≤V - неравенство
при
m,n
Определив Jt из (6) и подставив в (2), получим функцию двух переменных I(T,t), которую требуется минимизировать при ограничениях (7)-(10).
*
*
*
*
Допустим, что функционал принимает минимальное значение при некоторых значениях T,t, так что все неравенства (7)-(10) являются строгими. Можно утверждать, что при некоторых значениях J* и t величина |J|t не увеличится, ограничение по скорости будет выполнено и перехват цели произойдет в момент Т≤Т. В результате значение функционала (2) уменьшится. Поэтому минимальное значение функционала (2)следует искать при условии, что одно или два неравенства из (7)-(10) становятся равенствами.
На втором этапе алгоритма последовательно проверяются следующие условия.
t
0
max
1. Если (8) является равенством, то выполняется условие |V|=|V+Jt|=V. С его помощью функционал (2) можно представить в виде
После подстановки Jt из (6) получим
После замены переменной Т на z = 2T-t функционал принимает вид
а равенство (8) -
Введем обозначения
Тогда после возведения (12) в квадрат получим
а (11) принимает вид
После замены переменных х = 1/ z; y = t/z поиск минимума (11) сводится к минимизации функционала
при ограничении
Если ввести множитель Лагранжа λ, то необходимым условием минимума будет
a
a
Обозначим P=2y+b+dx; Q=2ƒx+e+dy; H=(d-е)х+(2-b)y.
После исключения λ и вычисления производных получим уравнение
Избавившись от корня с помощью возведения в квадрат, получим равенство
которое после упрощения с помощью (16) принимает вид
0
1
1
1
2
2
2
a
Тем самым, задача минимизации (15) сведена к решению системы уравнений (16), (17). Так как коэффициент ƒ=|r| положителен, заменой х=(2ξ-dy-е)/2ƒ можно привести (16) к виду ξ = y+by+с. При этом (17) можно записать в виде:
k
где h(y) - некоторые многочлены степени k. После возведения в квадрат останутся только четные степени ξ, которые выражаются через у. В результате получится уравнение двенадцатой степени относительно y. Численно найдем все его действительные корни при помощи известных алгоритмов нахождения корней многочленов [5]. Подставим найденные корни в (16) и из полученного квадратного уравнения найдем действительные значения х, если таковые существуют. В результате получим несколько пар значений х, у. Перейдем обратно к переменным T,t, и выбросим те значения, которые не удовлетворяют (7), (9) и (10). Оставшиеся пары занесем в общий список кандидатов на минимум функционала (2).
max
2. Если равенством является (7), т.е. |J|=J, то из него можно выразить t:
max
где использованы обозначения (13). Знак перед вторым слагаемым выбран исходя из условия t≤Т. В функционале (2) положим |J|=J и подставим в него найденное выражение для t. В результате функционал качества становится функцией Т:
m,n
Вычислим производную dI(T)/dT и приравняем ее нулю. Если обозначить
то после ряда преобразований условие равенства нулю производной определяется соотношением
которое после раскрытия скобок приводит к уравнению восьмой степени по переменной Т. Решим его численно. Для каждого полученного Т найдем t из (18). Из всех полученных пар действительных значений (T,t) оставим только те, которые удовлетворяют (8), (9) и (10). Занесем их в общий список кандидатов на минимум функционала (2).
3. Если равенством является (9) (Т=t), т.е. с начала перехвата цели до его окончания реализуется равноускоренный полет перехватчика, то выразим Jt из (6) и подставим его в (2):
Если перейти к z=1/T, то в обозначениях (13) получим
m,n
Уравнение dI(z)/dz=0 сводится к уравнению шестой степени
Решим его численно и те корни, для которых выполнены (7), (8) и (10), добавим в общий список кандидатов на минимум функционала (2).
0
0
min
*
4. Если равенством является (10) (t=0), т.е. имеет место полет с постоянной скоростью, то расстояние от перехватчика до цели в момент Т* будет |r+(V-V)T|. Оно принимает минимальное значение  при  в обозначениях (13). Если  и величина промаха r находится в допустимых пределах, то добавим пару значений ; t=0 в общий список кандидатов на минимум с соответствующим значением функционала .
5. В случае, когда из четырех неравенств (7)-(10) два являются равенствами, возможны следующие ситуации.
t
max
max
5.1. Пусть равенствами являются выражения (7) и (8), т.е. |V|=V,|J|=J. Сделаем замену z=2Т-t. Тогда после возведения в квадрат в обозначениях (13) равенство (8) примет вид (14), а равенство (7) запишется как
Сложив (19) и (14), получим
Можно сократить на z т.к. z=T+(Т-t)≥T>0:
Выразим отсюда z и подставим в (14). Получится уравнение шестой степени относительно t:
где обозначено
Численно найдем все действительные корни t уравнения (21), затем найдем соответствующие значения z из (20) и значения T=(z+t)/2.
Удовлетворяющие неравенствам (9) и (10) значения занесем в общий список кандидатов на минимум функционала (2).
5.2. Пусть равенствами являются (7) и (9). Тогда после подстановки t=Т в (7) и возведения в квадрат получится уравнение
Его решения, удовлетворяющие неравенствам (8) и (10), добавим в общий список кандидатов на минимум функционала (2).
5.3. Пусть теперь равенствами являются (8) и (9). Подставим t=T в (8) и возведем в квадрат. В обозначениях (13) получим уравнение
Его решения, удовлетворяющие неравенствам (7) и (10), добавим в общий список кандидатов на минимум функционала (2).
5.4. Вырожденный случай, когда одним из равенств является (10), уже был рассмотрен ранее в п. 4.
m,n
Теперь найдем глобальный минимум функционала (2). Для всех пар величин (T,t) из общего списка кандидатов на минимум функционала (2), построенного на предыдущих этапах, вычислим Jt с помощью (6) и подставим полученное значение в (2). Выберем те величины, которые дают минимальное значение. Полученное значение Т вместе с соответствующим значением t, значением функционала I и вектором J определяют наилучшую траекторию перехвата цели и затраты на ее реализацию.
n,m
m
Решив задачу поиска минимума (2) для одиночного перехватчика и цели, перейдем к третьему этапу алгоритма. Для каждого перехватчика с номером n и цели с номером m определяют наилучшую траекторию перехвата и соответствующее значение I функционала (2). Для важных целей по формуле (4) определяются требуемые количества перехватчиков k. Задача поиска целераспределения попадает в один из четырех классов.
n,m
1. Важных целей нет, все цели равнозначны. Задача поиска целераспределения в этом случае формулируется как «задача о назначениях» [6], с матрицей стоимости I. Способ решения этой задачи известен под названием «венгерский алгоритм» [6]. Этот алгоритм состоит из последовательных итераций, на каждой из которых назначение m(n) формируется так, что суммарная стоимость выбора на каждой последующей итерации уменьшается. В результате получается такой вариант назначения перехватчиков на цели, который дает минимальное значение суммарных затрат на его реализацию. Если М>N, то каждому перехватчику будет назначена своя цель, но для некоторых целей перехватчики назначены не будут. Если N>M, то для каждой цели будет назначен перехватчик и некоторые перехватчики останутся без назначения.
n,m
2. Некоторые из целей являются важными, но количество перехватчиков достаточно для назначения требуемого количества перехватчиков на важные цели и по одному из перехватчиков на обычные цели. Для решения построим ту же матрицу I, что и в предыдущем пункте.
m
m
Затем вместо столбца с номером m, соответствующего важной цели, вставим k копий этого столбца. Применение «венгерского алгоритма» к построенной таким образом расширенной матрице даст искомое целераспределение. Каждой важной цели будет назначено k перехватчиков, другим целям будет назначено по одному перехватчику, лишние перехватчики, если они есть, будут свободны.
3. Некоторые из целей являются важными, а количество перехватчиков недостаточно для назначения требуемого количества перехватчиков на важные цели. Тогда поставленная задача не имеет решения.
m
n,m
max
n,m
n,m
max
4. Некоторые из целей являются важными, количество перехватчиков достаточно, чтобы выделить по k перехватчиков на важные цели, но оставшихся перехватчиков недостаточно для того, чтобы назначить по одному перехватчику для обычных целей. Эту задачу уже нельзя сформулировать в виде «задачи о назначениях». Однако ее можно сформулировать в виде более общей задачи нахождения потока минимальной стоимости в графе. Подробное описание этой задачи и способов ее решения можно найти в [7, 8]. Как правило, все исходные данные предполагаются целочисленными, поэтому следует предварительно преобразовать матрицу I, для чего нужно найти максимальный элемент I матрицы I, а затем умножить все элементы I на 10000/I и округлить до целых чисел.
n,m
n,m
m
Задача поиска целераспределения в виде задачи нахождения потока минимальной стоимости в графе формулируется следующим образом. Граф целераспределения (фиг. 2) представляет собой направленный граф, содержащий по одной вершине для каждого перехватчика и цели, а также две специальные вершины: исток (И) и сток (С). От каждого перехватчика n к каждой цели m ведет ребро стоимостью I (целое число) и с единичной пропускной способностью. Из истока к каждому перехватчику ведет ребро нулевой стоимости и единичной пропускной способности. От каждой цели к стоку идет ребро. Для обычных целей его стоимость задается величиной, значительно превышающей максимум величин I, а его пропускная способность равна единице. Для важных целей стоимость ребра равна нулю, а пропускная способность равна k. Требуется пропустить поток размера N из истока в сток. Решением задачи является величина потока для каждого ребра. Назначение целей на перехватчики определяется ребрами, ведущими от перехватчиков к целям, для которых величина найденного потока равна единице.
Сформированное в результате решения задачи назначение целей перехватчикам по линиям связи передают в систему командного управления, в которой формируют сигналы управления перехватчиками, обеспечивающие их наведение на выбранные цели.
Следует отметить, что для использования алгоритма необходимы оценки: векторов скорости всех перехватчиков и целей; векторов относительного положения для каждой пары перехватчик - цель; максимальных ограничения на величины скорости и ускорения перехватчиков. Эти данные могут быть представлены в любой форме: в декартовых или полярных координатах, в абсолютных или относительных величинах. Нужно лишь указать способ вычисления коэффициентов (13).
Работоспособность разработанного алгоритма (2)-(22) исследовалась в процессе имитационного моделирования. В качестве примера рассмотрим процедуру перехвата целей  перехватчиками .
Схема расположения N = 6 перехватчиков и М = 3 целей при моделировании целераспределения с учетом приоритета показана на фиг. 3. Цель с номером 4 считается важной. Вероятность ее поражения отдельным перехватчиком принята равной 0,5, а требуемая вероятность перехвата положена равной 0,9. В соответствии с формулой (4) для ее перехвата требуется четыре перехватчика. Поэтому общее количество перехватчиков недостаточно для перехвата всех целей и поставленная задача соответствует четвертому пункту третьего шага алгоритма. В результате решения задачи о минимальном потоке в графе на цель номер 4 были назначены первый, второй, третий и четвертый перехватчики, на вторую цель был назначен пятый перехватчик, а на третью цель - шестой. Для первой цели перехватчиков назначено не было. Предполагаемые траектории перехвата, соответствующие этому назначению, показаны на фиг. 3.
Полученный алгоритм группового целераспределения подтвердил свою эффективность в широком поле условий применения. Его достоинством является то, что он позволяет обеспечить не только назначение перехватчиков на цели с учетом важности целей, но и построение предполагаемых траекторий перехвата с учетом реальных ограничений на предельно допустимые скорости и ускорения.
Предложенный алгоритм можно использовать для реализации различных методов наведения.
Промышленная применимость предлагаемого технического решения подтверждается также возможностью реализации его назначения с помощью стандартных бортовых вычислительных средств.
Следует отметить, что предлагаемый алгоритм следует общей схеме, используемой в отечественных авиационных комплексах радиолокационного дозора и наведения.
Список использованных источников
1. Е.А. Федосов. Реализация сетецентрической технологии ведения боевых действий потребует создания БРЛС нового поколения. // Фазотрон. 2007. №1, 2.
2. R. Ahuja, A. Kumar, J. Krishna, J. Orlin. Exact and heuristic algorithms for the weapon - target assignment problem. //Operations research, 2007, 55, №6, pp. 1136-1146.
3. J. Zhang, С. Hu, X. Wang, D. Yuan. ACGA algorithm of solving weapon -target assignment problem. // Open journal of applied sciences, 2012.
4. В.И. Меркулов, A.C. Пляшечник. Групповое целераспределение в воздушном противоборстве. //Информационно-измерительные и управляющие системы. 2016. №7. С. 59-63.
5. М.А. Jenkins. Algorithm 493: Zeros of a real polynomial. // ACM transactions on mathematical software, 1975, 1, №2, pp. 178-189.
6. J. Munkres. Algorithms for assignment and transportation problems. // Journal of the society for industrial and applied mathematics, 2000, 5, №1, pp. 32-38.
7. Кристофидес H. Теория графов. Алгоритмический подход. М.: Мир, 1978.
8. Gross J.L., Yellen J., Zhang P. Handbook of Graph Theory. CRC Press, 2014.
9. Зуенко Ю.А., Коростелев С.Е. Боевые самолеты России. М: Элакос, 1994.
10. Williams М. Superfighters: The Next Generation of Combat Aircraft. AIRTime Publishing, Incorporated, 2002.