Smooth and time‐optimal trajectory planning for industrial manipulators along specified paths

This article presents a method for determining smooth and time‐optimal path constrained trajectories for robotic manipulators and investigates the performance of these trajectories both through simulations and experiments. The desired smoothness of the trajectory is imposed through limits on the torque rates. The third derivative of the path parameter with respect to time, the pseudo‐jerk, is the controlled input. The limits on the actuator torques translate into state‐dependent limits on the pseudo‐acceleration. The time‐optimal control objective is cast as an optimization problem by using cubic splines to parametrize the state space trajectory. The optimization problem is solved using the flexible tolerance method. The experimental results presented show that the planned smooth trajectories provide superior feasible time‐optimal motion. © 2000 John Wiley & Sons, Inc.     

Knot calculation for spline fitting via sparse optimization

Curve fitting with splines is a fundamental problem in computer-aided design and engineering. However, how to choose the number of knots and how to place the knots in spline fitting remain a difficult issue. This paper presents a framework for computing knots (including the number and positions) in curve fitting based on a sparse optimization model. The framework consists of two steps: first, from a dense initial knot vector, a set of active knots is selected at which certain order derivative of the spline is discontinuous by solving a sparse optimization problem; second, we further remove redundant knots and adjust the positions of active knots to obtain the final knot vector. Our experiments show that the approximation spline curve obtained by our approach has less number of knots compared to existing methods. Particularly, when the data points are sampled dense enough from a spline, our algorithm can recover the ground truth knot vector and reproduce the spline.     

Approximation and estimation bounds for free knot splines

The fitting to data by splines has long been known to improve dramatically if the knots can be adjusted adaptively. To demonstrate the quality of the obtained free knot spline, it is essential to characterize its generalization ability. By utilizing the powerful techniques of the empirical process and approximation theory to address the estimation and approximation error bounds, respectively, the generalization ability of the free knot spline learning strategy is successfully characterized. We show that the Pseudo-dimension of free knot splines is essentially a linear function of the number of knots. A class of rather general loss functions is considered here and the squared loss is specially treated for its excellent property. We also provide some numerical results to demonstrate the utility of these theoretical results in guiding the process of choosing the appropriate knot numbers through the training data to avoid the overfitting/underfitting problem.     

Optimal trajectory generation algorithm for serial and parallel manipulators

In this paper, an Optimal Trajectory Generation Algorithm (OTGA) is developed for generating minimum-time smooth motion trajectories for serial and parallel manipulators. OTGA is divided into two phases. The first phase encompasses derivation of minimum-time optimal trajectory using cubic spline due to its less vibration and overshoot characteristics. Although cubic splines are widely used in robotics, velocity and acceleration ripples in the first & last knots can worsen manipulator trajectory. The second phase includes changing cubic spline interpolation in the first and last knots of optimized trajectory with 7th order polynomial for having zero jerk at the beginning and end points of trajectory. Performing this modification eliminate undesired worsening in the trajectory and provide smoother start and stop of joint motions. Particle Swarm Optimization (PSO) is chosen as optimization algorithm because of its easy implementation and successful optimization performance. OTGA has been tested in simulation for PUMA robot and results are compared with algorithms proposed by earlier authors. In addition, a discrete-time PID control scheme for PUMA robot is designed for comparing energy consumption of OTGA with algorithms developed by previous authors. Comparison results illustrated that OTGA is the better trajectory generation algorithm than the others.     

Approximate merging of B-spline curves via knot adjustment and constrained optimization

This paper addresses the problem of approximate merging of two adjacent B-spline curves into one B-spline curve. The basic idea of the approach is to find the conditions for precise merging of two B-spline curves, and perturb the control points of the curves by constrained optimization subject to satisfying these conditions. To obtain a merged curve without superfluous knots, we present a new knot adjustment algorithm for adjusting the end k knots of a kth order B-spline curve without changing its shape. The more general problem of merging curves to pass through some target points is also discussed.     

计算机数控系统光滑时间最优轨迹规划

