Многоагентная робототехническая система спасения при землетрясениях тема диссертации и автореферата по ВАК РФ 05.02.05, кандидат наук Чжай Мэйсинь

• Чжай Мэйсинь
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Чжай Мэйсинь

ВВЕДЕНИЕ

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

1.1. Существующие проблемы и задачи

1.1.1. Общее описание катастрофы

1.1.2. Применение агентов-роботов при проведении поисково-спасательных работ

1.1.3. Основные задачи и требования к спасению при землетрясениях

1.2. Выполнение спасательных операций с помощью многоагентной робототехнической системы

1.2.1. Существующие методы и алгоритмы поиска и обнаружения целей

1.2.2. Существующие методы и алгоритмы распределения задач

1.2.3. Структура МРТС

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

Выводы по первой главе

ГЛАВА 2. МЕТОДИКА ПЛАНИРОВАНИЯ И РЕАЛИЗАЦИИ СПАСАТЕЛЬНЫХ ОПЕРАЦИЙ

2.1. Последовательность задач, решаемых МРТС и формирование спасательной команды

2.1.1. Анализ чрезвычайной ситуации

2.1.2. Планирование процесса поисково- спасательных операций во времени

2.1.3. Формирование состава спасательной команды роботов

2.2. Структура МРТС и управляющий центр

2.2.1. Структура МРТС

2.2.2. Система обработки информации в МРТС

2.2.3. Система формирования команд в МРТС

2.2.4. Механизм координации в МРТС

2.3. Коммуникация между агентами

2.3.1. Глобальная коммуникация между агентами

2.3.2. Локальная коммуникация между агентами

Выводы по второй главе

ГЛАВА 3. ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК ПОИСКОВЫХ ОПЕРАЦИЙ МЕТОДАМИ ТЕОРИИ ВЕРОЯТНОСТЕЙ

3.1. Датчики обнаружения выживших под завалами

3.1.1. Инфракрасные излучатели

3.1.2. Акустическое и видео-частотное зондирование

3.1.3. Радиолокационное зондирование

3.1.4. Сравнение и использование различных приборов для обнаружения пострадавших

3.2. Исследование процессов поиска с использованием аппарата теории вероятности

3.2.1. Вероятностные модели поиска

3.2.2. Моделирование процессов поиска одноагентной системой

3.3. Построение групповой модели поиска

3.3.1. Группа агентов выполняет поисковую задачу без кооперирований

Выводы по третьей главе

ГЛАВА 4. РАСПРЕДЕЛЕНИЕ ЗАДАЧ В МНОГОАГЕНТНОЙ РОБОТОТЕХНИЧЕСКОЙ СИСТЕМЕ

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

4.2. Централизованное распределение в МРТС

4.2.1. Распределение задач между агентами: алгоритм роя частиц

4.2.2. Распределение задач между агентами: генетический алгоритм

4.2.3. Сравнительный анализ централизованных алгоритмов распределения задач

4.3. Децентрализованное распределение задач в МРТС

4.3.1.Распределение задач между агентами: алгоритм аукциона

4.3.2.Распределение задач между агентами: теория игр

4.3.3.Сравнительный анализ децентрализованных методов

распределения задач

Выводы по четвертой главе

ГЛАВА 5. ЭКСПЕРИМНТАЛЬНЫЕ ИССЛЕДОВАНИЯ. КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ МРТС

5.1. Моделирование МРТС в среде ROS

5.1.1.Планирование траектории в среде ROS

5.1.2. Результаты моделирования в среде ROS

5.2. Моделирование МРТС в среде V-rep

5.2.1.Алгоритмы, использующиеся в процессе моделирования в среде V-rep

5.2.2. Результаты моделирования в среде V-rep

Выводы по пятой главе

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

СПИСОК ЛИТЕРАТУРЫ

СПИСОК СОКРАЩЕНИЙ И ОБОЗНАЧЕНИЙ

МРТС - многоагентная робототехническая система; БПЛА - беспилотный летательный аппарат; БПНА - беспилотный наземный аппарат; БППА - беспилотный поверхностный аппарат; УЦ - управляющий центр; АРЧ - алгоритм роя частиц; ГА - генетический алгоритм; ROS - Robot Operating System.

ВВЕДЕНИЕ

Актуальность темы исследования

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

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

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

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

Разработки робототехнических систем спасения при землетрясениях ведутся в различных организациях Китая, России, США, Европы и Японии. Ключевыми в данном вопросе являются Шэньянский институт автоматизации Китайской академии наук (Китай), МГТУ им. Н. Э. Баумана, Институт робототехники в университете Карнеги-Меллона, Лаборатория Multi-robot Systems Lab (MSL) в Бостонском университете, Технологический институт Джорджии (Georgia Institute of Technology, COA), Центральный научно-исследовательский и опытно-конструкторский институт робототехники и технической кибернетики (ЦНИИ РТК).

Цели и задачи

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

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

2. Выбор принципа построения МРТС, формирование структуры и состава системы управления.

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

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

5. Моделирование работы МРТС с учетом взаимодействия различных групп роботов.

Методология и методы исследования

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

Научная новизна

1. Разработана методика формирования коллектива роботов, предназначенного для спасения людей при землетрясениях.

2. Предложены и реализованы этапы спасательной операции с учетом конкретных характеристик катастрофы.

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

4. Разработаны и использованы методы распределения задач в группе БПНА для оптимизации процесса спасения. В основе алгоритма глобального распределения лежит метод роя частиц, при локальном распределении используется теория игр.

Практическая значимость

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

время поиска и спасения пострадавших. Защищаемые положения

1. Методика планирования этапов спасательной операции и количественного состава групп БПЛА и БПНА, совместно выполняющих спасение пострадавших.

2. Модульный подход к построению системы управления МРТС.

3. Алгоритмы поиска пострадавших, основанные на методах теории вероятности.

4. Применение методов распределения задач в группе БПНА для оптимизации процесса спасения.

Введение диссертации (часть автореферата) на тему «Многоагентная робототехническая система спасения при землетрясениях»

Апробация работы

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

1. Международная научно-техническая конференция «Экстремальная робототехника» (Санкт-Петербург, 2-3 ноября 2017).

2. III Международная научно-практическая конференция: «Word Science» (Чехия, Карловы Вары - Россия, Москва, 28-29 сентября 2018).

3. Научная конференция для студентов, молодых ученых и аспирантов МГТУ им. Н. Э. Баумана, посвященная 105-летию академика РАН Е. П. Попова (Москва, 27-28 марта 2019).

4. Первый всероссийский семинар с международным участием «Искусственный интеллект, когнитивное моделирование и интеллектуальная робототехника» (Дубна, 13-17 мая 2019).

Публикации

Результаты диссертационной работы отражены в 8 научных статьях, 4 из которых опубликованы в изданиях из перечня ВАК РФ. Структура и объём работы

Диссертационная работа состоит из введения, пяти глав, заключения и списка

литературы. Объем работы составляет 151 печатных страниц, 78 рисунков, 29 таблиц. Библиография содержит 83 наименования.

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

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

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

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

распределить цели (обнаруженных пострадавших) между спасательными агентами для выполнения необходимых действий. В главе решается вопрос глобального и локального распределения задач между агентами. В качестве методов глобального (централизованного) распределения рассмотрены и исследованы алгоритм роя частиц (АРЧ) и генетический алгоритм (ГА), для решения задач локального (децентрализованного) распределения - алгоритм аукциона и теория игр.

Пятая глава посвящена созданию комплексной компьютерной модели в средах ROS и V-Rep, с помощью которой проведены экспериментальные исследования всех разработанных методов и алгоритмов.

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

Благодарности

Автор выражает благодарность всем преподавателям кафедры СМ-7 МГТУ им. Баумана за ценные советы, замечания и поддержку.

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

1.1. Существующие проблемы и задачи

