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

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

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

С ПРИМЕНЕНИЕМ ГРУПП

АВТОНОМНЫХ НЕОБИТАЕМЫХ ПОДВОДНЫХ АППАРАТОВ

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

и комплексы программ

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

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

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

Научный руководитель: Щербатюк Александр Фёдорович, член-корреспондент РАН, доктор технических наук, заведующий лабораторией систем навигации и обработки сенсорной информации

ИПМТ ДВО РАН

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

Ведущая организация: Институт проблем управления им. В. А. Трапезникова РАН, г. Москва

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

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

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

Ученый секретарь диссертационного совета Д 005.007.01, д.т.н. А.В. Лебедев

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

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

Большая работа в этом направлении проделана зарубежными организациями, в их числе: Массачусетский технологический институт, в котором создана и поддерживается 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-III-В-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 таблиц.

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

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

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

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

объёма и количества растворённого вещества.

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

Ставится задача составления оптимального плана, и исследуются алгоритмы её решения.

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

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

Предполагается, что имеется m аппаратов и n заданий. Планирование происходит перед началом выполнения миссии. Известно, что q-ый аппарат через время uq окажется в точке sq трёхмерного пространства и будет готов к выполнению заданий (если аппарат q готов к выполнению задания на момент планирования, то uq = 0). Вводится функция dq(a, b), обозначающая время перехода АНПА от точки a к точке b. Она может иметь простой вид, например d q (a, b) | a b | / U q, где Uq – максимальная скорость q-ого АНПА, или более сложный. Для i-ого задания дано vi вариантов его выполнения и j-ый вариант для q-ого аппарата характеризуется тройкой (a i, j, b i, j, li, j,q ), обозначающей соответственно точку начала задания, точку окончания и оценку времени его выполнения.

Планом аппарата назван кортеж пар p = (i1, j1), (i2, j2), …, (i|p|, j|p|) такой, что ik 1..n, jk 1..vik для всех k 1.. | p |. Выполнение плана q-ым аппаратом плана заканчивается в точке b i|p|, j|p|. Таким образом, время выполнения аппаратом с номером q плана p, составляет:

Общим планом является кортеж планов P = (p1, p2, …, pm) такой, что каждое задание встречается среди его планов один раз и в одном варианте.

Время выполнения общего плана определяется выражением:

поскольку миссию можно считать завершённой только после того, как все аппараты выполнили работу. Задача состоит в том, чтобы при данных uq и sq, известных заданиях и вариантах их выполнения найти общий план P, минимизирующий t(P):

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

Предложена обобщающая модификация алгоритма Хельда-Карпа. С помощью двоичного поиска по времени плана T ' с верхней границей T и точностью, задача поиска оптимального плана сводится к следующей: для заданного T ' найти план, стоимость которого не превышает T ', либо установить, что это невозможно. Для решения задачи использован метод динамического программирования. Обозначим за ~ ' (q, S, x) минимальное время выполнения плана для q-ого аппарата, в следующем состоянии: для аппаратов 1..q–1 планы уже построены и время выполнения каждого из них не превышает T ', использованы задания из подмножества S, текущий план для аппарата q заканчивается в точке x из множества {b i, j}i1..n,j1..v {s i }i1..m. Если такое состояние невозможно, положим ~ ' (q, S, x). Первоначально известно, ~ (1,{}, s ) u. Кроме того, справедливы правила перехода:

Используя правила перехода теперь можно вычислить ~ ' для всех tT допустимых состояний. Искомый план со временем выполнения не более T ' существует тогда и только тогда, когда Восстановив аргументы, на которых достигается минимум выражения (4), несложно получить и сам план.

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

где N i1..n vi, T – априорная оценка времени выполнения миссии сверху, – величина, на которую допускается превышения стоимости плана над оптимальной.

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

Алгоритм позволяет по заданным i1, i2, …, i|p| найти набор j1, j2, …, j|p| для составления оптимального плана аппарата p = (i1, j1), (i2, j2), …, (i|p|, j|p|).

Обозначим за tq (k, j ) минимальное время выполнения q-ым аппаратом заданий i1, i2, …, ik при условии jk = j. Для первого задания известно, для j 1..vi1. При этом справедливо правило перехода:

