Статья: Использование фильтра частиц для решения задачи навигации внутри помещений

Использование фильтра частиц для решения задачи навигации внутри помещений

А.С. Смирнов

В работе рассматривается использование метода Монте-Карло в задаче навигации внутри помещений. Первоначально расчет координат происходит за счет обработки измерений мощности Wi-Fi/Bluetooth сигналов, а также информации о динамике движения человека. Далее применяется алгоритм Байесовской фильтрации, использующий карту помещения. В заключении приводятся сравнительные результаты испытаний.

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

Можно выделить несколько основных подходов решения задачи внутреннего позиционирования. Один из них - это использование дополнительной инфраструктуры и специальных радиопередатчиков, позволяющих точно измерять время распространения радиосигнала, производить трилатерацию [1]. Для решения навигационной задачи в случае невозможности применения дополнительного дорогостоящего оборудования, принято использовать информацию о мощности принимаемого Wi-Fi/Bluetooth сигнала. Ввиду распространённости этих технологий, внутри помещений могут быть доступны 5-7 различных точек доступа одновременно, что позволяет построить карту мощностей принимаемого сигнала (RSSI) в опорных точках с необходимой точностью. В дальнейшем навигация осуществляется путём сравнения мощностей принимаемых сигналов с заранее составленной картой помещения [2].

Измерения мощности сигналов Wi-Fi/Bluetooth, традиционно используемые для решения этой задачи, имеют сильные флуктуации (рис. 1), что оказывает существенное влияние на точность позиционирования, для улучшения которой монте карло навигация коррекция

Рис. 1 Разброс измерений мощности Wi-Fi сигнала двух различных точек доступа.

используется информация о динамике движения (длина пройденного пути, направление движения, моменты остановок, детектирование шагов и определение их длины). Эти параметры могут быть определены за счет обработки измерений инерциально-измерительного блока (ИИБ) и других датчиков, таких как магнитометр, барометр и др.[3]

Также в качестве дополнительной информации можно использовать карту помещения, позволяющую определять наиболее вероятную траекторию и избежать пересечения стен и других преград. Ключевая идея - объединить модель движения человека и картографическую информацию для уменьшения ошибок позиционирования. Использование данных о карте помещения требует применения новых нелинейных алгоритмов. Фильтр частиц, или последовательный метод Монте-Карло, является фильтром байесовского типа и используется для оценки апостериорной плотности вероятности переменных вектора состояния с использованием значений наблюдаемых переменных [4]. Для фильтров такого типа может быть использована любая модель вектора состояния с необходимым распределением шума измерений. Выборка из распределения представляется как набор частиц, где каждая частица имеет вес, означающий вероятность попадания в выборку.

Общей проблемой таких фильтров является проблема деградации, или непропорциональности весов частиц, решаемая за счет этапа повторной выборки, который может отличаться в зависимости от модификаций алгоритма и конкретной задачи. Такие методы фильтрации часто являются альтернативными расширенному фильтру Калмана, но имеют преимущество в точности оценки при достаточном количестве частиц, поэтому предлагается использовать фильтр частиц для комплексирования позиционной информации, доставляемой обработкой Wi-Fi/Bluetooth сигналов, и информации о динамике движения человека, получаемой за счет анализа измерений ИИБ. При этом для создания ограничений на траекторию движения будет использоваться карта помещений.

Фильтр частиц

В настоящее время карты помещений доступны в любом цифровом формате или могут быть созданы, используя широкий выбор доступного программного обеспечения. При создании системы позиционирования внутри помещений целесообразно использовать карту здания, которая может накладывать естественные ограничения на траекторию движения человека. Во время движения люди не могут пересекать стены или внезапно переместиться в другую часть здания. Для уменьшения влияния таких эффектов может быть применён парциальный фильтр, использующий набор частиц, распределенных по цифровой карте [4]. Каждая частица обладает весом, учитывая который можно оценить наиболее вероятное расположение приёмного устройства.

Фильтр частиц состоит из трёх этапов:

1. Прогноз.

2. Коррекция.

3. Повторная выборка.

Прогноз

В течение первого этапа прогноза частицы эволюционируют на карте в соответствии с уравнением:

(1)

Где i номер текущей итерации, N количество частиц, угол курса, полученный с помощью обработки измерений ИИБ и магнитометра, l - длина шага, вычисленная на основе модуля вектора ускорения[5]. После вычисления текущих координат на i+1 шаге, необходимо исключить все недопустимые траектории. Таким образом, если частица пересекла стену или любое другое препятствие, должно быть учтено, что:

(2)

Предлагается использовать цифровые карты помещения в формате BMP с глубиной цвета 1 бит на пиксель и числом частиц N=1000, которое может быть уменьшено при наличии ограничений на вычислительные ресурсы. На этапе инициализации (i=0) частицы равномерно распределяются по всей карте с одинаковыми весами

Коррекция

Когда Wi-Fi/Bluetooth измерения становятся доступны, вес частиц должен быть скорректирован. В первую очередь вычислим :

(3)

где координаты приёмника, полученные за счет сравнения мощности Wi-Fi/Bluetooth сигналов с заранее составленной радиокартой. В данной работе предлагается использовать вероятностный метод позиционирования (метод гистограмм), представленный в [6].

