Orientation Calculi and Route Graphs: Towards Semantic Representations for Route Descriptions | SpringerLink
Skip to main content
Springer Nature Link
Log in

Orientation Calculi and Route Graphs: Towards Semantic Representations for Route Descriptions

  • Conference paper
Geographic Information Science (GIScience 2006)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 4197))

Included in the following conference series:

Abstract

We are aiming for semantic representations of route descriptions for dialogues between a driver and the Bremen intelligent wheelchair Spatial Cognition Rolland, integrating qualitative orientation calculi with RouteGraphs. Relative orientations, and the algebraic properties of the inverse and full complement operations, are the basis for specifying properties of orientations between directed edges between locations. 8 orientations at the entry and the exit of an edge are then used to define the relations of variants of the Double-Cross Calculus with 8 and 12 orientations, resp. With an additional predicate “at” a location, we then define all 15 relations. Edges are related to route segments with orientation functions at entries and exits. The inherent origin orientation at a place is then used to solve the place integration problem when joining individual routes into Route Graphs. Finally, some abstract predicates for route descriptions such as “via”, “pass by”, etc., are defined in terms of these calculi.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Allen, J.F.: Maintaining knowledge about temporal intervals. CACM 26(11), 832–843 (1983)

    MATH  Google Scholar 

  2. Astesiano, E., Bidoit, M., Krieg-Brückner, B., Kirchner, H., Mosses, P., Sannella, D., Tarlecki, A. (eds.): CASL - the Common Algebraic Specification Language. Number Special Issue. Springer, Heidelberg (2003)

    Google Scholar 

  3. Cohn, A.G., Bennett, B., Gooday, J., Gotts, N.M.: Qualitative spatial representation and reasoning with the region connection calculus. Ceoinformatics 1, 1–44 (1997)

    Google Scholar 

  4. Denis, M.: The description of routes: A cognitive approach to the production of spatial discourse. Cahiers de Psychologie Cognitive 16, 409–458 (1997)

    Google Scholar 

  5. Fischer, K.: Linguistic methods for investigating concepts in use. Methodologie in der Linguistik (2003)

    Google Scholar 

  6. Frank, A.U.: Qualitative spatial reasoning with cardinal directions. In: Proc. Seventh Austrian Conference on Artificial Intelligence, Springer, Heidelberg (1991)

    Google Scholar 

  7. Freksa, C.: Qualitative spatial reasoning. In: Mark, D.M., Frank, A.U. (eds.) Cognitive and Linguistic Aspects of Geographic Space. Kluwer, Dordrecht (1991)

    Google Scholar 

  8. Freksa, C.: Using orientation information for qualitative spatial reasoning. In: Frank, A.U., Formentini, U., Campari, I. (eds.) GIS 1992. LNCS, vol. 639, pp. 162–178. Springer, Heidelberg (1992)

    Google Scholar 

  9. Group, T.C.L.D., Krieg-Brückner, E., Mosses, E.D.: casl summary. In: Mosses, P.D. (ed.) CASL Reference Manual. LNCS, vol. 2960, pp. 1–69. Springer, Heidelberg (2004)

    Google Scholar 

  10. Krieg-Brückner, B., Frese, U., Lüttich, K., Mandel, C., Mossakowski, T., Ross, R.J.: Specification of route graphs via an ontology. In: Freksa, C., Nebel, B., Krieg-Brückner, B., Knauff, M., Barkowsky, T. (eds.) Spatial Cognition IV. LNCS, vol. 3343, pp. 989–995. Springer, Heidelberg (2005)

    Google Scholar 

  11. Kuipers, B.: The spatial semantic hierarchy. Artificial Intelligence 119, 191–233 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  12. Lankenau, A., Röfer, T.: A safe and versatile mobility assistant. IEEE Robotics and Automation Magazine 1, 29–37 (2001)

    Article  Google Scholar 

  13. Lankenau, A., Röfer, T.: Mobile robot self-localization in large-scale environments. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1359–1364 (2002)

    Google Scholar 

  14. Mandel, C., Huebner, K., Vierhuff, T.: Towards an Autonomous Wheelchair: Cognitive Aspects in Service Robotics. In: Towards Autonomous Robotic Systems (TAROS 2005), Proceedings (to appear, 2005)

    Google Scholar 

  15. Moratz, R., Ragni, M.: Qualitative spatial reasoning about relative point position. Journal of Visual Languages & Computing (to appear, 2006)

    Google Scholar 

  16. Mossakowski, T.: CASL: From semantics to tools. In: Schwartzbach, M.I., Graf, S. (eds.) TACAS 2000. LNCS, vol. 1785, pp. 93–108. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  17. Mossakowski, T.: Heterogeneous tool set (Hets) (2004), Web Site, http://www.informatik.uni-bremen.de/cofi/hets

  18. Mossakowski, T.: Heterogeneous specification and the heterogeneous tool set. Technical report, Universitaet Bremen, Habilitation thesis (2005)

    Google Scholar 

  19. Mosses, P.D. (ed.): CASL Reference Manual. LNCS, vol. 2960. Springer, Heidelberg (2004)

    MATH  Google Scholar 

  20. Mosses, P.D., Bidoit, M.: CASL — the Common Algebraic Specification Language: User Manual. In: Mosses, P.D. (ed.) CASL Reference Manual. LNCS, vol. 2960. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  21. Renz, J., Mitra, D.: Qualitative direction calculi with arbitrary granularity. In: Zhang, C., Guesgen, H.W., Yeap, W.-K. (eds.) PRICAI 2004. LNCS, vol. 3157, pp. 65–74. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  22. Roggenbach, M., Mossakowski, T., Schröder, L.: Libraries. In: Mosses, P. (ed.) CASL Reference Manual [19] Part VI

    Google Scholar 

  23. Schlieder, C.: Anordnung: Eine Fallstudie zur Semantik bildhafter Repräsentation. In: Freksa, C., Habel, C. (eds.) Reprësentation and Verarbeitung räumlichen Wissens, pp. 129–142. Springer, Heidelberg (1990)

    Google Scholar 

  24. Shi, H., Krieg-Brückner, B.: Modelling human route descriptions using qualitative spatial calculi and route graphs (submitted, 2006)

    Google Scholar 

  25. Shi, H., Tenbrink, T.: Telling Rolland where to go: HRI dialogues on route navigation. In: Proc. WoSLaD Workshop on Spatial Language and Dialogue, October 23-25 (2005)

    Google Scholar 

  26. Talmy, L.: How language structures space. In: Pick, H.L., Acredolo, L.P. (eds.) Spatial Orientation: Theory, Research and Application. Plenum, NY (1983)

    Google Scholar 

  27. Timpf, S.: Making sense of space – the legibility of public transport stations. Environment and Planning (submitted)

    Google Scholar 

  28. Tversky, B.: Structures of mental spaces – how people think about space. Environment and Behavior 35(1), 66–80 (2003)

    Article  Google Scholar 

  29. Tversky, B., Lee, P.U.: How space structures language. In: Freksa, C., Habel, C., Wender, K.F. (eds.) Spatial Cognition 1998. LNCS, vol. 1404, pp. 157–175. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  30. Werner, S., Krieg-Brückner, B., Herrmann, T.: Modelling navigational knowledge by route graphs. In: Habel, C., Brauer, W., Freksa, C., Wender, K.F. (eds.) Spatial Cognition 2000. LNCS, vol. 1849, pp. 295–317. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  31. Zimmermann, K., Freksa, C.: Qualitative spatial reasoning using orientation, distance, and path knowledge. Applied Intelligence 6, 49–58 (1996)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universität Bremen and DFKI-Lab Bremen, Germany

    Bernd Krieg-Brückner & Hui Shi

Authors
  1. Bernd Krieg-Brückner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hui Shi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Geography, University of California, Santa Barbara, 5713 Ellison Hall, 93106, Santa Barbara, CA, U.S.A.

    Martin Raubal

  2. University of Utah, 84112-9155, Salt Lake City, UT, USA

    Harvey J. Miller

  3. Vienna University of Technology, 1040, Vienna, Austria

    Andrew U. Frank

  4. University of California, 93106-4060, Santa Barbara, CA, USA

    Michael F. Goodchild

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Krieg-Brückner, B., Shi, H. (2006). Orientation Calculi and Route Graphs: Towards Semantic Representations for Route Descriptions. In: Raubal, M., Miller, H.J., Frank, A.U., Goodchild, M.F. (eds) Geographic Information Science. GIScience 2006. Lecture Notes in Computer Science, vol 4197. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11863939_16

Download citation

  • DOI: https://doi.org/10.1007/11863939_16

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-44526-5

  • Online ISBN: 978-3-540-44528-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation