Разработка, реализация и исследование эффективных алгоритмов локализации мобильных объектов, снабженных картой внешней среды Дао Зуй Нам

Содержание к диссертации

Введение

ГЛАВА 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

Список литературы

• Алгоритм локализации объекта с использованием декомпозиции карты на ячейки видимости
• Построение скелета многоугольнка видимости
• Разработка алгоритма и программы генерации различных видов и разных размеров карты, представленной в виде простого многоугольник
• Сравнение алгоритмов 2, оптимизированного алгоритма 3 и 4

Введение к работе

Актуальность темы исследования. Прикладная задача локализации мобильных
объектов часто встречается при решении научно-технических задач, например, в областях
робототехники, исследования Мирового океана, в системах двойного назначения и т.п.
Задача определения точного местоположения мобильного объекта – проблема локализации
или позиционирования, - является одной из важнейших задач, а для её формализации,
получения алгоритма решения и его программной реализации используются модели и
методы вычислительной геометрии и программирования. Информация о точном
местоположении мобильного объекта необходима для решения более сложных и
комплексных задач навигации, построения пути и построения карты окружающей среды.
Существует несколько различных подходов к решению проблемы локализации. Эти подходы
основаны на применении различных сенсоров, используют алгоритмы обработки данных и
управления перемещениями мобильного объекта. Один из подходов к локализации основан
на применении моделей и методов вычислительной геометрии (computational geometry),
которые позволяют анализировать все гипотетические местоположения объекта и при этом
минимизировать расстояние, проходимое объектом в процессе локализации.

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

Сформулированную выше задачу локализации мобильного объекта (ЛМО) можно
классифицировать как детерминированную геометрическую оптимизационную задачу.

Наряду с ней могут рассматриваться и другие актуальные формы постановки задачи ЛМО, например, такие как:

1. Стохастическая задача, включающая оценивание (фильтрацию) состояния объекта;

2. Кооперативная задача для группы объектов;

3. Одновременная локализация и составление объектом карты (SLAM).

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

Целью диссертационной работы является разработка быстрых алгоритмов локализации

мобильного объекта и их программных реализаций, исследование и анализ их

эффективности (в первую очередь с точки зрения времени выполнения в сравнении с
известными алгоритмами).

Для достижения поставленной цели в процессе выполнения диссертационной работы решены следующие задачи:

4. Анализ методов и алгоритмов локализации мобильного объекта. Анализ сложности и сравнение реализаций алгоритмов ЛМО.

5. Формирование обобщенного алгоритма локализации мобильного объекта.

6. Разработка алгоритма генерации гипотез локализации с использованием триангуляции простого многоугольника.

7. Разработка алгоритмов локализации на основе систематического использования триангуляции простого многоугольника.

8. Разработка реализации алгоритмов локализации мобильного объекта:

1. Алгоритма с использованием декомпозиции карты на ячейки видимости.

2. Алгоритма, использующего рандомизацию при проверке гипотез.

3. Алгоритма на основе триангуляции карты.

4. Алгоритма с использованием окон в многоугольнике карты.

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

7. Компьютерное исследование и сравнительный анализ реализаций алгоритмов ЛМО на множестве сгенерированных карт.

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

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

Методы исследования. Теоретическая часть работы выполнена на основе применения
моделей, методов и алгоритмов вычислительной (алгоритмической) геометрии,

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

Научная новизна полученных результатов заключается в следующем:

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

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

/'. Алгоритм локализации объекта с использованием триангуляции карты. п. Алгоритм локализации объекта с использованием окон в многоугольнике карты.

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

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

Практическая значимость результатов диссертационной работы заключается в разработке инструментария и технологии построения алгоритмов ЛМО на основе методов детерминированной геометрической оптимизации. На защиту выносятся следующие основные результаты и положения:

1. Алгоритм построения скелета многоугольника видимости (относительно текущего положения объекта) на основе триангуляции многоугольника карты.

2. Приближённый алгоритм локализации мобильного объекта с систематическим использованием триангуляции карты.

3. Приближённый алгоритм локализации мобильного объекта с использованием окон в многоугольнике карты.

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

