Моделирование и анализ алгоритмов отслеживания цели, использующих только расстояние до нее
Общая характеристика алгоритма стохастической аппроксимации с пробным возмущением на входе. Знакомство с причинами изменения поведения алгоритмов в зависимости от входных параметров. Анализ задач минимизации нестационарного функционала среднего риска.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 15.05.2013 |
| Размер файла | 2,1 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Введение
алгоритм стохастический аппроксимация
Проблема оптимизации того или иного функционала встает во многих практических приложениях. Иногда требуемые экстремальные значения можно вывести аналитически, но часто приходится иметь дело с неизвестным функционалом, имея доступ лишь к его значению в некоторых точках, либо же к значению его градиента. Особенно распространены задачи, в которых точка минимума функционала дрейфует, а сам функционал изменяется с течением времени. В этой работе рассматриваются подходы для работы как раз с такими функционалами.
Особенный интерес представляет одно из приложений таких алгоритмов - задача трекинга объекта, покоящегося либо же движущегося в дискретном времени. Задачи отслеживания цели и трекинга траектории для машиноподобных неголономных Робот называется неголономным, если он имеет больше эффективных степеней свободы, чем управляемых степеней свободы, в данном случае, робот не имеет возможности двигаться вбок. роботов широко исследовались на протяжении двух последних десятилетий. Такие роботы имеют существенные ограничения в мобильности из-за особенной природы неголономных систем, например кручения колес без возможности движения в боковых направлениях. Из-за недостатка управляемости их линейных моделей, эти системы не могут быть управляемы линейными операторами. Таким образом, для систем такого класса стали широко изучаться нелинейные операторы.
Задача отслеживания траектории и навигации с использованием только данных о расстоянии до цели мотивирована своими областями применения, например, беспроводные сети, управление беспилотными подводными устройствами, системы наблюдения и безопасности, и многими другими, где единственная доступная информация о цели - это расстояние между ней и преследующим роботом. Такое расстояние может получаться путем измерений, например, времени отклика акустического сигнала от объекта или силой сигнала, полученного от искомого объекта. Такой подход может потенциально повлечь за собой существенное уменьшение сложности и стоимости управляющего оборудования. Однако для реализации этого требуется общий алгоритм, посредством которого преследующий робот может быть управляемо направлен к цели основываясь лишь на расстоянии до нее.
Как уже было сказано, такая задача может быть описана как частный случай более общей задачи - минимизации некоторого функционала, изменяющегося с течением времени. В данной работе будут рассмотрены два разных подхода к решению задачи трекинга, один - в контексте глобальной задачи, второй же разработанный непосредственно для отслеживания траектории. Во Введении будет обрисована проблематика и актуальность данной области. В Разделе 2 и Разделе 3 будет представлен краткий обзор существующих алгоритмов, в соответствующих контекстах, затем будут математически поставлены задачи, и, наконец, рассмотрены конкретные алгоритмы с обоснованием их состоятельности, а также с исследованием их поведения на различных входах. В Разделе 4 предлагается проекция данных алгоритмов на одну плоскость в виде задачи трекинга траектории, производится анализ этих алгоритмов, и получаются численные оценки эффективности их работы в различных условиях, с добавлением разных помех. В Разделе 5 предлагается оптимизация одного из алгоритмов с помощью другого с целью получить более помехоустойчивый алгоритм. Наконец, в Заключении подводится итог проделанной работы.
Цель работы
Целью работы является проведение всестороннего анализа алгоритмов преследования цели, основанных только лишь на измерении расстояния до нее. Для анализа и моделирования были выбраны два алгоритма: Алгоритм стохастической аппроксимации с пробным возмущением на входе [1] и Алгоритм отслеживания цели и трекинга траектории на основе лишь данных о расстоянии до нее [2]. Обе статьи были представлены на международной конференции Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference, December 2009 в Шанхае, в декабре 2009 года.
В ходе дипломной работы перед автором были поставлены следующие задачи:
1. Реализовать данные алгоритмы.
Для реализации была выбрана среда Matlab, как наиболее подходящая для решения подобных задач, благодаря удобным средствам для разработки алгоритмов, а также гибкими возможностям визуализации данных и их последующего анализа.
2. Придумать задачу, для которой успешно применимы оба алгоритма.
Как уже говорилось, в общем случае эти алгоритмы решают разные задачи, поэтому необходимо было выбрать их проекцию на одну плоскость. Такой проекцией стала задача трекинга траектории. Таким образом, в этом случае минимизируемый функционал в РАСА определяется функцией квадрата расстояния до заданной точки.
3. Изучить изменение поведения алгоритмов в зависимости от входных параметров.
4. Провести серию экспериментов на предмет анализа алгоритмов.
Были выбраны несколько классов помех, при добавлении которых необходимо было провести сравнительный анализ эффективности алгоритмов и уровня погрешности в доставляемых ими оценках.
5. Подвести итог анализа и получить рекомендации по оптимальному использованию каждого из алгоритмов.
6. Попытаться скомбинировать эти алгоритмы с целью получения более помехоустойчивого решения для задачи отслеживания цели.
Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации. Обзор существующих методов
Задачи оптимизации можно рассматривать в постановках с дискретным и непрерывным временем. Мы ограничимся рассмотрением моделей первого типа. Пусть - функционал, который необходимо минимизировать в момент времени . Существуют несколько стандартных методов для решения подобных проблем, которые детально рассматриваются в книге Б.Т.Поляка [3] - методы Ньютона и градиентный, которые применимы в случае дважды дифференцируемого функционала при условии . Оба метода возможны при условии непосредственного измерения градиентов функционала в произвольной точке. В реальности же любые измерения всегда подразумевают наличие помех. Устойчивость алгоритма к помехам очень важна практически во всех инженерных приложениях. Для решения задач в условиях помех в пятидесятые годы XX века появляются методы стохастической аппроксимации Роббинса-Монро и Кифера-Вольфовица, история развития которых детально описана [3-5]. Общий подход для поиска экстремума, используемый в алгоритмах стохастической аппроксимации, может быть формализован следующим образом:
где - генерируемая алгоритмом последовательность оценок точки экстремума, - псевдоградиент (заменяющий градиент из метода Ньютона), который «в среднем» должен совпадать с градиентом и близок к нулю, когда его аргумент стремится к точке экстремума. Важными свойствами алгоритмов такого типа являются простота и рекуррентность, в силу которых они стали активно применяться в разных областях науки и техники.
Алгоритмы стохастической аппроксимации с пробным одновременным возмущением на входе и с одним или двумя на каждой итерации зашумленными измерениями минимизируемой функции появились в работах различных исследователей конце 80-х, начале 90-х гг. ХХ века. В англоязычной литературе они получили название Simultaneous Perturbation Stochastic Approximation (SPSA).
Эти алгоритмы известны состоятельностью оценок при почти произвольных помехах наблюдения, которые должны быть только в определенном смысле ограничены и независимы на каждой итерации с пробным случайным возмущением на входе. Более того, количество измерений исследуемой функции на одной итерации составляет всего 1 или 2 и не зависит от размерности пространства состояний. При этом они имеют оптимальный порядок асимптотической скорости сходимости (по числу итераций), что позволяет говорить о существенном повышении скорости сходимости в многомерном случае () по сравнению с классическими алгоритмами, оценивающими градиент через конечную разность, так как у них количество измерений на каждом шаге прямо пропорционально . Алгоритмы стохастической аппроксимации первоначально обосновывались в условиях минимизации стационарных функционалов. В [3] приведена версия алгоритма градиентного спуска для нестационарного случая и доказана его состоятельность в некотором смысле. Дальнейшее развитие эти идеи получили в статье [6] для более общего случая.
В [4] было предложено использовать для оптимизации нестационарных функционалов алгоритмы типа стохастической аппроксимации с пробным одновременным возмущением на входе, которые могли бы быть более эффективными, так как они полагаются только на одно или два измерения на каждом шаге, а значит, способны быстрее адаптироваться к изменениям функционала.
Постановка задачи
В статье [1] рассматривается применение алгоритма стохастической аппроксимации с пробным одновременным возмущением на входе для задачи оптимизации нестационарного функционала. Пусть время является дискретным и определяется номером шага (итерации) набор функций от двух векторных переменных, на каждом шаге n мы можем измерять значение:
где - известные (выбираемые) точки, в которых производятся наблюдения (план эксперимента), - независимые случайные величины, выражающие неконтролируемую неопределенность, заданные на некотором вероятностном пространстве и имеющие одинаковое, вообще говоря, неизвестное распределение , - искажения в наблюдениях (могут быть и неслучайные).
Рассмотрим задачу минимизации нестационарного функционала среднего риска:
.
Требуется оценить - точку минимума функции , изменяющуюся с течением времени:
.
Для характеристики поведения оценок точек минимума нестационарного функционала используем два определения, приведенных в статье [1]:
Определение 2.1. Последовательность оценок точек минимума стабилизируется в среднеквадратичном смысле, если существует такое , что
где E - символ математического ожидания.
Определение 2.2. Число называется асимптотической границей среднеквадратичных невязок оценивания, если для последовательности оценок точек минимума выполняется:
Алгоритм оценивания
Пусть - последовательность пробных одновременных возмущений, подаваемых на вход алгоритма оценивания, является некоторой реализацией последовательности независимых бернуллиевских случайных векторов из , у которых каждая компонента независимо принимает с вероятностью значения, равные .
Выберем некоторый начальный вектор . Авторы [1] предлагают оценивать последовательность точек минимума последовательностью , определяемой алгоритмом стохастической оптимизации с пробным одновременным возмущением на входе, который имеет следующий вид:
Для обоснования среднеквадратичной стабилизации оценок алгоритма будем считать, что
(RAND) случайные величины (рандомизация входа алгоритма) и , не зависят между собой, а также от , , , и , . Если полагаются случайной природы, то , , не зависят от , .
Среднеквадратичная стабилизация оценок
Будем рассматривать задачу о построении последовательности стабилизирующихся оценок при следующих условиях, описанных в статье [1]:
(A) Функции сильно выпуклые по первому аргументу для каждого :
(B) градиент удовлетворяет условию Липшица с константой :
и для него выполняется
(C) локальное свойство Лебега: окрестность и функция такие, что .
(D) Скорость дрейфа точки минимума ограничена следующими условиями:
(E) Для помех наблюдения выполнены условия
,
либо, если они представляют собой последовательность случайных величин, то
.
Заметим, что последнему условию удовлетворяют детерминированные, но ограниченные последовательности .
Условие (C) обеспечивает возможность перестановки операций интегрирования и дифференцирования при обосновании стабилизируемости оценок.
Ограничения типа (D) включают как дрейф типа случайных блужданий, так и направленный дрейф в определенную сторону. Например, можно рассматривать такое ограничение:
,
где является ограниченной случайной величиной. Среднеквадратичная стабилизируемость оценок алгоритма поиска минимума в условиях (D) означает применимость его к широкому классу различных задач.
Обозначим .
Для обоснования среднеквадратичной стабилизации оценок приведем теорему, описанную и доказанную в работе [1]:
Теорема 2.1. Пусть выполнены условия (A)-(E) и условие о рандомизации (RAND) и параметры алгоритма выбраны такими, что .
Если , тогда оценки алгоритма стабилизируются в среднеквадратичном смысле.
Кроме того, и для любого параметра , удовлетворяющего условию
,
справедливы оценки
,
где .
Заметим, что, в частности, в Теореме 2.1 устанавливается асимптотическая граница среднеквадратичных невязок оценивания
Эту формулу для границы можно минимизировать по . В результате получается
Условия (A)-(C), (E), (RAND) являются стандартными для доказательства состоятельности оценок алгоритмов стохастической аппроксимации с возмущением на входе.
Доказательство данной Теоремы 2.1 приведено в приложении к статье [1], здесь же мы приводить его не будем.
Выбор параметров
Рассмотрим практическое приложение алгоритма стохастической аппроксимации с пробным возмущением на входе для решения задачи минимизации нестационарного функционала. Пусть требуется оценить координаты движущейся точки в многомерном пространстве, когда единственная доступная информация на каждом шаге - это расстояние до нее, измеряемой с помехой. В силу Теоремы 2.1 оценки алгоритма будут стабилизироваться вдоль траектории движения при условии ограниченности нормы дрейфа экстремума.
Рассмотрим двумерный случай, когда модель дрейфа является участком окружности: . Можно рассмотреть семейство функций , которые определяют квадрат расстояния до искомой точки. Эти функции удовлетворяют условиям Теоремы 2.1. Выберем управляющие параметры алгоритма: , , . Добавим помеху: , где помехи . Еще один важный параметр алгоритма - число экспериментов. Алгоритм независимо запускается определенное число раз, затем производится усреднение по числу запусков, в результате повышается точность измерений. В наших примерах мы будем использовать 5 запусков алгоритма.
Ниже приведен график ошибки оценивания:
Рис.
Как видно, оценки некачественны, норма ошибки «скачет». Теперь попробуем запустить алгоритм с несколько другими параметрами: , . Ниже приведен график ошибки оценивания:
Рис.
Теперь нормы ошибок не превосходят 1, что является приемлемым результатом. Это видно и на графике траектории движения:
Рис.
Необходимо отметить, что путем выбора параметров РАСА можно влиять на точность, калибровать параметры для получения более точного результата. Для каждого типа помехи существует своя оптимальная пара , обеспечивающая наилучшую точность. Опытным путем было проверено, что для достижения наивысшей точности оценивания, большим помехам должно соответствовать меньшее , и наоборот. Таким образом, в каждом конкретном случае, с любой помехой, имеет место так называемая калибровка параметров, для любой помехи и любой траектории можно подобрать такую пару управляющих параметров , при которой достигается наивысшая точность оценивания точки минимума дрейфующего функционала. Вероятно, возможен строгий вывод связи между и в зависимости от величины помехи и явное получение эффективных параметров для каждого случая, но оставим этот вопрос на откуп авторам алгоритма.
Приведем еще один пример выбора параметров. Возьмем нормально распределенную помеху, принимающую значения от -3 до 3 ( в синтаксисе Matlab), с большим коэффициентом, :
Рис.
Рис.
На левом рисунке изображен график нормы ошибки оценивания при использовании следующих параметров алгоритма: . Видно, что при такой помехе эти параметры не годятся, поэтому путем подбора мы получили следующую пару: . Результат стал гораздо лучше, норма ошибки держится на уровне 1, что является приемлемым результатом.
Алгоритм отслеживания цели для машиноподобных роботов, использующий лишь расстояние до нее. Обзор существующих методов
В литературе встречаются множество разных сложных подходов к задаче отслеживания цели и трекинга траектории колесных роботов. Существует стратегия регулирования машиноподобного робота, использующая метод удаляющегося горизонта [8]. В работе Янга и Кима [9] предлагалось управление со скользящим режимом для задачи трекинга траектории неголономного мобильного робота. Схема управления в таком подходе основана на вычислении крутящего момента в сочетании с линеаризацией модели системы обратной связью. Всеобъемлющие краткое изложение существующих подходов и алгоритмов для планирования движения и управления колесными роботами представлено в работе Диксона, Доусона и др. [10].
Среди всех остальных подходов, управление со скользящим режимом для машиноподобного робота, вследствие быстрого отклика, хорошего переходного поведения и робастности против неопределенностей системы, получало все возрастающее внимание исследователей. Суть управления со скользящим режимом заключается в том, что траектория движения неизвестна заранее, она скользит вдоль ограничений управляющих структур, однажды попав на поверхность скольжения. Такое движение называется скользящим, а геометрическое место точек траектории - поверхность скольжения. Управляющие структуры в таких системах могут быть очень простыми, например они могут лишь определять двигаться вперед или назад. Поэтому главные свойства таких систем - робастность Робастность означает малое изменение выхода замкнутой системы управления при малом изменении параметров объекта управления., а также конечное время достижения поверхности скольжения. В статье [11] был предложен основанный на модели оператор со скользящим режимом для трекинга траектории подводного робота. Подход для стабилизации неголономных систем в терминах управления со скользящим режимом был предложен Блоком и Дракуновым [12]. Метод управления со скользящим режимом прокладывания пути для автономных транспортных средств описывается в работе Солеа и Нунеса [13].
Необходимо отметить, что большинство существующих подходов к трекингу траектории предполагают, что для алгоритмов навигации управления доступны одновременно и угол линии прямой видимости цели, и относительное расстояние до цели. Существует довольно много работ в исследовании навигационных алгоритмов, основанных только на измерении углов направления от объекта до цели. Напротив, опубликовано считанное число результатов в задаче навигации и управления к неизвестной цели с использованием измерения только лишь расстояния до нее.
Постановка задачи
В статье [2] рассматриваются два плоских мобильных робота, представляющее из себя одноколесные велосипеды. Они ездят с изменяющимися с течением времени скоростями и радиусами поворота, ограниченными известными константами. Линейное ускорение также ограничено подобным образом. Один из роботов, назовем его робот 1, выполняет роль цели, задача же второго следовать за целью на заданном расстоянии . В отличие от многих работ в данной области, в данном случае преследователь (робот 2) имеет доступ только лишь к текущему расстоянию до робота 1 и к производной расстояния . Ему также известны верхние границы скорости, ускорения и радиуса поворота робота 1. В то же время, он не имеет доступа к настоящим значениям этих переменных и он не знает, по какому управляющему правилу движется робот 1.
Кинематическая модель -ого робота () выглядит следующим образом:
(3.1)
Здесь - вектор декартовых координат соответствующего робота, - его направление, и - скорость и угловая скорость соответственно. Верхние границы , и даны.
В приведенной статье излагается следующая задача. По данным роботам, найти такой оператор, который асимптотически приведет робота 2 на требуемое расстояние () к роботу 1, независимо от характера движения последнего, то есть функций , , и , удовлетворяющих уравнению движения (3.1).
Алгоритм управления
В работе [2] описывается следующий управляющий алгоритм для преследователя (робот 2):
(3.2)
Где
а , - управляющие параметры. Также необходимо принять следующее допущение, которое предполагает, что преследующий робот более маневренный, чем робот-цель.
Предположение 3.1. Выполнены следующие неравенства: и .
Основной результат
Для начала предлагается ввести следующую константу, которая зависит от верхних границ скоростей , из (3.1) и параметра и используется при условии, что :
Чтобы достигнуть цели управления, необходимо сделать еще одно предположение.
Предположение 3.2. Начальная и требуемая дистанции между роботами достаточно велики:
где - минимальный радиус поворота робота 2, а - расчетный параметр, такой, что .
Теперь можно сформулировать основной результат, описанный в работе [2].
Теорема 3.1. Допустим, что предположения 1 и 2 выполнены, а параметры и управляющего оператора (3.2) выбраны так, что вместе с параметром из Предположения 3.2 они удовлетворяют следующему неравенству:
Тогда управляющий оператор (3.2) асимптотически направляет робота 2 на требуемое расстояние к роботу 1, то есть . Это верно независимо от характера движения робота 1.
Доказательство Теоремы приведено в приложении к статье [2].
Следующее дополнение к Теореме 3.1 проливает свет на особенности относительного движения роботов, показывая, что преследующий робот в конечном итоге движется по кругу вокруг цели, с угловой скоростью, превышающей определенный нижний порог. Чтобы строго обосновать это, введем движущуюся нормально-ориентированную декартову систему координат, центрированную по характеристической точке цели (робот 1). Оси системы сохраняют свои направления неизменными. Пусть и являются полярными координатами преследующего робота (робот 2) в такой системе. Иначе говоря, это расстояние между роботами, а алгебраический угол между осью абсцисс и вектором от цели к преследователю.
Предложение 3.1. Предположим, что условия Теоремы 3.1 выполнены. Тогда независимо от характера движения робота 1, выполняется одно из двух:
или
Комментарий 3.1:
1) Из Теоремы 3.1 и Предложения 3.1 следует, что в выбранной полярной системе координат, центрированной в положении робота-цели, робот-преследователь асимптотически движется вокруг точки начала координат на искомом расстоянии со скоростью . Если цель покоится (), эта система координат также не движется, а преследователь асимптотически вращается со скоростью по кругу радиуса с центром в точке положения цели.
2) Алгоритм управления (3.2) демонстрирует движение со скольжением для робота 2.
3) Легко показать, что число растет с ростом . Так, уменьшение улучшает нижнюю оценку в области притяжения, тогда как условие устойчивости (неравенство из Теоремы 3.1) не ограничивает снизу. В то же время, уменьшение может пагубно сказываться на качестве переходного процесса.
4) Учитывая предыдущее замечание, величина растет с ростом и . Принимая во внимание неравенство из Теоремы 3.1, это означает, что чем больше начальное и требуемое расстояния, тем больше свободы в выборе управляющих параметров.
5) Случай покоящейся цели. Рассматривая Теорему 3.1 и Предложение 3.1 с точки зрения неподвижной цели, мы получим следующее:
Следствие 3.1. Пусть цель покоится, , , и
Предположим также, что параметры и управляющего оператора (3.2) удовлетворяют неравенству:
Тогда управляющий оператор (3.2) направляет робота 2 на требуемое расстояние к роботу 1, то есть . Асимптотически, преследователь описывает окружности вокруг цели на требуемом расстоянии таким образом, что вектор от цели к преследователю крутится с угловой скоростью , где .
Комментарий 3.2:
1) Оператор такого сорта (3.2) не может обеспечивать глобальную сходимость даже для покоящейся цели. Для любых управляющих параметров существует непустое множество в фазовом пространстве, такое, что когда бы робот 2 не вошел в него, впоследствии он движется с постоянной угловой скоростью по окружности радиуса . Тогда расстояние колеблется и не сходится к . Именно поэтому неизбежны требования к начальному и искомому расстояниям между роботами (Предположение 3.2).
2) В случае покоящейся цели можно выполнить комплексный анализ поведения, демонстрируемого управляющим алгоритмом (3.2), для любых значений параметров. Можно показать, что, как только параметр превышает определенный порог, вышеуказанная область несходимости становится бесконечной: всякий раз, когда роботы изначально далеки друг от друга, сходимость все равно не выполняется. Если же превышает другой, еще больший порог, сходимость не выполняется для почти всех начальных состояний.
Выбор параметров
Для демонстрации влияния параметров на работу алгоритма, рассмотрим вариант с преследованием покоящейся цели. Зададим начальные положения роботов, а также верхние границы их линейных и угловых скоростей:
Зададим требуемое расстояние, , а также выберем управляющие параметры , и , которые удовлетворяют условию Теоремы 3.1. Применив данный алгоритм с заданными параметрами, мы получим, что преследующий робот приближается к неподвижной цели и описывает вокруг нее окружности, таким образом, что . Геометрия движения робота до того момента, как он попадет на орбиту цели, называется логарифмической спиралью:
Рис.
Теперь попробуем запустить алгоритм с другими параметрами. Начальные положения, верхние границы линейных и угловых скоростей оставим прежними. Изменим лишь управляющие параметры (, и ):
Рис.
Видно, что если , то спираль стремится к прямой линии, которая является оптимальной траекторией. Отметим, что выбор параметров здесь влияет лишь на скорость достижения цели, а не на точность, как в алгоритме стохастической аппроксимации. В то же время достигается робастность системы от выбора управляющих параметров - какими бы мы ни выбирали параметры, если они будут удовлетворять Предположениям и Теореме 3.1, управляющий алгоритм непременно приведет траекторию в область скольжения.
Анализ двух алгоритмов
В данном разделе мы будем анализировать результаты моделирования работы обоих алгоритмов на одинаковых задачах. Мы возьмем конкретную траекторию дрейфа точки минимума в случае рандомизированного алгоритма стохастической аппроксимации и такую же траекторию движения робота-цели в алгоритме отслеживания цели для машиноподобного робота. Затем добавим разнообразные помехи для того, чтобы понять, как алгоритмы справляются с ними. Теоретические выкладки обещают, что алгоритм стохастической аппроксимации лучше справится с помехами и даст более точные оценки. Наша задача - проверить это на конкретных примерах.
Пусть искомая точка дрейфует по участку окружности:
Выберем следующие управляющие параметры:
· число запусков РАСА по-прежнему будет 5, ,
· количество шагов обоих алгоритмов - 500.
· параметры алгоритма трекинга останутся равными , , , .
· верхние границы скоростей также оставим без изменений: , , , .
· алгоритмы начинаю свою работу в точке , цель же начинает дрейф в точке .
Для начала рассмотрим случай без помех в измерениях. Так выглядит результат моделирования работы РАСА. Ломаная на координатной плоскости изображает траекторию, доставляемую алгоритмом стохастической аппроксимации, спиралевидная же линия является траекторией движения робота-преследователя в алгоритме трекинга:
Рис.
На этом рисунке траектория, генерируемая РАСА, сливается с траекторией цели из-за характера работы алгоритма и масштаба - алгоритм отслеживает цель фактически по ее следу, в то время как робот-преследователь из алгоритма трекинга имеет спиралевидную траекторию движения, отсюда и видимые петли вокруг цели.
Рис.
Рис.
Как видно из графиков, РАСА гораздо быстрее получает приемлемые оценки, но дает немного худшую точность ( против ). Алгоритм трекинга же дал очень хорошие результаты, показав близкие к нулю ошибки оценивания. Заметим, что если откалибровать управляющие параметры РАСА на (), то можно добиться также почти нулевой погрешности РАСА, и алгоритмы будут доставлять одинаковые оценки.
Оценки, доставляемые алгоритмом стохастической аппроксимации, в данном примере качественны уже начиная с 30-40 шага (ошибки оценивания сильно меньше 1). Оценки же алгоритма трекинга траектории в данных условиях стабилизируются только к 200 шагу. Как говорилось в Разделе 3.5, путем иного выбора управляющих параметров, можно добиться более быстрого достижения приемлемых оценок, но все равно они будут колебаться в районе 100-го шага. Стоит отметить, что выбор управляющих параметров ограничен условиями сходимости алгоритма, о чем подробнее написано в комментариях к Теореме 3.1, поэтому более быстрой сходимости достичь не удастся - алгоритм расходится.
Теперь будем добавлять различные помехи. Начнем с помехи неслучайного характера: для четных шагов и для нечетных. Возьмем три случая - приведенный, и случай, когда помеха умножается на некий множитель (). Графики траекторий приводить не будем ввиду их схожести со случаем без помех. Поэтому будем рассматривать только графики ошибок оценивания.
Алгоритмы РАСА и трекинга, неслучайная помеха, :
Рис.
Рис.
Опять же мы видим более быструю сходимость РАСА, в совокупности уже c более лучшей точностью - порядок ошибки остался практически без изменений для РАСА, и существенно вырос для алгоритма трекинга.
Теперь рассмотрим случай, когда помеха взята с весовым коэффициентом, .
Алгоритмы РАСА и трекинга, неслучайная помеха, :
Рис.
Рис.
На этот раз точность РАСА ухудшилась незначительно, в то время как алгоритм трекинга начал сильно портить оценки (высокая интенсивность графика). В свете этого факта интересно посмотреть на траекторию, получаемую вторым алгоритмом, так как график оценок сильно колеблется.
Траектория движения алгоритма трекинга, :
Рис.
Видно, что траектория получается очень «рваной», отчетливо видны петли, описываемые роботом-преследователем вокруг цели (отсюда и такая интенсивность графика). В целом, можно сказать, что с данной помехой алгоритмы справились хорошо.
Для интереса попробуем еще увеличить плечо помехи: . Вместе с этим, для РАСА необходимо изменить управляющие параметры: теперь . Получается следующая картинка:
Рис.
Рис.
Нормы ошибок оценивания алгоритма трекинга слишком велики, поэтому в дальнейшем не будем рассматривать такой коэффициент в помехах - и так ясно, что с весами подобного рода алгоритм не справляется. Ошибки же РАСА подросли незначительно (порядка ).
Теперь возьмем равномерно распределенную помеху: .
Алгоритмы РАСА и трекинга, равномерная помеха, :
Рис.
Рис.
Алгоритмы РАСА и трекинга, равномерная помеха, :
Рис.
Рис.
Мы видим, что в первом случае алгоритмы опять же дают более-менее сходные результаты (усредненное значение ошибки второго алгоритма примерно равно ). Но в случае наблюдается резкое увеличение ошибки для алгоритма преследования цели, что говорит о сильных колебаниях петлей траектории. Примечательно, что оценки, доставляемые алгоритмом стохастической аппроксимации, портятся очень незначительно.
В свете этого факта, интересно взглянуть на траекторию движения робота во втором алгоритме для случая :
Рис.
Как и было верно предположено из графика ошибки, петли сильно искажены, появляются лишние витки вдали от цели, траектория практически «разрушена».
Теперь протестируем следующую, нормально распределенную на отрезке длинной равной количеству шагов, помеху. В синтаксисе Matlab она принимает значения от до и описывается следующим образом: . Алгоритмы РАСА и трекинга, нормальная помеха, :
Рис.
Рис.
Алгоритмы РАСА и трекинга, нормальная помеха, :
Рис.
Рис.
Опять же, как и в случае с нормально распределенной помехой, мы наблюдаем более-менее достойные результаты алгоритма трекинга в первом случае, так как ошибка стабильно не превосходит 1. Зато в случае наблюдается резкое ухудшение оценок второго алгоритма, еще более сильное, чем при равномерной помехе с тем же множителем. Ошибки же оценивания РАСА по-прежнему малы.
Взглянем на траекторию преследования цели алгоритма трекинга:
Рис.
На этой помехе алгоритм практически разошелся, оценки, доставляемые алгоритмом, некачественны и носят почти случайный характер. Таким образом, алгоритм отслеживания цели, использующий только информацию о расстоянии до нее, оказался устойчив лишь к небольшим помехам, при добавлении более сильных помех алгоритм стремительно теряет в качестве, и ошибки оценивания растут высокими темпами. Стоит отметить, что это неудивительно, так как алгоритм стохастической аппроксимации с пробным одновременным возмущением на входе и 1-2 измерениями на итерации специально ориентирован на нивелирование помех в своих оценках, в то время как в алгоритме трекинга такой задачи не стояло. Поэтому очень интересно было протестировать на реальных примерах, как же они справляются с одними и теми же классами помех.
Все тесты проводились с одинаковыми параметрами: для РАСА и для алгоритма трекинга. Необходимо отметить, что если перебор параметров алгоритма трекинга влияет только на скорость сходимости, то путем выбора параметров для РАСА можно влиять на точность, калибровать параметры для получения более точного результата. Для каждого типа помехи существует своя оптимальная пара , обеспечивающая наилучшую точность. Подробнее выбор параметров описан в Разделе 2.5.
Теперь рассмотрим последний случай, в котором помеха генерируется по закону синуса: .
Алгоритмы РАСА и трекинга, синусоидальная помеха, :
Рис.
Рис.
Алгоритмы РАСА и трекинга, синусоидальная помеха, :
Рис.
Рис.
Опять мы видим знакомую ситуацию - ошибка оценивания РАСА в случае держится на уровне чуть выше 0.1, в то время как ошибки алгоритма трекинга колеблются в районе 0.25.
В случае , как и во всех предыдущих экспериментах, когда алгоритм трекинга становился близок к расхождению, появляются сильные колебания в графике ошибок оценивания, что мы и видим на данных рисунках.
Ниже приведена траектория преследования цели алгоритмом трекинга:
Рис.
Как легко заметить, данный график с большой натяжкой можно назвать траекторией отслеживания цели. Данный алгоритм не выдержал синусоидальной помехи с коэффициентом .
Подводя итог анализу данных алгоритмов, необходимо сделать следующие выводы:
Во-первых, эксперименты показали, что алгоритм трекинга со скользящим режимом дает более точные оценки в случае отсутствия помех, а при некоторых классах помех и небольших коэффициентах дает сходные с РАСА оценки. С другой стороны, РАСА отлично работает и абсолютно устойчив к помехам практически произвольной природы, достаточно, чтобы они были ограничены в некотором смысле. Как видно из примеров, РАСА справляется даже с большими весовыми коэффициентами помех, путем специального выбора управляющих параметров (Раздел 2.5). Ошибки оценивания растут очень незначительно, а сам алгоритм практически не теряет в скорости сходимости. Алгоритм трекинга же при наличии даже небольших помех (за исключением некоторых случаев) начинает расходиться, а при добавлении весовых коэффициентов (случаи со ) к помехам фактически разваливается.
Во-вторых, необходимо уделить некоторое внимание времени работы алгоритмов. Несмотря на то, что алгоритм трекинга из-за гладкости траектории сходится медленнее, чем РАСА, в целом он работает существенно быстрее из-за меньшего количества вычислительных операций на каждом шаге. С другой стороны, РАСА гораздо быстрее достигает цели (это хорошо продемонстрировано на самом первом рисунке, где изображены одновременно траектории обоих алгоритмов), это может быть очень полезно в определенных задачах, например, в стационарном случае. Быстрота сходимости второго же алгоритма ограничена условиями на линейные и угловые скорости роботов.
В-третьих, можно сделать вывод, что алгоритм стохастической аппроксимации с пробным возмущением на входе и 1-2 измерениями на итерации следует использовать в задачах, где отсутствует гладкое движение и присутствуют помехи, так как он хорошо нивелирует их влияние на итоговые оценки. Напротив, алгоритм отслеживания цели хорошо зарекомендовал себя в ситуациях без помех, либо же в случаях наличия очень незначительных помех. Также он применим для непосредственной навигации роботов.
В-четвертых, нельзя не упомянуть, что, в общем случае, РАСА ориентирован на более широкий круг задач - ведь функционалы, которые надо минимизировать, вообще говоря, не обязательно являются функциями расстояния между точками. В частности, можно применить данный алгоритм для управления загрузкой узлов распределенной вычислительной системы, где помехами являются сторонние задачи, а минимизируемый функционал является функцией распределения задач по узлам и минимизируется по времени выполнения.
В-пятых, заметим, что робот-преследователь из алгоритма трекинга описывает вдоль траектории цели окружности радиусом . Поэтому алгоритм трекинга со скользящим режимом успешно применяется в аэронавигационных задачах, например, в управлении беспилотными летательными объектами.
Комбинированный алгоритм
Анализируя выводы предыдущего раздела, заметим, что единственный серьезный недостаток алгоритма трекинга - это его слабая, почти нулевая помехоустойчивость. Попробуем оптимизировать его с целью достичь необходимой помехоустойчивости.
Для этого поступим следующим образом. Известно, что алгоритм трекинга со скользящим режимом использует в качестве информации для навигации робота-преследователя только расстояние до целевого робота. Что делать, если такое расстояние измеряется с ошибкой?
В данной работе предлагается следующее решение: использовать вместо данного расстояния информацию, полученную от рандомизированного алгоритма стохастической аппроксимации. Таким образом, новое расстояние будет получаться как , где - текущее местоположение робота-преследователя, а - очередная оценка, доставленная алгоритмом стохастической аппроксимации. Надо отметить, что примеров такого симбиоза алгоритмов много - очень часто требуется калибровка параметров в процессе работы основного алгоритма. Роль калибровщика выполняет РАСА, нивелируя почти произвольные помехи.
Таким образом, алгоритм трекинга со скользящим управлением приобретает важное свойство - помехоустойчивость от РАСА, не теряя при этом остальных своих качеств. Продемонстрируем данный факт результатами путем моделирования работы такого комбинированного алгоритма. Для начала приведем результат работы алгоритма трекинга в случае, когда нет помех в измерениях расстояния, а само расстояние измеряется обычным образом. Затем покажем траекторию, доставляемую тем же алгоритмом, но с равномерно распределенной помехой. Наконец, мы приведем результат работы комбинированного алгоритма и сравним уровни ошибок оценивания. Случай без помех, обычный алгоритм трекинга:
Рис.
Равномерно распределенная взвешенная помеха, обычный алгоритм трекинга:
Рис.
Комбинированный алгоритм, та же помеха:
Рис.
Исходя из графиков, можно предположить, что новый подход отлично справился с задачей нивелирования помех. Продемонстрируем данный факт количественными оценками ошибок.
Обычный (слева) и комбинированный (справа) алгоритмы:
Рис.
Рис.
Мы добились того, чего хотели - уровень ошибки существенно снизился, получившийся алгоритм приобрел помехоустойчивость РАСА.
Как говорилось, задача отслеживания траектории и навигации с использованием только данных о расстоянии до цели возникает во все возрастающем количестве практических приложений - например, в области беспроводных сетей, управлении беспилотными подводными устройствами, системах наблюдения и безопасности, и во многих других, где единственная доступная информация о цели - это расстояние между ней и преследующим роботом. Такое расстояние может получаться путем измерений, например, времени отклика акустического сигнала от объекта или силой сигнала, полученного от искомого объекта. Такой подход может потенциально повлечь за собой существенное уменьшение сложности и стоимости управляющего оборудования. Однако в реальном мире измерения всегда предполагают наличие помех. Получившийся же в результате симбиоза РАСА и Алгоритма трекинга со скользящим режимом алгоритм успешно решает задачу отслеживания траектории и навигации для мобильного колесного робота, невзирая на помехи в измерениях.
Заключение
В ходе дипломной работы автором были достигнуты следующие цели:
1. Описанные в тексте дипломной работы, а также в статьях [1], [2] алгоритмы полностью реализованы в среде Matlab.
2. Для анализа алгоритмов выбрана задача отслеживания движущейся точки и дальнейшее ее преследование на заданном расстоянии.
3. Изучено поведение данных алгоритмов на различных входах и их зависимость от управляющих параметров.
4. Проведен комплексный анализ алгоритмов применительно к задаче трекинга траектории с использованием четырех классов помех: неслучайная помеха, равномерно распределенная помеха, нормально распределенная помеха и синусоидальная помеха, а также отдельно был рассмотрен случай с отсутствующими помехами. Кроме того, все помехи рассматривались с разными весовыми коэффициентами, повышающими их абсолютную величину.
5. Получены рекомендации по эффективному использованию каждого из алгоритмов.
6. На основе анализа двух алгоритмов получен новый комбинированный алгоритм, который является модификацией обычного алгоритма трекинга со скользящим режимом, решает ту же задачу, но обладает помехоустойчивостью рандомизированного алгоритма стохастической аппроксимации.
Список литературы
1.Вахитов А. Т., Граничин О. Н., Гуревич Л. С. Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации. - 2009.
2.A. S. Matveev, H. Teimoori and A. V. Savkin, «The Problem of Target Following Based on Range-only Measurements For Car-like Robots», Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference, December 2009.
3.Поляк Б. Т. Введение в оптимизацию. - М.: Наука. 1983.
4.Граничин О. Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. - М.: Наука. 2003. 291 с.
5.Kushner H, Yin G. Stochastic Approximation and Recursive Algorithms and Applications. - Springer. 2003.
6.Попков А. Ю. Градиентные методы для нестационарных задач безусловной оптимизации // Автоматика и телемеханика. 2005. №6. С. 39-47.
7.Gurevich L., Vakhitov A. SPSA Algorithm for Tracking // In Proc. 12-th International Student Olympiad on Automatic Control (Baltic Olympiad). 2008. PP. 52-57.
8.D. Gu and H. Hu, «A stabilizing receding horizon regulator for nonholonomic mobile robots,» IEEE Transactions on Robotics and Automation, vol. 21, no. 5, pp. 1022-1028, October 2005.
9.J. M. Yang and J. H. Kim, «Sliding mode control for trajectory tracking of nonholonomic wheeled mobile robots,» IEEE Trans. on Robotics and Automation, vol. 15, no. 3, pp. 578-587, 1999.
10.W. E. Dixon, D. M. Dawson, E. Zergeroglu, and A. Behal, Nonlinear Control of Wheeled Mobile Robots. London: Springer-Verlag, 2001.
11.B. Xu, S. Pandian, M. Inoue, N. Sakagami, and S. Kawamura, «Modelbased sliding mode control of underwater robot manipulators,» Int. J. Offshore and Polar Engineering, vol. 16, pp. 210-217, 2006.
12.A. Bloch and S. Drakunov, «Stabilization of a nonholonomic system via sliding modes,» in Proc. IEEE Int. Conf. Decision Contr., pp. 2961-2963, Dec. 1994.
13.R. Solea and U. Nunes, «Trajectory planning and sliding-mode control based trajectory-tracking for cybercars,» Integr. Comput.-Aided Eng., vol. 14, no. 1, pp. 33-47, 2007.
Размещено на Allbest.ru
Подобные документы
Анализ алгоритмов, оценка параметров алгоритма (эффективности, сложности, правильности). Комплексный анализ эффективности алгоритма на основе комплексной оценки ресурсов формальной системы. Верификация при коллективной разработке программных систем.
презентация [234,9 K], добавлен 22.10.2013Комплексное исследование истории развития, основных понятий, области применения и особенностей генетических алгоритмов. Анализ преимуществ генетических алгоритмов. Построение генетического алгоритма, позволяющего находить максимум целочисленной функции.
курсовая работа [27,9 K], добавлен 23.07.2011Обзор основных алгоритмов и методов распознавания лиц. Архитектура средств динамического отслеживания лиц в видеопоследовательности. Результаты тестирования на больших объемах видеоданных. Разработка алгоритмов и методов динамического отслеживания лиц.
дипломная работа [5,9 M], добавлен 20.07.2014Виды алгоритмов как логико-математических средств, характеристика свойств. Корректный вывод алгоритма при решении вычислительной задачи. Механизм реализации алгоритма, его описание. Решение задачи Майхилла при помощи автоматной модели поведения стрелка.
курсовая работа [53,6 K], добавлен 17.07.2014Критерии и основные стратегии планирования процессора. Разработка моделей алгоритмов SPT (Shortest-processing-task-first) и RR (Round-Robin). Сравнительный анализ выбранных алгоритмов при различных условиях и различном количестве обрабатываемых данных.
курсовая работа [179,3 K], добавлен 21.06.2013Понятие алгоритма и анализ теоретических оценок временной сложности алгоритмов умножения матриц. Сравнительный анализ оценки временной сложности некоторых классов алгоритмов обычным программированием и программированием с помощью технологии Open MP.
дипломная работа [1,6 M], добавлен 12.08.2017Создание схем алгоритмов и составление программы на языке Pascal для вычисления значений заданных функций. Сущность и порядок нахождения значения определенного интеграла. Анализ работы подпрограмм. Разработка тестов для проверки правильности алгоритмов.
контрольная работа [831,0 K], добавлен 24.11.2013Основные особенности эволюционных алгоритмов. Описание алгоритмов селекции, мутации, скрещивания, применяемых для реализации генетических алгоритмов. Вычисление функции приспособленности. Программная реализация. Тестирование и руководство пользователя.
курсовая работа [1,3 M], добавлен 11.03.2014Проблема улучшения качества отпечатков пальца с целью повышения эффективности работы алгоритмов биометрической аутентификации. Обзор алгоритмов обработки изображений отпечатков пальцев. Анализ алгоритма, основанного на использовании преобразования Габора.
дипломная работа [4,5 M], добавлен 16.07.2014Появление алгоритмов, связанных с зарождением математики. Последовательность алгоритмов решения задач. Словесная форма их записи. Система обозначений при графическом способе записи алгоритма. Алгоритм, в котором команды выполняются одна за другой.
презентация [262,8 K], добавлен 19.01.2015
