| --- |
| library_name: kernels |
| license: apache-2.0 |
| tags: |
| - simulation |
| - slime-mold |
| - shortest-path |
| - network-design |
| - agent-based |
| - neon |
| - aarch64 |
| --- |
| |
| # physarum |
|
|
| *Physarum polycephalum* (slime mould) on the CPU, loadable through |
| `kernels`, two ways: an agent model that grows the organic transport |
| networks the organism forms, and a flow solver that finds shortest paths and |
| builds networks by the Tero adaptive-conductivity model. The reference |
| baselines are breadth-first search, Dijkstra, and the terminals' minimum |
| spanning tree, matched exactly on length. |
|
|
| Slime mould solves routing problems by growing: it thickens the tubes that |
| carry flux and abandons the rest, and the surviving network is a shortest |
| path or an efficient multi-terminal network. This kernel runs both |
| formulations fast enough to be interactive on a Raspberry Pi, so the |
| biological algorithm becomes a usable network-design tool, including one |
| thing the classical algorithms do not give: a network that survives any |
| single edge cut. |
|
|
|  |
|
|
| *1200x1200 field, 680k agents, on a Raspberry Pi 4.* |
|
|
| ## Usage |
|
|
| ```python |
| import torch |
| from kernels import get_kernel |
| |
| physarum = get_kernel("phanerozoic/physarum", version=1, trust_remote_code=True) |
| |
| open_mask = physarum.maze(127, 127, seed=5) # 1 = open, 0 = wall |
| solver = physarum.PhysarumFlow(open_mask) |
| solver.solve([(2, 2), (124, 124)], [1, -1]) # a source and a sink |
| path = solver.path((2, 2), (124, 124)) # [(x, y), ...], the route |
| |
| sim = physarum.Physarum(width=1024, height=1024, agents=200_000, seed=0) |
| for _ in range(400): |
| sim.step() |
| img = sim.image() # [H, W, 3] uint8, inferno colormap |
| ``` |
|
|
| `version` selects the release branch; `trust_remote_code` is required by |
| `kernels` for publishers without the trusted-publisher mark. |
|
|
| ## API |
|
|
| | Symbol | Purpose | |
| |---|---| |
| | `PhysarumFlow(open_mask)` | flow solver; `.solve(terminals, inject)`, `.solve_robust(terminals)`, `.network(thresh)`, `.path(a, b, thresh)` | |
| | `maze(height, width, seed)` | a recursive-division maze as a `[H, W]` open/wall mask | |
| | `Physarum(width, height, agents, seed, sense_dist, sense_ang, turn, speed, deposit, decay)` | agent simulation; `.step(n)`, `.image(gamma, percentile)`, field `.trail` | |
| | `flow_cg(cE, cS, b, p, ground, max_iters, tol)` | one Jacobi-PCG solve of the weighted-Laplacian flow, `p` in place | |
| | `physarum_step(trail, tmp, ax, ay, ah, seed, ...)` | one agent-model step | |
|
|
| ## Method |
|
|
| The flow solver follows Tero et al. (2010): current flows between terminals |
| on a masked grid, each step reinforces high-flux edges and lets the rest |
| decay, so the conductivities converge onto the shortest path (one source and |
| sink) or an efficient network (several terminals). The inner step is a |
| weighted-graph-Laplacian solve exposed as `flow_cg`, Jacobi-preconditioned |
| conjugate gradients over a NEON 5-point mat-vec. |
|
|
| The agent model follows Jones (2010): each agent samples the field at three |
| sensors (ahead, and +/- `sense_ang` at `sense_dist` px), rotates by `turn` |
| toward the strongest, moves `speed` px, and deposits `deposit`; the field is |
| then convolved with a separable 3-tap [1 2 1]/4 kernel and multiplied by |
| `decay`. The agent update runs across cores via `at::get_num_threads()`, and |
| agents are counting-sorted into 32px tiles every eight steps so consecutive |
| and same-core agents sense a hot window rather than scattering three gathers |
| across the field. The step is deterministic for any thread count. |
|
|
| ## Measured |
|
|
| Flow solver, single-core solve time (200 adaptation steps, `flow_cg`): |
|
|
| | host | 127x127 maze | 140x140 hub + 6 network | |
| |---|---|---| |
| | Pi 4 (Cortex-A72, 1.8 GHz) | 4.0 s | 4.9 s | |
| | Pi 5 (Cortex-A76, 2.4 GHz) | 1.2 s | 1.4 s | |
|
|
| CG is sequential and the grids are modest, so the solve is vectorised but |
| not threaded; the mat-vec is a 5-point weighted stencil in gather form. |
|
|
| Agent model, 1024x1024 field, 200k agents (NEON, tile-sorted): |
|
|
| | host | 1 core | 4 cores | |
| |---|---|---| |
| | Pi 4 (Cortex-A72, 1.8 GHz) | 37 fps | 62 fps | |
| | Pi 5 (Cortex-A76, 2.4 GHz) | 74 fps | 165 fps | |
|
|
| ## Comparison with classical algorithms |
|
|
| `benchmark.py` compares the solver to breadth-first search, Dijkstra, and |
| the terminals' minimum spanning tree on a 4-connected grid, averaged over |
| random configurations: |
|
|
| | problem | classical | physarum | |
| |---|---|---| |
| | shortest path (maze) | BFS optimal | equal length, exact | |
| | connect N terminals (length) | MST | spanning-tree length | |
| | survive any single edge cut | a tree cannot | 2-edge-connected network | |
|
|
|  |
|
|
| The flow model converges to the shortest path for a single source and sink, |
| reproducing Dijkstra's length exactly (Dijkstra is faster in time). `solve` |
| connects several terminals with a network of spanning-tree length; |
| `solve_robust` reinforces the flux over every terminal pair to build a |
| network that survives any single edge cut. |
|
|
| ## Requirements and limits |
|
|
| - float32, CPU. NEON on aarch64; portable scalar elsewhere. |
| - Flow solver: 4-connected grid, one node grounded for the gauge; |
| deterministic. |
| - Agent model: threaded update (`torch.set_num_threads`), serial deposit and |
| diffusion, deterministic for any thread count. |
| - Behavioural and phenomenological models of Physarum, not biophysical ones. |
| - `get_kernel` loads a prebuilt aarch64 or x86_64 variant for torch |
| 2.11-2.13; for other torch versions, `load_local.load()` JIT-compiles the |
| same source. |
|
|
| ## References |
|
|
| Tero et al., "Rules for biologically inspired adaptive network design" |
| (Science, 2010); Jones, "Characteristics of pattern formation and evolution |
| in approximations of Physarum transport networks" (2010). |
|
|
| ## License |
|
|
| Apache-2.0. |
|
|
