АНАЛИЗ МЕТОДОВ ПРОСТРАНСТВЕННОЙ НАВИГАЦИИ И ТРАССИРОВКИ МАРШРУТОВ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ

УДК 681.142

Дубовик Н.Н.¹, Лавров А.В.², Ногин О.А.¹, Туманов В.М.¹

¹ Магистр, ² канд. техн. наук, доцент, МГТУ им. Н.Э. Баумана, кафедра «Проектирование и технология производства электронной аппаратуры»

АНАЛИЗ МЕТОДОВ ПРОСТРАНСТВЕННОЙ НАВИГАЦИИ И ТРАССИРОВКИ МАРШРУТОВ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ

Аннотация

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

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

Dubovik N.N.¹, Lavrov A.V.², Nogin O.A.¹, Tumanov V.M.¹

¹ Undergraduate, ² PhD in Engineering, Associate Professor, BMSTU, Department "Design and technology of electronic equipment"

ANALYSIS OF METHODS OF SPATIAL NAVIGATION AND TRACE OF ROUTE WITH LINEAR CONSTRAINTS

Abstract

This article is devoted to research issues related to navigation within the various rooms, which have a complex structure. The first part is a comparative analysis of existing systems, methods and technologies of positioning, considered their main characteristics, strengths and weaknesses. The second part of the article deals with the problems of building a navigation system, graphical visualization and optimal route search. Provided optimum solutions for the graphic representation of maps of buildings, considered various software technologies and algorithms for the construction of navigation routes in custody are the advantages of the chosen solution for the construction of the navigation recommendations for use.

Keywords: navigation, a building with a complex structure, tracing, orientation, geometry, three-dimensional graphics, algorithms, software.

 

ВВЕДЕНИЕ

Решению проблем гео- и локальной навигации посвящено большое количество работ, обзор которых приведен в [1], однако проблемы локальной навигации - навигации внутри различных зданий и помещений  остается актуальной. Следует отметить и значительную заинтересованность в сервисных услугах, предоставляемых на основе местоположения клиента и его предпочтений. Здания с каждым днем становятся все более объемными, а их структура усложняется, в них вносятся планировочные изменения, которые не всегда оперативно учитываются. В сооружениях такого типа уверенно могут ориентироваться лишь постоянные посетители. Очевидно, что в такой ситуации на освоение в незнакомом месте тратится огромное количество времени. Таким образом, возникает потребность в сервисе, который поможет любому его пользователю максимально просто и без траты лишнего времени добраться до нужного ему места в здании. Такие системы, как: GPS, Galileo, ГЛОНАСС, iBeacon, WPS и др., обеспечивающие работу таких сервисов, как Google Maps, NAVIMIND, 2GIS и др., ориентированы на решение задач геонавигации и проблемы локальной навигации не решают. Стоит так же отметить, что решения проблемы локальной навигации часто являются актуальными не только внутри, но и вне зданий – в условиях плотной застройки часто неэффективны даже системы, предназначенные специально для навигации на открытой местности.

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

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

• единое ядро для мобильного и веб-приложения;
• использование 2D и 3D – карт;
• построение наиболее простых и понятных маршрутов;
• упрощение взаимодействия клиентов (посетителей) и зданий;
• возможность пользовательского развития, когда пользователи имеют возможность вносить (после модерации) оперативные изменения в планы помещений;
• предоставление актуальной информации, такой как график работы, контактная информация и т.п.

Задачи прокладки эффективных маршрутов внутри зданий можно отнести к классическим задачам трассировки с линейными и пространственными ограничениями, которые хорошо проработаны и эффективно применяются в радиоэлектронике [2-9].

 1. СИСТЕМЫ ГЕОЛОКАЦИИ И ИХ ПАРАМЕТРЫ

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

Таблица 1.1 – Системы определения местоположения

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

В таблице 1.2 проанализируем различные представленные сейчас на рынке навигационные сервисы.

Таблица 1.2 – Навигационные сервисы

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

