Graph-Based Representations of Free Space for Path Planning

22 concepts13 papers1 proposal

When an agent navigates a physical environment, the most intuitive distance metric is a straight line. However, Euclidean distance fails dramatically in the presence of obstacles. A wall can make two physically adjacent points practically miles apart. To plan paths effectively, robots and navigation systems must understand the true geometry of traversable space.

Traditional motion planning often relies on dense grids or continuous configuration spaces, but these suffer from the curse of dimensionality and require heavy, repetitive collision checking. The core insight unifying this body of research is a paradigm shift: instead of mapping obstacles or checking collisions against dense grids, we can explicitly represent the topology of free space as a sparse connectivity graph. By discretizing navigable regions, obstacle boundaries, or free-space volumes into nodes and edges, continuous motion planning collapses into an efficient, discrete graph search.

The Failure of Straight Lines

Why do we need to explicitly map free space? As Karan Mirakhor et al. demonstrate in Task Planning for Visual Room Rearrangement under Partial Observability, relying on Euclidean distance to determine an agent's next action leads to highly suboptimal trajectories because it completely ignores environmental geometry like walls and furniture. To solve this, the authors construct a spatial graph where edges represent the actual path-length distance calculated via shortest-path algorithms, ensuring the agent chooses the most efficient route.

This problem extends beyond robotics into human spatial planning. In the context of architectural layout optimization, Anton Ipsen et al. show in Hierarchical Seating Allocation (Extended Abstract) that straight-line metrics fail when arranging teams in an office, often seating collaborating groups on opposite sides of a physical wall. By utilizing robotics-inspired pathfinding algorithms (such as Probabilistic Roadmaps) to sample collision-free points and construct a connectivity graph, the authors ensure that the calculated distances reflect actual walking paths through corridors.

Euclidean Metric (Fails):
[Agent] ------------ (Wall) ------------> [Goal]  (Attempts impossible straight line)

Graph-Based Path-Length (Succeeds):
[Agent] ----> [Node 1] ----> [Node 2] ----> [Goal] (Navigates around the wall)

Decomposing Free Space into Geometric Volumes

How do we mathematically capture "emptiness" to build this graph? Pioneering work by Rodney A. Brooks shifted the focus away from obstacle boundaries and directly onto the "freeways" of empty space. In Solving the Find-Path Problem by Good Representation of Free Space, Rodney A. Brooks proposed modeling free space as a union of overlapping generalized cones. In Find-Path for a PUMA-Class Robot, the author extended this to represent unoccupied regions as a network of overlapping channels defined by a central axis and a clearance radius. This structure transforms continuous motion into a discrete search problem where nodes represent the intersections of these channels.

Building on this volumetric intuition, Tomás Lozano-Pérez introduced an approach in A Simple Motion Planning Algorithm for General Robot Manipulators that characterizes free space as a collection of overlapping regions, each containing an internal "kernel" of guaranteed collision-free space. Movement within a kernel is a simple straight line, and transitions occur smoothly where regions overlap, streamlining the pathfinding process.

Modern iterations refine this concept for dynamic, high-speed environments. For instance, Matej Petrlík et al. developed SphereMap in SphereMap: Dynamic Multi-Layer Graph Structure for Rapid Safety-Aware UAV Planning, which represents free space as a graph of intersecting spheres. Because each node's radius corresponds to the distance to the nearest obstacle, safety and clearance information are inherently baked into the graph topology, allowing Unmanned Aerial Vehicles (UAVs) to navigate complex environments without expensive, real-time collision checks.

  Volumetric Free Space Graph:
     ( O ) --- ( O ) --- ( O )
    /     \     /     \     \
  ( O ) --- ( O ) --- ( O ) --- ( O )
  [Each node 'O' is a safe sphere or kernel with a known clearance radius]

Discretizing Obstacle Boundaries and Critical Points

An alternative to mapping the vast volumes of free space is to map the critical boundaries that constrain it. Thomas Sayre-McCord argues in Perception-driven sparse graphs for optimal motion planning that instead of a uniform global grid, a planner can discretize only the boundaries of detected obstacles to serve as transition points. Optimal control principles guarantee that the shortest path in continuous space can be found simply by connecting these boundary-aligned nodes.

Similarly, Logan E. Beaver et al. construct a fully connected graph in A Graph-Based Approach to Generate Energy-Optimal Robot Trajectories in Polygonal Environments where nodes represent critical obstacle interaction points, and edges represent unconstrained trajectory segments between them.

By shifting the perspective entirely, Beipeng Mu et al. show in Information-based Active SLAM via Topological Feature Graphs that modeling obstacles as non-traversable edges between discrete features in a graph enables closed-form collision checking. This mathematical formulation bypasses the need for heavy sampling against dense occupancy grids, drastically accelerating path planning during simultaneous localization and mapping (SLAM).

Constructing and Querying the Obstacle-Aware Graph

Once an environment is structured as a graph, pathfinding becomes a matter of computing shortest paths over valid edges. In Complex Robotic Manipulation via Graph-Based Hindsight Goal Generation, Matthias Brucker et al. discretize the accessible goal space into a grid of vertices, connecting adjacent vertices with edges only if the direct path between them avoids obstacles. Pre-computing all-pairs shortest paths via Dijkstra's algorithm yields a distance matrix that accurately encodes obstacle-aware distances, guiding reinforcement learning agents around obstacles in sparse-reward environments.

This graph-construction strategy applies broadly across diverse domains:

Why It Works: The Intuition

Graph-based free space representations work because they strip away irrelevant environmental data. In a continuous space or a dense grid, a path planner spends the majority of its computational budget asking, "Am I hitting something right now?" at thousands of arbitrary points.

By abstracting the environment into a graph of free-space volumes (like spheres, channels, or kernels) or boundary transitions, the collision-checking problem is solved during the graph's construction phase. Once the graph exists, every edge is guaranteed to be valid, or its traversability cost is explicitly quantified. The continuous, high-dimensional problem of avoiding obstacles is thus transformed into the well-understood, highly efficient problem of traversing a discrete topological network.

Key Foundational Work

Solving the Find-Path Problem by Good Representation of Free Space (1982) — contributed 2 concept elements to this direction.
Find-Path for a PUMA-Class Robot (1983) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_based_collision_checking_c0e74255,
  title = {graph-based collision checking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-collision-checking/rdr_c0e7425553b9409384cab994e77d7342},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_based_collision_checking_c0e74255_v1,
  title = {graph-based collision checking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-collision-checking/rdr_c0e7425553b9409384cab994e77d7342/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake