Ant Colony Pathfinding 3D

A Blender garden: ants walk tours between flower beds, trails glow where pheromone is strong.

Presets

Playback

Camera

Layers

Quality

Model check

The science

Ants as a search algorithm

Real ants find short routes because each ant lays pheromone while it walks and later ants prefer stronger trails; shorter routes are completed more often per unit time, so they gain more pheromone, while unused trails evaporate. Ant colony optimisation (Dorigo, 1992) turns this into an algorithm for the travelling-salesman problem: visit N cities once each and return, with the shortest total length L. The number of different tours is (N − 1)! / 2 (about 1.8×1015 for 18 cities), so exhaustive search is hopeless and a heuristic is needed.

The rules (Ant System)

An ant standing in city i chooses the next unvisited city j with probability pij = τijα ηijβ / Σk τikα ηikβ, where τ is the pheromone, η = 1/dij the visibility and α, β their weights. After all m ants have built a tour, the trails are updated: τij ← (1 − ρ) τij + Σk Δτijk with Δτkij = Q / Lk (here Q = 1) on every edge of ant k's tour. The evaporation rate ρ keeps the colony from freezing on early, poor tours: without deposits a trail decays exactly as τ0(1 − ρ)t.

Variants

Elitist adds e Q / Lbest on the best-so-far tour every iteration. Max-Min Ant System lets only one ant deposit (the iteration best, every fifth iteration the best so far) and clamps all trails to [τmin, τmax with τmax = 1/(ρ Lbest), which prevents stagnation.

What the graphs show

The branching factor counts, for each city, the edges whose trail exceeds τmin + 0.05(τmax − τmin); it falls towards 2 (one tour: each city keeps its two neighbours) as the colony converges. The reference length is the exact optimum from the Held-Karp dynamic programme for 13 cities or fewer (2N N2 operations), otherwise the best of the 2-opt-polished nearest-neighbour tours, which is a good but not proven bound. For random uniform tours the expected length is exactly N times the mean pairwise distance, a baseline the ants must beat.

Honest simplifications

The ants of one iteration walk simultaneously and the trails are updated when they return (the animation shows the tours that update was computed from). Real ants do not know the whole map, deposit continuously and cannot compute a tour length; the model keeps only the part that explains the optimisation: positive feedback, evaporation and a greedy bias. For 40 cities the result is a heuristic, not a proof of optimality.

Loading model...
Loading Blender model...
Tour length against iteration
Branching factor (trail diversity)
Tour lengths of this iteration
Made with 🟠 Blender · Three.js