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

• Дао Зуй Нам
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Дао Зуй Нам

СПИСОК УСЛОВНЫХ СОКРАЩЕНИЙ

ВВЕДЕНИЕ

ГЛАВА

ОБЗОР ЗАДАЧИ ЛОКАЛИЗАЦИИ МОБИЛЬНОГО ОБЪЕКТА

1.1. Постановка задачи локализации

1.2. Обзор алгоритмов и обоснование места работы

1.2.1. Базовые понятия задачи локализации

1.2.2. Задача о картинной галерее

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

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

1.2.5. Алгоритм локализации объекта на основе решения полугрупповой задачи Штейнера

Выводы по первой главе

ГЛАВА

АЛГОРИТМЫ ЛОКАЛИЗАЦИИ МОБИЛЬНОГО ОБЪЕКТА

2.1. Анализ алгоритмов локализации объекта

2.1.1. Выделение основных подзадач

2.1.1.1. Генерация гипотезы

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

2.1.1.3. Кратчайший путь между двумя точками в многоугольнике

2.1.1.4. Пересечение двух многоугольников

2.1.2. Обобщенный алгоритм решения задачи

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

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

2.4. Идеи и необходимые элементы алгоритмов ЛМО

2.5. Базовые задачи предлагаемых алгоритмов

2.5.1. Вычисление скелета многоугольника видимости

2.5.2. Пересечение многоугольников

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

ГЛАВА

ПРОГРАММА РЕШЕНИЯ И ИССЛЕДОВАНИЯ ЗАДАЧИ ЛОКАЛИЗАЦИИ МОБИЛЬНОГО ОБЪЕКТА, СНАБЖЕННОГО КАРТОЙ

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

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

3.3. Реализация алгоритма генерации гипотез локализации

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

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

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

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

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

ГЛАВА

ИСПЫТАНИЕ АЛГОРИТМОВ ЛОКАЛИЗАЦИИ МОБИЛЬНОГО ОБЪЕКТА НА МОЖЕСТВЕ СГЕНЕРОВАННЫХ КАРТ

4.1. Сравнение алгоритмов 1, 2, 3 и

4.2. Сравнение алгоритмов 2, 3 и

4.3. Сравнение алгоритмов 2, оптимизированного алгоритма 3 и 4 .... 102 Выводы по четвертой главе

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

СПИСОК УСЛОВНЫХ СОКРАЩЕНИЙ

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

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

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

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

ЛМО Локализации мобильного объекта

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

ВВЕДЕНИЕ

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

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

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

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

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

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

В работе исследуется именно детерминированная геометрическая

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

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

1. Анализ известных методов и алгоритмов локализации мобильного объекта.

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

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

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

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

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

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

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

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

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

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

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

т-ч и и

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

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

оптимизационной задачи локализации мобильного объекта, снабженного картой.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и вредрение результатов. Теоретические и практические результаты работы использованы в учебном процессе кафедры МОЭВМ СПБГЭТУ «ЛЭТИ».

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

Публикации. По теме работы опубликованы 10 научных работ, среди которых 5 публикации в ведущих рецензируемых изданиях,

рекомендованных ВАК, 1 статья в другом издании, 3 доклада на международных, всероссийских и межвузовских научно-технических конференциях, 1 свидетельство программы для ЭВМ.

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

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

Далее рассматриваются три известных приближённых (полиномиальных) алгоритма локализации мобильного объекта:

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

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

3. Алгоритм локализации объекта на основе решения полугрупповой задачи Штейнера (далее в работе не исследуется).

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

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

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

Проводится таблица сложности четырех приближённых (известных и новых) алгоритмов локализации мобильного объекта.

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

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

Рассмотрены алгоритмы генерации гипотез локализации с помощью среды Visual C++ 2010, которая выбрана для разработки генерации гипотез.

Рассмотрены реализации четырёх приведенных выше алгоритмов локализации объекта:

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

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

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

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

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

