💻 computer science

Separation Logic for Verifying Physical Collisions of CNC Programs

This paper presents a formal verification framework that models the CNC workspace as a spatial heap and applies Separation Logic to detect physical collisions as logical data races, thereby reducing reliance on iterative simulation for safer, autonomous manufacturing.

Original authors: Yeonseok Lee

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yeonseok Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a high-speed, automated factory where a robotic arm (the CNC machine) is carving a piece of metal. Traditionally, to make sure the robot doesn't smash its own arm into the metal or the table, engineers run thousands of computer simulations. They watch the robot move in a virtual world, hoping to catch a crash before it happens in real life. But if you change the design even slightly, you have to run all those simulations again. It's slow, repetitive, and doesn't give a 100% guarantee.

This paper proposes a completely different way to think about safety. Instead of watching a movie of the robot moving, it treats the factory floor like a computer's memory.

Here is the simple breakdown of their idea:

1. The Factory Floor is a "Memory Grid"

Imagine the entire workspace of the machine is a giant 3D grid of tiny cubes (like pixels, but in 3D).

The Old Way: You calculate the exact curve of the robot's arm as it moves through the air. This is mathematically messy and hard to prove is safe.
The New Way: The authors say, "Let's stop worrying about the smooth curves. Let's just look at which cubes are occupied."
- If a cube has the Tool in it, it's marked "Tool."
- If a cube has the Metal Block in it, it's marked "Stock."
- If a cube has a Clamp in it, it's marked "Environment."
- If a cube is empty, it's marked "Empty."

2. The "Parser-Prover Handshake" (The Translator)

The machine speaks a language of smooth, floating-point numbers (like X = 10.5432). The safety checker speaks a language of strict, whole numbers (like Cube 10, Cube 11).

The paper introduces a Translator (called the Parser) that sits between the machine code and the safety checker.

The Job: The Translator takes the smooth, wiggly path the robot might take and snaps it onto the nearest grid cubes. It also adds a little "safety buffer" (like putting a fuzzy coat around the tool) to make sure even if the robot wobbles a tiny bit, it doesn't hit anything.
The Result: By the time the safety checker sees the problem, there are no more wiggly lines or decimals. It's just a list of specific cubes: "The tool is here, the metal is there, and the path is clear."

3. Collisions are "Data Races"

In computer programming, a "data race" happens when two programs try to write to the same memory spot at the same time, causing a crash.

The Paper's Big Idea: A physical crash in a factory is exactly the same thing. If the "Tool" tries to claim ownership of a cube that is already owned by the "Clamp," that is a Spatial Data Race.
The Logic: The authors use a special math system called Separation Logic. This system has a simple rule: Two things cannot own the same piece of space at the same time.
The Check: The safety checker (the Prover) looks at the list of cubes. It asks: "Does the Tool's list of cubes overlap with the Clamp's list?"
- If the answer is No, the move is safe.
- If the answer is Yes, the math immediately says "FALSE." The system stops the machine instantly, proving a crash would happen, without ever needing to run a slow simulation.

4. Cutting Metal is "Deleting Memory"

When the robot cuts the metal, it removes material.

In this new system, cutting isn't just a visual change; it's a logical update.
As the tool moves through the metal cubes, the system logically changes those cubes from "Stock" to "Empty."
It's like playing a game of Tetris where, as the block falls, the squares it touches disappear from the board. The math proves that the tool only touches squares that were actually "Stock" and not "Clamp."

5. Working Together (Concurrency)

What if you have two robots working on the same table?

The paper uses an extension of their logic to handle this. It treats the workspace like a shared office.
If Robot A needs to use a specific area (a "hand-off zone") to pass a part to Robot B, the system acts like a lock.
Robot A "locks" the zone (claims ownership of those cubes). Robot B cannot enter that zone until Robot A is done and "unlocks" it (returns the cubes to "Empty").
This prevents the two robots from crashing into each other because the math proves they can never hold the same "lock" at the same time.

