Development of models, methods and tools for creating a digital platform for agreed planning of heterogeneous group of small space satellites for remote earth sensing

Full Text

Введение

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

При этом, с одной стороны, наблюдается многократное увеличение количества поступающих заявок на съемку объектов наблюдения (ОН) и повышение требований к качеству, оперативности и эффективности съемки. С другой стороны, растет число предложений от разных производителей МКА, отличающихся своими функциональными и стоимостными возможностями. Примерами являются проекты компании Planet Lab, спутниковая группировка которых насчитывает более 200 действующих спутников Dove (Flock) и 13 спутников субметрового разрешения SkySat, проект компании BlackSky Global, орбитальная группировка которого состоит из 60 спутников ДЗЗ [2], программа создания спутниковой группировки «Сфера» от Роскосмоса на 600 МКА [3] и др. При этом современный технический прогресс делает разработку новых МКА доступной как для университетов, так и для предприятий малого и среднего бизнеса.

Для устранения возможной монополии на рынке, агрегации разрозненных ресурсов и повышения эффективности ДЗЗ предлагается создание цифровой платформы управления гетерогенными группировками МКА разных производителей. Такая платформа призвана выполнять функции «космического юбера» рынка ДЗЗ, позволяя потребителям через «одно окно» подавать запросы на съемку интересующих их ОН, согласованно планировать МКА и наземные станции приема-передачи информации (НС), переданные в управление платформе, и доставлять результаты ДЗЗ потребителями. Под согласованным планированием в данном контексте понимается процесс планирования, при котором итоговое расписание формируется на основе поиска баланса интересов множества конкурирующих и кооперирующихся между собой элементов системы, каждый из которых «оптимизирует» свою целевую функцию (например, заказ «хочет» быть максимально быстро исполненным или ресурс «хочет» быть максимально загруженным), но готов идти на переговоры и уступки ради достижения своих целей. Формируемая таким образом открытая распределенная система ДЗЗ (РС ДЗЗ) позволит повысить оперативность, гибкость, производительность, масштабируемость и надежность работы группировки как для потребителей, так и для поставщиков услуг, снизить транзакционные издержки.

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

Большинство существующих разработок, такие как SaVoir [4], STM [5], STK Scheduler [6] и т. д., представляют собой централизованные, монолитные, иерархические и последовательные решения. Данные системы лишь отчасти удовлетворяют вышеописанным требованиям, что делает их слабо применимыми при построении планов работ крупномасштабных РС ДЗЗ. Таким образом, возникает необходимость либо в серьезной доработке уже существующих программно-алгоритмических решений с учетом возникающих требований, либо в разработке новых подходов к планированию орбитальных группировок МКА, более глубоко учитывающих семантику предметной области.

В качестве одного из таких подходов можно представить расширенное применение мультиагентных технологий, идея которого описана в [7–9]. Их применение на данный момент уже хорошо зарекомендовало себя на практике в различных промышленных решениях [10], которые позволяют гибко и адаптивно производить синтез расписания по событиям в режиме, близком к реальному времени, учитывая индивидуальные особенности заказов и ресурсов. А лежащая в основе данного подхода модель акторных вычислений делает возможным создание высокопроизводительных, распределенных, отказоустойчивых решений, что в совокупности позволяет более эффективно управлять ресурсами РС ДЗЗ в сравнении с традиционными методиками. Таким образом, применение мультиагентного подхода к планированию заявок для крупномасштабных РС ДЗЗ позволяет удовлетворить все вышеуказанные требования.

Предлагаемый в данной работе подход развивает решение, предложенное в работах предшественников [11–13], путем усовершенствования архитектуры мультиагентной системы, а также введения дополнительных эвристик, позволяющих значительно уменьшить сложность аукционоподобных переговоров и комбинаторного перебора при поиске решения.

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

1.     Задача управления орбитальной группировкой малых космических аппаратов ДЗЗ

1.1. Структура космической системы ДЗЗ

Рассмотрим основные компоненты моделируемой РС ДЗЗ. Система представляет собой совокупность двух сегментов: космического комплекса и наземного специального комплекса. На рис. 1 приведена ее упрощенная схема.

Рис. 1. Структура космической системы ДЗЗ

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

