A swarm that maps a building it has never seen

Why we built it

It is a demo rather than a product. Our results usually run quietly in the background of systems we are not allowed to name, which makes “what have you done?” an awkward question to answer honestly. Showing the reasoning is easier than describing it.

Since we had worked on similar planning problems before, this became a summer internship project with support from the team. Our interns get real technical problems rather than decorative side quests, and this one shipped.

The problem

Several agents, each carrying a LIDAR scanner, are dropped into an environment nobody has mapped. They share what they see. To explore it well, the system needs a representation of the environment that updates as observations arrive and a planner that can decide where to go next without spending a minute on each step.

Three challenges follow from that. Representing known space and the reachable unknown in a form you can plan over. Finding paths into it that keep a safe distance from the walls. Coordinating several agents so they do not all chase the same corridor.

How it works

Scans become an occupancy grid of free, blocked, and unknown cells. For every cell we compute the distance to the nearest obstacle, giving a distance field that reads like a terrain map where height means clearance. The ridges of that field run down the middle of the navigable space, and those are the safest routes through it.

The ridges are dense and noisy, so we sample them down to the points that matter: junctions, and places representing a large area of free space. Each surviving point is a circle of clear space as wide as its distance to the nearest obstacle. Connect the circles that overlap and the result is a sparse roadmap on which travelling between centres is safe by construction. Corridors become chains of small circles, open halls a few large ones. The approach follows the Skeleton Disk-Graph Roadmap of Noël et al. (2023).

Exploring is then a choice between the roadmap nodes that border unknown space, the frontier nodes. Each is scored on what it costs to reach and how much new area it is likely to reveal, the best one wins, and Dijkstra or A* draws the path. For several agents we use prioritised planning: agents plan in sequence, each taking the earlier plans into account. It is not the optimal joint solution, and it turns a problem that grows exponentially with the number of agents into a series of nearly single-agent ones.

What it is made of

A Python backend runs the simulation loop and the planner, a FastAPI server sits between the halves, and a React, TypeScript, and Three.js frontend provides two views. The demo control view is for dropping obstacles into the world. The supervisor view shows what a real operator would monitor.

The planner is deliberately separate from the simulation. The planner controls the robots and the simulation owns the environment, so the planning system can be lifted out and used somewhere that is not a simulation.

What we took from it

Papers need adapting. We added a distance threshold to stop skeleton points appearing too close to walls, which would otherwise have produced paths that were safe on paper and not in the corridor.

There was a practical lesson in large language models as well. Generating large blocks of code with them moves quickly at the start and is painful to live with later. We ended up using them for small, isolated pieces and keeping architectural control in human hands.

If you have an R&D project involving simulation, planning logic, or algorithm-heavy systems, and you are a few steps away from something that works, this is the kind of gap we close.