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

ИНСТИТУТ ПРОБЛЕМ МОРСКИХ ТЕХНОЛОГИЙ

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

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

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

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

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

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

Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ Диссертация на соискание учёной степени кандидата технических наук

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

СОДЕРЖАНИЕ

Содержание

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

Введение

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

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

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

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

1.4. Выводы

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

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

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

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

2.2.2. Эвристический алгоритм на основе аукционного метода.................. 2.3. Дополнительные факторы модели

2.4. Выводы

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

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

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

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

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

3.5. Выводы

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

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

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

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

4.4. Выводы

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

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

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

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

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

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

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

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

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

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

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

5.4. Выводы

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

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

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

АНПА – автономный необитаемый подводный аппарат АНВА – автономный необитаемый водный аппарат ГБО – гидролокатор бокового обзора ДВФУ – Дальневосточный федеральный университет ИПМТ ДВО РАН – Институт проблем морских технологий Дальневосточного отделения Российской академии наук ЛВС – локальная вычислительная сеть ЛН – локальная неоднородность МАРК – морской автономный робототехнический комплекс СПУ – система программного управления 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].

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

Результаты практического использования нескольких АНПА одновременно приводятся в докладе [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 из США. Существует также его использованы для измерения концентрации кислорода Гринвичском заливе [55].

Отмечается, что использование АНПА позволило увеличить качество получаемых данных о концентрации растворённого кислорода.

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

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

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

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

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

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

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

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

Возникают вопросы к надёжности и эффективности подобных решений в сравнении с традиционными методами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Представленные в диссертационной работе исследования выполнены в рамках Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 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).

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

содержание диссертации, получены автором самостоятельно.

В работах [29, 30, 103] автором разработан алгоритм предварительной оценки формы локальных неоднородностей, алгоритм вычисления параметров локальных неоднородностей, метод организации работы группы АНПА, вычислительный эксперимент.

В работах [28, 102] автором разработан статистический критерий перехода между режимами траектории, метод организации работы группы АНПА, вычислительный эксперимент.

В работах [6, 7, 8, 58, 104] автором разработаны механизмы системы программного управления АНПА, обеспечивающие их групповую работу, реализована часть других модулей системы программного управления.

В работе [24] автором разработаны и реализованы механизмы моделирования, позволяющие использовать модули СПУ АНПА совместно с имитационно-моделирующим комплексом.

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

изложено на 120 страницах машинописного текста, содержит 38 рисунков и 5 таблиц.

ГЛАВА 1. СОВРЕМЕННЫЕ МЕТОДЫ, АЛГОРИТМЫ И МОДЕЛИ

УПРАВЛЕНИЯ ГРУППАМИ АНПА

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

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

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

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

Траектория представляет собой меандр с переменной длиной галса. Длина гласа выбирается в зависимости от ширины шлейфа на рассматриваемом срезе.

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

Работа демонстрирует работоспособность предложенных алгоритмов.

Пример использования АНПА для поиска источника шлейфа излагается в работе [64]. Поиск источника выполнялся на основе управления с несколькими поведениями (режимами). В каждый момент времени ровно одно поведение было активно и переключение между ними осуществлялось бинарным образом. Каждое поведение формировало желаемый курс и скорость АНПА. Поведения включали:

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

Серией из 15 запусков была продемонстрирована работоспособность предложенного алгоритма.

Параметрический метод рассмотрен в докладе [45]. Рассматривается плоская модель ЛН в виде эллипса. Для вычисления параметров эллипса используется нелинейный метод наименьших квадратов. В случае использования непараметрических методов производится оконтуривание ЛН. При этом предлагается использовать PD-регулятор и основная задача состоит в выборе величины, для которой осуществляется регулирование (вопрос организации оконтуривания, т.е. движения АНПА по изолиниям поля, изучен и рассмотрен, например, в [17]). Рассматривается также задача определения центра масс ЛН.

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

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

Предлагается траектория, многократно пересекающая границу неоднородности.

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

Обследованиям ЛН типа «шлейф» с использованием групп АНПА посвящена работа [4]. Для локализации шлейфа используется понятие центральной линии – траектории с максимальным значением исследуемого поля, и используется соответствующая математическая модель шлейфа.

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

Коллективный метод поиска центра ЛН приводится в работе [97]. Каждый аппарат группы периодически получает информацию об измерениях, произведённых другими АНПА, и на основе этого формирует свою траекторию, следуя по градиенту поля, в соответствии с алгоритмами, приведёнными в [73].

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

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