基于控制向量参数化(CVP)方法, 研究了计算机数控(CNC)系统光滑时间最优轨迹规划方法. 通过在规划问题中引入加加速度约束, 实现轨迹的光滑给进. 引入时间归一化因子, 将加加速度约束的时间最优轨迹规划问题转化为固定时间的一般性最优控制问题. 以路径参数对时间的三阶导数(伪加加速度)和终端时刻为优化变量, 并采用分段常数近似伪加加速度, 将最优控制问题转化为一般的非线性规划(NLP)问题进行求解. 针对加加速度、加速度等过程不等式约束, 引入约束凝聚函数, 将过程约束转化为终端时刻约束, 从而显著减少约束计算. 构造目标和约束函数的Hamiltonian函数, 利用伴随方法获得求解NLP问题所需的梯度.     

Subdivision Surfaces with Creases and Truncated Multiple Knot Lines

We deal with subdivision schemes based on arbitrary degree B‐splines. We focus on extraordinary knots which exhibit various levels of complexity in terms of both valency and multiplicity of knot lines emanating from such knots. The purpose of truncated multiple knot lines is to model creases which fair out. Our construction supports any degree and any knot line multiplicity and provides a modelling framework familiar to users used to B‐splines and NURBS systems.     

Constrained minimum-time path planning for robot manipulators viavirtual knots of the cubic B-spline functions

The B-spline functions are used to generate the constrained minimum-time path for a robot manipulator. The interpolated path via B-spline functions is determined via a unique set of virtual knots so that the robot path can pass every intermediate knot and satisfy the boundary conditions. The local control property of the B-spline functions can also be utilized to simplify the involved computational complexities. The flexible polyhedron search algorithm is used to generate the near minimum-time path with velocity, acceleration, and jerk constraints on every intermediate point. This approach can simplify the formulation and procedures for generating the near minimum-time cubic B-spline path. The use of this method to generate the constrained minimum-time joint trajectories for a PUMA 560 robot is discussed as an example     

Surface reconstruction using bivariate simplex splines on Delaunay configurations

Recently, a new bivariate simplex spline scheme based on Delaunay configuration has been introduced into the geometric computing community, and it defines a complete spline space that retains many attractive theoretic and computational properties. In this paper, we develop a novel shape modeling framework to reconstruct a closed surface of arbitrary topology based on this new spline scheme. Our framework takes a triangulated set of points, and by solving a linear least-square problem and iteratively refining parameter domains with newly added knots, we can finally obtain a continuous spline surface satisfying the requirement of a user-specified error tolerance. Unlike existing surface reconstruction methods based on triangular B-splines (or DMS splines), in which auxiliary knots must be explicitly added in advance to form a knot sequence for construction of each basis function, our new algorithm completely avoids this less-intuitive and labor-intensive knot generating procedure. We demonstrate the efficacy and effectiveness of our algorithm on real-world, scattered datasets for shape representation and computing.     

Optimal trajectory planning for industrial robots

An analysis of the results of an algorithm for optimal trajectory planning of robot manipulators is described in this paper. The objective function to be minimized is a weighted sum of the integral squared jerk and the execution time. Two possible primitives for building the trajectory are considered: cubic splines or fifth-order B-splines. The proposed technique allows to set constraints on the robot motion, expressed as upper bounds on the absolute values of velocity, acceleration and jerk. The described method is then applied to a 6-d.o.f. robot (a Cartesian gantry manipulator with a spherical wrist); the results obtained using the two different primitives are presented and discussed.     

Smooth time-optimal tool trajectory generation for CNC manufacturing systems

An optimization approach is proposed in this paper for generating smooth and time-optimal path constrained tool trajectory for Cartesian computer numerical control (CNC) manufacturing systems. The desired smooth time-optimal trajectory generation (STOTG) problem is formulated as a general optimal control problem. And axis jerk (derivative of acceleration with respect to time) constraints are introduced into this problem to remove discontinuities of the acceleration profiles. The desired smoothness of the trajectory can be accomplished by adjusting the values of jerk constraints. A control vector parameterization (CVP) method is applied to convert the optimal control problem into a nonlinear programming (NLP) problem which can be solved conveniently and effectively. The third derivative of the path parameter with respect to time (pseudo-jerk) and jerk act as optimization variables. The pseudo-jerk is approximated as piecewise constant, thus for at least second-order continuous parametric path, the resulted optimized trajectory with respect to time is also at least second-order continuous. Sequential quadratic programming (SQP) method is used to solve the NLP problem, through which numerical solution is obtained. Non-smooth (i.e. without considering jerk constraints) time-optimal trajectory generation (non-STOTG) problem is also considered in this paper for the purpose of comparison. Solutions of time-optimal trajectory generation (TOTG) problems for two test paths are performed to verify the effectiveness of the proposed approach.     

