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

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

Пельцвергер Светлана Борисовна

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

Специальность 05.13.01 "Системный анализ, управление и обработка информации"

АВТОРЕФЕРАТ

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

Москва -

2004

Работа выполнена в Институте Системного Анализа РАН

Научный руководитель: Доктор физико-математических наук,

профессор Афанасьев Александр Петрович

Официальные оппоненты: Доктор технических наук

профессор Цыгичко Виталий Николаевич

Кандидат технических наук старший научный сотрудник Топка Владимир Владимирович

Ведущая организация: Вычислительный Центр РАН

Защита состоится 21 июня 2004 г. в 1 Iм на заседании диссертационного совета Д.002.086.02 в Институте Системного Анализа РАН по адресу: 117312, г. Москва, пр-т 60-летия Октября, 9.

С диссертацией можно ознакомиться в библиотеке Института Системного Анализа РАН

Автореферат <разослан ^^ 2004 г.

Ученый секретарь диссертационного совета

д.т.н., проф. Пропой Анатолий Иванович

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

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

Первые попытки оценить состояние динамической системы в условиях неопределенности были сделаны немецким математиком К.Ф. Гауссом в начале 19 века. Проблеме оценивания и управления посвящены работы Н. Винера, А.Н. Колмогорова, Р.Е. Калмана, Н.Н. Красовского, А.А. Красовского, А.Б. Куржапского, ИЛ. Каца, Б.И. Ананьева, ФЛ. Черноусько, D.P. Bertsekas, F.C. Schweppe, P. Varaiya и многих других.

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

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

Результаты по исследованию особенностей поведения оптимальных траекторий и построения схемы решения задач оптимального оценивания и управления основаны на процедуре продолжения оптимальных решений, разработанной А. П. Афанасьевым. Этот подход, реализуя сстсствешгую декомпозицию задачи, позволяет использовать параллельные и распределенные вычисления. Идеи и методы подхода, предложенного А.Б. Куржанским и ФЛ. Черноусько для задач эллипсоидальной аппроксимации, в данной работе развиваются применительно к аппроксимациям многогранниками. Работа развивает подход В.М. Кунцсвича и В.И. Ширяева по аппроксимации n-мерных информационных множеств многогранниками.

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

I* уос НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

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

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

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

Из цели вытекают следующие задачи:

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

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

• сравнить разработапные алгоритмы с существующими алгоритмами;

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

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

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

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

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

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

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

• для реализации алгоритмов в реальном времени информационные множества аппроксимируются проекциями на 2-х мерные плоскости.

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

Разработанпые алгоритмы применялись для:

• оценивания устойчивости 76-ти этажного здания при ветровых возмущениях;

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

Реализация и внедрение результатов работы. Результаты диссертационной работы использовались в учебном процессе каф. «Информационные и вычислительные науки» Государственного университета г. Коламбус шт. Джорджия (США). Алгоритмы, разработанные в диссертации, переданы для использования в проекте "Позиционирование мобильных терминалов" в ООО "Южно-Уральский сотовый телефон" (г. Челябинск).

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на семинаре «Актуальные проблемы фундаментальных наук» (Москва, 1991 г.), конференции «Системы цифровой обработки и анализа изображений» (Рига, 1991 г.), конференции «Обработка и анализ цифровых изображепий» (Рига,

1991 г.), международной конференции по интервальным и стохастическим методам в науке и технике «Интервал-92» - (Москва, 1992 г), конференции «Проблемы прикладной математики» (Саратов, 1992 г.), на 4-ой международной конференции по кибернетике и информатике «SCI 2001» -(США, 2001 г.), па 6-ой международная конференция по информационным системам, анализу и синтезу «ISAS: 2001»» - (США, 2001-г.), на 11-ой международной конференции по телекоммуникационным системам, моделированию и анализу (США, 2003 г.), на 42-ой ежегодпой конференции Association of Computer Machinery (США, 2004 г.) и др.

Публикации. По теме диссертации опубликовано 9 работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (107 паимепований) и двух приложений. Объем основного текста диссертации 120 страниц; включающих 55 рисунков и 15 таблиц.

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

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

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

Рис. 1. Нахождение чебышевского центра пересечения множеств при аппроксимации их многогранниками и эллипсоидами

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

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

(а)

(б)

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

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

Приводится оценка Buchta количества граней многогранника из Rn, которое будет линейно зависеть от количества вершин т

/(п,т) = 8(п)(т + о(п)),

§(п)=-Г{(п -1)2 К" -1)4"-0, /(0)=Нр)=

1

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

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

Уравнение динамической системы и измерителя имеют вид

= 1 + ВкЩ + ; .Ук+1 = + + Пк+и к = ОД.....

где - фазовый вектор системы; - вектор измерений;

независимые гауссовские случайные векторы с нулевым математическим ожиданием и известными матрицами ковариации Qk и Як соответственно. Начальное состояние Хц - гауссовский вектор, независящий от 1 с

известной ковариационной матрицей О значениях математического

ожидапия Мх,, возмущениях неопределенного характера известно

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

Мхо еХ0, ще!Гк сГ, ушеГ1+1сП", к = 0,....

Все остальные матрицы в (1) известны и корректно определены.

Рассмотрим в пространстве Л х

следующее множество

(О

= О = К. VI,..., У^}:

*о е^о.П = 0,...,ЛГ-1}.

По известной реализации измерений = пеобходимо найти

