Graph Search on Your Floor: How Robot Vacuums Use Pathfinding Algorithms
I have been writing about shortest-path algorithms and A* heuristics in the context of road networks and pgRouting. But the same graph search concepts show up in a device that millions of people own and never think twice about: the robot vacuum.
A robot vacuum has to solve three problems every time it runs. It needs to figure out where it is, decide where to clean next, and find its way back to the charging dock when it is done. Each of those problems maps to a well-known algorithm family. If you have been following along with Dijkstra and A*, you already have the foundation to understand how a robot navigates your living room.
Building the Map: SLAM and Occupancy Grids
Before a robot vacuum can plan any path, it needs a map. Early vacuums (the original 2002 models) did not build maps at all. They used a stochastic approach: bounce off a wall, turn a random angle, drive straight until hitting something else. It worked eventually, but coverage was unpredictable and slow. I often heard my friends refer to this as the “drunken toddler” method.
Modern robot vacuums often use a technique called SLAM (Simultaneous Localization and Mapping). The concept originated in robotics research in the 1980s and 1990s, with foundational work by researchers including Hugh Durrant-Whyte and John Leonard. Their 2006 tutorial in IEEE Robotics & Automation Magazine remains the canonical introduction to the problem. How can a robot build a map of an unknown environment while simultaneously tracking its own position within that map? Accurate positioning requires a map, and building a map requires accurate positioning.
SLAM solves this by combining sensor data with probabilistic estimation. Depending on the model, the sensors might include a downward-facing camera (what iRobot calls vSLAM), a LiDAR spinner, bump sensors, wheel odometry (counting wheel rotations to estimate distance traveled), and infrared cliff sensors. The robot combines these inputs using probabilistic filters to maintain an understanding about where it is and what the room looks like. A filter takes noisy, imprecise sensor readings and combines them into a single best estimate of the robot’s position, updating that estimate continuously as new data arrives.
The output of SLAM is an occupancy grid: a two-dimensional array of cells, each marked as free, occupied, or unknown. Alberto Elfes described the approach in his 1989 paper in IEEE Computer. Think of it as a bitmap of your floor. Walls, furniture legs, and the neverending piles of shoes by the door show up as occupied cells. Open floor is free. Areas the robot has not reached yet are unknown.
This grid is the graph that everything else operates on. Each free cell is a vertex, and adjacent free cells are connected by edges. The cost of moving between cells is typically uniform (one cell width), though some implementations weight cells near obstacles higher to keep the robot from scraping along walls.
Deciding Where to Clean: Boustrophedon Coverage
Once the robot vacuum has a map, it needs a strategy for visiting every free cell. Random wandering is inefficient. The algorithm most commonly described in robotics literature for this problem is boustrophedon decomposition, a term borrowed from ancient Greek writing that alternated direction line by line, left-to-right then right-to-left. (Bous=ox, strophe=turn, don=like… if you want a good rabbit hole, see https://en.wikipedia.org/wiki/Boustrophedon.)
Howie Choset formalized this idea for robotic coverage in 1997 at Carnegie Mellon, in a paper titled “Coverage Path Planning: The Boustrophedon Cellular Decomposition”. The algorithm divides the free space into regions (cells in the decomposition sense, not grid cells) separated by obstacles. Within each region, the robot drives in straight back-and-forth passes, like mowing a lawn (or driving an ox). When one region is complete, the robot moves to an adjacent uncovered region and repeats.
This is a coverage path planning problem rather than a shortest-path problem, but graphs still drive the solution. The decomposed regions form a graph called an adjacency graph, where each region is a node and edges connect regions that share a boundary. The robot needs to visit every node in this graph, which is a variant of the Traveling Salesman problem. The order in which the robot tackles regions affects total travel time, and planning that order is itself a graph optimization.
During cleaning, the vacuum also handles replanning. If it encounters an obstacle that was not in the original map (like my dog decides to move from his bed to lie in a sunbeam), it updates the occupancy grid and recalculates. This incremental replanning is one of the reasons SLAM runs continuously rather than just once at startup.
Getting Home: Shortest Path on the Grid
This is where the connection to Dijkstra and A* becomes direct. When the vacuum decides to return to its dock, whether because the battery is low or cleaning is complete, it has a known current position and a known dock position on the occupancy grid. It needs the shortest obstacle-free path between them.
The occupancy grid is already a graph. The robot runs a shortest-path algorithm on it. According to published robot vacuum patents and robotics literature, the approach is typically A* or a variant of it. A* is a natural choice here for the same reasons I described in my previous post: the robot knows the geometric position of the dock, so straight-line distance provides a useful heuristic. The algorithm prioritizes cells that are closer to the dock, avoiding the exhaustive all-directions expansion that Dijkstra would perform.
On an occupancy grid, each cell has up to eight neighbors (four cardinal directions plus four diagonals). The cost to move to a cardinal neighbor is 1 cell unit; diagonal moves cost roughly 1.41 (the square root of 2). The heuristic is Euclidean distance from the current cell to the dock cell. A* combines the known cost so far with this estimate and expands the most promising cell at each step, exactly as it does in pgRouting but on a uniform grid instead of a road network.
One important difference from road routing: the vacuums’s grid changes. If the robot mapped a clear path to the dock during cleaning but that dog moved meanwhile, the path is blocked. The robot detects this through its sensors, updates the grid, and replans. Some implementations use D* Lite, an algorithm designed by Sven Koenig and Maxim Likhachev in their 2002 AAAI paper specifically for replanning in partially known environments. D* Lite is an incremental version of A* that reuses previous search results rather than starting from scratch when the graph changes, which makes it faster for the kind of small, frequent updates a robot encounters. This retention of partial knowledge must explain why I have a hard time getting my Roomba to work on multiple floors of the house.
When to Use Grid-Based Pathfinding (and When Not To)
Occupancy grids with A* work well when the environment is relatively small, when the robot needs to replan frequently, and when the graph is dense enough that the grid resolution captures all relevant obstacles.
For large outdoor environments or road networks with thousands of intersections, the grid approach breaks down. A city represented as a fine-grained grid would have millions of cells, most of them inaccessible by a vehicle. Road networks are better modeled as sparse graphs where vertices are intersections and edges are road segments, which is exactly what pgRouting and tools like OSRM and Valhalla are designed for.
What I might be thinking about next: Grid pathfinding also appears in video game navigation, warehouse robotics, autonomous drone flight planning, and any scenario where the environment is bounded and the resolution can be fixed.
