Alex Goldhoorn

SLAM with Growing Neural Gas (GNG)

This simulation demonstrates the mapping component of my Bachelor's thesis (2006) on using Growing Neural Gas networks for SLAM (Simultaneous Localization and Mapping).

1. What is SLAM?

SLAM is the fundamental problem in mobile robotics: a robot must simultaneously:

• Map the environment (build a representation of unknown surroundings)
• Localize itself within that map (determine its own position)

This is a chicken-and-egg problem: you need a map to localize, but you need to know your position to build an accurate map. SLAM algorithms solve this by maintaining probabilistic estimates of both simultaneously.

2. Traditional SLAM Approaches

Common methods in 2006 (when this work was done) included:

• Grid-based (Occupancy Grids): Discretize space into cells, each storing probability of being occupied. Memory-intensive and struggles with large environments.
• Feature-based (EKF-SLAM): Extract and track geometric features (corners, lines). Requires careful feature extraction.

3. Growing Neural Gas for Mapping

Instead of using fixed grids or handcrafted features, this approach uses a self-organizing neural network called Growing Neural Gas (GNG). The network dynamically adapts its structure to represent the environment.

How GNG Works

GNG is an unsupervised learning algorithm that maintains a graph of nodes and edges:

• Input: Sensor measurements (e.g., lidar hit points from obstacles)
• Adaptation: The nearest node ("winner") moves towards the input signal
• Topology Learning: Edges connect nodes that respond to similar inputs, learning the shape of obstacles
• Growth: When a node accumulates high error (distance from inputs), the network spawns a new node to better cover that region
• Pruning: Edges that become too old (unused) are removed, allowing the network to forget outdated structure

4. Key Advantages

• Adaptive Resolution: The network automatically allocates more nodes to complex regions (doorways, corners) and fewer to simple walls.
• Compact Representation: Uses far fewer nodes than a grid to represent the same environment.
• Topology Preservation: The network structure reflects the actual shape of obstacles, not just their presence.
• Incremental Learning: Can update the map online as the robot explores, without recomputing from scratch.

5. The Algorithm in the Simulation

In this interactive demo:

• The Robot (Blue): Equipped with simulated lidar sensors that measure distance to walls.
• Yellow Rays: Lidar beams scanning the environment.
• Red Dots: Points where rays hit obstacles. These are the "training signals" for the GNG network.
• Green Network: The GNG nodes (circles) and edges (lines) that learn to represent the environment's structure.

6. Parameters

The GNG algorithm has several tunable parameters (visible in the code):

• maxEdgeAge (70): How many iterations before an edge is removed.
• epsilonB (0.2): Learning rate for the winner node.
• epsilonN (0.006): Learning rate for neighbors of the winner.
• lambda (100): Frequency of adding new nodes (every 100 inputs).

7. Bachelor Thesis Context

This work was part of my Bachelor's thesis at the University of Groningen (2006), where I explored using self-organizing neural networks for mobile robot SLAM. The thesis compared GNG-based mapping with traditional grid-based approaches, demonstrating advantages in memory efficiency and adaptive resolution.

8. Modern Developments

Since 2006, SLAM has evolved significantly with methods like FastSLAM, ORB-SLAM, and LiDAR-based approaches. However, the core concept of using adaptive, self-organizing structures for efficient map representation remains relevant, particularly in resource-constrained systems and for topological mapping.

Try the Simulation Back to Tools