ДЕЦЕНТРАЛИЗОВАННОЕ ПАКЕТНОЕ РАСПРЕДЕЛЕНИЕ ЦЕЛЕВЫХ ЗАДАЧ ДЛЯ РАЗРЕЖЕННОГО КЛАСТЕРА КОСМИЧЕСКИХ АППАРАТОВ



МЕЛАНЧЕНКО А.Г., СИНЧА А.А. Розглядається метод розподілу цільових завдань проміж КА у складі розрідженого кластеру спостереження Землі, що поєднує відомі підходи вибору КА - переможця зарезультатами аукціону з наступним узгодженням отриманих результатів на підставі консенсусу. Метод що пропонується має переваги перед відомими аналогами.

Ключовіслова: космічний апарат; кластер; цільова задача; інформація про обстановку.

Method of objective task allocation among satellites of sparse Earth observation cluster that combines certain approaches to selection of satellite-auction winner and successive agreement of results on basis of consensus is proposed. The proposed method has advantages over analogues.

Keywords: satellite, cluster, objective problem, situation awareness.

УДК 629.78

Введение

В настоящее время к выходу готовится журнал "Вестник Днепропетровского Национального университета. Ракетно-космическая техника", в котором к публикации принята статья авторов, посвященная субоптимальному методу децентрализованного распределения задач наблюдения Земли для разреженного кластера КА. Полученные результаты показали, что предложенный метод обеспечивает высокую эффективность и быструю сходимость процесса распределения задач. Однако метод базировался на допущении, что одному КА может быть назначено не более одной целевой задачи.

С практической точки зрения иногда более целесообразно иметь возможность пакетного планирования, когда каждому КА кластера назначается не одна, а несколько целевых задач. Для случая компактного кластера, в котором расстояния между КА малы по сравнению с размерами объектов наблюдения, решение такой задачи было предложено в [1], где кластер может рассматриваться как виртуальный многоэлементный КА, и целевые задачи могут распределяться между КА кластера произвольным образом.

Для разреженного кластера условия наблюдения одного и того же объекта наблюдения различными КА могут различаться, что исключает произвольное распределение целевых задач между КА. Для успешного достижения цели, поставленной перед разреженным кластером, необходимо скоординированное пакетное распределение целевых задач между КА.

Основной материал

Пусть известен перечень ${{N}_{T}}$ целевых задач. Необходимо распределить их между ${{N}_{A}}$ КА кластера так, чтобы каждая задача была назначена не более чем одному КА, максимизировав при этом показатель эффективности миссии. Каждому КА может быть назначено не более ${{L}_{T}}$ целевых задач, и процесс распределения задач считается завершенным, как только будет распределено ${{N}_{\min }}=\min \left\{ {{N}_{T}},\ \ {{N}_{A}},{{L}_{T}}\right\}$ задач. КА кластера объединены в неориентированную информационную сеть, имеющую симметричную матрицу смежности $G\left( \tau \right)$, такую, что ${{g}_{ik}}\left( \tau \right)=1$, если в момент времени τсуществует линия связи между КА i и k . Глобальную целевую функцию определим как сумму локальных показателей эффективности, в качестве которых будем использовать функцию оценки всех целевых задач, назначенных конкретному КА.

В рассмотренной постановке распределение целевых задач в кластере КА задач представляет собой задачу целочисленного программирования следующего вида:

\[\max \sum\nolimits_{i=1}^{{{N}_{A}}}{\left(\sum\nolimits_{j=1}^{{{N}_{T}}}{{{c}_{ij}}}({{x}_{i}},{{p}_{i}}){{x}_{ij}}\right)},\ \sum\nolimits_{i=1}^{{{N}_{A}}}{{{x}_{ij}}}\le {{L}_{T}},\ \]

\[\forall i\in I,\sum\nolimits_{j=1}^{{{N}_{T}}}{{{x}_{ij}}}\le 1,\ \forall j\in J,\]

