This article considers the problem of spatial representation for animat navigation systems. It is proposed that the global navigation task, or "wayfinding, " is best supported by multiple interacting subsystems, each of which builds its own partial representation of relevant world knowledge. Evidence from the study of animal navigation is reviewed to demonstrate that similar principles underlie the wayfinding behavior of animals, including humans. A simulated wayfinding system is described that embodies and illustrates several of the themes identified with animat navigation. This system constructs a network of partial models of the quantitative spatial relations between groups of salient landmarks. Navigation tasks are solved by propagating egocentric view information through this network, using a simple but effective heuristic to arbitrate between multiple solutions.
Agre, P.E. (1991) The dynamic structure of everyday life. Cambridge, UK: Cambridge University Press.
2.
Anderson, J.R. (1983) The architecture of cognition. Cambridge: Harvard University Press.
3.
Arbib, M.A. (1989) The metaphorical brain. New York: Wiley.
4.
Arbib, M.A. (1990) Interaction of multiple representations of space in the brain. In J. Paillard (Ed.), Brain and space. Oxford: Oxford University Press.
5.
Beer, R.D. (1995) Computational and dynamical languages for autonomous agents. In T. van Gelder & R. Port (Eds.), Mind as motion. Cambridge, MA : MIT Press.
6.
Brooks, R.A. (1985) Visual map making for a mobile robot. In Proceedings of the IEEE International Conference on Robotics and Automation.
7.
Brooks, R.A., & Flynn, A. (1989) Robot beings. Proceedings of the IEEE/RSJ International Workshop on Intelligent Robots and Systems.
8.
Brooks, R.A. (1995) Intelligence without reason. In L. Steels & R. Brooks (Eds.), The artificial life route to artificial intelligence. Hillsdale, NJ: Lawrence Erlbaum.
9.
Cartwright, B.A., & Collett, T.S. (1979) How honeybees know their distance from a nearby visual landmark. Journal of Experimental Biology, 82, 367-372.
10.
Cartwright, B.A., & Collett, T.S. (1983) Landmark learning in bees: Experiments and models . Journal of Comparative Physiology [A], 151(4), 521-544.
11.
Cartwright, B.A., & Collett, T.S. (1987) Landmark maps for honeybees. Biological Cybernetics, 57, 85-93.
12.
Chapuis, N., Thinus-Blanc, C., & Poucet, B. (1983) Dissociation of mechanisms involved in dogs' oriented displacements. Quarterly Journal of Experimental Psychology , 35B, 213-219.
13.
Chatila, R. (1986) Mobile robot navigation: Space modelling and decisional processes. In O. D. Faugeras & G. Giralt (Eds.), Third International Symposium on Robotics Research. Cambridge, MA: MIT Press.
14.
Clark, A. (in press). Being there: Putting brain, body and world together again . Cambridge, MA: MIT Press.
15.
Collett, T.S., Cartwright, B.A., & Smith, B.A. (1986) Landmark learning and visuospatial memory in gerbils . Journal of Comparative Physiology [A], 158, 835-851.
16.
Connell, J. (1988) Navigation by path remembering. SPIE Vol. 1007: Mobile Robots III.
17.
Connell, J.H. (1990) Minimalist mobile robots. Boston : Academic.
18.
Crowley, J.L. (1985) Navigation for an intelligent mobile robot. IEEE Journal of Robotics and Automation, 1(1), 31-41.
19.
Dijkstra, E.W. (1959) A note on two problems in connexion graphs. Numerishe Mathematik, 1, 269-272.
20.
Etienne, A.S. (1992) Navigation of a small mammal by dead reckoning and local cues. Current Directions in Psychological Science , 1(2), 48-52.
21.
Farin, G. (1988) Curves and surfaces for computer aided geometric design: A practical guide. Boston: Academic.
22.
Gallistel, C.R. (1990) The organisation of learning. Cambridge, MA: MIT Press.
23.
Gould, J.L. (1986) The locale map of honeybees: Do insects have cognitive maps?Science, 232, 861-863.
24.
Hertz, J., Krogh, A., & Palmer, R.G. (1991) Introduction to the theory of neural computation . Redwood City, CA: Addison-Wesley .
25.
Hinton, G.E., McClelland, J.L., & Rumelhart, D.E. (1986) Distributed representations . In D. E. Rumelhart & J. L. McClelland (Eds.), Parallel distributed processing: Explorations in the micro-structure of cognition, Vol. 1. Cambridge, MA: Bradford Books.
26.
Iyengar, S., Jorgensen, C.; Rao, S., & Weisbin, C. (1985) Learned navigation paths for a robot in unexplored terrain. In Proceedings of the Second Conference on Artificial Intelligence Applications, vol. 1, 147-156.
27.
Jamon, M. (1990) The contribution of quantitative models to the long distance orientation problem. In J.-A. Meyer & S. Wilson (Eds.), From animals to animats: Proceedings of the First International Conference on Simulation of Adaptive Behaviour. Cambridge, MA: MIT Press.
28.
Kortenkamp, D., Weymouth, T., Chown, E., & Kaplan, S. (1992) A scene-based multilevel representation for mobile robot spatial mapping and navigation (Tech. Rep. No. CSE-TR-119-92). Ann Arbor: University of Michigan Press.
29.
Kuipers, B.J. (1982) The "map in the head" metaphor. Environment and Behaviour, 14, 202-220.
30.
Kuipers, B.J., & Byun, Y.T. (1987) A robust, qualitative method for robot exploration and map-learning. Proceedings of the Sixth National Conference on AI (AAAI-87). St. Paul, MN: Morgan Kaufmann.
31.
Kuipers, B.J., & Byun, Y.T. (1991) A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Robotics and Autonomous Systems, 8, 47-64.
32.
Kuipers, B.J., & Levitt, T. (1988) Navigation and mapping in large-scale space. AI Magazine (summer 1988), 25-43.
33.
Leiser, D., & Zilbershatz, A. (1989) The traveller: A computational model of spatial network learning. Environment and Behaviour , 21(4), 435-463.
34.
Levitt, T.S., & Lawton, D.T. (1990) Qualitative navigation for mobile robots. Artificial Intelligence, 44, 305-360.
35.
Lozano-Perez, T. (1983) Spatial-planning: A configuration space approach . IEEE Transactions on Computers, C-32(2), 108-121.
36.
Maes, P. (1992) Behaviour-based artificial intelligence. In J.-A. Meyer, H. L. Roitblat, & S. W Wilson (Eds.), From animals to animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behaviour. Cambridge, MA: MIT Press.
37.
Mataric, M.J. (1990) Navigating with a rat brain: A neurologically inspired model for robot spatial representation. In J.-A. Meyer & S. Wilson (Eds.), From Animals to Animats: Proceedings of the First International Conference on Simulation of Adaptive Behaviour. Cambridge, MA: MIT Press.
38.
Mataric, M.J. (1995) Integration of representation into goal-driven behaviour-based robots. In L. Steels & R. Brooks (Eds.), The artificial life route to artificial intelligence. Hillsdale, NJ: Lawrence Erlbaum.
39.
Maybeck, P.S. (1979) Stochastic models, estimation and control. Boston: Academic.
McNaughton, B.L., Chen, L.L., & Markus, E.J. (1991) Landmark learning and the sense of direction—a neurophysiological and computational hypothesis. Journal of Cognitive Neuroscience, 3(2), 192-202.
42.
Meyer, J., & Guillot, A. (1990) Simulation of adaptive behaviour in animats: Review and prospect. In J.-A. Meyer & S. Wilson (Eds.), From animals to animats: Proceedings of the First International Conference on Simulation of Adaptive Behaviour. Cambridge, MA: MIT Press .
43.
Morris, R.G.M., Garrud, P., Rawlins, J.N.P., & O'Keefe, J. (1982) Place navigation impaired in rats with hippocampal lesions. Nature, 297, 681-683.
44.
Neisser, U. (1976) Cognition and reality. San Francisco: Freeman.
45.
O'Keefe, J. (1990a) Computational theory of the hippocampal cognitive map. Progress in Brain Research, 83, 301-312.
46.
O'Keefe, J. (1990b) Computations the hippocampus might perform. In L. Nadel, L. Cooper, P. Culicover, & R. M. Harnish (Eds.), Neural connections, mental computation. Cambridge, MA: MIT Press.
47.
O'Keefe, J. (1990c) The hippocampal cognitive map and navigational strategies. In J. Paillard (Ed.), Brain and Space. Oxford: Oxford University Press.
48.
O'Keefe, J.A., & Nadel, L. (1978) The hippocampus as a cognitive map. Oxford: Oxford University Press.
49.
Olton, D.S. (1979) Mazes, maps, and memory. American Psychologist, 34(7), 583-596.
50.
Olton, D.S. (1982) Spatially organized behaviours of animals: Behavioural and neurological studies. In M. Potegal (Ed.), Spatial abilities: Development and physiological foundations . New York: Academic.
51.
Piaget, J., Inhelder, B., & Szeminska, A. (1960) The child's conception of geometry. New York: Basic Books.
52.
Poucet, B., Thinus-Blanc, C., & Chapuis, N. (1983) Route planning in cats, in relation to the visibility of the goal. Animal Behaviour, 31, 594-599.
53.
Prescott, T.J. (1993a) Building long-range cognitive maps using local landmarks. In J.-A. Meyer, H. L. Roitblat, & S. W Wilson (Eds.), From animals to animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behaviour . Cambridge, MA: MIT Press.
54.
Prescott, T.J. (1993b) Explorations in reinforcement and model-based learning. Unpublished doctoral thesis, University of Sheffield , UK.
55.
Prescott, T.J. (1994) Spatial learning and representation in animats . In D. Cliff, P Husbands, J-A. Meyer, & S. W Wilson (Eds.), From animals to animats 3: Proceedings of the Third International Conference on Simulation of Adaptive Behaviour. Cambridge, MA: MIT Press .
56.
Presson, C., & Hazelrigg, M. (1984) Building spatial representations through primary and secondary learning. Journal of Experimental Psychology: Learning, Memory and Cognition, 6, 516-528.
57.
Rao, N., Stoltzfus, N., & Iyengar, S. (1988) A retraction method for terrain model acquisition . Proceedings of the IEEE International Conference on Robotics and Automation.
58.
Roifblat, H.L. (1994) Mechanism and process in animal behaviour. In D. Cliff, P Husbands, J-A. Meyer, & S. W. Wilson (Eds.), From animals to animats 3: Proceedings of the Third International Conference on Simulation of Adaptive Behaviour. Cambridge, MA: MIT Press .
59.
Scholl, M.J. (1987) Cognitive maps as orienting schemata. Journal of Experimental Psychology: Learning, Memory and Cognition, 13, 615-628.
60.
Scholl, M.J. (1992) Landmarks, places, environments: Multiple mind-brain systems for spatial orientation. Geoforum, 23(2), 151-164.
Siegel, A.W., & White, S.H. (1975) The development of spatial representations of large-scale environments. In H. W Reese (Ed.), Advances in Child Development and Behaviour. New York: Academic.
63.
Smith, R., Self, M., & Cheeseman, P. (1990) Estimating uncertain spatial relationships in robotics . In I.J. Cox & G. T. Wilfong (Eds.), Autonomous robot vehicles . New York: Springer-Verlag.
64.
Soldo, M. (1990) Reactive and preplanned control in a mobile robot . Proceedings of the IEEE Conference on Robotics and Automation, Cincinnati, OH.
65.
Touretzky, D.S. (1994) Neural representation of space in rats and robots . In J. M. Zurada & R. J. Marks (Eds.), Computational intelligence: Imitating life. New York: IEEE Press .
66.
Turchan, M., & Wong, A. (1985) Low-level learning for a mobile robot: Environment model acquisition. Proceedings of the Second Conference on Artificial Intelligence Applications.
67.
Wehner, R. (1983) Celestial and terrestrial navigation: Human strategies—insect strategies. In F. Huber & H. Markl (Eds.), Neuroethology and behavioural physiology. Berlin: Springer-Verlag .
68.
Wehner, R., & Menzel, R. (1990) Do insects have cognitive maps?Annual Review of Neuroscience, 13, 403-414.
69.
Wilson, S.W. (1990) The animat path to AI. In J.-A. Meyer & S. Wilson (Eds.), From animals to animats: Proceedings of the First International Conference on the Simulation of Adaptive Behaviour. Cambridge, MA: MIT Press.
70.
Worden, R. (1992) Navigation by fragment fitting: A theory of hippocampal function. Hippocampus, 2(2), 165-188.
71.
Yeap, W.K. (1988) Towards a computational theory of cognitive maps . Artificial Intelligence, 34, 297-360.
72.
Zipser, D. (1983a) The representation of location (Rep. No. ICS 8301) . San Diego: Institute for Cognitive Science, University of California at San Diego.
73.
Zipser, D. (1983b) The representation of maps (Rep. No. ICS 8304) . San Diego: Institute of Cognitive Science, University of California at San Diego.
74.
Zipser, D. (1986) Biologically plausible models of place recognition and place location. In J. L. McClelland & D. E. Rumelhart (Eds.), Parallel distributed processing: Explorations in the micro-structure of cognition, Vol. 2. Cambridge, MA: Bradford Books.