В статье [65] приводятся результаты работы группы глайдеров. Конкретных стратегий по формированию траектории обследования работа не содержит, однако в ней разработан механизм получения карты ошибок на основе гауссовых процессов для восстановления параметра среды. Особенностью метода является учёт не только пространственной изменчивости параметра, но и его изменчивости по времени (т.е. рассматривается трёхмерное скалярное поле). Движение группы организуется с использованием метода виртуальных тел и искусственных потенциалов (VBAP, см. [76]). Метод позволяет задать, используя попарные расстояния, «виртуальное тело» – формацию, которую должны соблюдать аппараты относительно базовой точки. Управление осуществляется путём перемещения базовой точки. Каждый аппарат при этом перемещается на свою позицию относительно базовой точки. Это позволяет регулировать расстояние между аппаратами таким образом, чтобы обеспечить необходимое рассредоточение. Управление группой является централизованным. Каждые два часа глайдер всплывает, уточняет своё местоположение, используя спутниковую навигационную систему, и получает новую путевую точку от центрального узла через спутниковую систему связи. Исследованию управления формациями посвящён также доклад [31]. Механизм планирования миссии для глайдеров представлен в докладе [107]. Задание новых путевых точек осуществляется в автоматическом режиме (иногда под контролем оператора) на основе имеющейся модели океанических течений.

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

Другой подход использует итерационные процедуры, в которых на каждом шаге формируется новая точка для измерения, при этом оптимизируется некоторая информационная метрика. Такой подход используется в работах [77, 109, 110, 112], которые различаются используемыми метриками и алгоритмами поиска оптимального решения. К итерационным относится и алгоритм, предложенный в работе [43]. Ставится задача измерения поля для последующего восстановления с заданной точностью (при определенных условиях на гладкость).

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

Вокруг каждого аппарата строится окружность доверительного радиуса и на ней выбирается точка. Доверительный радиус рассчитывается исходя из требуемой погрешности восстановления на основе оценки ошибки восстановления поля методом радиальных базисных функций. Выбор конкретных точек на окружности осуществляется путем минимизации функционала, «притягивающего» аппараты к тем точкам рассматриваемой области, которые еще не находятся ни в одной доверительной окружности. Если таких точек нет, то алгоритм завершает свою работу. Таким образом, время, необходимое для перехода от одной точки измерения до другой не учитывается и не ставится задача его минимизации. Более того, на каждом шаге алгоритма требуется синхронизация аппаратов: расчет следующего шага должен быть осуществлен только тогда, когда все АНПА выполнили предыдущий шаг. В работе [42] описанный подход развивается для случая ограниченного радиуса коммуникации между аппаратами: движение осуществляется так, чтобы граф коммуникации оставался связным. Существуют также подходы к обследованию областей сложной формы [75, 85].

Другой прикладной задачей, для решения которой исследуются подходы на основе групп АНПА, является поиск мин. Доклад [88] посвящен групповому алгоритму обследования заданной акватории на предмет наличия мин.

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

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

1.2. Существующие модели и алгоритмы для управления Имеется широкое многообразие моделей и алгоритмов, предложенных в настоящее время для управления группами роботов, обусловленное разнообразием решаемых в данной области задач. Согласно [14], стратегии децентрализованному управлению.

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

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

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

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

В различных условиях целесообразно применение различных стратегий управления. Например, как отмечено в [33], при возрастании количества участников группы и ограниченном времени принятия решения, приходится переходить к децентрализованным схемам. При децентрализованном управлении каждый участник рассматривается как самостоятельный агент, взаимодействующий с окружением. В случае, когда в качестве элементов группы рассматриваются не просто роботы, а некоторые абстрактные агенты, говорят о применении мультиагентного подхода [21, 22, 80]. В применении к АНПА в качестве агентов могут рассматриваться как сами аппараты [67, 74], так и отдельные задания в системе управления [13].

Задача распределения заданий внутри группы роботов (multi-robot task allocation /MRTA/) состоит в том, чтобы назначить имеющиеся задания (которые могут заключаться в требовании посетить заданную точку пространства, обследовать заданный участок и т. д.) роботам группы и определить порядок их выполнения. При этом необходимо минимизировать некоторый функционал, который может включать общее время выполнения задания, суммарный пройденный путь и т.д. Если рассматривать задачи данного типа с точки зрения формирования команд в рамках теории управления организационными системами [25], то они относятся к «задаче о назначении» (имеется ввиду не конкретная задача о назначениях, а собирательный образ подобных оптимизационных задач).

В работе [68] приводится классификация задач MRTA. Показано, что, несмотря на разнообразие постановок, они чаще всего сводятся к широко известным задачам дискретной оптимизации, таким как задача о назначениях или нескольких странствующих коммивояжёрах (multiple travelling salesman problem /MTSP/ [100]).

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

Другой класс алгоритмов — это алгоритмы коллективного планирования, возникающие в децентрализованных системах. Их использование целесообразно, например, для ситуаций, когда задания добавляются по мере работы группы или когда центральный узел недоступен. Такие алгоритмы предполагают некоторый процесс согласования при выборе заданий. Один из способов согласования в группировке роботов — аукционный метод. При появлении нового задания некоторые роботы делают «ставки», оценивая свои затраты для выполнения этого задания. Такие алгоритмы использованы в работах [70, 71]. Обзор аукционных методов проделан в статье [61]. В работах [36, 49, 56, 66, 98] приводятся алгоритмы решения специфических постановок задачи планирования и исследуются другие подходы.

