Reasoning About Large Places

Abstract

To support natural interactive way- nding tasks, computational formalisms of places are needed. In this extended abstract we present the idea of conceptual route graphs, which represent places using decision points, local route graphs and directional relations for modelling places in di erent way- nding situations. The application of formal spatial representations allows formal spatial reasoning about places, in particular deductions with qualitative calculi.

Large Places with Local Route Graphs

Here, we extend the above notions for \small" places, suitable for reasoning about decision points in a network, e.g. in a corridor-like situation, with a framework for \large" places that have a sizable extent, such that, to reach an outgoing from an incoming route segment, one has to \cross" the (supposedly vacuous) place, walk around its perimeter (as for a tra c circle), or do some even more complicated micro-navigation. First, we consider large places which cover a wellde ned area (that constitutes a region in itself) with a border. We classify such large places according to their accessibility (and resulting navigability), e.g.: open the area is an open navigable space, allowing cross-cuts; closed the central area is closed, navigation is only possible around the perimeter (e.g. a tra c circle); complex navigability is more complex (e.g. a tra c circle with an island, such that navigation around the perimeter permits occasional access to the island, which is a nested open space allowing cross-cuts).

In either case we may represent the large place by a local route graph that re nes the place (as seen at a higher level of abstraction) into a route graph with a \higher resolution" for micro-navigation; incoming and outgoing route segments are connected to this local route graph such that it allows a transition from each incoming to every outgoing route segment (this condition has been speci ed for route graph re nements in [ 3 ]).

An open place is represented by a route graph that includes all possible connections of incoming to outgoing segments cutting across the open space; a closed place by a linear route graph representing the perimeter (mono- or bidirectional). The dynamic situation of a person being \in the middle" of an open space can be handled by a (dynamically moving) extra place representing the pose (position and orientation) of this person, with route segments connecting to (incoming and) outgoing segments. 3

Direction Relations for Large Places

As an alternative to route descriptions, human way- nding tasks often specify locations of salient landmarks in an open space. A recent experiment showed that such scene descriptions improve visualization, memorization and way- nding success, in an indoor environment [ 6 ]. Combining route descriptions with location speci cations is required for navigation tasks in an environment containing large places where route graphs do not exist or are less explicit: from an incoming route ending at an exit location in the perimeter of a large place, navigation will be continued using a place description leading to an entry location of an outgoing route segment.

A place description comprises landmarks and directional relations. Since DDC is a model of relations between three points, or between a point and a directed route segment, and does not capture relations between objects with spatial extent, new models are needed for the formal representation of directional relations. For example, Goyal and Egenhofer's direction-relation matrix [ 2 ], Skiadopoulos and Koubarakis' projection based cardinal directional relations [ 7 ], or Kurata and Shi's heterogeneous cardinal direction [ 5 ] are possible models for representing and deducing directional relations between spatial objects. 4

Conclusions

To model places in human or cooperative human-robot way- nding tasks, qualitative maps that integrate route graphs, point-based orientation models and directional models for representing places are needed. Depending on the level of abstraction, a place may be either, a decision point in a route graph, at which reorientation is needed to connect incoming and outgoing route segments; after re nement, a local route graph, which allows a transition from each incoming to every outgoing route segment; or a large open place, where scene descriptions are required to make the local connection.

Extending the conceptual route graph developed in [ 4 ] with directional models for place descriptions poses a new challenge. The focus will be on the connection of two route segments conjoined by a large place represented as a detailed conceptual route graph or modelled via a set of directional relations between spatial objects.

References

1. C. Freksa . Using orientation information for qualitative spatial reasoning . In A. U. Frank, I. Campari , and U. Formentini, editors, Theories and methods of spatio-temporal reasoning in geographic space , volume 639 of LNCS , pages 162 { 178 . Springer, Berlin, 1992 .

2. R. Goyal and M. Egenhofer . Consistent queries over cardinal directions across di erent levels of detail . In 11th International Workshop on Database and Expert Systems Applications , pages 876 { 880 , 2000 .

3. B. Krieg-Bru ckner, U. Frese, K. Luttich, C. Mandel, T. Mossakowski , and R. Ross . Speci cation of an Ontology for Route Graphs . In C. Freksa, M. Knau , B. KriegBruckner, B. Nebel, and T. Barkowsky, editors, Spatial Cognition IV: Reasoning , Action, Interaction. International Conference Spatial Cognition 2004 , Frauenchiemsee, Germany, October 2004 , Proceedings, pages 390 { 412 , Berlin, Heidelberg, 2005 . Springer.

4. B. Krieg-Bruckner and H. Shi . Orientation Calculi and Route Graphs: Towards Semantic Representations for Route Descriptions . In M. Raubal, H. Miller , A. Frank , and M. Goodchild, editors, Geographic Information Science - Fourth International Conference, GIScience 2006, number 4197 in Lecture Notes in Computer Science , pages 234 { 250 . Springer, Berlin, 2006 .

5. Y. Kurata and H. Shi . Toward heterogeneous cardinal direction calculus . In Proceedings of the 32nd Annual German Conference on Arti cal Intelligence , volume 5803 of Lecture Notes in Arti cal Intelligence , 2009 .

6. V. Mast , C. Jian , and D. Zhekova . Elaborate descriptive information in indoor route instructions . In Cognitive Science 2012 , to appear.

7. S. Skiadopoulos and M. Koubarakis . Composing cardinal direction relations . Articial Intelligence , 152 ( 2 ): 143 { 171 , February 2004 .

8. K. Zimmermann and C. Freksa . Qualitative Spatial Reasoning Using Orientation, Distance, and Path Knowledge . Applied Intelligence , 6 ( 1 ): 49 { 58 , 1996 .