Software & Systems

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

Рассматриваемый в данной статье алгоритм может быть использован на мобильном устройстве, оснащенном системой глобального позиционирования (GPS, ГЛОНАСС), что позволит увеличить фактор персонализации за счет получения информации о наиболее часто используемых пользователем маршрутах (из предположения, что со временем они становятся для него хорошо знакомыми) [1].

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

Когнитивная карта и навигация

Когнитивная карта – образ знакомого пространственного окружения. Навигация – процесс управления некоторым объектом в определенном пространстве передвижения. Подзадачами навигации являются маршрутизация, выбор оптимального пути следования объекта в пространстве.

Человек строит когнитивную карту в своем сознании при перемещении в пространстве, со временем карта дополняется и уточняется [2]. Обычно выделяют две основные системы координат: аллоцентрическую и эгоцентрическую. Карта, представляющая собой местность с объектами в абсолютных координатах, не принимающая в расчет местоположение человека, называется аллоцентрической. Если положение человека влияет на текущее представление карты, она называется эгоцентрической. Иногда выделяют третий вариант – геоцентрический [3], представляющий собой смесь аллоцентрической и эгоцентрической систем с установленным направлением гравитации.

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

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

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

Проблема описания маршрута актуальна и на сегодняшний день недостаточно исследована.

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

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

Человек объясняет маршрут (вариант 1):

1)    стоишь у библиотеки им. Ленина;

2)    поворачиваешься к Кремлю;

3)    идешь прямо до Манежа;

4)    далее поворачиваешь налево и идешь полкилометра до входа в Охотный ряд;

5)    здесь место встречи.

Навигатор объясняет маршрут (вариант 2, основан на результатах Google Maps):

1)    старт: ул. Воздвиженка‎;

2)    следуйте на восток по ул. Воздвиженка в сторону ул. Моховая (идти 130 м);

3)    резкий поворот налево на ул. Моховая (идти 600 м);

4)    поверните направо на пл. Манежная (идти 40 м);

5)    финиш: пл. Манежная‎.

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

Актуальность применения описания маршрута в удобном для человека виде

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

·       Навигация внутри зданий со сложной планировкой.

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

·       Навигация в городском окружении.

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

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

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

Пример работы алгоритма

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

Помимо этого, текстовое описание дополняется изображениями используемых POI с того ракурса, с которого их увидит пользователь, и подробным текстовым описанием внешнего вида совместно с официальным названием (рис. 2).

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

Персонализация информации

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

–      отслеживаются промежутки времени, при которых телефон был относительно неподвижен (остановки более чем на 30 минут);

–      отслеживаются быстрые (движение на автомобиле или в общественном транспорте) и медленные (перемещение пешком при скорости менее 20 км/ч) изменения координат;

–      при остановках возможно дополнительное уточнение у пользователя, какое конкретно место (заведение, фирму, магазин) он посещает (аналогично сделано в социальной сети «foursquare»).

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

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

–      частота перемещений по конкретному маршруту или его участку;

–      частота посещения различных мест;

–      эмоциональное отношение пользователя к конкретному участку дороги и/или к месту.

Все три перечисленных пункта позволяют более точно персонализировать карту, сделав ее максимально удобной для использования. При прокладывании маршрута будут использоваться статистические частотные данные, позволяющие проложить маршрут, наиболее знакомый пользователю, несмотря на возможную меньшую оптимальность траектории пути (из предположения, что маршрут, которым человек чаще пользуется, может быть описан менее детально, нежели новый, неизвестный) [7]. Вводимое пользователем в ручном режиме эмоциональное отношение к участкам пути и/или к конкретным объектам на нем дает возможность создать такой вариант маршрута, который будет казаться ему более коротким и оптимальным [6, 8, 9] (основано на подтвержденных исследованиях в системе виртуальной реальности CAVE, проводимых факультетом психологии МГУ им. М.В. Ломоносова [10]).

Описание алгоритма и программная реализация

