Методы решения задачи привязки трека к плану помещения

Характеристика этапов алгоритма частичного перебора и метода частиц. Графическое изображение работы алгоритмов по определению местоположения объекта в помещении. Сравнение двух алгоритмов корректировки трека объекта и привязки его к плану помещения.

Рубрика Коммуникации, связь, цифровые приборы и радиоэлектроника
Вид статья
Язык русский
Дата добавления 22.01.2017
Размер файла 381,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ПРИВЯЗКИ ТРЕКА К ПЛАНУ ПОМЕЩЕНИЯ

Сорокин Федор Валерьевич1, Воронов Роман Владимирович2

1Петрозаводский государственный университет, студент 3-го курса направления «Информационные системы и технологии»

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

Аннотация

В системах определения местоположения объектов внутри помещения, основанных на распространенных стандартах беспроводной передачи данных (Wi-Fi, Bluetooth и др.), могут возникать проблемы с перегрузкой сети, или же с неопределенностью местоположения и необходимостью его уточнения. Многие современные мобильные устройства оснащены модулем распознавания движения (IMU, Inertial Measurement Unit), основанного на использовании данных от акселерометра, гироскопа и магнитометра. По информации, полученной от этого модуля, можно построить трек объекта. Однако, модуль распознавания движения допускает погрешность при оценке длины шага и определении направления движения. Данная статья посвящена сравнению двух алгоритмов корректировки трека объекта и привязки его к плану помещения.

Ключевые слова: алгоритм привязки трека к плану помещения, траектория, трек

Введение

Многие современные системы локации мобильных объектов внутри помещений основаны на использовании беспроводной сети датчиков [6], [7], [9], [10], [11], [12], [13], [16], [17], [18], [19], [20], [21], [22]. Информация, полученная от этих датчиков, используется для уточнения местоположения объекта [1], [2], [3], [4], [5], [8]. Например, датчики движения, закрепленные на теле человека, позволяют восстанавливать трек (путь объекта) в помещении [14]. Знание начальной точки и последующего трека объекта может помочь в определении места его расположения после перемещения.

В математической модели трек состоит из N последовательных точек, заданных в некоторой системе координат. Длины единичного отрезка в системе координат трека и системе координат помещения совпадают. Задана начальная точка трека в системе координат помещения.

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

где гi -- удельное изменение длины звена, ?цi -- изменение угла между звеном i и i-1. c1 и c2 -- коэффициенты влияния на оценку изменений длин звеньев и углов между звеньями соответственно.

Далее будут рассмотрены и сравнены два алгоритма привязки трека к плану помещения: метод частичного перебора, представленный в статье [22] и алгоритм, основанный на методе частиц [21], [23].

Алгоритм частичного перебора

алгоритм трек объект привязка

На входе алгоритма начальная точка трека, последовательность векторов di и множество стен H (план помещения).

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

План помещения должен быть разбит на квадратные участки s, множество которых обозначим S. Размер клетки отвечает за точность расчетов.

Главная идея алгоритма -- для каждого i=1..N и каждого участка s запоминается не более одного варианта траектории из первых i звеньев исходной ломаной. Пусть Si -- подмножество участков, для которых существуют заканчивающиеся в них варианты траекторий из первых i звеньев ломаной. Вариант траектории из первых i звеньев исходной ломаной, заканчивающийся в участке s будем называть (i,s)-траекторией.

Если подобрана (i,s)-траектория, то она фиксируется и не изменяется. Это позволяет существенно сократить число перебираемых вариантов траекторий ломаной. Недостатком алгоритма является то, что возможна потеря «плохих» начальных фрагментов ломаных, оценка которых может оказаться ниже траектории, полученной в результате выполнения алгоритма.

Пусть d - вектор ломаной. Введем обозначение для отображения, вращающего вектор d на угол ц и растягивающего (сжимающего) его длину в г раз: Gгц(d).

Для каждого s?Si (i=1..N) будем определять:

1. Сi(s) -- оценку (i,s)-траектории;

2. qi(s) -- последнюю точку (i,s)-траектории;

3. шi(s) -- суммарное изменение углов траектории;

4. жi(s) -- участок, содержащий предпоследнюю точку (i,s)-траектории.