2. ИНС – ИНФОРМАЦИОННО – НАВИГАЦИОННАЯ СИСТЕМА

 2.1. Преимущества ИНС

 В качестве примера для анализа принципов реализации indoor - систем рассмотрим информационно-навигационную систему (ИНС), которую авторский коллектив реализует на базе МГТУ им. Н.Э. Баумана. Что из себя представляет ИНС?

Во-первых, это модульная система, состоящая из нескольких подсистем, которая позволяет пользоваться всем арсеналом функций навигации на максимальном количестве устройств: терминал, планшет, смартфон, web и т.д. (см. рис. 1). Это достигается благодаря выбранным технологиям, которые позволяют получить не только удобный интерфейс взаимодействия с пользователем, но и эффективную систему, обеспечивающую высококлассную навигацию по выбранному объекту, в данном случае по МГТУ им. Н.Э. Баумана, некоторые из зданий которого датируются 19 веком и имеют сложные архитектурные решения.

Рисунок 1 – Работа единой системы на разных устройствах

Во-вторых, в системе помимо 2D карт используются и 3D-карты, так как только они могут удовлетворить требованию качественной и понятной прокладки маршрута. Зачастую в зданиях со сложной архитектурой 2D – карты не помогают, а наоборот вносят путаницу.

Рассмотрим эту проблему на примере ставшей нарицательной проблемой поиска аудитории 501Ю ГУК МГТУ им.Н.Э.Баумана: Ее расположение на 2D карте МГТУ им. Н.Э. Баумана показано на рис. 2:

Рисунок 2 – 2D карта 5 этажа южного крыла – аудитория 501-Ю

Проход к этой аудитории напрямую через центральную часть здания невозможен, так как все переходы закрыты. Попасть в аудиторию 501 Ю можно только поднявшись снизу и только по одной - единственной лестнице (рис. 3):

 

Рисунок 3 – 2D карта 5 этажа южного крыла – путь к аудитории 501-Ю.

Таким образом, студенты сталкиваются с другой проблемой: как найти эту самую лестницу? Попасть на нее так же довольно сложно: гарантированный проход есть только на 3 этаже. 3D карты с легкостью решают эту проблему, наглядно показывая весь путь до необходимой аудитории, как это показано на рис. 4.

Рисунок 4 – 3D путь до аудитории 501-Ю

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

 2.2. Архитектура и виды обеспечений ИНС

Для обеспечения работоспособности сервиса на максимальном количестве устройств используются следующие Web-технологии: HTML5, CSS3, Javascript. Но это лишь скелет программной составляющей. Для реализации необходимых функций используется огромное количество фреймворков и библиотек для Javascript. Так же для требуемой визуализации используется графическая библиотека WebGL [11].

WebGL (Web-based Graphics Library) — программная библиотека для JavaScript, позволяющая создавать интерактивную 3D-графику, функционирующую в широком спектре совместимых с ней веб-браузеров. За счёт использования низкоуровневых средств поддержки OpenGL, часть кода на WebGL выполняется непосредственно на видеокартах. WebGL — это контекст элемента canvas HTML, который обеспечивает API 3D графику без использования плагинов.

Библиотека построена на основе OpenGL ES 2.0 и обеспечивает API для 3D-графики, использует HTML5-элемент canvas, также оперирует с DOM. Автоматическое управление памятью предоставляется языком JavaScript.

На сегодняшний день имеются эффективные реализации WebGL для большинства десктопных и мобильных браузеров: Mozilla Firefox, Google Chrome, Safari, Opera, IE11. В состав рабочей группы разработавший стандарт, входят: Khronos Group, Apple Safari, Google Chrome, Mozilla Firefox и Opera, а также специалисты AMD и Nvidia.

WebGL [11] реализует императивный подход, то есть программный код должен точно описывать алгоритм преобразования данных для построения сцены. Несмотря на сложность, такой подход предоставляет гораздо больше возможностей для редактирования и обработки 3D – сцены.