исследования задачи локализации мобильного объекта на множестве сгенерированных карт.

ГЛАВА 1

ОБЗОР ЗАДАЧИ ЛОКАЛИЗАЦИИ МОБИЛЬНОГО ОБЪЕКТА

1.1. Постановка задачи локализации

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

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

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

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

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

< \

Р1

Р2

Р V уро=ур2)=ур)

Рисунок 1.1. Многоугольник карты Р и начальное положение р (слева), многоугольник видимости V (в центре) и два возможные начальные местоположения р1 и р2 , соответствующие многоугольнику видимости (справа)

■

• й е

с I

91

Р2

92 . й е Р1

Ь

с I

Рис. 1.2. Слева - некоторые допустимые положения объекта в многоугольнике aЬcdefgh. Справа - видимость из точки р1 в направлении (р1;й). Точки отрезка (й,91] невидимы, поскольку их заслоняет вершина й. Точки отрезка (е,д2] не видимы из точки р2 (в том числе сторона йе, не считая самой вершины е), поскольку их заслоняет вершина е.

Ь

а

е

с

р

а

h

h

а

Ь

g

g

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

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

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

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

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

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

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

прикладных задачах такого рода данные могут быть получены, например, от лазерных дальномеров. Отметим, что в случае положения объекта в точке р2 любое малое смещение его по направлению вверх (на север) сделает все точки стороны ¿в «видимыми» и расстояние от точки р2 до них - измеримым.

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

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

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

своем местоположения и таким образом определить свое истинное начальное местоположение.

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

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

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

обязательно влечет за собой необходимость осуществить перемещение объекта с намерением найти в окружающем пространстве ориентиры, позволяющие устранить (или хотя бы для начала уменьшить) неоднозначность. Например, на рисунке 1.3, перемещение из любого начального положения А, В, С, Б, Е, Е, в или Н с выходом в горизонтальный «коридор» снимает неоднозначность.

Рисунок 1.3. Самоподобная окружающая среда. Данные видимости в местоположениях А, В, С, Б, Е, Е, в, Н являются одинаковыми.

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

необходимых перемещениях. Оказывается, что такая оптимизационная задача локализации является ^Р-трудной [41].

Чтобы пояснить возникающие проблемы, рассмотрим пример карты, изображенной на рис.1.4. На этом примере можно продемонстрировать, что простые эвристические стратегии локализации, используемые на практике, могут иногда показывать неудовлетворительные результаты работы (похожий пример есть в [41]). Пусть на карте имеется множество «горизонтальных» коридоров (на рис.1.4 для определенности и простоты изображения их показано 3). Коридоры имеют одинаковую структуру, отличаясь лишь местом расположения Т-образной комнаты, которая и

позволяет объекту идентифицировать коридор.

Рисунок 1.4. Коридоры имеют одинаковую структуру, отличаясь лишь местом расположения Т-образной комнаты, которая и позволяет объекту идентифицировать

коридор

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

Рисунок 1.5. Отдельно изображен коридор такого типа, простирающийся достаточно

далеко вправо и влево Предположим (см. рис.1.5), что слева от объекта на расстоянии ё+А находится вход в искомую комнату, а справа на расстоянии ё - вход в комнату другого типа. Кроме того, вправо от начального положения объекта простирается длинная последовательность комнат, достижение ни одной из которых не даёт возможности единственным образом идентифицировать местоположение объекта на карте. Если объект использует жадную стратегию и выбирает направление перемещения к ближайшему входу в комнату, то он будет перемещаться вправо от начального местоположения до ближайшей комнаты, а не влево на большее расстояние. Далее такой выбор и перемещение вправо будут повторяться, пока не встретится длинный участок коридора, такой, что расстояние до ближайшей комнаты вправо будет большим, чем расстояние влево от текущего положения объекта до комнаты, которая была ближайшей слева от начального местоположения объекта.

Действительно, пусть в общем случае комнаты, находящиеся на карте справа от начального положения объекта, начиная с ближайшей,