Задачи, возникающие при исследовании моделей коллективного управления, могут быть решены с использованием итерационной процедуры согласования. Так, в работе [15] рассматривается итерационный алгоритм улучшения плана при коллективном управлении. Используется математическая модель задачи о назначениях: задаётся матрица, которая определяет вклад в целевой функционал для каждой пары робот – задача. Ставится задача максимизации данного функционала. Классическая задача о назначениях может быть решена за время порядка O(n3) с использованием «венгерского» алгоритма (здесь n – максимум из количества задач и количества исполнителей). Однако при этом необходимо, чтобы имелся единственный вычислитель, и матрица была известна ему целиком, что несправедливо при коллективном управлении. В работе предполагается составление оптимального плана и обмен отдельными заданиями или конструирование цепочек обмена.

Задача коллективного управления рассматривается и в докладе [23].

Ставится задача патрулирования или обследования большой акватории, разбитой на области. Каждой из областей назначен приоритет. Координатор каждой области может отдавать команды по переназначению АНПА областям. Считается, что каждый координатор не имеет полной информации о количестве аппаратов в его области. С использованием формализма дискретных событийных систем ([2, 99]) оценено число шагов перераспределения аппаратов между областями, через которое желаемо распределение будет достигнуто. С задачей патрулирования связана также работа [5], однако в ней используется другая фиксированным траекториям. При использовании коллективного управления в группе АНПА, одним из критически важных вопросов является обеспечение связи. Этому посвящён, например, доклад [57], в котором также рассматривается задача патрулирования, но исследование посвящено больше устойчивости гидроакустической связи.

Алгоритмы централизованного и коллективного планирования находят применение в системах управления группами роботов [41, 71, 81, 82, 105]. В системе ALLIANCE [82] рассматривается распределение заданий в группе разнородных роботов. Используются алгоритмы, основанные на «жадном»

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

Экспериментальный проект CENTIBOTS [81] посвящён управлению группой более чем из ста роботов для решения обследовательских задач в помещении. В каждый момент времени в системе имеется набор неподвижных целей, которые необходимо посетить. Планирование может осуществляться в двух режимах: централизованном и коллективном. В централизованном режиме план посещения целей строится на основе приближённого решения задачи MTSP с использованием «жадного» алгоритма. Коллективное планирование основано на методе аукционов. При этом отмечается, что в начале работы системы объем передаваемых об аукционах сообщений столь велик, что пропускная способность коммуникационной сети оказывается недостаточной. Система MissionLab используется в Georgia Institute of Technology для управления разнородными (летательными, наводными, подводными) аппаратами. Для решения задачи MRTA в ней используется аукционный метод [105].

В работе [16] исследована задача, в которой задано множество целей на плоскости и необходимо разработать план посещения как можно большего их количества аппаратами группы (т.е. используется модификация обыкновенной, «точечной» модели). Ставится задача оптимизации. Целевой функционал представляет собой сумму функционалов для каждого аппарата, наподобие того, который используется в задаче о назначениях. Добавляются ограничения на длину траектории каждого АНПА (что связано с ограниченностью запаса батареи) и ограничения на радиус коммуникации. Максимизация используемого функционала при заданных ограничениях не обязательно влечёт за собой посещение всех целей. Для решения поставленной задачи оптимизации используется генетический алгоритм, позволяющий гибко задавать ограничения на траектории аппаратов. Исследуются как траектории с возвратом в точку старта, так и разомкнутые траектории.

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

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

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

В докладе [72] рассматривается задача составления оптимального плана миссии для группы АНПА. Предлагается модель, в которой обследование прямоугольного участка акватории с помощью меандра является отдельным заданием. Миссия состоит из набора таких прямоугольников. Для i-ого прямоугольника рассматриваются координаты его центра (xi, yi) и алгоритм планирования использует евклидово расстояние между центрами прямоугольников как оценку времени перехода от одного задания к другому.

Такая модель пренебрегает размерами обследуемых прямоугольников, что справедливо лишь в случае, если расстояния между прямоугольниками намного больше их размеров. Для решения задачи MTSP, возникающей при реализации алгоритма планирования, предложено использовать метод колонии муравьёв (см. [62]). Данный метод является итерационным эвристическим. Ребру между двумя вершинами графа (вершины соответствуют прямоугольникам для обследования) i и j ставится в соответствие действительное число ij (т.н. «уровень феромона»). Строится случайный путь в графе. При добавлении нового ребра к пути, оканчивающемуся вершиной i, рассматриваются ij для всех j, ещё не входящих в путь и на её основе вычисляется вероятность попадания соответствующего ребра. В зависимости от стоимости полученного пути изменяются значения ij для входящих в него рёбер. С целью обобщения метода колонии муравьёв для формирования нескольких цепей в графе, в работе предлагается ввести параметр L0 – запрещённое расстояние.

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

