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

Алгоритм оптимального планирования операций по ликвидации последствий пожаров и чрезвычайных ситуаций гетерогенной группой

автономных мобильных роботов

Н.Г. Топольский1, В.Я. Вилисов2

'Академия Государственной противопожарной службы МЧС России, Москва, 2 Технологический университет, Королев

Аннотация: Предложен алгоритм планирования работ в группе автономных мобильных роботов, выполняющих функции ликвидации последствий пожаров или чрезвычайных ситуаций (ЧС). Такая мультиагентная робототехническая система (МРТС) должна эффективно работать без непосредственного участия оператора, выполняющего функции лица, принимающего решения (ЛИР). Автономность работы МРТС обусловлена условиями ЧС с очагами заражения, опасного для пребывания людей. В работе предложен подход и соответствующий алгоритм построения машинообучаемой модели, решающей для МРТС задачи оптимального текущего планирования операций по ликвидации ЧС, где в качестве учителя выступает опытный ЛПР-оператор.

Ключевые слова: мобильные роботы, рабочая зона, распределение заданий, ограниченные ресурсы, задача линейного программирования, оптимальное планирование, ограничения.

Введение

В приоритетных направлениях развития науки, техники и технологий в МЧС России, определенных на перспективу до 2030 года, к числу основных отнесены, в том числе, и робототехнические системы (РТС).

По мнению Б. Гейтса [1], в наше время робототехника развивается так же стремительно, как и вычислительная техника в начале 80-х годов. Развиваются как технические средства (механика, кинематика, сенсорика и др.) на основе использования современных материалов, приводов, средств связи и телекоммуникаций, так и интеллект роботов - с применением мощных и компактных компьютеров, нейросетевых технологий, биологически инспирированных принципов построения и обучения РТС.

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

М Инженерный вестник Дона, №4 (2021) ivdon.ru/ru/magazine/arcliive/n4y2021/6961

делить на легкие (носимые операторами), средние (размером с детский автомобиль) и тяжелые (размером с танк). Отечественные РТС существуют всех трех классов. Для дальнейшего анализа приведем краткие характеристики [2] двух типичных представителей среднего класса роботов (рис. 1, табл. 1) разработки МГТУ им. Н.Э. Баумана.

а) б)

Рис. 1. Пожарные роботы среднего класса: а) МРК-27; б) МРК-46

Таблица №1

Характеристики роботов среднего класса

Наименование Размеры (ДхШхВ), см Масса, кг Макс. скор., м/с Максим. дальность, м Время автономной работы, ч

МРК-27 112х71х65 170-210 0,5 200-500 4

МРК-46М 234х114,6х132 650+100 0,5 200-2000 4

На платформе МРК-27 на гусеничном ходу с электроприводом (табл. 1) было создано несколько специализированных роботов для таких задач МЧС как: поиск, уничтожение, эвакуация взрывоопасных предметов; работа в зонах химического и радиационного заражения (экспресс-анализ проб жидкости, грунта, воздуха - имеется манипулятор для укладывания опасных предметов в спецконтейнер). Все модификации оснащены видеокамерами.

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

М Инженерный вестник Дона, №4 (2021) ivdon.ru/ru/magazine/arcliive/n4y2021/6961

Как отмечается в ряде аналитических работ [3], основными целями применения РТС при ликвидации ЧС являются:

- повышение боевых возможностей подразделений МЧС;

- снижение необходимой численности личного состава;

- снижение времени ликвидации пожаров и ЧС, человеческих потерь и ущерба.

В числе задач, которые следует решать с помощью РТС [4], следующие:

• химическая, радиационная, биологическая разведка и мониторинг зоны ЧС;

• транспортно-логистические, погрузочно-разгрузочные и монтажно-демонтажные работы в зоне ЧС средствами многостепенных манипуляторов, захватов и другого навесного сменного оборудования;

• обработка почвы, строений, машин и оборудования в зоне ЧС и др.

Среди проблем применения РТС отмечаются следующие [3]:

1. Роль человека все еще остается чрезмерно большой, что сопряжено с высокими рисками для личного состава [5].

