Research Abstracts - 2007

Overview

I present a system that builds up a knowledge base of spatial information and communicates this information to people in terms that are consistent with their mental maps of a city. Current work in mapping applications and location-based services has focused on finding places of interest based on various search criteria and providing directions to those places. This work addresses a different aspect of these applications — that of presenting location information to people in a manner consistent with their mental map of a city so that they can (1) better understand where places are and (2) more easily integrate these places into their existing mental map. This work supplements the turn-by-turn directions and route maps produced by online mapping services with route overviews. Route overviews are higher-level route descriptions that people often provide when giving directions but that are not available in the detailed turn-by-turn directions offered by services such as MapQuest. In this abstract, I focus on how the system builds up its spatial knowledge base.

The LAIR Spatial Representation

Spatial knowledge is stored in LAIR, a spatial representation that is largely based on design principles from the TOUR model [2] and PLAN [1]. The elements of the LAIR representation have close analogs to those people use to describe their knowledge of the city: there are 0-dimensional places that represent nodes of activity, 1-dimensional paths that link one place to another, 2-dimensional regions that represent a collection of paths and places, and orientation frames that describe which paths are parallel and perpendicular in a particular region.

A novel feature of LAIR is its use of the aforementioned elements to represent and manipulate route knowledge. A route can be represented as a (partially bounded) region with an associated orientation frame. This is a fairly schematized representation of a route, and is similar to hand-drawn route maps in that it simplifies the angles of turns along a route and avoids clutter by including only select features to aid navigation. A set of inference rules uses the qualitative aspects of this representation to generate new spatial relations and create new hierarchical regions when a single piece of spatial information is added to LAIR. These inference rules are triggered when expectations about the relative distance or connectivity between two places are violated. The results of this process can be quite dramatic, and are similar to those "a-ha" moments people experience when learning a new piece of location information causes a significant change in the individual's mental map of the world.

One of the major tenets of this work is that there can be multiple representations of the same space, each at different scales, and possibly conflicting with one another. Since expectations are violated when local features are extrapolated to a global context, when a piece of information that runs contrary to expectations is added to LAIR, instead of maintaining a single global map, the inference rules create another region at a larger (more zoomed-out) scale to account for this global truth not necessary for route navigation at the original scale.

Example

As an example of the sorts of additions that the inference rules can make to the LAIR knowledge base, consider the following example illustrated by the figure below. Figures 1a and 1b show two different regions, each drawn with nominal "North" at the top. In each region, there is a path from Union Square to Harvard Square. Compared to an actual map of the area, shown in Figure 1d, a number of inconsistencies between the two regions becomes apparent. First, Somerville Avenue and Beacon Street are considered parallel in one region but are known to intersect in the other. Second, Oxford and Kirkland/Washington streets appear to be parallel to each other, which, from Figure 1d, is clearly not the case. Third, in Figure 1a, Kirkland/Washington Street is not known to extend from Harvard to Union Square. However, once this fact is introduced to LAIR, the inference rules produce a new region, shown in Figure 1c, that not only reflects the new direct route between Harvard and Union Squares, but also provides a more globally accurate depiction of the relative orientation of the streets and the places they connect.

Figure 1. Figures 1a and 1b show two different, partially overlapping regions. In both, nominal "North" is at the top of the figure. Similar to the simplifications people make in their sketch maps, these qualitative representations of the regions can differ dramatically from an actual map (Figure 1d). However, once LAIR knows that Kirkland/Washington Street extends between Harvard and Union Squares, LAIR creates a new region to accurately capture this and other spatial relationships that were not known before.

References:

[1] Eric Chown, Stephen Kaplan and David Kortenkamp. Prototypes, Location, and Associative Networks (PLAN): Towards a Unified Theory of Cognitive Mapping. In Cognitive Science, vol. 19, no. 1, 1995, pp. 1--51.

[2] Benjamin Jack Kuipers. Representing Knowledge of Large-Scale Space. PhD thesis, Massachusetts Institute of Technology, July 1977. MIT AI/TR 418.