оцепку Хх=хи(ук(-)) , удовлетворяющую условию е^ = ст^ , где

¿¿=тттаф-2||2 = тах ||2 , (2)

а величипа а\ =ТгРк не зависит от значения реализовавшегося сигнала уц(-) и параметра с .

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

Оценки Хл множества Хк удовлетворяют, начиная с известного Х0, соотношениям для множественно-множественных отображений

=ЗД + ВкШк + ЛА+10>*+1 - (3)

(5)

где мпожества Хк1к^х,¥к+1,Х[ук^1\ определяются выражениями

Хк+\1 к = Ак+Л + ВкЩ > Ук = 0^1- НМГМ) П Ск+1хк+11к, Х&к+1 ] = {*: Ск+\Х + нк+1*=Ук+Ь е }. Для чебьппевских радиусов множеств Хл имеет место неравенство к

Построив одну из оценок Хл информационного множества Хк из решения минимакспой задачи (2) найдем минимаксную оценку х'к вектора фазовых координат хк

шш шах || х - 21|2= шш тах || х — г ||2= тах || х - х'к ||2 . ген' хеХ* хеХл

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

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

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

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

Существует два представления многогранников в пространстве размерности л: ^многогранники, представленные выпуклой оболочкой множества точек у,е Ус Л" Р=сот{ } которые также могут быть

т т

представлены как выпуклая комбинация вершин х = = 1, Я,- & 0 и Н —

ы\ <=1

многогранники - представленные как пересечения полупространств Р=ПП Ах<Ь,хе1Г.

Согласно > теореме МсМи11епа об оценке • сверху количества граней многогранника из Л" с т вершинами (табл. 1) для пространства размерности 5 для 30 вершин имеем 702 грани, Гк (Р) = (С(п,т)), Ук = 1 ,...,п -1.

Таблица 1

р- & Л £ й и

С(5,10) 10 45 100 105 42

С(5,20) 20 190 580 680 272

С(5,30) 30' 435 1460 1755 702

Рис. 2. Аппроксимация многогранника проекциями на плоскости параллельные координатным плоскостям

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

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

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

А + В = сопу{ а( + ¿у: / = 1, ,п а,] -1, л ь} ,

где т и Ь] соответственно вершины многогранников А и В. Для рассматриваемой-задачи будет достаточно найти аппроксимацию выпуклой оболочки с заданпой точностью. Основным достоинством этого подхода будет эффективность и скорость нахождения результата. Известно, что построение точной выпуклой оболочки невозможно быстрее, чем О(т^т). Для аппроксимации выпуклой оболочки используется алгоритм Бептли - Фауст -Препарата с вычислительной сложностью О(т), где т - количество точек. Идея алгоритма заключается в разделении плоскости на интервалы и нахождению экстремальных точек (&) для каждого интервала (рис. 3).

Рис. 3. Построение выпуклой оболочки