В лаборатории подводных систем и технологий (LSTS) университета Порто (Португалия) ведётся разработка программного обеспечения для управления совместной работой разнородных автономных аппаратов (подводных, поверхностных, летательных) [60]. Унифицированная СПУ под названием DUNE [86] использует прикладной протокол передачи сообщений IMC [79] для обмена как между модулями СПУ на борту аппарата, так и для обмена сообщениями между аппаратами. Также разработан пульт оператора, позволяющий одновременно отслеживать состояние нескольких аппаратов.

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

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

Одной из СПУ АНПА с открытым исходным кодом является MOOSIvP [39]. На бортовом вычислителе аппарата одновременно работает несколько модулей, обменивающихся данными через общую память, называемую MOOSDB. Целевые параметры движения АНПА определяются с использованием функции полезности, заданной на основе возможных действий аппарата (см.

диссертацию [38]). Функция полезности формируется как взвешенная сумма нескольких одновременно работающих поведений. Областью, на которой определена такая функция, может являться трёхмерное пространство «курс– скорость–глубина». Например, при движении АНПА к заданной точке акватории могут действовать два поведения: одно формирует функцию полезности, которая тем больше, чем ближе курс АНПА к курсу на целевую точку; другое поведение даёт больший вес курсам, отворачивающим от препятствий. Перемещение аппарата на основе общей целевой функции позволяет добраться до заданной целевой точки, не столкнувшись с препятствиями. Для решения задачи оптимизации используется метод на основе представления целевых функций кусочно-линейным образом.

Алгоритмы группового управления в MOOS-IvP реализуются в виде дополнительных модулей. Так, в работе [59] предлагается групповое взаимодействие АНПА по следующей схеме. Имеется центральный узел, который является источником заданий (это может быть компьютер, контролируемый оператором, или АНПА, на который загружен полный план миссии).

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

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

Если аукционеру назначено задание, то он влияет на функцию полезности своего АПНА.

В настоящее время в основе систем управления АНПА лежат идеи гибридной программной архитектуры (см. [1]). В соответствии с ней вся система управления делится на три уровня:

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

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

Верхний уровень управления строит план действий в соответствии с имеющейся миссией и моделью среды.

Каждый уровень передаёт нижестоящему команды, а принимает данные, отражающие текущую обстановку. К гибридным СПУ относятся, например, DUNE [86], DSAAV [50] (университет Сингапура), СПУ ИПМТ ДВО РАН [1].

Некоторые СПУ используют иные принципы. Так, примером СПУ, основанной на поведениях, может служить MOOS-IvP [39]. В системе TRex [92] управление осуществляется на основе иерархической структуры по схеме восприятие – модель – план – действие.

Задача поиска ЛН и оценки их параметров и задача съёмки параметра среды с заданной точностью являются важными и актуальными.

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

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

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

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

Централизованное управление не требует процедур согласования между АНПА, как того требуют аукционные методы коллективного планирования.

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

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

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

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

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

ГЛАВА 2. ЦЕНТРАЛИЗОВАННОЕ ПЛАНИРОВАНИЕ МИССИИ

В ГРУППЕ АНПА

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

Миссия рассматривается как набор неделимых независимых заданий.

Каждое задание должно быть выполнено одним АПНА и не может быть прервано.

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

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

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

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

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

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

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

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

Необходимо также иметь возможность изменять состав группы и учитывать, какая часть общей миссии уже выполнена, а какая – ещё нет. Это особенно важно при выполнении миссии, в которой возможны сбои при запусках отдельных аппаратов. Так, например, в работе [89] опубликована статистика, согласно которой при поиске затонувшего самолёта рейса Air France 447 доля успешных запусков при использовании трёх АПНА Remus 6000 составила порядка 67%. Причинами ошибок являются, помимо сбоев оборудования, и ошибки в программировании миссии.

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

Будем считать, что миссия представляет собой набор заданий. Типичное задание для АНПА – проход по отрезку на заданной глубине с включённым датчиком (например, с гидролокатором бокового обзора). Несколько проходов по отрезку позволяют осуществить площадную съёмку. Примером более сложного задания является оконтуривание неоднородности морской среды [30]. Для простоты планирования будем считать задания неделимыми, т.е. каждое задание должен выполнить единственный аппарат, не останавливаясь в процессе выполнения.

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

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

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

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

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

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

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

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

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

Аппарат включён в состав миссии.

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

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

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

Пусть имеется 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..vi для всех k 1.. | p |. Выполнение плана q-ым аппаратом начинается в точке sq в момент времени uq. Вначале аппарат переходит к точке a i, j и выполняет j1-ый вариант задания i1. Затем аппарат переходит к точке a i, j и выполнения плана p аппаратом с номером q есть Общим планом является кортеж планов P = (p1, p2, …, pm) такой, что каждое задание встречается среди его планов ровно один раз и ровно в одном варианте.

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

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

