A Parameter-Linear Formulation of the Optimal Path Following Problem for Robotic Manipulator

AI summary

Overview

• Research area: Robotics — trajectory planning and optimization for robotic manipulators (time-optimal path following).
• Technical level: Advanced. The paper is written for readers comfortable with manipulator dynamics, path parameterization, constrained optimization, and sequential convex programming.
• Scope: The paper derives a parameter-linear reformulation of the optimal path following problem that maximizes squared path speed along a prescribed path instead of minimizing travel time directly, thereby avoiding the zero-speed singularities of the conventional formulation, and validates it numerically on a 6-DOF manipulator.

What This Paper Is About

Time-optimal path following normally works by minimizing travel time after rewriting the problem in terms of a path parameter. That reformulation contains a division by the square root of the squared path speed, so the problem becomes singular wherever the path speed is zero, which makes it difficult to use arbitrary discretization methods and to produce smooth trajectories efficiently. The authors instead maximize the squared path speed along the path, an integral that has no division and no singularity, and they show that the resulting discrete problem is linear in the optimization variables when jerk constraints and viscous friction are set aside.

Key Contributions

1. A reformulation of the optimal path following (OPF) problem based on maximizing the integral of the squared path speed, which avoids the singularities at zero path speed that arise when minimizing terminal time directly.
2. A demonstration that the discrete version of this problem is linear in the optimization variables for two different representations of the path speed: a piecewise-linear polynomial approach and a B-spline approach.
3. A smooth-trajectory capability: because an arbitrary path-speed approximation can be used, the B-spline variant produces smooth second derivatives of the path speed and hence smooth joint jerk trajectories, which the piecewise-linear approach cannot do.
4. A numerical comparison against the conventional time-optimal approach across four paths and two discretization levels, showing equal terminal times and solutions with computation time reduced by more than 50 percent.

Main Findings

• No singularity at zero speed: Because the objective is the integral of z(sigma) over the path, and z is bounded, no division by the square root of z appears, so no singularity has to be handled.
• Parameter-linear structure: Without the joint jerk constraints and without viscous friction in the torque equation (that is, d(sigma) = 0), the discrete problem is linear in the path-speed variables z_k in the piecewise-linear case (equation 9) and linear in the control points p_i in the B-spline case (equation 11).
• Sequential convex programming handles the remainder: The joint jerk constraints and viscous friction are brought back in through an SCP framework, since they cannot be included in the linear problem directly.
• Smooth planning is feasible with a small cost penalty: For the arbitrary joint path, the piecewise-linear approach gave t_T = 0.429 s with t_comp. = 0.515 s, while the B-spline approach (d = 3, n = 61, N = 100) gave t_T = 0.427 s with t_comp. = 0.899 s. The second derivative of z* is smooth only with the B-spline approach, so only that variant yields smooth joint jerk trajectories.
• Equal terminal times across four paths: In Table 1, the conventional approach (min t_T) and the presented approach produce identical terminal times for paths A (arbitrary joint path), B (rectangle with rounded corners, inspired by the ISO-9283 norm), C (meander-shaped end-effector path), and D (arbitrary spatial curve), and the resulting trajectories are also reported as equal.
• Computation time reduced substantially: At N = 100, the relative reduction in computation time p_tcomp was 90.132 percent for path A, 86.014 percent for B, 79.602 percent for C, and 87.120 percent for D. At N = 200, the reductions were 91.117 percent for A, 89.34 percent for B, 77.303 percent for C, and 88.877 percent for D. The relative difference in terminal time p_tT was 0.000 percent in every listed case.
• Sub-time-optimal guarantee, not proven equivalence: The authors state that maximizing z up to the maximum velocity curve (MVC) yields at least a sub-time-optimal solution, and that to the best of their knowledge no proof exists that the two optimization problems are equivalent.
• Modest cost of smoothness: The computational effort increases only slightly when planning smooth joint jerk trajectories, in contrast to the conventional approach.