Алгоритм реализован на языке программирования JavaScript, работает на базе любого современного веб-браузера. При его реализации использовались библиотеки jQuery (для сокращения кода и поддержки кроссбраузерности) и Google Maps JavaScript API v3 (для получения картографических, навигационных и информационных данных o POI), функционал HTML5 (для отображения результата, отслеживания местоположения пользователя и хранения локальных данных). Приложение, содержащее алгоритм, работает только на клиентской стороне, запрашивая необходимые данные с картографического сервиса. Серверная часть отсутствует из-за ее ненадобности ввиду сильного развития клиентских технологий.

Архитектура

Программа алгоритма состоит из следующих функциональных частей.

·       Хранилище персональных данных и дополнительная картографическая информация об объектах. Является структурой данных со следующими полями:

ID – идентификатор записи;

PLACE_ID – идентификатор места на карте, используемой картографической системой (в данном случае идентификатор из Google Maps), является обычно HEX-строкой;

LAT_LNG – структура данных, хранящая долготу и широту местоположения объекта;

NAME – название объекта, если оно применимо (имя учреждения, магазина и т.д.);

VISUAL_DESCRIPTION – визуальное описание объекта, прочитав которое, пользователь может понять, о каком объекте идет речь, когда встретит его на пути;

SHORT_DESCRIPTION – короткое описание, используемое непосредственно в текстовом описании маршрута для сокращения длины и в случае отсутствия имени у объекта;

COMMON_POPULARITY – значение популярности данного объекта исходя из общего мнения (обычно оценка от 1 до 10 в звездочках);

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

ATTRIBUTES – атрибуты объекта: PASS_ THROUGH (объект стоит на дороге, и сквозь него можно пройти, например арка), NON_REACHA­BLE (объект, который может служить ориентиром, но до которого нельзя добраться обычным способом, например маяк на реке).

·       Хранилище знакомых маршрутов. Является набором массивов географических координат, описывающих ломаные линии маршрутов, по которым когда-либо перемещался пользователь. Каждый маршрут имеет счетчик количества его прохождений USAGE_COUNTER. Один маршрут отделяется от другого продолжительной паузой, означающей остановку в движении пользователя. Равенство маршрутов проверяется при помощи расчета суммарного отклонения ломаной линии одного маршрута от ломаной линии другого. Для каждого маршрута можно задать его имя ROUTE_ NANE и описание ROUTE_DESCRIPTION, которые будет использовать алгоритм.

·       Словарь навигационных терминов. Это набор слов на родном языке пользователя совместно с набором синонимов:

FORWARD (например «вперед»);

BACKWARD (например «назад»);

LEFT (например «налево»);

RIGHT (например «направо»);

UTURN (например «развернуться»);

TILL (например «до»);

THROUGHT (например «сквозь»);

WALK (например «идти»).

·       Словарь дополнительных терминов. Это слова, которые придают навигационному тексту подобие человеческой речи, призванные упростить восприятие и облегчить запоминание. Используются случайным образом при составлении описания. Количество слов может быть любым, например, в текущей реализации используются «далее», «затем», «после этого», «потом».

·       Интерфейс для взаимодействия с картографическим сервисом. Может использоваться любая картографическая система, реализующая следующий функционал:

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

–      принимает на вход географические координаты объекта и точки обзора, возвращает графическое изображение объекта с данной точки.

·       Алгоритм преобразования навигационной информации в текстовое описание (подробнее далее), удобное для человека. Это основной алгоритм, состоящий из следующих шагов:

–      получение на вход точек начала и окончания маршрута;

–      получение от картографического сервиса ломаной линии проложенного маршрута;

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

–      формирование HTML-кода результата.

Алгоритм преобразования навигационной информации в текстовое описание

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

·       Ломаная линия маршрута разделяется на массив STEP (шаги пути из относительно прямолинейных участков, обычно эту информацию предоставляет картографический сервис). У каждого элемента STEP есть следующий набор полей:

LAT_LNG – структура, хранящая географические координаты начала и конца «шага»;

LENGTH – длина «шага» в метрах;

KNOWN_PATH_ID – переменная для хранения идентификатора знакомого маршрута, если данный STEP совпадает с ним.

·       Для каждого STEP определяется его наличие в хранилище знакомых пользователю маршрутов, и в случае полного совпадения идентификатор найденного пути записывается в KNOWN_ PATH_ID.

·       Для всех остальных STEP определяются близлежащие к его окончанию POI и выбирается обладающий наибольшим общим значением, исходя из набора характеристик:

–      степень его популярности для пользователя PRIVATE_POPULARITY;

–      степень его популярности в целом COMMON_POPULARITY;

–      расстояние до него от конца STEP.

·       Для каждого POI формируется ссылка на его изображение в картографическом сервисе с места, с которого его увидит пользователь, для этого на ломаной линии STEP выбирается наиближайшая точка обзора к POI, расположенная по линии следования до POI, и на основе координат выбранной точки обзора и POI строится URL-ссылка на требуемое изображение.

·       Далее для всех STEP, не найденных в хранилище известных пользователю маршрутов, находятся все POI c атрибутом PASS_THROUGH.

·       Результирующим шагом является построение текстового описания. Каждый STEP описывается отдельно, формирование осуществляется с конца:

–      все STEP и найденные маршруты последовательно формируются в предложение;

–      POI с атрибутом PASS_THROUGH используются с навигационным термином THROUGH;

–      все остальные POI используются с термином TILL;

–      все POI имеют приписанный глагол WALK;

–      стыковки разных STEP осуществляются при помощи терминов LEFT/RIGHT/UTURN;

–      описание знакомых пользователю STEP заменяется соответствующим именем, указанным ранее пользователем, если это возможно;

–      для каждого POI используется соответствующий ему SHORT_DESCRIPTION;

–      добавляются дополнительные термины.

Пример практического применения

Описанный выше алгоритм построения текстового описания был применен на практике для навигации внутри высотного офисного здания «Sky­Light» в Москве.

Система когнитивной навигации интегрирована в корпоративный портал. Любой сотрудник может найти другого сотрудника в адресной книге, просмотреть его личную карточку, узнать место его посадки, а также получить краткую и легкую для запоминания инструкцию «как пройти» к нему (рис. 4).

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

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

Литература

1.     Tetereva A., Pestun M., and Menshikova G. Effect of ne­gative emotions on the cognitive maps acquisition. Proc. of 37th European Conf. on Visual Perception. Belgrad, Serbia, 2014, p. 140.

2.     Yeap W.K., Jefferies M.E. On early cognitive mapping. Spatial Cognition and Computation. Netherlands: Kluwer Academic Publ. 2000, vol. 2 (2), pp. 85–116.

3.     Paillard J. The motor determinants of spatial organization. Cahiers de Psychologie, 1971, vol. 14, pp. 261–316.

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

5.     Cousins J.H., Siegel A.W., and Maxwell S.E. Way-Finding And Cognitive Mapping in Large-Scale Environments: A Test of a Developmental Model. Journ. of Experimental Child Psychology. 1983, no. 35, pp. 1–20.

6.     Allen G.L., Kirasic K.C., Siegel A.W., and Herman J.F. Development Issues in Cognitive Mapping: The Selection and Utilization of Environmental Landmarks. Child Development, 1979, no. 50, pp. 1062–1070.

7.     Loomis J.M., Klatzky R.L., and Colledge R.G. Human navigation by path integration. Wayfinding: Cognitive mapping and spatial behavior, 1999.

8.     Klatzky R.L., Freksa C., Habel C., and Wender K.F. Allocentric and Egocentric Spatial Representations: Definitions, Distinctions, and Interconnections. Artificial Intelligence (Eds.), Springer, 1997, vol. 1404, pp. 1–17.

9.     Klatzky R.L., Loomis J.M., Golledge R.G., Cicinelli J.G., Doherty S., and Pellegrino J.W. Acquisition of route and survey knowledge in the absence of vision. Journ. of Motor Behavior, 1990, no. 22, pp. 19–43.

10.  Lakhtionova I., Menshikova G. The method of testing the ability of allocentric cognitive maps acquisition. Proc. of 36th European Conf. on Visual Perception, Bremen, Germany, 2013, p. 53.

11.  Пестун М.В. Компьютерная система описания маршрута в удобном для человека формате // Новые информационные технологии в автоматизированных системах: науч.-практич. сем. М., 2014. С. 125–134.