Задача составления плана сходна с задачей коммивояжёра (TSP), для которой существуют методы получения как точных, так и приближённых решений, которым посвящены книги [35, 54, 100]. Полученная задача является более широкой её версией из-за наличия нескольких коммивояжёров и более сложной постановки: при планировании не просто посещаются вершины некоторого графа, а является существенным, какой вариант выполнения задания будет выбран. Задача коммивояжёра получается из задачи (3) при следующих упрощающих предположениях: m = 1, vi = 1, ai,1 = bi,1, li,1 = 0, uq = 0.

Известна также задача нескольких коммивояжёров (см., например, книгу [100]). С помощью дополнительного построения она сводится к TSP (добавляются фиктивные вершины, посещение которых означает смену коммивояжёра). Однако её стандартная постановка подразумевает минимизацию суммы пути, пройденного каждым коммивояжёром, а не минимизацию максимума (см.

выражения (2) и (3)). Решение подобных задач относят также к области исследования операций и теории расписаний [11]. В данной области имеется ряд моделей, как правило, приводящих к задачам дискретной оптимизации. Одни задачи такого рода допускают алгоритм решения с полиномиальным временем работы (задача о назначениях, задача о выборе заявок [19], задача Джонсона), для других полиномиальные алгоритмы неизвестны (задача построения расписаний программных движений промышленных роботов).

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

2.2. Алгоритмы составления оптимального плана Алгоритмы для решения TSP можно поделить на два класса: точные и приближённые. К приближённым относятся различные эвристические стратегии (например, жадная стратегия, эвристика Кристофидеса и др.) и итерационные алгоритмы (генетические алгоритмы, метод отжига, эвристика Лина-Кернигана и др.). Для различных алгоритмов существуют оценки в худшем (как для эвристики Кристофидеса), так и в среднем случае. К точным алгоритмам решения TSP относятся полный перебор, алгоритм Хельда-Карпа, методы, основанные на LPрелаксации исходной задачи и др. При этом для некоторых успешных методов, основанных на построении LP-релаксации (им посвящена книга [35]), не существует в настоящее время достаточно точных оценок времени работы.

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

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

2.2.1. Модификация алгоритма Хельда-Карпа Данный алгоритм доставляет точное решение задачи (3). Он основан на идее динамического программирования и представляет собой модификацию алгоритма Хельда-Карпа [69], решающего задачу коммивояжёра. Исходная постановка TSP такова: имеется полный граф (с множеством вершин V), каждому ребру которого сопоставлено число – стоимость ребра. Необходимо построить цикл минимальной стоимости, проходящий по всем вершинам ровно один раз. В алгоритме Хельда-Карпа предлагается решать задачу методом динамического программирования. Не ограничивая общности, будем строить искомый цикл, начиная с некоторой вершины r V, каждый раз добавляя к пути новую, еще не взятую вершину. Состояние такого процесса описывается (для фиксированного r) парой (r’, V’), где r’ – последняя добавленная вершина, а V’ – множество уже добавленных вершин (V’ V). Обозначим за B(r’, V’) стоимость минимального пути, описываемого парой (r’, V’). Очевидно, что B(r, {r}) = 0. Остальные значения могут быть найдены с использованием простых правил перехода. Зная все значения B(r’, V) легко найти длину кратчайшего цикла, которая составит min( B( r ',V ) c( r ', r )), где c(r’, r) – стоимость ребра из r’ в r.

Вернёмся к нашей задаче для нескольких аппаратов. С помощью двоичного поиска задача сводится к следующей: найти план со временем выполнения не более T ', либо установить, что его не существует (если плана не существует, T ' следует увеличить, иначе – уменьшить). Для решения последней задачи применим составление плана для каждого подводного аппарата, при этом будем осуществлять лишь такие переходы, при которых время выполнения не превысит T '. Состояние системы описывается тройкой (q, S, x), где q – номер текущего аппарата, S – подмножество заданий, которые уже включены в план, x – точка, в которой в конце текущего плана будет находиться аппарат q. Точка х может быть поскольку в конце плана аппарат либо находится в своём начальном положении (если план пуст), либо в конечной точке последнего задания, выполненного в соответствующем варианте.

Обозначим за ~ ' ( q, S, x ) минимальное время выполнения плана для q-ого аппарата, в следующем состоянии: для аппаратов 1..q–1 планы уже построены и время выполнения каждого из них не превышает T ', использованы задания из подмножества S, текущий план для аппарата q заканчивается в точке x. Если такое состояние невозможно, то положим ~ (q, S, x). Первоначально известно, что ~ (1,{}, s ) u, что означает, что аппарат 1, не выполнив ни одного задания, будет находиться в точке s1 через время u1. Далее, используем следующие правила перехода:

Правило перехода (4) служит для завершения формирования плана аппарата с номером q – 1 и начала формирования плана для аппарата q. При этом если для заданного S время выполнения оптимального плана для АНПА с номером q - превышает T ', это значение S не может быть использовано для дальнейшего формирования плана на данном шаге. Правило (5) используется для добавления задания i в варианте выполнения j к текущему плана аппарата q. При этом аппарат переходит в точку bi,j, приводя, таким образом, процесс планирования в состояние ~ ( q, S {i}, b ). При этом, перед добавлением задания i план АНПА j был либо пуст, либо уже содержал задание i1. Этому соответствует два аргумента минимума в выражении (5). Во втором случае следует также перебрать вариант j выполнения задания i1. Искомый план со временем выполнения не более T ' существует тогда и только тогда, когда Восстановив аргументы, на которых достигается минимум выражения (5), несложно получить и сам план.

Полученный алгоритм представлен на рис. 1. Здесь T – оценка ответа сверху, - величина, на которую допускается превышения стоимости плана над оптимальной. Основная часть алгоритма представляет собой цикл из шагов 6-15, проходящий по состояниям. Он выполняется на каждой итерации двоичного поиска. Условие на шагах 20-21 служит для того, чтобы таблицы состояний содержали успешно построенный план по окончании поиска. Шаги 22- представляют собой алгоритм восстановления оптимального плана.

Количество итераций двоичного поиска не превосходит log(T / ) + 1.

Количество итераций основного цикла динамического программирования, определяемого на шаге 6, не превосходит 2n m (m + N), где N i1..n vi. При этом внутренний цикл, определяемый на шаге 11, состоит не более чем из N итераций.

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

15.

17.

18.

19.

20.

21.

22. q m; S {1,...,n}; k arg min ~ ' ( m,{1,..., n}, X k ) T ' ;

23. пока q 1 или |S| > 0:

24.

25.

26.

27.

28.

29.

30.

Рис. 1. Модифицированный алгоритм Хельда-Карпа.

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

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

позиция нового задания в текущем плане аппарата;

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

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

полиномиальным по сложности и эвристическим. Вычисление новой стоимости плана на шаге 8 может быть произведено за время O(1), поскольку получается простым пересчётом из стоимости уже существующего плана. Циклы шагов 5 и дают не более n + m итераций, в то время как циклы шагов 3 и 7 дают множитель N. Шаг 11 не влияет на асимптотику, поскольку требует O(n) шагов. Таким образом, асимптотическая сложность алгоритма есть O(N (n + m)).

сохранением полиномиального времени работы. В изложенном алгоритме предполагается, что при вычислении стоимости нового плана на шаге 8, варианты используемых вариантов заданий, даже без изменения порядка их выполнения, может давать план с меньшим временем выполнения. Построим алгоритм на основе метода динамического программирования, который позволяет по заданным i1, i2, …, i|p| найти набор j1, j2, …, j|p| для составления оптимального плана аппарата p = (i1, j1), (i2, j2), …, (i|p|, j|p|). Такой алгоритм может быть использован для улучшения плана, найденного с использованием любого приближённого метода.

в позицию k.

10.

вставить вариант j1 задания i в позицию k1 плана p q1 ;

11.

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

для k > 1, j 1..vi. Последовательно вычисляя tq (k, j ) для всех k, получаем оптимальное время плана аппарата как минимальное tq (| p |, j ) по всем j 1..vi.

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

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

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

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

Различие в бортовом оборудовании аппаратов может быть учтено введением матрицы назначений B, где Bq,i равно либо 0, либо 1 в зависимости от того, может ли задание q быть выполнено аппаратом i. Учёт ограничений данного вида не требует существенной модификации изложенных алгоритмов.

Влияние динамики АНПА на время выполнения заданий. При достаточно протяжённых траекториях данным фактором можно пренебречь. К примеру, при выполнении галса длиной 1000 м на типичной скорости 1 м/с, время поворота АНПА на 90, приблизительно равное 10 с., составляет лишь 1% от общего времени выполнения задания. Однако данный фактор становится более существенным при выполнении более коротких траекторий. Тем не менее, изложенная постановка задачи уже допускает учёт эффектов, рассматривать ai,j, bi,j, sq не как точки трёхмерного пространства, а как векторы состояния АНПА, включающие, например, его курс. В таком случае, для вычисления стоимости переходов и времени выполнения каждого задания, следует использовать динамическую модель АНПА, вычисляя с её помощью ответы на запросы вида «сколько времени необходимо для перехода из состояния a в состояние b?».

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

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

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

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

Показано, как в рамках предложенной модели может быть произведён учёт различных дополнительных факторов.

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

ЗАДАННОЙ ТОЧНОСТЬЮ, ИСПОЛЬЗУЮЩИЙ ГРУППУ АНПА

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

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

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

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

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

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

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

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

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

характеристик ее локальной окрестности. При обходе области класса i обеспечивается расстояние hi (шаг) между галсами при проходе по ней. При этом шаги связаны между собой соотношением: hi+1 = qhi.

