The fundamental process of the subdivision algorithm (
Brooks and Lozano-Perez, 1982) is that configuration space is first decomposed into rectangles with edges parallel to the axes of the space, then each rectangle is labeled as
E (empty) if the interior of the rectangle nowhere intersects
obstacles,
F (full) if the interior of the rectangle everywhere intersects
obstacles, or
M (mixed) if there are interior points inside and outside of
obstacles. A free path is found by finding a connected set of empty rectangles that include the initial and goal configurations. If such an empty cell path cannot be found in the initial subdivision of
, then a path that includes mixed cells in found. Mixed cells on the path are subdivided, by cutting them with a single plane normal to a coordinate axis, and each resulting cell is appropriately labeled as empty, full, or mixed. A new round of searching for an empty-cell path is initiated, and so on iteratively until success is achieved. If at any time no path can be found through non-full cells of greater than some preset minimal size, then the problem is regarded as insoluble.