6. Spinning Tables (5-Axis Machines)

Some machines have tables that spin while the tool moves. This is usually very hard to calculate.

The paper's trick: The Translator (Parser) does all the heavy spinning math before the safety checker looks at it.
It calculates exactly which cubes the spinning metal block will sweep through and turns that into a simple list of "Occupied Cubes."
The safety checker then just checks if the Tool's list and the Spinning Metal's list overlap. If they don't, the move is safe.

Summary

Instead of trying to simulate the physics of a crashing robot, this paper turns the factory floor into a logical puzzle.

Translate the robot's smooth path into a grid of cubes.
Check if the Tool's cubes overlap with the Clamp's or Metal's cubes.
Prove safety by showing they are completely separate (disjoint).

If the math says the cubes don't overlap, the machine is guaranteed to be safe. If they do overlap, the math proves a crash is inevitable, stopping the machine before it even starts. This replaces thousands of slow, repetitive tests with a single, instant mathematical proof.

Technical Summary: Separation Logic for Verifying Physical Collisions of CNC Programs

1. Problem Statement

Traditional safety verification for Computer Numerical Control (CNC) machining relies heavily on geometric simulations and swept volume analysis. While effective for identifying obvious G-code errors, these methods suffer from fundamental limitations:

Lack of Symbolic Proof: They provide probabilistic confidence rather than deterministic, symbolic proofs of safety.
Computational Cost: They require repetitive testing cycles, especially when specifications or G-code change.
Handling of Uncertainty: They struggle to rigorously account for continuous kinematic variables, non-deterministic rapid-positioning paths, and mechanical variabilities (e.g., servo lag) without becoming computationally expensive.
Scalability: Existing methods often fail to scale efficiently to complex multi-axis environments (e.g., 5-axis Table-Table configurations) and collaborative multi-tool systems.

The paper posits that physical collisions in CNC machining can be redefined as logical contradictions within a managed resource model, offering a deterministic alternative to stochastic simulation.

2. Methodology

The proposed framework introduces a Parser-Prover Handshake architecture that decouples continuous physical kinematics from discrete formal logic. This approach conceptualizes the physical CNC workspace as a Spatial Heap, treating physical occupancy as a managed logical resource.

2.1 Architectural Decoupling

The system operates through a strict boundary between two domains:

The Parser (Continuous Domain): Acts as a virtual machine that consumes raw G-code, tool geometry, and safety margins. It exhausts continuous kinematic variables (floating-point coordinates, feed rates) and physical uncertainties into a discrete integer domain ( $Z^3$ ). It utilizes Minkowski sums to expand tool volumes by a user-defined safety margin ( $\epsilon$ ) and employs Bresenham's 3D algorithm to generate discrete voxel paths for linear interpolation (G01) and bounding boxes for rapid positioning (G00).
The SL Prover (Discrete Domain): Operates strictly on the discrete spatial sets emitted by the Parser. It functions as a memory manager, evaluating Separation Logic (SL) triples against a Spatial Heap ( $h$ ). The Prover does not query a variable store; it only validates spatial disjointness.

2.2 The Spatial Heap Model

The physical workspace is mapped to a finite partial function $h: Z^3 \rightharpoonup \{Tool, Environment, Stock, Empty\}$ .

Spatial Data Races: Physical collisions are redefined as "Spatial Data Races," occurring when two distinct physical resources (e.g., Tool and Environment) attempt to claim ownership of the same discrete memory address simultaneously.
Separating Conjunction ( $*$ ): The core logical operator asserts that subformulas hold for disjoint portions of memory. If $R(C_1, \theta_1) * R(C_2, \theta_2)$ is evaluated, it is only satisfiable if $C_1 \cap C_2 = \emptyset$ . A non-empty intersection renders the logic unsatisfiable, deterministically signaling a fault.

2.3 Verification Pipeline

The verification process follows a unidirectional pipeline:

