Введение
ГЛАВА 1 14
Обзор задачи локализации мобильного объекта 14
1.1. Постановка задачи локализации 14
1.2. Обзор алгоритмов и обоснование места работы
1.2.1. Базовые понятия задачи локализации 25
1.2.2. Задача о картинной галерее 30
1.2.3. Алгоритм локализации объекта с использованием декомпозиции карты на ячейки видимости 32
1.2.4. Алгоритм локализации объекта, использующий рандомизацию при проверке гипотез 35
1.2.5. Алгоритм локализации объекта на основе решения полугрупповой задачи Штейнера 37
Выводы по первой главе 39
ГЛАВА 2 40
Алгоритмы локализации мобильного объекта 40
2.1. Анализ алгоритмов локализации объекта 40
2.1.1. Выделение основных подзадач 40
2.1.1.1. Генерация гипотезы 40
2.1.1.2. Построение скелета многоугольнка видимости 41
2.1.1.3. Кратчайший путь между двумя точками в многоугольнике 41
2.1.1.4. Пересечение двух многоугольников 41
2.1.2. Обобщенный алгоритм решения задачи 42
2.2. Алгоритм локализации мобильного объекта с использованием триангуляции карты 43
2.3. Алгоритм локализации мобильного объекта с использование окон в многоугольнике карты 52
2.4. Идеи и необходимые элементы алгоритмов ЛМО 56 2.5. Базовые задачи предлагаемых алгоритмов 57
2.5.1. Вычисление скелета многоугольника видимости 57
2.5.2. Пересечение многоугольников 61
Выводы по второй главе 67
ГЛАВА 3 68
Программа решения и исследования задачи локализации мобильного объекта, снабженного картой 68
3.1. Разработка структуры программы решения и исследования задачи локализации мобильного объекта, снабженного картой. 68
3.2. Разработка алгоритма и программы генерации различных видов и разных размеров карты, представленной в виде простого многоугольник . 71
3.3. Реализация алгоритма генерации гипотез локализации 76
3.4. Алгоритм локализации объекта с использованием декомпозиции карты на ячейки видимости. 80
3.5. Алгоритм локализации объекта, использующий рандомизацию при проверке гипотез 82
3.6. Алгоритм локализации объекта с использованием триангуляции карты. 84
3.7. Алгоритм локализации объекта с использованием окон в многоугольнике карты. 86
Выводы по третьей главе 88
ГЛАВА 4 89
Испытание алгоритмов локализации мобильного объекта на можестве сгенерованных карт 89
4.1. Сравнение алгоритмов 1, 2, 3 и 4 89
4.2. Сравнение алгоритмов 2, 3 и 4 98
4.3. Сравнение алгоритмов 2, оптимизированного алгоритма 3 и 4
Выводы по четвертой главе 111
Заключение 112
Список литературы
