UA   EN
ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

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

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

1. Актуальность темы

Современным решением задачи навигации выступает навигация с помощью беспроводных технологий. Разработка таких систем и сервисов стала популярна в последние годы в IT-индустрии. Некоторые современные здания, например, аэропорты, торговые центры, склады имеют настолько сложную структуру и масштабы, чтобы чувствовать нехватку собственных навигационных инструментов. Так как это закрытые помещения, то спутниковая навигация в них невозможна по ряду причин, во-первых – спутниковый сигнал не проходит или искажается, проходя сквозь железобетонные здания, во-вторых – точность спутниковых координат составляет в среднем 6 метров, что является очень грубой погрешностью в пределах помещения.

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

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

Магистерская работа посвящена актуальной научной задаче разработки аппаратно-программной поддержки системы навигации для внутренних помещений, направленной на создние программного продукта осуществляющего функции системы навигации внитри зданий. В качестве операционной системы для программного продукта выступает ОС Android, так как данная операционная система установлена на большистве мобильных устройств во все мире [1]. На рисунке 1 приведен график использования операционных систем.

Статистика использования операционных систем в мире

Рисунок 1 – Статистика операционных систем

2. Цель и задачи исследования, планируемые результаты

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

Основные задачи исследования:

  1. Анализ методов навигации внутри помещения.
  2. Анализ алгоритмов поиска пути.
  3. Разработка графического интерфейса пользователя для отображения результатов работы системы.
  4. Разработка клиент-серверного взаимодействия системы навигации.
  5. Оценка эффективности разработанной системы.

Объект исследования: навигация внутри помещений

Предмет исследования: реализация аппаратно-программной поддержки системы навигации

В рамках магистерской работы планируется получение актуальных научных результатов по следующим направлениям:

  1. Получение оптимальной модели для хранения графа помещения.
  2. Реализация алгоритма поиска пути по графу и оценка его эффективности.
  3. Определение подхода клиен-серверного взаимодействия системы и спобов передачи элементов графа.
  4. Оценка производительности системы навигации.

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

  1. Клиент в виде приложения для мобильного устройства.
  2. Сервер базы данных для централизованного хранения информации.
  3. Графический интерфейс для отображения результатов работы системы.
  4. Модуль поиска пути для осуществления навигации.

3. Обзор исследований и разработок

Системы навигации внутри помещений можно разделить на два класса, а именно – активные и пассивные. Активные системы авигации предполагают использование активных датчиков/излучателей и позволяют отслеживать местоположение и траффик в реальном времени. Пассивные системы, соответственно, не используют для своей работы датчики/излучатели [2].

3.1 Активные системы навигации

Активные системы навигации внутри помещений используют следующие беспроводные технологии технологии: IR, UWB, Wi-Fi, BLE и 5G. Маяки распространяют сигнал, который улавливает устройство пользователя. Затем сигнал обрабатывается и на его основе определяется местоположение устройства пользователя относительно маяков, а в итоге относительно помещения. Основным преимуществом систем Wi-Fi является то, что они могут использовать существующие средства связи. Напротив, BLE гибок и удобен в развертывании. Чтобы соответствовать требованиям будущего Интернета вещей (IoT) и точной локализации, в новейшие технологии Wi-Fi и BLE были добавлены новые функции. 5G привлек к себе пристальное внимание благодаря своей высокой скорости, высокой надежности и малой задержке связи. По сравнению с предыдущими сотовыми технологиями, 5G определила три категории приложений, включая сверхнадежную связь с малой задержкой (URLLC) для обеспечения высокой надежности (например, надежность 99,999% при высокоскоростном движении со скоростью 500 км / ч) и сценарии с малой задержкой (например, на уровне миллисекунды) (например, автомобильные сети, промышленный контроль и телемедицина), улучшенная широкополосная мобильная связь (eMBB) для высокой скорости передачи данных (например, уровень гигабит в секунду, с пик 10 гигабит в секунду) и сценарии сильной мобильности (например, видео, дополненная реальность, виртуальная реальность и удаленное обслуживание). Существуют решения PLAN для помещений, основанные на других типах сигналов окружающей среды, таких как магнитные, акустические, атмосферное давление, видимый свет и другие.[3]

Местоположение в таких системах навингации определяется чаще всего по методу геометрического определения местоположения. Основной принцип - это геометрический расчет расстояний и углов. По типу измерения методы определения местоположения включают в себя основанные на диапазоне (например, мультилатерация, min – max, центроид, близость и гиперболическое позиционирование), на основе угла (например, мультиангуляция) и на основе угла и диапазона ( например, мультиангуляция). На рисунке 2 показан основной принцип этих методов.

Методы определения местоположения

Рисунок 2 – Методы определения местоположения

3.2 Пассивные системы навигации

