автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы построения навигационных описаний маршрутов для картографических компьютерных систем

На правах рукописи

Пестун Максим Вадимович

Методы построения навигационных описаний маршрутов для картографических компьютерных систем

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

5 АБГ 2015

Москва - 2015

005571303

005571303

Работа выполнена в федеральном государственном бюджетном учреждении науки Институте прикладной математики им. М.В. Келдыша Российской академии наук

Научный руководитель: Доктор физико-математических наук, профессор

Галактионов Владимир Александрович, заведующий отделом компьютерной графики и вычислительной оптики Института прикладной математики им. М.В. Келдыша Российской академии наук.

Официальные оппоненты: Доктор технических наук, доцент Карпов Леонид

Евгеньевич, ведущий научный сотрудник Института системного программирования Российской академии наук.

Кандидат физико-математических наук Игнатенко Алексей Викторович, старший научный сотрудник лаборатории компьютерной графики и мультимедиа факультета вычислительной математики и кибернетики Московского государственного университета

им. М.В. Ломоносова.

Ведущая организация: Федеральное государственное автономное

образовательное учреждение высшего

образования "Санкт-Петербургский

национальный исследовательский университет информационных технологий, механики и оптики" (НИУ ИТМО).

Защита состоится 13 октября 2015 г. в 11:00 часов на заседании диссертационного совета Д 002.024.01, созданного на базе ФГБУН Институт прикладной математики им. М.В. Келдыша РАН, расположенного по адресу: 125047 Москва, Миусская пл., д.4.

С диссертацией можно ознакомиться в библиотеке и на сайте ФГБУН Институт прикладной математики им. М.В. Келдыша РАН: www.keldysh.ru.

Автореферат разослан «_££_» ¿^СОа^^_2015 г.

Ученый секретарь

диссертационного совета,

доктор физико-математических наук

Т.А. Полилова

Общая характеристика работы

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

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

«Sin» и «OK Google», представляющие из себя персональных цифровых ассистентов.

Таким образом, можно выделить следующие недостатки существующих картографических навигационных систем:

• карты не подстраиваются под пользователя и не выделяют важную только для него информацию, усложняя тем самым их использование;

• навигационно-картографические системы мало приспособлены для слабовидящих или незрячих пользователей;

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

• существующие методы ввода маршрута в компьютер малофункциональны или отсутствуют;

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

Описание маршрута от точки А до точки Б в удобном для человека виде актуально в следующих задачах:

• навигация внутри зданий со сложной планировкой;

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

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

• навигация в городском окружении;

• Использование навигационных систем (например, автомобильного навигатора) частично решает проблему поиска нужного места в сложной системе дорог, однако их рекомендации не всегда бывают удобны для водителя, из-за чего ему требуется отвлекаться от дороги на монитор устройства с изображением карты и нарисованной поверх нее траектории движения. Инструкция «поверните налево через 712 метров» может быть оформлена в более удобном виде: «поверните налево на втором светофоре».

• указание компьютеру о следовании по специальному маршруту;

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

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

• взаимодействие с роботизированными системами в области описания маршрута;

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

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

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

• исследовать и провести анализ существующих навигационно-картографических решений;

• исследовать существующие методы построения описания (вывода) маршрута; разработать алгоритм построения текстового описания маршрута в удобной для человека форме;

• исследовать существующие методы задания (ввода) маршрута в компьютер; разработать алгоритм преобразования текстового описания маршрута в удобное для обработки компьютером представление;

• разработать компьютерную систему, спроектировав ее архитектуру, реализующую данные алгоритмы.

Научная новизна. Получены следующие новые результаты в области передачи навигационной информации:

• на основе проведенного исследования методов ввода и вывода маршрута разработаны и реализованы новые алгоритмы построения и распознавания персонализированного когнитивного текстового описания маршрута, упрощающие использование навигационных систем;

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

• предложена методика проверки качества предлагаемых текстовых описаний и их удобства для человека на основе статистики использования и анкетирования, выявляющая объективное мнение пользователей;

• на основе разработанных методов и алгоритмов реализована программная компонента, интегрируемая в существующие

картографические системы и используемая в реальных практических приложениях.

Рис. 1: Летающий робот (квадрокоптер), перемещающийся по маршруту, описанному пользователем

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

• в созданной автором навигационной системе Интранета высотного офисного здания SkyLight (Ленинградский проспект, д. 39) — любой сотрудник, работающий в данном здании, имеет возможность получить подробную инструкцию, как добраться до рабочего места интересующего его человека, просмотрев информацию о нем в персональном профиле на корпоративном портале; обычные методы навигации (указатели, надписи) работали плохо ввиду сложного зеркального по четырем направлениям расположения рабочих мест (используется методика рассадки open-space);