Согласно статистике, ежегодно в мире фиксируется 5 миллионов землетрясений, но большинство из них происходит в океанах или глубоко в земной коре, либо они обладают слишком малой интенсивностью и человеком не ощущаются. Тем не менее, случаются и сильные землетрясения, которые приводят к огромным человеческим жертвам и материальным потерям. Только с конца прошлого века более 1.2 миллиона человек в мире погибли в результате землетрясений и их последствий. На Рис. 1.1 показано число жертв землетрясений с 2000 по 2015 год. В связи с этим, огромное значение приобретает организация и развертывание спасательных операций. Основными задачами таких операций являются быстрое обнаружение пострадавших и оказание им возможной помощи, чтобы свести к минимуму количество погибших и уменьшить материальный ущерб.

1.1.1. Общее описание катастрофы

Землетрясение является одним из самых опасных природных бедствий из-за его внезапности и непредсказуемости. Странами и областями, которые находятся в сейсмически опасной зоне, являются регионы Тихого и Индийского океанов на стыке тихоокеанских, азиатско-европейских и индийских тектонических пластов. Постоянной опасности подвергаются Япония, Китай, Индонезия, Таиланд, Филиппины, Бангладеш и другие азиатские страны. Кроме того, западные Соединенные Штаты также расположены в сейсмически опасном поясе. Рассмотрим несколько произошедших землетрясений и их последствия.

350 000

300 000 •

X

к

250 000 •

ю к

[-Н 200 000

О

с

о 150 000

£ к

V 100 000

50 000

298101

21357 33819 1685

231

226050

87992..............887.0.8..

6605

708

1790

21942

689 1572 756 9624

гоО° гф\фъ гФъ гФл гФъ ^

Рис. 1.1. Число погибших в результате землетрясений с 2000 по 2015 год

Сычуаньское землетрясение, произошло 12 мая 2008 года в 14:28:01.42 по Пекинскому времени в китайской провинции Сычуань. Магнитуда землетрясения составила 8 MW согласно данным Китайского сейсмологического бюро [1]. Эпицентр зафиксирован в уезде Вэньчуань в 75 км от города Чэнду, столицы провинции Сычуань, гипоцентр — на глубине 19 км. Официальные источники заявляют, что на 4 августа 2008 погибло 69 227 человек, пропало без вести около 18 тыс. человек, 288 431 человек пострадало. Общая площадь серьезно пострадавших территорий составила 10 000км2 (Рис. 1.2).

(а)

(б)

Рис. 1.2. Обстановка в эпицентре Сычуаньского землетрясения: (а) до землетрясения; (б) после землетрясения

Землетрясение в Тихом океане у восточного побережья острова Хонсю в Японии произошло 11 марта 2011 года в 14:46 по местному времени, магнитуда составляла от 9.0 до 9.1 MW. Эпицентр землетрясения был определен в 130 км к востоку от города Сендай. Гипоцентр наиболее разрушительного подземного толчка находился на глубине 32 км ниже уровня моря в Тихом океане, землетрясение вызвало сильное цунами. По состоянию на 10 июня 2015 года официальное число погибших в результате землетрясения и цунами составило 15 892 человек, 2 576 человек числятся пропавшими без вести, 6 152 человека были ранены. Тысячи спасшихся находились в местах, отрезанных от связи с миром. Общая площадь особо пострадавших территорий составила 21 068км2. На Рис. 1.3 показана обстановка до и после землетрясения в городе Сендай [2].

(а)

(б)

Рис. 1.3. Обстановка в городе Сендай: (а) до землетрясения; (б) после

землетрясения

Землетрясение с магнитудой 7,1 Mw произошло в Мексике 19 сентября 2017 года в 13:14 по местному времени (18:14 ЦГС). Его эпицентр находился на глубине 51 км в 55 км к югу от города Пуэбла-де-Сарагоса и в 120 км от Мехико. Землетрясение вызвало разрушения в штатах Пуэбла, Морелос и в агломерации Мехико. Погибли 370 человек и более 6000 получили ранения. Разрушено более 40 зданий. В ходе спасательной операции из-под обломков было спасено 57 человек. На Рис. 1.4 показана обстановка до и после землетрясения [3].

V'-

Рис. 1.4. Обстановка в Мексике до и после землетрясения

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

В Таблице 1.1 представлена последовательность спасательных мероприятий после Сычуаньского и японского землетрясений [4].

Таблица 1.1.

Спасательные операции после Сычуаньского и японского землетрясений

Место Время Сычуаньское землетрясение Японское землетрясение

Этап 1: После землетрясения 0 - 2 часа 1.Создан командный пункт 2.В пострадавшую область отправлено 6100 офицеров и солдат, местные народные ополченцы сразу начинают спасательные операции в окружающем районе. 1.Создан командный пункт 2. В зону бедствия отправлены войска самообороны - наземные, морские и воздушные. Наземные войска используют вертолеты для передачи видео из района бедствия. Морские войска используют БПЛА для сбора информации о прибрежных районах.

Этап 2: После землетрясения, 2 часа - 24 часа Офицеры, солдаты и профессиональные спасатели прибывают в зону бедствия с обученными собаками и специальным оборудованием, таким как детекторы жизни, большие погрузчики, и т.д. Офицеры, солдаты и специалисты прибывают в зону бедствия, 20 военных кораблей также отправляются в прибрежную зону.

Этап 3: От 24 часа - до окончания операции спасения Спасатели прибывают в зону бедствия с питанием и необходимыми лекарствами для пострадавших. Наземные, морские и воздушные войска совместно выполняют спасательные операции.

Результаты поисково- спасательных операций с участием войсковых подразделений Всего найдено 27000 человек, из них выживших - 3338. При выполнении первого этапа поиска найдено 70 человек, на втором этапе найдено 90 человек, на третьем этапе -120 человек

Результаты поисково- спасательных операций, выполненных специалистами (профессиональные спасатели) Всего найдено 17808 человек, из них выживших - 4514. В течение 20 дней всеми подразделениями спасено 10134 выживших.

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

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

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

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

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

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

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

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

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

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

мобильные роботы различной специализации и беспилотные летательные аппараты.

1.1.2. Применение агентов-роботов при проведении поисково-спасательных работ

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

Существует четыре типа спасательных роботов [6]: беспилотные летательные аппараты - БПЛА, беспилотные наземные аппараты - БПНА, беспилотные поверхностные аппараты - БППА и беспилотные морские или подводные аппараты - БПМА. Рассмотрим эти типы роботов подробнее.

Беспилотный летательный аппарат - это робот многоразового или условно-многоразового использования, не имеющий на борту экипажа и способный самостоятельно целенаправленно перемещаться в воздухе для выполнения различных задач в автономном режиме с помощью собственной управляющей программы или посредством дистанционного управления, осуществляемого человеком-оператором со стационарного или мобильного пункта управления. В настоящее время в качестве БПЛА используются вертолеты и дроны, такие, как квадрокоптеры или мультикоптеры, обладающие возможностями стабилизации в пространстве, способные справляться с сильным ветром и улетать на несколько километров от базовой станции. БПЛА очень полезны в операциях спасения. Они могут применяться для осмотра зон бедствия сверху, съемки и реконструкции изменений окружающей среды. Вертикальная составляющая их положения обеспечивает большой обзор, что является полезным как при поиске и спасении пострадавших, так и при транспортировке питания и медикаментов, а также для передачи информации из/в зону бедствия. Ниже представлены некоторые примеры использования БПЛА в условиях стихийных бедствий.

Современные наземные мобильные роботы способны перемещаться по

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

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

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

9 августа 2017 на северо-западе Китая, в Синьцзян-Уйгурском автономном районе произошло землетрясение магнитудой 7 на глубине около 15-35 км. Частная китайская компания DJI отправила в пострадавшую зону несколько БПЛА собственной разработки для обеспечения надежных авиационных съемок и отслеживания изменения обстановки в зоне бедствия. На Рис. 1.5 показаны БПЛА, которые участвовали в поисково-спасательной операции. Поскольку в пострадавшей зоне были повреждены волоконно-оптические кабели, базовые станции подверглись разрушению и отсутствовала связь, были использованы также привязные БПЛА (Рис. 1.5, б) которые стали воздушными базовыми станциями связи и обеспечивали непрерывный доступ в интернет и безопасную передачу данных в пределах 100 квадратных километров в течении 24 часов.

(б)

Рис. 1.5. БПЛА: (а) DJI Matrice 200 и DJI Inspire 2; (б) привязные БПЛА

В спасательных работах на японской атомной электростанции в Фукусиме в 2011 году кроме БПЛА также использовались роботы QUINCE (Рис. 1.6, а) и PackBot (Рис. 1.6, б), которые перемещались по нескольким этажам и проводили радиационные и температурные измерения, а также сделали много четких фотографий внутри здания ядерного реактора.

(а) (б)

Рис. 1.6. БПЛА: (а) QUINCE; (б) PackBot

Сатоши Тадокоро, известный в Японии ученый-исследователь, создал робот-змею (Рис. 1.7), предназначенный для ликвидации последствий аварий и способный осуществлять поиск людей в завалах. Робот обладает тепловизорным зрением и используется для разведки в условиях городских подземных коммуникаций, для проверки и наблюдения в канализации, узких тоннелях или трубах, пещерах, недоступных другим робототехническим системам. Данный робот использовался спасательной командой при ликвидации последствий аварии на автостоянке во Флориде [7].

Рис. 1.7. Наземный мобильный робот-змея

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

неструктурированной среде, например, на поверхности планет и т.д.

1.1.3. Основные задачи и требования к спасению при землетрясениях

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

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

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

1.2. Выполнение спасательных операций с помощью многоагентной робототехнической системы

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

1.2.1. Существующие методы и алгоритмы поиска и обнаружения целей

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

Существует множество алгоритмов, например, Balch и Arki [10,11], где используется метод стохастического поиска в неизвестном районе, повышающий эффективность путем распределения роботов в поисковой зоне. Но этот пассивный поисковый метод не может избежать повторений, что снижает скорость поиска. Parker [12] создал новую распределенную кооперативную многоагентную модель для повышения скорости поиска. Этот метод представляет собой полностью распределенный поиск, обладающий надежностью и отказоустойчивостью. Solanas

[13] с помощью алгоритма K-Means разделил поисковый район на несколько частей, и каждый робот выполняет задачи поиска в своей зоне. На основе сетчатой карты проходимости Moravec и Elfes [17] предложили модель клеточной декомпозиции, где поисковый район разбивается на клетки одинакового размера и формы. Gabriely и Rimon [18] выполняют задачу поиска с помощью минимального ветвящегося дерева (spanning tree), которое подразделяет рабочую зону на дискретные клетки, и робот может посетить каждую точку только один раз. Latombe и Choset [19, 20] предложили метод трапециевидного разбиения поискового района (Рис. 1.8, а), но этот метод подходит только к плоскому многоугольному пространству. Далее появился метод клеточного разбиения «бустрофедона» (Рис. 1.8, б), поскольку метод трапециевидного разложения создает выпуклые клетки. А затем Acar [21] обобщил методы [19, 20] и предложил новый способ разбиения поискового района на основе функции Морса (Morse functions), с помощью которого можно создать разные клетки путем выбора различных функций Морса. Кроме того, существует метод обследования неизвестного района роботами, движущимися строем, который имеет высокую эффективность. Однако после землетрясения окружающая среда очень сложная, коммуникация между роботами не всегда устойчивая, поэтому данный метод не является работоспособным. В работах [14-16] рассмотрено выполнение поисковой задачи через коммуникацию, кооперирование и переговоры между роботами, что повышает эффективность решения. Кроме того, рассматриваются такие методы, как нейросетевой, муравьиный, генетический [2224], а также алгоритмы на основе «рыночных» подходов [25], но они обладают высокой вычислительной сложностью и низкой устойчивостью.

Список литературы диссертационного исследования кандидат наук Чжай Мэйсинь, 2020 год

- - - - _

— — ___ А ----

Б'

100 200 300 400 500 600 700

Размер популяций а)

