Lexicographic optimization for real-time CNC feedrate planning with coupled orientation handling

This paper proposes a tuning-free, real-time lexicographic optimization framework for five-axis CNC feedrate planning that synchronously handles tool position and orientation while significantly reducing machining time through sparsity-exploiting formulations and sequential windowing.

The Gist

Imagine you are driving a high-performance race car around a complex, winding track. Your goal is to finish the lap as fast as possible without crashing or damaging the car. However, you have two conflicting goals:

1. Speed: You want to go as fast as the engine and tires allow.
2. Smoothness: You don't want to jerk the steering wheel or slam on the brakes, because that makes the ride uncomfortable and can damage the car.

This paper presents a new "co-pilot" for industrial machines (specifically 5-axis CNC machines used to carve complex shapes) that solves this exact problem. Here is how it works, explained in everyday terms:

The Problem: The Old Way vs. The New Way

The Old Way (Industrial Standard):
Current factory machines use a "pre-set menu" approach. They look at the path ahead and try to fit the drive into a rigid, pre-defined shape (like a staircase or a simple curve). It's like trying to drive a race car by only using three specific gears: slow, medium, and fast. This is safe and fast to calculate, but it's not truly optimal. The machine often has to slow down more than necessary because it can't find the perfect speed for every curve.

The New Way (This Paper's Solution):
The authors propose a "smart navigator" that calculates the perfect speed for every single millimeter of the path. It doesn't just guess; it solves a complex math puzzle to find the absolute fastest route that still respects the machine's physical limits (like how fast its motors can spin or how hard they can push).

The Three Big Innovations

1. The "Two-Step" Priority System (Lexicographic Optimization)

Usually, when you try to be fast and smooth, you have to guess a "balance knob." If you turn it too far toward speed, the ride gets bumpy. If you turn it toward smoothness, you lose time.

This paper introduces a two-step priority system that removes the need for guessing:

• Step 1: The computer first asks, "What is the absolute fastest we can go?" It finds that limit.
• Step 2: Then, it asks, "Now that we know the fastest speed, how can we make the ride as smooth as possible without slowing down more than a tiny, acceptable amount (like 1%)?"

The Analogy: Imagine you are packing a suitcase.

• Old way: You try to fit clothes in while balancing the weight, but you keep overstuffing it or leaving gaps because you don't know the limit.
• New way: First, you pack the suitcase to its absolute maximum capacity. Then, you gently rearrange the clothes to make them sit flat and neat, ensuring you haven't lost any space in the process. You get the most capacity and the neatest arrangement without needing to guess how much to pack.

2. The "Window" Strategy (Sequential Windowing)

Calculating the perfect speed for a very long path (like a 10-mile track) all at once is like trying to solve a 10,000-piece puzzle in your head instantly. It takes too long and crashes the computer.

The authors use a sequential windowing strategy.
The Analogy: Instead of trying to see the whole 10-mile track at once, the computer only looks at the next 500 meters (a "window"). It plans the perfect speed for that short stretch, executes it, and then immediately shifts the window forward to the next 500 meters.

• Why it works: It's like a driver looking ahead just far enough to see the next curve. This allows the system to run on older, slower computer chips (like those found in many existing factory machines) while still being fast enough to work in "real-time."

3. The "Unified Map" (Coupled Orientation)

In 5-axis machining, the machine doesn't just move the tool left/right/forward/back; it also tilts and rotates the tool to cut complex angles.
The Analogy: Imagine a human arm. If you move your hand forward, your elbow and shoulder have to move in a specific, coordinated way. If you plan the hand's movement and the elbow's movement separately, they might get out of sync.
This paper treats the tool's position and its angle as one single, unified path. It plans the movement of the "hand" and the "wrist" simultaneously, ensuring they move perfectly together without needing extra steps to sync them up later.

The Results: What Did They Prove?

The authors tested this system on a complex, free-form shape (like a sculpted car part).

• Speed: Compared to a standard industrial machine controller, their method finished the job 15% faster.
• Efficiency: It could handle a path with one million checkpoints (extremely detailed) in about 50 seconds on a powerful computer, and 14 seconds on an older computer.
• Smoothness: By using their "two-step" system, they reduced the "jitter" (vibrations) in the machine's movement by 24% without slowing down significantly.

Summary

This paper gives factory machines a smarter brain. Instead of using rigid, pre-set rules, it calculates the perfect speed for every moment, prioritizing speed first and smoothness second, all while breaking the long path into manageable chunks so it can run instantly on standard hardware. The result is faster production times and smoother, higher-quality cuts.

Technical Summary

Technical Summary: Lexicographic Optimization for Real-Time CNC Feedrate Planning with Coupled Orientation Handling

Problem Statement
While optimization-based feedrate planning offers the potential to significantly enhance machining productivity by fully exploiting servo drive dynamics, its industrial adoption is hindered by high computational costs and the extensive tuning effort required for multi-objective trade-offs. Current industrial CNC kernels rely on profile-based methods (e.g., seven-phase profiles) that impose fixed, piecewise-linear trajectory structures. These heuristic approaches fail to accurately capture the curvature-dependent, freeform nature of time-optimal feedrate profiles, inherently compromising time optimality. Furthermore, existing optimization algorithms (e.g., second-order cone programming, sequential quadratic programming) often lack the computational efficiency required for real-time execution on long toolpaths, particularly when handling coupled tool position and orientation constraints in five-axis machining.

Methodology
The paper proposes a comprehensive framework that integrates three core components to address these limitations:

1. Lexicographic Optimization Principle:
   Instead of combining time optimality (minimizing finishing time) and motion smoothness (minimizing chattering) into a single weighted objective function—which requires difficult, geometry-dependent tuning of weighting factors—the authors employ a lexicographic approach.

   • Step 1: The primary objective is to maximize the feedrate (minimize finishing time) to obtain an optimal solution $b^*(u)$.
   • Step 2: The secondary objective is to minimize the variation in the feedrate profile (smoothness) subject to a constraint that the finishing time degrades by no more than a small, predefined relative tolerance $\epsilon$.
   • This approach adaptively balances the objectives without manual parameter tuning, aligning more closely with engineering intuition.

2. Unified Toolpath Parameterization:
   The framework utilizes a unified parameterization scheme where the toolpath is defined by a normalized path parameter $u \in [0, 1]$. This allows for the synchronous handling of tool position ($p$) and orientation ($o$) within a single optimization variable. By deriving kinematic Jacobians and velocity transformations analytically, the method enforces Cartesian constraints (position and orientation) directly in the machine coordinate system (MCS) without requiring separate arc-length or arc-radian parameterizations, thereby ensuring inherent motion synchronization.

3. Sparse Discretization and Sequential Windowing (SeWin):
   To achieve real-time capability, the continuous optimization problem is discretized into a large-scale linear programming (LP) problem that exploits sparsity.

   • Sparse Formulation: The problem is reformulated using piecewise linear representations and slack variables to linearize absolute value terms, creating a sparse matrix structure solvable by efficient LP solvers (e.g., HiGHS).
   • Sequential Windowing: To handle long toolpaths without overwhelming memory or CPU resources, the optimization is performed sequentially on overlapping windows. The initial conditions of each subsequent window are derived from the solution of the previous window's overlap region. This strategy eliminates the need for multiple CPU cores or large memory buffers, making it compatible with legacy CNC hardware.

Key Contributions
The paper identifies two primary contributions:

1. Adaptive Smoothing: A lexicographic design that enables feedrate smoothing without manual tuning of weighting factors, effectively reducing acceleration-level chattering while preserving near-optimal finishing times.
2. Scalable Real-Time Execution: A sparse formulation combined with a sequential windowing strategy that has been verified to handle toolpaths with up to one million constraint checkpoints on single-core CPUs, including legacy hardware.

Results
The proposed method (LexLP + SeWin) was validated through simulations and experiments on a five-axis machine tool:

• Computational Performance: On an Intel i5-3470 CPU, the method optimized feedrate profiles for a toolpath with 100,000 checkpoints in 14 seconds. On a high-performance AMD 9950X CPU, it processed one million checkpoints in 52 seconds. The computational load scales linearly with toolpath length, unlike the polynomial scaling of one-shot solutions.
• Time Optimality: Compared to an industrial CNC kernel, the proposed method reduced finishing time by more than 15% (e.g., from 20.24 s to 16.86 s in a freeform test case).
• Smoothness vs. Time Trade-off: In the lexicographic optimization, setting a relative tolerance of $\epsilon = 1\%$ reduced acceleration-level chattering by 24% with only a 1.3% increase in finishing time compared to the raw time-optimal solution.
• Experimental Validation: In physical experiments on a 3.7-meter freeform trajectory, the method achieved a 15% reduction in finishing time compared to the industrial CNC kernel while maintaining tracking errors at a similar level. The control signals were slightly larger during transient phases due to less conservative handling of acceleration limits compared to the profile-based kernel.

Significance and Claims
The authors claim that this work significantly narrows the gap between theoretical feedrate optimization and practical CNC application. By demonstrating verified real-time performance on legacy hardware for ultra-long toolpaths, the paper suggests that the proposed framework is a viable candidate for integration into future industrial CNC kernels. The method successfully addresses the inherent trade-off between time optimality and motion smoothness without the need for case-specific tuning, while simultaneously handling the complex, coupled constraints of five-axis orientation and position. The authors note that future work will focus on extending this framework to parallel kinematics to allow for direct formulations in Cartesian space.