Saturday , August 18 2018

The Inn at the Crossroads – A Model of Distributed Spatial Knowledge

Ioan SUSNEA
University “Dunarea de Jos” of Galati,
47 Domneasca St., Galati, 800008, Romania
ioan.susnea@ugal.ro

Abstract: The paper describes a simple experiment aimed to demonstrate the possibility to create distributed cognitive maps of certain environments by means of recording basic information about the purposeful motion of a population of mobile agents. The environment is assumed to consist in a set of behaviorally significant places interconnected by predefined paths, just like the inns at the crossroads used to be deployed along and across populated areas centuries ago. These active places interact with the mobile agents and create local patches of relevant navigation information, which is shared with other agents that reach the respective place. As a result, the system exhibits a globally consistent spatial behavior, using only locally available, incomplete spatial knowledge. A NetLogo simulation allowed us to compare the average distance traveled by the agents, and the average travel time before reaching their goals, with a similar system wherein the agents walk randomly. As expected, the agents using the distributed spatial knowledge reached their goals much faster than those walking randomly in the same environment. We also explore the possible applications of systems built according to the principles described here.

Keywords: Multi-agent systems, spatial cognition, distributed memory maps, cognitive stigmergy.

>>Full text<<
CITE THIS PAPER AS: Ioan SUSNEA, The Inn at the Crossroads – A Model of Distributed Spatial Knowledge, Studies in Informatics and Control, ISSN 1220-1766, vol. 25(1), pp. 15-20, 2016.

  1. Introduction

Arguably, spatial orientation is one of the most important requirements for survival in the biological world. Most living organisms need to be able to navigate through the environment in search of food, to return to certain significant places such as nests or shelters, or to recognize certain “signs” in the environment as potential dangers or hideouts.

Animals often exhibit amazing abilities of spatial navigation: consider the examples of the Chinook salmon (oncorhynchus tshawytscha) that travel 3000 Km to spawn in the exact place where they come to life, or of the Arctic tern (sterna paradisaea) that fly 70,000 Km each year, from Greenland to Antarctica and back.

The neural mechanisms that allow such extraordinary exploits are not fully understood. After studying how rats find their way to the food in a maze, Tolman [1] coined the term “cognitive maps” to designate some hypothetical neural structures that reproduce geometric features and relative positions of the perceived objects in space.

Subsequent studies of O’Keefe & Dostrovsky [2], Ranck [3], and Moser [4] and many others support the hypothesis of Tolman, by providing experimental evidence of the existence of specialized neurons called “place cells”, “head direction cells”, and “grid cells” (in hippocampus and in other areas of the brain), all involved in the process of spatial orientation.

Though the formal definition of the cognitive maps is still under debate (see [5], [6], [7]), it is now widely accepted that there exists a neural model of the spatial environment, and in a general sense, a cognitive map is any mental representation of the space.

The interest for spatial cognition and mapping exceeds the boundaries of the biology and neurology, and there is now a huge literature that explores these topics from various perspectives: psychology, engineering (robotics, wireless sensor networks), urbanism, etc.

In engineering, for obvious reasons, the problems related to spatial localization and mapping were mainly studied in the context of robotics (see [8], [9], [10], [11]] for a quick image of the complexity of these problems).

An interesting taxonomy of the approaches used in robotic mapping starting from the hierarchy of the levels of abstraction of the features used in navigation is available in [12].

Rather surprisingly, while reviewing the vast literature dedicated to spatial cognition from an engineering perspective, it becomes obvious that there are at least two implicit assumptions that tend to hinder the understanding of these topics:

  • One is the idea that the spatial cognition is a purely individual process, wherein the environment is entirely passive – just the object of the cognitive reflection, and the reflexive subject is completely disconnected from other individuals.
  • The second implicit assumption is the idea that “the map is not the territory” – a famous statement that seems so obvious that makes us ignore the fact that the territory often contains map-specific features, usually in the form of traces resulted from the activity of other agents. These traces may be interpreted as indirect communication messages capable to influence the spatial navigation of the other agents (see [13]). In fact, the boundary between the map and the territory is not always very crisp.

The aim of the research described in this paper is to explore the situations when the spatial cognition is neither individual nor local, i.e. when the cognitive map results from the activity of a whole population of agents, and this map is organized as a set of “sub-maps” distributed over the environment in certain active places that act as “patches of knowledge”.

To this purpose, we have created a NetLogo ([14]) model, wherein a number of mobile agents move through an environment, organized as a topological graph, consisting in a set of nodes, interconnected by edges.

However, this graph structure only exists for an external observer. No instance in this system has a global representation of the topology of the environment, and the mobile agents (“walkers”) navigate relying only on the incomplete and locally available information resulted from their interaction with the nodes of the graph.

The NetLogo simulation allowed us to measure and compare the average distance traveled by the agents, and the average travel time before reaching their goals, with those measured in a similar system wherein the agents walk randomly. As expected, the agents using the distributed cognitive map reached their goals up to ten times faster than those walking randomly in the same environment. We also explored a few possible applications of systems built according to the principles described here.

The rest of this paper is structured as follows:

  • Section 2 contains a brief review of the related work;
  • Section 3 contains a description of the experiment, and the results.
  • Section 4 is reserved for discussion and conclusions.