Input: Raw G-code, tool mask geometry, safety margin ( $\epsilon$ ), and resolution factor.
Discretization: The Parser converts inputs into discrete spatial sets ( $V_{start}, V_{final}, V_{path}$ ).
Logical Inference: The Prover evaluates the Separation Logic Triple $\{ \Sigma_0 \} \text{CSL} \{ \Sigma_{final} \}$ ${Σ_{0}} CSL {Σ_{f ina l}}$ .
- Precondition ( $\Sigma_0$ ): Asserts the initial disjoint ownership of the tool, environment, stock, and empty space.
- Command (CSL): Represents the discrete motion (e.g., G00, G01) as heap mutations.
- Postcondition ( $\Sigma_{final}$ ): Asserts the updated ownership after the tool's displacement and material removal.

2.4 Extensions to Concurrency and Multi-Axis

Concurrent Separation Logic (CSL): For multi-tool or collaborative environments, the Spatial Heap is partitioned into thread-local sub-heaps ( $h_{local}$ ) and a shared heap ( $h_{shared}$ ). Physical hand-offs are verified as formal ownership transfers using Critical Regions (with Res do C), ensuring mutual exclusion without dynamic locks.
Multi-Axis Kinematics: The framework scales to 5-axis operations by treating the cutting tool and the rotatable workpiece as two concurrent, mutually mutable spatial threads. The Parser pre-calculates the rotational swept volume of the stock (using rotation matrices) and the linear swept volume of the tool, presenting both as discrete sets to the Prover. This abstracts complex trigonometric kinematics away from the proof engine.

3. Key Contributions

Formal Redefinition of Collisions: The paper establishes a formal correspondence between physical occupancy and logical memory ownership, redefining physical collisions as logical "Spatial Data Races."
Parser-Prover Handshake: A novel architectural boundary that exhausts continuous uncertainties into a discrete integer domain, allowing the Prover to operate within a tractable fragment of Separation Logic while avoiding the complexity of general pointer arithmetic.
Integration of Geometric Safety Margins: The methodology integrates Minkowski sums to provide formal safety margins ( $\epsilon$ ) directly within the discrete logic, accounting for real-world mechanical uncertainties.
Scalability to Advanced Kinematics: The framework natively supports multi-axis (e.g., 5-axis) and concurrent multi-tool environments by modeling the workpiece as a dynamically mutable spatial resource and utilizing Concurrent Separation Logic for shared workspace verification.

4. Results and Validation

The paper demonstrates the methodology through:

Deterministic Verification: The system successfully verifies safe trajectories by proving the satisfiability of Separation Logic triples.
Collision Detection: In a case study involving a rapid traverse into a fixture, the system detects a "Spatial Data Race" (non-empty intersection of claimed memory) and transitions to a fault state deterministically, prior to physical execution.
Concurrency and Hand-offs: The framework validates parallel execution of dual tools in disjoint spaces and the safe sequential hand-off of a shared resource, proving that the separating conjunction enforces mutual exclusion.
Multi-Axis Verification: The approach successfully verifies 5-axis operations by reducing complex rotational kinematics to discrete voxel sets, proving that the tool and stock paths do not intersect the environment or each other.

5. Significance and Claims

The paper claims that this approach offers a deterministic alternative to traditional geometric simulation, providing symbolic proofs of safety rather than probabilistic confidence. By serving as a complement to simulation, the framework aims to:

Reduce Iterative Testing: Minimize the number of required test cycles when G-code or specifications change.
Enable Autonomous Manufacturing: Provide a mathematically grounded foundation for autonomous, less-collision manufacturing systems.
Decouple Complexity: Separate the computational burden of continuous kinematics from the logical proof, making formal verification tractable for complex industrial applications.

The authors position this work not as a replacement for all simulation, but as a rigorous, scalable layer that ensures safety prerequisites are met before state transitions occur, mirroring mechanized semantics used in other domains like additive manufacturing. Future work is noted to explore "Incorrectness Separation Logic" for isolating legacy bugs and real-time integration into embedded controllers.