AI Glossary / Graphs and symbolic AI / Intermediate
Cell decomposition
Definition
Cell decomposition is a planning technique that divides a space into regions called cells and represents usable connections between them. A planner can then search a graph of connected cells instead of reasoning directly over every possible continuous position. In robotics, the relevant space is often configuration space, which represents the robot's possible positions and orientations.
What it means
The purpose is to turn a geometric navigation problem into a manageable combination of local movement and graph search. Within a suitable cell, connecting positions should be straightforward. Between cells, the planner needs valid adjacency information and a way to cross their shared connection without collision.
Exact decompositions aim to preserve the free space's relevant structure under their assumptions. Approximate decompositions, such as resolution-limited grids, trade detail for convenience. That distinction matters: failure to find a route in a coarse representation may mean the representation missed a narrow passage, rather than that the physical route does not exist.
How it works
Start with a representation of obstacles and the configurations the robot may occupy without collision. Partition that free region into cells with useful geometric properties, or subdivide a broader region while classifying cells as free, blocked, or unresolved. Construct a graph that connects cells when a valid passage between them is established.
Locate the start and goal in the representation, search for a connecting cell sequence, and construct actual motion segments through it. The local segments must remain valid, not merely join arbitrary cell centers. The decomposition, graph construction, and path extraction together determine the planner's guarantees.
Three practical examples
- A planar robot planner divides obstacle-free configuration space into simple regions and searches their adjacency graph.
- A coverage planner organizes an area into cells that can be swept systematically, then plans transitions between them.
- A warehouse navigation model uses a grid-like approximation to organize free and blocked regions, with resolution and collision checks chosen for the robot.
Think of it this way
Think of navigating a building by first choosing a sequence of rooms and doorways, then moving safely within each room. The analogy captures cell connectivity. It is limited because a robot's configuration space can include orientation and joint angles, so a cell need not correspond to a visible patch of floor or an ordinary room.
Worked example
Consider a simplified point robot in a 6-by-4 rectangle. An obstacle occupies the vertical strip from x = 2 to x = 4 and from y = 0 to y = 3. A free passage remains above the obstacle. Define three interior free regions: left L with x below 2, top T with y above 3, and right R with x above 4, using appropriate shared portals at their interfaces.
The cell graph has L connected to T and T connected to R; there is no direct crossing through the obstacle from L to R. A start at (1, 1) and goal at (5, 1) can follow points (1, 3.5), (5, 3.5), then the goal. The three segments remain outside the obstacle. This is an illustrative region-and-portal representation, with boundary handling stipulated, not a formal disjoint decomposition proof. A robot with nonzero size requires its shape and clearance to be incorporated before the same route can be accepted.
Illustrative case study
At fictional Pine Robotics, a team observes that a coarse map labels a narrow corridor as blocked. It refines the relevant region and checks the robot's full footprint before deciding whether passage is possible. The team also inspects the motion between representative cell points rather than assuming graph connectivity alone is enough.
This fictional case illustrates the relationship between geometric detail and path validity. It does not claim that refinement always finds a path or that a collision-free geometric path automatically satisfies the robot's turning and motion-control constraints.
Common misconceptions and mistakes
Cell decomposition is not necessarily a uniform grid. Cells may have different shapes and sizes, and exact geometric methods can construct them from obstacle boundaries. It is also not the same as cellular network coverage or biological cell segmentation.
A connected cell graph is useful only if its edges correspond to valid local motion. Conversely, an incomplete approximate graph can miss real connections. Fewest cell transitions need not mean shortest physical distance. Finally, configuration-space planning must account for the robot's geometry; treating a large robot as a point in an unmodified floor map can produce collisions.
Business use
Businesses evaluating robotic planning should ask what the cells represent, how obstacle uncertainty and robot dimensions are handled, and what a no-path result means. A decomposition can support understandable route diagnostics because blocked connections can be inspected. However, map updates may invalidate cells or adjacency, and dynamic obstacles require additional handling. The representation should be evaluated together with collision checking and the motion system that executes the path.
People also ask
Are all cells squares?
No. Grids are one option; other decompositions use different geometric regions.
Does a coarse grid prove that no continuous path exists?
Not generally. Its resolution may omit a usable passage.
Is a path through connected cells automatically the shortest route?
No. The search objective, representative points, and geometric path construction determine what is optimized.
Check your understanding
A graph edge joins two free cell centers, but the straight segment between them crosses an obstacle. Is that edge a valid motion connection?
Answer: No. The local path must be collision-free; free endpoints alone are insufficient.
Related terms
- Configuration space
- Motion planning
- Occupancy grid
- Graph search
- roadmap
- collision checking
- resolution completeness
Learn next
Draw the worked obstacle and proposed path, then give the robot a nonzero radius. Determine which clearances change before rebuilding the cell connections. This shows why geometry, representation, and graph search must be checked together rather than treating the graph as a complete physical model.
More in Graphs and symbolic AI
- Cascaded finite-state transducers - Cascaded finite-state transducers are a sequence of finite-state processing stages in which one stage's output becomes input for the next.
- Case agreement - Case agreement is compatibility in grammatical case between words or phrases that a language's grammar requires to agree.
- Case-based planning - Case-based planning constructs a plan for a new situation by retrieving relevant previous planning experiences and adapting them.
- Certainty effect - The certainty effect is a pattern in decision making in which a guaranteed outcome receives disproportionate weight compared with outcomes that are merely...
- Certainty equivalent - A certainty equivalent is a guaranteed outcome that a decision maker values equally to a specified uncertain prospect.
- Certification - Certification is a formal attestation that a specified object meets defined requirements within an identified scope.
Sources
Sources: Steven LaValle, original Planning Algorithms, Vertical Cell Decomposition: https://msl.cs.uiuc.edu/~lavalle/planning/node262.html . LaValle, Solving a Query: https://lavalle.pl/planning/node266.html . Author's planning text and chapter resources: https://lavalle.pl/planning/ .
Previous: Cell Next: Cellular architecture