Is skeletonization one specific algorithm?

No. In this planning context, it describes a family of graph-based representations and methods.

Does the graph contain every free configuration?

Usually not. It selects representative configurations and connections.

Does failure to find a graph path prove the task impossible?

Only if the construction and search provide the relevant completeness guarantee; a sparse roadmap alone does not.

AI Glossary / Graphs and symbolic AI / Intermediate

Skeletonization

Definition

In robot path planning, skeletonization represents navigable configuration space using a graph of selected configurations and feasible connections. A planner connects the start and goal to this roadmap and searches the graph for a route. The graph is a simplified planning structure, not a complete list of every possible configuration.

What it means

This entry follows the supplied glossary's robotics meaning. Image-processing skeletonization, which thins shapes into narrow structures, is a related-sounding but distinct use of the word. In planning, the central purpose is to replace a continuous navigation problem with a manageable graph search.
A configuration may describe a robot's position, orientation, or joint angles. Free configuration space contains configurations that avoid modeled obstacles. A useful skeleton captures ways of moving through that space, including the connections needed to travel between relevant regions. A graph drawn over a map is only useful if its edges correspond to valid movements.

How it works

Construct representative configurations and local connections through free space. Geometric approaches can use structures related to obstacle boundaries, such as a Voronoi roadmap that favors clearance. Sampling-based approaches, such as probabilistic roadmaps, use sampled configurations and checked local connections.
For a query, attach the start and goal through feasible connectors, search the roadmap, and translate the resulting edge sequence into a path. The method's guarantees depend on the construction. A sparse sampled roadmap can miss a narrow passage, while a graph path can become invalid if the environment changes. Geometry, robot size, and movement constraints must remain consistent throughout.

Three practical examples

A mobile-robot simulator can plan repeated journeys through a fixed floor layout using a reusable roadmap.
A robotic-arm planning demonstration can search connections among collision-free joint configurations.
A navigation lesson can compare a clearance-oriented roadmap with a shorter route that passes closer to an obstacle.

Think of it this way

Think of a transport diagram that reduces a large city to junctions and connecting routes. It leaves out most possible positions but preserves useful ways to travel. The analogy is limited because a roadmap edge must be validated against the robot's geometry and motion rules; a line on a diagram does not make a movement feasible.

Worked example

Consider an original geometric example with a point robot in a rectangular room from x = 0 to 12 and y = 0 to 8. A closed rectangular obstacle occupies 4 ≤ x ≤ 8 and 2 ≤ y ≤ 6. The start is S = (1, 4), and the goal is G = (11, 4).
Define four roadmap points: P = (3, 1), Q = (9, 1), R = (3, 7), and U = (9, 7). Include edges S - P, P - Q, Q - G, S - R, R - U, and U - G. Each segment stays inside the room and avoids the obstacle. The horizontal connections pass below or above it, while the slanted connectors remain to its left or right.
The lower graph route S - P - Q - G has length sqrt(13) + 6 + sqrt(13), about 13.211. The upper route has the same length by symmetry. The direct S - G segment has length 10 but crosses the obstacle and is invalid.
Graph search can therefore choose either of the two valid roadmap routes. This does not prove that either is the shortest possible continuous-space route: the chosen roadmap contains only selected connections. Nor does the example establish validity for a robot with nonzero size. Such a robot requires obstacle and boundary handling that accounts for its shape and orientation. The simple graph illustrates the planning abstraction, not an exact Voronoi construction.

Illustrative case study

In a fictional case, Rowan Logistics develops a virtual cart-navigation demonstration. The team builds a roadmap for a static arrangement of shelves and successfully finds graph routes between several stations. When a temporary display blocks one connection, the old graph still reports a route unless that edge is checked or updated.
Engineers mark the affected connection unavailable and rerun the query. They also distinguish “no path in this roadmap” from “no physical route exists,” because the graph may omit another corridor. The case illustrates maintenance of the representation rather than a claimed deployment result.

Common misconceptions and mistakes

A roadmap is not necessarily a geometric centreline or the medial axis. Different construction methods prioritize different properties. A graph route is not automatically a shortest route in continuous space, and a shortest geometric path is not automatically dynamically executable.
Do not confuse robot workspace with configuration space. An arm's joint-angle path can be collision-free only after considering the whole arm, not merely its end-effector location. Also, disconnected roadmap components may reflect insufficient sampling rather than disconnected free space. Completeness claims must be tied to the particular method and assumptions.

Business use

Business teams considering robotic movement can use skeletonization to understand how continuous geometry becomes a route-planning problem. It is particularly helpful when explaining reusable planning structures and why map updates can invalidate earlier routes.
Evaluate construction time, query time, collision-checking cost, route quality, and failure cases. Document whether the roadmap captures a static scene, how temporary obstacles are handled, and what constitutes a valid connection. A visually neat graph should not replace checks of robot clearance and executable motion.

Check your understanding

Why is the direct S - G connection excluded from the example?

Answer: It crosses the rectangular obstacle, even though both endpoints are in free space.

Related terms

Learn next

Remove edge P - Q while leaving the other edges unchanged. The upper route S - R - U - G remains available. Then explain why removing both horizontal edges disconnects this particular graph without, by itself, proving that the room has no feasible route.

Sources

Sources: Russell and Norvig, original AIMA robotics slides, configuration-space planning and skeletonization: https://aima.cs.berkeley.edu/4th-ed/slides-pdf/chapter25-6pp.pdf . LaValle, Planning Algorithms, maximum-clearance roadmaps: https://msl.cs.illinois.edu/~lavalle/planning/node270.html . Original AIMA glossary context: https://raw.githubusercontent.com/aimacode/aima-glossary/master/sentences.txt .

Previous: Size (statistics) Next: Sketching