AI Glossary / Graphs and symbolic AI / Intermediate
Exact cell decomposition
Definition
Exact cell decomposition is a motion-planning approach that partitions the collision-free configuration space into cells while preserving its relevant geometry and connectivity. A planner connects neighboring cells and searches the resulting graph for a route. Under the method's modeling and algorithmic assumptions, valid routes are not lost merely because a coarse grid missed them.
What it means
A configuration describes the robot's position and, when relevant, orientation or joint settings. Configuration space collects those possibilities. Its free region contains configurations that avoid the modeled obstacles.
Cell decomposition divides that free region into simpler pieces. Cells should support easy internal motion and have well-defined connections to adjacent cells. Exact decomposition represents the free region faithfully within the specified mathematical model, rather than approximating every boundary with a chosen grid size.
The word exact does not mean that a floor plan or sensor measurement perfectly describes reality. It also does not promise a shortest path. The principal purpose is to preserve the existence and connectivity of feasible motions while turning a continuous problem into a manageable discrete search.
How it works
First construct the configuration-space obstacles, accounting for the robot's shape and allowed motions. A point robot in a two-dimensional polygonal map is a particularly accessible case.
One method extends vertical segments from obstacle vertices through free space until they reach another boundary. The resulting regions are triangles or trapezoids, with connecting boundary segments represented appropriately. Convex cells allow their interior points to be connected by straight lines.
The planner records adjacency and builds a roadmap with collision-free connections through the cells. It locates the start and goal, connects them to this representation, and searches for a route.
Correct treatment of boundaries and geometric special cases is essential. A shared obstacle corner is not automatically a traversable passage. More complex robot motions can create high-dimensional or curved obstacle regions, making exact decomposition considerably harder than the simple planar illustration suggests.
Three practical examples
1. A geometric planner determines whether a point-like agent can pass between two locations in a precisely specified polygonal map.
2. A design tool examines whether a translating part can move through a modeled workspace after accounting for the part's physical extent in configuration space.
3. A robotics course compares a cell-based roadmap with a fixed grid, showing how a narrow corridor can disappear under coarse discretization even when the geometric model permits passage.
Think of it this way
Think of dividing a building's usable floor area into simple rooms and recording the doorways that connect them. Planning becomes choosing a sequence of rooms and crossing their connecting openings.
The analogy is limited because mathematical cells are artificial subdivisions, not necessarily real rooms. A robot's configuration space can also have dimensions for orientation or joints, so it cannot always be understood as an ordinary floor plan.
Worked example
Consider a point robot inside the open rectangle 0 < x < 10 and 0 < y < 6. A closed rectangular obstacle occupies 4 ≤ x ≤ 6 and 2 ≤ y ≤ 4. Touching the obstacle is forbidden.
Partition the free region into four two-dimensional cells: the left region with x < 4, the right region with x > 6, the lower middle region with 4 < x < 6 and y < 2, and the upper middle region with 4 < x < 6 and y > 4. All cells also obey the workspace bounds.
Four open vertical interface segments connect these regions at x = 4 and x = 6, below y = 2 or above y = 4. Including these interfaces preserves the free region instead of accidentally deleting the crossings.
A start at (2, 3) can reach a goal at (8, 3) through the lower cells. For example, the waypoint sequence (2, 3), (3, 1), (5, 1), (7, 1), (8, 3) remains collision-free along every connecting straight segment.
The direct horizontal segment at y = 3 crosses the obstacle. The cell route demonstrates feasibility, not shortest-path optimality. This hand-built decomposition illustrates the principle rather than claiming to execute a general decomposition algorithm.
Illustrative case study
Fictional case: Mica Automation tests a geometric planner for moving a flat component across a work surface. Its first demonstration treats the component as a point and finds a passage through a gap.
The team then constructs obstacles for the actual component geometry and discovers that the passage is unavailable for the allowed motion. It retains the cell-decomposition method but corrects the model. The case illustrates that exact reasoning about an oversimplified free space can still produce an operationally unsuitable route.
Common misconceptions and mistakes
Do not confuse exact decomposition with a sufficiently fine occupancy grid. Grid refinement can improve approximation without making it the same mathematical representation.
Do not connect cells merely because their closures touch at an obstacle point. The connection must correspond to permitted motion.
Avoid assuming that graph-search optimality implies geometric shortest-path optimality. The graph and its edge costs determine what the search optimizes.
Finally, do not extend a two-dimensional polygonal construction unchanged to arbitrary rotating robots. Their configuration-space obstacles can have substantially different geometry.
Business use
Exact cell methods can help when geometric correctness within a stable model is central and the problem structure supports tractable construction. They are particularly instructive for understanding what a roadmap must preserve.
Assess decomposition cost, numerical robustness, update requirements, and dimensionality before selecting an implementation. Separate geometric feasibility from clearance margins, dynamics, timing, and execution control. Those additional requirements may need a richer model or later validation rather than being implied by a collision-free path.
People also ask
Does exact mean a real robot cannot collide?
No. The guarantee concerns the modeled geometry and assumptions; sensing and execution errors remain separate issues.
Are all cells squares?
No. Planar methods may use triangles or trapezoids, and other decompositions use different cell forms.
Does a route through cells have minimum length?
Not automatically. Feasibility and shortest-path optimization are distinct requirements.
Check your understanding
In the example, can the robot use the direct segment from (2, 3) to (8, 3)?
Answer: No. It passes through the obstacle for x between 4 and 6. A route above or below the obstacle is needed.
Related terms
- Configuration space
- Free space
- Motion planning
- roadmap
- vertical decomposition
- convex cell
- adjacency
- approximate cell decomposition
Learn next
Study configuration-space obstacles first, then draw the worked example with separate interior cells and connecting segments. Compare its connectivity with a coarse occupancy grid and explain which passages a grid representation can miss.
More in Graphs and symbolic AI
- Evolutionary algorithms - Evolutionary algorithms are a family of search and optimization methods inspired by variation and selection in biological evolution.
- Evolutionary strategies - Evolutionary strategies, commonly called evolution strategies or ES, are optimization methods that improve candidate solutions through variation...
- Evolving intelligent system - An evolving intelligent system is a learning system that can adapt its internal structure as new data arrive, as well as update numerical parameters.
- Execution - Execution is the process of carrying out selected actions or instructions.
- Exhaustive decomposition - An exhaustive decomposition describes a category using subcategories whose combined membership covers the whole category.
- Existence uncertainty - Existence uncertainty is uncertainty about whether a modeled object, event, or relationship actually exists.
Sources
Primary source: Steven M. LaValle, Planning Algorithms, Chapter 6, especially vertical cell decomposition and roadmaps: https://lavalle.pl/planning/ch6.pdf
Scope is geometric motion planning. The rectangular example, waypoint checks, and fictional case are original; exactness is explicitly limited to the stated model.
Previous: Exact algorithm Next: Exact match