На рис. 3 показана используемая траектория типа меандр с переменным шагом. АНПА начинает съемку заданного участка обычным меандром с максимальным шагом h1 (галсы А, В и С). Если в процессе съемки (галс В) будет обнаружен более изменчивый участок поля (класс 2), то следует организовать более частое обследование и выполнить маневр В1–В5. При этом расстояние между галсами B2 и B4 составляет 2h2, однако, с учетом уже выполненного галса B, обеспечивается необходимое расстояние h2 между галсами в области класса 2.

В процессе выполнения маневра В1–В5 может возникнуть необходимость в еще более детальной съемке (область класса 3), которая реализуется аналогично меандром с шагом h3 (галсы В41-В45) и так далее.

Для определения константы q рассмотрим ситуацию, в которой область, состоящая из точек класса k, пересекает два соседних параллельных галса первоначального меандра (например, A и B на рис. 3). В соответствии с алгоритмом, вдоль этих галсов будут совершены дополнительные маневры для классов 2, 3, …, k. Таким образом, вдоль B будут следовать параллельно ему дополнительные галсы, подобно B4 и B44 на рис. 3. Самый дальний галс будет отстоять от B на расстояние L = h2 + … + hk, то есть L = h1(q + … + qk-1).

Аналогично, параллельно галсу A будут располагаться галсы, самый дальний из которых будет отстоять на то же расстояние L от него. Для полного покрытия необходимо обеспечить расстояние hk между двумя наиболее удаленными галсами (один от A, другой – от B). Таким образом, необходимо, чтобы выполнялось соотношение h1 – 2L = hk, т.е. имеем уравнение:

откуда следует, что q = 1 / 3.

Рис. 3. Траектория движения типа меандр с переменным шагом для АНПА.

На вход алгоритма поступает отрезок для обследования (ab – очередной галс или фрагмент галса), параметры метода и параметры рекурсии. Сокращение времени операции по сравнению с обыкновенной реализацией достигается за счёт дополнительного обследования «на месте». В случае если по ходу движения осуществляется рекурсивный вызов процедуры обхода с меньшим значением h (см. рис. 4 и рис. 5).

Рис. 4. Формирование траектории при рекурсивном вызове.

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

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

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

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

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

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

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

если точность не достигается для y на расстоянии h / (23i–1) от x 11.

12.

14.

16.

17.

18.

19.

23. перейти к шагу 5;

Для принятия решения об изменении шага меандра предположим, что измеряемое поле Z является реализацией случайного процесса. Такой подход применяется в геостатистике [10]. Если характеристики случайного процесса одинаковы во всей рассматриваемой области, то он является стационарным. В нашем случае предположение о различных статистических характеристиках Z на различных участках означает, что процесс не является стационарным. Таким образом, с одной стороны, при формировании критерия следует использовать расположенных к текущей. С другой стороны, меньшая выборка обеспечивает формирования выборки рассмотрим работу алгоритма, изложенного выше. При движении АНПА вдоль отрезка сформированной траектории, наиболее близкие точки, в которых были произведены измерения – это последний участок проделанных измерений. Необходимо сформировать критерий, позволяющий отнести текущую точку x к одному из классов. Для этого необходимо на основе имеющейся выборки оценить величину ошибки, которая будет допущена после интерполяции в точках между галсами. Будем оценивать ошибку в точке y, равноудалённой от двух соседних галсов, т.е.

Критерий 1. Обозначим рассматриваемый случайный процесс за Z, а результат измерения в точке x за zx. Если существуют и известны плотности распределения f (в том числе и совместные) в каждой точке рассматриваемой области, то ошибка может быть оценена на основе условного распределения Z(y) | Z(x) = zx:

Теперь, если при интерполяции используется значение zy для аппроксимации исследуемого параметра в точке y, то вероятность совершить ошибку более чем на определяется выражением:

К примеру, если известно, что Z – стационарный гауссов процесс со средним и изотропной ковариационной функцией K, то имеем (см. [93]):

необходимости дополнительного обследования вблизи точки x:

1. На основе M последних измерений z1, z2, …, zM, произведённых в точках x(1), x(2), …, x(M) оценить выборочное среднее z и корреляционную функцию процесса вблизи точки x:

2. На основе выражений (13) и (14) оценить вероятность того, что Z(y) отклонится от среднего более чем на. При этом вместо и K использовать z и K соответственно.

3. В случае если вычисленная вероятность превышает порог r, произвести обследование на уровне i.

Критерий 2. В случае если гауссова модель не применима к исследуемому (критерий 2). В предположении, что рассматриваемый процесс стационарен вблизи x, имеем (см. [10]):

В качестве критерия необходимости дополнительного обследования уровня i рассмотрим следующее условие:

или с учётом (16) и (11):

Критерий 2, в отличие от критерия 1 не использует дополнительных предположений о распределении величин Z, и поэтому не даёт оценок вероятности, с которой будет соблюдена точность.

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

вычислительных экспериментов.

Использовались искусственно сгенерированные данные, которые были получены с использованием модификации алгоритма последовательного гауссова стохастического моделирования (см. разд. 5.1.2 и рис. 6).