• в картографической системе Карты Mail.Ru для предоставления описания маршрута пользователю в удобном персонализированном виде;

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

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях и семинарах:

1. Международная Конференции по Компьютерной Графике и Зрению GraphiCon'2012 (Москва, факультет ВМК МГУ).

2. Международная Конференции по Компьютерной Графике и Зрению GraphiCon'2014 (Ростов-на-Дону, ЮФУ).

3. Научно-практический семинар «Новые информационные технологии в автоматизированных системах» 2014 года (Москва, НИУ ВШЭ).

4. Научно-практический семинар «Новые информационные технологии в автоматизированных системах» 2015 года (Москва, НИУ ВШЭ).

5. Семинар направления "Программирование" им. М. Р. Шура-Бура в ИПМ им. М. В. Келдыша РАН.

Публикации. По результатам работы имеются 8 публикаций [1-8], из них 2 опубликованы в рецензируемых журналах Перечня ВАК [6, 8], 1 публикация входит в библиографические базы Web Of Science и Scopus [1].

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения и списка литературы. Общий объем диссертации составляет 111 страниц, из них — 97 страниц основного текста, включая 35 рисунков. Библиография включает 78 наименований.

Содержание работы

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

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

• методы построения описания маршрута:

• пошаговая инструкция;

• изображение траектории;

• методы распознавания описания маршрута:

• ввод опорных точек маршрута путем их расстановки мышкой на стационарном компьютере; между ними маршрут прокладывается автоматически;

• ввод точек транзита путем задания их конкретных координат или имени POI (от англ. Point Of Interest — точки интереса: здания, улицы, предприятия, магазины, парки и т.д.).

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

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

• текстовое представление может быть отображено на любом экране (черно-белом, цветном и даже только текстовом);

• текстовое представление поддается легкому вводу в устройство с учетом развития технологий распознавания речи и персональных ассистентов, таких как Siri и Google Now, работающих исключительно на голосовых командах;

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

Выводы об удобстве использования человеком текстового описания маршрута были получены на основе проведенных исследований [1, 2, 5, 6] совместно с факультетом психологии МГУ им. М.В. Ломоносова с

использованием специальной системы построения виртуальной реальности CAVE (рис. 2).

Рис. 2: Схематическое представление системы построения виртуальной

реальности CAVE

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

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

которым он часто перемещается и может идентифицировать по заданному названию);

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

3. группировка интервалов по однотипным навигационным директивам (навигационные директивы - это команды к перемещению вида «повернуть налево», «двигаться прямо», «развернуться»);

4. формирование каркаса результата (рис. 3) из лексем (под каркасом понимается представление итогового текстового описания в абстрагированном от естественного языка виде);

5. склонение названий и интеграция их в каркас;

6. замена оставшихся лексем по словарю;

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

8. формирование результирующего текстового описания в формате HTML с изображениями и с визуальным форматированием.

{ACTION} -{DIRECTION} "{DISTANCE}, • {JUNK} •{TURN_LEFT}, •{JUNK} "{ACTION} • {GRCUP_DIR£CTICN} ■ {GRCUP_DISTANCE) "{TILL} "{POI_NAME}, "{JUNK} ■ {KNOKN_ACTION} " {KN0KN_NA>1E}, "{JUNK} "{ACTION} ■ {GROUP_DIRECTION} • {GRCUP_DISTANCE}"{TILL}"{POI_NAME}Л

Рис. 3: Пример построенного каркаса (промежуточного представления) будущего текстового описания маршрута

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

• полные и упрощенные названия POI, используемые в прямой речи;

• словесное описание внешнего вида POI;

• склонения названий POI ({POI_NAME});

• знакомые пользователю интервалы пути ({KNOWN_NAME});

• директивы к перемещению ({ACTION}, {DIRECTION});

• упрощенные округленные расстояния ({GROUP_DISTANCE});

• группы однотипных действий ({GROUPDIRECTION});

• предлоги, союзы, знаки препинания ({TILL}, «,», «.»);

• «мусорные» слова, придающие тексту «человечности» ({JUNK}).

упрощенные названия POI. используемые в прямой речи

полные и

группы

ОДНОТИПНЫХ

действий

сповестное описание внешнего вида POI

"мусорные" снова придающие тексту

человечности

склонения названий POI

предлоги, союзы знаки препинания

директивы к перемещению

упрощенные округленные расстояния

Рис. 4: Составные части текстового описания пути, используемые алгоритмом

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

