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

На правах рукописи

Туфанов Игорь Евгеньевич

МЕТОДЫ РЕШЕНИЯ ОБЗОРНО-ПОИСКОВЫХ ЗАДАЧ С ПРИМЕНЕНИЕМ ГРУПП АВТОНОМНЫХ НЕОБИТАЕМЫХ ПОДВОДНЫХ АППАРАТОВ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание ученой степени кандидата технических наук

П 3 АПР 2014

0055466/Ь Владивосток-2014

005546676

Работа выполнена в научно-образовательном центре «Подводная робототехника» Института проблем морских технологий ДВО РАН и Дальневосточного федерального университета.

Научный руководитель: Щербатюк Александр Фёдорович,

член-корреспондент РАН, доктор технических наук, заведующий лабораторией систем навигации и обработки сенсорной информации ИПМТ ДВО РАН

Официальные оппоненты:

Капустян Сергей Григорьевич, доктор технических наук, профессор, заведующий отделом НИИ многопроцессорных вычислительных систем им. A.B. Каляева Южного федерального университета

Егоров Сергей Александрович, кандидат технических наук, доцент, заведующий сектором НИИ специального машиностроения МГТУ им. Н.Э. Баумана

Ведущая организация:

Институт проблем управления

им. В. А. Трапезникова РАН, г. Москва

Защита состоится «25» апреля 2014 г. в 12 часов на заседании диссертационного совета Д 005.007.01 в Институте автоматики и процессов управления ДВО РАН по адресу: 690041, г. Владивосток, ул. Радио, 5.

С диссертацией можно ознакомиться в библиотеке Института автоматики и процессов управления ДВО РАН и на сайте ИАПУ ДВО РАН по адресу http://iacp.dvo.ru/russian/institute/dissertation/represent.html.

Автореферат разослан « /?-» 2014 г.

Ученый секретарь

диссертационного совета Д 005.007.01, д.т.н.

A.B. Лебедев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Большая работа в этом направлении проделана зарубежными организациями, в их числе: Массачусетский технологический институт, в котором создана и поддерживается MOOS-IvP — открытая групповая система управления (СУ) мобильными объектами; Технологический институт Джорджии, в котором ведутся исследования групповой работы АНПА на базе системы ROS; университет Порто, в котором разработана СУ DUNE; национальный университет Сингапура и многие другие. В России исследования по созданию более эффективных и надёжных методов решения обзорно-поисковых задач применительно к подводным аппаратам ведутся в ИПМТ ДВО РАН, Дальневосточном федеральном университете, НИИ СМ МГТУ им. Баумана, ИДСТУ СО РАН и других организациях. В области группового управления мобильными роботами и сложными распределёнными системами большой вклад принадлежит научным школам ИПУ им. В. А. Трапезникова РАН, ИПМ им. М. В. Келдыша РАН, ЦНИИРТК, МГТУ МИРЭА, НИИ МВС ЮФУ им. А. В. Каляева и др.

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

Многие из существующих решений обзорно-поисковых задач, основанных на использовании группы АНПА, либо не рассматривают составление оптимального плана работ, либо рассматривают лишь точечные задания, выполнение которых заключается в их «посещении». Однако, в задаче поиска локальных неоднородностей (ЛН) водной среды, задания уже не являются точечными и необходимо усовершенствование существующих подходов. В ряде работ развиваются методы съёмки параметра водной среды,

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

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

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

Для достижения поставленной цели в диссертационной работе ставились и решались следующие задачи:

1. Разработка и исследование математической модели организации работы в группе АНПА.

2. Разработка и исследование метода измерения параметров водной среды с заданной точностью на основе использования группы АНПА.

3. Разработка и исследование метода поиска и обследования локальных неоднородностей водной среды на основе использования группы АНПА.

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

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

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

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

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

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

Практическая значимость и реализация результатов работы.

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

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

Представленные в диссертационной работе исследования выполнены в рамках Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы (государственный контракт №02.740.11.0166 на выполнение в период 2009-2011 гг. научно-исследовательской работы по теме «Разработка многофункционального малогабаритного необитаемого подводного аппарата»), гранта РФФИ № 10-08-00249 на период 2010-2012 гг. на тему «Разработка комплексов интеллектуальных подводных роботов для долговременного сбора данных в океане», гранта РФФИ №13-08-00967а по проекту: «Разработка интеллектуального необитаемого водного аппарата, предназначенного для поддержки работы необитаемых подводных аппаратов при решении широкого круга задач освоения Мирового океана», а также гранта ДВО РАН № 12-Ш-В-01И-007 на тему «Разработка и исследование адаптивных и групповых алгоритмов работы автономных необитаемых подводных аппаратов для решения задач обследования морской среды», выполненного в 2012 г. Положения, выносимые на защиту:

1. Математическая модель задачи планирования в группе АНПА.

2. Алгоритмы решения задачи планирования в группе АНПА на основе алгоритма Хельда-Карпа и аукционного метода.

3. Метод измерения параметров водной среды с требуемой точностью на основе использования группы АНПА.

4. Метод поиска и обследования локальных неоднородностей водной среды, использующий группу АНПА.

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

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

