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

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

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

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

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

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



Аннотация

В системах определения местоположения объектов внутри помещения, основанных на распространенных стандартах беспроводной передачи данных (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. c₁ и c₂ -- коэффициенты влияния на оценку изменений длин звеньев и углов между звеньями соответственно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

для которых

Точка

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

Положим

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

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

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

Тогда

x_i = q_i(s_i)

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

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

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

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

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

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

Метод частиц

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x_i = q_i-1 + G_г,щ+ц(d_i),

где

щ= ш_i-1.

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

C_i(s) = C_i-1(s_i-1)+|1-г|+|ц|, q_i(s) = x_i, ш_i(s) = щ + ц, ж_i(s) = s_i-1.

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

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

s_i = ж_i+1.

Тогда

x_i = q_i

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

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

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

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

Рисунок 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

...