2. Роботы имеют низкий уровень автоматизации, интеллектуализации и автономности [6].

3. Практически не используется синергетический эффект от применения групп роботов [3].

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

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

Контекстом применения машинообучаемых моделей в РТС будем считать ЧС, в которой имеется рабочая зона с очагами заражения или возгорания [6]. В качестве прототипов автономных роботов, оснащенных интеллектуальным управлением, будем иметь в виду неавтономных роботов, приведенных выше.

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

1) выявление очагов возгорания/заражения;

2) определение их параметров;

3) маркировка эпицентров и границ допустимых уровней пожароопасности / заражения;

4) определение маршрутов безопасного прохода людей в рабочей зоне;

5) мониторинг динамики изменения параметров заражения рабочей

зоны;

6) ликвидация последствий ЧС (дегазация, дезактивация, разбор завалов, проделывание проходов, сбор и локализация загрязнений, земляные и дорожные работы и др.).

В такой МРТС каждый робот является агентом со своим набором функций (реализуемых навесным оборудованием), системой коммуникации и бортовым компьютером. Координация работ в МРТС может быть организована по-разному. Существуют проекты, в состав МРТС которых входит более 3000 агентов [7], содержащих, как правило, однотипных

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

В состав МРТС входят агенты-роботы, оснащенные специализированным оборудованием различных типов. Центр супервизорного управления (ЦСУ) группой роботов формирует комплексное задание, которое затем разбивается на отдельные работы (задания), лежащие в «сфере компетенций» того или иного типа роботов. Одна из основных функций ЦСУ - оптимальное распределение работ в группе роботов.

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

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

перенастроена оператором и передана в систему управления для замены предыдущей ее версии. Эти два контура управления: модель-роботы и оператор-модель могут функционировать независимо, каждый в своем темпе.

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

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

Для оптимизации работы МРТС следует планировать в каждом сеансе для текущего состава роботов в группе свой объем выполняемых работ. По своей структуре задача планирования работ в описанных сеансах относится к задачам объемного планирования, которые сводятся к модели, структурно адекватной задаче линейного программирования (ЗЛП) [8]. Формализация задачи планирования работы МРТС может быть представлена следующим образом (рассмотрим, без потери общности, случай малой размерности).

Пусть все работы, выполняемые в рабочей зоне, укрупненно представляются двумя типами:

1. вывоз мусора из рабочей зоны. Он измеряется в «робото-поездках», количество которых за планируемый сеанс обозначим х1;

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

Каждая из планируемых работ вносит свой вклад в общий эффект по ликвидации ЧС и имеет свою полезность. Тогда общий эффект (полезность) можно представить целевой функцией (ЦФ) вида:

Ь

где с1,с2 - обобщенные весовые коэффициенты вклада в общий эффект единицы работы того или иного типа. Они и являются предметом машинного обучения по действиям опытных ЛПР-операторов (или групп экспертов).

В моделируемом варианте в состав группы входят два типа роботов: R1 (их 3 единицы) оснащен ковшом захватом и емкостью для перевозки грузов (как мусора, так и маркеров для разметки зоны); R2 (их 2 единицы) имеет манипулятор с клещами, дозиметрическое оборудование и емкость с дезактивирующим веществом. Приведенные количества типов роботов соответствуют начальному составу группы в первом сеансе, в последующих сеансах состав будет «плавающим». Каждый планируемый сеанс работы МРТС начинается при выбытии одного из роботов на заправку или при возвращении робота после заправки.

Ресурсы, лимитирующие количество планируемых работ, это оставшийся заряд аккумуляторов, для роботов каждого из типов (соответственно - а10, а20), и оставшийся объем дезактивирующего вещества - а30. Будем считать, что а10,а20 измеряются в единицах времени (хотя

можно измерять и в единицах оставшейся электроэнергии), а ресурс а3 0 - в количестве замеров.

Для выполнения каждой из работ того или иного вида требуется определенное количество ресурса каждого вида. Эту потребность обозначим как aij, где i - тип ресурса (i =1;2;3); j - вид работы j=1;2).