Точка И не является экстремальной в своем интервале, по должна принадлежать выпуклой оболочке. Такие точки пе могут находиться от границы далее чем (хп„х-ХттУК, где К - количество интервалов. Регулировка точности достигается изменением ширины интервалов.

Построение геометрической» разности двух многогранников В и А сводится к нахождению пересечений множеств получепных путем сдвигов множества В на вектор а(

В*А=С\(В'-а,),{ = 1,..,па,

где а, и 6 соответственно вершины многогранников А и В.

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

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

Для построения пересечения используется алгоритм O'Rouгke (рис. 4), основанный на последовательном чередующемся обходе многоугольников. Решение о том, какой многоугольник обходить на следующем шаге принимается на основе знака ориентированной площади треугольника, содержащего две вершины ребра одного многоугольника и очередной вершины другого многоугольника. Вычислительная сложность соответственно количество вершин многоугольников А и Я-

1-7 - последовательность обхода ребер

Рис. 4. Построение пересечения двух пятиугольников

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

Вершины многогранника: 8,, s3 Начальная сфера:

• центр-д,,

• радиус s0

Рис. 5. Нахождение чебышевского центра четырех точек

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

• центр с* должен принадлежать выпуклой оболочке, построенной па вершинах, принадлежащих поверхности сферы с*есот{В},

• 54: соэгЬгЬипиенты этих точек в выпуклой комбинаттии должны не больше

ЬеВ ЬеВ

где все точки из В лежат на поверхности сферы.

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

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

Сравпение с методом эллипсоидов по точности оценивания и требуемым вычислительным ресурсам производилось на примере, взятом из работы Ф.Л. Черноусько. Рассматривалась система вида

* = С(0* + и, и(0 е Е(/(1),В(<)), Ф) е £(<*<,>&).' ^

где*

еД4 с дискретным наблюдателем

х0 = НЦ)х{1)+тт е £(0,£(')).' £ где у еР2. Внешние возмущения при моделировании задавались в виде «1(0 = 51п(-У2<), ы2(/) = со8(-У2/), начальные дшшые дня системы принимались пулевыми, а ошибки измерепий задавались в виде

= &(0 = /?СО5(л/2<).

(а) (б)

Рис. 6. Результаты фильтрации: (а) — метод эллипсоидов; (б) - разработанпый алгоритм

На рис. 6 приведены графики зависимости отнесенного к к объема v(f) информационных мпожеств. Средняя величина объема для разработанного алгоритма оказывается меньше.

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

При оценивании' состояния 76-ти этажного здания производилось сравнение с разработкой J.C. Wu и др. Общая масса здания 153,000 тонн. Общий объем здания 510,000 м3 с плотностью 300 кг/м. Отношение высота к ширине 306.1/42 = 7.3. Периметр здания состоит из 24 железобетонных колон диаметром 6.5 м, соединенных на каждом этаже балками с сечением 900 мм х 400 мм. Динамика процесса описывается следующей системой:

*<ui = А 4 + Bkwk + Ctft. k = 0,1.....

Ук+1 = + Hk+ivk+i + Vk+u

Щк =0» Щк+1 =0,cov{&}=ßt ,cov{7t+i}=Äi+1, где jcjgR46, jteR27. Необходимо оценить максимально возможное отклонение здания от вертикали для каждого этажа доя 90 итераций (15 мип).

В табл. 2 и па рис. 7 приведен сравнительный анализ результатов, полученных при использовании разработанной модели, модели J.C. Wu и др., а также результатов, полученных в результате тестирования модели здания в аэродинамической трубе. Масштаб модели 1:400. Площадь информационного множества приведена только для разработанного алгоритма. Под информационным множеством попимается совокупность состояний системы, совместных с полученными измерениями.

Таблица 2

Этаж Отклонение от вертикали (см) Площадь информационного' множества для этажа (СМ2)

J.C. Wu и др. (см) Разработанный алгоритм (см) Моделирование в аэродинамической трубе (см)

1 0.053 0.049 0.044 0.001

30 6.838 6.385 5.595 20.785

50 15.201 16.585 13.339 158.997

75 31.588 28.645 24.841 465.138

76 32.300 29.105 25.381 492.718

Время моделирования с использованием процессора 1 ГГц приводится в табл. 3. На итерациях с 1 по 24, когда количество вершин информационного множества растет, время необходимое для обработки информации возрастает.

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

атаж __.__

30

.г® т

чК -.У •» 0 >>! Г-» Л М V)

Рис. 7. Максимальное отклонение от вертикали: — результаты тестирования в аэродинамической трубе; результаты J.C. Wu и др.; - - результаты разработанного алгоритма

Таблица 3

Итерация к 2 5 7 10 20 23 25 90

Время CPU/fc (сек.) 15.8 18.2 18.5 18.7 18.9 19.3 19.4 19.4

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

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

Рис. 8. Архитектура сети. С - стационарный компьютер, Т - мобильпые терминалы, R— передвижная установка беспроводной связи -

Для корректировки спутниковых сигналов, а именно ошибок, приведенных в табл. 4, используется дифференциальная GPS (DGPS), которая использует базовый GPS-приемник передвижной установки.

Таблица 4

Источник ошибки Величипа ошибки

Часы приемника Аг 1 мс (300 м)

Часы спутника Дг' 20 нс

Орбитальные ошибки е1 20 см

Тропосфера Ар1^ <30 м

Ионосфера Ар'юпо <150 м

Многоволновость Дт <5 м

Шум измерителя приемника 4 1 м (С/А коде) 0.1 м (Р коде)

Для каждого из т клиентов рассмотрим систему = Л + Вкщ + Ск к = 0,1,.... В моменты времени к — 1,... осуществляется измерение 2х мерного параметра (позиции: широта долгота), связанного с вектором фазовых координат д^ € Л2 линейным соотношением

Л = Gtxk rjitk = 1,2.....

Здесь Чк пезависимые гаусовские последовательности, причем -

У^К\со\^хса^по) = Р0,хТ1О=>Мх0= х0 еХ0. Зпачения вычисляются из табл. 4 по методикам расчета Chang и Paige.

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

того чтобы найти оценку хгЛу вектора хк+1 по данным измерениям {уо, ... необходимо найти информационное множество A^i (3)-(5) и вычислить его чебышевский цегггр. Используемое оборудование, а также внешние факторы будут одинаковыми для всех клиентов, более того клиенты независимы, поэтому нет необходимости рассматривать т различных систем. Ограничившись построением оценки для одного клиента, все остальные оценки могут быть построены на основе векторного переноса.

Имея оценку JC4+it для одного клиента и каждого

клиента, где Ayj[ = ук — y\,i = 2,m, за лучшую точку размещения передвижной установки беспроводной связи принимается чебышевский центр множества что гарантирует минимальное расстояние до паиболее удаленного

клиента.

250 • 200 ■ 150 ■ 100 ■ 50 •

°-50 0 50 100 150 200 250

к

Рис. 9. Коэффициент мощности и взаимное расположение передвижпой установки беспроводной связи и клиептов.

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

*-*/)l|2 +II*/ ||2)/50 = 3.752 м, где дг/ широта, х? - долгота.

Результаты расчетов для 10 мобильных клиентов приведены на рис. 9. При N=200 в моменты времени 60 (+), 120 (о), 180 (0), 240 (□), 300 (*) отображено

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

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

Таблица 5

К Реальная позиция (м) Оценка позиции (м)

широта долгота долгота широта-

1 0.82 1.42 0.70 2.12

5 5.88 3.40 3.52 3.52

10 8.95 5.17 6.86 6.61

20 13.98 7.22 10.86 9.15

30 21.98 11.63 16.06 13.35

40 29.74 17.17 22.48 18.59

50 40.63 23.46 30.18 24.85

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

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

В приложении приведены дапные для оценивания устойчивости 76-ти этажного здания при ветровых возмущениях

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

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

2. На основе разделения априорных и апостериорных данных приводится решение задачи о построении информационных множеств для реализации алгоритмов оценивания в реальном времени.

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ширяев В.И., Пельцвергср СБ. О выпуклых многогранниках в задачах оцепивания и управления // Всесоюзп. конф. "Актуальные проблемы прикладпой математики". Тез. докл. -Саратов: 1991. Т. 11. - С. 131-135.

2. Ширяев В.И., Пельцвергср СБ. Синтез управления динамическими системами в статистически неопределенных ситуациях // Междун. конф. "Актуальные проблемы фундаментальных наук". Тез. докл. - М.: Изд-во МГТУ, 1991. Т.1.-С86-89.

3. Ширяев В.И., Халили Н.Б. Пельцвергср СБ. Алгоритмическое обеспечение процессов принятия решения в динамических системах в условиях статистической неопределенности ситуациях // Мсждунар. копф. по интервальным и стохастическим методам в науке и технике (Интсрвал-92). Сб.пауч.тр. - М.: 1992. Т.1. -С 203-206.

4. Shirjaev W.I., Pelzwciger S.B., Velkova I.S., Burtscv S.M. Convex polyhedrons in dynamic solution taking process under uncertain conditions // International Congress on Computer systems and Applied Mathematics CSAM'93 (St Petersburg, July 19-23, 1993.) Proceedings of 1993 Center of Modern Communications POLYLOG. -P. 101.

5. Теория и информационные технологии управления. Научно-технический отчет / В.И. Ширяев, И.С. Велкова, СБ. Пслыгвсргер и др. №ГР 01950001228 пр. инв. 02.950001162 закл.инв № 02950000864. - Челябинск: НИЧ ЧГТУ, 1994.30с.

6. Shiryaev V., Peltsvcrgcr S. Algorithms for Calculation of Information Set in Discrete Systems Under Conditions of Statistical Uncertainty // SCI 2001/1SAS 2001 July 22-24. Orlando: 2001. - P. 1856-1859.

7. Peltsvergcr В., Peltsvcrgcr S. Optimal Allocation ofWireless Points in Mobile Networks //Procedings of the 11th International Conference on Telecommunication Systems. Monterei, CA, 2003. - P. 77-79.

8. Bartolacci M. R., Peltsvcrger В., Konak A., Peltsvcrgcr S. Allocation of Multiple Wireless Access Points in Mobile Networks// Procedings of the 42th ACM Southeastern Conference. Huntsville, AL, 2004. - P. 1-4.

9. Пельцвергер СБ. Быстрые алгоритмы полиэдральной аппроксимации в задачах минимаксно-стохастической фильтрации // Известия Челябинского научного центра УРО РАН.- 2004. - Вып. 1(22)-с.37-48.

Подписано к печати 17.05.04. Объем 1 пл. Формат 60x90/16. Бумага офсетная. Тираж 70 экз.

»10324

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ.

ВВЕДЕНИЕ.

ГЛАВА 1. ОЦЕНИВАНИЕ В ЛИНЕЙНЫХ ДИНАМИЧЕСКИХ СИСТЕМАХ

1.1. Введение.

1.2. Оценивание в условиях неопределенности.

1.2.1. Фильтр Калмана.

1.2.2. Байесовские методы.

1.2.3. Метод максимума правдоподобия.

1.2.4. Минимаксный подход.

1.2.5. Минимаксно - стохастический подход.

1.3. Операции над множествами в задачах оценивания.

1.3.1. Представление информационных множеств 26 эллипсоидами.

1.3.2. Представление информационных множеств 30 многогранниками.

1.4. Постановка задачи и цели исследования.

ГЛАВА 2. МИНИМАКСНО-СТОХАСТИЧЕСКОЕ ОЦЕНИВАНИЕ В ЛИНЕЙНЫХ СИСТЕМАХ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

2.1. Введение.

2.2. Определяющие соотношения в задаче фильтрации.

2.3. Рекуррентный минимаксный фильтр.

2.4. Сглаживающий и прогнозирующий минимаксные фильтры.

• 2.5. Информационные множества в задачах оценивания.

2.5.1. Линейное преобразование и сдвиг множества на 53 вектор

2.5.2. Сумма множеств по Минковскому.

2.5.3. Геометрическая разность и пересечение множеств.

2.5.4. Аппроксимация множеств.

2.5.5. Чебышевский центр множества.

Выводы ко второй главе.

ГЛАВА 3. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ В ЗАДАЧАХ

ОЦЕНИВАНИЯ

3.1. Введение.

3.2. Представление информационных множеств многогранниками.

3.3. Представление многогранника в виде проекций.

3.4. Построение суммы по Минковскому и выпуклой оболочки множеств.

3.5. Построение геометрической разности многогранников.

3.6. Построения пересечения многогранников.

3.7. Построение чебышевского центра многогранника.

3.8. Линейное преобразование многогранника.

3.9. Аппроксимация информационных множеств.

Выводы к третьей главе.

ГЛАВА 4. МИНИМАКСНО-СТОХАСТИЧЕСКОЕ ОЦЕНИВАНИЕ В ф СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ

• 4.1. Введение.

4.2. Сравнительный анализ представления информационных множеств эллипсоидами и многогранниками.

4.3. Сравнение с известными решениями.

4.4. Динамическое размещение передвижных установок беспроводной связи.

Ф 4.4.1. Технические характеристики передвижной установки беспроводной связи.

4.4.2. Моделирование сети.

4.4.3. Результаты численных экспериментов.

Выводы к четвертой главе.

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

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

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

Первые попытки оценить состояние динамической системы в условиях неопределенности были сделаны немецким математиком К.Ф. Гауссом в начале 19 века. В современной теории наблюдения и управления наряду с вероятностным подходом [1] к описанию состояния динамической системы в условиях неточных измерений используется детерминированный подход, основанный на построении информационных множеств [2, 3]. Под информационным множеством понимается совокупность состояний системы, совместных с полученными измерениями.

Решение многих задач теории управления и наблюдения в условиях неопределенности в гарантированной постановке связано с построением трубок траекторий динамических систем (эволюции множеств достижимости) [3-7]. Среди численных методов построения трубок траекторий в настоящее время активно развиваются методы, основанные на аппроксимации множеств классом областей некоторой фиксированной формы (в частности, эллипсоидами, параллелепипедами). Идеи и методы подхода, предложенного А.Б. Куржанским для задач эллипсоидальной аппроксимации, в данной работе развиваются применительно к аппроксимациям мн огогранникам и.

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

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

Первые попытки применения аппроксимации выпуклых тел многогранниками на практике были сделаны Л.С. Понтрягиным и др. [13-15] для аппроксимации множеств достижимости динамических систем. Эти методы использовались для теоретических оценок. В настоящее время теоретически и экспериментально исследован и широко применяется целый ряд алгоритмов аппроксимации, оптимальных с точки зрения сложности описания аппроксимирующих множеств [16- 18]. Результаты по исследованию особенностей поведения оптимальных траекторий и построения схемы решения задач оптимального оценивания и управления основаны на процедуре продолжения оптимальных решений, разработанной А.П. Афанасьевым [19-22]. Этот подход, реализуя естественную декомпозицию задачи, позволяет использовать параллельные и распределенные вычисления [23].

Работа так же развивает подход В. И. Ширяева [24-33] построения п-мерных информационных множеств в задаче оценивания состояния линейных динамической систем, первоначальное состояние которых известно, но последующие измерения не точны из-за помех неопределенного характера и они характеризуются тем, что об одной части действующих возмущений и помех известны их области изменения, а о другой их статистические характеристики.

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

Из цели вытекают следующие задачи:

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

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

• сравнить разработанные алгоритмы с существующими алгоритмами;

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

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

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

В последнее время много внимания уделяется надежности геометрических алгоритмов, наряду с «точными вычислениями», когда результат находится до последнего значимого бита, что приводит к замедлению работы алгоритмов, развивается и подход, впервые предложенный Guibas и др. [90], основанный на сочетании интервальной арифметики и обратному анализу ошибок.

В работе особое внимание уделено эффективности и надежности работы алгоритмов для пространств большой размерности. Двухмерное пространство в иллюстрациях выбрано для наибольшей наглядности. В случаях, когда размерность п пространства мала: п < 3, анализ многогранников в значительной степени упрощается благодаря возможности «увидеть» объект изучения. Но уже при п=4 роль этого фактора существенно снижается.

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

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

Председатель комиссии подпись Симмерс В.) . Члены комиссии: подпись Курковский С.) (подпись Вайтхед С.) .

Система университетов штата Джорджия

1. Справочник по теории автоматического управления / Под ред. А.А. Красовского.- М.: Наука, 1987. - 712 с.

2. Milanese М. and et al. Bounding Approaches to System Identification / M, Milanese, J. Norton, E. Walter.- London: Plenum Press, 1996.- 586 p.

3. Kurzhanskii A.B., Valyi I. Ellipsoidal Calculus for Estimation and Control. -Boston: Birkhauser, 1997. - 321 p.

4. Куржанский А.Б. Задачи идентификации - теория гарантированных оценок // Автоматика и телемеханика. 1991. № 4. -С.3-26.

5. Колмогоров А.Н. Интерполирование и экстраполирование стационарных случайных последовательностей // Изв. АН СССР. Математика. 1941. Т. 5. № 1. 3-14.

6. Winer N. Extrapolation, Inteфolation and Smoothing of Stationary Time Series. -New York: Wiley, 1949. - P. 11-23.

7. Калман P.E. 06 общей теории систем управления // Тр. 1 Конгресса ИФАК. -М.: Изд-во АН СССР, 1961.- 521-547.

8. Фильтрация и стохастическое управление в динамических системах / Под ред. К.Т.Леондеса. - М.: Мир, 1980. - 407с.

9. Зонов Н.И., Красильщиков Н.Н. Система рекуррентных байесовских алгоритмов оценивания, адаптивных к разнородным неконтролируемым факторам // Изв. РАН. Техн. киберн. 1994. № 4. - 5-16.

10. Mehra R. Approaches to adaptive filtering // IEEE Transactions on Automatic Control. 1972. V. 17 - P. 693-698.

11. Куржанский А.Б. Задачи идентификации - теория гарантированных оценок // Автоматика и телемеханика. 1991. № 4. - 3-26.

12. Кунцевич В.М. Определение гарантированных оценок векторов состояния и параметров линейных динамических систем при ограниченных возмущениях// Докл. АН СССР. 1986. №3. - 567-570.

13. Понтрягин Л.С., Андронов А.А., Витт А.А. О статическом рассмотрении динамических систем //ЖЭТФ. 1933. Т.З. Вып. 3. - 165-180.

14. Математическая теория оптимальных процессов / Л.С. Понтрягин, В.Г. Болтянский, Р.В. Гамкрелидзе, Е.Ф. Мищенко. - М.: Физматгиз, 1961. -391с.

15. Понтрягин Л.С. Избранные научные труды. - М.: Наука, 1988. Т. 11.- 575 с.

16. Бушенков В.А., Лотов А.В. Методы и алгоритмы анализа линейных систем на основе построения обобщенных множеств достижимости // ЖВМ и МФ. 1980. Т. 20. №5.-С. 1130-1141.

17. Панков А.Р., Семенихин К.В. Минимаксная идентификация обобщённой неопределённо-стохастической линейной модели // Автоматика и телемеханика. 1998. №11.-С. 158-171.

18. Панков А.Р., Миллер Г.Б. Минимаксная линейная рекуррентная фильтрация // Информационные процессы. 2001. Т.1. №2. - 150-166.

19. Afanasiev А. Р. Isoperimetric problem with а polylinear integrand on a polyedron // Сотр. math, and modeling. -New York:Consultations bureau, 1992.

20. Афанасьев A. П. Обобщенная изопериметрическая задача на многограннике // Дифф. ур. 1993. т.29. № 11.

21. Afanasiev А. Р. On the dual problem in the optimal trajectories continuation and Maximal principle for the linear control systems // Proceedings of ISA «Dynamics of non-homogeneous systems». M.: 1997.

22. Afanasiev A. P. Estimates of distances in many-valued mappings determined by perturbed domains admissible solutions in mathematical programming // Proceedings of ISA «Dynamics of non-homogeneous systems». M.: 2001. v. 4.

23. Ширяев В.И. Алгоритмы управления динамическими системами в условиях неопределенности // Мехатроника.2001. №8. - 2-5.

24. Ширяев В.И., Халили Н.Б,, Пельцвергер СБ. Минимаксная фильтрация двумерных дискретных полей. // Системы цифровой обработки и анализа изображений: Тез. докл. межрегионального семинара. - Рига: ИЭиВТ ЛАН, 1991.-С. 97-99.

25. Ширяев В.И., Пельцвергер СБ. Синтез управления динамическими системами в статистически неопределенных ситуациях//Междунар. конф. "Актуальные проблемы фундаментальных наук". Сб. докл. -М.: Изд-во МГТУ, 1991. Т.1.-С. 86-89.

26. Shiryaev V.I., Velkova I.S. Estimation and Control of the Dynamic Systems under Uncertainty Conditions // Advances in Modeling & Analysis, C, AMSE Press, 1995. Vol.46. №3. - P. 55-63.

27. Shiryaev V.I. Prediction in fuzzy social-economic process models under incomplete and inaccurate information// SAMS. 1995. Vol. 18-19. - P. 775-778.

28. Ширяев В.И. Построение позиционного управления роботами в условиях неопределенности по неполной и неточной информации // Тр. VI-й Международной научно-технической конференции "Робототехника для экстремальных условий". - СПб, 1996. - 171-179.

29. Ширяев В.И., Панченко И.С, Шустова М.А., Сидорова Н.Б,, Схмолянский Н.Ю. АлгориТхМЫ минимаксного оценивания в условиях неопределенности // Цифровые радиоэлектронные системы (эл.журнал). 1997. -Вып.1.

30. Ширяев В.И. Алгоритмы реального времени оценивания и позиционного управления динамическими системами в условиях неопределенности // Материалы VIII НТК "Экстремальная робототехника". -СПб.: Изд-во СПбГТУ, 1997. - 253-263.

31. Peltsverger В., Peltsverger S. Optimal Allocation of Wireless Points in Mobile Networks //Procedings of the 11**^ International Conference on Telecommunication Systems. - Monterei, CA, October 2003. - P.77-79.

32. Дробышевский С , Козловская A. Внутренние аспекты денежно- кредитной политики России Москва // ИЭПП. 2002. № 45. - 157 с.

33. Калман Р.Е., Бьюси Р.С. Новые результаты в линейной фильтрации и теории предсказания // Техническая механика ( сб. переводов). 1961. Сер. Д. №1. -С . 123-136.

34. Калман Р.Е., Фалб П., Арбиб М. Очерки по математической теории систем. - М.: Мир , 1971. - 340 с.

35. Сейдж Э.П., Меле Дж. Теория оценивания и ее применение в связи и управлении. - М.: Связь, 1976. - 496с.

36. Брайсон А., Хо Ю-Ши. Прикладная теория оптимального управления. - М: Мир. 1972, - 544с.

37. Magill D. Optimal adaptive estimation of sample stochastic processes // IEEE Trans, on Automatic Control. 1965 V.10(4). -P. 434-439.

38. Гриценко H.C. Логинов В.Д. Мальцев В.И. и др. Определение параметров движения объектов в статистически неопределенных ситуациях // Зарубежная радиоэлектроника. 1988. № 2. - 3-29.

39. Chaer W., Bishop R., Ghosh J. Hierarchical adaptive Kalman filtering for inteфlanetary orbit determination // IEEE Trans. Aero, Elec. Sys. 1998. V.34(3). -P. 883-896.

40. Bertsekas D.P., Rhodes LB. On the minimax feedback control of uncertain systems // Proc. IEEE Conf. on Decision and Control. 1971. - P. 451-455.

41. Matasov A.I. Estimators for Uncertain Dynamic Systems. Dordrecht: Kluwer Academic Publ., 1999. - 432 p.

42. Гриценко H.C., Логинов В.Д. Севостьянов К.К. Адаптивное оценивание // Зарубежная радиоэлектроника. 1983. №7. - 3-27.

43. Кац И.Я., Куржанский А.Б. Минимаксная многошаговая фильтрация в статистически неопределенных ситуациях // Автоматика и телемеханика. 1978. № 11.-С. 74-87.

44. Калман Р.Е. Идентификация систем с шумами // Успехи мат. наук. 1985. Т. 40. №4.-С. 27-41.

45. Черноусько Ф.Л. Оценивание фазового состояния динамических систем. Метод эллипсоидов. - М.:Наука, 1988. - 320 с.

46. Панченко И. Алгоритмы оценивания аддитивных скачкообразных возмущений в линейных динамических системах в условиях статистической неопределенности: Дисс. к-та. техн. наук. - Челябинск, 1997. - 152 с.

47. Вагапу I., Рог А. 0-1 polytopes with many facets // Advances in Math. 2001. V.161.-P. 209-228.

48. Fukuda K., Liebling T. M., Margot. F. Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron // Computational Geometry. 1997. V8. - P.1-12.

49. Buchta C, Muller J., and Tichy R. F. Stochastical approximation of convex bodies // Math. Ann. 1985. V.271(2). - P. 225-235.

50. Красовский H.H. Задачи управления и стабилизации динамических систем // ВРШИТИ, Итоги науки и техники, серия: Современная математика и ее приложения, тематические обзоры. 1998. Т. 60. - 24-41.

51. Кац И.Я. Задачи об устойчивости движения, оценивания и управления в системах со случайными параметрами. Дисс, д-ра физ.-мат. наук. -Свердловск, 1984. - 260 с.

52. Кац И.Я. Минимаксно-стохастические задачи оценивания в многошаговых системах // Оценивание в условиях неопределенности. -Свердловск: У Щ АН СССР, 1982. - 43-59.

53. Кац И.Я. Асимптотические свойства информационных множеств в задаче минимаксно-стохастической фильтрации // Эволюционные системы в задачах оценивания. - Свердловск: УНЦ АН СССР, 1985. - 31- 37.

54. Кац И.Я., Куржанский А.Б. О некоторых задачах наблюдения и управления в случайных обстоятельствах // Автоматика и телемеханика. 1970. №12.-С. 15-25.

55. Кац И.Я., Куржанский А.Б. О двойственности статических задач оптимального управления и наблюдения // Автоматика и телемеханика. 1971. №3.-С. 12-22.

56. Кац И.Я., Куржанский А.Б. К задачам оптимального наблюдения // Прикладная математика и механика. 1973. Т.37. Вып. 5. - 771-786.

57. Кац И.Я., Куржанский А.Б. Минимаксное оценивание в многошаговых системах // ДАН СССР. - 1975. - Т. 221. - № 3. - 535-538.

58. Кунцевич В.М., Лычак М.М. Синтез оптимальных и адаптивных систем управления: Игровой подход. - Киев: Наук, думка, 1985. - 245 с.

59. Кунцевич В.М. Определение гарантированных оценок векторов состояния и параметров линейных динамических систем при ограниченных возмущениях // Докл. АН СССР. 1986. Т.288. № 3. - 567-570.

60. Красовский А.А. Общие решения задачи оптимизации управления при неклассическом функционале // ДАН СССР. 1985. Т. 284. №4. - 808-811.

61. Ананьев Б.И., Ширяев В.И. О выборе наихудших сигналов в многошаговых задачах гарантированного оценивания // Динамические задачи оценивания в условиях неопределенности. - Свердловск: УВЦ УрО АН СССР, 1989.-С. 11-20.

62. Колмановский В.Б., Матасов А.И. Задача фильтрации в системах с последействием при ненулевых начальных условиях // ДАН. 2000, Т. 372. № 3. - 463-468.

63. Черноусько Ф.Л, Колмановский В.Б. Оптимальное управление при случайных возмущениях. - М.: Наука, 1978. - 351 с.

64. Shiryaev V., Peltsverger, S. Algorithms for Calculation of Information Set in Discrete Systems Under Conditions of Statistical Uncertainty // SCI 2001/ISAS. 2001.-P. 1856-1859.

65. Рокафеллар P. Выпуклый анализ. - М.: Мир, 1973. - 472 с.

66. Ананьев Б.И. Минимаксные среднеквадратичные оценки в статистически неопределенных системах // Дифф.уравнения. 1984. Т.20. № 8. -С. 1291-1297.

67. Ананьев Б.И., Ширяев В.И. О выборе наихудших сигналов в многошаговых задачах гарантированного оценивания // Аннотации докладов VI Всесоюзного съезда по теоретической и прикладной механике. - Ташкент, 1986.-С. 37-38.

68. Красовский А.А. Проблемы физической теории управления // Автоматика и телемеханика. 1990. №11. - 3-28,

69. Покотило В,Г. Новый метод квазиоптимальной аппроксимации пересечения эллипсоидов. Препр. // АН УССР. Ин-т кибернетики им В.М. Глушкова. - Киев, 1990. - 18с.

70. Рокитянский Д.Я. Точное решение эллипсоидов, аппроксимирующих область достижимости одного класса линейных систем // Изв. РАН, Теория и системы управления, 1996. №1. - 16-22.

71. Препарата Ф., Шеймос М, Вычислительная геометрия. Введение. - М.:Мир, 1989. - 478с.

72. Bazaraa, Sherali, Shetty. Nonlinear Programming: Theory and Algorithms. - New York: Wiley, 1993. - 656p.

73. McMullen. P. The maximum number of faces of a convex polytope // Mathematika. 1970 . V. XVII - P. 179-184.

74. Gonzalez R.C., Woods R.E, Digital Image Processing. - Boston: Addison- Wesley, 1993.-716 p.

75. Chemikova N.V. Algorithm for finding a general formula for the nonnegative solutions of a system of linear equations // Zh. vych. mat. 1964. V.4. -P. 733-738.

76. Graham R. An Efficient Algorithm for Determining the Convex Hull of a Finite Point Set // Info. Proc. Letters 1. 1972. - P. 132-133.

77. Chand D.R., Kapur S.S. An Algorithm for convex polytops // JACM. 1970. V.17(l)-P. 78-86.

78. Overmars M. H., Van Leeuwen J. Maintenance of configurations in the plane // J. Comput. Sys. Sci. 1981. V.23. - P. 166-204.

79. Hershberger J., Suri S. Off-line maintenance of planar configurations // J. Algorithms. 1996. V. 21(3). - P. 453-475.

80. Kapoor S. Dynamic maintenance of 2-d convex hulls and order decomposable problems // Manuscript. 1995. - 22p.

81. Andrew A.M. Another efficient algorithm for convex hulls in two dimensions // ACM Information Processing Letters. 1979. V.9. - P. 216-219,

82. Chan T.M. Random sampling, halfspace range reporting, and construction of (<k)-levels in three dimensions // SIAM J. Comput. 2001. V.30. - P. 561-575.

83. Burl J. Linear Optimal Control. -Boston: Addison Wesley, 1999. - 432 p.

84. O'Rourke J. Computational Geometry. -New York: Cambridge University Press, 1995. -376p.

85. Goodman J.E., O'Rourke J. Handbook of discrete and computational geometry. - Boca Raton, FL: CRC Press, 1997. - 991 p.

86. Elzinga D.J., Heam D.W. The Minimum Covering Sphere Problem // Management Science. 1972. V. 19(1). - P. 96-104.

87. Fischer К., Gartner В., Kutz М. Fast Smallest-Enclosing-Ball Computation in High Dimensions // Proceedings of the 11th Annual European Symposium on Algorithms (ESA). 2003. - P. 630-641.

88. Guibas L. J., Salesin D., Stolfi J. Epsilon Geometry: Building Robust Algorithms from Imprecise Computations // Symposium on Computational Geometry. 1989. - P. 208-217.

89. Хворова Л.А., Брыксин В.М. Применение математических методов и математического моделирования для оценки агроклиматического потенциала территорий // Известия АГУ. 2002. Вып. 1(23) .

90. Чеботарев В. Моделирование бизнеса: средства и методы // PC Weel</RE. 2000. № 9. - 32-34.

91. Getting I. А. The Global Positioning System // IEEE Spectrum. 1993. V. 12.-P. 36-47.

92. Малышев В.В., Куршин В.В. Адаптивный навигационный алгоритм в условиях селективного доступа к системе GPS // Изв. АН. Теория и системы управления. 2001. №5. - 134-142.

93. Каменев Г.К. Исследование итерационных методов аппроксимации выпуклых множеств многогранниками. - М.: ВЦ АН СССР, 1986. - 39с.

94. В ел нова И. С , Ширяев В.И. Операции над выпуклыми многогранниками в задачах гарантированного оценивания // Межрегиональн. научн.-техн. конф. 11-15 октября 1993г. Тез. докл. - Пермь: ПГТУ, 1993.

95. Simon D. El-Sherief Н. Fuzzy Logic for Digital Phase-Locked Loop Filter Design // IEEE Trans, on Fuzzy Systems. 1995. V. 3. - P. 211-218.

96. Simon D.A. Game Theory Approach to Contrained Minimax State Estimation // International Journal of Uncertainty, Fuzziness, and Knowledge-Based Systems. 2002. V. 10. - P. 363-384.

97. Sayed A.H. A framework for state space estimation with uncertain models // IEEE Trans, on Automatic Control. 2001. V. 46. № 7. -P. 998-1013.

98. Wu J.C., Yang J.N., Agrawal, A.K. Applications of Sliding Mode Control to Benchmark Problems // Journal of Earthquake Engineering & Structural Dynamics. 1998. V. 27. № 11. - P. 1247-1265.

99. Grewal M. S., Weill L. R., Andrews A. P. Global Positioning Systems, Inertial Navigation, and Integration. -New York: John Wiley and Sons Publication, U.S.A., 2001.-416p.

100. Jekeli. Heights, the Geopotential, and Vertical Datums // Technical Report 459, Ohio Sea Grant Development Program, NOAA, Grant No. NA86RG0053 (R/CE-7-PD), 2000. -34 p.

101. Войнич X., Малич И., Бронич А. Система позиционирования мобильных терминалов//Эрикссон Никола Тесла. 2001. Вып.13. №26 - 63-70.

102. Невдяев Л. Путеводная звезда, которая светит всегда // Сети. 1998. №6. -С. 12-20.

103. Chang X., Paige An Orthogonal Transformation Algorithm for GPS Positioning // SIAM Journal on Scientific Computing. 2003. V.24. № 5. - P. 1710-1732.

104. Bartolacci M. R., Peltsverger В., Konak A., Peltsverger S. Allocation of Multiple Wireless Access Points in Mobile Networks// Procedings of the 42* ACM Southeastern Conference. - Huntsville, AL, 2004. - P. 1-4.