Все описание разбивается на блоки PB = {ACTION TYPE, DIRECTION, RELATIVITY NEAR, POI_NAME_NEAR, DISTANCE, RELATIVITY TILL, POINAMETILL} (важно сразу отметить, что не все поля пятерок PB будут использованы в итоговом сформированном текстовом описании):

• ACTION TYPE — вид действия, это может быть «проходите», «проезжайте», «двигайтесь», «поверните», «развернитесь» и так далее;

• DIRECTION — направление движения, это может быть «прямо», «мимо», «налево», «направо» и так далее;

• RELATIVITY NEAR — относительность действия к POI, это может быть «у», «мимо», «рядом» и так далее;

• POI NAME NEAR — название POI, рядом с которым происходит действие, связанное с RELATIVITY NEAR;

• DISTANCE — расстояние, которое необходимо преодолеть, это может быть «полкилометра», «четверть километра», «пара километров», «сразу» и так далее;

• RELATIVITY TILL — относительность действия к POI, это может быть «до», «вплоть» и так далее;

• POI_NAME_TILL — название POI, рядом с которым происходит действие, связанное с RELATIVITY TILL.

Далее алгоритм разбивает PB на предложения, для чего используются следующие правила:

• в одном предложении может быть минимум один и максимум три блока PB:

• один блок РВ может быть только в конечном предложении и только в том случае, если к нему не может быть добавлен другой блок РВ;

• в остальных случаях используется два или три блока РВ;

• вероятность появления трех блоков РВ определяется значением наперед заданной константы Ч^.

• в случаях, когда два последовательных блока РВ содержат одинаковые значения ACTIONTYPE, они могут быть сгруппированы в один; вероятность определяется наперед заданной константой IS.

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

• 4*1 — вероятность предложения из трех блоков РВ;

• Ч^ — вероятность группировки двух блоков РВ в один.

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

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

• для ACTION TYPE-. «снова», «и опять», «еще раз» и другие;

• для DIRECTION: «в ту же сторону» и другие;

• для DISTANCE', «столько же», «такое же расстояние» и другие.

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

Рис. 5: Пример перевода изображения траектории пути в текстовое представление с использованием знакомых пользователю маршрутов и POI

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

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

В заключении сформулированы основные результаты работы.

Основные результаты

Основные результаты работы:

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

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

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

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

Список публикаций

1. G. Menshikova, Yu. Bayakovski, E. Luniakova, M. Pestun, D. Zakharkin, Virtual Reality Technology for the Visual Perception Study, Springer //Transactions on Computational Science XIX, Lecture Notes in Computer Science Volume 7870. - Germany, 2013. P. 107-116.

2. G. Menshikova, Yu. Bayakovski, E. Luniakova, M. Pestun, D. Zakharkin, Virtual reality technology for the visual perception study //The 22nd International Conference on Computer Graphics and Vision (GraphiCon'2012). - Moscow, Russia, 2012. P. 51.

3. M.B. Пестун, Компьютерная система описания маршрута в удобном для человека формате //Научно-практический семинар "Новые информационные технологии в автоматизированных системах". - М„ Россия, 2014. С. 125-134.

4. М.В. Пестун, Методы преобразования текстового описания маршрута в компьютерное представление //Научно-практический семинар "Новые информационные технологии в автоматизированных системах". - М., 2015. С. 510-517.

5. A. Tetereva, M. Pestun, G. Menshikova, Effect of negative emotions on the cognitive maps acquisition //Proc. of 37 th European Conference on Visual Perception. - Perception, v.43, ECVP Abstract

supplement. - Belgrad, Serbia, 2014. P. 140.

6. Г.Я. Меньшикова, Ю.М. Баяковский, Е.Г. Лунякова, М.В. Пестун, Д.В. Захаркин, Эффект артикуляции в трехмерных зрительных иллюзиях //Экспериментальная психология. - М.: ГБОУ ВПО «Московский городской психолого-педагогический университет», 2013, №2. С. 46-57.

7. М.В. Пестун, Алгоритмы построения и хранения навигационной когнитивной карты для взаимодействия с человеком //Материалы конференции GraphiCon 2014. - Ростов н/Д, 2014. С. 119-122.

8. М.В. Пестун. Когнитивная навигация и алгоритм построения текстового описания маршрута в удобном для человека виде //Программные продукты и системы /Гл. ред. академик РАН C.B. Емельянов. - Тверь: Научно-исследовательский институт «Центрпрограммсистем», 2015. С. 28-33.

Подписано в печать 25.06.2015. Формат 60x84/16. Усл. печ. л. 1,2. Тираж 70 экз. Заказ А-4. ИПМ им. М.В. Келдыша РАН. 125047, Москва, Миусская пл., 4