Апробация результатов работы. Основные результаты работы докладывались на всероссийской конференции «Управление в распределённых, сетецентрических и мультиагентных системах» (Геленджик, 2011); на всероссийской конференции «Технические проблемы освоения Мирового океана» (Владивосток, 2011); на международной конференции «Современные методы и средства океанологических исследований» (Москва, 2011); на международной конференции «Underwater Intervention» (New Orleans, USA, 2011); на международной конференции «ISOPE Pacific/Asia Offshore Mechanics Symposium» (Владивосток, 2012); на международной конференции «OCEANS» (Yeosu, Korea, 2012); на международной конференции «International Symposium on Unmanned Untethered Submersible Technology» (Portsmouth, USA, 2013); на международной конференции «Graphicon» (Владивосток, 2013).

Публикации результатов работы. По материалам диссертации опубликовано 12 печатных работ, из них 4 статьи в журналах, входящих в перечень ВАК.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы, включающего 112 наименований. Основное содержание работы изложено на 120 страницах машинописного текста, содержит 38 рисунков и 5 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

Предполагается, что имеется т аппаратов и п заданий. Планирование происходит перед началом выполнения миссии. Известно, что <г/-ый аппарат через время щ окажется в точке трёхмерного пространства и будет готов к выполнению заданий (если аппарат ({ готов к выполнению задания на момент планирования, то ид = 0). Вводится функция с1я(а, Ь), обозначающая время перехода АНПА от точки а к точке Ь. Она может иметь простой вид, например й?Да,Ь) =|а-Ъ |/и , где С/? - максимальная скорость д-ого АНПА, или более сложный. Для /-ого задания дано V, вариантов его выполнения и у'-ый вариант для <7-ого аппарата характеризуется тройкой (а,;,Ь1у,/(;?), обозначающей соответственно точку начала задания, точку окончания и оценку времени его выполнения.

Планом аппарата назван кортеж пар р = 0'ьу'|), 02,АХ • ••, 0и,Л<:) такой, что е1..л, Д е 1 ..у(( для всех к е\..\ р\. Выполнение плана д-ым аппаратом

начинается в точке ъд. Вначале аппарат переходит к точке а, у и выполняет]\-

ый вариант задания Затем аппарат переходит к точке а,и т.д. Выполнение

плана заканчивается в точке Ь^ ^. Таким образом, время выполнения

аппаратом с номером q плана р, составляет:

1р1 и

1„(р) = ид + + ■ (1)

2 к=1

Общим планом является кортеж планов Р = (риР2, ■■■,Рт) такой, что каждое задание встречается среди его планов один раз и в одном варианте. Время выполнения общего плана определяется выражением:

/(Р) = шах/,(/»,). (2)

..т ^

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

известных заданиях и вариантах их выполнения найти общий план Р, минимизирующий t(P):

f(P)-»min. (3)

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

Предложена обобщающая модификация алгоритма Хельда-Карпа. С помощью двоичного поиска по времени плана V с верхней границей Т и точностью е, задача поиска оптимального плана сводится к следующей: для заданного Т найти план, стоимость которого не превышает Т, либо установить, что это невозможно. Для решения задачи использован метод динамического программирования. Обозначим за 7T,(q,S,x) минимальное время выполнения плана для q-oro аппарата, в следующем состоянии: для аппаратов \..q-\ планы уже построены и время выполнения каждого из них не превышает Т\ использованы задания из подмножества S, текущий план для аппарата q заканчивается в точке х из множества {Ьм}(е, nJe, V| U{s,}i6l „. Если

такое состояние невозможно, положим tT.(g,S,\) = <х>. Первоначально известно, что ^,(1>{}>Si) = и, • Кроме того, справедливы правила перехода: 7Г (q, S и {/}, b, j ) = 1Ш + mm[7r(q,S,sq) + dq(sq, а.,),

min min (7Г (q, S, b ) + dq (b, , a( j))],(4)

с- л ¡и ecmimin7T(q-l,S,x)<T\ tT.(q,S,s ) = < " - (5)

|oo, иначе.

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

min/J.,(m,{l,...,n},x)<7". (6)

X

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

Рассмотренная модификация алгоритма Хельда-Карпа имеет асимптотическую сложность:

0(2"mN(m + N)log(T/s)), (7)

где N = л vi 1 Т - априорная оценка времени выполнения миссии сверху, е -величина, на которую допускается превышения стоимости плана над оптимальной.

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

Алгоритм позволяет по заданным i\,ii, ■■■,i\P\ найти набор уuji, • ■•,j\P\ Для составления оптимального плана аппаратар = (i\,ji), (hji), 0'и>Л>|)-

Обозначим за t (к, у) минимальное время выполнения <у-ым аппаратом

заданий i'b i2, ..., ikпри условии jk =j. Для первого задания известно,

iq(\J) = uq+dq(sq,altJ + Ljq, (8)

для у е 1 ..v. . При этом справедливо правило перехода:

tq(k,j) - min(f (к -1,/) + dq(b4jJ.,aw) + /,.,„), (9)

для к> 1, ye 1-v, ■ Последовательно вычисляя tq(k,j) для всех к, получаем

оптимальное время плана аппарата как минимальное tq(\p\,j) по всем

/еl..v. . Сам оптимальный план может быть восстановлен по значениям J 'и

аргументов, на которых достигается минимум выражения (9). Таким образом, асимптотическая сложность алгоритма нахождения локально-оптимального плана для одного аппарата может быть оценена как 0(пЫг), где N = max v;.

/el., и

Разработан также алгоритм нахождения плана, использующий действие аукционного метода, применяемого в при мультиагентном подходе. Алгоритм является эвристическим и полиномиальным по сложности. Задания добавляются к общему плану по одному. Каждый из аппаратов (агентов) ищет позицию в своём плане рд для вставки нового задания, перебирая варианты его выполнения. После этого, для каждого аппарата вычисляется стоимость нового плана. Задание назначается АНПА, минимизировавшему стоимость. Асимптотическая сложность полученного алгоритма составляет 0(N(n + т)).

На практике при построении плана рекомендовано выбирать точный алгоритм при небольшом размере задачи и приближённые в противном случае.

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

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

Для измерения параметра водной среды используется группа АНПА. Каждый аппарат оснащён датчиком для измерения заданного параметра среды, средствами связи и навигации. Исследуемый параметр Z(x) рассматривается как реализация некоторой, нестационарной, двумерной (глубина движения АНПА

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

1. обследование заданной области с использованием меандра с шагом /г;

2. выполнение дополнительного манёвра при нахождении на галсах АНПА отрезков, на расстоянии /г/2 от которых необходимая точность не достигается.

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

Шаг 1 предложено реализовать с использованием централизованного планирования, как это изложено во второй главе. Положим, что область обследования - это прямоугольник размером IV по оси Ох и И(п - 1) по оси Оу, а начало координат поместим в один из его углов. Сформулируем задания для задачи (3):

у. =2, /. = /.,. /и , ..и .д,,

аи=Ьи=(0,(1-1)А), а|12=Ь,,=0Г,(/-1)Й).

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

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

'/2 Е[г(х) - г(у)]2 = К( 0) - щ/2) > р, (11)

где |х - у| = /г/2, К - оценка автокорреляционной функции, ар- пороговое значение, являющееся параметром метода.

Для формирования траектории дополнительного обследования на шаге 2 предложен алгоритм «меандр с переменным шагом», представленный на рис. 1. На вход алгоритма поступает отрезок для обследования (аЬ), параметры метода и параметры рекурсии. Сокращение времени операции по сравнению с обыкновенной реализацией достигается за счёт дополнительного обследования «на месте». В случае если по ходу движения АНПА встречается отрезок х,дх,2 на котором радиус корреляции измеренного параметра меньше установленного порога, то на расстоянии от его окончания осуществляется рекурсивный вызов процедуры обхода с меньшим значением И (см. рис. 2). Если при каждом рекурсивном вызове параметр И изменяется в д раз, то при бесконечной череде рекурсивных вызовов, наиболее удалённый от центральной линии аЬ галс отстоит от неё на расстояние Ь = /г (д + д2 + ...). Из условия полного покрытия и отсутствия перекрытий, можно заключить, что Ь = /г / 2, откуда д = 1 / 3.

С целью исследования предложенного метода был проведён ряд вычислительных экспериментов. Производилось сравнение с обыкновенным меандром по методике, основанной на имитационном моделировании: 1. С помощью меандра с переменным шагом получить траекторию Т\, измерить её длину Ь{Т{).

2. Получить траекторию Т2 на основе обыкновенного меандра с минимальным шагом, при котором Ь(Т2) > ЦТ\).

3. Получить оценку 7,\ и 22 интерполяцией значений 2 с данными в точках Т\ и Т2 соответственно.

4. Сравнить распределения Z - 2\ и 2-22.

Меандр с переменным шагом (а, Ь, И, /гь е, г, Я, Я\)

1. установить путевую точку АНПА \у а;

2. дождаться выхода АНПА в точку \у;

3. для г е Ях.Л: х, , <— х,;2 <— 0;

4. установить путевую точку АНПА \у <— Ь;

5. дождаться очередного измерения параметра 2\

6. х <— текущее положение АНПА;

7. 8. если \у достигнута и х,= 0 для всех 1 е завершить;

9. для 1 е. 1:

10. если Р{\2{у) - 2(х)\ > е}> г для у на расстоянии И / (2-3' ') от X

11. или w достигнута и х,-д Ф 0:

12. Х/,2 *— х;

13. если х,! = 0:

14. Х;л <— х;

15. если |х - х12| > к\ / 3':

16. 8 <— вектор длины к / 3', перпендикулярный х, 2 - ь

17. Меандр с переменным шагом(х + 5, х,1 + 5, /г/3, е, г я, 0;

18. Меандр с переменным шагом (х;д - 5, х - 5, /г/3, е, г к, 0;

19. установить путевую точку АНПА <— х;

20. дождаться выхода АНПА в точку \у;

21. хи <- х,-2 <- 0;

22. перейти к шагу 4;

Рис. 1. Алгоритм «меандр с переменным шагом».

Х|.1-6 х — б

X

а Ж ' А/3 * , Ь

Х,д + 6 Х+6

Рис. 2. Траектория движения, формируемая алгоритмом.

В диссертационной работе приведены результаты экспериментов, произведённых на искусственных данных. Поле 2 задавалось как функция на равномерной прямоугольной сетке. Искусственные данные были получены методом последовательного гауссова стохастического моделирования. Для получения функции с нестационарной АКФ использовалось сумма двух стационарных функций с различными АКФ, одна из которых была к тому же

локализована. Фрагменты сформированного скалярного поля представлены на рис.3. На рис.4 представлены логарифмические гистограммы ошибок, полученные в одном из вычислительных экспериментов на описанных данных. В центре поля находилась область с быстро спадающей АКФ, и её обследование требовало меандра с меньшим шагом. Предложенный метод при использовании статистического критерия (11) сформировал траекторию длинной 17591 единиц (единица измерения - шаг сетки). При обследовании поля традиционным методом с фиксированным шагом меандра, равным минимальному из использованных в предложенном алгоритме переменному шагу меандра, необходима траектория длины 95500, что в 5,4 раза длиннее.

При выполнении этапа 2 в соответствии с алгоритмом «меандр с переменным шагом», значения /д, 1а в выражении (10) представляют собой оценку снизу для времени выполнения задания. При этом может оказаться, что один из АНПА выполнит свой план существенно раньше остальных. В этом случае предложено осуществить перепланирование: для каждого аппарата оценить время, оставшееся до выполнения текущего задания, и используя его в качестве и, решить новую задачу (3) для тех заданий, выполнение которых ещё не началось.

Ф

а) * • • 'шбЩЯШШШШк в)* Ш —

Рис. 3. Результаты моделирования поля с ковариационной функцией вида К (к) = а2 ехр(-/г / р2): а) при р= 20; б) при /7= 100; в) граница смены К.

ом мпш

ом мпш

а) Ошибка б) Ошибка

Рис. 4. Сравнение логарифмических гистограмм (МПШ) и г - 72 (ОМ) в

одном из вычислительных экспериментов: а) «идеальный» критерий б) статистический критерий (11).