5. Программные реализации алгоритмов локализации мобильного объекта, снабженного картой; программа компьютерного моделирования для сравнительного исследования алгоритмов (объем кода на C++ « 28000 строк).

Апробация работы. Основные результаты работы докладывались и обсуждались на 66-й научно-технической конференции профессорско-преподавательского состава СПБГЭТУ «ЛЭТИ» (Санкт-Петербург, январь-февраль 2013 г.), Всероссийской научной конференции по проблемам управления в технических системах (ПУТС-2015, СПБГЭТУ «ЛЭТИ», Санкт-Петербург, 28-30 октября 2015), а также на Международной конференции Informational Conference Southeast Asian Open and Distance Learning in the 21^st Century “ISODL”, 2012 г. Достоверность научных положений и результатов работы, полученных с применением математического аппарата вычислительной геометрии и геометрической оптимизации, подтверждается результатами вычислительных экспериментов, результатами испытаний разработанных программных средств в условиях моделирования различных видов и разных размеров многоугольника карты.

Реализация и внедрение результатов. Теоретические и практические результаты работы использованы в учебном процессе кафедры МОЭВМ СПБГЭТУ «ЛЭТИ». Публикации. По теме работы опубликованы 10 научных работ, среди которых 5 публикаций в ведущих рецензируемых изданиях, рекомендованных ВАК, 1 статья в другом издании, 3 доклада на международных, всероссийских и межвузовских научно-технических конференциях, 1 свидетельство о регистрации программы для ЭВМ.

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

Алгоритм локализации объекта с использованием декомпозиции карты на ячейки видимости

Сформулируем теперь основные модельные предположения о самом объекте:

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

2. У объекта имеется карта среды, то есть ему известен многоугольник карты P и его ориентация в пространстве.

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

4. У объекта имеется компас и устройства для определения расстояний от точки стояния (от текущего местоположения) до «видимых» преград;

5. Из своего текущего местоположения объект может сделать ряд наблюдений (обследований окрестности). Наблюдения имеют результатом набор измерительных данных (см. следующий пункт), позволяющий определить (вычислить) видимую из данной позиции p область (так называемый многоугольник видимости) V = V(p). Объекту также известно его местонахождение в многоугольнике V.

6. Датчики (сенсоры) объекта могут обеспечить измерение расстояния до тех точек на границах, до которых можно провести прямую линию (отрезок луча) от объекта, не выходя за границы многоугольника карты, т.е. не пересекая других сторон многоугольника, и не касаясь других вершин или сторон многоугольника (см. рис.1.2, справа). В прикладных задачах такого рода данные могут быть получены, например, от лазерных дальномеров. Отметим, что в случае положения объекта в точке p2 любое малое смещение его по направлению вверх (на север) сделает все точки стороны de «видимыми» и расстояние от точки p2 до них - измеримым.

7. Объект перемещается со скоростью v и время регистрации и обработки его наблюдений

Итак, объект снабжен компасом и сенсорным устройством (п.4), с помощью которого он осуществляет круговой обзор и определяет расстояние до преграды (п.5-6). Отметим, что наличие компаса принципиально, поскольку позволяет сопоставлять текущее местонахождение (многоугольник видимости) с областями карты. В случае отсутствия компаса объект не сможет правильно сориентировать карту (то есть «привязать» её по направлению), и задача локализации в этом случае, вообще говоря, не будет иметь единственного решения (например, в простейшем случае квадрата однозначная локализация возможна только при положении объекта в центре квадрата, во всех остальных точках имеются 4 решения, отличающиеся поворотами на угол /2, и 3/2).

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

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

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

Одним из реальных примеров окружающей среды такого типа являются офисные здания или отели, где несколько множеств комнат, коридорного пространства и других общих пространств могут иметь идентичную структуру (если отвлечься от оформления интерьера и наличия мебели). Следовательно, если бы объект оказался ("проснулся") в одной такой комнате, оценка его начального местоположения была бы неоднозначной, так как нельзя принять единственное решение, в какой из многих подобно выглядящих комнат (помещений) объект в действительности находится. Неоднозначность окружающей среды обязательно влечет за собой необходимость осуществить перемещение объекта с намерением найти в окружающем пространстве ориентиры, позволяющие устранить (или хотя бы для начала уменьшить) неоднозначность. Например, на рисунке 1.3, перемещение из любого начального положения A, B, C, D, E, F, G или H с выходом в горизонтальный «коридор» снимает неоднозначность.