Алгоритм состоит из двух этапов: прямой и обратный обходы.

Первый этап алгоритма. Пусть x0 - первая точка ломаной, s0 - участок, содержащий точку x0. Тогда C0(s0) = 0, q0(s0) = x0, ш0(s0) = 0, ж0(s) -- не определено.

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

принадлежит участку s, и отрезок (x0, x1) не пересекается с отрезками множества H и при этом достигается минимум |1-г|. Положим

Из участков s, для которых найдены такие точки x1, сформируем множество S1.

Далее при всех i-ых звеньев (i = 2..N), для каждого участка s найдем перебором

,

для которых

Точка

принадлежит участку s, отрезок (xi-1, xi) не пересекается с отрезками множества H и при этом достигается минимум

Положим

Из участков s, для которых найдены такие точки xi, сформируем множество Si.

Второй этап алгоритма. Пусть sN

-- участок множества SN, для которого достигается минимум CN(s). Участки si, содержащие точки лучшей траектории ломаной находятся по формуле

Тогда

xi = qi(si)

для i = 0..N. Полученная таким образом последовательность x0, x1,…, xN определяет искомую оптимальную траекторию ломаной, привязанную к плану помещения.

Время работы алгоритма равно

Пример работы первого алгоритма:

Рисунок 1.1 Трек, полученный с помощью IMU

Рисунок 1.2 Траектория, результат работы жадного алгоритма

Рисунок 1.3 Реальное перемещение объекта

Метод частиц

На входе алгоритма начальная точка трека, последовательность векторов di и множество стен H (план помещения).

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

Для краткости будем называть вариант траектории из первых i звеньев ломаной (i)-траекторией.

Главная идея алгоритма - для каждого i=1..N запоминается не более n (i)-траекторий. Пусть S - множество (i)-траекторией, найденных на конкретной итерации и принятых к дальнейшему рассмотрению.

Так же, как и для предыдущего алгоритма, определяем GгЦ(d) - отображение, вращающее вектор d на угол ц и растягивающее (сжимающего) его длину в г раз.

Для каждой (i)-траекторий (i=1..N) будем определять:

1. Сi -- оценку (i)-траектории;

2. qi -- последнюю точку (i)-траектории;

3. шi -- суммарное изменение углов траектории;

4. жi -- (i-1)-траектория, содержащаяся в (i)-траектории.

Алгоритм состоит из двух этапов: прямой и обратный обходы.

Первый этап алгоритма. Пусть x0 - первая точка ломаной. Тогда C0 = 0, q0 = x0, ш0 = 0, ж0 -- не определено.

Построение первых звеньев траекторий ломаной. Перебираем все возможные значения ц из детерминированного множества [-р; р] и mслучайных значений

Для каждой пары считаем точку

Если отрезок (x0, x1) не пересекается с отрезками множества H, формируем (1)-траекторию с параметрами:

Формируем множество S1 из n (1)-траекторий с наименьшими параметрами С1.

Далее для каждой (i)-траектории из Ci (для каждого i = 2..N), выбираем m пар значений и . Считаем для каждой пары точку

xi = qi-1 + Gг,щ+ц(di),

где

щ= шi-1.

Если отрезок (xi-1, xi) не пересекается с отрезками множества H, формируем (i)-траекторию с параметрами

Ci(s) = Ci-1(si-1)+|1-г|+|ц|, qi(s) = xi, шi(s) = щ + ц, жi(s) = si-1.

Формируем множество Si из n (i)-траекторий с наименьшими параметрами С¬i.

Второй этап алгоритма. Пусть (N)-траектория -- вариант траектории из множества SN, для которого достигается минимум CN. (i)-траектории, содержащиеся в лучшей траектории ломаной находятся по формуле

si = жi+1.

Тогда

xi = qi

для i = 0..N. Полученная таким образом последовательность x0, x1,…,xN определяет искомую оптимальную траекторию ломаной, привязанную к плану помещения.

Время работы алгоритма равно .

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

Пример работы второго алгоритма:

Рисунок 2.1 Трек, полученный с помощью IMU

Рисунок 2.2 Траектория, результат работы метода частиц

Рисунок 2.3 Реальное перемещение объекта