Теперь есть все необходимые вероятности для обновления веса частиц. Нужно лишь совместить их для нахождения нового апостериорного распределения (рис. 2):

(4)

Для получения апостериорной функции распределения необходимо нормализовать веса:

(5)

Поэтому, каждая частица должна иметь вес:

(6)

Теперь можно вычислить новое апостериорное распределение(рис. 2):

(7)

Где дельта функция Дирака.

Рис.2 Распределение веса частиц после коррекции.

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

(8)

Критерием для запуска этапа повторной выборки служит условие:

Treshold

где Treshold - заранее заданное пороговое значение. Наиболее удобно задавать его в процентном соотношении от общего количества частиц.

Повторная выборка

Общепринятым решением вышеописанной проблемы является пересчет. Набор старых частиц заменяется новым в соответствии с текущей плотностью распределения весов (7):

Т.е. частицы с большим весом с большой вероятностью будут использованы несколько раз на карте, в то время как частицы с маленьким весом наоборот, могут быть вовсе не использованы. Величина всех новых частиц задается равной 1/N.

В этой работе предлагается использовать многослойную выборку, когда все частицы в соответствии с весом делятся на N слоев размера 1/N, где N - суммарное количество частиц. Для каждого слоя генерируется равномерно распределенное случайное число rand, а в выборку попадает частица, соответствующая обратной функции распределения .

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

Результаты

Тестирование алгоритмов проводилось во время проведения VIII Международного навигационного форума и выставки «Навитех 2014». Навигационные алгоритмы были встроены в приложение для смартфонов посетителей выставки, обладающих приемником Wi-Fi/Bluetooth сигналов и ИИБ. На площади 14000 кв.м. были расставлены 140 Bluetooth Low Energy маяков, передающих сигнал на расстояние 50 м. Частота передачи радиосигнала - 1 Гц. В 143 опорных точках была предварительно снята карта радиосигналов помещения, состоявшего из двух этажей (смена этажа автоматически определялась навигационной системой). На рис. 4 показана траектория пользователя, вычисленная разработанной системой позиционирования внутри помещения. Результаты были получены смартфоном Apple iPhone 5. Все вычисления производились в реальном времени на смартфоне пользователя.

Рис. 4 Показана траектория, рассчитанная с помощью алгоритма использующего метод гистограмм, фильтр частиц и ИИБ. Черными точками отмечено истинное положение.

В таблице 1 представлены результаты оценки точности работы разработанной системы позиционирования с использованием разных алгоритмов. Точность оценивалась путём сравнения вычисленных координат в определённые моменты времени с известными точными координатами контрольных точек (рис.4). Случай 1 соответствует вероятностному методу определения местоположения (методу гистограмм) без использования фильтра частиц и ИИБ. Вторая строчка таблицы соответствует совместному использованию фильтра частиц и метода гистограмм. В 3 случае помимо вышеописанных алгоритмов используется информация о динамике движения человека, доставляемая за счет обработки измерений ИИБ.

Т а б л и ц а 1

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

Заключение

В данной работе описаны алгоритмы разработанной навигационной системы, вычисляющей местоположение за счет обработки измерений Wi-Fi/Bluetooth сигналов, инерциально-измерительного блока и карты помещений. Особое внимание уделено фильтру частиц, использование которого позволяет комплексировать позиционную и картографическую информацию. Данные о динамике движения человека (момент и длина шага, моменты остановок, угол курса), доставляемые ИИБ, используются на этапе прогноза.

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

Литература

1. Dokpikul P. Indoor Positioning Based on IEEE 802.15.4a Standard Using Trilateration Technique and UWB Signal // P. Dokpikul, S. Promwong, J. Sangthong. - Progress In Electromagnetics Research Symposium Proceedings, 2012.- p.473

2. Панёв А.А. О навигации внутри помещений с использованием грубой БИНС и данных о мощностях Wi-Fi сигналов. / А.А. Панёв [и др.] // Материалы 20 Санкт-Петербургской международной конференции по интегрированным навигационным системам.- СПб.: ОАО «Концерн «ЦНИИ «Электроприбор», 2013.

3. Golovan A.A. Indoor Positioning Using Wi-Fi Fingerprinting, Pedestrian Dead Reckoning and Aided INS. / A.A. Golovan, A.A. Panyov, A.S. Smirnov. // Proceedings of the 1th IEEE International Symposium on Inertial Sensors and Systems, 2014.

4. Liu P., Ling Pei. An Improved Indoor Localization Method Using Smartphone Inertial Sensors /P.Liu [and oth.] // Proceedings of International Conference On Indoor Positioning And Indoor Navigation (IPIN).

5. Gerard L. Motion mode recognition and step detection algorithms for mobile phone users. / L. Gerard, S. Melania, R. Valerie // Sensors, 13.2, 2013, p. 1539-1562.

6. Панёв А.А. Навигация внутри помещений с использованием Wi-Fi сигналов, магнитометра и информации о движении человека / А.А. Панёв [и др.] // Материалы 21 Санкт-Петербургской международной конференции по интегрированным навигационным системам.- СПб.: ОАО «Концерн «ЦНИИ «Электроприбор», 2014.