RatSLAM

RatSLAM is a new method of robot control that allows a robot to learn a map of any area and then navigate using that map. The new method is based on ideas from models of rodent brains.

The RatSLAM project has two intended outcomes:

To provide a new and effective method for the mobile robot problem of Simultaneous Localisation And Mapping (SLAM), and
To reproduce a high-level brain function in a robot in order to increase the understanding of memory and learning in mammals, including humans.

The project has been funded by Australian Research Council Grants (Discovery Projects DP0346075 (2003), DP0559380 (2005) and Thinking Systems Special Research Initiative TS0669699 (2006))

Prehistory

The project started with the publication of a paper in Adaptive Behaviour in 1998 "Cognitive Models of Spatial Navigation from a Robot Builder's Perspective" (Wyeth and Browning, 1998) which compared the navigation abilities of a simple maze solving robot with the computational neuroscience models of spatial navigation current at the time of writing (1996). In summary, the paper found that the models at the time were generally piecemeal, each missing key components that would allow the creation of a maze solving robot built on computational neuroscientific principles.

At the same time as the paper in Adaptive Behaviour was going to press, David Redish's thesis from Carnegie Mellon University "Beyond the Cognitive Map: Contributions to a Computational Neuroscience Theory of Rodent Navigation" (Redish, 1997; Redish, 1999) tied many of the pieces together . Founded on the landmark studies by O'Keefe and Nadel "The Hippocampus as a Cognitive Map" (O'Keefe and Nadel, 1978), his thesis (and associated publications) described a detailed computational neuroscience model that was to form the basis of our first attempts to build a vision based mapping and localising robot. That attempt was published in Brett Browning's thesis "Biologically Plausible Spatial Navigation for a Mobile Robot" (Browning, 2000) which formed the foundation for the first RatSLAM models of the hippocampal complex.

At about the same time, Angelo Arleo published his PhD "Spatial Learning and Navigation in Neuro-Mimetic Systems, Modeling the Rat Hippocampus" (Arleo, 2000) which demonstrated a complete computational model operating both in simulation and on a small robot. Arleo's model, too, showed promise for the hippocampal complex as the basis of a robot navigation system.

One of the key lessons from Brett's study was that working on small embedded robots creates many unnecessary headaches, which slow the research progress. 2001 and 2002 were mostly about securing the necessary funds for robots and further studies. In 2001, an equipment grant was used to purchase three Pioneer DX2 robots, and David Prasser was given a scholarship to start working on the vision system. His work on establishing a well characterised artificial landmark vision system for the Pioneer robots (Prasser and Wyeth, 2003a) won Best Student Paper at the International Symposium on Autonomous Minirobots for Research and Entertainment, with later results showing the suitability for its use in SLAM (Prasser and Wyeth, 2003b). With the research platform in place, funding was won in 2002 to begin the RatSLAM project proper commencing in 2003.

RatSLAM Begins

The first step in the RatSLAM project was to create a complete computational model of the hippocampal complex and use it as the basis for SLAM (Simultaneous Localisation and Mapping) on a Pioneer robot. The principles of the model were similar to these used in Brett Browning's thesis, and held much in common with Arleo's model (see figure below).

Figure 1: Initial architecture for RatSLAM. The separation of head direction and place code caused problems in larger environments.

The Head Direction (HD) and Place Code (PC) networks were implemented as competitive attractor neural networks. The Local View (LV) network was driven from David Prasser's artificial landmark system while Path Integration (PI) came from the Pioneer's odometry. By late 2003, Michael Milford had completely implemented and tested the first system with the results published (Milford and Wyeth, 2003). A live demonstration of the system was given at the Australian Conference on Robotics and Automation.

It was at this stage that we first identified a key issue with the models of hippocampal complex that were the basis of the RatSLAM system - they didn't work in large environments. While the robot was kept in a small environment so that there was little uncertainty in Head Direction, the maps converged and the robot could successfully localised. However, when the Head Direction representation contained more than one attractor (in other words, it contained multiple hypotheses about the direction that the robot was facing) the map would quickly diverge. This was a major problem if RatSLAM was ever to be useful as a robotic SLAM system and needed to be addressed. These issues are discussed in (Milford and Wyeth, 2003).

RatSLAM Evolves

This discovery led to a major change in the RatSLAM system; rather than representing pose with a one-dimensional orientation network (HD) and a separate two dimensional position (PC) network, we used a three dimensional network which we called the Pose Cells. The Pose Cells used competitive attractor dynamics to keep the activity packet stable, and to perform the Path Integration process. The distance, relative orientation and colour of artificial landmarks was represented by a sparse code in a three dimensional Local View (LV) network. Associations were learnt between active LV cells and active Pose Cells using Hebbian update rules. The updated RatSLAM system could build consistent maps and remain localised in an environment with coloured markers (Milford, Wyeth and Prasser, 2004a).

Figure 2: Local View and Pose Cell arrangement for artificial landmarks. The integration of both orientation and position into a single network solved the issues found with earlier models.

Figure 3: The Pioneer using RatSLAM with Pose Cells to map a large environment using sparsely placed coloured cylinders as landmarks. A blue landmark is shown in the foreground, and an orange cylinder can be seen further down the corridor.

In parallel to this work, David Prasser had been developing vision techniques for extracting natural landmarks, so that RatSLAM would not rely on the artificial landmarks for generating the Local View. In initial results, David used ideas from visual cortex with some success (Prasser and Wyeth, 2003c). Simplifying these ideas, David then employed landmarks based on visual appearance, with scenes pre-processed with Gabor filters, and then compared to a database of templates. Recognised templates resulted in activation of the corresponding Local View code, while new templates were added to the database and assigned a new code. RatSLAM was now capable of many difficult SLAM problems: real-time and online SLAM based on vision using natural features, that could perform loop closure and recover from kidnapping. Results from localisation in office environments were presented in (Prasser, Wyeth and Milford, 2004a) and (Milford, Wyeth and Prasser, 2004b).

Figure 4: Template Cells were used for natural landmarks, with template cells becoming active if the current visual scene was a close match to the template.

Figure 5: Results from an indoor experiment using natural landmarks. The map shows the path taken by the robot around the office and labs. The graph shows the peak activity in the Pose Cells and an occupancy grid built from sonar reflections. The occupancy grid is for illustrative purposes and is not used by the RatSLAM algorithm.

The system was adapted for outdoor use, using a template database formed from the scenes' colour histogram. Results presented in (Prasser, Milford and Wyeth, 2004b) and (Prasser, Milford and Wyeth, 2005) demonstrated the system's effectiveness in localising in two large outdoor experiments.

Figure 6: Results from an outdoor experiment. The map shows the path taken by the robot around the campus. The graph shows the peak activity in the Pose Cells (looking in the position plane). Note the topological links that create loop closure.

Path Planning with RatSLAM

The first attempts at path planning with RatSLAM involved the production of a Goal Memory system in conjunction with the Local View and Pose Cell systems. The Goal Memory learnt the temporal relationship between Pose Cells. Pose Cells that were activated one after the other developed strong connections in Goal Memory. Paths were then determined by spreading activation from the goal to the robot's current location. Activation spread most strongly along paths with strong connections, meaning places that had been experienced close together in time. The robot then followed activation trail to the goal. This method proved successful, provided that the Pose Cell representation was well organised. This work was published in (Milford, Wyeth and Prasser, 2005a).

Figure 7: Spread of activity to a goal location (right lower). Lighter areas correspond to lower cell activity levels and hence locations closer in time to the goal than darker areas. The robot successfully navigates to the goal from position A.

After this successful trial, we put together a framework to allow longer term testing of the RatSLAM system (Emami et al, 2005). The intention was to allow users to control to the Pioneer robot over the internet using the RatSLAM system to perform mapping, localisation and path planning. To our disappointment, we found that hashing collisions in the Pose Cells (a Pose Cell representing more than one pose of the robot) were fatal to the Goal Memory system. Occasional hashing collisions within the Pose Cells are unavoidable, so the Goal Memory system had to be revised.

Based on the ideas developed through the Goal Memory, Michael Milford invented a new extension of RatSLAM, Experience Mapping. The idea of Experience Mapping is to produce a spatially continuous map without collisions from the sometimes messy representations found in the Pose Cells. It does this by combining information from the Pose Cells with the Local View cells and the robot's current behaviour. The Experience Mapping algorithm runs online and in real time in conjunction with all of the other learning systems. The algorithm and initial results are shown in (Milford, Prasser and Wyeth, 2005b).

Figure 8: The Experience Map algorithm takes a heavily distorted Pose Cell map with many collisions and links and produces a spatially continuous map without collisions.

The Experience Map algorithm also allowed the number of Pose Cells to be greatly reduced. As can be seen in the results above, the Pose Cells sometimes wrap around from one edge to the other. We explored the effects of greatly reducing the number of Pose Cells so that the Pose Cell map wrapped many times in a given environment. Results presented in (Milford et al, 2006c) showed that a useful Experience Map still developed even when the Pose Cells had wrapped around four to five times in both x and y directions. (Milford, Wyeth and Prasser, 2006a)showed that the Experience Map can deal with changes to the environment, such as a corridor being temporarily blocked.

RatChat

RatChat is a project that seeks to evolve a language based on the representations found in the RatSLAM system. This part of the project is still in its founding stages. Early results published in (Milford et al, 2006b), (Schulz et al, 2006a) and (Schulz et al, 2006b).

Thinking Systems

We are now investigating some new directions from RatSLAM:

Now that we have made a fully functional system based on rodent hippocampal models, are we in a better position to inform those models? Are there new biological findings that might help explain some of the key problems that we encountered along the way?
The human hippocampus is believed to perform many core cognitive functions apart from spatial navigation. Are there parallels between spatial navigation and other cognitive functions such as reasoning, language and creativity? Can RatSLAM explain models for these cognitive functions? Could RatSLAM form the basis of new AI algorithms in the space of ideas, instead of physical space?
How can we make RatSLAM cheap and affordable? It would be useful, for example, to have your autonomous vacuum cleaner know which areas have been cleaned and which have not. RatSLAM could solve this problem, but would require a camera and significant processing power which are costly in the context of a consumer product. What would be required to bring RatSLAM to the level where it could be an affordable resource in a domestic product?

These questions are being investigated in the context of the Thinking Systems project.

Publications from Project

M.J. Milford, G. Wyeth, D. Prasser, (2006a) "RatSLAM on the Edge: Revealing a Coherent Representation from an Overloaded Rat Brain", International Conference on Intelligent Robots and Systems, Beijing, China, 2006.

M. J. Milford, R. Schulz, D. Prasser, G. Wyeth, J. Wiles, (2006b) "Learning Spatial Concepts from RatSLAM Representations", Robotics and Autonomous Systems, to appear.

M.J. Milford, D. Prasser and G. Wyeth (2006c) "Effect of Representation Size and Visual Ambiguity on RatSLAM System Performance" Australasian Conference on Robotics and Automation, Auckland, New Zealand, 2006.

R. Schulz, P. Stockwell, M. Wakabayashi, J. Wiles, (2006a). "Towards a spatial language for mobile robots", In A. Cangelosi, A. D. M. Smith & K. Smith (Eds.), The Evolution of Language: Proceedings of the 6th International Conference on the Evolution of Language. Singapore: World Scientific Press.

R. Schulz, P. Stockwell, M. Wakabayashi, J. Wiles, (2006b). "Generalization in languages evolved for mobile robots", In L. M. Rocha, L. S. Yaeger, M. A. Bedau, D. Floreano, R. L. Goldstone & A. Vespignani (Eds.), ALIFE X: Proceedings of the Tenth International Conference on the Simulation and Synthesis of Living Systems. (pp. 486-492) MIT Press.

M. J. Milford, G. Wyeth, D. Prasser (2005a), "Efficient Goal Directed Navigation using RatSLAM," International Conference on Robotics and Automation, Barcelona, Spain, 2005.

M. J. Milford, D. Prasser, G. Wyeth (2005b), "Experience Mapping: Producing Spatially Continuous Environment Representations Using RatSLAM," Australian Conference on Robotics and Automation, Sydney, Australia, 2005.

S. Emami, G. Wyeth, M. Milford, D. Prasser (2005), "Framework for the Long-Term Operation of a Mobile Robot via the Internet," Australian Conference on Robotics and Automation, Sydney, Australia, 2005.

D. Prasser, M. J. Milford, G. Wyeth (2005), "Outdoor Simultaneous Localisation and Mapping using RatSLAM," accepted to the International Conference on Field and Service Robots , Port Douglas, Australia, 2005.

D. Prasser, G. Wyeth, M. J. Milford (2004a), "Biologically Inspired Visual Landmark Processing for Simultaneous Localization and Mapping," International Conference on Intelligent Robots and Systems, Sendai, Japan, 2004

M. J. Milford, G. Wyeth, D. Prasser (2004a), "RatSLAM: A Hippocampal Model for Simultaneous Localization and Mapping," International Conference on Robotics and Automation, New Orleans, United States, 2004.

M. J. Milford, G. Wyeth, D. Prasser (2004b), "Simultaneous Localization and Mapping from Natural Landmarks using RatSLAM," Australian Conference on Robotics and Automation, Canberra, Australia, 2004.

D. Prasser, G. Wyeth, M. J. Milford (2004b), "Experiments in Outdoor Operation of RatSLAM," Australian Conference on Robotics and Automation, Canberra Australia, 2004.

M. J. Milford and G. Wyeth (2003), "Hippocampal Models for Simultaneous Localisation and Mapping on an Autonomous Robot," Australian Conference on Robotics and Automation, Brisbane, Australia, 2003.

D. Prasser and G. Wyeth (2003a) "Laboratory Vision System for Simultaneous Localization and Mapping" Proceedings of the Second International Symposium on Autonomous Minirobots for Research and Edutainment. Brisbane. 2003.

D. Prasser and G. Wyeth (2003b) "Probabilistic Visual Recognition of Artificial Landmarks for Simultaneous Localization and Mapping" Proceedings of the 2003 IEEE International Conference on Robotics and Automation. Taipei. 2003.

D. Prasser, and G. Wyeth (2003c) "Representation and learning of visual information for pose recognition" Proceedings of the 2003 Australasian Conference on Robotics & Automation. Brisbane. 2003.

B. Browning (2000) "Biologically Plausible Spatial Navigation for a Mobile Robot", Ph.D. Thesis, Computer Science and Electrical Engineering Department, University of Queensland, Australia, 2000.

G. Wyeth and B. Browning (1998) "Cognitive Models of Spatial Navigation from a Robot Builder's Perspective", Adaptive Behaviour, MIT press, Volume 6, Issue 3/4, pp.509-534.

Other References

Arleo A., (2000) "Spatial Learning and Navigation in Neuro-Mimetic Systems: Modeling the Rat Hippocampus" in Information Science. Milan: University of Milan, pp. 198.

O'Keefe, J. and Nadel, L. (1978), "The hippocampus as a cognitive map", Oxford University Press

Redish, A.D. (1997) "Beyond the Cognitive Map: Contributions to a Computational Neuroscience Theory of Rodent Navigation" PhD Thesis, Computer Science Department and the Center for the Neural Basis of Cognition, Carnegie Mellon University, Pittsburgh, USA.

Redish, A. D. (1999), "Beyond the Cognitive Map: From Place Cells to Episodic Memory", MIT Press.