Skip to main content
Top

2015 | OriginalPaper | Chapter

Learning Spatial Models for Navigation

Authors : Susan L. Epstein, Anoop Aroor, Matthew Evanusa, Elizabeth I. Sklar, Simon Parsons

Published in: Spatial Information Theory

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Typically, autonomous robot navigation relies on a detailed, accurate map. The associated representations, however, do not readily support human-friendly interaction. The approach reported here offers an alternative: navigation with a spatial model and commonsense qualitative spatial reasoning. Both are based on research about how people experience and represent space. The spatial model quickly develops as the result of incremental learning while the robot moves through its environment. In extensive empirical testing, qualitative spatial reasoning principles that reference this model support increasingly effective navigation in a variety of built spaces.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Arkin, R.C.: Integrating behavioral, perceptual, and world knowledge in reactive navigation. Robot. Auton. Syst. 6, 105–122 (1990)CrossRef Arkin, R.C.: Integrating behavioral, perceptual, and world knowledge in reactive navigation. Robot. Auton. Syst. 6, 105–122 (1990)CrossRef
2.
go back to reference Bailey, T., Durrant-Whyte, H.: Simultaneous localization and mapping: part II. IEEE Robot. Autom. Mag. 13(3), 108–117 (2006)CrossRef Bailey, T., Durrant-Whyte, H.: Simultaneous localization and mapping: part II. IEEE Robot. Autom. Mag. 13(3), 108–117 (2006)CrossRef
3.
go back to reference Björnsson, Y., Halldórsson, K.: Improved heuristics for optimal path-finding on game maps. In: Laird, J., Schaeffer, J. (eds.) AIIDE 2006, pp. 9–14. AAAI, Marina del Rey (2006) Björnsson, Y., Halldórsson, K.: Improved heuristics for optimal path-finding on game maps. In: Laird, J., Schaeffer, J. (eds.) AIIDE 2006, pp. 9–14. AAAI, Marina del Rey (2006)
4.
go back to reference Botea, A., Harabor, D.: Path planning with compressed all-pairs shortest paths data. In: Borrajo, D., Fratini, S., Kambhampati, S., Oddi, A. (eds.) ICAPS-2013, pp. 288–292. AAAI, Rome (2013) Botea, A., Harabor, D.: Path planning with compressed all-pairs shortest paths data. In: Borrajo, D., Fratini, S., Kambhampati, S., Oddi, A. (eds.) ICAPS-2013, pp. 288–292. AAAI, Rome (2013)
5.
go back to reference Brooks, R.A.: Intelligence without representation. Artif. Intell. 47(1–3), 139–160 (1991)CrossRef Brooks, R.A.: Intelligence without representation. Artif. Intell. 47(1–3), 139–160 (1991)CrossRef
6.
go back to reference Durrant-Whyte, H., Bailey, T.: Simultaneous localization and mapping: part I. IEEE Robot. Autom. Mag. 13(2), 99–110 (2006)CrossRef Durrant-Whyte, H., Bailey, T.: Simultaneous localization and mapping: part I. IEEE Robot. Autom. Mag. 13(2), 99–110 (2006)CrossRef
7.
go back to reference Epstein, S.L.: For the right reasons: the FORR architecture for learning in a skill domain. Cogn. Sci. 18(3), 479–511 (1994)CrossRef Epstein, S.L.: For the right reasons: the FORR architecture for learning in a skill domain. Cogn. Sci. 18(3), 479–511 (1994)CrossRef
8.
go back to reference Epstein, S.L.: Spatial representation for pragmatic navigation. In: Hirtle, S.C., Frank, A.U. (eds.) COSIT 1997. LNCS, vol. 1329, pp. 373–388. Springer, Heidelberg (1997) CrossRef Epstein, S.L.: Spatial representation for pragmatic navigation. In: Hirtle, S.C., Frank, A.U. (eds.) COSIT 1997. LNCS, vol. 1329, pp. 373–388. Springer, Heidelberg (1997) CrossRef
9.
go back to reference Epstein, S.L.: Pragmatic navigation: reactivity, heuristics, and search. Artif. Intell. 100(1–2), 275–322 (1998)CrossRefMATH Epstein, S.L.: Pragmatic navigation: reactivity, heuristics, and search. Artif. Intell. 100(1–2), 275–322 (1998)CrossRefMATH
10.
go back to reference Epstein, S., Schneider, E., Ozgelen, A.T., Munoz, J.P., Costantino, M., Sklar, E.I., Parsons, S.: Applying FORR to human/multi-robot teams. In: Human-Agent-Robot Teamwork Workshop at 7th ACM/IEEE International Conference on Human-Robot Interaction (2012) Epstein, S., Schneider, E., Ozgelen, A.T., Munoz, J.P., Costantino, M., Sklar, E.I., Parsons, S.: Applying FORR to human/multi-robot teams. In: Human-Agent-Robot Teamwork Workshop at 7th ACM/IEEE International Conference on Human-Robot Interaction (2012)
11.
go back to reference Frommberger, L., Wolter, D.: Spatial abstraction: aspectualization, coarsening, and conceptual classification. In: Freksa, C., Newcombe, N.S., Gärdenfors, P., Wölfl, S. (eds.) Spatial Cognition VI. LNCS (LNAI), vol. 5248, pp. 311–327. Springer, Heidelberg (2008) Frommberger, L., Wolter, D.: Spatial abstraction: aspectualization, coarsening, and conceptual classification. In: Freksa, C., Newcombe, N.S., Gärdenfors, P., Wölfl, S. (eds.) Spatial Cognition VI. LNCS (LNAI), vol. 5248, pp. 311–327. Springer, Heidelberg (2008)
12.
go back to reference Gat, E.: On three-layer architectures. In: Kortenkamp, D., Bonnasso, R.P., Murphy, R. (eds.) Artificial Intelligence and Mobile Robots. AAAI Press, Cambridge (1998) Gat, E.: On three-layer architectures. In: Kortenkamp, D., Bonnasso, R.P., Murphy, R. (eds.) Artificial Intelligence and Mobile Robots. AAAI Press, Cambridge (1998)
13.
go back to reference Gerkey, B., Vaughan, R., Howard, A.: The player/stage project: tools for multi-robot and distributed sensor systems. In: The International Conference on Advanced Robotics, pp. 317–323 (2003) Gerkey, B., Vaughan, R., Howard, A.: The player/stage project: tools for multi-robot and distributed sensor systems. In: The International Conference on Advanced Robotics, pp. 317–323 (2003)
14.
go back to reference Gibson, J.J.: The theory of affordances. In: Shaw, R., Bransford, J. (eds.) Perceiving, Acting, and Knowing: Toward an Ecological Psychology, pp. 67–82. Lawrence Erlbaum, Mahwah (1977) Gibson, J.J.: The theory of affordances. In: Shaw, R., Bransford, J. (eds.) Perceiving, Acting, and Knowing: Toward an Ecological Psychology, pp. 67–82. Lawrence Erlbaum, Mahwah (1977)
15.
go back to reference Golledge, R.G.: Path selection and route preference in human navigation: a progress report. In: Kuhn, W., Frank, A.U. (eds.) COSIT 1995. LNCS, vol. 988. Springer, Heidelberg (1995) Golledge, R.G.: Path selection and route preference in human navigation: a progress report. In: Kuhn, W., Frank, A.U. (eds.) COSIT 1995. LNCS, vol. 988. Springer, Heidelberg (1995)
16.
go back to reference Golledge, R.G.: Human wayfinding and cognitive maps. In: Golledge, R.G. (ed.) Wayfinding Behavior, pp. 5–45. Hopkins University Press, Baltimore (1999) Golledge, R.G.: Human wayfinding and cognitive maps. In: Golledge, R.G. (ed.) Wayfinding Behavior, pp. 5–45. Hopkins University Press, Baltimore (1999)
17.
go back to reference Hamburger, K., Dienelt, L.E., Strickrodt, M., Röser, F.: Spatial cognition: the return path. In: Knauff, M., Pauen, M., Sebanz, N., Wachsmuth, I. (eds.) Cognitive Science 2013, pp. 537–542. Cognitive Science Society, Austin (2013) Hamburger, K., Dienelt, L.E., Strickrodt, M., Röser, F.: Spatial cognition: the return path. In: Knauff, M., Pauen, M., Sebanz, N., Wachsmuth, I. (eds.) Cognitive Science 2013, pp. 537–542. Cognitive Science Society, Austin (2013)
18.
go back to reference Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. SSC4 4(2), 100–107 (1968)CrossRef Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. SSC4 4(2), 100–107 (1968)CrossRef
19.
go back to reference Hölscher, C., Tenbrink, T., Wiener, J.M.: Would you follow your own route description? cognitive strategies in urban route planning. Cognition 121, 228–247 (2011)CrossRef Hölscher, C., Tenbrink, T., Wiener, J.M.: Would you follow your own route description? cognitive strategies in urban route planning. Cognition 121, 228–247 (2011)CrossRef
20.
go back to reference Jonietz, D., Timpf, S.: An affordance-based simulation framework for assessing spatial suitability. In: Tenbrink, T., Stell, J., Galton, A., Wood, Z. (eds.) COSIT 2013. LNCS, vol. 8116, pp. 169–184. Springer, Heidelberg (2013) CrossRef Jonietz, D., Timpf, S.: An affordance-based simulation framework for assessing spatial suitability. In: Tenbrink, T., Stell, J., Galton, A., Wood, Z. (eds.) COSIT 2013. LNCS, vol. 8116, pp. 169–184. Springer, Heidelberg (2013) CrossRef
21.
go back to reference Joshi, S., Schermerhorn, P., Khardon, R., Scheutz, M.: Abstract planning for reactive robots. In: Parker, L.E. (ed.) ICRA 2012, pp. 4379–4384. IEEE, Saint Paul (2012) Joshi, S., Schermerhorn, P., Khardon, R., Scheutz, M.: Abstract planning for reactive robots. In: Parker, L.E. (ed.) ICRA 2012, pp. 4379–4384. IEEE, Saint Paul (2012)
23.
go back to reference Kostavelis, I., Gasteratos, A.: Semantic mapping for mobile robotics tasks: a survey. Robot. Auton. Syst. 66, 86–103 (2015)CrossRef Kostavelis, I., Gasteratos, A.: Semantic mapping for mobile robotics tasks: a survey. Robot. Auton. Syst. 66, 86–103 (2015)CrossRef
24.
go back to reference Mataric, M.: Integration of representation into goal-driven behavior-based robots. IEEE Trans. Robot. Autom. 8(3), 304–312 (1992)CrossRef Mataric, M.: Integration of representation into goal-driven behavior-based robots. IEEE Trans. Robot. Autom. 8(3), 304–312 (1992)CrossRef
25.
go back to reference Meilinger, T.: The network of reference frames theory: a synthesis of graphs and cognitive maps. In: Freksa, C., Newcombe, N.S., Gärdenfors, P., Wölfl, S. (eds.) Spatial Cognition VI. LNCS (LNAI), vol. 5248, pp. 344–360. Springer, Heidelberg (2008) Meilinger, T.: The network of reference frames theory: a synthesis of graphs and cognitive maps. In: Freksa, C., Newcombe, N.S., Gärdenfors, P., Wölfl, S. (eds.) Spatial Cognition VI. LNCS (LNAI), vol. 5248, pp. 344–360. Springer, Heidelberg (2008)
26.
go back to reference Montello, D.R., Sas, C.: Human factors of wayfinding in navigation. In: Karwowski, W. (ed.) International Encyclopedia of Ergonomics and Human Factors, 2nd edn, pp. 2003–2008. CRC Press, London (2006) Montello, D.R., Sas, C.: Human factors of wayfinding in navigation. In: Karwowski, W. (ed.) International Encyclopedia of Ergonomics and Human Factors, 2nd edn, pp. 2003–2008. CRC Press, London (2006)
27.
go back to reference Mozos, Ó.M., Triebel, R., Jensfelt, P., Rottmann, A., Burgard, W.: Supervised semantic labeling of places using information extracted from sensor data. Robot. Auton. Syst. 55, 391–402 (2007)CrossRef Mozos, Ó.M., Triebel, R., Jensfelt, P., Rottmann, A., Burgard, W.: Supervised semantic labeling of places using information extracted from sensor data. Robot. Auton. Syst. 55, 391–402 (2007)CrossRef
28.
go back to reference Ozgelen, A.T., Sklar, E.I.: Toward a human-centric task complexity model for interaction with multi-robot teams. In: Workshop on Human-Agent Interaction Design and Models (HAIDM) at AAMAS-2014 (2014) Ozgelen, A.T., Sklar, E.I.: Toward a human-centric task complexity model for interaction with multi-robot teams. In: Workshop on Human-Agent Interaction Design and Models (HAIDM) at AAMAS-2014 (2014)
29.
go back to reference Ratterman, M.J., Epstein, S.L.: Skilled like a person: a comparison of human and computer game playing. In: Moore, J.D., Lehman, J.F. (eds.) Cognitive Science 95, pp. 709–714. Lawrence Erlbaum Associates, Pittsburgh (1995) Ratterman, M.J., Epstein, S.L.: Skilled like a person: a comparison of human and computer game playing. In: Moore, J.D., Lehman, J.F. (eds.) Cognitive Science 95, pp. 709–714. Lawrence Erlbaum Associates, Pittsburgh (1995)
30.
go back to reference Reineking, T., Kohlhagen, C., Zetzsche, C.: Efficient wayfinding in hierarchically regionalized spatial environments. In: Freksa, C., Newcombe, N.S., Gärdenfors, P., Wölfl, S. (eds.) Spatial Cognition VI. LNCS (LNAI), vol. 5248, pp. 56–70. Springer, Heidelberg (2008) Reineking, T., Kohlhagen, C., Zetzsche, C.: Efficient wayfinding in hierarchically regionalized spatial environments. In: Freksa, C., Newcombe, N.S., Gärdenfors, P., Wölfl, S. (eds.) Spatial Cognition VI. LNCS (LNAI), vol. 5248, pp. 56–70. Springer, Heidelberg (2008)
31.
go back to reference Sklar, E.I., Ozgelen, A.T., Munoz, J.P., Gonzalez, J., Manashirov, M., Epstein, S.L., Parsons, S.: Designing the HRTeam framework: lessons learned from a rough-and-ready human/multi-robot team. In: Dechesne, F., Hattori, H., ter Mors, A., Such, J.M., Weyns, D., Dignum, F. (eds.) AAMAS 2011 Workshops. LNCS, vol. 7068, pp. 232–251. Springer, Heidelberg (2012) CrossRef Sklar, E.I., Ozgelen, A.T., Munoz, J.P., Gonzalez, J., Manashirov, M., Epstein, S.L., Parsons, S.: Designing the HRTeam framework: lessons learned from a rough-and-ready human/multi-robot team. In: Dechesne, F., Hattori, H., ter Mors, A., Such, J.M., Weyns, D., Dignum, F. (eds.) AAMAS 2011 Workshops. LNCS, vol. 7068, pp. 232–251. Springer, Heidelberg (2012) CrossRef
32.
go back to reference Speekenbrink, M., Konstantinidis, E.: Uncertainty and exploration in a restless bandit task. In: Bello, P., Gaurini, M., McShane, M., Scassellati, B. (eds.) Cognitive Science 2014, pp. 1491–1496. Cognitive Science Society, Austin (2014) Speekenbrink, M., Konstantinidis, E.: Uncertainty and exploration in a restless bandit task. In: Bello, P., Gaurini, M., McShane, M., Scassellati, B. (eds.) Cognitive Science 2014, pp. 1491–1496. Cognitive Science Society, Austin (2014)
33.
go back to reference Takemiya, M., Ishikawa, T.: Strategy-based dynamic real-time route prediction. In: Tenbrink, T., Stell, J., Galton, A., Wood, Z. (eds.) COSIT 2013. LNCS, vol. 8116, pp. 149–168. Springer, Heidelberg (2013) CrossRef Takemiya, M., Ishikawa, T.: Strategy-based dynamic real-time route prediction. In: Tenbrink, T., Stell, J., Galton, A., Wood, Z. (eds.) COSIT 2013. LNCS, vol. 8116, pp. 149–168. Springer, Heidelberg (2013) CrossRef
34.
go back to reference Tenbrink, T., Bergmann, E., Konieczny L.: Wayfinding and description strategies in an unfamiliar complex building. In: 33rd Annual Conference of the Cognitive Science Society, pp. 1262–1267 (2011) Tenbrink, T., Bergmann, E., Konieczny L.: Wayfinding and description strategies in an unfamiliar complex building. In: 33rd Annual Conference of the Cognitive Science Society, pp. 1262–1267 (2011)
35.
go back to reference Thrun, S., Bücken, A., Burgard, W., Fox, D., Fröhlinghaus, T., Hennig, D., Hofman, T., Krell, M., Schmidt, T.: Map learning and high-speed navigation in RHINO. In: Kortenkamp, D., Bonasso, R.P., Murphy, R. (eds.) AI-based Mobile Robots: Case Studies of Successful Robot Systems, pp. 21–52. MIT Press, Cambridge (1998) Thrun, S., Bücken, A., Burgard, W., Fox, D., Fröhlinghaus, T., Hennig, D., Hofman, T., Krell, M., Schmidt, T.: Map learning and high-speed navigation in RHINO. In: Kortenkamp, D., Bonasso, R.P., Murphy, R. (eds.) AI-based Mobile Robots: Case Studies of Successful Robot Systems, pp. 21–52. MIT Press, Cambridge (1998)
36.
go back to reference Tversky, B.: Cognitive maps, cognitive collages, and spatial mental models. In: Frank, A.U., Campari, I. (eds.) Spatial Information Theory: A Theoretical Basis for GIS. LNCS, vol. 716, pp. 14–24. Springer, Berlin (1993)CrossRef Tversky, B.: Cognitive maps, cognitive collages, and spatial mental models. In: Frank, A.U., Campari, I. (eds.) Spatial Information Theory: A Theoretical Basis for GIS. LNCS, vol. 716, pp. 14–24. Springer, Berlin (1993)CrossRef
37.
go back to reference Vasardani, M., Timpf, S., Winter, S., Tomko, M.: From descriptions to depictions: a conceptual framework. In: Tenbrink, T., Stell, J., Galton, A., Wood, Z. (eds.) COSIT 2013. LNCS, vol. 8116, pp. 299–319. Springer, Heidelberg (2013) CrossRef Vasardani, M., Timpf, S., Winter, S., Tomko, M.: From descriptions to depictions: a conceptual framework. In: Tenbrink, T., Stell, J., Galton, A., Wood, Z. (eds.) COSIT 2013. LNCS, vol. 8116, pp. 299–319. Springer, Heidelberg (2013) CrossRef
38.
go back to reference Vasudevan, S., Gächter, S., Nguyen, V., Siegwart, R.: Cognitive maps for mobile robots —an object based approach. Robot. Auton. Syst. 55(5), 359–371 (2007)CrossRef Vasudevan, S., Gächter, S., Nguyen, V., Siegwart, R.: Cognitive maps for mobile robots —an object based approach. Robot. Auton. Syst. 55(5), 359–371 (2007)CrossRef
39.
go back to reference Weiser, P., Frank, A.U.: Cognitive transactions – a communication model. In: Tenbrink, T., Stell, J., Galton, A., Wood, Z. (eds.) COSIT 2013. LNCS, vol. 8116, pp. 129–148. Springer, Heidelberg (2013) CrossRef Weiser, P., Frank, A.U.: Cognitive transactions – a communication model. In: Tenbrink, T., Stell, J., Galton, A., Wood, Z. (eds.) COSIT 2013. LNCS, vol. 8116, pp. 129–148. Springer, Heidelberg (2013) CrossRef
40.
go back to reference Wolf, D.F., Sukhatme, G.S.: Semantic mapping using mobile robots. IEEE Trans. Robot. 24(2), 245–258 (2008)CrossRef Wolf, D.F., Sukhatme, G.S.: Semantic mapping using mobile robots. IEEE Trans. Robot. 24(2), 245–258 (2008)CrossRef
41.
go back to reference Zetzsche, C., Galbraith, C., Wolter, J., Schill, K.: Representation of space: image-like or sensorimotor? Spat. Vis. 22(5), 409–424 (2009)CrossRef Zetzsche, C., Galbraith, C., Wolter, J., Schill, K.: Representation of space: image-like or sensorimotor? Spat. Vis. 22(5), 409–424 (2009)CrossRef
Metadata
Title
Learning Spatial Models for Navigation
Authors
Susan L. Epstein
Anoop Aroor
Matthew Evanusa
Elizabeth I. Sklar
Simon Parsons
Copyright Year
2015
DOI
https://doi.org/10.1007/978-3-319-23374-1_19

Premium Partner