Пассивная система навигации основывается на следующих технологиях: RFID, QR-коды, NFC и пр. Пассивная система навигации устроена следующим образом: специальные метки расположены в важных и доступных частях помещения. Взаимодействуя с метками пользователь может узнать где он находится в данный момент, а также система может предложить маршрут к желаемой части здания с учетом текущего местоположения. Система навигации, реализованная на пассивных девайсах, имеет ряд преимуществ по отношению к навигации, реализуемой посредством технологий активных девайсов. Основным преимуществом данного типа навигации является простота развертывания и высокая скорость интеграции. Так как для таких технологий не требуются источники питания и минимум специализированного оборудования, то это еще и экономически целесообразно для предприятий с малым бюджетом [2].

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

Аспекты сложности для внутренних навигационных систем включают вмешательство / усилия человека во время развертывания и обслуживания внутренней навигационной системы, а также необходимое время вычислений и обработки устройства, которое несет пользователь. Из-за усилий, необходимых для установки всех компонентов системы, таких как метки местоположения и метки карты, вмешательство человека во время первоначального развертывания внутренней системы NFC очень велико; но, напротив, человеческие усилия, необходимые для обслуживания, очень низкие после процесса развертывания. По отношению к пользователям; они не будут тратить время на использование системы, поскольку необходимое время обработки для любого действия, такого как определение местоположения, вычисление маршрутов и т. д., очень мало и может быть измерено в миллисекундах. На этом этапе следует отметить, что если теги местоположения распределены более плотно, пользователи могут тратить свое время, слишком часто касаясь тегов, возможно, для повышения точности своего местоположения. В заключение можно сказать, что сложность такой системы навигации средняя [5].

На рисунке 3 изображена система навигации, использующая ключевые точки. Такая система не требует активного оборудования, но и местоположение пользователя отслеживается только в ключевых точках. В данном случае местоположение пользователя задается в системе при помощи считывания RFID, NFC меток, QR-кода либо задается вручную самим пользователем. Система получает ключевую точку пункта назначения и строит маршрут, однако в отличие от системы с относительными координатами, в случае отклонения пользователю нужно будет считывать новую метку или задавать свое новое местоположение, чтобы система перестроила маршрут.

Пример работы системы навигации с относительными координатами

Рисунок 3 – Пример работы системы навигации с относительными координатами
(анимация: 6 кадров, непрерывные повторения, 23 килобайта)

4. Алгоритмы поиска пути

Работа систем навигации основана на поиске пути от точки отправления к точке прибытия на графе, который представляет собой упрощенную цифровую копию реального мира. Возможность реализации графа очень гибкая, поскольку реальный мир можно оцифровать с необходимой для работы системы навигации точностью. Нет необходимости переносить на граф детали реального мира, несущественные для решения задачи поиска пути в каждом конкретном участке объекта навигации. Для поиска пути по графу существует множество алгоритмов, как универсальных, так и специализированных под конкретные ситуации. Многие алгоритмы, работающие с графами, требуют определенной систематической обработки вершин или ребер графа. Среди них можно выделить: поиск в ширину, алгоритм Дейкстры и алгоритм А* [6].

Поиск в ширину (обход в ширину, breadth-first search) — это один из основных алгоритмов на графах. В результате поиска в ширину находится путь кратчайшей длины в невзвешенном графе, т.е. путь, содержащий наименьшее число рёбер. Алгоритм был разработан независимо Муром и Ли для разных приложений (поиск пути в лабиринте и разводка проводников соответственно) в 1959 и 1961 годах. Этот алгоритм можно сравнить с поджиганием соседних вершин графа: сначала мы зажигаем одну вершину (ту, из которой начинаем путь), а затем огонь за один элементарный промежуток времени перекидывается на все соседние с ней не горящие вершины. В последствие то же происходит со всеми подожженными вершинами. Таким образом, огонь распространяется «в ширину». В результате его работы будет найден кратчайший путь до нужной клетки.

Алгоритм Дейкстры – разработан Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов с рёбрами положительного веса. Алгоритм использует «жадный» подход в том смысле, что мы находим следующее лучшее решение, надеясь, что конечный результат является лучшим решением для всей задачи.

Алгоритм А* – алгоритм поиска, который находит маршрут от стартовой вершины к финальной с наименьшей стоимостью. Был разработан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Данный алгоритм по сути является расширением алгоритма Дейкстры, но достигает более высокой производительности за счет введения в работу алгоритма эвристической функции.

Задача алгоритма поиска А*состоит в том, что некий подвижный объект должен перейти из точки А в точку B по оптимальной траектории. Участок перемещения объекта содержит различные препятствия, которые необходимо обойти. Кроме этого, возможно добавление различных критериев (минимальный/максимальный угол поворота, ускорение/замедление и т.п.) для перемещения по прогнозируемой траектории.

