Задача привязки траектории объекта к плану помещения

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