Minimum jerk motion planning for a prosthetic finger

In this paper we propose a method, based on both physiologic and engineering considerations, for the motion planning of a prosthetic finger. In particular, we exploit a minimum jerk approach to define the trajectory in the Cartesian space. Then, cubic splines are adopted in the joint space. The redundancy problem arising from the presence of three links is solved by assuming that there is a constant ratio between the second and the third joint motion. The value of the proportional constant is determined by minimizing the maximum jerk in the joint space. It is found that this constant value can be suboptimally but effectively set to one for all the movements. This approach guarantees a natural movement of the finger as well as reduced vibrations in the mechanical structure and increased control performances. © 2004 Wiley Periodicals, Inc.     

Smooth trajectory planning for a parallel manipulator with joint friction and jerk constraints

In order to achieve better tracking accuracy effectively, a new smooth and near time-optimal trajectory planning approach is proposed for a parallel manipulator subject to kinematic and dynamic constraints. The complete dynamic model is constructed with consideration of all joint frictions. The presented planning problem can be solved efficiently by formulating a new limitation curve for dynamic constraints and a reduced form for jerk constraints. The motion trajectory is planned with quartic and quintic polynomial splines in Cartesian space and septuple polynomial splines in joint space. Experimental results show that smaller tracking error can be obtained. The developed method can be applied to any robots with analytical inverse kinematic and dynamic solutions.     

Degree elevation of unified and extended spline curves

Unified and extended splines （UE-splines）, which unifl and extend polynomial, trigonometric, and hyperbolic B-splines, inherit most properties of B-splines and have some advantages over B-splines. The interest of this paper is the degree elevation algorithm of UE-spline curves and its geometric meaning. Our main idea is to elevate the degree of UE-spline curves one knot interval by one knot interval. First, we construct a new class of basis functions, called bi-order UE-spline basis flmctions which are defined by the integral definition of splines. Then some important properties of bi-order UE-splines are given, especially for tile transformation formulae of the basis functions before and after inserting a knot into the knot vector. Finally, we prove that the degree elevation of UE-spline curves can be interpreted as a process of corner cutting on the control polygons, just as in the manner of B-splines. This degree elevation algorithm possesses strong geometric intuition.     

Solving minimum distance problems with convex or concave bodies using combinatorial global optimization algorithms.

Determining the minimum distance between convex objects is a problem that has been solved using many different approaches. On the other hand, computing the minimum distance between combinations of convex and concave objects is known to be a more complicated problem. Most methods propose to partition the concave object into convex subobjects and then solve the convex problem between all possible subobject combinations. This can add a large computational expense to the solution of the minimum distance problem. In this paper, an optimization-based approach is used to solve the concave problem without the need for partitioning concave objects into convex pieces. Since the optimization problem is no longer unimodal (i.e., has more than one local minimum point), global optimization techniques are used. Simulated Annealing (SA) and Genetic Algorithms (GAs) are used to solve the concave minimum distance problem. In order to reduce the computational expense, it is proposed to replace the objects' geometry by a set of points on the surface of each body. This reduces the problem to an unconstrained combinatorial optimization problem, where the combination of points (one on the surface of each body) that minimizes the distance will be the solution. Additionally, if the surface points are set as the nodes of a surface mesh, it is possible to accelerate the convergence of the global optimization algorithm by using a hill-climbing local optimization algorithm. Some examples using these novel approaches are presented.     

Elitist clonal selection algorithm for optimal choice of free knots in B-spline data fitting

