This paper proposes a cognitively motivated approach to interpreting destination descriptions without computing spatial relations. In contrast to other computational approaches, this approach is based on a few assumptions drawn from human communication behavior. Although this cognitively motivated approach is relatively simple, the performance of the approach is almost as good as other computational approaches.
People provide destination descriptions when they specify where to go to.
Destination descriptions are referring expressions [
Although humans have the capability of understanding the spatial relations
in destination descriptions, making sense of spatial relations is not an easy task
for computational systems. The major challenge is interpreting the qualitative
relations frequently used in destination descriptions. Characterizing or
interpreting topological relations, such as in, requires access to the spatial extents of the
involved spatial features. Orientation directions, such as in front of, require size
and shape information. Distance relations, such as near, require taking
contextual factors into account such as the size of the features, the purpose of the
located feature, the distance from the observer, the functional relationship and
interaction between the two features, and the asymmetry from the order in which
locations are retrieved in memory [
Common ground is the basis of joint actions by speakers and listeners [
Research has been made on formalization and computational modeling of
spatial relations. Models for characterizing topological relations exist (e.g., [
If destinations are hard to recognize, ambiguous or lacking in the common
ground, people usually refer to the most salient landmark nearby according to
their knowledge, which is chosen from potentially large numbers of spatial
features available. From the speaker’s perspective, the more salient the landmark
is in the environment, the more likely it is to be known to the listener.
However people perceive the urban environment variously. Petrol stations are more
meaningful, thus salient, to car drivers than to walkers. Therefore it is more
likely that car drivers refer to petrol stations in destination descriptions than
walkers. It appears that the choice of a landmark relies more on its salience than
on the spatial relation between the destination and the addressed landmark.
Furthermore, spatial relations are mental connections, or characterizations of
the configuration of spatial features at particular locations [
By referring to a chosen landmark, the speaker wants to ensure that the listener can figure out the destination effectively and unambiguously. If there are two pizza shops in the neighborhood of the landmark, the speaker has some choices to disambiguate. They can specify the name of the target one, such as “the Pizza Hut next to the petrol station” (i.e., not Domino’s), or employ another landmark to avoid such confusion, like “the pizza shop opposite the church” (which is also next to the petrol station, but does not apply for Domino’s). Or they can name a disambiguating spatial relation, like “the pizza shop left of the petrol station” (instead of the one right of the petrol station). Except for the third case, it can be inferred that in destination descriptions the destination is unique within the neighborhood of the chosen landmark. The third case can be discovered either from inflection (where the relation would be stressed), or from discovering the ambiguities in the interpretation. The third case requires special treatment, but for the other cases we can make our third assumption: – The landmark is chosen because it is sufficient enough to disambiguate the destination.
These assumptions require a computational model of neighborhood. Moulin et
al. advise that the influence area of a spatial feature defines the portion of
neighborhood in which every other features are spatially related to the located
feature in a qualitative way [
The interpretation of a destination description starts with a list of identified
potential destination candidates. In the example above, it would start with a
list of all known pizza shops. If there is no destination (no pizza shop) found
in the database, the interpretation fails, similar to lacking common ground in
human-to-human communication. If there is only one pizza shop found in the
database, the interpretation completes successfully, and the relation to the
landmark can only be used in an affirmative way. But if there are multiple destination
candidates found, then the assumptions above will allow the disambiguation of
destination candidates. This disambiguation process will use only the locations of
landmarks, the salience of landmarks, and the location of destination candidates.
The interpretation process computes a second list, namely a list of landmark
candidates, e.g., all petrol stations. If this list is empty, no common ground could be
established. If exactly one landmark candidate is found, the nearest destination
is considered as a solution. If multiple landmarks are found, their neighborhoods
are computed [
This algorithm discovers automatically the third case – where the spatial relation is used for disambiguation – when no landmark has a unique destination candidate in their neighborhood. In this case the algorithm has to fall back to computing the spatial relations (which is possible, but not addressed in this paper).
This interpretation process offers an approach that avoids in many cases computing of spatial relations. The next section explains by example how this approach works. 4
Angela wants to meet her friend for lunch, and says “let’s meet at the pizza shop next to the 7-Eleven”. The pizza shop is the destination (x), and the 7-Eleven is chosen as the landmark (y). This section demonstrates how the cognitively motivated approach interprets the spatial relation in this destination description, and finds “the pizza shop”. At first it is supposed that the spatial restriction of this communication is known from context (the area shown in Figure 2). In this area three 7-Eleven and three pizza shops are found (Figure 2, left). The 7-Eleven are of similar salience, therefore no hierarchy is created. The neighborhoods of three 7-Eleven are defined by Voronoi cells. In Figure 2, left, the 7-Eleven at the right-bottom corner has no pizza shop in its neighborhood, thus does not define any destination; the 7-Eleven on the top has two pizza shops in its neighborhood, thus destination candidates are found ambiguous; and the 7-Eleven on the left has a unique pizza shop in its neighborhood. Assuming the rules of relevance theory, this pizza shop would be the target destination. Therefore, the hypothesis is proven. This is the general process of the cognitively motivated approach, and the computation complexity is O(n). In comparison, other computational approaches need to compute the spatial relation between each 7-Eleven and pizza shop, and then check whether the relationship is a “next to” relation. If this process identifies any nearest pizza shop to a 7-Eleven, it could omit less relevant pizza shops. Thus the computation complexity is O(n2).
In some cases, the general process cannot obtain a unique result. For example, Angela specifies the name of the pizza shop by saying “let’s meet at the Pizza Hut next to the 7-Eleven”. Figure 2, right, shows a unique Pizza Hut in two 7-Eleven’s neighborhood separately. In this case, the two 7-Eleven (on the top and on the left) are results through this cognitively motivated approach, and further refinement to resolve the remaining ambiguity is needed.
Computational approaches require separate computation algorithms for various types of spatial relations, i.e., topology, orientation, distance relations. As natural language is flexible, categorizing spatial relation in destination descriptions may introduce error. Mismatching between the identified types from descriptions and the preset types in algorithms will also cause failure. This cognitively motivated approach only checks the uniqueness of destination candidates within neighborhood of each landmark candidates, therefore avoids these risks. However the precision of this approach depends on the appropriate definition of landmark neighborhood. Imprecision may also be produced when spatial relations are used to disambiguate destinations. 5
To evaluate the performance of the cognitively motivated approach, a gazetteer
was built, including 36,134 instances. The gazetteer data is based on the point of
interest data from Whereis1 and VicNames data2 over the entire area of Victoria,
Australia. Each instance consists of three essential attributes: the place name,
the category of place, and a geographic location provided by the data sources
[
The only other attribute needed is a salience value. Salience is derived here by
a method suggested by Duckham et al. [
From salience, the influence areas of all instances are computed at all levels
of a salience hierarchy, according to Winter et al. [
After preparing the gazetteer data, we collected 57 destination descriptions given by participants in an interview experiment. Examples of these collected destination descriptions are “Yarra Bend Park near Alphington”, and “Lorne on the Western Coast Road, between Geelong and Apollo Bay, about half way 1 www.whereis.com.au 2 http://services.land.vic.gov.au/vicnames/ between each”. In total, 80 individual places were mentioned in the collection of destination descriptions, including street names, suburb names, names of stations, restaurants, shopping centers, hospitals, clubs, universities, and parks. Besides individual places, there are 15 paraphrased places found in the collection, such as “the library”. In the collected data, there are 38 descriptions (67%) including spatial relations and reference place names.
For this experiment the cognitively motivated approach was implemented to interpret the given destination descriptions. Participants were asked to judge the interpretation results. For comparison, we also developed an approach computing topological, orientation and distance relations. According to their judgement, 27 destination descriptions were interpreted correctly by the cognitively motivated approach, and 28 by the approach computing relations explicitly (the cognitively motivated approach was not allowed to fall back on the explicit computation of relations). The results show that the performance of the cognitively motivated approach is almost as good as the approach with explicit computation of relations. 6
Destination descriptions can use various qualitative spatial relations, thus computing spatial relations can be computationally expensive. This may be one of the reasons why no commercial navigation system has implemented methods for interpreting spatial relations (Google Maps, for example, ignores any given relationship and imposes a ‘near’ relationship on any destination description, of which the semantics remains opaque, of course). Compared to other computational approaches, this cognitively motivated approach is relatively simple, because no computation of individual spatial relation needed.
This paper proposes a cognitively motivated approach to interpreting destination descriptions without computing spatial relations. This approach is based on disambiguating combinations of the multiple destination and landmark candidates found in gazetteers. Given the context, further discussion is needed to retrieve relevant destination candidates and salient landmark candidates from gazetteers. Furthermore, the cognitive adequacy of the construction of the hierarchy of neighborhoods also needs further study.