Тогда задача оптимального объемного планирования примет такой вид: X0рt = arg m ах х 1>Х2 L

] 2= iaijxj ^ ai0,

где - вектор оптимальных значений искомых

переменных; T - символ транспонирования.

Таким образом, решив ЗЛП (1)-(4) любым из способов [8], можно передать программу роботам для исполнения. Но в этой задаче неизвестны коэффициенты целевой функции Cj. Для их оценивания и воспользуемся предлагаемыми методами машинного обучения, обеспечивающими адаптацию этой модели планирования к целевым предпочтениям ЛПР-оператора.

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

Общая постановка задачи. Одна из взаимно преобразуемых форм ЗЛП [8] может быть представлена в следующей форме. Целевая функция:

71

L

j=i

и

= ага шах Ь(х),

хеп

где Ь - целевой показатель; Х = [х 1 х 2    хп] т - вектор переменных ЗЛП; с = [ с1 с2    сп] т - вектор коэффициентов целевой функции ЗЛП. Критерий выбора оптимального решения :

гд е П - область допустимых решений (ОДР) или допустимая область варьирования переменных .

Ограничения-неравенства задачи формируют область допустимых решений О из ограничений на текущие запасы ресурсов и ограничений неотрицательности переменных:

Ах < а0,

х > О,

здесь: - матрица спецификаций, отражающая потребности видов

работ в тех или иных ресурсах; - вектор текущих объемов

ресурсов.

Взаимосвязь параметров в ЗЛП условно представлена на схеме рис. 2, где совокупность параметров {Л , а0} отражает текущую СТПР.

Ш

(а03

Алгоритм р ешешм прямой задачи лгшепного пр огр аммир ов ашы

Ы

Рис. 2. Взаимосвязь параметров прямой ЗЛП На рис. 2 фигурными скобками показана совокупность наблюдений, т.е., например, {Л } = {Л 2,  . к } , где К - количество наблюдений (объем выборки).

Выражения (5)-(8) — это модель выбора оптимального плана распределения ресурсов между роботами. Поскольку данный вид распределения, как и многие аналогичные, относится к категории задач многокритериального выбора, то в приведенной постановке вся априорная и

текущая неопределенность целевой функции сосредоточена в векторе параметров с. Очередная новая ситуация, требующая принятия решения (СТПР) полностью определяется набором значений элементов вектора а0, т.е. уровней распределяемых ресурсов. Особенности структуры и состава МРТС находят свое отражение в матрице А, значения элементов которой неизменны на протяжении всей операции.

Критериальную неопределенность (воплощенную в значения элементов вектора с) предлагается снять за счет решения обратной ЗЛП (ОЗЛП), путем машинного обучения модели по данным опытного оператора, как «учителя» [8]. В результате такого обучения оценка вектора ЦФ с становится аппроксимацией предпочтений и опыта ЛПР-оператора (или группы экспертов).

При машинном обучении модели используются выборки данных о СТПР (вектор ), принятых и реализованных решениях (разметка выборки решений на хорошие и плохие), а также данные о системе (матрица ). Схема взаимосвязи входных и выходных параметров в ОЗЛП приведена на рис. 3.

Алгоритмы настройки. Задачу вычисления оценок коэффициентов ЦФ по размеченной выборке наблюдений можно решить разными способами [8], наиболее универсальным из которых является рекуррентный стохастический алгоритм, позволяющий пересчитывать (уточнять) вектор оценок коэффициентов целевой функции с (и соответствующей матрицы Q,

И

* Алгоритм р еш енпя о бр атноп (с,} > задачи линейного =

. пр огр аммир ов анпя

{А}

Рис. 3. Взаимосвязь параметров ОЗЛП

определяющей дисперсионные свойства этих оценок) после каждого очередного к-го наблюдения.

Каждая ]-я координата е/у /-го вектора спектра решений связана с координатой су искомого нормального вектора единичной длины (НВЕД), соответствующего ЦФ ЛПР, уравнением измерений с аддитивным шумом [8]. Спектр решений — это пучок НВЕД, соответствующих пучку гиперплоскостей ограничений (7)-(8), образующих крайнюю точку ОДР, совпадающую с точкой решения, принятого ЛПР-оператором х. Каждая координата вектора оценок обрабатывается в соответствии с рекуррентными уравнениями вида [8]:

= % + + - Ф>

= - + 1У1^'

где - элементы дисперсионной матрицы Фишера; «тильда» над

символами означает, что это оценки соответствующих переменных, полученные на текущем шаге; - начальные значения оценок, которые

обычно задают для нулевыми, а для большими (обычно достаточно

-э

бывает 10 ).

Укрупненные этапы получения оценки НВЕД ЦФ ЛПР с использованием рекуррентного алгоритма (9)-(10) включает следующие четыре этапа (рис. 4).

В блоке 1 опытный ЛПР-оператор (и/или диспетчер МРТС) в условиях полигона или на тренажере [9] выполняет все действия по планированию операций. Если его действия признаны эффективными, то эти данные формируют обучающую выборку.

В блоке 2 СТПР и решения ЛПР преобразуются в выборку векторов измерений , которая является «сырьем» для рекуррентного оценивания по формулам (9), (10) в блоке 3.

и

В блоке 4 вектор текущих оценок нормируется (приводится к единичной длине) и текущий (по к наблюдениям) вектор оценок ск реального вектора с может быть уточнен и далее по очередному решению ЛПР, а может быть (при достаточной точности аппроксимации [10]) передан для реализации в МРТС.

Рис. 4. Рекуррентный алгоритм вычисления оценок ЦФ ЗЛП по наблюдениям

за решениями, принимаемыми ЛПР Правила остановки. Как в любых последовательных процедурах, важным является вопрос о достаточной точности модели. Наиболее универсальным правилом и достаточно просто реализуемым в бортовых компьютерах роботов представляется правило [8], основанное на сходимости оценок по приращениям. Для мониторинга сходимости оценок используется длина разности текущего и предыдущего векторов оценок. Тогда мера сходимости будет иметь следующий вид:

0.5, к = 1,2,..., К.

бс = \СК + 1-С1

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

у = 0.3504Х4451

3 0.5 2 И

и

о °-4

П

И §

Ы 0.2

е

Приращ.НВЕД

оценки

Степенная СПрнращ.НВЕД опенки)

№ наблюдения

а) б)

Рис. 5. Сходимость оценок ЦФ ЛПР по приращениям НВЕД оценки В данном примере выполнена аппроксимация степенной функцией

вида:

= 0.3504/с-1,451.

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

Выводы

Дополнительные исследования [8] показали, что скорость сходимости оценок для рассматриваемого типа моделей остается высокой и при больших размерностях пространства переменных (видов работ МРТС). Во многих случаях имеется возможность ускорения настройки (или повышения точности оценок) за счет специального подбора СТПР (например, методами оптимального планирования эксперимента) или путем распараллеливания

(декомпозиции) исходной СТПР на ряд более простых средствами композиционного планирования эксперимента.

Настроенная и размещенная в МРТС модель планирования операций в зоне ЧС, в высокой степени адекватна предпочтениям опытного ЛПР-оператора. Решения, принимаемые на основе машинообученной модели в режиме супервизорного управления МРТС, будут не хуже решений «учителя» модели. В тех случаях, когда существенно изменяются параметры среды и/или предпочтения ЛПР, процедура настройки модели может быть выполнена вновь. Перезагрузка модели может выполняться в «горячем» режиме - без прекращения сеансов планирования и выполнения работ.

Предложенная форма представления, хранения и использования знаний опытного ЛПР-оператора МРТС о целях управления в ряде случаев является и более удобной для мониторинга и интерпретации принимаемых решений чем, другие варианты машинообучаемых моделей, например, искусственные нейронные сети, представляющие собой «черный ящик».

Литература

1. Yang G.Z., Bellingham J., Dupont P.E., et al. The grand challenges of Science Robotics. Science Robotics 31 Jan 2018: Vol. 3, Issue 14, eaar7650 DOI: 10.1126/scirobotics.aar7650

2. RoboTrends. URL: robotrends.ru/robopedia/klassifikaciya-robotov-po-konstrukcii.