Рис. 6. Пример искусственно сгенерированных данных, использованных в Данные заданы на равномерной прямоугольной сетке размером 1200 700.

Расстояния измеряются в шагах сетки. Основная часть сгенерированного скалярного поля представляет собой реализацию гауссова процесса с ковариационной функцией K ( h ) exp( h 2 / 1002 ). Однако, в центре поля, в квадрате размером 200 200 сгенерированы данные с ковариационной функцией K ( h ) exp( h 2 / 202 ). Итоговое поле получено как сумма двух сгенерированных полей (см. разд. 5.1.2). Таким образом, искусственно сгенерировано поле, имеющее различные статистические характеристики на различных участках.

Исследуемый параметр среды принимает значения из отрезка [-5,54; 6,04].

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

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

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

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

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

Результаты наиболее показательных экспериментов собраны в таблице 1. В экспериментах №1–3 шаг базового меандра составлял 87 шагов сетки, в эксперименте №4 – 70 шагов.

В эксперименте №1 использовался «идеальный критерий»: решение о необходимости дополнительного обследования уровня i принималось исходя из значений в ячейках сетки на расстоянии от 1 ячейки до h / (2 · 3i – 1), расположенных на прямой, перпендикулярной галсу. Использовалось значение = 0,5. При этом ошибка восстановления параметра находится в диапазоне [–; ] за исключением нескольких узлов сетки (общее количество которых составляет 0,0067% от общего числа узлов), в которых величина ошибки превысила заданный порог из-за различия между предполагаемым и действительным расстоянием между траекториями.

Детальная информация о распределении ошибок представлена на логарифмической гистограмме на рис. 7а. На данной гистограмме представлены две выборки. Количество элементов в каждой выборке равно количеству узлов сетки. Первая выборка образована значениями Z – Z1 и обозначена кодом «МПШ». Она представляет собой ошибки восстановления поля в узлах сетки, исходя из известных значений вдоль траектории меандра с переменным шагом.

Аналогично, вторая выборка обозначена кодом «ОМ» и образована значениями Z – Z2. Из гистограммы видно, что меандр с переменным шагом, построенный по «идеальному критерию», приводит к ошибкам восстановления, находящимся в заданных пределах. В то же время, обыкновенный меандр такой же длины имеет разброс ошибки от -4 до 5, однако количество узлов сетки с ошибкой восстановления, близкой к нулю, также больше. Можно сказать, что необходимая точность обследования у меандра с переменным шагом при той же длине траектории, что и у обыкновенного меандра, достигается благодаря «искривлению» гистограммы ошибок.

Эксперимент №2 иллюстрирует работу меандра с переменным шагом, использующего критерий 1 (см. раздел 3.2). Перед оценкой корреляционной функции из текущей выборки вычитался линейный тренд. Использовалось значение r = 0,954 (два сигма), глубина рекурсии была ограничена числом 3.

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

Соответствующая логарифмическая гистограмма ошибок представлена на рис. 7б.

В данном эксперименте меандр с переменным шагом позволяет восстановить исследуемый параметр среды с ошибкой в пределах [-1,69; 2,06], в то время как обыкновенный меандр той же длины даёт ошибку в пределах [-5,00; 5,49].

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

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

дополнительного обследования лежат в диапазоне 17500–22600 (шаг сетки полагается равным единице). Минимальный шаг, использованный меандром с переменным шагом, составил 9 единиц. Это соответствует длине траектории 95500 единиц для обыкновенного меандра, что в 4,2–5,4 раз длиннее траектории, полученной с помощью предложенного алгоритма. Данный показатель изменяется от поля к полю и зависит, в том числе, от соотношения площадей областей различных классов.

Таблица 1. Результаты вычислительных экспериментов, сравнивающих меандр с АМ, = 0.5, критерий АМ, = 0.5, критерий Рис. 7. Сравнение логарифмических гистограмм Z – Z1 (меандр с переменным шагом /МПШ/) и Z – Z2 (обыкновенный меандр/ОМ/): а) эксперимент №1, Положим, что область обследования – это прямоугольник размером W по первой оси и h(n – 1) по второй, а начало координат поместим в один из его углов.

Сформулируем задания для задачи (3):

Здесь Uq – оптимальная скорость движения АНПА с номером q. План с меньшей стоимостью может быть получен дроблением отрезков, соединяющих точки ai,j и bi,j. Предполагается, что uq = 0 и известны начальные положения аппаратов sq.

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

Рис. 8. Результаты работы алгоритмов в процессе съемки модельной карты на На рис. 8 приведены траектории движения группы из трех АНПА, сформированные в процессе съемки модельной карты в вычислительном эксперименте №2. Все АНПА начинают работу, находясь в верхнем левом углу заданной прямоугольной области. Траектории первого, второго и третьего АНПА отображены непрерывной, пунктирной и точечной линиями соответственно.

Имеется 9 галсов, каждый из которых разделён на 3 равные части. В результате имеется 27 заданий, пронумерованных от 0 до 26 сверху вниз слева направо.