Ориентация на WebGL обусловлена следующими преимуществами:

-         кроссплатформенность —WebGL может использоваться практически для всех мобильных и десктопных браузеров;

-        открытость платформы, доступность и бесплатность.

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

Таблица 2.2.1- Сравнение алгоритмов построения оптимального пути

В рассматриваемой системе используется алгоритм A*(ASTAR) [14].

Во время исследований скорости работы алгоритма Дейкстры в 1964 году Н. Нильсен предложил улучшить уже имеющийся алгоритм путем дополнительного использования эвристики. Новый алгоритм был назван А1. В течении следующих трех лет коллега Нильсена Б. Рафаэль занимался улучшением и оптимизацией алгоритма А1, но значительного улучшения характеристик ему достичь не удалось. Тем не менее, следующая итерация алгоритма получила название А2. Годом спустя П. Э. Харт смог достичь оптимальности алгоритма благодаря дополнительным изменениям в эвристической части алгоритма. Так же он смог доказать, что в определенных условиях его версия алгоритма А2 была наиболее эффективной среди алгоритмов поиска маршрута в графе. Эта версия алгоритма была названа А*, где звездочкой были обозначены все прочие итерации алгоритма [14].

Алгоритм А* используется для нахождения кратчайшего пути между двумя любыми вершинами графа, поочередно просматривая все возможные пути в графе, пока не находит наиболее короткий. От других алгоритмов А* отличает то, что при сравнении учитывается весь пройденный до вершины путь (функция g(x) отвечает именно за это). Алгоритм поэтапно просматривает все смежные вершины, двигаясь в сторону пути с наименьшим весом (функция f(x), определяющая общий вес пути). На каждом шаге алгоритм так же обрабатывает все оставшиеся пути до еще не пройденных вершин, помещая их в очередь по приоритету. Этот приоритет определяется общей функцией f(x) = g(x) + h(x), где h(x) – эвристическая составляющая пути. Алгоритм продолжает циклично просматривать все пути в очереди до тех пор, пока не найдет путь с наименьшим значением функции f(x). Этот путь и является искомым кратчайшим путем между двумя вершинами графа.

Последовательность шагов используемого алгоритма показана на рисунке 3.

Рисунок 3 – Основные шаги алгоритма А*

Из множественных решений выбирается решение с наименьшей стоимостью. Чем меньше эвристическая функция h(x), тем больше приоритет. Таким образом, итоговым маршрутом является не первый попавшийся, а самый эффективный.

 ЗАКЛЮЧЕНИЕ

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

ИНС обладает сразу несколькими преимуществами:

• информативность;
• кроссплатформенность;
• навигация с использованием как 2D -, так и 3D - карт

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

Программная реализация системы и используемые решения позволяют системе быстро и эффективно работать на широком спектре платформ и устройств.

В свою очередь использование интерактивных 2D – и 3D – карт помогает легко сориентироваться в зданиях любой сложности.

Разработанная система является универсальным и удобным инструментом, способным быстро и эффективно решить любую задачу, связанную с предоставлением информации касательно здания, в котором применяется ИНС.

 

Литература