для k > 1, j 1..vik. Последовательно вычисляя tq (k, j ) для всех k, получаем оптимальное время плана аппарата как минимальное tq (| p |, j ) по всем j 1..vi| p|. Сам оптимальный план может быть восстановлен по значениям аргументов, на которых достигается минимум выражения (9). Таким образом, асимптотическая сложность алгоритма нахождения локально-оптимального плана для одного аппарата может быть оценена как O (nN 2 ), где N max vi.

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

Асимптотическая сложность полученного алгоритма составляет O ( N ( n m )).

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

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

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

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

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

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

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

Предложенный метод состоит из следующих шагов:

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

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

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

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

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

Решение о том, достигается ли необходимая точность, производится на основе критерия вида где |x – y| = h/2, K – оценка автокорреляционной функции, а p – пороговое значение, являющееся параметром метода.

Для формирования траектории дополнительного обследования на шаге предложен алгоритм «меандр с переменным шагом», представленный на рис. 1.

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

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

1. С помощью меандра с переменным шагом получить траекторию T1, измерить её длину L(T1).

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

3. Получить оценку Z1 и Z2 интерполяцией значений Z с данными в точках T1 и T2 соответственно.

4. Сравнить распределения Z – Z1 и Z – Z2.

Меандр с переменным шагом (a, b, h, h1,, r, R, R1) 1. установить путевую точку АНПА w a;

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

3. для i R1..R: xi,1 xi,2 0;

4. установить путевую точку АНПА w b;

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

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

7. если w достигнута и xi,1 = 0 для всех i R1..R:

9. для i R1..R–1:

если P{|Z(y) – Z(x)| > } > r для y на расстоянии h / (23i–1) от x вектор длины h / 3i, перпендикулярный xi,2 – xi,1;

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

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

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

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

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

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

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

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

Рис. 3. Результаты моделирования поля с ковариационной функцией вида Рис. 4. Сравнение логарифмических гистограмм Z – Z1 (МПШ) и Z – Z2 (ОМ) в одном из вычислительных экспериментов: а) «идеальный» критерий б) Рис. 5. Результат планирования на различных этапах работы алгоритма:

первоначальный план (вверху), итоговый план (внизу).

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

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

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

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

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

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

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

Предлагаемый метод обследования включает два этапа.

Этап 1. Предварительный осмотр «грубым» меандром. Организуется покрытие области A горизонтальным меандром на плоскости с шагом h между галсами (см. рис. 6а). Шаг h выбирается равным половине размера минимальной области, которая может рассматриваться как ЛН. Входные данные для задачи (3) при этом аналогичны (10).

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

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

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

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

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

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

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

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

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

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

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

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

визуализация областей ЛН (справа); результат планирования при m = 3 (внизу).

Параметры Z, визуализация ЛН и решение соответствующей задачи планирования для одного из экспериментов представлены на рис. 7.

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

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

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

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

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

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

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

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

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

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

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

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

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

Далее в главе описывается реализация алгоритмов группового планирования в системе программного управления (СПУ) АПНА «МАРК» [2].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Denisenko M., Dubrovin F., Mun S., Nepostaev E., Suraev N., Tuphanov I, 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. Туфанов И.Е., Щербатюк А.Ф. Об одном алгоритме обследования локальных неоднородностей морской среды с использованием группы конференции «Технические проблемы освоения Мирового океана». – Владивосток, 2011.– С. 371–375.

7. Дубровин Ф.С., Непостаев Е.И., Сураев Н.В., Денисенко М.В., Туфанов И.Е., Щербатюк А.Ф. Навигационно-управляющий комплекс автономного необитаемого подводного аппарата для выполнения мультиконференции по проблемам управления. Локальная научнотехническая конференция «Управление в распределенных сетецентрических и мультиагентных системах». – Геленджик, 2011. – C. 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. Морозов М.А., Туфанов И.Е. Графический моделирующий комплекс для автономного необитаемого подводного аппарата // Graphicon-2013, 23rd International Conference on Computer Graphics and Vision. –Vladivostok, Russia, 2013. – С. 161–165.

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

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

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

С ПРИМЕНЕНИЕМ ГРУПП

АВТОНОМНЫХ НЕОБИТАЕМЫХ

ПОДВОДНЫХ АППАРАТОВ

диссертации на соискание ученой степени Усл. п. л. 1,25. Уч.-изд. л. 1,02. Тираж 120 экз.

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

ТИГ ДВО РАН