3. Цариченко С.Г., Молчанов В.П. Проблемы развития экстремальной робототехники в рамках развития инновационной деятельности МЧС России // Экстремальная робототехника. Сб. XXIII Междунар. науч.-тех. конф. СПб: Изд. Политехника-сервис. 2012. С. 19-22.

4. Баев Д.В. Анализ состояния и применения робототехнических комплексов для проведения аварийно-спасателных работ в МЧС России //

Экстремальная робототехника // Сб. XXX-й Междунар. науч.-тех. конф. СПб:

2019. С. 148-149.

5. Тужиков Е. Н., Перевалов А. С., Рассохин М. А. Перспективы развития и применения робототехники в МЧС России // Техносферная безопасность. Вып. 2(23). 2019. С. 85-91.

6. Северов Н.В., Байков А.В. Применение робототехнических средств МЧС России для ликвидации последствий техногенных чрезвычайных ситуаций // Вестник КРСУ. 2012. Том 12, № 7. С. 134-138.

7. Genesis Celebrates Launch in China with Dazzling, World Record-breaking Drone Show Over Shanghai's Iconic Skyline. URL: prnewswire.com/news-releases/genesis-celebrates-launch-in-china-with-dazzling-world-record-breaking-drone-show-over-shanghais-iconic-skyline-301261643.

8. Вилисов В.Я. Адаптивный выбор управленческих решений. Модели исследования операций как средство хранения знаний ЛПР. Саарбрюкен (Германия): LAP LAMBERT Academic Publishing. 2011. 376 с.

9. Сидоров М.В., Сидоров В.Н. Имитационное моделирование работы трансмиссии трактора МТЗ-82 в среде Simulink // Инженерный вестник Дона,

2020, №12. URL: ivdon.ru/ru/magazine/archive/n12y2020/6709.

10. Кравченко Е.В. Решение проблемы недостоверности получаемых данных в процессе управления технологическим объектом промышленного предприятия // Инженерный вестник Дона, 2020, №12. URL: ivdon.ru/ru/magazine/archive/n12y2020/6750.

References

1. Yang G.Z., Bellingham J., Dupont P.E., et al. Science Robotics 31 Jan 2018: Vol. 3, Issue 14, eaar7650 DOI: 10.1126/scirobotics.aar7650

2. RoboTrends. URL: robotrends.ru/robopedia/klassifikaciya-robotov-po-konstrukcii.

3. Carichenko S.G., Molchanov V.P. Ekstremal'naya robototekhnika. Sb. XXIII Mezhdunar. nauch.-tekh. konf. SPb: Izd. Politekhnika-servis. 2012. pp. 19-22.

4. Baev D.V. Ekstremal'naya robototekhnika. Sb. XXX-j Mezhdunar. Nauch. tekh. konf. SPb: 2019. pp. 148-149.

5. Tuzhikov E. N., Perevalov A. S., Rassohin M. A. Tekhnosfernaya bezopasnost'. Vyp. 2(23). 2019. pp. 85-91.

6. Severov N.V., Bajkov A.V. Vestnik KRSU. 2012. Tom 12, № 7. pp. 134-138.

7. Genesis Celebrates Launch in China with Dazzling, World Record-breaking Drone Show Over Shanghai's Iconic Skyline. URL: prnewswire.com/news-releases/genesis-celebrates-launch-in-china-with-dazzling-world-record-breaking-drone-show-over-shanghais-iconic-skyline-301261643.

8. Vilisov V.YA. Adaptivnyj vybor upravlencheskih reshenij. Modeli issledovaniya operacij kak sredstvo hraneniya znanij LPR [Adaptive choice of management decisions. Operations research models as a means of storing knowledge of decision makers]. Saarbryuken (Germaniya): LAP LAMBERT Academic Publishing. 2011. 376 p.

9. Sidorov M.V., Sidorov V.N. Inzhenernyj vestnik Dona, 2020, №12. URL: ivdon.ru/ru/magazine/archive/n12y2020/6709.

10. Kravchenko E.V. Inzhenernyj vestnik Dona, 2020, №12. URL: vdon.ru/ru/magazine/archive/n12y2020/6750.