Результаты тестирования

Оба алгоритма были реализованы на языке программирования Java 7. Тестировались на ноутбуке HP Envy dv6-7252er с процессором Intel® Core™ i7-3630QM.

Точность

Среднее отклонение результата первого алгоритма от реального перемещения равна одному метру при размерах клетки 0,7. При 0,6 может достигаться отклонение 0,9, но время работы увеличивается в два раза.

У второго алгоритма точность не зависит от параметров. На рисунке 3.1 представлен график зависимости среднего значения среднего отклонения от параметра n, при фиксированном значении m. Для каждой пары параметров алгоритм был выполнен 100 раз.

Рисунок 3.1 Зависимость среднего отклонения от n при m=3

На следующем графике (Рисунок 3.2) можно заметить, что, хоть среднее отклонение при паре параметров m=3, n=40 может достичь двух с лишним метров, в среднем результаты будут отклоняться на один-полтора метра.

Рисунок 3.2 Распределение среднего отклонения при m=3, n=40

При паре параметров m=3, n=130 (Рисунок 3.3) максимальное отклонение значительно меньше, но распределение не самое лучшее. Таким образом, по данному критерию выигрывает всё равно пара параметров 3 40.

Рисунок 3.3 Распределение среднего отклонения при m=3, n=130

Время выполнения

Время выполнения первого алгоритма колеблется вокруг одного и того же значения - 450 мс. При оптимальных параметрах.

У второго же время выполнения зависит от случайных чисел, генерируемых внутри.

Представлен график (Рисунок 3.4) зависимости времени работы от параметра n при фиксированном значении m=3. Время работы при параметре m=4 и далее рассмотрено не будет, т.к. точность от параметров не зависит, и время работы при том становится больше.

Рисунок 3.4 Среднее время работы при m=3

При паре параметров m=3, n=40 алгоритм чаще всего будет работать за 35 секунд. Данный факт пригодится в дальнейшем. Большое время работы встречается очень редко, в 10% случаев.

Сравнение алгоритмов

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

Результаты тестов показали, что второй алгоритм работает примерно в 20 раз быстрее первого. Это первый плюс второго алгоритма.

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

Для второго алгоритма оптимальные значения мы получили экспериментально. Эти параметры будут оптимальными для любого плана помещения.

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

Библиографический список

1. Воронов Р.В. Развитие технологий локации объектов в беспроводных системах // В сборнике: Классический университет в пространстве трансграничности на севере Европы: стратегия инновационного развития // Материалы международного форума. Петрозаводский государственный университет. Петрозаводск, 2014. С. 16-17.

2. Воронов Р.В., Мощевикин А.П. Применение условной энтропии при формировании рекомендаций по размещению базовых станций в локальных системах позиционирования // Информационные технологии. 2014. № 10. С. 11-16.

3. Liu H. et al. Survey of wireless indoor positioning techniques and systems // Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on. - 2007. - Т. 37. - №. 6. - С. 1067-1080.

4. Deak G., Curran K., Condell J. A survey of active and passive indoor localisation systems // Computer Communications. - 2012. - Т. 35. - №. 16. - С. 1939-1954.

5. Овчинников С. Системы позиционирования и мониторинга // Технологии и средства связи. - 2014. № 2. С. 18-22.

6. Мехтиев А. Д. и др. Применение сенсорных сетей для мониторинга и локального определения местоположения в промышленности // Хабаршысы вестник. - 2013. - С. 68-62.

7. Pei Z. et al. Anchor-free localization method for mobile targets in coal mine wireless sensor networks // Sensors. - 2009. - Т. 9. - №. 4. - С. 2836-2850.

8. Galov, A., Moschevikin, A. Bayesian filters for ToF and RSS measurements for indoor positioning of a mobile object // Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN-2013), Montbeliard, France, October 28-31, 2013, pp. 310-317.

9. Мощевикин А. П., Галов А. С., Волков А. С. Локация в беспроводных сетях датчиков стандарта nanoLOC (IEEE 802.15.4a) // Информационные технологии. - 2011. № 8, С.43-47.

10. Мощевикин А. П., Галов А. С., Волков А. С. Точность расчета локации в беспроводных сетях датчиков стандарта nanoLOC // Информационные технологии. - 2012. - № 9. - С. 37-41.