Построение скелета многоугольнка видимости

Сформулируем теперь основные модельные предположения о самом объекте: 1. Объект мобилен и способен перемещаться в статическом двумерном пространстве в замкнутой области, ограниченной на плоскости многоугольной преградой без дополнительных препятствий. Допустимому положению объекта сопоставляется точка p внутри многоугольника карты или на его границе (см.рис.1.2, слева). Движение объекта моделируется как движение точки в многоугольнике. 2. У объекта имеется карта среды, то есть ему известен многоугольник карты P и его ориентация в пространстве. 3. Объект может совершать безошибочные перемещения между произвольными позициями, соответствующими начальной и конечной точкам перемещения в многоугольнике карты. При этих перемещениях с учетом существующих преград путь объекта является ломаной линией, не выходящей за пределы многоугольника карты. 4. У объекта имеется компас и устройства для определения расстояний от точки стояния (от текущего местоположения) до «видимых» преград; 5. Из своего текущего местоположения объект может сделать ряд наблюдений (обследований окрестности). Наблюдения имеют результатом набор измерительных данных (см. следующий пункт), позволяющий определить (вычислить) видимую из данной позиции p область (так называемый многоугольник видимости) V = V(p). Объекту также известно его местонахождение в многоугольнике V. 6. Датчики (сенсоры) объекта могут обеспечить измерение расстояния до тех точек на границах, до которых можно провести прямую линию (отрезок луча) от объекта, не выходя за границы многоугольника карты, т.е. не пересекая других сторон многоугольника, и не касаясь других вершин или сторон многоугольника (см. рис.1.2, справа). В прикладных задачах такого рода данные могут быть получены, например, от лазерных дальномеров. Отметим, что в случае положения объекта в точке p2 любое малое смещение его по направлению вверх (на север) сделает все точки стороны de «видимыми» и расстояние от точки p2 до них - измеримым. 7. Объект перемещается со скоростью v и время регистрации и обработки его наблюдений Итак, объект снабжен компасом и сенсорным устройством (п.4), с помощью которого он осуществляет круговой обзор и определяет расстояние до преграды (п.5-6). Отметим, что наличие компаса принципиально, поскольку позволяет сопоставлять текущее местонахождение (многоугольник видимости) с областями карты. В случае отсутствия компаса объект не сможет правильно сориентировать карту (то есть «привязать» её по направлению), и задача локализации в этом случае, вообще говоря, не будет иметь единственного решения (например, в простейшем случае квадрата однозначная локализация возможна только при положении объекта в центре квадрата, во всех остальных точках имеются 4 решения, отличающиеся поворотами на угол /2, и 3/2).

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

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

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

Одним из реальных примеров окружающей среды такого типа являются офисные здания или отели, где несколько множеств комнат, коридорного пространства и других общих пространств могут иметь идентичную структуру (если отвлечься от оформления интерьера и наличия мебели). Следовательно, если бы объект оказался ("проснулся") в одной такой комнате, оценка его начального местоположения была бы неоднозначной, так как нельзя принять единственное решение, в какой из многих подобно выглядящих комнат (помещений) объект в действительности находится. Неоднозначность окружающей среды обязательно влечет за собой необходимость осуществить перемещение объекта с намерением найти в окружающем пространстве ориентиры, позволяющие устранить (или хотя бы для начала уменьшить) неоднозначность. Например, на рисунке 1.3, перемещение из любого начального положения A, B, C, D, E, F, G или H с выходом в горизонтальный «коридор» снимает неоднозначность.

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

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

