Abstract
Robotic assembly planning requires bridging the gap between low-level CAD geometry and high-level sequence reasoning. This paper introduces the Non-Directional Blocking Graph (NDBG), a qualitative representation that discretizes the infinite space of possible motion directions into a finite set of regions. By identifying where part interferences remain constant, the NDBG enables the use of efficient polynomial-time graph algorithms to solve complex assembly sequencing problems, moving beyond exhaustive geometric simulations.
Introduction
In modern manufacturing, a standard geometric model of a machine—detailing the precise location of every screw, gear, and housing—is insufficient for automated assembly planning. Such models do not explicitly answer critical questions: In what order should parts be assembled? Which parts are "trapped" by others? Can a specific subassembly be extracted without disturbing the rest of the structure?
Reasoning about these questions is computationally expensive because there are an infinite number of directions a part could potentially move. Traditional methods often relied on trial-and-error path planning. Wilson and Latombe proposed a "qualitative" structure to summarize all possible blocking relationships, transforming a continuous geometric problem into a discrete combinatorial one.
The Blocking Graph Framework
The core of the approach rests on two nested concepts: the Directional Blocking Graph (DBG) and the Non-Directional Blocking Graph (NDBG).
Directional Blocking Graph (DBG)
For a single, fixed direction of motion $d$, a DBG is a directed graph where nodes represent parts. An arc exists from part $P_i$ to part $P_j$ if $P_j$ physically blocks $P_i$ from moving in direction $d$.
As shown in the figure above, the blocking relationships change depending on the chosen direction. In direction $d_1$ (up), $P_3$ is blocked by $P_1$ and $P_2$. In direction $d_2$ (diagonal), the relationships shift, and $P_1$ is now blocked by $P_3$.
Non-Directional Blocking Graph (NDBG)
The NDBG is the "master" representation. The authors observed that as the direction of motion rotates, the blocking relationships (the arcs in the DBG) only change at specific "critical" orientations. These orientations are typically defined by the surface normals of the parts in contact.
By identifying these critical boundaries, the space of all directions (a circle in 2D or a sphere in 3D) can be partitioned into a finite arrangement of regular regions. Within each region, the DBG remains constant.
Once the NDBG is constructed, assembly planning becomes a graph theory problem. For instance, a subassembly is "locally free" to move in a direction if its corresponding nodes in the DBG have no outgoing arcs to parts outside that subassembly. This acts as a high-speed filter, ruling out impossible sequences before more expensive motion planners are invoked.
Computational Complexity and Implementation
The paper provides polynomial-time algorithms to compute these graphs. For the 2D case, the complexity is $O(c \log c + cn^2)$, where $n$ is the number of parts and $c$ is the number of contact segments. In 3D, the complexity is $O(c^2n^2)$. The authors also extended this logic to include infinitesimal rigid motions (combining rotation and translation) and extended translations (moving a part to infinity).
The implementation was evaluated on geometric models of industrial assemblies, such as a 22-part electric bell and a 42-part engine. The system successfully handled the engine model, demonstrating that the qualitative approach scales to real-world industrial complexity where manual sequence planning is often error-prone.
Discussion and Limitations
While foundational, the NDBG framework has several limitations:
- The "Two-Hand" Assumption: The model assumes one subassembly moves relative to a stationary remainder. It does not easily account for "multi-handed" maneuvers where three or more parts must move simultaneously.
- Idealized Physics: The algorithm assumes perfectly rigid parts and exact geometry, neglecting manufacturing tolerances, friction, and gravity.
- Grasping: The NDBG identifies if a part can move, but not how a robot should grasp it or maintain the stability of the remaining assembly.
Future work involves layering higher-order constraints, such as tool clearance and structural stability, on top of this qualitative blocking structure.
Conclusion
The Non-Directional Blocking Graph represents a significant step in robotic reasoning. By discretizing the continuous space of motion into qualitatively distinct regions, it provides a computationally efficient bridge between CAD data and high-level task planning.
Summary updated