1. Шепель В. И., Ергалиев Д. С., Тулегулов А. Д. Сравнительный анализ глобальных навигационных спутниковых систем // Труды Международного симпозиума «Надежность и качество». Том 1. 2012.
2. Камышная Э.Н., Маркелов В.В., Соловьев В.В. Конструкторско-технологические расчеты электронной аппаратуры: Учебное пособие. – М. Изд-во МГТУ им. Н. Э. Баумана, 2014.
3. Андреев К.А., Власов А.И., Камышная Э.Н., Тиняков Ю.Н., Лавров А.В. Автоматизированная пространственная оптимизация компоновки блока управления датчика давления по тепловому критерию // Инженерный журнал: наука и инновации. - 2013. № 6 (18). - С. 51.
4. Камышная Э.Н., Маркелов В.В., Соловьев В.В. Формальное представление электрических принципиальных схем для решения задач автоматизированного проектирования электронной аппаратуры: Учебное пособие. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2011. – 44, [4] с.
5. Применение методов искусственного интеллекта в САПР технологических процессов производства электронной аппаратуры: Учебное пособие / Григорьев В.П., Камышная Э.Н., Нестеров Ю.И., Никитин С.А. - М.: Изд-во МГТУ им. Н.Э. Баумана, 1998. 48 с.
6. Е.М. Парфенов, Э.Н. Камышная, В.П. Усачов. Проектирование конструкций радиоэлектронной аппаратуры: Учеб. Пособие для вузов. - М.: Радио и связь, 1989. – 272 с.
7. Алексеев В.Г., Камышная Э.Н., Усачев В.П. Автоматизированная компоновка схем ЭВА и РЭА по конструктивным модулям первого уровня: Методические указания по курсовому и дипломному проектированию. – М.: Изд-во МВТУ им. Н.Э. Баумана, 1988. – 40 с.
8. Н. Л. Дембицкий, А. В. Назаров. Модели и методы в задачах автоматизированного конструирования радиотехнических устройств - Москва, Изд-во МАИ. 2011. 203 с. Сер. Научная библиотека.
9. Назаров А.В. Оптимизация расстановки элементов печатных модулей методом компактного размещения // Интеграл. 2014. № 4. С. 12-14.
10. Власов А.И., Лыткин С.Л., Яковлев В.Л. Краткое практическое руководство разработчика по языку PL/SQL - Москва, Сер. Библиотечка журнала "Информационные технологии". Том 2. 2000.
11. WebGL [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/WebGL (дата обращения: 10.11.2015).
12. Bellman–Ford algorithm [Электронный ресурс] URL: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm (дата обращения: 10.11.2015).
13. Dijkstra's algorithm [Электронный ресурс] URL: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm (дата обращения: 10.11.2015).
14. A* search algorithm [Электронный ресурс] URL: https://en.wikipedia.org/wiki/A*_search_algorithm (дата обращения: 10.11.2015).
15. Lee algorithm [Электронный ресурс] URL: https://en.wikipedia.org/wiki/Lee_algorithm (дата обращения: 10.11.2015).
16. Johnson's algorithm [Электронный ресурс] URL: https://en.wikipedia.org/wiki/Johnson%27s_algorithm (дата обращения: 10.11.2015).
17. Floyd–Warshall algorithm [Электронный ресурс] URL: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm (дата обращения: 10.11.2015).
18. Дубовик Н. Н., Ногин О. А., Туманов В. М., Лагута А. Е. Исследование проблем 3D навигации в условиях пространственных ограничений // 17-ая международная конференция «Наукоемкие технологии и интеллектуальные системы». Том 2. 2015. [Электронный ресурс] URL: https:// http://iuru/konf/2015_ts/03_tom02.pdf (дата обращения: 10.11.2015).
19. Дубовик Н. Н., Ногин О. А., Туманов В. М. Информационно-навигационная система «ИНС» // Международный инвестиционный форум «WEB – Ready 2015». [Электронный ресурс] URL: https:// web-ready.ru/files/insdoc (дата обращения: 10.11.2015).

References

1. Shepel' V. I., Ergaliev D. S., Tulegulov A. D. Sravnitel'nyj analiz global'nyh navigacionnyh sputnikovyh sistem // Trudy Mezhdunarodnogo simpoziuma «Nadezhnost' i kachestvo». Vol. 1. 2012.
2. Kamyshnaja Je.N., Markelov V.V., Solov'ev V.V. Konstruktorsko-tehnologicheskie raschety jelektronnoj apparatury: Uchebnoe posobie. – M. Izd-vo MGTU im. N. Je. Baumana, 2014.
3. Andreev K.A., Vlasov A.I., Kamyshnaja Je.N., Tinjakov Ju.N., Lavrov A.V. Avtomatizirovannaja prostranstvennaja optimizacija komponovki bloka upravlenija datchika davlenija po teplovomu kriteriju // Inzhenernyj zhurnal: nauka i innovacii. - 2013. № 6 (18). - P. 51.
4. Kamyshnaja Je.N., Markelov V.V., Solov'ev V.V. Formal'noe predstavlenie jelektricheskih principial'nyh shem dlja reshenija zadach avtomatizirovannogo proektirovanija jelektronnoj apparatury: Uchebnoe posobie. – M.: Izd-vo MGTU im. N.Je. Baumana, 2011. – 44, [4] p.
5. Primenenie metodov iskusstvennogo intellekta v SAPR tehnologicheskih processov proizvodstva jelektronnoj apparatury: Uchebnoe posobie / Grigor'ev V.P., Kamyshnaja Je.N., Nesterov Ju.I., Nikitin S.A. - M.: Izd-vo MGTU im. N.Je. Baumana, 1998. 48 p.
6. E.M. Parfenov, Je.N. Kamyshnaja, V.P. Usachov. Proektirovanie konstrukcij radiojelektronnoj apparatury: Ucheb. Posobie dlja vuzov. - M.: Radio i svjaz', 1989. – 272 p.
7. Alekseev V.G., Kamyshnaja Je.N., Usachev V.P. Avtomatizirovannaja komponovka shem JeVA i RJeA po konstruktivnym moduljam pervogo urovnja: Metodicheskie ukazanija po kursovomu i diplomnomu proektirovaniju. – M.: Izd-vo MVTU im. N.Je. Baumana, 1988. – 40 p.
8. N. L. Dembickij, A. V. Nazarov. Modeli i metody v zadachah avtomatizirovannogo konstruirovanija radiotehnicheskih ustrojstv - Moskva, Izd-vo MAI. 2011. 203 p. Nauchnaja biblioteka.
9. Nazarov A.V. Optimizacija rasstanovki jelementov pechatnyh modulej metodom kompaktnogo razmeshhenija // Integral. 2014. № 4. p. 12-14.
10. Vlasov A.I., Lytkin S.L., Jakovlev V.L. Kratkoe prakticheskoe rukovodstvo razrabotchika po jazyku PL/SQL - Moskva, Ser. Bibliotechka zhurnala "Informacionnye tehnologii". Vol. 2. 2000.
11. WebGL [Electronic resource] URL: https://ru.wikipedia.org/wiki/WebGL (accessed: 10.11.2015).
12. Bellman–Ford algorithm [Electronic resource] URL: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm (accessed: 10.11.2015).
13. Dijkstra's algorithm [Electronic resource] URL: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm (accessed: 10.11.2015).
14. A* search algorithm [Electronic resource] URL: https://en.wikipedia.org/wiki/A*_search_algorithm (accessed: 10.11.2015).
15. Lee algorithm [Electronic resource] URL: https://en.wikipedia.org/wiki/Lee_algorithm (accessed: 10.11.2015).
16. Johnson's algorithm [Electronic resource] URL: https://en.wikipedia.org/wiki/Johnson%27s_algorithm (accessed: 10.11.2015).
17. Floyd–Warshall algorithm [Electronic resource] URL: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm (accessed: 10.11.2015).
18. Dubovik N. N., Nogin O. A., Tumanov V. M., Laguta A. E. Issledovanie problem 3D navigacii v uslovijah prostranstvennyh ogranichenij // 17-aja mezhdunarodnaja konferencija «Naukoemkie tehnologii i intellektual'nye sistemy». Vol. 2. 2015. [Electronic resource] URL: https:// http://iu4.ru/konf/2015_ts/03_tom02.pdf (accessed: 10.11.2015).
19. Dubovik N. N., Nogin O. A., Tumanov V. M. Informacionno-navigacionnaja sistema «INS» // Mezhdunarodnyj investicionnyj forum «WEB – Ready 2015». [Electronic resource] URL: https:// web-ready.ru/files/ins_1.doc (accessed: 10.11.2015).