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

УНИВЕРСИТЕТ

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

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

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

МИКРОКОМПЬЮТЕРОВ МОБИЛЬНЫХ ОБЪЕКТОВ

С ГРУППОВЫМ ВЗАИМОДЕЙСТВИЕМ

05.13.11 — Математическое и программное обеспечение

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

АВТОРЕФЕРАТ

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

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

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

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

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

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

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

Автореферат разослан “ ” 2012 г.

Ученый секретарь диссертационного совета Кривулин Н. К.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Материалы диссертации докладывались на семинарах кафедры системного программирования СПбГУ, на российских и международных конференциях по программированию, информатике, оптимизации и теории управления: XXVII конференции памяти Н.Н. Острякова (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 источников. Текст занимает страниц, содержит 15 рисунков и одну таблицу.

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

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

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

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

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

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

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

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

В п. 2.1 предлагается для оценивания неизвестных параметров динамической системы управления по конечному числу наблюдений при произвольных внешних помехах добавлять рандомизацию к используемой стратегии управления. Рассматривается объект управления (ОУ) со скалярными входами ut и выходами yt. Помехи vt описывают все другие источники кроме ut, которые вызывают изменения в yt, z 1 — оператор задержки:

z 1 ut = ut1. Передаточная функция G (z 1 ) имеет вид G (z 1 ) = B (z 1 )/A (z 1 ), где натуральные числа na, nb — порядки модели по выходу и входу (управлению); l — задержка в управлении, 1 l nb. Часть из коэффициентов ai, bj неизвестна, и для них требуется определить с заданной вероятностью области достоверности по наблюдениям выходов {yt } на конечном интервале времени t = 1, 2,..., N и известных входов (управлений) {ut }, которые можно выбирать.

Пусть (, F, P) — вероятностное пространство, s na + nb l + 1 — положительное целое число (обычно равное количеству неизвестных параметров объекта (1)), N = s · N с некоторым N.

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

Более точно, будем строить управление {ut }t=0 по правилу где {t } — “собственно” управление, которое определяется некоторым регулируеu мым законом обратной связи ut = Ut (yt, yt1,..., ut1,...), t 0, uk = 0, k > 0.

В диссертации вводится вектор параметров, находящийся во взаимно-однозначном соответствии с набором неизвестных коэффициентов ОУ (1), и для любого k {1, 2,..., s} описан способ построения содержащих его множеств k, использующий два целочисленных параметра q и M, выбираемых пользователем.

Вероятность того, что принадлежит каждому из k, k = 1, 2,..., s, дается в теореме 2.1: Если пользователь может выбрать n и этот выбор не влияет на внешние шумы vsn,..., vs(n+1)1, тогда P{ k } = 1 2q/M. Получаем доверительные интервалы, которые могут использоваться в адаптивных стратегиях принятия решения.

В п. 2.2 рассматривается задача предсказания (фильтрации) случайного процесса {t }, t Rs, порождаемого линейным фильтром в котором A — известная матрица: A = max (AAT ) 1, а {wt } – последовательность одинаково распределенных, центрированных независимых случайных векторов с ограниченной ковариационной матрицей, на основании наблюдений скалярного сигнала представляющих собой смесь преобразованного векторного процесса {t } и помехи наблюдения {vt }. Здесь и далее t — известные в моменты времени t s-мерные вектора входов (регрессоров), которые представляют собой последовательность независимых одинаково распределенных случайных векторов с известными конечными математическими ожиданиями Et, ковариационными матрицами и ограниченными четвертыми моментами, max (A) — максимальное собственное значение матрицы A.

Если случайные вектора t = t Et имеют симметричные относительно нуля функции распределения, то для рандомизированного алгоритма построения очередной оценки предсказания где t = 1,..., > 0 — размер шага и — положительно определенная симметричная матрица, t = T t yt — невязка, в теореме 2.3 получены среднеквадратичt ные оценки для качества предсказания при условиях, когда последовательность помех наблюдения {vt }t1 представляет собой либо значения детерминированной неизвестной ограниченной функции, либо при каждом t — реализацию случайных величин, которые независимы с t и ограничены в среднеквадратическом смысле.

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

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