800 900 1000

Й £

СП g

К

о ft U

- _ _ - ^

В'

~ ~ ~ - - -

Г'

---

500 1000 1500

Число итераций

в)

2000

60

к

и I-1 й К:

о м

S § hQ я ft о ь

И н

Я й

т

ft

Щ 0

Б А

— — "** "" - " - " " - "

100 200

300 400 500 S00 700 800 900 1000

Размер популяций

40

и S

§ I20

S 2 « н IS й о ft га

о

Г В

___- - ----'

О 500 1000 1500

Число интераций

г)

2000

Рис. 4.9. Сравнительный анализ АРЧ и ГА

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

4.3. Децентрализованное распределение задач в МРТС

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

Постановка задачи. Пусть на ограниченной площадке расположено несколько

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

Формализация процесса распределения задач выглядит следующим образом. Необходимо распределить m задач. Каждый агент Ai может находиться в двух возможных состояниях: «свободен» и «занят». Он знает свои текущие координаты

и вектор Цр = ( 11, 12,..., 1™) возможностей решения каждой из m задач, где Е (0,1), у = 1, 2, ..., m. Для каждой задачи Т- известно количество агентов С-, необходимое для ее решения. Например, пусть задача, которую нужно распределить, находится в точке (2, 14), причем для выполнения этой задачи необходимо использовать 3 робота, тогда параметры задачи у будут иметь вид Т- = <(2, 14), (3)>. Каждый агент может двигаться в любом направлении с постоянной скоростью. Предполагается, что агенты не сталкиваются друг с другом. Необходимо распределить задачи между агентами, обеспечив минимизацию общих раходов.

4.3.1.Распределение задач между агентами: алгоритм аукциона

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

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

аукционер выбирает наилучшего претендента на «покупку» каждой задачи.

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

Пример

Пусть, например, десять изоморфных агентов-роботов А1, А2, ..., А10 могут выполнять любую из распределяемых задач. Координаты агентов указаны в Таблице 4.14. Локальный аукционер распределяет три задачи со следующими параметрами: Т = < (9,13), (3) >, Т2 = < (3,13), (2) >, Тз = < (8,5), (4) >, то есть, для выполнения 1 -ой задачи требуется 3 агента, для выполнения 2-ой задачи требуется 2 агента, для 3-ей задачи требуется 4 агента.

Таблица 4.14.

Матрица затрат агентов при выполнении задач

Координаты задач Начальные координаты агентов Т1, (9,13) Т2, (3,13) Тз, (8,5)

А1, (13,7) 52 136 29

А2, (8,2) 123 146 9

Аз, (9,16) 9 45 123

А4, (6,6) 58 58 5

Аз, (3,12) 37 1 74

Аб, (7,9) 20 32 17

А7, (10,19) 37 85 200

Ав, (0,8) 106 34 73

Ая, (8,7) 37 61 4

А10, (10,7) 37 85 8

Процедура аукциона является итерационной и включает последовательность шагов. См. Рис. 4.10:

Рис. 4.10. Этапы аукциона

1) Локальный аукционер сообщает данные о задачах агентам.

2) Агенты отправляют аукционеру свои данные - состояние (свободен/занят) и координаты.

3) Локальный аукционер обрабатывает данные: а) формирует матрицу затрат (Таблица 4.14), содержащую квадраты расстояний между роботами и задачами; б) сортирует задачи в порядке возрастания потребностей: Т2, Т1, Т3.

4) Локальный аукционер начинает аукцион. Поскольку для выполнения задачи Т2 достаточно двух агентов, по минимуму соответствующих затрат выбираются агенты Аз и А6, их статус становится «занят», и в дальнейшем выборе они не участвуют. Для решения задачи Т1 необходимо три агента, выбираются агенты А 3, А7и А9, их статусы меняются на «заняты». Для решения задачи Т3 требуется четыре агента, и из оставшихся «свободными» выбираются агенты А1, А2, А4 и А10 (в случае,

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

5) Локальный аукционер сообщает результаты агентам, и они начинают выполнять задачи.

Таблица 4.15.

Результат распределения задач

Задачи Потребности (число роботов) Результаты - номера роботов

Т2, (3,13) 2 А5,Аб

Т1, (9,13) 3 Аз, А7, Ад