REFERENCES

  1. TOLMAN, E. C., Cognitive Maps in Rats and Men, Psychological Review, 1948, 55.4: 189.
  2. O’KEEFE, J., DOSTROVSKY, J., The Hippocampus as a Spatial Map. Preliminary Evidence from Unit Activity in the Freely-Moving Rat, Brain Research, 1971, 34.1: 171-175.
  3. RANCK JR., J. B. Head-direction Cells in the Deep Cell Layers of Dorsal Presubiculum in Freely Moving Rats, Society for Neuroscience Abstracts, 1984.
  4. MOSER, E. I., E., KROPFF, M.-B., MOSER, Place Cells, Grid Cells, and the Brain’s Spatial Representation System, Neuroscience, 2008, 31.1: 69.
  5. BENNETT, A. T., Do Animals Have Cognitive Maps?, The Journal of Experimental Biology, 1996, 199.1: 219-224.
  6. JACOBS, L. F., The Evolution of the Cognitive Map, Brain, Behavior and Evolution, 2003, 62.2: 128-139.
  7. CHEESEMAN, J. F., et al. Way-finding in Displaced Clock-shifted Bees Proves Bees Use a Cognitive Map, Proceedings of the National Academy of Sciences, 2014, 111.24: 8949-8954.
  8. THRUN, S., et al. Robotic Mapping: A Survey. Exploring Artificial Intelligence in the New Millennium, 2002, pp. 1-35.
  9. VASUDEVAN, S., et al. Cognitive Maps for Mobile Robots – an Object Based Approach. Robotics and Autonomous Systems, 2007, 55.5: 359-371.
  10. WOLF, D. F., SUKHATME, G. S., Mobile Robot Simultaneous Localization and Mapping in Dynamic Environments, Autonomous Robots, 2005, 19.1: 53-65.
  11. GARCIA-FIDALGO, E.; A., ORTIZ, Vision-based Topological Mapping and Localization Methods: A Survey, Robotics and Autonomous Systems, 2015, 64: 1-20.
  12. TAPUS ,A., Topological SLAM-Simultaneous Localization and Mapping with Fingerprints of Places, 2005, PhD Thesis, Université Joseph Fourier Grenoble, France.
  13. TUMMOLINI, L., CASTELFRANCHI, C., Trace Signals: the Meanings of Stigmergy, Environments for Multi-Agent Systems III, Springer Berlin Heidelberg, 2007, pp. 141-156.
  14. WILENSKY, U., NetLogo (and NetLogo User Manual), Center for Connected Learning and Computer-Based Modeling, Northwestern University. http://ccl. northwestern. edu/netlogo, 1999.
  15. BENI, G., J., WANG, Swarm Intelligence in Cellular Robotic Systems, Robots and Biological Systems: Towards a New Bionics?, Springer Berlin Heidelberg, 1993, pp. 703-712.
  16. CHIALVO, D. R., M. M., MILLONAS, How Swarms Build Cognitive Maps, The Biology and Technology of Intelligent Autonomous Agents, Springer Berlin Heidelberg, 1995, pp. 439-450.
  17. RICCI, A., et al., Cognitive Stigmergy: Towards a Framework Based on Agents and Artifacts, Environments for Multi-Agent Systems III, Springer Berlin Heidelberg, 2007. pp. 124-140.
  18. ZAMFIRESCU, C.-B., FILIP, F. G., Swarming Models for Facilitating Collaborative Decisions, International Journal of Computers, Communications & Control, 2010, 1: 1841-1844.
  19. SUSNEA, I., G., VASILIU, D. E., MITU, Enabling Self-Organization of the Educational Content in Ad Hoc Learning Networks, Studies in Informatics and Control, 2013, 22.2: 143-152.
  20. SUSNEA, I., Engineering Human Stigmergy. International Journal of Computers Communications & Control, 2015, 10.3: 420-427.
  21. SUSI, T., T., ZIEMKE, Social Cognition, Artefacts, and Stigmergy: A Comparative Analysis of Theoretical Frameworks for the Understanding of Artefact-Mediated Collaborative Activity. Cognitive Systems Research, 2001, 2.4: 273-290.
  22. PARUNAK, H. V. D., A Survey of Environments and Mechanisms for Human-Human Stigmergy, Environments for Multi-Agent Systems II. Springer Berlin Heidelberg, 2006. pp. 163-186.
  23. OMICINI, A., Agents Writing on Walls: Cognitive Stigmergy and Beyond, in The Goals of Cognition. Essays in Honor of Cristiano Castelfranchi, vol. 20 of Tributes, chapter 29, 543–556, College Publications, London, (December 2012).
  24. CONRADT, J.-A., A Distributed Cognitive Map for Spatial Navigation Based on Graphically Organized Place Agents, 2008, PhD Thesis, Swiss Federal Institute of Technology, Zurich.
  25. LOVÁSZ, L., et al., Random Walks on Graphs: A Survey, Combinatorics, Paul Erdos is Eighty, 1996, 2: 353-398.
  26. BALATA, J., et al., Collaborative Navigation of Visually Impaired. Journal on Multimodal User Interfaces, 2014, 8.2: 175-185.

https://doi.org/10.24846/v25i1y201602