О 1000 2000 3000 4000 5000 6000 7000 № шага модели

Рис. 5. Результат планирования на различных этапах работы алгоритма: первоначальный план (вверху), итоговый план (внизу).

На рис. 5 представлен результат такого перепланирования. Рассмотрено действие трёх АНПА.План содержит 9 основных галсов, разбитых на 3 части (27 заданий; переход 24-26 имеет высокую стоимость, поэтому задание 26 назначено последнему, а не первому аппарату). Видно, что задания с номерами 10, 13, 16 охватывают область с быстро спадающей АКФ и время их выполнения больше, чем у остальных заданий. Несколько итераций перепланирования позволяют равномерно распределить задания.

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

Четвёртая глава посвящена разработке и исследованию метода поиска и обследования локальных неоднородностей морской среды. Предложен алгоритм формирования траектории АНПА, позволяющий провести обследование, разработан способ вычисления объёма локальной неоднородности и количества растворённого в ней вещества.

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

• априорно задано значение глубины, на которой следует производить обследование;

• указан минимальный размер ЛН;

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

Предлагаемый метод обследования включает два этапа. Этап 1. Предварительный осмотр «грубым» меандром. Организуется покрытие области А горизонтальным меандром на плоскости с шагом А между галсами (см. рис. 6а). Шаг к выбирается равным половине размера

минимальной области, которая может рассматриваться как ЛН. Входные данные для задачи (3) при этом аналогичны (10).

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

Рис. 6. Этапы выполнения метода: а) этап 1; б) полученные отрезки; в) этап 2.

Первоначальный план строится на основе предположения, что каждой компоненте связности О соответствует единственная ЛН. Неоднородности аппроксимируются многоугольниками с помощью алгоритма на основе поиска в глубину. Первая задача при обследовании ЛН — её оконтуривание в горизонтальной плоскости. Если имеется п ЛН, и г-ая неоднородность аппроксимирована многоугольником р.р г, то входные данные для задачи (3) задаются как:

1

/

1ш ищК

Ри-Р«, 1+£|Р<4 -Р/.Л

Л=1

■Л+1

-Р (12)

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

В работе впервые была поставлена задача оценки объёма ЛН и количества растворённого в ней вещества. Предложен алгоритм решения

данной задачи в случае, когда области ЛН выпуклы или имеют близкую к выпуклой форму:

1. Произвести оконтуривание г-ой ЛН в горизонтальной плоскости.

2. Принимая траекторию АНПА при выполнении шага 1 за сечение ЛН горизонтальной плоскостью, найти р,^, - диаметр этого сечения.

3. Произвести оконтуривание ЛН в вертикальной плоскости, проходящей через заданный диаметр.

4. Пройти по отрезку р,^,, измеряя значение функции 1 вдоль траектории.

5. Интерполировать 1 внутри ЛН на основе произведённых измерений и вычислить требуемые параметры, используя численное интегрирование.

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

