ForkFilter. Как мы придумали real-time алгоритм фильтрации «плохих» координат при построении пройденного маршрута

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Привет, инженеры! :) Мое имя — Артем, и я работаю девелопмент-директором в Onde. В компании я прошел путь от Junior Android Developer до текущей менеджерской роли (бэкенд тоже потрогал, если что). Когда я был Android-разработчиком, мы столкнулись с одной нетривиальной и очень неприятной проблемой, которая заставила нас изрядно попотеть и даже придумать свой алгоритм. И вот, спустя года, я решил поделиться решением, которые мы придумали. Думаю, вам будет интересно взглянуть, сколько подводных камней имеет на первый взгляд простенькая проблемка.

Сегодня я расскажу вам о ForkFilter — real-time алгоритме фильтрации «плохих» координат при построении пройденного маршрута.

С чего все началось

В Onde мы делаем софт для заказа такси (ну или доставки, или вообще чего угодно). В процессе заказа мы записываем GPS-координаты водителя, по которым потом определяем расстояние поездки и, собственно, конечную цену заказа. Но при получении координат с телефона случаются помехи: может прийти координата в 10 км от реального местоположения.

Почему так происходит?

Целостность маршрута часто нарушают «выпады» местоположений. Выпады возникают из-за параллельной работы трех источников получения геоданных (Wi-Fi, сети сотовой связи и GPS). В итоге конечное расстояние, зафиксированное мобильным телефоном, может в разы отличаться от реального, — и цена заказа вместе с ним.

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

Начали мы с командой с нуля.

Что делает ForkFilter

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

Сейчас ForkFilter состоит из следующих основных этапов:

  • Получение новой координаты и определение для нее родительской точки с помощью функции isConnect (о ней я расскажу ниже).
  • Построение дерева возможных путей.
  • Слияние веток.
  • Определение/изменение main fork.
  • Выдача pre-filtered-координат для отображения маршрута и цены в реальном времени.
  • Выдача filtered-координат, которые будут учитываться в формировании конечного пути и конечной цены.

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

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

Вот так это выглядит

Каждый узел графа — это координата пути. Последовательность координат порождает путь. Количество возможных вариантов путей = количество листовых вершин.

Когда в ForkFilter поступает новая точка, происходит вот что:

1. Сначала алгоритм перебирает все листовые узлы и проверяет, не является ли координата в листовом узле родительской точкой для новой координаты (точка А родительская для точки Б, если точка А старше точки Б и точка Б соединяется с точкой А). Точка Б соединяется с точкой А, если результат функции isConnect возвращает true.

2. Если найден один листовой узел, с которым соединяется новая точка, то листовой узел становится родительским для новой точки. Новая точка добавляется в дерево и буфер.

3. Если найдено n (n>=2) листовых узлов, с которыми соединяется новая точка, то n возможных путей объединяются в одной точке. Тогда нужно построить n путей, выбрать из них лучший и удалить все остальные. Затем новая точка добавляется в буфер и дерево. Родительским узлом для новой точки будет последний узел лучшего пути.

4. Если ни один листовой узел не найден, то мы пробуем соединить новую точку с узлами, не являющимися листовыми. Для этого перебираем все точки, не являющимися листовыми, в порядке, обратном порядку добавления (от самой недавно добавленной точки к добавленной самой первой). Затем для каждой точки проверяем значение функции isConnect(point, newPoint), где newPoint — поступившая в ForkFilter новая точка, а point — не являющаяся листовой точка.

Тут важно отметить, что если мы нашли такую не листовую точку, с которой соединяется новая точка, то все ее предки (точки, располагающиеся выше по дереву) должны быть исключены из проверки. На это есть 2 причины. Во-первых, все предки точки, с которой соединяется новая точка, также будут являться точками, с которым соединяется новая точка, ввиду смысловой нагрузки функции isConnect. Во-вторых, строя маршрут, мы соединяем последнюю точку уже пройденного пути с новой точкой. Соответственно, нам нужно соединить только последнюю точку уже известного пусти с новой точкой (см. рисунок под абзацем). Точка 1 исключается из проверки, так как она является предком для точки 2 (и 3), с которым соединяется новая точка 8.

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

Новая точка (8) соединяется с не листовыми узлами 2 и 3

5. Если найдено n (n>=2) не листовых узлов, с которыми соединяется новая точка, то нужно выбрать единственную родительскую точку для новой координаты путем выбора лучшего пути среди образовавшихся после появления новой точки. После того, как будет выбран лучший путь, новая точка добавляется в буфер и дерево. Родительским узлом для новой точки будет являться последний узел лучшего пути.

6. Если не найден ни один не листовой узел, с которым соединяется новая точка, мы считаем эту координату плохой и не добавляем ее в дерево и буфер.

Что за функция isConnect

Функция isConnect(pointA, pointB) — это система неравенств, которая отвечает на вопрос «можно ли оказаться в точке pointB из точки pointA». Если функция возвращает true, можно считать, что точка pointB является продолжением пути, для которого pointA была последней точкой.

Первое неравенство проверяет, старше ли новая точка pointB точки сравнения pointA. Благодаря этому условию координаты в пути не перемешиваются по времени.

Третье неравенство ограничивает максимальную скорость на участке между точкой pointA и точкой pointB. Значение MAX_SPEED_THRESHOLD = 300 км/ч. Это ограничение мы ввели из эмпирических соображений: алгоритм нам нужен для отслеживания движения нормального, гражданского наземного транспорта, скорость движения которого не превышает это значение.

Но самое любопытное второе неравенство. Функция getSuddenness возвращает неожиданность точки pointB относительно pointA.

Значение SUDDENNESS_THRESHOLD = 3.5 м/с^2. Эту константу мы вывели эмпирическим путем на основе анализа десятков реальных треков транспортных средств. Неожиданность — это нормированная величина изменения скорости и направления реальной точки относительно предсказанной.

Как ForkFilter определяет, какой путь лучший, если новая точка соединяется с n(n>=2) точками?

Чтобы определить лучший путь, в этом случае используется функция weightFork. Она возвращает double-значение — вес пути. Для определения лучшего пути достаточно посчитать вес каждого пути и выбрать путь с минимальным весом. Чем меньше вес, тем лучше набор точек, составляющий этот путь.

Но чтобы взвесить путь, нужно знать начальную неожиданность каждой точки. Неожиданность — это случайная величина X с нормальным распределением. Весом пути назовем дисперсию неожиданности D(X), где X — неожиданность, M — математическое ожидание случайной величины X.

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

Расчет именно начальной неожиданности нужен, чтобы не потерять истинное (начальное) значение неожиданности. Нам всегда нужно знать, насколько точка была неожиданна в момент попадания в ForkFilter. Начальную неожиданность мы вычисляем следующим образом:

  • Если при добавлении точки в ForkFilter она присоединилась к одному или более листовому узлу, что начальная неожиданность рассчитывается как неожиданность точки относительно родительской точки;
  • Если при добавлении точки в ForkFilter она не соединяется ни с одним листовым узлом, то начальная неожиданность рассчитывается как неожиданность точки относительно последней добавленной точки в ForkFilter.

А что, если буфер фильтра пуст?

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

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

Виртуальная вершина имеет нулевую начальную неожиданность, потому никак не влияет на вес под-пути. Виртуальная вершина удаляется из буфера, как только все напрямую зависящие от нее узлы (child node) будут удалены из буфера.

Виртуальная вершина (VR), точка выпада (1) и последовательность хороших точек (2,3,4,5)

Как получать отфильтрованные данные

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

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

Как ForkFilter работает в реальном времени

Чтобы алгоритм работал в реальном времени, мы ввели механизм pre-filtered (предварительно отфильтрованных) координат. Pre-filtered-точка выдается немедленно, но не является гарантированно хорошей, то есть не обязательно будет выдана как filtered.

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

  • Если дерево путей после добавления новой точки содержит лишь один листовой узел, и этим листовым узлом является только что добавленная новая точка;
  • Если дерево путей содержит n (n>=2) листовых узла, однако новая добавленная точка содержится в «главном под-пути».

Соответственно, такую точку можно без промедления выдать из ForkFilter как pre-filtered.

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

Чтобы сделать pre-filtered-точки более достоверными, мы разработали механизм «главного под-пути» (англ., main fork). Конечной точкой главного под-пути является точка листового узла. Этот под-путь имеет лучшую (минимальную) характеристику главного под-пути. Точки главного под-пути с большей вероятностью окажутся в финальной выдаче filtered-координат.

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

ForkFilter в работе

Уже четыре года мы успешно используем ForkFilter в работе Onde. В большинстве случаев он эффективен, работает в режиме реального времени, и независимо от источника координат (как мы и хотели), потребляет мало ресурсов и в целом очень адаптивен. Из минусов можно назвать только то, что фильтр не чувствителен к небольшим выпадам и не фильтрует координаты, которые приходят реже, чем раз в минуту.

👍ПодобаєтьсяСподобалось3
До обраногоВ обраному3
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Самое очевидное, но явно неактуальное если заюзали алгоритм, это проверять новую координату на основе предыдущих. Разве нельзя определить аномальную координату? Если чел условно за секунду оказался за несколько км то это 100% аномалия.

Так это — фильтр Калмана.

Да, что то типа, но я о нем не думал ) велосипед изобрел ))

Не зовсім Калман — скоріш раціональні обмеження на першу та другу похідні від часу.

Я, свого часу, просто перевіряв швидкість та прискорення між поточною та попередньою точками. І прийняв обгрунтовані припущення, що автотранспорт не повинен рухатися дорогами загального користування із швидкостями, вищими за 200 км/годину та з прискореннями, більшими за 1g. Якщо нова точка породжувала швидкість чи прискорення, більші за обмеження, то вона відкидалася.

Не 100% надійний метод, але дешевий та достатньо ефективний.

Когда читаешь статью про новый метод, то в первую очередь хочется увидеть сравнение с другими известными методиками.

рисунки не подписаны
который из них 3.2?

А чем фильтр Калмана не угодил?..

Толковая статья, спасибо !

Підписатись на коментарі