Тз, (8,5) 4 А1, А2, А4, А10

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

4.3.2.Распределение задач между агентами: теория игр

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

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

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

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

Таким образом, распределение задач сводится к поиску равновесия Нэша. Для этого определяют все возможные ходы и их полезность. Затем избирают наиболее выгодную стратегю.

Если количество агентов-роботов равно числу задач, то игроками являются агенты. Например, 2 агента (А1,А2) должны выполнить 2 задачи (Т1, Т2), причем каждый агент будет выполнять только одну задачу. Здесь для каждого игрока имеется набор чистых стратегий: А1^ < [Т1},{Т2] > ; А2^ < [Т1},{Т2] > . Платежные матрицы - это затраты, соответствующие расстоянию между агентами и задачами (Таблица 4.16). Если два агента одновременно выполняют одну и ту же задачу, затраты оцениваются как бесконечность. При «жадной» стратегии (без кооперации) каждый агент думает только о себе, то есть, А1 ^ {Т2} , А2 ^ {Т2} и общие затраты стремятся к бесконечности. В данной ситуации целесообразно использовать кооперативную игру - каждый агент, в соответствии с равновесием Нэша, выбирает такую стратегию, при которой суммарные затраты группы роботов минимальны: А1 ^ [Т1} , А2 ^ {Т2} (Таблица 4.17).

Таблица 4.16.

Платежная матрица

Задачи Агенты Т1 Т2

А 20 12

^2 30 15

Результат перераспределения задач на основе теории игр

ai

Ä2

ti t2

ti (12, 30)

t2 (20, 15)

Пример

Исходные данные приведены в Таблице 4.14. Допустим, все агенты знают решения других агентов. У всех агентов одна цель, состоящая в уменьшении затрат. В данном примере это сумма расстояний U = Y,j=i Щ , где U - глобальная платежная функция, Uj - платежная функция выполнения задачи j. Таким образом, мы имеем игру с известной информацией. Цель игры - найти 'равновесие Нэша', то есть наименьшее из всех возможных решений U*: u*(ui, и2, и3) < U(u1, u2, u3).

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

Т = {(а1,а2,аз),(а1,а2,а4),(а1,а2,а5) ...}, Т2 = {(а1,а2),(а1,аз),(а1,а4)...},

Т3 = {(Ai, А2, А3, А4), (А1, А2, А3, аб), (А1, А2, А3, Аб) }.

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

Ui = [и1(Аз,А5,Аб),щ(А5,Аб),щ(А2 ,А4 ,А9 ,AW)} = 125.

Однако, поскольку агенты A5 и A6 одновременно могут выполнять только одну задачу, необходимо искать другие варианты. Например:

U2 = [ui(a3,a6,a7),u2(a5,aq),u3(a2 , A4 , Ag ,Aio)} = 127 U3 = {Ui(A3,A7,A10),U2(A5,Аб),U3(Ai ,A2 ,Ag ,AW)} = 166

и4 = [и1(А1,А31А7),и2(А51А6)1и3(А2 ,А4 ,Ад ,А^)} = 157 Нетрудно видеть, что вариант и2 - лучший. Следовательно, он является равновесием Нэша (Таблица 4.18). Таким образом, оптимальное распределение задач для данного примера:

и*(и*1,и*2,и*3) = [и1(А3,Аб,А7)1и2(А51А8)1и3(А2 ,Ад ,А^}.

Таблица 4.18.

Результат распределения задач на основе теории игр

Задачи Потребности (число роботов) Результаты - номера роботов

Т1, (9,13) 3 Аз, А6, А7

Т2, (3,13) 2 А5, Ав

Тз, (8,5) 4 А2, А4, Ад, А10

В следующем разделе приведен сравнительный анализ двух рассмотренных методов распределения задач в МРТС.

4.3.3.Сравнительный анализ децентрализованных методов распределения задач

Из Таблиц 4.15 и 4.18 видно, что при распределении задач среди агентов МРТС методы теории игр дают лучший результат, чем алгоритм аукциона. Применение теории игр позволяет найти оптимальное решение. При этом, по сравнению с алгоритмом аукциона, вычислительный процесс при использовании теории игр занимает значительно больше времени, особенно, когда в распределении участвует большое количество агентов и задач.

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

увеличивает временные затраты.

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

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

Выводы по четвертой главе

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

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

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

ГЛАВА 5. ЭКСПЕРИМНТАЛЬНЫЕ ИССЛЕДОВАНИЯ. КОМПЬЮТЕРНОЕ

МОДЕЛИРОВАНИЕ МРТС

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

5.1. Моделирование МРТС в среде ROS

ROS (Robot Operating System) обеспечивает разработчиков библиотеками и инструментами для создания робототехнических приложений, предлагает аппаратную абстракцию, драйверы устройств, библиотеки, визуализаторы, механизмы обмена сообщениями, менеджеры пакетов и многое другое, а также позволяет непосредственно управлять реальными роботами или агентами. Моделирование проведено в среде ROS с использованием расширения ROS Navigation Stack, которое позволяет управлять движением роботов из одной точки в другую без столкновений.

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

- распределение целей между роботами управляющим центром;

- планирование оптимальной траектории каждым роботом (обход статических и динамических препятствий и нахождение оптимального пути).

Первая задача исследована в п. 4.2. и п. 4.3 диссертации, вторая задача решена с использованием расширения ROS Navigation Stack.

5.1.1. Планирование траектории в среде ROS

ROS Navigation Stack - это библиотека алгоритмов, включающая функции локализации, навигации, планирования оптимальной траектории и т.д., с помощью которой робот может переместиться из одной точки в другую без столкновений и потерь. Эта задача решается, благодаря получению информации от одометра и дальномера. Основные этапы навигации: получение координат цели, определение положения робота с помощью системы локализации AMCL, планирование траектории, движение робота на основе информации от датчиков. На Рис. 5.1 показана структурная схема ROS Navigation Stack [80].

На Рис. 5.1 amcl (Adaptive Monte Carlo Localization Approach) - программный модуль локализации на базе адаптивного метода Монте-Карло; sensor transforms -модуль преобразования данных сенсорной системы, публикующихся с помощью

сообщения tf/tfMessage; odometry source - модуль одометрии, который публикует данные с использованием сообщения nav_msgs/Odometry; модуль move_base планирует движение робота; модуль global_planner планирует маршрут к целевой точке с помощью глобальной карты рабочей зоны; модуль local_planner выполняет планирование траектории с помощью локальной карты, корректируя глобальный маршрут в случае обнаружения препятствий; модуль global_costmap содержит обработанную глобальную карту; модуль local_costmap - это обработанная локальная карта; модуль base_controller отправляет команды управления с помощью сообщения geometry_msgs/Twist; map_server предоставляет и сохраняет данные карты через сообщение nav_msgs/getmap; Sensor Sources - информация от датчиков, которая необходима, чтобы избегать столкновений с препятствиями; датчики публикуют сообщения sensor_msgs/laserscan или sensor_msgs/PointCloud.

Локализация робота выполняется с помощью amcl (Adaptive Monte Carlo Localization Approach), которая представляет собой вероятностную систему локализации мобильных роботов, движущихся по плоской поверхности. В amcl используется фильтр частиц, который позволяет отследить положение робота на сетчатой карте. Основной целью навигационной системы мобильного робота является управление его движением в пространстве и перемещение в заданные точки. Решение данной задачи обычно разделяют на два этапа: планирование оптимальной траектории по карте и следование вдоль полученного маршрута.

Для отображения окружающей обстановки рабочей зоны используется карта. Существуют два основных типа представления карты: геометрическое и представление в виде графа. Представление в виде графа, в свою очередь, подразделяется на сетчатые карты проходимости (occupancy grid map) и топологические карты. В разработанной модели использована сетчатая карта проходимости.

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

и размер клетки карты.

На Рис. 5.2 показана карта стоимости, где красные клетки являются препятствиями. Красный многоугольник представляет собой след робота. Чтобы избежать столкновений, след робота никогда не должен пересекаться с красными клетками, а центр робота - с синими клетками. Карта стоимости обновляется в режиме реального времени. В процессе обновления добавляются или удаляются препятствия. Каждая клетка содержит целочисленное значение стоимости в интервале [0, 255], пять из них имеют специальное на значение.

На Рис. 5.3 показан график зависимости стоимости ячейки от расстояния между центром робота и ближайшей ячейкой с препятствием. Значения, записанные в клетках катры стоимости, можно интерпретировать следующим образом: 255 - не хватает информации, чтобы определить состояние клетки; 254 - обнаружение препятствия в клетке, опасность столкновения; 253 - клетка свободна, но ее размер меньше размера робота, и, если робот перемещается в такую клетку, обязательно происходит столкновение; 128-252 - клетка свободная, но столкновения может произойти или нет, в зависимости от ориентации робота; 0 - клетка свободная, центр робота может переместиться в эту клетку без столкновений. Безопасные траектории планируются с помощью специальных алгоритмов, основываясь на данных карты стоимости.

Рис. 5.2. Карта стоимости (costmap)

стоимость

Рис. 5.3. График зависимости стоимости ячейки от расстояния между центром робота и ближайшей ячейкой с препятствием В разработанной модели траектория планируется глобально и локально. Глобальное планирование - это планирование пути от начальной точки до цели по данным глобальной карты. Этот процесс происходит до начала перемещения агентов и выполняется с помощью алгоритма A*. Локальное планирование - это построение пути по опорным точкам, полученным при глобальном планировании, в зависимости от локальной карты, обновляющейся в режиме реального времени. Такой подход помогает избегать столкновений с динамическими препятствиями. Он реализован с помощью алгоритмов Trajectory Rollout и динамического окна. Рассмотрим данные алгоритмы подробнее.

Алгоритм A* осуществляет поиск кратчайшего пути на графе. Этот эвристический алгоритм сортирует все узлы по стоимости наилучшего маршрута,

идущего через этот узел. Он сочетает в себе учет длины предыдущего пути из алгоритма Дейкстры и эвристику из алгоритма «лучший-первый». Алгоритм А* гарантированно находит кратчайший путь до тех пор, пока эвристическое приближение является допустимым, т.е. никогда не превышает действительного оставшегося расстояния до цели. В отличие от других методов, этот алгоритм наилучшим образом использует эвристику, обрабатывая наименьшее число узлов. Для использования этого алгоритма необходимо отобразить карту рабочей зоны на графе. Отображение сетчатой карты является стандартным, при этом карта представляет собой восьмисвязный граф, вершины которого находятся в центре каждой ячейки, а ребрами являются переходы к соседним ячейкам. Каждая ячейка может быть «свободной», «занятой», а также обладать некоторой стоимостью перехода через нее [81].

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

Уг = У5пУапУа (5.1)

Здесь, Уг - вектор оптимальной скорости. У5 - допустимые скорости,

ограниченные

0 , и

тах

, (в зависимости от возможностей

^тах > ^тах

робота); Уа - безопасные скорости движения, которые исключают столкновение, т.е., скорости, гарантирующие своевременную остановку робота перед препятствиями; Уй - динамические ограничения, определяемые максимальными ускорениями, \а = {(и, ш)Уу Е [ус — уь • Д1,ус + уа^ Дь] Аш Е [шс — шь •

Д1,шс + ша • Д1]}, ус и шс - текущие скорости, уь , уа, шь, 6)а-возможности ускорения и замедления, зависящие от характеристик мотора робота.