Алгоритм начинается со стартовой точки, и считается, что она была получена переходом типа 3.1. Обмен ролей триангуляций может происходить, только если полученная на предыдущем переходе точка относится к случаю 2.2.2, 2.1.2, 3.1 или 3.2, причём в случае 2.2.2 обмен происходит всегда. В случаях 2.1.2, 3.1 и 3.2 верхней становится та триангуляция, чьё структурное ребро выбирается в качестве очередного переходного ребра. При этом из двух возможных рёбер переходным ребром следует выбрать ребро с максимальным углом поворота налево относительно направления обхода. Если оба ребра реализуют поворот направо, то выбрать ребро с минимальным углом правого поворота. Если направления рёбер совпадают, то следует выбрать ребро верхней триангуляции.

Пример карты: вверху – схема карты из повторяющихся фрагментов (включая фрагменты «гармошка» и «вилка»), внизу – детализация части схемы. Показаны также начальное положение объекта p и положения, соответствующие гипотезам локализации. Рисунок 2.15. Триангулированные фрагменты карты «гармошка» и «вилка» и их наложение.

Сложность алгоритма в худшем случае есть O(n2). Для пояснения рассмотрим пример многоугольника, изображённого на рис. 2.14. При вычислении фрагмента пересечения InterS(P1,P2 ) c учётом гипотетического положения объекта p при работе алгоритма будет происходить следующее. Поскольку фрагменты «гармошка» и «вилка» будут накладываться друг на друга (см. рис. 2.15), то в процессе прохода по сторонам (структурным рёбрам) фрагмента «вилка» будут многократно пересекаться рёбра триангуляции фрагмента «гармошка». Если число и тех, и других рёбер будет O(n), то число таких пересечений и соответствующих действий будет O(n2).

Отметим, что ситуации, подобные приведённому примеру, в большинстве конфигураций карт, характерных для ЗЛМО, либо не возникают, либо соответствующие гипотезы быстро отсекаются. Поэтому алгоритм построения пересечения на основе триангуляции должен быть эффективен: в построении будут использоваться только те треугольники триангуляций, которые содержат точки фрагмента пересечения, и в среднем это даст сложность О(n). Выводы по второй главе 1. Проведено выделение основных подзадач, присутствующих в задаче ЛМО. 2. На основе анализа известных и новых алгоритмов локализации получен обобщенный алгоритм решения задачи локализации мобильного объекта. 3. Предложен и обоснован новый алгоритм локализации мобильного объекта с использованием триангуляции карты, существенно (в n log n раз) сокращающий время решения задачи по сравнению с известными алгоритмами. 4. Предложен и обоснован новый алгоритм локализации мобильного объекта с использование окон в многоугольнике карты, также существенно (в n log n раз) сокращающий время решения задачи по сравнению с известными алгоритмами. 5. Разработан алгоритм построения скелета многоугольника видимости на основе триангуляции, используемый в алгоритмах п.п.3,4. 6. Разработан алгоритм построения фрагмента пересечения двух многоугольников на основе их триангуляций, учитывающий особенности пересечения многоугольников в задаче локализации объекта.

Разработка структуры программы решения и исследования задачи локализации мобильного объекта, снабженного картой. Структура программы решения и исследования задачи локализации мобильного объекта, снабженного картой, влючает следующие блоки: - генерация карты; - генерация гипотез локализации; - решение для алгоритма локализации объекта с использованием декомпозиции карты на ячейки видимости; - решение для алгоритма локализации объекта, использующего рандомизацию при проверке гипотез; - решение для алгоритма локализации объекта с использованием триангуляции карты; - решение для алгоритма локализации объекта с использованием окон в многоугольнике карты; - решение для паралелльного алгоритма локализации объекта с использованием триангуляции карты. «Входом» для блока “генерации карты” являются кодинаты вершин карты и область видимости начального объекта, а «выходом» являются длина пути перещения объекта, чтобы устранить неправильные гипотезы и время работы соответствующего выбранного алгоритма локализации объекта.

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

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

Алгоритм и программа генерации карты плоской внешней среды, представленной простым многоугольником, предназначены для исследования алгоритмов ЛМР. При проведении эксперимента использовалась генерация карт различных модельных типов и размеров.

Сравнение алгоритмов 2, оптимизированного алгоритма 3 и 4

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