11. Savic V., Wymeersch H., Larsson E. G. Simultaneous sensor localization and target tracking in mine tunnels // Information Fusion (FUSION), 2013 16th International Conference on. - IEEE, 2013. - С. 1427-1433.

12. Widmann D. et al. Characterization of in-tunnel distance measurements for vehicle localization // Wireless Communications and Networking Conference (WCNC), 2013 IEEE. - IEEE, 2013. - С. 2311-2316.

13. Deak G., Curran K., Condell J. A survey of active and passive indoor localisation systems // Computer Communications. - 2012. - Т. 35. - №. 16. - С. 1939-1954.

14. Овчинников С. Системы позиционирования и мониторинга // Технологии и средства связи. - 2014. № 2. С. 18-22.

15. Moschevikin A., Voronov R., Galov A., Soloviev A. Using pressure sensors for floor identification in wireless sensors networks // В сборнике: 2012 IEEE 1st International Symposium on Wireless Systems - Within the Conferences on Intelligent Data Acquisition and Advanced Computing Systems, IDAACS-SWS 2012 2012. С. 2-6.

16. Воронов Р.В., Малодушев С.В. Динамическое создание карт уровня wifi-сигналов для систем локального позиционирования // Системы и средства информатики. 2014. Т. 24. № 1. С. 80-92.

17. Воронов Р.В., Волков А.С., Региня С.А., Федоров А.А., Мощевикин А.П. Метод обработки данных распределенной сети датчиков давления для оценки относительной высоты мобильного узла // Современные проблемы науки и образования. 2013. № 4. С. 13.

18. Galov A., Moschevikin A., Voronov R. Combination of rss localization and tof ranging for increasing positioning accuracy indoors // В сборнике: 2011 11th International Conference on ITS Telecommunications, ITST 2011 2011. С. 299-304.

19. Воронов Р.В., Галов А.С., Мощевикин А.П., Воронова А.М., Стёпкина Т.В. Метод определения местоположения мобильных объектов в шахте // Современные проблемы науки и образования. 2014. № 4. С. 155.

20. Воронов Р.В., Лукашенко О.В., Мощевикин А.П. Автоматическая калибровка локальных систем позиционирования на основе построения карты сил сигналов // Труды Карельского научного центра Российской академии наук. 2014. № 4. С. 29-35.

21. Mikov A. G., Moschevikin A. P., Fedorov A. A., Sikora A. A Localization System Using Inertial Measurement Units from Wireless Commercial Hand-held Devices // Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN-2013), Montbeliard, France, October 28-31, 2013. - Montbeliard, 2013. - Р. 857-863.

22. Воронов Р.В., Галов А.С., Мощевикин А.П., Воронова А.М. Задача привязки траектории объекта к плану помещения // Ученые записки Петрозаводского государственного университета. Серия: Естественные и технические науки. 2015. № 1. С. 87-91.

23. Moschevikin A., Galov A., Soloviev A., Mikov A., Volkov A., Reginya S. RealTrac technology overview // EvAAL 2013, Communications in Computer and Information Science series CCIS. - 2013. - Т. 386 - С. 60-71.

Размещено на Allbest.ru

...

