Does a Voronoi route always minimize distance?

No. Clearance-oriented routes can be longer than direct feasible routes.

Are start and goal automatically on the graph?

Usually not. Valid connecting motions must be provided.

Is this identical to graph Voronoi cells?

No. Graph cells assign vertices to centers; this robotics roadmap follows a geometric free-space skeleton derived from obstacle distances.

AI Glossary / Graphs and symbolic AI / Intermediate

Voronoi graph

Definition

A Voronoi graph is a roadmap derived from locations that are equally close to two or more nearest obstacles or obstacle-boundary features. In robot motion planning, it forms a skeleton of free space along which a planner can search for routes. Its attraction is obstacle clearance: the roadmap tends to run between obstacles rather than closely following their edges.

What it means

The graph reduces a geometric environment. Junctions and connecting branches capture possible ways through free space, while start and goal configurations must be connected to the roadmap by valid motions.
This robotics meaning differs from assigning ordinary graph vertices to their nearest service center. Here the relevant sites are obstacle features, and the roadmap follows boundaries between nearest-feature regions. The word nearest is essential. Being equally distant from two faraway obstacles does not place a point on the useful roadmap if a third obstacle is closer or the point is not in free space.

How it works

Represent obstacles and the robot's collision-free configurations. Construct the relevant generalized Voronoi structure or an approximation, identify its branches and junctions, and turn those into a searchable roadmap. Connect the initial and target configurations to that roadmap with collision-free paths.
Search the graph for a suitable route and translate its edges back into motions. The planner must account for robot size, motion constraints, and map accuracy. A geometric skeleton alone does not guarantee that a vehicle can execute every curve. Depending on the construction and assumptions, the roadmap can preserve useful connectivity while trading direct path length for additional clearance.

Three practical examples

A mobile-robot simulation can use a Voronoi roadmap to plan routes through corridors between obstacles.
A map-analysis exercise can identify junctions where several free-space branches meet.
A planning comparison can examine the difference between a clearance-oriented roadmap route and a shorter route that passes closer to boundaries.

Think of it this way

Think of walking down the middle of hallways and using their intersections as navigation choices. That network simplifies building navigation. The analogy is limited because mathematical obstacle features may be curved or complex, and a real robot's feasible motion depends on more than the position of a point on a floor plan.

Worked example

Consider an original corridor bounded by two infinite parallel walls at y = 0 and y = 10. Treat the robot first as a point and ignore other obstacles. At a position with 0 < y < 10, the distances to the walls are y and 10 − y.
Equating those distances gives y = 10 − y, so the centerline is y = 5. In this simple environment, that line is the Voronoi roadmap branch between the two walls. Its nearest-wall distance is five.
Let the start be S = (0,2) and the goal be G = (8,2). The direct horizontal route has length eight and remains two units from the lower wall. A route that first connects S to (0,5), follows the centerline to (8,5), and then connects to G has length 3 + 8 + 3 = 14.
The centerline portion has clearance five, greater than the direct route's clearance two. However, the complete roadmap-connected route still has minimum clearance two because its endpoints lie two units from the lower wall. It would be incorrect to say that every point on the full route has clearance five. This distinction separates a roadmap's central segment from its start and goal connectors.
Now model a circular robot of radius one. Its center must remain more than one unit from either wall if contact counts as collision. At y = 5, the robot's body has four units of clearance from each wall. At y = 2, its lower-side clearance is one. A point-robot distance must therefore be interpreted relative to the actual robot geometry.
Finally, insert a rectangular obstacle spanning x from three to five and y from four to six. The old centerline passes through that obstacle. Although points there remain equally distant from the original two walls, they are not valid free-space roadmap points. The obstacle set and nearest-feature relationships must be recomputed.
The skeleton exposes central routes but does not guarantee shortest paths or remain valid after environmental changes.

Illustrative case study

In a fictional indoor-navigation project, a team builds a roadmap from a static obstacle map and uses it to propose corridor routes. Reviewers notice that the robot's turning radius and body width are missing from the initial point model.
The team updates collision and motion checks, then examines start-to-roadmap connections as carefully as the roadmap edges. It also invalidates affected routes when obstacles change. This fictional case illustrates engineering review.

Common misconceptions and mistakes

A Voronoi graph is not simply every geometric location equidistant from any two obstacles. Free-space membership and nearest-obstacle relationships matter. Nor is it generally the same as a visibility graph, whose edges represent direct unobstructed connections between selected features.
Do not assume maximum clearance along one branch proves global path optimality. Do not treat a roadmap found for a point robot as automatically valid for a robot with extent. Finally, discretized map skeletons can introduce artifacts, so their connectivity and clearance need validation against the underlying representation.

Business use

The concept helps teams understand why a navigation system may choose a longer central route instead of a shorter boundary-hugging route. The graph also exposes passages and junctions.
Specify robot geometry, obstacle representation, distance measure, and movement constraints. Evaluate route length, clearance, and execution feasibility separately. If the map is uncertain or changes, define how the system updates or checks the roadmap. The skeleton model must match the application.

Check your understanding

Why is the complete centerline-connected route's minimum clearance only two in the point-robot example?

Answer: Its start and goal are two units from the lower wall, even though the central roadmap segment has clearance five.

Related terms

Skeletonization
Configuration space
Generalized Voronoi diagram
Medial axis
Roadmap
Clearance
Visibility graph
Collision checking

Learn next

Next, move both start and goal onto y = 5 while keeping their x coordinates unchanged and removing the inserted obstacle. The direct route and centerline route now coincide with length eight. Explain why the earlier extra length came from the connectors rather than the centerline itself.

Sources

Primary sources: Russell and Norvig's AIMA robotics source context: https://raw.githubusercontent.com/aimacode/aima-glossary/master/sentences.txt ; Howie Choset, CMU Robotic Motion Planning, introductory generalized-Voronoi construction discussion: https://www.cs.cmu.edu/~motionplanning/lecture/lec15.pdf . The corridor geometry and clearance calculations are original.

Previous: Voronoi cells Next: Voting Classifier