Санкт-Петербургский Государственный Университет

Математико-механический факультет

Кафедра Информатики

Моделирование и анализ алгоритмов отслеживания цели, использующих только расстояние до нее
Дипломная работа студента 542 группы

Соколова Павла Михайловича

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

Аспирант…………………………………………………………/А. Т. Вахитов/
Рецензент,

д.ф.-м.н, профессор……………………………………………/О. Н. Граничин/

“Допустить к защите”

Заведующий кафедрой,

д.ф.-м.н. профессор……………………………………………/Н. К. Косовский/

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

2010

St. Petersburg State University

Faculty of Mathematics and Mechanics

Chair of Computer Science

Modeling and analysis of target following algorithms based on range-only measurements
Graduate paper of 542 group’s student

Pavel Mikhailovich Sokolov

Scientific Advisor,

Post-graduate student………………………………………………/A. T. Vakhitov/
Reviewer,

Dr. of Phys. and Math. Sci., Professor……………………………/O. N. Granichin/

“Admitted to Defense”

Head of the Chair,

Dr. of Phys. and Math. Sci., Professor………….………………/N. K. Kosovskiy/

St. Petersburg

2010

Оглавление

Введение

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

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

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

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

1. Цель работы

Целью работы является проведение всестороннего анализа алгоритмов преследования цели, основанных только лишь на измерении расстояния до нее. Для анализа и моделирования были выбраны два алгоритма: Алгоритм стохастической аппроксимации с пробным возмущением на входе [1] и Алгоритм отслеживания цели и трекинга траектории на основе лишь данных о расстоянии до нее [2]. Обе статьи были представлены на международной конференции² в Шанхае, в декабре 2009 года.

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

1. 
   Реализовать данные алгоритмы.
   

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

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

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

3. 
   Изучить изменение поведения алгоритмов в зависимости от входных параметров.
   
4. 
   Провести серию экспериментов на предмет анализа алгоритмов.
   

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

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

2. 
   следующая страница>