Для анализа эффективности предложенных алгоритмов проводилось экспериментальное исследование, основанное на их программной реализации (Visual C++ 2010), а также реализациях алгоритмов [41] [88] [72] и сравнении таких их характеристик, как величина суммарного пути перемещения объекта и время работы алгоритма локализации. Ранее было установлено [2], что алгоритм 2 [88], использующий рандомизацию при проверке гипотез, более эффективен, чем алгоритм 1 [41], использующий декомпозицию карты на ячейки видимости и имеющий асимптотическую сложность 0(п log п), а также более эффективен, чем алгоритм [72], основанный на решении полугрупповой задачи Штейнера и имеющий вычислительную сложность (n12). Поэтому далее приводится сравнение именно с алгоритмом 2 [88]. На алгоритмы, участвовавшие в эксперименте, будем ссылаться, обозначив их для краткости цифрами: 2 -алгоритм локализации мобильного объекта (АЛМО) с использованием рандомизации при проверке гипотез [88](число точек, случайным образом размещаемых в исследуемой области, X = 100); 2 – тот же АЛМО [88] с использованием рандомизации при проверке гипотез, но число точек, случайным образом размещаемых в исследуемой области, X = 500; 3 – АЛМО с использованием триангуляции карты; 4 – АЛМО с использованием окон в многоугольнике карты.

При проведении эксперимента использовалась генерация карт различных модельных типов. Генерация осуществлялась по нескольким задаваемым шаблонам: первый из них задает общую укрупненную схему карты в виде регулярного дерева, вершины которого соответствуют фрагментам карты «комната» или «коридор», для которых в свою очередь задаются свои шаблоны. Сочетание параметров, задающих размеры шаблонов, определяет общий размер карты n, и при такой генерации его числовое значение можно регулировать, как правило, лишь приближенно. На рис. 4.18 приведен пример генерации карты размера n = 746 и с числом гипотез k = 7 при любом из обозначенных на рисунке начальных положений pi (i=1..7).

Предварительный анализ показал, что полученные характеристики алгоритмов (длина пути d, пройденного объектом до окончания локализации, и время t работы алгоритма локализации) существенно зависят от начального расположения объекта (от номера гипотезы). По этой причине целесообразно усреднять по гипотезам не сами характеристики, полученные для разных алгоритмов, а их отношения, которые и будут характеризовать сравнительную эффективность алгоритмов. Выберем характеристики алгоритма с триангуляцией (номер алгоритма 3) в качестве «эталона» для сравнения. Т.е. для алгоритмов (с номером a) будут вычислены (здесь i – номер гипотезы)

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

На рис. 4.19 и 4.20 приведены графики зависимостей средних значений указанных отношений от размера многоугольника карты n. Различные типы линий графиков на рис. 4.19 - 4.20 относятся к алгоритмам с соответствующими номерами.

Данные на этих рисунках показывают (более наглядно на рис. 4.21), что в приведенном диапазоне значений размера карты n алгоритм 3 показывает значительно меньшее время работы, а вторым по времени работы оказывается алгоритм 4.

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

При проведении эксперимента использовалась генерация карт различных модельных типов. Генерация осуществлялась по нескольким задаваемым шаблонам. Сочетание параметров, задающих размеры шаблонов, определяет общий размер карты n, и при такой генерации его числовое значение можно регулировать, как правило, лишь приближенно. На рис. 4.22 приведен пример генерации карты размера n = 672 и с числом гипотез k = 144 при любом из обозначенных на рисунке начальных положений pi (i=1..144). Отметим, что такая структура карты обеспечивает относительно большое отношение k / n, а именно, k / n = 0.21.

Предварительный анализ показал, что полученные характеристики алгоритмов (длина пути d, пройденного объектом до окончания локализации, и время t работы алгоритма локализации) существенно зависят от начального расположения объекта (от номера гипотезы). По этой причине целесообразно усреднять по гипотезам не сами характеристики, полученные для разных алгоритмов, а их отношения, которые и будут характеризовать сравнительную эффективность алгоритмов. Выберем характеристики алгоритма с триангуляцией (номер алгоритма 3) в качестве «эталона» для сравнения. Т.е. для алгоритмов (с номером a) будут вычислены (здесь i – номер гипотезы)