Этот метод позволяет учесть динамику мобильного робота. В его основе лежит поиск экстремума функционала в динамическом окне:

Т

{и* , = агдех1г(С(у,ш)) (5.2)

Здесь С(у,ш) - критерий оптимальности, т.е. функционал, учитывающий степень совпадения траектории робота со спланированным маршрутом, а также положение

и траекторию движения препятствия. Самый распространенный критерий максимизации функционала имеет следующий вид:

в(у, ш) = а(а • кеа(опд(у, ш) + Р • (ьб^у, ш) + у • уе1осиу(у, ш)) (5.3) Здесь кеа(тд(у,ш) - функционал курса на целевую точку; в - отклонение курса между целевым и спланированным положениями (Рис. 5.4); аз1(у,ш) -функционал расстояния до ближайшего препятствия; уе1осИу(у, ш)-функционал скорости движения робота; а,@,у - весовые коэффициенты; а-нормирующий коэффициент. Кроме того, необходимо провести нормировку:

И е а (Ипд(Ь )

nomalheading(i) — nomaldist(i) —

nomalvelocity(Q —

Ef=1 h e a d ing( i ) dist(i)

dist(i) velocity(i) eY=i velocity (i)

(5.4)

Здесь, п - это количество всех проверяемых траекторий, проверяемая траектория.

цель

I - это текущая

х'Т^ч "спланированное

( \ положение

реальное положение Рис. 5.4. Отклонение курса на целевую точку

Теперь для выбора вектора управления достаточно найти такие значения скоростей, при которых достигается максимум данного критерия в области, ограниченной динамическим окном. Аналитически максимизировать данный критерий не представляется возможным. Поэтому, для практического применения метода динамического окна генерируется набор траекторий (Рис. 5.5),

для каждой из которых рассчитывается значение критерия. Отметим, что при реализации можно добавлять любые ограничения на скорости перемещения, например, на отрицательную линейную скорость, чтобы робот мог двигаться только вперед. На Рис. 5.5 красным цветом обозначена оптимальная траектория движения робота, зеленым - допустимые траектории, синим - недопустимые, которые приводят к столкновению.

(vc + va -at,wc +wa-At)

>y

6.5-

6 -

5.5 -

5 -

(uc + va ■ At, o)c + (bb ■ At)

(vc - vb ■ At, ыс - ыь - At)

4.5 -

препятствие

60 60.5 61 61.5 62 62.5

x/м

Рис. 5.5. Набор проверяемых траекторий

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

Алгоритм траектории Rollout является эффективным методом планирования локальной траектории роботов по известной карте. По сути rollout аналогичен алгоритму динамического окна. Ниже приводится его подробное описание.

Сначала отбираются образцы траекторий в пространстве управления роботом (dx, dy, dff). После этого для каждого отобранного образца проводится моделирование скорости в течение заданного времени, начиная с текущего состояния, в том числе выясняется, как будет перемещаться робот на этих скоростях и оцениваются результаты моделирования (траектории движения). В результате

удаляются образцы траекторий, приводящие к столкновению с препятствиями, и выбирается оптимальный образец. Роботу присваивается скорость, которая соответствует оптимальному образцу. Этот процесс проиллюстрирован на Рис. 5.6.

Рис. 5.6. Алгоритм траектории Rollout

Алгоритм динамического окна отличается от алгоритма траектории Rollout способом отбора образцов траекторий в пространстве управления роботом. Алгоритм траектории Rollout выбирает образцы по результатам всего процесса моделирования, руководствуясь ограничениями ускорения робота, а алгоритм динамического окна выполняет отбор образцов только на конкретном шаге моделирования. В результате алгоритм динамического окна является более эффективным, чем алгоритм траектории Rollout. Но, если заданное ограниченное ускорение очень мало, алгоритм траектории Rollout будет работать более эффективно и быстро. Все рассмотренные алгоритмы использованы в процессе моделирования.

5.1.2. Результаты моделирования в среде ROS

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

условиях наличия априорной информации о внешней среде (карты). Для реализации такой модели в режиме реального времени потребовался компьютер, оснащенный операционной системой Ubuntu14.04 с установленной средой ROS (Robot Operating System). Построенная модель показана на Рис. 5.7.

Рис. 5.7. Модель в среде ROS

Группа состоит из двух роботов, которые имеют координаты (18 32), (17 14); имеются две цели, координаты которых (10 12), (20 21). Расположение роботов и целей на карте показано на Рис. 5.8.

» © /home/zha¡me¡x¡n/catk¡n_ws/src/allocat¡on_navÍ_multi/i

/home/zhaimeixin/catkin_w... х /home/zhaimeixin/catkinw... x

send_goals (allocation_navi_nulti/send_goals) ROS_MASTER_URI=http://localhost:11311

. vVí; ХЗС?£ГО Ц

core service [/rosout] found process[send_goals-l]: started with pid

[ INFO] [1553450047.132891108]: Halting base action server

[ INFO] [1553450O47.471599772, 30,80000« ed to nove base server [ INFO] [1553450047.471816770, 30.80000« goal to robot_0: x = 10.000000, y = 12. = 0.000000

[ INFO] [1553450047.472181839, 30.80000« goal to robot_l: x = 20.000000, y = 21,

[20080]

for the move

00O]: Sending 000000, theta

ООО]: Sending 000000, theta

. Г"' г, й—в—°

'Us ;

■ И

fLSS-« V_____1

-40 -36 -32 -20 -24 -20 -16 -12

_12__га_2i_2fi_32_i3S_Ш_M_4fi_52_

Рис. 5.8. Расположение роботов и целей на карте

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

Рис. 5.9. Глобальное планирование траектории

Роботы начинают перемещаться, при этом включается локальное планирование, позволяющее избегать столкновений с препятствиями. Этот процесс показан на Рис. 5.10.

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

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

Структурная схема модели МРТС в среде ROS показана на Рис. 5.11. Модель внешней среды разработана в симуляторе Stage. Процесс моделирования спасательной операции строится следующим образом (Рис. 5.12 красные блоки -целевые точки, черные блоки - новые целевые точки, остальные маленькие блоки - роботы): несколько мобильных роботов готовы к выполнению задач спасения; управляющий центр распределяет задачи между агентами (алгоритм роя частиц и ГА); агенты начинают выполнять свои задачи, осуществляется планирование траекторий их движения к целям; когда связь с УЦ потеряна, агенты распределяют задачи между собой с помощью переговоров (теория игр).

Рис. 5.11. Структурная схема модели МРТС в среде ROS

Рис. 5.12. Процесс моделирование в ROS/Stage

Условия моделирования: N =10 роботов вместе выполняют М задач. В связи с непрерывностью процесса обнаружения и спасения постоянно находятся новые цели. Пусть первый раз нужно выполнить М=7 задач, второй раз М=4 задачи (новые целевые точки). В процессе моделирования два робота теряют связь с управляющими центром и не могут выполнить свои задачи, тогда необходимо распределить задачи между другими роботами (локальное распределение).

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

Таблица 5.1.

Результаты моделирования в среде ROS

Метод Время выполнения задач (сек) Затраты

Алгоритм роя частиц 30 563

Генетический алгоритм 42 1144

Замечание: время выполнения задач - общее время, которое затрачено на выполнение всех задач; затраты - сумма квадратов перемещений всех роботов. Из Таблицы 5.1 видно, что алгоритм роя частиц дает лучшее решение. Проведенное моделирование подтверждает вывод, полученный в четвертой главе.

5.2. Моделирование МРТС в среде У-гер

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

5.2.1. Алгоритмы, использующиеся в процессе моделирования в среде V-rep

Планирование траектории и объезд препятствий решено моделировать с помощью содержащейся в V-rep модели робота Pioneer p3dx (Рис. 5.13, а). Данный робот оснащен шестнадцатью ультразвуковыми датчиками, расположенными по его периметру (Рис. 5.13, б).

(а) (б)

Рис. 5.13. Модель робота Pioneer p3dx

В процессе моделирования строятся траектории движения агентов в целевую точку с учетом объезда препятствий. Маршруты планируются в режиме реального времени с помощью алгоритма Брайтенберга [82]. Основная идея данного алгоритма заключается в том, что при обнаружении датчиком препятствия увеличивается угловая скорость двигателя колеса со стороны соответствующего датчика, при этом уменьшается угловая скорость двигателя колеса на противоположной стороне робота. Таким образом, при наличии препятствия алгоритм обеспечивает разные скорости двигателей колес, что приводит к повороту агента-робота. В зависимости от параметров активации датчиков препятствия, агент либо поворачивается, либо вращается на месте. Управляющие сигналы для левого и правого колес робота определяются по формулам:

Мг = £=6 + (5.5)

Мг = + ^ (5.6)

Здесь параметр ^ обозначает активацию датчика ¡, которой является функция расстояния между ¡-м датчиком и препятствием; ^ - параметр связи /-го датчика с левым колесом; ш10 - это идеальная активация левого колеса. Аналогично

V г

определяются параметры правого колеса: .

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

5.2.2. Результаты моделирования в среде У-гер

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

построенной модели приведены в Приложении А.

*

Рис. 5.14. Модель спасательной команды в приложении У-гер

Результаты моделирования показаны на Рисунках 5.15 - 4.19. Из Рис. 5.15 видно,

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

Рис. 5.15. Результат моделирования в приложении У-гер

На Рис. 5.16 - 5.19 приведены траектории движения, а также графики координат, угловой и линейной скоростей агентов.

Рис. 5.16. Траектории агентов в процессе моделирования

Рис. 5.17. Координаты агентов в процессе моделирования

Рис. 5.18. Линейные скорости агентов в процессе моделирования

Рис. 5.19. Угловые скорости агентов в процессе моделирования

Достигнув своей цели, агенты остановились и их координаты постоянны, что видно из Рис. 5.16 и 5.17. Если датчики не обнаруживают препятствий и агенты едут к цели, линейные скорости агентов постоянны, угловые скорости агентов тоже не изменяются (Рис. 5.18 и 5.19). Когда линейные и угловые скорости резко изменяются, агенты обходят препятствия.

Проведенные исследования доказали работоспособность и эффективность алгоритма локального планирования траектории.

По результатам моделирования в средах ROS и V-rep сделаны следующие выводы:

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

- обе модели обладают эффективностью, надежностью и устойчивостью;

- моделирование в V-rep более простое и позволяет легко регулировать, а также непосредственно наблюдать динамические характеристики агентов, такие как скорость движения, ускорение и т.д.;

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

Выводы по пятой главе

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

В разделах 5.1 и 5.2 приведены результаты экспериментальных исследований алгоритмов распределения целей и планирования траекторий. Выполнено компьютерное моделирование с помощью сред V-rep и ROS, которое доказало работоспособность и эффективность предположенных методов и алгоритмов.

Кроме того, по результатам проведенного моделирования сделаны следующие

выводы:

- среда V-rep является более пригодной для моделирования динамических характеристик роботов;

- среда ROS является предпочтительной для управления реальными роботами.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

В ходе работы над диссертацией были получены следующие основные

результаты:

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

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

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

4. При локальном децентрализованном распределении задач для получения оптимального решения целесообразно использовать теорию игр. При большом количестве задач (больше 5) предлагается применять алгоритм аукциона.

5. Проведено компьютерное моделирование в средах ROS и V-rep, подтвердившие эффективность предложенных методов и алгоритмов, а также проведено имитационное моделирование процесса обнаружения и спасения при землетрясениях.

СПИСОК ЛИТЕРАТУРЫ

1. Liu Huijun, Chen Qian, Wen Changli. The research of geological disasters in wenchuan county before and after the '5.12' earthquake // Journal of Geological Hazards and Environment Preservation. 2009. Vol. 20(2). P. 112-115. (in Chinese)

2. Satellite photos of japan, Before and after the quake and tsunami // URL: http://www.nytimes.com/interactive/2011/03/13/world/asia/satellite-photos-iapan-before-and-after-tsunami.html?mcubz=0 (date of the application 13.04.2018)

3. Землетрясение в Пуэбле (2017) // URL: https://ru.wikipedia.org/wiki/Землетрясение в Пуэбле (2017) (дата обращения: 15.02.2018).

4. Xu Jianhua, Luo Ling, Li Jianhua. Comparison of rescue operation of wenchuan earthquake and east japan earthquake // China Emergency Rescue. 2014. Vol. 5. P. 35-38. (in Chinese)

5. European center on prevention and forecasting of earthquakes (ECPFE) and the earthquake planning and protection organization of Greece (EPPO) // Search & Rescue Operations in Earthquakes. 2nd ed. Athens. 1999. 48р.

6. Yogesh V. B. An overview on search and rescue robots during earthquake and natural calamities // IJISET - International Journal of Innovative Science, Engineering & Technology. Vol. 2(5). May 2015. P. 2037-2040.

7. Drone & Robot // URL: http://www.pcpop.com/article/1504612.shtml (дата обращения: 25.05.2018).

8. Багницкий А.В., Инзарцев А.В. Планирование и реализация траекторий движения автономного подводного робота при выполнении мониторинга в акваториях различных типов // Подводные исследования и робототехника. 2016. № 2(22). C. 25-35.

9. Thersa Marie Driscoll. Complete coverage path planning in an agricultural environment // Graduate theses and dissertations. Iowa State University. 2011. 63р.

10. Mac Kenzie D., Balch T. Making a clean sweep: behavior based vacuuming // In

AAAI Fall Symposium, Instationating Real-World Agents. 1996. P. 93-98.

11. Arkin R.C., Balch T., Nitz E. Communication of behavioral state in multi-agent retrieval tasks // Proc. 1003 IEEE International Conference on Robotics and Automation. Atlanta. GA. 1993. Vol. 1. P. 588-594.

12. Parker L.E. ALLIANCE: An architecture for fault-tolerant multi-robot cooperation // IEEE Transactions on Robotics and Automation. 1998. Vol. 14(2). P. 220-240.

13. Solanas A., Garcia M.A. Coordinated multi-robot exploration through unsupervised clustering of unknown space // In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Sendai. Japan. 2004. P. 717-721.

14. Correll N., Martinoli A. Robust distributed coverage using a swarm of miniature robots // In Proceedings of IEEE International Conference on Robotics and Automation. Roma. Italy. 2007. P. 379-384.

15. ZHANG Fei, CHEN Weidong, XI Yugeng. Improved market-based approach to collaborative multi-robot exploration // Control and Decision. 2005. Vol. 20(5). P. 516-520. (in Chinese)

16. Haxon N., Kaminka G.A. Redundancy efficiency and robustness in multi-robot coverage // In Proceedings of the IEEE International Conference on Robotics and Automation. 2005. P. 747-753.

17. Moravec H.P., Elfes A. High resolution maps from wide angle sonar // In Proceedings of the IEEE International Conference on Robotics and Automation. St. Louis. 1985. P. 116-121.

18. Gabriely Y., Rimon E. Spanning-tree based coverage of continuous areas by a mobile robot // Annals of Mathematics and Artificial Intelligence. 2001. Vol. 31(4). P. 77-98.

19. Choset H., Lynch K., Hutchinson S., Kantor G., Burgard W., Kavraki L. and Thrun S. Principles of robot motion: Theory algorithms and implementation. The MIT Press. 2007. 597p.

20. Latombe J. C. Robot motion planning. Kluwer Academic Publishers. 1991. P. 643.

21. Acar E. U., Choset H., Rizzi A. A., Atkar P. N., Hull D. Morse decomposions for coverage tasks // International Journal of Robotics Research. 2002. Vol. 21(4). P.

331-344.

22. Luo C., Yang S. A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environments // Neural Networks IEEE Transactions. 2008. Vol. 19(7). P. 1279-1298.

23. Wagner I. A., Bruckstein A.M. Efficiently searching a graph by a smell-oriented vertex process // Annals of Mathematics and Artificial Intelligence. 1998. Vol. 24(1). P. 211-223.

24. Jimenez P. A., Shirinzadeh B., Nicholson A., Alici G. Optimal area covering using genetic algorithms // Proceedings of IEEE/ASME International Conference on Advanced Intelligent Mechatronics. Zurich. Switzerland. 2007. P. 1-5.

25. Xiong L. H., Guo S. L. Trend test and change-point detection of the annual discharge series of the Yangtze River at the Yichang hydro logical station // Hydrological Sciences. 2004. Vol. 49(1). P. 99-112. (in Chinese)

26. James R. Riehl, Gaemus E. Collins, Joao P. Hespanha. Cooperative search by UAV Teams: A Model Predictive Approach using Dynamic Graphs // IEEE Transactions on aerospace and electronic systems. 2011. Vol. 47(4). P. 2637-2656.

27. John T., Allison R., Zu K., David T., J. Karl Hedrick. A multiple UAV system for vision-based search and localization // In Proceedings of the American Control Conference. 2008. P. 1985-1990.

28. F. Bourgault, T. Furukawa, H.F. Durrant-Whyte. Decentralized bayesian negotiation for cooperative search // 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Sendai. 2004. P. 2681-2686.

29. Frederic Bourgault, Tomonari Furukawa, Hugh F. Coordinated decentralized search for a lost target in a bayesian world // International Conference on Intelligent Robots and Systems. Las Vegas. Nevada. 2003. P. 48-53.

30. Yun Zhong, Peiyang Yao, Yu Sun, Juan Yang. Method of Multi-UAVs cooperative search for Markov moving targets // 29th Chinese Control and Decision Conference (CCDC). 2017. P. 6783-6789.

31. M. Mirzaei, F. Sharifi, B. W. Gordon, C. A. Rabbath, Y M. Zhang. Cooperative Multi-Vehicle search and coverage problem in uncertain environments // IEEE

Conference on Decision and Control and European Control Conference (CDC-ECC). Orlando. FL. USA. 2011. P. 4140-4145.

32. R.P.S. Mahler. Multitarget Bayes filtering via first-order multitarget moments // In IEEE Transactions on Aerospace and Electronic Systems. 2003. Vol. 39(4). P. 11521178.

33. Yoonchang Sung, PratapTokekar. Algorithm for searching and tracking an unknown and varying number of mobile targets using a limited FoV sensor // IEEE International Conference on Robotics and Automation (ICRA). Singapore. 2017. P. 6246-6252.

34. Yang Y, Minai A. A., Polycarpou M. Decentralized cooperative search in UAV's using opportunistic learning // In AIAA Guidance, Navigation, and Control Conference and Exhibit. Monterey. California. 2002. P. 1-10.

35. Инзарцев А.В., Багницкий А.В. Планирование и реализация траекторий движения автономного подводного робота при выполнении мониторинга в акваториях различных типов // Подводные Исследования и Робототехника. 2016. Т. 22, № 2. С. 25-35.

36. Shehory O., Kraus S. Methods for task allocation via agent coalition formation // Artificial Intelligence. 1998. P. 165-200.

37. Юревич И.Е. Интеллектуальные роботы // Машиностроение. 2007. 360с.

38. Tang Suyuan, ZHU Yifan, LI Qun, LEI Yonglin. Survey of task allocation multi agents systems // Systems Engineering and Electronics. 2010. Vol. 32(10). P. 21552161. (in Chinese)

39. Berman S., Halasz A., Hsieh M. A., Kumar V. Optimized stochastic policies for task allocation in swarms of robots // IEEE Transactions on Robotics. 2009. Vol. 25(4). P. 927-937.

40. Meng Y, Gan J. Self-adaptive distributed multi-task allocation in a multi-robot system // IEEE Congress on Evolutionary Computation. 2008. P. 398-404.

41. Choi H.L., Brunet L. and How J. Consensus-based decentralized auctions for robust task allocation.// IEEE Transactions on Robotics, 25(4), 2009. P. 912-926.

42. Dias M., Stentz A. Opportunistic optimization for market-based multirobot control

// International Conference on Intelligent Robots and Systems. 2002. Vol. 3. P. 27142720.

43. Chapman A.C., Micillo R. A., Ramachandra Kota, Jennings N.R. Decentralized dynamic Task Allocation: A Practical Game-Theoretic Approach // In Proceedings of 8th International Conference on Autonomous Agents and Multi-agent Systems. AAMAS 2009. Budapest. Hungary. 2009. P. 915-922.

44. Shaheen Fatime S., Michael Wooldridge. Adaptive task resource allocation in multiagent systems // In Proceedings of 5th International Conference on Autonomous Agents. ACM. New York. USA. 2001. P. 537-544.

45. Yan Kong, Minjie Zhang, Dayong Ye. A group task allocation strategy in open and dynamic grid environments // 7th International workshop on Agent based Complex Automated Negotiations. ACAN 2014. Paris. France. 2014. P. 121-139.

46. Beni G., Wang J. Swarm intelligence in cellular robotic systems // Proceeding NATO Advanced Workshop on Robots and Biological Systems. Tuscany. Italy. 1989. P. 703-712.

47. Bonavear F., Dorigo M. Swarm Intelligence: from natural to artificial systems. М.: Oxford university Press. 1999. 309р.

48. Corne D., Dorigo M., Glover F. New Ideas in Optimization. // McGrav-Hill. 1999.

49. Kennedy J., Eberhart R. Particle swarm optimization // IEEE International Conference on Neural Networks. 1995. Vol. 11(4). P. 1942-1948.

50. Holland J.H. Adaptation in natural and artificial systems. М.: MIT press. Cambridge. 1992. 232р.

51. Contract Net Protocol // URL: https://en.wikipedia.org/wiki/Contract Net Protocol (дата обращения: 15.06.2018).

52. Gao Huiying, Li Qingxia. Study on the rapid evaluation model for seismic cadualties // Journal of catastropholog. 2010. P. 275-277. (in Chinese)

53. Li Yuanyuan, Su Guofeng, Weng Wenguo, Yuan Hongyong. A review of researches on seismic casualty estimation // Journal of catastrophology. 2014. Vol. 29(2). P. 223-227. (in Chinese)

54. WU Jiangfeng, WANG Haixia. The factor analysis of earthquake casualties based

on AMOS // Journal of Earchquake Engineering and Engineering Vibration. 2013. Vol. 33(02). P. 221-228. (in Chinese)

55. LI Xi, GUO Jun, Chen Kun-hua, Lu Yong-kun. Application of primary assessment method based on GIS after the Yingjiang Ms 5.8 and Myanmar Ms 7.2 earthquakes // Journal of Seismological Research. 2012. Vol. 35(1). P. 104-109. (in Chinese)

56. CHEN Hongfu, DAI Junwu, SUN Baitao, WANG Yanru, ZHANG Canghai. Investigation report on influence factors of casualties in April 14, 2010 Yushu earthquake // Journal of Earthquake Engineering and Engineering Vibration. 2011. Vol. 4. P. 18-25. (in Chinese)

57. MA Yuhong, XIE Lili. Methodologies for assessment of earthquake casualty // Journal of Earthquake Engineering and Engineering Vibration. 2000. Vol. 20(4). P. 140-147. (in Chinese)

58. YANG Zhe, CHENG Jiayu. Correlation analysis of house collapse rate and intensity in Tangshan earthquake // Seismology and Geology. 1994. Vol. 3. P. 283-288. (in Chinese).

59. Назарова А.В., Мэйсинь Чжай. Проблемы использования робототехнических систем в операциях спасения при землетрясениях // Робототехника и Техническая Кибернетика. Санкт-Петербург: ЦНИИ РТК. 2018. Т. 20, № 3. С. 31-38.

60. Meet Japan's earthquake search - and - rescue robots [Electronic resource] // Popular Science: [site]. - URL: https://www.popsci.com/technology/article/2011-03/six-robots-could-shape-future-earthquake-search-and-rescue#page-4 (Дата обращения 28.01.2019)

61. Рыжова Т. П. Система управления коллективом мобильных роботов: дис. Канд. Тех. Наук. Москва. 2013. 182с.

62. Gelernter D., Carriero N. Coordination languages and their significance // Communications of the ACM. 1992. Vol. 35(2). P. 97-107.

63. Huhns, M. N., Stephens L. M. Multiagent systems and societies of agents // Multiagent systems: a modern approach to distributed artificial intelligence. 1999. P. 79-114.

64. Ren Xiaoping, CAI Zixing, CHEN Aibin. Current research in multi-mobile robots communication system // Control and Decision. 2010. Vol. 25(3). P. 327-332.

65. Bers J., Redi J. Supporting robot teams with CougaarME over wireless ad-hoc networks // Proceeding of the 1st Open Cougaar Conference. New York. 2004. P. 110.

66. Бугаев А.С., Васильев И.А., Ивашов С.И., Разевиг В.В., Шейко А.П. Обнаружение и дистанционная диагностика людей за препятствиями с помощью радиолокационных средств // Вестник КДПУ им. Михайла Остраградського. 2008. Т. 52, № 5. C. 40-43.

67. Аксенов М.Б., Переяслов А.Н. Основные тенденции развития приборов поиска пострадавших // Технологии Гражданской Безопасности. 2006. Т. 9, № 1. С. 100-109.

68. Возможности радиоволновых методов для обнаружения живых людей за преградами по дыханию и сердцебиению // Датчики и Системы. 2012. Т. 158, № 7. С.74-84.

69. Rajeev Joshi, Pratap Chandra Poudel, Pankaj Bhandari. An embedded autonomous robotic system for alive human body detection and rescue operation // International Journal of Science and Research Pulications. 2014. Vol. 4(5). P. 1-5.

70. Liu Lianggang, Zhang Biyan, Yu Feipeng. Developing and testing of the inferared life detector // Crustal Deformation and Earthquake. 1999. Vol. 19(3). P. 82-86. (in Chinese)

71. Sensors // URL: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5038650/ (дата

обращения: 15.02.2017)

72. Khablov D.V., Sovlukov A.S. State of the art in microwave devices for determination of alive people through obstacles // Digest of the TransBlack Sea Region Symposium on Applied Electromagnetism. Metsovo. Greece. 1996. 135р.

73. Koopman B. O. The theory of search // Operations research. 1956. N 3. 4. 5. P. 503531.

74. Anxing Shan, Xianghua Xu, Zongmao Cheng. Target coverage in wireless sensor

networks with probabilistic sensors // Sensors (Basel). 2016. Vol. 16(9). P. 13721393.

75. Wang B. Coverage problems in sensor networks: A survey // ACM Computing Surveys. 2011. Vol. 43(4). P. 32-51.

76. Kamrani F. Using on-line simulation in UAV pathing planning: Dissertation. Stockholm. Sweden. 2007. 101р.

77. William Feller. An introduction to probability theory and its applications. М.: Wiley. 3rd Edition. 1968. 509р.

78. Beni G., Wang J. Swarm intelligence in cellular robotic systems // Proceeding NATO Advanced Workshop on Robots and Biological Systems. Tuscany. Italy. 1989. P. 703-712.

79. Wang Yan, Zeng Jianchao. A survey of a multi-objective particle swarm optimization algorithm // CAAI Transactions on Intelligent Systems. 2010. Vol. 5(5). P. 377-384.

80. Map_server // URL: https://wiki.ros.org/map server?distro=jade (дата обращения: 15.06.2016)

81. Герасимов В. Н. ^стема навигации сервисного робота в среде с динамическими препятствиями: дис. Канд. Тех. Наук. Москва. 2015. 182с.

82. Ralf Salomon. Evolving and optimizing braitenberg vehicles by means of evolution stragegies // International Journal of Smart Engineering Systems Design. 1999. Vol. 2(1). P. 69-77.

83. Braitenberg V. VEHICLES: Experiments in synthetic psychology. М.: MIT-Press, Cambridge. Massachusetts. 1984. 145p.

ПРИЛОЖЕНИЕ А

Матрица затрат 200^10, элемент матрица г у - ресурсы, затраченные у-м

агентом на выполнение ¡-й задачи, где ¡= {1, 2, ..., 200},)= {1, 2, ..., 10}.

[ 7.5036 2.3183 4.4472 9.6912 0.7758 2.8229 6.3268 5.6702 6.1724 2.2378;

7.9699 3.7431 8.6596 5.4536 8.9852 5.8857 5.6337 5.0472 9.9713 2.0538;

9.9758 2.6042 6.7181 4.4303 3.1479 1.0434 8.6339 6.4372 6.6366 2.3468;

8.4833 5.9142 7.5361 7.3720 5.6119 6.6152 1.1630 7.0308 7.3269 5.7854;