Алгоритм реализуется следующими шагами:

  1. Формируются 2 списка вершин: уже рассмотренные вершины и ожидающие рассмотрения. В список рассмотренных заносится A.
  2. Для каждой соседней вершины производится расчет F = G + H, где G – стоимость пути от старта, а H – эвристическое приближение стоимости пути.
  3. Выбирается вершина с наименьшим F. Если она является B, то сохраняется путь, двигаясь от B назад к целевой точке. Иначе эта вершина выбирается текущей, удаляется из открытого списка и заносится в закрытый.
  4. Для каждой из точек, соседних с текущей, производятся следующие действия:
    1. Если соседняя точка уже рассмотрена, то она пропускается.
    2. Если соседней точки нет в списке ожидающих рассмотрения, то она добавляется в этот список. Текущая клетка для неё становится родительской. Рассчитывается F, G, H.
    3. Если соседняя клетка уже в списке ожидающих рассмотрения, то проверяется, не дешевле ли путь через эту клетку. Стоимость сравнивается по G. Если стоимость меньше, то родитель клетки меняется на текущую клетку и для неё пересчитываются стоимости G и F.
  5. Если список ожидающих рассмотрения пуст, а цели нет, то это означает, что маршрута до цели не существует.

Таким образом, алгоритм А* не только проведет движущийся объект беспрепятственно к цели, но и при этом обходит минимальное количество вершин, поскольку он эффективно использует эвристику [7].

5. Приложение

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

Структура системы поиска и построения маршрутов внутри помещения

Рисунок 4 – Структура системы поиска и построения маршрутов внутри помещения

Структурная схема включает в себя следующие элементы:

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

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

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

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

Заключительным этапом работы системы является окно отображения маршрута пользователю. В данном окне отображается список контрольных точек, полученный в результате работы системы анализа маршрута. Список контрольных точек отображается в виде карточек, смахивая которые пользователь перемещается к следующему или предыдущему элементам списка [8].

Карточки реализованы с помощью инструментов Android Jetpack, а именно с помощью MotionLayout. MotionLayout – это слой, который поддерживает переходы между различными состояниями, которые определены в MotionScene [9].

6. Выводы

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

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

Список источников

  1. Mobile Operating System Market Share Worldwide [Электронный ресурс] // StatCounter. – URL: https://gs.statcounter.com/os-market-share/mobile/worldwide
  2. Алутин Е.А. РАЗРАБОТКА СИСТЕМЫ НАВИГАЦИИ ВО ВНУТРЕННИХ ПОМЕЩЕНИЯХ НА ПЛАТФОРМЕ ANDROID / Алутин Е.А., Кривошеев С.В. // ИНФОРМАТИКА, УПРАВЛЯЮЩИЕ СИСТЕМЫ, МАТЕМАТИЧЕСКОЕ И КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ (ИУСМКМ-2020)Сборник материалов XI Международной научно-технической конференции в рамках VI Международного Научного форума Донецкой Народной Республики. - Донецк, с. 495-499
  3. El-Sheimy, N., Li, Y. Indoor navigation: state of the art and future trends. Satell Navig 2, 7 (2021). https://doi.org/10.1186/s43020-021-00041-3
  4. Абдрахманова А.М., Намиот Д.Е. Использование двумерных штрихкодов для создания системы позиционирования и навигации в помещении // Прикладная информатика. 2013. №1 (43). URL: https://cyberleninka.ru/article/n/ispolzovanie-dvumernyh-shtrihkodov-dlya-sozdaniya-sistemy-pozitsionirovaniya-i-navigatsii-v-pomeschenii (дата обращения: 14.12.2021).
  5. Ozdenizci B, Coskun V, Ok K. NFC internal: an indoor navigation system. Sensors (Basel). 2015 Mar 27;15(4):7571-95. doi: 10.3390/s150407571. PMID: 25825976; PMCID: PMC4431189.
  6. Алутин Е.А. Анализ производительности алгоритмов поиска пути для графа навигации / Алутин Е.А., Мальчева Р.В. //
  7. Койбаш А.А. Прогнозирование траектории движения подвижного объекта распределенного симулятора тяжелой инженерной техники / А. А. Койбаш, С. В. Кривошеев // Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ – 2016): материалы VII междунар. науч.-техн. конф., Донецк, 2016. / редкол. А. Ю. Харитонов и др. Донецк: ДонНТУ, 2016. С. 343–346.
  8. Алутин Е.А. Система поиска и построения маршрутов внутри помещения с помощью путевых карточек / Алутин Е.А., Кривошеев С.В. // ПРОГРАММНАЯ ИНЖЕНЕРИЯ: МЕТОДЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ИНФОРМАЦИОННО-ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (ПИИВС-2020) сборник научных трудов III Международной научно-практической конференции (студенческая секция). Донецк, 2020, с. 155-161.
  9. MotionLayout [Электронный ресурс] // Android Developers. – URL: https://developer.android.com/reference/androidx/constraintlayout/motion/widget/MotionLayout