Подобные документы

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

    дипломная работа [3,5 M], добавлен 25.10.2011

  • Изучение алгоритмов, используемых при проектировании узлов радиоэлектронных средств на печатных платах. Построение минимального покрывающего дерева с помощью алгоритма Прима; расслоение топологии. Реализация алгоритмов решения задачи трассировки.

    курсовая работа [370,1 K], добавлен 09.05.2015

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

    курсовая работа [1,1 M], добавлен 19.06.2010

  • Технический паспорт объекта "Брянский Открытый Институт Управления и Бизнеса". Обоснование целесообразности разработки проекта. Выбор средств защиты объекта. Безинструментальная оценка звукоизоляции помещения. Инженерно-техническая защита информации.

    курсовая работа [721,3 K], добавлен 21.08.2014

  • Особенности аттестации объекта информатизации по требованиям безопасности информации. Разработка проекта организации защиты информации в выделенном помещении и подготовка её к аттестационным мероприятиям. Расчет звукоизоляции ограждающих конструкций.

    дипломная работа [2,7 M], добавлен 27.01.2014

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

    курсовая работа [1,9 M], добавлен 19.06.2013

  • Описание объекта и функциональная спецификация. Описание ресурсов МК: расположение выводов; исполнение микроконтроллера; особенности микроконтроллеров. Разработка алгоритмов устройства. Описание функциональных узлов МПС и алгоритма их взаимодействия.

    курсовая работа [5,2 M], добавлен 27.12.2009

  • Сущность и значение радиосвязи, ее применение. Проблемы организaции трaнкинговых систем. Конвенционaльные рaдиосистемы: непaрaметрическое кодирование речи. Специфика общего алгоритма скремблирования. Пример простых алгоритмов скремблирования данных.

    курсовая работа [509,5 K], добавлен 25.06.2011

  • Проектирование табличным методом алгоритмов работы на сотовом мобильном телефоне GA 628 Ericsson. Использование символьных наборов. Описание работы автомата таблицей переходов. Разработка алгоритмов функций. Использование телефона как блокнота.

    контрольная работа [92,3 K], добавлен 09.05.2011

  • Эффективность алгоритмов и оценка их вычислительной сложности. Модель вычислительного процесса и классификация алгоритмов по вычислительной сложности. Принцип "разделяй и властвуй". Общие свойства базовых алгоритмов цифровой обработки сигналов.

    контрольная работа [29,1 K], добавлен 11.09.2015

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

    дипломная работа [177,9 K], добавлен 24.06.2010

  • Автоматизация управления газоперекачивающим агрегатом компрессорной станции Сургутского месторождения. Характеристика технологического процесса. Выбор конфигурации контроллера и программного обеспечения. Разработка алгоритмов работы объекта автоматизации.

    дипломная работа [3,9 M], добавлен 29.09.2013

  • Описание схемы контроля и автоматизации регулировки температуры распределенного теплового объекта. Анализ динамических свойств объекта управления, расчет переходного процесса с учетом датчика. Изучение алгоритма управления на базе контроллера ТРМ-32.

    курсовая работа [1,5 M], добавлен 14.01.2015

  • Разработка системы управления приточно-вытяжной вентиляцией офисного помещения на программируемом контроллере LOGO фирмы "Siemens". Проектирование функциональной и принципиальной электрической схемы объекта. Программирование и размещение контроллера.

    дипломная работа [4,3 M], добавлен 19.02.2012

  • Проектирование помещения для хранения ценной информации. Возможные каналы утечки данных. Характеристики средств защиты информации. Съем информации за счет электромагнитных излучений проводных линий 220 B, выходящих за пределы контролируемой зоны.

    курсовая работа [2,9 M], добавлен 14.08.2015

  • Характеристика объекта системы автоматического управления. Передаточная функция замкнутой системы. Начальное и конечное значение переходного процесса. Сравнение частотных характеристик объекта управления и замкнутой системы. Оценка устойчивости системы.

    курсовая работа [1,6 M], добавлен 18.01.2016

  • Модель обработки радиоголографических изображений. Изображение объекта, находящегося за препятствием. Фильтр для практической реализации метода. Исследование эффективности метода пространственной фильтрации при малом поглощении и преломлении в стене.

    дипломная работа [4,1 M], добавлен 19.06.2013

  • Управляемый объект из четырех типовых динамических звеньев, соединенных между собой в определенной последовательности с образованием двух замкнутых контуров. Исследование устойчивости объекта. Расчетная схема цифровой модели объекта для системы Simulink.

    курсовая работа [571,3 K], добавлен 11.02.2013

  • Оптимізація плану покриття, тобто забезпечення мобільного зв'язку у заданій зоні з мінімально необхідним використанням апаратних і частотних ресурсів (кількості базових станцій, використаних частотних радіоканалів). Частотний план кожної базової станції.

    курсовая работа [2,0 M], добавлен 07.06.2010

  • Классификация отказов. Номенклатура и классификация показателей надежности. Характеристика основных показателей надежности и их статистическое определение. Переход объекта из одного вышестоящего технического состояния в нижестоящее. Кривая жизни объекта.

    реферат [431,2 K], добавлен 28.01.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.