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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

005007933 ^

АМЕЛИН Константин Сергеевич

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

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

2 6 Я Н 3 2012

Санкт-Петербург 2012

005007933

Работа выполнена на кафедре системного программирования математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель:

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

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

доктор физико-математических наук, профессор ГРАНИЧИН Олег Николаевич

доктор технических наук, профессор ТИМОФЕЕВ Адиль Васильевич (Санкт-Петербургский институт информатики и автоматизации РАН)

доктор физико-математических наук, профессор МЕЛАС Вячеслав Борисович (Санкт-Петербургский государственный университет)

Институт проблем управления им. В. А. Трапезникова РАН (Москва)

Защита состоится " 2012 года в <£[¿2 часов на заседании сове-

та Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., 28, Математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан "¿С? " ^¿¿г/'^с 2012 г.

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

диссертационного совета __-____ Кривулин Н. К.

/ / (' /

Общая характеристика работы

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

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

а в остальном они могут быть произвольными. Такая постановка задачи рассматривается в работах Ю.С. Кана, А.И. Кибзуна, A.B. Куржанского, А.Р. Панкова, Б.Т. Поляка, К.В. Семенихина, Р. Темпо, В.Н. Фомина, Ф.Л. Черноусько, П.С. Щербакова и др. Применение фильтрации в системах навигации мобильных планеров исследовалось В.Д. Андреевым, В.Н. Васильевым, O.A. Бабичем, A.B. Осиповым, O.A. Степановым и др. Для оценки случайных процессов в системах навигации мобильных объектов достаточно часто и эффективно применяется фильтр Калмана, который удовлетворительно работает на больших мобильных объектах с разнообразным навигационным оборудованием. Для легких мобильных объектов задача снижения уровня отклонения от заданной траектории движения остается открытой, так как влияние на них сопутствующих неопределенностей более значительно.

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

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

щена монография О.Н. Граничина и Б.Т. Поляка "Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах". Рассматриваемый в этой книге новый тип рандомизированных алгоритмов стохастической аппроксимации, называемых в англоязычной литературе Simultaneous Perturbation Stochastic Approximation (SPSA), был предложен в работах О.Н. Граничина, Б.Т. Поляка и А.Б. Цыбакова, Дж. Спалла, Х.-Ф. Чена, Т. Дункан и Б. Пасик-Дункан. Они основаны на аппроксимации градиента вдоль случайно выбранного направления — рандомизации, которая опирается на некоторые контролируемые случайные величины, влияющие на результаты наблюдений, существующие в системе или добавляемые экспериментатором. Эти алгоритмы относятся к более широкому классу методов случайного поиска, которые ранее в русскоязычной литературе исследовались, например, в работах С.М. Ермакова, А.А. Жиглявского, А. Жилинскаса, В.Б. Ме-ласа, JI.A. Растригина, Ю.А. Сушкова и др. В отличие от предлагавшихся ранее методов рандомизированные алгоритмы стохастической оптимизации обеспечивают состоятельность оценок при существенно менее значительных предположениях о свойствах неизвестной функции потерь и помех в измерении ее значений.

Использование группы мобильных объектов позволяет увеличить эффективность выполнения задач поиска, мониторинга или исследования территории с применением алгоритмов распознавания образов к данным газоанализаторов, тепло-датчиков, фото- и видео- регистраторов. Современные алгоритмы теории распознавания образов, классификации и кластерного анализа базируются на работах С.А. Айвазяна, В.Н. Вапника, Ф. Розенблата, Р.А. Фишера, В.Н. Фомина, И. Фор-джи, К. Фукунаги, Дж. Хартигана, А.Я. Червоненкиса, Я.З. Цыпкина, В.А. Якубовича и др. Многие современные системы распознавания образов основаны на принципах нейронных сетей (А.В. Тимофеев, С. Хайкин, Ф. Уоссерман и др.).

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

взаимодействия.

Цель достигается в диссертации через решение следующих задач:

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

2. Разработка и исследование методов выбора направления движения легкого мобильного объекта для уменьшения отклонения от заданной траектории при действии помех.

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

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

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

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

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

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

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

Научная новизна. Все основные научные результаты диссертации являются новыми.

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

Предложенные новые методы могут быть использованы при решении современных практических задач. Разработанные математическое обеспечение оптимизации движения, архитектура и технология программирования программно-аппаратного комплекса для исследования и мониторинга территорий с помощью группы мобильных объектов позволяют повысить качество проводимых работ по решению задач исследования территорий с применением фото- и видео- регистраторов и алгоритмов распознавания образов. При этом разработанная архитектура и математическое обеспечение могут применяться как в уже существующих комплексах, так и стать основой для создания новых. Разработанное программное обеспечение для группового взаимодействия, автоматической фотосъемки, сохранения и передачи данных представляет собой самостоятельную практическую ценность. Апробация работы. Материалы диссертации докладывались на семинарах кафедры системного программирования СПбГУ, на российских и международных конференциях по программированию, информатике, оптимизации и теории управления: XXVII конференции памяти H.H. Острякова (12-14 октября 2010 г. Санкт-Петербург, Россия), Второй и Третьей традиционных всероссийских молодежных летних школах "Управление, информация и оптимизация" (2010 гг. и 2011 гг.), Первой российской MeeGo конференции (Москва, 11 марта 2011 года), 5th International Conference on Physics and Control (PhysCon 2011) (5-8 September, 2011, Leon, Spain), международной конференции "Science and Progress 2011" (Санкт-Петербург, Россия, 14-18 ноября, 2011 г.), международной научно-практической мультиконферен-ции "Управление большими системами" (УБС 2011) (Институт проблем управления

им. В.А. Трапезникова РАН Москва, 14-16 ноября 2011 г.).

По материалам диссертации было получено свидетельство об официальной регистрации программы для ЭВМ № 2010612684 "SmartFly Together" от 19 апреля 2010 г. Результаты диссертации использованы при выполнении работ по проекту "Мультиагентная система для управления группой легких беспилотных летательных аппаратов" в рамках программы "СТАРТ-10" Фонда содействия развитию малых форм предприятий в научно-технической сфере. Выполненный в ходе работы над диссертацией проект "Сетевое адаптивное управление группой легких беспилотных летательных аппаратов на основе мультиагентного подхода" был отмечен дипломом победителя конкурса грантов Санкт-Петербурга для студентов, аспирантов, молодых ученых, молодых кандидатов наук 2011 г.

Публикации. Основные результаты диссертации опубликованы в работах [1-17]. Из них три публикации [1-3] в журналах из перечня ВАК. Работы [1-6, 9-14] написаны в соавторстве. В работах [1, 2, 9-11] О.Н. Граничину принадлежат общие постановки задач, а К.С. Амелину - реализация описываемых методов, доказательства, создание демонстрационных примеров и программных средств. В [3] К.С. Амелиным получены и описаны основные практические результаты. В [4, 6, 12-14] К.С. Амелиным описаны технические характеристики разработанных комплексов беспилотных летательных аппаратов и предложены методы их практического применения в задачах распознавания образов. В зарегистрированной программе для ЭВМ [5] К.С. Амелиным разработаны программные компоненты для автопилота мобильного объекта.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы, включающего 125 источников. Текст занимает 90 страниц, содержит 15 рисунков и одну таблицу.

Содержание работы

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

В первой главе "Группа мобильных объектов для распознавания образов" вводятся основные понятия и постановки задач исследования, дается исторический контекст развития автономных мобильных объектов, рассматриваются преимуще-

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

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

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

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

В п. 1.3 описывается метод организации групповой работы мобильных объектов на примере мониторинга экологической обстановки с применением фоторегистраторов и алгоритмов распознавание образов. Протоколы взаимодействия мобильных объектов между собой и с базовыми станциями позволяют оперативно аккумулировать в центре обработки данных (ЦОДе) данные фотосъемок с "привязкой" их к координатам и времени. При этом возможно перераспределение заданий между отдельными мобильными объектами в ходе выполнения задачи. Определение аномалий на поверхности осуществляется по полученным фотоматериалам с помощью алгоритмов распознавания образов. Результаты распознавания можно оперативно использовать для корректировки заданий группе мобильных объектов.

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

В п. 2.1 предлагается для оценивания неизвестных параметров динамической системы управления по конечному числу наблюдений при произвольных внешних помехах добавлять рандомизацию к используемой стратегии управления. Рассматривается объект управления (ОУ)

у1 = С<г{г'1)щ + у1, 1 = 0,1,..., N, (1)

со скалярными входами щ и выходами Помехи г>г описывают все другие источники кроме и(, которые вызывают изменения в уи г"1 — оператор задержки: = Щ-1. Передаточная функция имеет вид (^»(г-1) =

где

АДА) = 1 + а^А + • • • + С А"*, ВДА) = Ь\ А' + б',+1А1+1 + • • ■ +

натуральные числа па,пь — порядки модели по выходу и входу (управлению); I — задержка в управлении, 1 < / < щ. Часть из коэффициентов о^, Ь{ неизвестна, и для них требуется определить с заданной вероятностью области достоверности по наблюдениям выходов {у(} на конечном интервале времени í = 1,2,...,ЛГ и известных входов (управлений) {«¿}, которые можно выбирать.

Пусть (47,Р) — вероятностное пространство, в <па+щ-1 + 1— положительное целое число (обычно равное количеству неизвестных параметров объекта (1)), N = в • А'д с некоторым ЛГд.

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

!Д„ + й,п_(, ¿ = 0,

п = 0,..., ЛГд - 1,

г = 1,2,...,в - 1,

где {й,} — "собственно" управление, которое определяется некоторым регулируемым законом обратной связи щ = Ы^у^ уг-1, ■ • •, Щ-1, ■ ■ ■), t > 0, = 0, к > 0.

В диссертации вводится вектор параметров 0„, находящийся во взаимно-однозначном соответствии с набором неизвестных коэффициентов ОУ (1), и для любого к 6 {1,2,. ..,5} описан способ построения содержащих его множеств &к, использующий два целочисленных параметра д и М, выбираемых пользователем. Вероятность того, что принадлежит каждому из Ок, к = 1,2,...,в, дается в теореме 2.1: Если пользователь может выбрать Д„ и этот выбор не влияет на внешние шумы ут,..., иг(„+1)_1, тогда Р{0» е б*} = 1 — 2д/М. Получаем доверительные интервалы, которые могут использоваться в адаптивных стратегиях

принятия решения.

В п. 2.2 рассматривается задача предсказания (фильтрации) случайного процесса {0(}, 6 К®, порождаемого линейным фильтром

0т=Аб(+и>(+1, (2)

в котором А — известная матрица: || А || = у Агпах(ААт) < 1, а {/ш(} - последовательность одинаково распределенных, центрированных независимых случайных векторов с ограниченной ковариационной матрицей, на основании наблюдений скалярного сигнала

Ш = ¥>¿01 + (3)

представляющих собой смесь преобразованного векторного процесса и помехи наблюдения Здесь и далее <рь — известные в моменты времени Ь 5-мерные вектора входов (регрессоров), которые представляют собой последовательность независимых одинаково распределенных случайных векторов с известными конечными математическими ожиданиями Е(р(, ковариационными матрицами и ограниченными четвертыми моментами, Лшах(А) — максимальное собственное значение матрицы А.

Если случайные вектора Д( = — имеют симметричные относительно нуля функции распределения, то для рандомизированного алгоритма построения очередной оценки предсказания

в1+1 = А0( - аАГД^е, 00 е К", (4)

где Ь = 1...., а > 0 — размер шага и Г — положительно определенная симметричная матрица, е1 — —1/( — невязка, в теореме 2.3 получены среднеквадратичные оценки для качества предсказания при условиях, когда последовательность помех наблюдения {ч(}(>1 представляет собой либо значения детерминированной неизвестной ограниченной функции, либо при каждом í — реализацию случайных величин, которые независимы с Д( и ограничены в среднеквадратическом смысле.

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

В п. 2.3.1 рассматривается упрощенная модель движения воздушного или на-

земного мобильного объекта, который перемещается в плоскости с постоянной по модулю скоростью о (крейсерская скорость объекта о г» 20 м/с) и подвержен действию бокового воздействия с постоянной по величине скоростью 6 -ф- О, Ь « а (например, ветра с Ъ ~ 2 — 3 м/с) и переменным направлением 6 К, удовлетворяющим модели (2) с в = 1 и А = 1. Задана целевая точка (А, В). В каждый момент времени 4 надо выбрать управляющее воздействие щ, задающее курс движения. Показания с ГЛОНАСС/СРЭ приемника поступают в систему набором данных с интервалом времени 5, т. е. в момент времени Т4 = То + Й поступают пары чисел (ж(,374), которые являются измерением текущей позиции (х(, уг) с некоторой ошибкой (еггх,еггу).

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

и, = М(0т), Щв) = -зтв. (5)

а

При неизвестных в(+1 для предсказания (определения) их значений по наблюдениям {(хь у^}к<л при отсутствии каких-либо существенных предположений о внешней помехе ь^ предлагается использовать рандомизированный алгоритм (4) с А = Г = 1, невязкой е(, равной отклонению от заданного в предыдущий момент времени курса, и сгенерированном пробном рандомизированном возмущений Д( — последовательности независимых, одинаково распределенных случайных величин, равных ±/3 с одинаковой вероятностью Константы а и /3 — параметры алгоритма. Для формирования управлений щ предлагается использовать стратегию (2) с в = 1 = Цд и Щу(, У1-1, ■■■, Щ-11 • • ■) = ¡¿<¿¡¡+1)-

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

Для увеличения продолжительности полета группы воздушных мобильных объектов в литературе описаны возможности использования восходящих термических

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

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

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

В п. 3.2 описывается технология программирования бортовых микрокомпьютеров мобильных объектов группы. Возможности перепрограммирования автопилота позволяют реализовать алгоритмы оптимизации полета и взаимодействия с микрокомпьютером среднего уровня, основные задачи которого — генерация обновлений маршрута для автопилота, работа с дополнительным оборудованием (фотокамерой, средствами связи и т. п.), обмен информацией с другими мобильными объектами, обмен информацией с базовой станцией и ЦОДом.

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

распознавания образов.

В заключении диссертации подведены итоги проведенного и завершенного в рамках поставленных задач исследования.

Работы автора по теме диссертации

Статьи в журналах, рекомендованных ВАК:

[1] Амелии К.С., Граничим О.Н. Мультиагентиое сетевое управление группой легких БПЛА // Нейрокомпьютеры: разработка, применение. 2011. № б. С. 6472.

[2] Амелии К. С., Граничим О.Н. Возможности рандомизации в алгоритмах предсказания калмановского типа при произвольных внешних помехах в наблюдении // Гироскопия и навигация. К» 2(73). 2011. С. 38-50.

[3] Рипгп Y.O., Shtukenberg A.G., Smetannikova O.G., Amelin K.S. Plagioclasc twin associations from the basic volcanic rocks of the Kamchatka, RUSSIA: Growth conditions and formation mechanisms // European Journal of Mineralogy. V. 22. No. 1. 2010. P. 139-145.

Другие публикации:

[4| Амелии К.С., Антал Е.И., Васильев В.И., Граничина Н.О. Адаптивное управление автономной группой беспилотных летательных аппаратов // Стохастическая оптимизация в информатике. Т. 5. 2009. С. 157-166.

[5] Амелин К.С., Антал Е.И., Васильев В.И., Граничин О.Н., Граничипа И.О. Программы для ЭВМ "SmartFly Together". Свидетельство о государственной регистрации программы для ЭВМ №2010612684 от 19 апреля 2010.

[6] Амелин К.С., Граничин О.Н., Кияев В.И. Мобильность или супервычисления. Кто кого? // Суперкомпьютеры. № 4 (4). 2010. С. 30-33.

[7] Амелин К. С. Легкий беспилотный летательный аппарат для автономной группы // Стохастическая оптимизация в информатике. Т. 6. 2010. С. 117-126.

[8] Амелин К. С. Мультиагентная система для управления группой легких беспилотных летательных аппаратов // Труды Второй традиционной всероссийской молодежной летней школы "Управление, информация и оптимизация". 2010. С. 9-18.

/

[9] Амелин К.С., Грапичип О.Н. Работоспособность алгоритмов предсказания калмановского типа и возможности рандомизации при неизвестных, но ограниченных помехах в наблюдении // В сб. тр. XXVII конференции памяти выдающегося конструктора гироскопов Н.Н. Острякова. — СПб. 2010. С. 33.

[10] Amelin К., Granichin О. Multiagent network control for the group of UAVs //In Proc. of the 5th International IEEE Scientific Conference on Physics and Control (PhysCon 2011). Leon, Spain. Sept. 2011. P. 64.

[11] Амелии К.С., Грапичип О.Н. Новые рандомизированные алгоритмы в управлении и обработке данных // Стохастическая оптимизация в информатике. 2011. Т. 7. С. 3-68.

[12] Амелин К. С., Грапичип О.Н., Иевлев Н.В., Кияев В.И. Мобильность и супервычисления на охране природы // Компыотер-Информ, №05-06 (303). 24.03.2011

[13] Амелин К.С., Грапичип O.E., Кияев В.И., Корявко A.B. Взгляд на перспективы развития принципиально новых компьютерных устройств и систем //В сб. тр. Всерос. научн. конф. "Научный сервис в сети Интернет: экзафлопеное будущее" (19-24 сентября 2011 г., г. Новороссийск). - М. 2011. С. 29-31.

[14] Амелии К.С., Грапичип О.Н., Кияев В.И., Корявко A.B. Введение в разработку приложений для мобильных платформ. Учебное пособие. — СПб. 2011.

[15] Амелин К.С. Сетевое адаптивное управление группой легких беспилотных летательных аппаратов на основе мультиагентного подхода // Материалы второй межвузовской научной конференции по проблемам информатики СПИСОК-2011. - СПб. 2011. С. 143-147.

[16] Амелип К.С. Технология программирования легкого БПЛА для мобильной автономной группы // Стохастическая оптимизация в информатике. Т. 7. 2011. С. 93-115.

[17| Amelin K.S. Programming technology for multi-agent controlling group of UAVs // Proc. of the Int. Student Conf. "Science and Progress". Saint-Petersburg, Russia, November 14-18, 2011. P. 66.

Подписано к печати 28.12.2011. Формат бумаги 60 х 84 1/16. Бумага офсетная. Печать ризографическая. Усл. печ. л. 1,0. Тираж 150 экз. Заказ 5333. Отпечатано в отделе оперативной полиграфии Химического факультета СПбГУ. 198504, Санкт-Петербург, Петродворец, Университетский пр. 26.

С. 24-25.

- 518 с.

61 12-1/440

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

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

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация

на соискание ученой степени кандидата физико-математических наук

Научный руководитель: д. ф.-м. н., проф. О. Н. Граничин

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

Амелин Константин Сергеевич

Санкт-Петербург 2012

Оглавление

Введение ............................... 3

1 Группа мобильных объектов для распознавания образов 11

1.1 Автономные мобильные объекты..............................11

1.2 Преимущества группы мобильных объектов ................15

1.3 Использование группы мобильных объектов для решения задач распознавания образов в разных областях............22

2 Рандомизированные алгоритмы оптимизации движения легких мобильных объектов 29

2.1 Добавление рандомизации в стратегию управления для оценивания параметров динамических систем ......... 30

2.2 Свойства оценок рандомизированного алгоритма предсказания (фильтрации) случайного процесса, наблюдаемого

на фоне почти произвольных помех............. 44

2.3 Рандомизированные методы прогнозирования и оценивания параметров внешней среды для оптимизации движения мобильных объектов при внешних воздействиях и существенных погрешностях в получаемых данных...... 49

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

3.1 Трехуровневая система управления группой мобильных объектов ............................... 61

3.2 Программирование бортовых микрокомпьютеров мобильных объектов группы..................... 68

3.3 Апробация алгоритмов и технологии программирования . 74

Заключение.............................. 78

Литература.............................. 79

Введение

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

смещения в следующий момент времени и внесение „на основе этих данных поправок в задаваемый курс.

Задача предсказания значений случайного процесса, порождаемого белым шумом, пропущенным через линейный фильтр, является наиболее типичной для калмановской фильтрации, базирующейся на работах P.E. Калмана и P.C. Бьюси [45]. Наряду со статистическими развиваются и минимаксные постановки задач, в которых о неопределенностях предполагается только ограниченность в каком-либо смысле, а в остальном они могут быть произвольными. Такая постановка задачи рассматривается в работах О.Н. Граничина [35], А.И. Кибзуна, Ю.С. Кана [109], А.Б. Куржанского [47], А.Р. Панкова, К.В. Семенихина [52], Б.Т. Поляка, П.С. Щербакова [55], Р. Темпо [89], В.Н. Фомина [78], Ф.Л. Чер-ноусько [80] и др. Применение фильтрации в системах навигации мобильных планеров исследовалось В.Д. Андреевым, O.A. Бабичем [20], O.A. Степановым, В.Н. Васильевым, A.B. Осиповым [64, 67] и др. Для оценки случайных процессов в системах навигации мобильных объектов достаточно часто и эффективно применяется фильтр Калмана, который удовлетворительно работает на больших мобильных объектах с применением различного навигационного оборудования. Для легких мобильных объектов задача снижения уровня отклонения от заданной траектории движения остается открытой, так как влияние на них сопутствующих неопределенностей более значительно.

Сравнительная дешевизна и доступность легких мобильных объектов позволяет при решении практических задач использовать их в группе, что оказывается эффективнее по сравнению с применением одного мобильного объекта. В связи с этим растет необходимость в разработках новых подходов к конструированию систем управления такими объектами. Для реализации новых преимуществ группы необходимо организовать автономное групповое взаимодействие. Для решения такого типа задач в последнее время успешно применяются мультиагентные технологии, развиваемые в работах В.И. Городецкого [30], П.О. Скобелева [60,61], И.Б. Тарасова [69], Ю. Шохама [121] и др. Применение мультиагентного

подхода к управлению группой мобильных планеров исследовали M. Зе-нар, А. Район [117], Т.Дж. Кут, С.М. Шахруз [108], и др. При этом алгоритмы многоагентного взаимодействия в основном применяются для задач предотвращения столкновения или организации группового полета мобильных вертолетов, самолетов и мультикоптеров с поддержанием заданной формации. В практических реализациях группа мобильных объектов обычно представляет собой несколько одиночных комплексов, которые управляются из единого центра управления, что существенно ограничивает организацию автономного внутригруппового взаимодействия.

При оптимизации движения одиночного мобильного объекта и группы в режиме реального времени возникают потребности в решении за ограниченное время многомерных оптимизационных задач при зашум-ленных наблюдениях. В таких условиях хорошо зарекомендовали себя рандомизированные рекуррентные алгоритмы стохастической оптимизации. Детальному анализу возможностей рандомизированных алгоритмов в задачах оценивания и оптимизации при произвольных помехах посвящена монография О.Н. Граничина и Б.Т. Поляка [37]. Рассматриваемый в этой книге новый тип рандомизированных алгоритмов стохастической аппроксимации, называемых в англоязычной литературе Simultaneous Perturbation Stochastic Approximation (SPSA), был предложен в работах О.Н. Граничина [31,32,34], Б.Т. Поляка и А.Б. Цыбакова [54], Дж. Спал-ла [123], Х.-Ф. Чена, Т. Дункан и Б. Пасик-Дункан [94]. Они основаны на аппроксимации градиента вдоль случайно выбранного направления — рандомизации, которая опирается на некоторые контролируемые случайные величины, влияющие на результаты наблюдений, существующие в системе или добавляемые экспериментатором. Эти алгоритмы относятся к более широкому классу методов случайного поиска, которые ранее в русскоязычной литературе исследовались, например, в работах JI.A. Растригина [56], Ю.А. Сушкова [68], С.М. Ермакова, В.Б. Мела-са [42], A.A. Жиглявского и А. Жилинскаса [44]. В отличие от предлагавшихся ранее методов рандомизированные алгоритмы стохастичес-

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

Использование группы мобильных объектов позволяет увеличить эффективность выполнения задач поиска, мониторинга или исследования территории с применением алгоритмов распознавания образов к данным газоанализаторов, теплодатчиков, фото- и видео- регистраторов. Современные алгоритмы теории распознавания образов, классификации и кластерного анализа базируются на работах С.А. Айвазяна [2], В.Н. Вапника иА.Я. Червоненкиса [23-25,124], Ф. Розенблата [57], P.A. Фишера [75,97], В.Н. Фомина [76], И. Форджи [98], К. Фукунаги [99], Дж. Хартигана [104], Я.З. Цыпкина [81,82], В.А. Якубовича [83] и др. Многие современные системы распознавания образов основаны на принципах нейронных сетей (A.B. Тимофеев [71], С. Хайкин [79], Дж. Хопфилда [105], Ф. Уоссер-ман [73] и др.).

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

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

Цель достигается в диссертации через решение следующих задач:

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

2. Разработка и исследование методов вв1бора направления движения легкого мобильного объекта для уменьшения отклонения от заданной траектории при действии помех.

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

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

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

Основные результаты. В работе получены следующие основные научные результаты.

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

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

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

4. Разработана трехуровневая архитектура и технология программирования программно-аппаратного комплекса для исследования и мониторинга территорий с помощью группы мобильных объектов на примере разработанной комплектации бортового оборудования планера с фоторе-

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

Научная новизна. Все основные научные результаты диссертации являются новыми.

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

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

Апробация работы. Материалы диссертации докладывались на семинарах кафедры системного программирования СПбГУ, на российских и международных конференциях по программированию, информатике, оптимизации и теории управления: XXVII конференции памяти Н.Н. Ост-рякова (12-14 октября 2010 г. Санкт-Петербург, Россия), Второй и Третьей традиционных всероссийских молодежных летних школах "Управ-

ление, информация и оптимизация" (2010, 2011 гг.), Первой российской MeeGo конференции (Москва, 11 марта 2011 г.), Второй межвузовской научной конференции по проблемам информатики СПИСОК-2011 (Санкт-Петербург, 27-29 апреля 2011 г.), 5th International Conference on Physics and Control (PhysCon 2011) (5-8 September, 2011, Leon, Spain), международной конференции "Science and Progress 2011" (Санкт-Петербург, Россия, 14-18 ноября, 2011 г.), международной научно-практической мульти-конференции "Управление большими системами" (УБС 2011) (Институт проблем управления им. В.А. Трапезникова РАН Москва, 14-16 ноября 2011 г.).

По материалам диссертации было получено свидетельство об официальной регистрации программы для ЭВМ № 2010612684 "SmartFly Together" от 19 апреля 2010 г. Результаты диссертации использованы при выполнении работ по проекту "Мультиагентная система для управления группой легких беспилотных летательных аппаратов" в рамках программы "СТАРТ-10" Фонда содействия развитию малых форм предприятий в научно-технической сфере. Выполненный в ходе работы над диссертацией проект "Сетевое адаптивное управление группой легких беспилотных летательных аппаратов на основе мультиагентного подхода" был отмечен дипломом победителя конкурса грантов Санкт-Петербурга для студентов, аспирантов, молодых ученых, молодых кандидатов наук 2011 г.

Публикации. Основные результаты диссертации опубликованы в работах [4-17,86,87,114]. Из них три публикации [12,13,114] в журналах из перечня ВАК. Работы [8-17,87,114] написаны в соавторстве. В работах [11-14,87] О.Н. Граничину принадлежат общие постановки задач, а К.С. Амелину - реализация описываемых методов, доказательства, создание демонстрационных примеров и программных средств. В [114] К.С. Амелиным получены и описаны основные практические результаты. В [8,10,15-17] К.С. Амелиным описаны технические характеристики разработанных комплексов БПЛА и предложены методы их практического применения в задачах распознавания образов. В зарегистрированной программе для ЭВМ [9] К.С. Амелиным разработаны программные

компоненты для автопилота мобильного объекта.

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

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

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

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