\[\sum\nolimits_{i=1}^{{{N}_{A}}}{\sum\nolimits_{j=1}^{{{N}_{T}}}{{{x}_{ij}}}}={{N}_{\min}}=\min \left\{ {{N}_{T}} \right.,\,\ \left. {{N}_{A}}{{L}_{T}} \right\},\,\]

\[\ {{x}_{ij}}\in\left\{ 0,\ 1 \right\},\ \forall \left( i,\ j \right)\in I\times J,\quad\quad\quad(1)\]

где двоичная переменная решения ${{x}_{ij}}=1$, если выполнение задачи j назначено КА i, а ${{x}_{i}}\in {{\left\{0,\ \ 1 \right\}}^{{{N}_{T}}}}$ – вектор, j-м элементом которого является переменная ${{x}_{ij}}$.

Вектор ${{p}_{i}}\in\left( J \right.\cup {{\left. \left\{ \varnothing \right\} \right)}^{{{L}_{T}}}}$ представляет собой упорядоченную последовательность целевых задач для КА i, и соответствует маршруту, вдоль которого выполняется наблюдение. Элемент pk этого вектора равен $j\in{J}$, если КА i назначено выполнение целевой задачи j в точке k маршрута, и $\varnothing$ (будем обозначать так «пустую» задачу), если этому КА назначено выполнение менее k задач. Оператор суммирования в скобках соответствует локальному эффекту выполнения целевых задач для КА i. Предполагается, что функция оценки удовлетворяет условию ${{}_{ij}}\left({{x}_{i}},{{p}_{i}} \right)\ge 0$.

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

В отличие от известных подходов, предусматривающих формирование пакетов целевых задач с последующим проведением аукциона по выбору пакета-победителя, предлагаемый метод предусматривает проведение аукционов на уровне отдельных целевых задач до включения их в пакет. Задачи выбираются из априорного плана [1], который формируется на Земле и передается на борт каждого КА кластера. Предлагаемый метод децентрализованного пакетного распределения задач реализуется циклически в виде двухэтапного процесса: формирование единого пакета целевых задач по результатам аукционов на первом этапе с последующим разрешением конфликтов по принципу консенсуса без необходимости согласования информации об обстановке между КА кластера.

Моделирование показало, что время распределения задач прямо зависит от ${{N}_{T}}$ и обратно – от ${{L}_{T}}$; при этом оно практически не зависит от погрешности информации об обстановке ${{\bar{\Delta}}_{SA}}$. Для оценки качества распределения задач полученный результат сравнивался с результатами, которые получены с использованием оптимального алгоритма координации задач при отсутствии погрешностей информации об обстановке. Вычислялось среднее значение показателя субоптимальности ${{\bar{\Delta }}_{opt}}$. как разность решения задачи (1) и оптимального решения, выраженная в процентах.

Было установлено, что при отсутствии погрешностей информации об обстановке результаты предлагаемого метода практически не отличаются от оптимальных (${{\bar{\Delta }}_{opt}}$ не превышает 3%). С ростом ${{\bar{\Delta}}_{SA}}$ значение показателя субоптимальности также растет, однако даже при максимальной погрешности информации об обстановке его значение не превышает 30%, что можно считать приемлемым результатом.

Выводы

Разработан новый метод пакетного децентрализованного распределения задач между КА разреженного кластера, который является обобщением полученных ранее результатов для случая назначения одному КА нескольких целевых задач. Результаты моделирования показали, что предложенный метод обеспечивает хорошую сходимость и получение приемлемого результата за ограниченное время, что позволит экономно расходовать вычислительные ресурсы бортового компьютера

Список литературы

$1.$ Меланченко А.Г. Целевое управление кластерами космических аппаратов наблюдения Земли // Автоматика-2014: Материалы 21-й Международной конференции по автоматическому управлению. К.: «Политехника», 2014 – с. 158-159.

Jul 5, 2016