= 2, 1п+,м=1„+и2,, =|Р;-Я, а„„,1 =ь„„,2 =Р,> а„+и=Ь„+м=я,.,

^+1-=2,/2„+гМ=/2п+(,2,? 1/С/9.а2„+и=Ь2П+г,1=Р.'а2»+/,2 =Ь2„+;,2=Ч.-

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

'5000" '5000*

5000 5000

5000 ,Р = 5000

4000 5000

ч5000у 5000,

Г150 350400610620" 250320 200100 400 150150150 120 180,

1000 № шага модели

2000

Рис. 7. Параметры 2 в одном из вычислительных экспериментов (слева)-, визуализация областей ЛН (справа)-, результат планирования при т = 3 (внизу).

Области ЛН

Параметры 2, визуализация ЛН и решение соответствующей задачи планирования для одного из экспериментов представлены на рис. 7. Исследования подтвердили работоспособность и эффективность предложенного метода. Для полей вида (14) ошибка определения объема ЛН и количества растворённого в них вещества составляла около 10%.

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

Рис. 8. Структура комплекса программ.

Планировщик управляет ходом выполнения миссии. Данный компонент содержит реализацию алгоритмов решения задачи (3) и декомпозицию миссии в соответствии с выражениями (10), (12), (13). Каждый раз, когда аппарат выполнил очередное задание или приступил к очередному заданию, он посылает отчёт об этом планировщику. Таким образом, планировщик хранит информацию о статусе всех заданий. Между АНПА и планировщиком происходит обмен периодическими сообщениями, что позволяет последнему иметь информацию о том, какие аппараты находятся в составе группы и отправлять им задания.

Модель АНПА содержит:

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

• состояние системы программного управления АНПА - имеется ли целевая точка движения и, если да, то её координаты;

• модель датчика для измерения параметра среды;

• кинематическую модель движения в трёхмерном пространстве с ограничениями по максимальной скорости и по угловым скоростям курса и дифферента.

Рис. 9. Структура СПУ АНПА «МАРК» со стороны центрального узла.

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

статистический анализ полей.

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

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

Далее в главе описывается реализация алгоритмов группового планирования в системе программного управления (СПУ) АПНА «МАРК» [2]. Вся СПУ выполнена в виде набора исполняемых модулей, работающих одновременно. Для обеспечения связи между модулями используется обмен сообщениями, что позволяет естественным образом обобщить передачу данных

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

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

Таким образом, разработанные в диссертации методы и алгоритмы были не только реализованы в виде комплекса программ для проведения вычислительного эксперимента, но и внедрены в СПУ конкретного АНПА.

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

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

2. Разработаны алгоритмы решения задачи оптимального планирования в рамках предложенной модели: точный - на основе алгоритма Хельда-Карпа и приближённый - на основе аукционного метода.

3. Разработан и исследован метод съёмки параметров водной среды с заданной точностью на основе применения группы АНПА. Метод использует формирование траектории типа «меандр с переменным шагом» и позволяет повысить эффективность съёмки при изучении нестационарных процессов.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Туфанов И.Е., Щербатюк А.Ф. Разработка алгоритмов группового поведения АНПА в задаче обследования локальных неоднородностей морской среды // Управление большими системами. - 2012. - вып. 36. -С. 262-284.

2. Ваулин Ю.В., Дубровин Ф.С., Кушнерик A.A., Туфанов И.Е., Щербатюк А.Ф. Малогабаритный автономный необитаемый подводный аппарат МАРК нового поколения для выполнения групповых операций // Мехатроника, автоматизация, управление. - 2012. -№6. - С. 59-65.

3. ТуфановИ.Е., ЩербатюкА.Ф. Об алгоритмах высокоточного измерения параметров водной среды, основанных на использовании группы АНПА // Управление большими системами. - 2013. - вып. 43. - С. 254-270.

4. Туфанов И.Е. Разработка системы централизованного управления группой АНПА// Мехатроника, автоматизация, управление. - 2013. -№7. - С. 65-70.

5. DenisenkoM., Dubrovin F., Mun S., Nepostaev E., SuraevN., Tuphanovl, Vaulin Y. Control System of Small AUV for Multiple Vehicle Operation // Proceedings of the international conference and exhibition «Underwater Intervention 2011». - New Orleans, USA, 2011. - P. 1-5.

6. Туфанов И.Е., Щербатюк А.Ф. Об одном алгоритме обследования локальных неоднородностей морской среды с использованием группы АНПА // Материалы 4-й Всероссийской научно-технической конференции «Технические проблемы освоения Мирового океана». -Владивосток, 2011.-С. 371-375.

7. Дубровин Ф.С., Непостаев Е.И., СураевН.В., Денисенко М.В., Туфанов И.Е., Щербатюк А.Ф. Навигационно-управляющий комплекс автономного необитаемого подводного аппарата для выполнения групповых операций // Материалы 4-й Всероссийской мультиконференции по проблемам управления. Локальная научно-техническая конференция «Управление в распределенных сетецентрических и мультиагентных системах». - Геленджик, 2011. -С. 346-350.

8. Дубровин Ф. С., Туфанов И.Е., Щербатюк А.Ф. Малогабаритный автономный необитаемый подводный аппарат для выполнения групповых операций на шельфе // Материалы XII Международной научно-технической конференции «Современные методы и средства океанологических исследований». - Москва, 2011. - Т. 2 - С. 66-69.

9. Tuphanov I., Scherbatyuk A. Algorithms for Underwater Local Heterogeneity Survey Based on AUV Group Usage// Proceedings of the OCEANS MTS/IEEE Conference. - Yeosu, Korea. - 2012.

10. Tuphanov I., Scherbatyuk A. Adaptive Algorithm of AUV Meander Pattern Trajectory Planning for Underwater Sampling// Proceedings of the Pacific Asia Offshore Mechanics Symposium (PACOMS). - Vladivostok, Russia, 2012.-P. 181-185.

11. Tuphanov I., Scherbatyuk A., Vaulin Yu. Development of Centralized Control System for AUV Group Operation// Proceedings of the 18th International Symposium on Unmanned Untethered Submersible Technology. - Portsmouth, USA, 2013.-P. 1-10.

12. Морозов M.A., Туфанов И.Е. Графический моделирующий комплекс для автономного необитаемого подводного аппарата// Graphicon-2013, 23rd International Conference on Computer Graphics and Vision. -Vladivostok, Russia, 2013.-C. 161-165.

Личный вклад автора.

Все результаты, составляющие основное содержание диссертации, получены автором самостоятельно. В работах [1,6,9] автором разработан алгоритм предварительной оценки формы локальных неоднородностей, алгоритм вычисления параметров локальных неоднородностей, метод организации работы группы АНПА, вычислительный эксперимент. В работах [3, 10] автором разработан статистический критерий перехода между режимами траектории, метод организации работы группы АНПА, вычислительный эксперимент. В работах [2, 5, 7, 8, 11] автором разработаны механизмы системы программного управления АНПА, обеспечивающие их групповую работу, реализована часть других модулей системы программного управления. В работе [12] автором разработаны и реализованы механизмы моделирования, позволяющие использовать модули СПУ АНПА совместно с имитационно-моделирующим комплексом.

Игорь Евгеньевич ТУФАНОВ

МЕТОДЫ РЕШЕНИЯ ОБЗОРНО-ПОИСКОВЫХ ЗАДАЧ С ПРИМЕНЕНИЕМ ГРУПП АВТОНОМНЫХ НЕОБИТАЕМЫХ ПОДВОДНЫХ АППАРАТОВ

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано к печати 14.02.2014 г. Формат 60x90/16. Печать офсетная. Усл. п. л. 1,25. Уч.-изд. л. 1,02. Тираж 120 экз. Заказ 22

Отпечатано в Информационно-полиграфическом хозрасчетном центре

ТИГ ДВО РАН

690041, г. Владивосток, ул. Радио. 7

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

На правах рукописи

04201457595 Туфанов Игорь Евгеньевич

МЕТОДЫ РЕШЕНИЯ ОБЗОРНО-ПОИСКОВЫХ ЗАДАЧ С ПРИМЕНЕНИЕМ ГРУПП АВТОНОМНЫХ НЕОБИТАЕМЫХ ПОДВОДНЫХ АППАРАТОВ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

Диссертация на соискание учёной степени кандидата технических наук

Научный руководитель -чл.-корр. РАН, д.т.н. А.Ф. Щербатюк

Владивосток - 2014

СОДЕРЖАНИЕ

Содержание......................................................................................................................2

Список условных сокращений.......................................................................................4

Введение...........................................................................................................................5

Глава 1. Современные методы, алгоритмы и модели управления группами АНПА .........................................................................................................................................15

1.1. Методы решения прикладных задач с использованием одиночных АНПА и их групп.......................................................................................................................15

1.2. Существующие модели и алгоритмы для управления группами мобильных роботов...........................................................................................................................21

1.3. СПУ, обеспечивающие групповую работу АНПА.......................................27

1.4. Выводы..............................................................................................................29

Глава 2. Централизованное планирование миссии в группе АНПА.......................32

2.1. Постановка задачи планирования..................................................................32

2.2. Алгоритмы составления оптимального плана..............................................37

2.2.1. Модификация алгоритма Хельда-Карпа...............................................38

2.2.2. Эвристический алгоритм на основе аукционного метода..................42

2.3. Дополнительные факторы модели.................................................................44

2.4. Выводы..............................................................................................................45

Глава 3. Метод измерения параметра водной среды с заданной точностью, использующий группу АНПА......................................................................................47

3.1. Формирование траектории обследования.....................................................47

3.2. Критерии смены шага меандра.......................................................................51

3.3. Результаты моделирования.............................................................................54

3.4. Обеспечение групповой работы.....................................................................59

3.5. Выводы..............................................................................................................64

Глава 4. Метод поиска и обследования локальных неоднородностей морской среды, использующий группу АНПА.........................................................................66

4.1. Метод обследования локальных неоднородностей......................................66

4.2. Результаты моделирования.............................................................................72

2

4.3. Групповая работа.............................................................................................77

4.4. Выводы..............................................................................................................80

Глава 5. комплекс программ и реализация системы централизованного управления на АНПА «МАРК»...................................................................................82

5.1. Комплекс программ для имитационного моделирования работы группы АНПА..............................................................................................................................82

5.1.1. Структура комплекса..............................................................................83

5.1.2. Модель среды..........................................................................................84

5.2. Реализация централизованного управления в составе СПУ АНПА «МАРК»..........................................................................................................................89

5.2.1. Состав и архитектура СПУ....................................................................89

5.2.2 Средства обеспечения групповой работы в СПУ.................................93

5.3. Испытания СПУ в составе АНПА «МАРК».................................................97

5.3.1. Миссия «меандр»....................................................................................98

5.3.2. Миссия «квадрат».................................................................................101

5.3.3. Миссия «зигзаг»....................................................................................103

5.4. Выводы............................................................................................................105

Основные результаты работы....................................................................................107

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

СПИСОК УСЛОВНЫХ СОКРАЩЕНИЙ

АНПА - автономный необитаемый подводный аппарат АНВА - автономный необитаемый водный аппарат ГБО - гидролокатор бокового обзора ДВФУ - Дальневосточный федеральный университет

ИПМТ ДВО РАН - Институт проблем морских технологий Дальневосточного отделения Российской академии наук ЛВС - локальная вычислительная сеть JIH - локальная неоднородность

МАРК - морской автономный робототехнический комплекс

СПУ - система программного управления

MRTA - Multi-Robot Task Allocation

MTSP - Multiple Travelling Salesmen Problem

TSP - Travelling Salesman Problem

ВВЕДЕНИЕ

Автономные необитаемые подводные аппараты /АНПА/ - один из инструментов для исследования Мирового океана. Автономность аппарата означает, что он может решать поставленные задачи без участия человека. История АНПА начинается с 60-х годов с создания аппарата SPURV [40].

На основе использования АНПА существуют методы решения различных прикладных задач экологического мониторинга [9, 34, 37, 53], обследования протяжённых объектов [48], поиска затонувших объектов [89] и др. [1, 95]. Одним из основных классов задач, решаемых с использованием АНПА, являются обзорно-поисковые задачи. Они заключаются в покрытии некоторой площади под водой либо с целью поиска и обследования заданных объектов (локальных неоднородностей среды, шлейфов, протяжённых донных сооружений и одиночных объектов), либо для построения карты с нанесёнными результатами измерений. Традиционный метод решения обзорно-поисковых задач с использованием АНПА заключается в покрытии указанной области сетью параллельных галсов. При этом миссия для аппарата представляет собой фиксированную траекторию, вводимую в систему программного управления /СПУ/ аппарата перед погружением.

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

Большая работа в этом направлении проделана зарубежными организациями, в их числе: Массачусетский технологический институт, в котором создана и поддерживается MOOS-IvP - открытая групповая система управления мобильными объектами; Технологический институт Джорджии, в котором ведутся исследования групповой работы АНПА на базе системы ROS; университет Порто, в котором разработана СПУ DUNE; национальный университет Сингапура и многие другие. Работы в данной области нередко объединяются в научные проекты, такие как европейский проект TRIDENT [96].

5

В России исследования по созданию более эффективных и надёжных методов решения обзорно-поисковых задач применительно к подводным аппаратам ведутся в ИПМТ ДВО РАН и других организациях. В области группового управления мобильными роботами и сложными распределёнными системами большой вклад принадлежит научным школам ИПУ им. В. А. Трапезникова РАН, ИПМ им. М. В. Келдыша РАН, ЦНИИРТК, МГТУМИРЭА, НИИМВСЮФУ им. А. В. Каляева и др.

Результаты практического использования нескольких АНПА одновременно приводятся в докладе [89], посвященном поискам обломков самолёта рейса Air France 447, разбившегося в 2009 году в Атлантическом океане. Зона поисков представляла собой круг радиусом порядка 70 км. Глубина в зоне поиска варьировалась от 700 до 4000 м. Операция была произведена с помощью трёх АНПА марки Remus-6000, оснащённых гидролокаторами бокового обзора /ГБО/ и работавших одновременно. Авторы отмечают высокую производительность работы трёх АНПА и сравнивают её с производительностью буксируемой системы ГБО меньшей частоты. Отмечается качество данных, полученных с помощью АНПА, гибкость в формировании траектории. Вместе с тем, приведены данные, согласно которым из 129 пусков аппаратов, совершённых во время поисковых работ, 87 (т.е. 67%) были успешными. Остальные запуски заканчивались неудачно из-за отказов оборудования и программного обеспечения. Управление каждым аппаратом было организовано независимо от других. Данные ГБО изучались вручную в режиме постобработки.

Пример использования двух разнородных АНПА описан в докладе [108]. Один из аппаратов использовался для съёмки батиметрической карты с использованием многолучевого сонара, а другой - для составления фотографической мозаики дна. При этом аппарат, оснащённый фотокамерой, привлекался для съёмки участков дна, которые были выбраны в результате постобработки данных, отснятых первым аппаратом. Ввод задания в АНПА осуществлялся вручную. В работе [87] докладывается о подготовке эксперимента

с одновременным использованием летательного, поверхностных и подводных автономных аппаратов.

Имеются примеры успешного использования АНПА и для экологического мониторинга. В докладе [101] изложены прикладные результаты, полученные и использованием АНПА Dorado в заливе Monterey на западном побережье США. К примеру, с помощью повторного построения батиметрической карты одного и того же района в два различных момента времени, было зафиксировано изменение батиметрии вплоть до 15 м. вследствие извержения подводного вулкана. АНПА данного класса используются также для изучения слоя фитопланктона и взятия проб воды в местах его наибольшей концентрации.

Работы [47, 78] посвящены опыту практического применения АНПА Hugin. Сравнивается экономическая эффективность использования данного АНПА по сравнению с буксируемыми системами. Делается вывод, что использование АНПА обходится в 2-3 раза дешевле. Данный аппарат использовался в работах для гидрографического обследования с целью прокладки донных труб, начиная с 1997 года. Известны его применения для построения карты рельефа на акватории размером 26 х 17 км. при рабочей глубине 1500 м. Максимальная глубина работы данного АНПА - 3000 м.

Для сбора океанографических данных на больших акваториях используют глайдеры - особый вид АНПА [106]. В работе [65] приводятся результаты экспериментов с группой глайдеров в заливе Монтерей на западном побережье США. Используемые в экспедиции глайдеры не имели гидроакустических средств связи. Они поднимаются на поверхность раз в два часа для сеанса связи. Осуществляется централизованное управление группой глайдеров: каждый из них получает путевую точку на очередном сеансе связи от управляющего узла через спутник связи. На другом побережье США, в Мексиканском заливе, действует группировка глайдеров, которая собирает океанографические данные в рамках организации GCOOS (Gulf of Mexico Coastal Ocean Observing System) [83, 84]. Приложения по использованию этих данных включают исследование

вредоносного цветения водорослей, гипоксии и последствий аварии на нефтяной платформе Deep Water Horizon в 2010 году.

Глайдеры представляют собой разновидность энергоэффективных АНПА. Передвижение аппарата такого класса осуществляется за счёт изменения плавучести. Другим по сравнению с используемым глайдерами способом увеличения времени работы АНПА является использование солнечных батарей. Данный подход был применён в аппарате SAUV, разработанном совместно ИПМТ ДВО РАН и институтом AUSI из США. Существует также его обновлённая модификация SAUV II. Аппараты данного класса были использованы для измерения концентрации кислорода Гринвичском заливе [55]. Отмечается, что использование АНПА позволило увеличить качество получаемых данных о концентрации растворённого кислорода.

Среди результатов, связанных с интеллектуализацией автономных аппаратов, можно отметить работы по обследованию локальных неоднородностей морской среды в виде шлейфа. Так, в работе [44] рассматривается задача локализации шлейфа тёплой воды, сбрасываемой АЭС Калверт Клифс в Чесапикский залив. Алгоритм формирования траектории позволил без детального обследования всего залива отследить шлейф тёплой воды с использованием АНВА. Для отслеживания шлейфа применялась т.н. индикаторная функция, которая является линейной комбинацией нескольких параметров среды, включающих температуру и электропроводность морской воды.

В докладе [64] представлены результаты работы АНПА по поиску источника химического шлейфа, который искусственно создавался с использованием родаминового красителя. Одиночный аппарат марки REMUS запускался несколько раз, осуществляя поиск источника загрязнения в квадрате размером 300 х 100 м. Был использован алгоритм, в котором АНПА, обнаружив шлейф, начинает движение против течения с поправкой в случае потери шлейфа. Серией запусков была продемонстрирована работоспособность предложенного алгоритма.

Существуют также методы групповой работы АНПА для поиска центра ЛН. Например, в докладе [97] приводятся результаты морских испытаний алгоритма коллективного поиска центра ЛН. Аппараты, описанные в работе, принадлежат классу микро-АНПА (весом 4,5 кг) и не имеют развитых средств связи и навигации. По этой причине каждый аппарат был запрограммирован на периодическое всплытие для уточнения своих координат с помощью спутниковой навигационной системы и получения данных от других аппаратов. Обмен данными происходил через судовой пост оператора. Использовалось искусственное поле ЛН, для которого значение обратно пропорционально квадрату расстояния до источника. Цель запусков состояла в том, чтобы все АНПА группы прибыли к источнику неоднородности. Доклад сообщает об успехе испытаний. Отмечается, что не все аппараты во всех тестах успешно смогли заглубиться для выхода в центр ЛН, тем не менее, в каждом тесте хотя бы один аппарат выполнял миссию.

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

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

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

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

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

Для достижения поставленной цели в диссертационной работе ставились и решались следующие задачи:

1. Разработка и исследование математической модели организации работы в группе АНПА.

2. Разработка и исследование метода измерения параметров водной среды с заданной точностью на основе использования группы АНПА.

3. Разработка и исследование метода поиска и обследования локальных неоднородностей водной среды на основе использования группы АНПА.

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

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

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

решения задачи о группе коммивояжёров на основе алгоритма Хельда-Карпа и аукционного метода.

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