Data fitting with B-splines is a challenging problem in reverse engineering for CAD/CAM, virtual reality, data visualization, and many other fields. It is well-known that the fitting improves greatly if knots are considered as free variables. This leads, however, to a very difficult multimodal and multivariate continuous nonlinear optimization problem, the so-called knot adjustment problem. In this context, the present paper introduces an adapted elitist clonal selection algorithm for automatic knot adjustment of B-spline curves. Given a set of noisy data points, our method determines the number and location of knots automatically in order to obtain an extremely accurate fitting of data. In addition, our method minimizes the number of parameters required for this task. Our approach performs very well and in a fully automatic way even for the cases of underlying functions requiring identical multiple knots, such as functions with discontinuities and cusps. To evaluate its performance, it has been applied to three challenging test functions, and results have been compared with those from other alternative methods based on AIS and genetic algorithms. Our experimental results show that our proposal outperforms previous approaches in terms of accuracy and flexibility. Some other issues such as the parameter tuning, the complexity of the algorithm, and the CPU runtime are also discussed.     

Reentry Trajectory Optimization for Hypersonic Vehicles Using Fuzzy Satisfactory Goal Programming Method

Constrained reentry trajectory optimization for hypersonic vehicles is a challenging job. In particular, this problem becomes more difficult when several objectives with preemptive priorities are expected for different purposes. In this paper, a fuzzy satisfactory goal programming method is proposed to solve the multi-objective reentry trajectory optimization problem. Firstly, direct collocation approach is used to discretize the reentry trajectory optimal-control problem with nonlinear constraints into nonlinear multiobjective programming problem with preemptive priorities, where attack angles and bank angles at nodes and collocation nodes are selected as control variables. Secondly, the preemptive priorities are transformed into the relaxed order of satisfactory degrees according to the principle that the objective with higher priority has higher satisfactory degree. Then the fuzzy satisfactory goal programming model is proposed. The balance between optimization and priorities is realized by regulating parameter λ, such that the satisfactory reentry trajectory can be acquired. The simulation demonstrates that the proposed method is effective for the multi-objective reentry trajectory optimization of hypersonic vehicles.     

B-Spline Curve Approximation by Utilizing Big Bang-Big Crunch Method

The location of knot points and estimation of the number of knots are undoubtedly known as one of the most difficult problems in B-Spline curve approximation. In the literature, different researchers have been seen to use more than one optimization algorithm in order to solve this problem. In this paper, Big Bang-Big Crunch method (BB-BC) which is one of the evolutionary based optimization algorithms was introduced and then the approximation of B-Spline curve knots was conducted by this method. The technique of reverse engineering was implemented for the curve knot approximation. The detection of knot locations and the number of knots were randomly selected in the curve approximation which was performed by using BB-BC method. The experimental results were carried out by utilizing seven different test functions for the curve approximation. The performance of BB-BC algorithm was examined on these functions and their results were compared with the earlier studies performed by the researchers. In comparison with the other studies, it was observed that though the number of the knot in BB-BC algorithm was high, this algorithm approximated the B-Spline curves at the rate of minor error.     

Image approximation by variable knot bicubic splines

This paper presents a degree of freedom or information content analysis of images in the context of digital image processing. As such it represents an attempt to quantify the number of truly independent samples one gathers with imaging devices. The degrees of freedom of a sampled image itself are developed as an approximation problem. Here, bicubic splines with variable knots are employed in an attempt to answer the question as to what extent images are finitely representable in the context of digital sensors and computers. Relatively simple algorithms for good knot placement are given and result in spline approximations that achieve significant parameter reductions at acceptable error levels. The knots themselves are shown to be useful as an indicator of image activity and have potential as an image segmentation device, as well as easy implementation in CCD signal processing and focal plane smart sensor arrays. Both mathematical and experimental results are presented.     

Trajectory control of biomimetic robots for demonstrating human arm movements

This study describes the trajectory control of biomimetic robots by developing human arm trajectory planning. First, the minimum jerk trajectory of the joint angles is produced analytically, and the trajectory of the elbow joint angle is modified by a time-adjustment of the joint motion of the elbow relative to the shoulder. Next, experiments were conducted in which gyro sensors were utilized, and the trajectories observed were compared with those which had been produced. The results showed that the proposed trajectory control is an advantageous scheme for demonstrating human arm movements.