располагаются на расстояниях ¿1, ¿2, ¿3, ..., ¿к и т.д. друг за другом в порядке удаления от начального положения объекта. В соответствие с жадной стратегией объект будет выбирать движение вправо, если последовательность (¿0/ такова, что

¿к < ¿0 + (¿1 + ¿2 + ¿3 +...+ ¿к-1), где ¿0 = ё + А, = ¿. Если обозначить проходимый объектом за к шагов путь как

Дк = ¿1 + ¿2 +...+ ¿к, то можно записать рекуррентные соотношения

Ок = Дц + ¿к, ¿к < ¿о + Дк-1 при До = 0 (т.е. ^ = ¿1 = ¿). В случае, когда = ^ при /=1..к, получим Дк = кй, т.е. объект, двигаясь вправо, за к шагов превышает оптимальную длину пути примерно в к раз (Ы вместо ¿0 = й + А). Если же расположение комнат таково, что ¿к = 2^^, т.е. ¿1 = ¿2 = 2й, ¿3 = 4й, ... и, следовательно, ¿к = 2^^, то Дк = (2k-1)й, т.е. при движении объекта вправо превышение оптимальной длины пути объекта увеличивается экспоненциально ((2к-1^ вместо й + А).

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

В одномерном случае это задача может рассматриваться как разновидность следующей известной задачи. Объект стоит перед

о о 1 о

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

Инициализация: Установить шаг Н=1. Выбрать произвольно направление перемещения (вправо или влево относительно положения «лицом» к стене).

Список литературы диссертационного исследования кандидат наук Дао Зуй Нам, 2016 год

СПИСОК ЛИТЕРАТУРЫ

1. Дао Зуй Нам. Сравнительный анализ алгоритмов локализации мобильного робота, использующего карту// Сб. тр 66-й науч.-техн. конф. проф.-преп. состава СПБЭТУ «ЛЭТИ». СПб., 2013. С. 112115.

2. Дао Зуй Нам, Ивановский С.А. Экспериментальный анализ алгоритмов локализации мобильного робота // Известия СПБЭТУ «ЛЭТИ». - 2014. № 1. С. 19-24.

3. Дао Зуй Нам, Ивановский С. А. Приближенный алгоритм локализации мобильного робота с использованием окон в многоугольнике карты // Известия СПБЭТУ «ЛЭТИ». 2014. № 3, С. 38-43.

4. Дао Зуй Нам, Ивановский С.А. Оптимизация алгоритма локализации мобильного робота с использованием триангуляции карты // Известия СПБЭТУ «ЛЭТИ». 2015. № 2, С. 26-32.

5. Дао Зуй Нам, Ивановский С.А. Приближённые алгоритмы локализации мобильного робота// Научный вестик НГТУ. 2014. № 2, С. 109-121.

6. Дао Зуй Нам, Фирсов М. А. Использование триангуляции многоугольников в задаче локализации мобильного робота // Компьютерные инструмненты в образование. 2014. № 5, С. 25-41.

7. Дао Зуй Нам, Ивановский С.А. Алгоритмы управления мобильным роботом в задаче локализации при заданной карте внешней среды // Всероссийская научная конференция по проблемам управления в технических системах "ПУТС" 2015. С. 85-89.

8. Фирсов М. А. Сравнение параллельных реализаций алгоритма пересечения полигонов на многоядерном и на графическом процессорах // 67-я науч.-техн. конф. профессорско-

преподавательского состава СПБЭТУ «ЛЭТИ» 2014: тез. докл. СПб., 27 янв. - 3 февр. 2014. СПб.: Изд-во СПБГЭТУ «ЛЭТИ», 2014. С. 103-107.

9. Фирсов М. А., Ивановский С. А. Параллельная реализация алгоритма построения пересечения простых полигонов с использованием технологии CUDA // Известия СПБЭТУ «ЛЭТИ». 2013. № 9, С. 2934.

10. Сандерс Дж., Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессоров. - М.: ДМК Пресс, 2011. - 232 с.

11. Скворцов А.В. Триангуляция Делоне и её применение. - Томск: Изд-во Том. ун-та, 2002. - 128 с.

12. Скворцов А.В. Построение объединения, пересечения и разности произвольных многоугольников в среднем за линейное время с помощью триангуляции // Вычислительные методы и программирование, 2002, Т. 3. С. 116-123.

13. Arras K. O., Castellanos J. A., Siegwart E. Feature-based multihypothesis localization and tracking for mobile robots using geometric constraints, In Proc. IEEE International Conference on Robotics and Automation (Washington DC, USA), 2002, pp. 1371-1377.

14. Avis D., Imai H. Locating a robot with angle measurements, J. Symbolic Computation 10 (1990), 311-326.

15. Avis D., Toussaint G. An optimal algorithm for determining the visibility of a polygon from an edge, IEEE Transactions on Computers C-30, No. 12 (1981), 910-914.

16. Balaban I. J. An optimal algorithm for finding segment intersections, in Proceedings of the 11th ACM Symposium on Computational Geometry, ACM, New York, 1995, pp. 211-219.

17. Bartal Y. Probabilistic approximations of metric spaces and its algorithmic applications, in Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 1996, pp. 184-193.

18. Bateman C. D., Helvig C. S., Robins G., Zelikovsky A. Provably good routing tree construction with multi-port terminals, in Proceedings of the ACM/SIGDA International Symposium on Physical Design, ACM, New York, 1997, pp. 96-102.

19. Brown R.G. , Donald B.E. Mobile robot self-localization without explicit landmarks, Algorithmica 26 (2000), no. 3/4, 515-559.

20. Berlekamp E.R. Factoring polynomials over large finite fields, Math. Comput. 24 (1970), 713-735.

21. Burgard W., Fox D., Hennig D., Schmidt T. Estimating the absolute position of a mobile robot using position probability grids, AAAI/IAAI, vol. 2, 1996, pp. 896-901.

22. Betke M., Gurvits L. Mobile robot localization using landmarks, IEEE Trans, on Eobotics and Automation 13 (1997), no. 2, 251-263.

23. Bose J., Guibas L., Lubiw A., Overmars M., Souvaine D., Urrutia J. The floodlight illumination problem, Int. Journal in Computational Geometry 7 (1997), 153-163.

24. Buck M., Schfer D., Noltemeier H. Practical strategies for hypotheses elimination on the self-localization problem, 1999.

25. Bungiu F., Hemmer M., Hershberger J., Huang K., Kroller A. Efficient computation of visibility polygons// EuroCG. 2014. - 4 p.

26. Chan T. M. On levels in arrangements of curves, Discrete Comput. Geom., 29 (2003), pp. 375-393.

27. Charikar M., Chekuri C., Cheung T. Y., Dai Z., Goel A., Guha S., Li M., Approximation algorithms for directed Steiner problems, J. Algorithms, 33 (1999), pp. 73-91.

28. Chazelle B. Triangulating a simple polygon in linear time // Discrete & Computational Geometry, 6(1):485-524, Springer-Verlag, 1991.

29. Chazelle B., Edelsbrunner H. An optimal algorithm for intersecting line segments in the plane, J. Assoc. Comput. 39 (1992), 1-54.

30. Chekuri C., Pal M. A recursive greedy algorithm for walks in directed graphs, in Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2005, pp. 245-253.

31. Chvatal V. A combinatorial theorem in plane geometry, J. Combinatorial Theory Series B 18 (1975), 39-41.

32. Cassandra A. E., Kaelbling L. P., Kurien J. A. Acting under uncertainty: Discrete bayesian models for mobile robot navigation, In Proc. IEEE/ESJ International Conference on Intelligent Eobots and Systems, 1996.

33. Chin W., Ntafos S. Optimum watchman routes, Information Processing Letters 28 (1988), 39-44.

34. Dao Duy Nam, S.A. Ivanovskiy. Two new approaches to minimum distance localization // Journal of science and technology University of Danang, No. 12,(73), 2013, P. 52-57.

35. De Berg M., Cheong O., Van Kreveld M., Overmars M. Computational Geometry: Algorithms and Applications, Berlin, Heidelberg: SpringerVerlag, 3rd rev. ed. 2008.-386 p.

36. Dellaert F., Fox D., Burgard W., Thrun S. Monte carlo localization for mobile robots, In Proc. IEEE Conference on Eobotics and Automation, 1999.

37. Dudek G., Jenkin M. Computational principles of mobile robotics, Cambridge University Press, 2000.

38. Demaine E. D., Lopez-Ortiz A., Munro J. I. Robot localization without depth perception, In Proc. 8th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science (Turku, Finland), vol. 2386,

2002, pp. 249-259.

39. Duckett T., Nehmzow U. Experiments in evidence-based localisation for a mobile robot, In Proc. AISB-97 Workshop on Spatial Eeasoning in Mobile Eobots and Animals, 1997.

40. Dudek G., Jenkin M. Computational Principles of Mobile Robotics, Cambrigde University Press, 2rd rev. ed. 2010. - 406 p.

41. Dudek G., Romanik K., Whitesides S. Localizing a robot with minimum travel// SIAM J. Comput.1998. Vol. 27, P. 583-604.

42.Engelson S. Passive map learning and visual place recognition, Ph.D. thesis, Computer Science Department, Yale University, 1994.

43.Even G., Kortsarz G., Slany W. On network design: Fixed charge flows and the covering Steiner problem, in Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, 2002, pp. 318-329.

44.Fakcharoenphol J., Rao S., Talwar K. A tight bound on approximating arbitrary metrics by tree metrics, in Proceedings of the 35th ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 448455.

45.Fox D., Burgard W., Dellaert F., Thrun S. Monte carlo localization: Efficient position estimation for mobile robots, AAAI/IAAI, 1999, pp. 343-349.

46.Fox D., Burgard W., Thrun S. Active markov localization for mobile robots, Robotics and Autonomous Systems 25 (1998), 195-207.

47. Fox D., Burgard W., Thrun S. Markov localization for reliable robot navigation and people detection, Sensor Based Intelligent Robots, 1998, pp. 1-20.

48.Fox D., Thrun S., Burgard W., Dellaert F. Particle filters for mobile robot localization, Sequential Monte Carlo Methods in Practice (New York) (A. Doucet, N. de Freitas, and N. Gordon, eds.), Springer, 2001.

49. Garg N., Konjevod G., Ravi R. A polylogarithmic approximation

algorithm for the group Steiner tree problem, J. Algorithms, 37 (2000), pp. 66-84.

50. Ghosh S. K. Visibility algorithms in the plane. Cambridge University Press, 2007. - 334 p.

51.El Gindy H., Avis D. A linear algorithm for computing the visibility polygon from a point, Journal of Algorithms 2 (1981), 186-197.

52. Gonzalez-Banos H. H., Latombe J.C. Planning robot motions for rangeimage acquisition and automatic 3d model construction, In Proc. AAAI Fall Symposium Series, 1998.

53. Gonzalez-Banos H. H., Latombe J.C. A randomized art-gallery algorithm for sensor placement, In Proc. 17th ACM Symposium on Computational Geometry, 2001, pp. 232-240.

54. Gonzalez-Banos H. H., Latombe J.C. Robot navigation for automatic model construction using safe regions, Experimental Robotics VII. Lecture Notes in Control and Information Sciences (In Proc. of Int. Symposium on Experimental Robotics 2001) 271 (2001), 405-415.

55. Gonzalez-Banos H. H., Latombe J.C. Navigation strategies for exploring indoor environments, International Journal of Robotics Research 21(10-11) (2002), 829-848.

56. Gonzalez-Banos H. H., Mao E., Latombe J.C., Murali T.M., Efrat A. Planning robot motion strategies for efficient model construction, Robotics Research - The 9th International Symposium (J.M. Hollerbach and D.E. Koditschek, eds.), Springer, 2000, pp. 345-352.

57. Gutmann J., Fox D. An experimental comparison of localization methods continued, In Proc. IEEE/ESJ International Conference on Intelligent Robots and Systems (Lausanne, Switzerland), 2002.

58. Guibas L. J., Hershberger J., Leven D., Sharir M., Tarjan R. E. Lineartime algorithms for visibility and shortest path problems inside triangulated simple polygons, Algorithmica 2 (1987), 209-233.

59. Guibas L. J., Motwani R., Raghavan P. The robot localization problem// SIAM J. Comput.1997. Vol. 26, P. 1120-1138.

60. Hershberger J., Snoeyink J. Computing minimum length paths of a given homotopy class // Computational Geometry. Theory and Applications, 1994. 4:63-98.

61. Hsu D., Kavraki L., Latombe J. C., Motwani R., Sorkin S. On finding narrow passages with probabilistic roadmap planners, In Proc. Int. Workshop on Algorithmic Foundations of Robotics, 1998.

62. Hyafil L., Rivest R. L. Constructing optimal binary decision trees is np-complete, Information Processing Letters 5 (1976), 15-17.

63.Ivanovskii Sergei. , Dao Duy Nam. Visualization algorithms for distance and blended learning // Informational Conference Southeast Asian Open and Distance Learning in the 21st Century "ISODL" 2012, P. 95-105.

64.Jensfelt P., Kristensen S. Active global localisation for a mobile robot using multiple hypothesis tracking, IEEE Transactions on Robotics and Automation 17(5) (2001), 748-760.

65. Kalai G. A subexponential randomized simplex algorithm, In 24th ACM STOC, 1992, pp. 475-482.

66. Karp R. M. An introduction to randomized algorithms, Discrete Appl. Math. 34 (1991), 165-201.

67. Kavraki L., Latombe J. C. Probabilistic roadmaps for robot path planning, Practical Motion Planning in Robotics: Current Approaches and Future Challenges (1998), 33-53.

68. Kleinberg J. The localization problem for mobile robots, In Proc. 35th IEEE Conference on Foundations of Computer Science (Santa Fe, NM), IEEE Computer Society Press, 1994, pp. 521-533.

69. Karch O., Noltemeier H., Wahl T. Robot localization: Theory and implementation, In Abstracts 13th European Workshop Comput. Geom.,

1997, pp. 17-19.

70. Karch O. Noltemeier H., Wahl T. Using polygon distances for localization, 1998.

71. Karch O., Wahl T. Relocalization - theory and practice, Special Issue of Discrete Applied Mathematics on Computational Geometry 93 (1999).

72. Koenig S., Mitchell J. S. B., Mudgal A., Tovey C. A near-tight approximation algorithm for the robot localization problem// SIAM J. Comput. 2009. Vol. 39, P. 461-490.

73. Koenig S., Tovey C. Localization: Approximation and Performance Bounds to Minimize Travel Distance // IEEE Transactions On Robotics . 2009. Vol. 26, P. 320-330.

74.Leonard J. J., Durrant-Whyte H. F. Mobile robot localization by tracking geometric beacons, IEEE Trans, on Robotics and Automation 7(3) (1991), 376-382.

75.Lee D. T. Visibility of a simple polygon, Computer Vision, Graphics, and Image Processing 22 (1983), 207-221.

76.Lee D. T., Lin A. K. Computational complexity of art gallery problems, IEEE Transactions on Information Theory 32 (1986), 276282.

77. De Leeuw K., Moore E. F., Shannon C. E., Shapiro N. Computability by probabilistic machines, Automata Studies (1955), 183-212.

78. MacKenzie P., Dudek G. Precise positioning using model-based maps, In Proc. IEEE Int. Conf. on Robotics and Automation, 1994, pp. 1615-1621.

79. Motwani R., Raghavan P. Randomized algorithms, Cambridge University Press, New York, 1995.

80.Jiri Matousek, Micha Sharir, Emo Welzl. A subexponential bound for linear programming, In Symposium on Computational Geometry, 1992, pp. 1-8.

81. Milstein A., Snchez J. N., Williamson E. Robust global localization using clustered particle filtering, AAAI/IAAI, 2002.

82. Nayar S., Murase H., Nene S. Learning, positioning, and tracking visual appearance, In Proc. of IEEE Int'l. Conf. on Robotics and Automation, 1994.

83. Nourbakhsh I., Powers R., Birchfield S. Dervish: an office navigating robot, AI Magazine 16(2) (1995), 53-60.

84. O'Rourke J., Chien C., Olson T., Naddor D. A new linear algorithm for intersecting convex polygons, Comput. Graph. Image Process. 19 (1982), 384-391.

85.J. O'Rourke, Computational geometry in c, Cambridge University Press, 1998.

86. Qi M., Cao T.-T., Tan T.-S. Computing 2D Constrained Delaunay Triangulation Using Graphics Hardware / School of Computing; National University of Singapore // Technical Report # TRB3/11, March 2011. 9 p.

87.Rabin M. O. Probabilistic algorithms, Algorithms and Complexity, Recent Results and New Directions (1976), 21-39.

88.Rao M., Dudek G., Whitesides S. Randomized algorithms for minimum distance localization// Internat. J. Robotics Research. 2007. Vol. 26, P. 917-934.

89. Seidel R. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons // Computational Geometry. Theory and Applications, 1991. 1(1):51-54.

90. Sven Schuierer, Sensing, modelling and planning, Intelligent Robots, ch. Efficient robot self-Localization in simple polygons, pp. 129-146, World Scientific Publ., 1996.

91. Sim R., Dudek G. Position estimation using principal components of range data, In Proc. IEEE/RSJ Conf. on Intelligent Robots and Systems, 1998.

92. Shermer T. Hiding people in polygons, Computing 42 (1989), 109131.

93. Shermer T. Recent results in art galleries, In Proc. IEEE, Special Issue on

Computational Geometry, vol. 80(9), 1992, pp. 1384-1399.

94. Simmons R., Koenig S. Probabilistic robot navigation in partially observable environments, In Proc. International Joint Conference on Artificial Intelligence, 1995, pp. 1080-1087.

95. Scott W., Roth G., Rivest J. F. View planning as a set covering problem, Tech. report, National Research Council of Canada (NRCC), Institute for Information Technology, 2001.

96. Solovay R., Strassen V. A fast monte carlo test for primality, SIAM J. Computing 6 (1977), no. 1, 84-85.

97. Sack J., Toussaint G. Guard placement in rectilinear polygons, Computational Morphology (1988), 153-175.

98. Sugihara K. Some location problems for robot navigation using a single camera, Computer Vision, Graphics, and Image Processing 42 (1988), 112-129.

99. Thrun S., Fox D., Burgard W. Monte carlo localization with mixture proposal distribution, AAAI/IAAI, 2000, pp. 859-865.

100. Thrun S., Fox D., Burgard W., Dellaert F. Robust monte carlo localization for mobile robots, Artificial Intelligence 128 (2001), no. 12,99-141.

101.Tovey C., Koenig S. Improved analysis of greedy mapping, In Proceedings of the International Conference on Intelligent Robots and Systems, 2003.

102.Toussaint T., A linear-time algorithm for solving the strong hidden-line problem in a simple polygon, Pattern Recognition Letters 4 (1986), 449451.

103.Tarjan R. E., Van Wyk C. J. A linear-time algorithm for triangulating simple polygons, In Proc. 18th annual ACM Symposium on Theory of Computing (Berkeley, California, United States), 1986, pp. 380-388.