From Vacuums to Taxis: What Makes a Routing Problem Hard for Robots
Vacuum robots and self-driving taxi robots navigate physical spaces and avoid obstacles. That’s a super broad characterization. The more interesting question is why everything else about them is so different.
My friend was telling me recently about riding in a Waymo in Los Angeles, and we started discussing how they gathered data to know where to go. I mentioned that I’d been writing a series on geolocation and routing algorithms, and he hadn’t seen any of those posts. What followed was a long conversation about how a robot vacuum and a self-driving car appear to solve the same problem, just at different scales. I kept coming back to the same idea: the algorithms aren’t that different. What changes is the constraints.
The Shared Foundation
Both systems need to get from one place to another without hitting anything. Both maintain a model of their environment. Both detect obstacles and replan. In my post on robot vacuum pathfinding, I walked through how a vacuum robot uses SLAM to build a map, boustrophedon decomposition to plan coverage, and A* to navigate home. Those algorithms (occupancy grids, heuristic search, incremental replanning) show up in road routing too. The foundation is shared; the constraints are not.
State Space Size and Structure
State space refers to all of the situations the these robots can be in, and how it can move between these states. For a vacuum robot, this state space is fixed, and generally flat and rectangular. The state space for a taxi robot is much larger and open-ended with various road segments.
The vacuum robot operates in a closed environment. Your living room might be a few hundred square feet. The graph it navigates is a dense occupancy grid, typically a few thousand cells. The robot knows the edges of its world. When it reaches a wall, that’s the boundary of its state space.
A vehicle operates in a semi-open world (generally constrained to roads). A single trip might cover dozens of road segments, each connecting to others indefinitely. Waymo’s planning system works across multiple layers at once: route planning at the road network level, behavior planning for decisions like when to yield or change lanes, and motion planning for the precise trajectory the vehicle follows second by second, as described in Waymo’s safety documentation. The road network underlying route planning looks much more like what pgRouting works with than anything a vacuum robot encounters.
Grid-based graphs work when the space is bounded and the resolution can be fixed. Sparse road network graphs work when the space is effectively unbounded and the meaningful nodes are intersections. For large environments, occupancy grids break down under their own scale.
Dynamic Obstacles and Prediction
The vacuum robot’s obstacles are mostly furniture. Furniture doesn’t move much. When something does move (a pet, a person’s foot), the vacuum handles it reactively. It detects the obstruction, updates its occupancy grid, and replans its route. Reactive replanning is fine when your obstacles are slow-moving and your vehicle is slower. (Hat tip to our dog who learned how to boop our Roomba button off because he didn’t like this “reactive” bumping.)
A self-driving taxi can’t be purely reactive. A pedestrian stepping off a curb is not an event you respond to after it happens. By the time a sensor detects contact, you’re already past the point where you needed to act. The planning system has to predict where other entities are likely to be, not just where they are now. Modeling the probable trajectories of pedestrians, cyclists, and other vehicles, with enough confidence to act on, is a problem with no equivalent in a robot vacuum. Waymo describes this prediction layer as one of the core challenges in the system in their AI and ML overview.
The technical distinction is between reactive navigation (respond to what you observe) and deliberative navigation (predict what will happen and plan around it). Both are valid. The right choice depends on how fast your world moves relative to your vehicle.
Real-Time Constraints
A vacuum robot moves at roughly 0.3 meters per second. If replanning after an obstacle takes a few seconds, nothing bad happens. It can stop, think, and continue.
A road vehicle will travel at city and highway speeds. At 30 mph, that’s about 14 feet per second. A replanning cycle that takes half a second costs you six and a half meters of travel. That’s not a delay. That’s a gap in your safety envelope.
Meeting that latency budget requires more than a fast algorithm. Sensor fusion (combining lidar, radar, camera, and GPS data into a single world model) runs continuously and in parallel with prediction and planning. These are separate computational pipelines, each with strict latency requirements, coordinating outputs under real-time constraints. It is an orchestration problem as much as an algorithmic one, and the kind of distributed systems challenge that has nothing to do with which shortest-path algorithm you chose.
Safety Requirements and Failure Cost
A vacuum bumping the couch costs you nothing. One falling down the stairs is why cliff sensors exist. Not detecting dog poop on the floor… okay, I won’t share that experience. These are engineering problems. They are not life-safety problems.
A vehicle contacting a pedestrian is in a different category entirely. Safety requirements here don’t just tighten the margins on normal engineering practice. They change the architecture. Waymo’s approach, described on their safety page and in their research on safe AI, includes redundant sensor systems so no single failure causes blindness, formally defined safety envelopes the vehicle must stay within, and conservative fallback behaviors for any situation the system isn’t confident about. When the system doesn’t know what to do, it slows down or stops. It doesn’t guess.
A robot vacuum that is uncertain about a new floor layout can bump its way to understanding. A car that defaults to bumping its way around is not something you put on a public road.
The Fleet as a Learning System
Here is where the two systems diverge in a way that gets less attention than the algorithms.
A self-driving vehicle typically collects sensor data continuously during every trip. Lidar sweeps, camera footage, radar readings: all of it, from the environment around them, every time a vehicle is operating. Interior cameras also monitor the cabin, and according to Waymo’s documentation on cameras and data use, the company is preparing to use interior camera data for AI model training as well.
The data that these sensors produce is also how the system gets better. Waymo’s learning approach is described in their machine learning blog post: real-world fleet data surfaces edge cases, those edge cases feed into simulation, simulation generates more training data, models improve, and improved models go back into the fleet. There is no substitute for real-world autonomous experience. No amount of simulation alone replicates what the system encounters in the real world.
One key difference is the range of data collected. While most vacuum robots also collect floor plan data, an exterior sensor sweep of a self-driving car observes vehicles and pedestrians who haven’t consented to being recorded. Whether that constitutes surveillance is a fair question, and one that regulators and researchers are actively working through.
What the Constraints Tell You
The five dimensions (state space structure, obstacle dynamics, real-time latency, safety requirements, and continuous learning from real data) matter for routing problems in databases and distributed systems too, at smaller stakes. The algorithms don’t change much, whether they run on an occupancy grid, a road network, or a warehouse floor. What changes is which constraint dominates: scale, speed, safety, or data.
That’s the question worth asking before you choose an algorithm. Not “which pathfinding approach?” but “what actually makes this problem hard?”
If you’re building up the foundation, my posts on A* in pgRouting, robot vacuum pathfinding, and routing APIs compared cover the algorithmic pieces in more detail. And if you’re working on a routing or navigation problem of your own, autonomous or otherwise, drop me an email. I’d love to hear about the constraints in your use case.