Methodology in Plain English

The authors start with the standard equations of motion of an n-DOF manipulator and assume a geometric joint path q(sigma) is given, parameterized by sigma between 0 and 1, followed only in the forward direction. They introduce the squared path speed z(sigma) = sigma_dot squared, which lets joint velocities, accelerations, and jerks along the path be written in terms of z and its geometric derivatives.

Instead of the usual objective, the terminal time expressed as an integral of 1 over the square root of z, they maximize the integral of z itself. Because z is bounded and nonnegative, this integral is concave in z and needs no division, so the singularity problem disappears.

To solve it numerically, they discretize sigma on [0, 1] with N+1 grid points and represent z either with a piecewise-linear polynomial between grid points (with z' evaluated at midpoints) or with B-splines whose control points p_i, degree d, and count n can be chosen independently of N. The objective, the joint velocity constraints, and the joint acceleration constraints come out linear in the optimization variables in both cases. Because joint jerk constraints and viscous friction torque terms break linearity, these are imposed through a sequential convex programming loop. The velocity constraints are squared carefully to keep them linear, while acceleration and torque constraints are evaluated at the midpoints (for the piecewise-linear case) or at the grid points (for the B-spline case).

The method was implemented in MATLAB using YALMIP, solved with MOSEK, and tested on a 6-DOF Comau Racer3 manipulator on an Intel Core i5-9500 CPU at 3.00 GHz running Windows 10, with symmetric upper and lower bounds.

Why This Matters

• For research: The paper offers an alternative objective for time-optimal path following that sidesteps a long-standing numerical difficulty (zero-speed singularities), and it shows that arbitrary smoothness in the path-speed representation still yields a linear discrete problem. It also turns the usual second-order-cone formulation's limitation, that it cannot plan trajectories with arbitrary smoothness, into an addressable one.
• Real-world applications:
  • Welding and painting robots that must follow a prescribed path while moving as quickly as allowed.
  • CNC machines following geometric tool paths.
  • Autonomous vehicles following a given route.
  • Robot arms performing contour-following tasks such as the rounded-rectangle path inspired by the ISO-9283 norm used in the evaluation.
• Industry relevance: The reported computation-time reductions, of more than 50 percent overall and over 90 percent in some cases at N = 100, point toward online trajectory generation. The authors explicitly name online applications as the motivating target, suggesting deployment on controllers where planning must happen quickly.

Future Directions

• Applying the approach in an online application framework, which the authors state will be addressed in future work.
• Using methods similar to those in model predictive control to reduce computation time further.
• Establishing a formal proof of the relationship between the maximized-path-speed problem and the conventional minimum-time problem, which the authors note does not currently exist.
• Deciding in practice when the B-spline variant's extra computation (higher t_comp. than the piecewise-linear variant, though still low) is worth the smooth jerk profile.

Target Audience

Researchers and graduate students in robotics and control who work on trajectory planning, path following, and numerical optimal control; engineers implementing motion planning for industrial manipulators, machine tools, or autonomous vehicles; and readers interested in reformulations that convert nonlinear path-following problems into linear programs solvable within a sequential convex programming framework. Familiarity with manipulator dynamics, path parameterization, B-splines, and convex optimization will make the paper substantially easier to follow.

Authors’ abstract

In this paper the computational challenges of time-optimal path following are addressed. The standard approach is to minimize the travel time, which inevitably leads to singularities at zero path speed, when reformulating the optimization problem in terms of a path parameter. Thus, smooth trajectory generation while maintaining a low computational effort is quite challenging, since the singularities have to be taken into account. To this end, a different approach is presented in this paper. This approach is based on maximizing the path speed along a prescribed path. Furthermore, the approach is capable of planning smooth trajectories numerically efficient. Moreover, the discrete reformulation of the underlying problem is linear in optimization variables.