В состав наземного комплекса входят следующие структурные элементы:

– центр управления работой орбитального сегмента, объединяющий ряд специальных станций;

– распределенная сеть НС для сбора данных ДЗЗ;

– информационные центры обработки и хранения данных ДЗЗ.

Приведенную структуру РС ДЗЗ можно представить в виде набора МКА $Sat=\left\{sa{t}_i\right\}$, $i=\overline{\mathrm{1,}L}$ и набора НС $GS=\left\{g{s}_j\right\}, r=\overline{\mathrm{1,}G}$. Для возможности настройки модели МКА на аппараты разных производителей для каждого МКА $\left\{sa{t}_i\right\}$ определим следующий набор изменяемых параметров: орбита $O_i$, предельные углы крена maxRollAngle_i и тангажа maxPitchAngle_i, а также параметры установленной на него съемочной аппаратуры ($f$ – фокусное расстояние, $matx$ – размеры матрицы, минимальный угол возвышения солнца minSunAngle_i, объем запоминающего устройства memVol_i). В свою очередь, для каждой НС $g{s}_j$ имеется возможность задать географическое местоположение coord_j параметрами установленной антенны (угол раствора и скорость приема данных). Состав МКА и НС может меняться с течением времени (вводятся в эксплуатацию новые МКА/НС, часть МКА/НС выходят из строя и т. д.). Каждый МКА может иметь ограничения на передачу информации на определенные НС (технического, организационного или какого-либо другого характера). Для НС и МКА могут быть указаны временные интервалы их недоступности.

Целевое функционирование РС ДЗЗ состоит в выполнении множества заявок на съемку ОН $R=\left\{r_p\right\}, p=\overline{\mathrm{1,}P}$. ОН с точки зрения планирования работы целевой аппаратуры орбитальной группировки МКА можно разделить на точечные и площадные. Для заявки $r_p$ может быть задан ее приоритет $p{r}_p$ и множество ограничений (период, в который необходимо выполнить заявку $t_p=\left[t_p^{start};t_p^{end}\right]$, допустимое линейное разрешение полученного снимка minR_p и maxR_p и допустимый угол солнца minSunAngle_p и maxSunAngle_p). Состав множества заявок также заранее целиком не известен и изменяется в ходе работы системы (поступают новые заявки, изменяются параметры уже существующих и т. д.).

В рассматриваемой модели РС МКА выполняет две операции:

– съемка ОН r_p imaging_p, характеризующаяся интервалом выполнения $t_p^{imag}=\left[t_p^{imagStart};t_p^{imagEnd}\right]$, углами крена rollAngle_p и тангажа pitchAngle_p МКА;

– проведение сеанса связи МКА с НС с целью передачи полученных данных на Землю drop_p, характеризующееся интервалом выполнения $t_p^{drop}=\left[t_p^{dropStart};t_p^{dropEnd}\right]$ и скоростью передачи данных baudRate_p.

НС, в свою очередь, выполняет одну операцию – получение данных с МКА receiv_j, характеризующуюся интервалом выполнения $t_p^{receiv}=\left[t_p^{receivStart};t_p^{receivEnd}\right]$.

1.2. Постановка задачи

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

Целевая функция (ЦФ) РС ДЗЗ имеет вид:

$OF=\frac{1}{s}\sum _{k=1}^{N}O{F}_k\to \max$;

$O{F}_k=\sum _{m=1}^M{c}_m{F}_m^k\to \max$, (1)

где $OF$ – ЦФ системы; $O{F}_k$ – ЦФ $k$-й заявки; $S$ – общее количество заявок; $N$ – количество размещенных заявок; $M$ – количество критериев оптимизации; $c_m$ – весовой коэффициент m-го критерия оптимизации ($0\le c_m\le 1, \sum _{m=1}^M{c}_m=1$); $F_m^k$ – оценка $m$-го критерия оптимизации для $k$-й заявки.

В качестве критериев оптимизации выбраны минимизация времени съемки $F_1^k$ и максимизация ее качества $F_2^k$:

$F_1^k=\frac{t_k^{end}-t_k^{imagEnd}}{t_k^{end}-t_k^{start}}$,

$F_2^k=\left\{\begin{array}{l}\frac{\min R_k-r_k}{\min R_k-\max R_k},еслиr_k\ge \max R_k;\\ \frac{r_k}{\max R_k}.\end{array}\right.$

Примем, что на полученное решение накладывается ряд ограничений:

– выполнение условия наблюдаемости между МКА и ОН при съемке;

– наличие радиовидимости МКА и НС при передаче результатов съемки;

– наличие свободного места в бортовом запоминающем устройстве МКА;

– выполнение условия приоритизации заявок;

– согласованность последовательности моментов времени проведения операций;

– возможность одновременного выполнения МКА и НС не более одной операции.

2.     Обзор источников

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

Методы линейного программирования в качестве способа решения данной задачи рассматриваются в работах [14–16]. Проведенные авторами экспериментальные исследования показали хорошие результаты в решении данной проблемы применительно даже к спутниковой группировке. Однако используемые в них ЦФ предполагают оптимизацию лишь по одному критерию, а время работы растет экспоненциально с ростом размерности входных данных. В работах [17, 18] для поиска решения предлагается применение модифицированного муравьиного алгоритма, в работах [19, 20] – метод локального поиска для планирования съемки КА с несколькими степенями свободы, а в работах [21, 22] – генетический алгоритм для планирования съемки площадных ОН. Эвристические и метаэвристические алгоритмы показывают более высокую производительность в сравнении с традиционными методами оптимизации, однако применяемые в них эвристики требуют жесткой спецификации под конкретные условия задачи, а время работы и качество полученного решения могут сильно зависеть от исходных данных. Попытки применения методов машинного обучения (МО) описываются в работах [23–25]. Данное направление имеет большой потенциал, т. к. позволяет производить обучение на данных без необходимости жесткого кодирования частей алгоритма. Однако на данный момент алгоритмы МО обладают ограниченной интерпретируемостью (например, отсутствует возможность явно указать ограничения) и требуют достаточно большого количества данных для обучения.

Кроме того, существует ряд работ, описывающих применение агентных подходов к решению задачи планирования ДЗЗ [26–28]. Процесс планирования, предложенный в работе [26], заключается во взаимодействии агентов полосы съемки и агентов КА и основывается на эвристиках из программирования в ограничениях. Приведенные авторами результаты сравнения с жадным алгоритмом, применяемым в настоящее время, показывают преимущества предлагаемого подхода. Однако производительность предлагаемого решения все еще остается недостаточной применительно к поставленной задаче. В работе [27] для распределения заказов на съемку ОН между спутниками в группировке рассматриваются механизмы рыночных аукционов. В рассматриваемой постановке задачи каждый спутник управляется отдельным центром миссии. Центры миссий координируют свое расписание, используя протоколы аукционов и предлагая цену за свободные заказы в зависимости от влияния на бортовой план и предполагаемую прибыль. В работе [28] затрагивается идея полностью автономного планирования на борту КА. Основные преимущества данного подхода предопределяются возможностями использования текущих фактических данных о состоянии КА и его ресурсов и возможностями реагирования на возникающие события в режиме реального времени. Однако, как отмечают авторы работы, с точки зрения практического реализации для создания полноценной мультиагентной системы из КА на орбите необходимо решить еще большое количество проблем, таких, например, как преодоление ограничений вычислительных возможностей бортовой аппаратуры КА, а также построение устойчивой коммуникационной системы из нескольких КА.

Рассмотренная ранее сложность и динамика рынка космических услуг в области ДЗЗ приводит к тому, что традиционные, централизованные, иерархические и последовательные методы, основанные на эвристических алгоритмах, не позволяют эффективно решить проблему адаптивного юбер-подобного управления ресурсами крупномасштабных РС ДЗЗ с приемлемым качеством и в требуемые сроки. В числе применяемых методов начинают появляться методы и алгоритмы на основе искусственного интеллекта и агентного подхода, связанные с учетом семантики предметной области, разбором конфликтов, недерминированным поведением, самоорганизацией, адаптацией, работой в реальном времени. Однако, как отмечается в [28, 29], данные направления исследований еще недостаточно глубоко проработаны и отсутствуют целостные решения проблемы, пригодные для практической цифровой реализации.

3.     Онтологическая модель данных ДЗЗ

В ходе разработки был проведен системный анализ и построена базовая онтология предметной области ДЗЗ, которая на текущем этапе была запрограммирована для повышения эффективности вычислений.

В разработанной онтологии используется модель данных, структура которой в виде диаграммы классов в нотации UML представлена на рис. 2.

Класс Resource описывает некоторый абстрактный ресурс, время использования которого необходимо запланировать. В качестве ресурсов выступают МКА (Satellite) и НС (GroundStation). Для ресурса могут быть заданы ограничения в виде графиков работы (Calendar) и интервалов недоступности (AvailabilityConstraint).

Класс ObjectForShooting представляет собой абстрактный объект наблюдения, съемку которого необходимо провести. Точечному ОН соответствует класс PointObjectForShooting, а площадному ОН – AreaObjectForShooting. Для каждого ОН создается ОС (ShootingArea).

Рис. 2. Модель данных

Класс Task представляет собой задачу, выполнение которой необходимо запланировать. Задача на съемку площадного объекта (AreaTask) представляет собой совокупность задач на съемку точечных объектов (PointTask).

Для каждой задачи на съемку точечного объекта формируются варианты размещения (ShootingWorkOption), которые представляют собой сочетание видимости МКА-ОН (SatelliteOSVisible) и видимости КА-НС (SatelliteGSVisible), а также значение ЦФ (1). В процессе планирования для задачи выбирается один из вариантов размещения, на базе которого создается работа по съемке (ShootingWork). Работа по съемке состоит из трех операций (Operation): съемка, сброс и прием данных. Для хранения всех запланированных работ по съемке используется расписание (Schedule).

Предполагается, что указанные понятия и связывающие их отношения в дальнейшем будут реализованы в онтологии ДЗЗ, открытой для редактирования (расширения) пользователями.

4.     Метод адаптивного планирования

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

Предлагаемый процесс планирования заявок на съемку ОН, поступающих в платформу, состоит из следующих основных шагов (рис. 3):

1. Фильтрация заявок.
2. Матчинг (поиск соответствия) подходящих к каждой заявке МКА.
3. Разделение площадного ОН.
4. Расчет видимостей между МКА и ОН из заявки на указанном горизонте.
5. Формирование вариантов возможного размещения.
6. Бесконфликтное планирование.
7. Проактивное планирование (самоулучшение планов).

Рис. 3. Схема процесса планирования заявок на съемку в системе. Входные данные выделены зеленым цветом, методы обработки – синим, выходные данные – оранжевым

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

4.1. Метод расчета вариантов возможного размещения

На следующем этапе для каждой задачи выполняется расчет вариантов возможного размещения, реализованный на базе метода последовательных уступок между критериями оперативности и качества получаемой информации, задаваемых коэффициентом $c_p$. В качестве главного критерия выбран критерий оперативности, а исходя из формулы (1) граничное время для сброса результатов съемки x рассчитывается по формуле:

$x=\frac{1}{c_p}\left(t_p^{end}-t_p^{start}\right)\times \left(1-\frac{\min R_p-r_p}{\min R_p-\max R_p}\right)\times \left(1-c_p\right)+t_p^{dropEnd}$.

Псевдокод метода расчета вариантов возможного размещения задачи представлен на рис. 4.

Рис. 4. Псевдокод метода расчета вариантов возможного размещения задачи

Рассмотрим подробнее работу данного метода. На вход метода поступает задача task_j, для которой необходимо осуществить расчет вариантов возможного размещения, и область съемки sa_j, соответствующая данной задаче, а также предварительно рассчитанные видимости МКА-ОН SOSV_j и МКА-НС SGSV. В начале работы метода выполняется сортировка видимостей МКА-ОН SOSV_j и МКА-НС SGSV по возрастанию времени начала соответствующего интервала (строки 1–2). Граничное время для сброса результатов съемки x принимается равным времени окончания планирования задачи task_j.endTime (строка 3). Далее выполняется последовательный перебор видимостей МКА-НС SGSV до тех пор, пока время начала очередной видимости sgsvk.startTime не превысит текущее граничное значение времени x (строки 6–20). На каждой итерации выполняется комбинация видимости МКА-НС sgsv_k и предшествующих ей видимостей МКА-ОН SOSV_j с последующим формированием на основе пары sgsv_k и sosv_p варианта размещения iwo (строки 9–14). В конце каждой итерации выполняется проверка, не превышает ли оценка новых найденных вариантов текущую лучшую оценку bestEvaluation (строка 17). Если это утверждение истинно, выполняется пересчет граничного времени для сброса результатов съемки х, а bestEvaluation принимает новое лучшее значение (строки 18–19). В ходе работы метода выстраивается последовательность вариантов возможного размещения задачи $IW{O}_j=\left\{iw{o}_l\right\}, l=\overline{\mathrm{1,}s}$, в начале которой стоит вариант размещения, расположенный в точке глобального оптимума ЦФ задачи OF_k (1).

4.2. Метод бесконфликтного планирования

На этапе бесконфликтного планирования с помощью «жадного» алгоритма оптимизации строится начальное допустимое расписание, при этом уровень качества полученного расписания не имеет значения. Цель данного этапа – формирование начального состояния для последующего этапа проактивного планирования. Идея бесконфликтного планирования состоит в том, что заявки занимают первый свободный вариант, не пытаясь сместить уже размещенные.

Метод бесконфликтного планирования состоит из следующих шагов:

1. Список заявок упорядочивается и группируется по значению приоритета $p{r}_p$.
2. Для каждой группы заявок производится попытка их планирования, в ходе которой:

2.1. Для каждой заявки последовательно перебираются варианты ее возможного размещения:

2.1.1. Для очередного варианта осуществляется поиск конкретных интервалов выполнения операций съемки и сброса в пределах указанных интервалов видимостей, для которых действуют следующие условия:

– МКА и НС не выполняют в заданные интервалы съемки и сброса другие ранее запланированные операции;

– имеется достаточный объем свободного места в бортовом запоминающем устройстве МКА на интервале времени от начала съемки ОН до окончания передачи данных на НС.

2.1.2. Если такие интервалы найдены, формируется работа по съемке ОН. В противном случае алгоритм переходит к следующему варианту размещения п. 2.1.1.

4.3. Метод проактивного планирования

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

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

$S{F}_k\left(i{w}_k\right)=1-\left(O{F}_k\left(iw{o}_k\right)-O{F}_k\left(i{w}_k\right)\right)$,

где $S{F}_k$ – функция удовлетворенности агента; $iw{o}_k$ – вариант размещения, расположенный в точке глобального оптимума ЦФ задачи; $i{w}_k$ – текущая работа по съемке ОН.

Перед началом планирования для каждой задачи создается ее программный агент. Управление ходом планирования осуществляется при помощи агента сцены, который действует в соответствии с алгоритмом 2 (его псевдокод представлен на рис. 5).

Рис. 5. Псевдокод метода проактивного планирования

Данный метод работает следующим образом. Запуск агентов на проактивность осуществляется итерационно, при этом перед началом каждой итерации выполняется проверка наличия событий изменения в исходных данных (строка 2). Если такие события имеются, выполняется обновление контекста планирования путем применения пришедших событий к текущим исходным данным (строка 3). Затем полученный на вход перечень всех агентов задач taskAgents помещается в очередь, отсортированную по возрастанию значения функции удовлетворенности агентов (строки 4–5). Агенты задач последовательно извлекаются из очереди (строка 9), и если агент не полностью удовлетворен своим текущим положением в расписании (срока 10), то ему отправляется сигнал о начале проактивности (строка 11). Протокол переговоров агентов в ходе проактивного планирования представлен на рис. 6. После получения сообщения с результатами проактивности, если проактивность завершилась удачно, выполняется пересчет оценок всех задач, затронутых данной проактивностью, и обновление порядка задач в очереди (строки 12–14). Условием завершения проактивного планирования является отсутствие перестановок агентов задач на очередной итерации планирования, это означает достижение точки равновесия при переговорах и возможность выдачи готового решения (строка 15).

Рис. 6. Протокол переговоров агентов входе поиска нового варианта размещения на этапе проактивного планирования

При получении сигнала о начале проактивности агент задачи выполняет попытку найти более выгодный для него вариант размещения по алгоритму 3 (рис. 7). В ходе проактивности агент задачи последовательно перебирает возможные варианты размещения лучше текущего, на котором запланирован (строки 2–16). На каждой итерации поиска он вначале рассчитывает максимально возможную компенсацию за перемещение compensation, которую сможет предоставить конфликтующим с ним за размещение агентам задач (строка 4). Затем выполняется поиск конфликтов по размещению (строка 6), и если таковые имеются, выполняется попытка их разрешить, используя вычисленную компенсацию (строки 7–12). При этом каждому агенту конфликтующей задачи последовательно отправляется сообщение с просьбой найти другие интервалы размещения (строка 10). Тот, в свою очередь, при получении данного сообщения выполняет попытку найти для себя новый вариант размещения, используя представленную компенсацию по алгоритму 3. Если попытка разрешения конфликта завершилась успешно и агент конфликтующей задачи готов к перемещению, из общей компенсации compensation вычитается компенсация, требуемая данным агентом, конфликт помечается как разрешенный и удаляется из общего перечня конфликтов (строки 11–13). В противном случае выполняется переход к следующему возможному варианту размещения. После того как все конфликты разрешены, на основе данного варианта размещения создается работа по съемке и добавляется в расписание вместо предыдущей (строки 14–16).

Рис. 7. Псевдокод метода проактивности агента задачи

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

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

5.     Прототип сервиса планирования цифровой платформы для решения задач управления РС ДЗЗ

5.1. Функциональные возможности прототипа сервиса платформы

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

Прототип обеспечивает следующие основные функции:

– загрузка исходных данных о составе и параметрах элементов РС ДЗЗ;

– загрузка заявок на съемку точечных и площадных ОН;

– составление локально-оптимального плана работы РС ДЗЗ (группировки МКА и НС) при заданном составе технических характеристик;

– адаптивное перестроение локально-оптимального плана работы РС ДЗЗ по событиям, изменяющим характеристики системы (состав МКА и НС, технических характеристик систем МКА и НС, добавление ограничений работы МКА и НС, изменение критериев планирования), а так же исходные данные по съемке точечных и площадных районов;

– визуальное моделирование процесса выполнения заявок ДЗЗ, приема и передачи данных на наземные станции;

– формирование графиков и диаграмм, отображающих результаты планирования;

– выгрузка полученного локально-оптимального плана работы РС ДЗЗ.

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

5.2. Архитектура прототипа

Разработанный прототип сервиса планирования целевого применения РС ДЗЗ имеет сетевую клиент-серверную архитектуру (рис. 8). Серверная часть системы написана на языке Java с применением фреймворка Spring [30]. Пользовательский интерфейс системы представляет собой одностраничное веб-приложение, написанное на языке JavaScript с применением фреймворка Vue.js [31]. Он позволяет получить удаленный доступ к ресурсам системы с любого устройства, обладающего связью с Интернет и допускающего использование браузера (ПК, ноутбуки, планшеты, мобильные телефоны). В качестве системы управления базами данных используется открытая кросс-платформенная СУБД PostgresSQL с расширением PostGIS [32] для хранения геопространственных данных.

Рис. 8. Архитектура прототипа сервиса планирования

Автоматизированное рабочее место (АРМ) оператора информационного центра представляет собой интерфейс пользователя, через который осуществляется ввод заявок, управление ходом планирования, мониторинг ресурсов, просмотр отчетов и результатов планирования.

База данных обеспечивает долгосрочное хранение исходных данных и результатов планирования.

Модуль управления взаимодействием обеспечивает маршрутизацию и преобразование информационных потоков между системой и внешней средой.

Модуль учетной системы предназначен для взаимодействия других частей системы с сервером базы данных. Включает в свой состав сервис обработки запросов на чтение и изменение данных, целью которого является осуществление запросов к реляционной БД посредством ORM (Object-Relational Mapping), а также сервис предоставления данных планировщику, предназначенный для преобразования и предоставления данных, хранимых в БД, в формат данных, понятный планировщику. Кроме того, сервис предоставления данных планировщику отслеживает изменения в исходных данных по запросу модуля планирования.

Модуль планирования предназначен для адаптивного построения расписания и его перестроения при внешних изменениях исходных данных. В состав модуля планирования, реализуемого на основе мультиагентной технологии, входят следующие основные элементы:

– адаптивный планировщик, включающий в свой состав хранилище агентов – модуль системы, аккумулирующий созданных агентов, и метод планирования – набор алгоритмов, отвечающих за управление ходом планирования и поведение агентов в зависимости от текущего контекста;

– сервис обработки событий, отвечающий за взаимодействие планировщика с остальными частями системы посредством выполнения соответствующих действий в ответ на возникающие внешние и внутренние события;

– сервис расчета вариантов размещения, обеспечивающий генерацию пространства возможных вариантов поиска по запросу планировщика. В ходе выполнения расчетов он обращается к модулю баллистики для получения циклограмм видимостей МКА-ОН и МКА-НС.

Текущее расписание представляет собой объектную структуру, содержащую исходные данные для планирования и назначения определенных ресурсов на заявки, полученные в ходе планирования.

5.3. Пользовательский интерфейс прототипа

Пользовательский интерфейс системы представляет собой одностраничное веб-приложение. На рис. 9 представлен один из экранов с данными для планирования – экран НС. В системе присутствуют аналогичные экраны для МКА, заявок на съемку ОН, календарей и ограничений доступности ресурсов. Данные для планирования можно добавлять, изменять, удалять, при этом будет производиться динамическое перестроение расписания с учетом возникших изменений.

Рис. 9. Экран с данными для планирования

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

Рис. 10. Экран с результатами планирования

На рис. 11 представлен экран с физической моделью мира, в котором функционирует КС: трехмерная модель Земли, орбиты МКА, расположение ОН и НС. При этом моделируются процессы проведения съемки и передачи ее результатов. В нижней части экрана находится временная шкала, на которой отображается очередь ближайших запланированных операций, и виджет управления модельным временем.

Рис. 11. Экран с физической моделью мира

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

– графики с историей изменения значения текущей и предельной целевой функции системы с момента начала планирования, при помощи которых можно оценить, насколько текущее значение ЦФ системы отличается от ее максимально возможного значения;

– столбчатую диаграмму распределения числа вариантов размещения лучше текущего, на которой запланирована задача, позволяющую проанализировать текущее положение задачи в расписании относительно всех возможных;

– столбчатую диаграмму распределения числа перестановок задач на каждой итерации планирования, при помощи которой можно проанализировать сходимость алгоритма планирования;

– столбчатую диаграмму распределения общего числа перестановок задачи в ходе планирования, позволяющую проанализировать, насколько активно менялось расписание в ходе планирования;

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

6.     Экспериментальные исследования

Для проведения экспериментальных исследований и оценки степени пригодности разработанной системы к решению задачи управления группировками МКА в реальном времени использовалась модель РС ДЗЗ, в состав космического комплекса которой входит группировка из 30 идентичных МКА; наземный комплекс системы представлен сетью из 10 НС. Моделировался случайный поток заявок на съемку объектов ДЗЗ, и результаты планирования подвергались автоматизированной обработке с участием экспертов.

Эксперименты проводились на ПК с ЦП Intel Core i7-3770 (4 ядра/8 потоков, 3.4 ГГц) и ОЗУ 8 Гб, под управлением операционной системы Windows 10.

Рис. 12. Экран с аналитической информацией

6.1. Исследование адаптивности получаемого в прототипе расписания работы РС ДЗЗ

В данном исследовании оценивалась способность метода к адаптации расписания по «разрушающим» событиям, в частности по выходу из строя одного из МКА.

В качестве исследуемого параметра здесь рассматривалось время, затраченное на перепланирование, и качество полученного расписания. Для этого была проведена серия из 10 экспериментов, в ходе которых вначале планировалось выполнение 3000 заявок на съемку ОН, сгенерированных случайным образом по равномерному закону распределения в диапазоне от -70° до 70° по широте и от ‑180° до 180° по долготе. Модель РС ДЗЗ в данном эксперименте была представлена космическим комплексом «Конопус-В» корпорации ВНИИЭМ, состоящим из 5 КА («Канопус-В» № 1, № 3, № 4, № 5, № 6) [33], и сетью из 10 НС. После того как все заявки были успешно размешены в расписании, из системы исключался один из МКА и измерялись время, затраченное на перестроение расписания, изменения значения ЦФ системы и количества запланированных заявок.

Результаты экспериментов представлены в таблице.

Результаты экспериментов по исследованию способности системы к адаптации расписания

Из результатов эксперимента видно, что выход из строя одного из МКА привел к резкому падению значения ЦФ системы в среднем на 0,1 и необходимости поиска новых вариантов размещения для 450 заявок. В ходе перестроения расписания на другие МКА было перепланировано 443 заявки, что составляет 98 % от числа заявок, которые были запланированы на удаленный МКА. В результате восстановления расписания значение ЦФ повысилось до 0,69, что меньше исходного всего на 0,04. Среднее время перепланирования при этом составило около 11 секунд. Таким образом, применение мультиагентного подхода при планировании позволяет оперативно, гибко и эффективно парировать возникновение внешних событий, приводящих к изменению условий решаемой задачи.

6.2. Анализ эффективности в сравнении с алгоритмами планирования, основанными на традиционных методах оптимизации

В данном исследовании проводился анализ эффективности разработанного метода в сравнении с алгоритмами планирования, основанными на традиционных методах оптимизации, таких как алгоритм имитации отжига, алгоритм Late Acceptance Hill Climbing (LAHC) и алгоритм Tabu Search, по качеству полученного расписания и временным затратам, необходимым на его составление. Приведенные алгоритмы оптимизации реализованы в открытом Java-фреймворке для планирования Optaplaner [34].

В ходе исследования проведена серия экспериментов, в которых моделировался случайный поток заявок на съемку объектов ДЗЗ. Количество заявок на съемку ОН изменялось от 100 до 20 000. Горизонт планирования в зависимости от числа заявок варьировался от 1 до 14 дней. При этом измерялось время, затраченное на составление плана, и значение ЦФ системы.

По результатам проведенных экспериментов построены графики зависимости значения ЦФ системы и времени планирования от количества заявок для различных алгоритмов планирования (рис. 13).

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

Рис. 13. Графики зависимости значения ЦФ (а) и времени планирования (б) от количества заявок

Заключение

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

Проведенные экспериментальные исследования продемонстрировали соответствие предлагаемого подхода требованиям, предъявляемым к методам и средствам планирования работы РС ДЗЗ. Так, общее время составления плана съемки для 20 тыс. объектов наблюдения составило порядка 3 часов, а время восстановления расписания, поврежденного выходом из строя одного из МКА, – менее 1 минуты.

Направления дальнейшего развития системы связаны с разработкой распределенного метода адаптивного планирования, позволяющего производить расчеты в вычислительных кластерах, а в перспективе – автономное планирование на борту МКА. Предполагается также введение онтологии с целью обеспечения более гибкой настройки применяемых правил построения расписания как в ЦУП на Земле, так и на борту МКА.

Предлагаемые методы и средства позволят перейти от прототипа к реальной системе управления крупномасштабными распределенными системами ДЗЗ, что может быть использовано, например, в рамках проектах «Сфера» Роскосмоса.

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

About the authors

Vladimir A. Galuzin

Author for correspondence.
Email: vladimir.galuzin@gmail.com
ORCID iD: 0000-0002-1460-613X

Junior Researcher

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Fig. 1

Download (75KB)

Indexing metadata

3. Fig. 2

Download (146KB)

Indexing metadata

4. Fig. 3

Download (115KB)

Indexing metadata

5. Fig. 4

Download (204KB)

Indexing metadata

6. Fig. 5

Download (203KB)

Indexing metadata

7. Fig. 6

Download (135KB)

Indexing metadata

8. Fig. 7

Download (227KB)

Indexing metadata

9. Fig. 8

Download (220KB)

Indexing metadata

10. Fig. 9

Download (69KB)

Indexing metadata

11. Fig. 10

Download (185KB)

Indexing metadata

12. Fig. 11

Download (331KB)

Indexing metadata

13. Fig. 12

Download (139KB)

Indexing metadata

14. Fig. 13

Download (113KB)

Indexing metadata