Continuous path planning and geometric queries in the presence of obstacles are computationally demanding. In non-convex environments, planners easily get trapped in local minima, and the complexity of collision checking scales poorly with both the degrees of freedom of the agent and the geometric detail of the obstacles. Free space partitioning resolves this by converting continuous geometric spaces into discrete topological graphs. By carving the obstacle-free space into structured sub-regions—such as convex cells, corridors, or functional zones—algorithms can solve high-level routing via efficient graph search, leaving local trajectory generation to simple, well-behaved operations within each cell.
Convex Decomposition: Eliminating Local Minima
Why partition space into convex regions? Inside a convex shape, any two points can be connected by a straight line without intersecting an obstacle boundary. This property guarantees that local minima do not exist within the cell. For high-dimensional systems like highly redundant robotic arms, Akira Hayashi et al. demonstrated in Path Planning for Highly Redundant Manipulators Using a Continuous Model that decomposing the environment into primary convex regions reduces pathfinding complexity from exponential to polynomial. Instead of searching a massive configuration space, a graph search identifies a sequence of safe zones.
This strategy also recovers mathematical tractability in complex control and verification problems. For instance, Shankara Narayanan Krishna et al. showed in The Reach-Avoid Problem for Constant-Rate Multi-Mode Systems that while navigating multi-mode hybrid systems through non-convex spaces is generally undecidable, partitioning the workspace into convex cells allows paths to be represented as a "witness channel"—a valid sequence of adjacent safe cells. Similarly, in hybrid automata verification, Shankara Narayanan Krishna et al. in Weak Singular Hybrid Automata decomposed non-convex environments into ranked convex regions to enable one-way transition hierarchies.
In modern optimization-based planning, Mingxin Yu leveraged a graph of overlapping convex polytopes in Rigid Body Path Planning using Mixed-Integer Linear Programming to isolate narrow passages before running Mixed-Integer Linear Programming (MILP), enabling online query times under 100ms. For stochastic systems where uncertainty must be managed, Kazuhide Okamoto highlighted in Optimal Stochastic Vehicle Path Planning Using Covariance Steering how decomposing the obstacle-free environment into convex sub-regions allows covariance steering algorithms to safely "shrink" vehicle state distributions through tight spaces. Even for coverage tasks, such as drone mapping of irregular terrains, Weichang Sun et al. utilized trapezoidal decomposition in Joint Deployment and Coverage Path Planning for Capsule Airports with Multiple Drones to break concave areas into manageable convex sub-regions.
Functional Partitioning: Oceans, Bays, and Corridors
When dealing with complex polygonal obstacles, a naive pathfinder's performance scales poorly with the total number of obstacle vertices ($n$). Functional space partitioning solves this by abstracting obstacle boundaries into broader topological features, making search complexity depend primarily on the number of obstacles ($h$) rather than their geometric detail.
A prominent manifestation of this is the "ocean-bay-canal" decomposition. As detailed by Sang Won Bae 0001 et al. in Computing the L1 Geodesic Diameter and Center of a Polygonal Domain and Danny Z. Chen et al. in Computing L1 Shortest Paths Among Polygonal Obstacles in the Plane, the free space is divided into an "ocean" (the wide-open central space surrounding the convex hulls of obstacles), "bays" (recessed pockets within obstacle indentations), and "canals" or "corridors" (narrow passages connecting different parts of the environment).
By isolating complex obstacle boundaries into simple geometric containers, global queries can be processed rapidly in the highly connected "ocean" or through a simplified network of corridors. Danny Z. Chen et al. leveraged this corridor decomposition in Two-Point L1 Shortest Path Queries in the Plane to achieve near-optimal $O(\log n)$ two-point shortest path queries under the $L_1$ metric. Similarly, Haitao Wang 0001 et al. used a spatial decomposition of junction rectangles and connecting corridors in Bicriteria Rectilinear Shortest Paths among Rectilinear Obstacles in the Plane to streamline bicriteria rectilinear shortest path planning.
For visibility queries, Haitao Wang et al. organized the free space into a hierarchical structure of corridors and canals in Quickest Visibility Queries in Polygonal Domains, successfully bounding the number of cell crossings relative to the number of holes (obstacles) rather than the vertex count of the visibility polygon. In a similar vein, Joseph S. B. Mitchell et al. in An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains utilized vertical and horizontal visibility decompositions to break free space into rectangular junction cells and corridors, tracking the propagation of minimum-link wavefronts across the domain.
Cellular Decomposition for Coverage and Reachability
Beyond finding a single path, partitioning free space provides a systematic way to guarantee complete coverage or analyze reachability boundaries.
In area coverage problems, Boustrophedon cellular decomposition breaks down an irregular environment into non-overlapping cells. As shown by Kelly Benson et al. in Efficient multi-robot coverage of a known environment, this allows multi-robot teams to efficiently cover complex spaces using simple, parallel back-and-forth sweeping motions within each cell. For robotic exploration of unknown polygonal environments, Gregory Dudek et al. optimized exploration in Multi-Robot Exploration of an Unknown Environment, Efficiently Reducing the Odometry Error by decomposing space based on reflex vertices (corners pointing into free space), keeping computational complexity linear with respect to the environment's geometric layout.
Decomposition also reveals the underlying reachability structure of an environment. Sarita de Berg et al. partitioned domains into cells where the shortest path to a specific vertex follows a consistent sequence of edges in Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain, providing a structured representation of path topology. For autonomous aerial mapping, Yichen Zhang et al. grouped free space into zones using 3D connected component labeling based on actual reachability in FALCON: Fast Autonomous Aerial Exploration using Coverage Path Guidance, preventing drones from attempting to navigate physically impassable narrow gaps.
In multi-agent path finding (MAPF), Poom Pianpak distributed the problem across nodes in DMAPF: A Decentralized and Distributed Solver for Multi-Agent Path Finding Problem with Obstacles by partitioning the environment into disconnected regions defined by obstacles. Finally, even when analyzing curve similarity, Jacobus Conradi et al. partitioned free space diagrams into monotone subcells by identifying boundary singularities in Revisiting the Fréchet distance between piecewise smooth curves, allowing complex non-convex regions to be evaluated using standard reachability logic. To detect when simple decoupled planning must be abandoned in favor of coordinated maneuvering, Mincheul Kang et al. utilized Generalized Voronoi Diagrams in Harmonious Sampling for Mobile Manipulation Planning to explicitly isolate narrow passages and topological bottlenecks.
Key Foundational Work
Path Planning for Highly Redundant Manipulators Using a Continuous Model (1991) — contributed 2 concept elements to this direction.
Multi-Robot Exploration of an Unknown Environment, Efficiently Reducing the Odometry Error (1997) — contributed 1 concept elements to this direction.