An approach for optimization of robot-generated rigid-body interpolation using dynamic criteria

The present paper describes an approach for generating spatial trajectories in multibody systems including rigid–body rotations such that dynamic criteria such as forces, accelerations, velocities, etc. as well as limiting restrictions for the motion–generating mechanical device, e.g., a robot, can be considered. The task is to find a rigid–body interpolation that fulfills optimality criteria at the target trajectory as well as in the mechanical system. Application of general optimization methods fails due to the difficulty of finding feasible initial guesses that will converge. The present approach proposes to decouple the general problem into two stages, a first stage in which a pure trajectory optimization is carried out without regard of the mechanical system, and a second stage in which the carrying mechanical system is incorporated. The trajectory planning involves the use of splines of 5–th order as well as an SQP optimization for determining the spline support points as design variables. The approach is illustrated for the example of the generalized waiter problem. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Refolding Planar Polygons

This paper describes an algorithm for generating a guaranteed intersection-free interpolation sequence between any pair of compatible polygons. Our algorithm builds on prior results from linkage unfolding, and if desired it can ensure that every edge length changes monotonically over the course of the interpolation sequence. The computational machinery that ensures against self-intersection is independent from a distance metric that determines the overall character of the interpolation sequence. This decoupled approach provides a powerful control mechanism for determining how the interpolation should appear, while still assuring against intersection and guaranteeing termination of the algorithm. Our algorithm also allows additional control by accommodating a set of algebraic constraints that can be weakly enforced throughout the interpolation sequence.     

An error term and uniqueness for Hermite–Birkhoff interpolation involving only function values and/or first derivative values

This paper discusses various aspects of Hermite–Birkhoff interpolation that involve prescribed values of a function and/or its first derivative. An algorithm is given that finds the unique polynomial satisfying the given conditions if it exists. A mean value type error term is developed which illustrates the ill-conditioning present when trying to find a solution to a problem that is close to a problem that does not have a unique solution. The interpolants we consider and the associated error term may be useful in the development of continuous approximations for ordinary differential equations that allow asymptotically correct defect control. Expressions in the algorithm are also useful in determining whether certain specific types of problems have unique solutions. This is useful, for example, in strategies involving approximations to solutions of boundary value problems by collocation.     

Trajectory planning based on minimum absolute input energy for an LCD glass-handling robot

The main idea of this paper is to design a novel point-to-point (PTP) trajectory based on minimum absolute input energy (MAIE) for an LCD glass-handing robot, which is driven by a permanent magnet synchronous motor (PMSM). The mechatronic system is described by a mathematical model of electrical and mechanical coupling equations. To generate the MAIE PTP trajectory, we employ a high-degree polynomial and compare with the trapezoidal, cycloidal and zero-jerk trajectories for various constraint conditions, which satisfy their corresponding desired constraints of angular displacement, speed, acceleration and jerk at the start and end times. The real-coded genetic algorithm (RGA) is used to search for the coefficients of high-degree polynomials for the PTP trajectories, and the inverse of absolute input electrical energy is adopted as a fitness function. From numerical simulations, it is found that either increasing the degree number of polynomials or decreasing the constraints at the start and end times will decrease the absolute input electrical energy. The proposed methodology for designing the MAIE PTP trajectory can also be applied to any mechatronic system driven by a PMSM.     

Optimal control of the rectilinear motion of a rigid body on a rough plane by means of the motion of two internal masses

The problem of the optimal control of a rigid body moving along a rough horizontal plane due to motion of two internal masses is solved. One of the masses moves horizontally parallel to the line of motion of the main body, while the other mass moves in the vertical direction. Such a mechanical system models a vibration-driven robot–a mobile device able to move in a resistive medium without special propellers (e.g., wheels, legs or caterpillars). Periodic motions are constructed for the internal masses to ensure velocity-periodic motion of the main body with maximum average velocity, provided that the period is fixed and the magnitudes of the accelerations of the internal masses relative to the main body do not exceed prescribed limits. Based on the optimal solution obtained for a fixed period without any constraints imposed on the amplitudes of vibration of the internal masses, a suboptimal solution that takes such constraints into account is constructed.     

Generating a reference trajectory with defined kinematics for the IRb-6 manipulator

The fundamental problem in industrial robots control concerns algorithms generating reference trajectories.References [1–4] suggest generating algorithms of a reference trajectory, which are based on an arbitrary discretization of the manipulator's internal coordinates. Each point of discretization in the external space approximating a reference trajectory corresponds to known discretized internal coordinates of the manipulator.In [5–7], iteration methods of determining the internal coordinates corresponding to external coordinates of the reference trajectory point have been suggested. In this method of internal coordinates, determining the point of the reference trajectory is being approached in successive steps of an iterative computation. In [5], a modified iterative method of generation of a straight segment reference trajectory has been presented.Analytic formulae, which are the solution of an inverse problem of manipulator kinematics, enable design of trajectory generating algorithms which compute, in one step only, the internal coordinates of points lying exactly on the reference trajectory, with the accuracy resulting from the computer register length.In this paper, the author has presented an original PLAN2 computer algorithm generating reference trajectories of motion for a task. The kinematics of those trajectories is defined at selected points through which a task is to be passed, the distances between them being optional. The algorithm is based on formulae which are analytic solutions to an inverse problem for an IRb-6 manipulator kinematics.     

Robust Optimal Trajectory Planning for Robots by Stochastic Optimization

In the optimal control of industrial, field or service robots, the standard procedure is to determine first offline a reference trajectory and a feedforward control, based on some selected nominal values of the unknown stochastic model parameters, and to correct then the inevitable and increasing deviation of the state or performance of the robot from the prescribed state or performance of the system by online measurement and control actions. Due to the stochastic variations of the model parameters, increasing measurement and correction actions are needed during the process. By optimal stochastic trajectory planning (OSTP), based on stochastic optimization methods, the available a priori and sample information about the robot and its working environment is incorporated into the control process. Consequently, more robust reference trajectories and feedforward controls are obtained which cause much less online control actions. In order to maintain a high quality of the guiding functions, the reference trajectory and the feedforward control can be updated at some later time points such that additional information about the control process is available. After the presentation of the Adaptive Optimal Stochastic Trajectory Planning (AOSTP) procedure based on stochastic optimization methods, several numerical techniques for the computation of robust reference trajectories and feedforward controls under real-time conditions are presented. Additionally, numerical examples for a Manutec r3 industrial robot are discussed. The first one demonstrates real-time solutions of (OSTP) based on a sensitivity analysis of a before-hand calculated reference trajectory. The second shows the differences between reference trajectories based on deterministic methods and the stochastic methods introduced in this paper. Based on simulations of the robots behavior, the increased robustness of stochastic reference trajectories is demonstrated.     

Three-parametric robot manipulators with parallel rotational axes

The paper deals with asymptotic motions of 3-parametric robot manipulators with parallel rotational axes. To describe them we use the theory of Lie groups and Lie algebras. An example of such motions are motions with the zero Coriolis accelerations. We will show that there are asymptotic motions with nonzero Coriolis accelerations. We introduce the notions of the Klein subspace, the Coriolis subspace and show their relation to asymptotic motions of robot manipulators. The asymptotic motions are introduced without explicit use of the Levi-Civita connection.     

On the dynamic model and motion planning for a spherical rolling robot actuated by orthogonal internal rotors

The paper deals with the dynamics of a spherical rolling robot actuated by internal rotors that are placed on orthogonal axes. The driving principle for such a robot exploits nonholonomic constraints to propel the rolling carrier. A full mathematical model as well as its reduced version are derived, and the inverse dynamics are addressed. It is shown that if the rotors are mounted on three orthogonal axes, any feasible kinematic trajectory of the rolling robot is dynamically realizable. For the case of only two rotors the conditions of controllability and dynamic realizability are established. It is shown that in moving the robot by tracing straight lines and circles in the contact plane the dynamically realizable trajectories are not represented by the circles on the sphere, which is a feature of the kinematic model of pure rolling. The implication of this fact to motion planning is explored under a case study. It is shown there that in maneuvering the robot by tracing circles on the sphere the dynamically realizable trajectories are essentially different from those resulted from kinematic models. The dynamic motion planning problem is then formulated in the optimal control settings, and properties of the optimal trajectories are illustrated under simulation.     

An approach for solving nonlinear multi-objective separable discrete optimization problem with one constraint

We propose an exact solution approach for solving nonlinear multi-objective optimization problems with separable discrete variables and a single constraint. The approach converts the multi-objective problem into a single objective problem by using surrogate multipliers from which we find all the solutions with objective values within a given range. We call this the surrogate target problem which is solved by using an algorithm based on the modular approach. Computational experiments demonstrate the effectiveness of this approach in solving large-scale problems. A simple example is presented to illustrate an interactive decision making process.     

Energy-Optimal Multi-Goal Motion Planning for Planar Robot Manipulators

In this work, the energy-optimal motion planning problem for planar robot manipulators with two revolute joints is studied, in which the end-effector of the robot manipulator is constrained to pass through a set of waypoints, whose sequence is not predefined. This multi-goal motion planning problem has been solved as a mixed-integer optimal control problem in which, given the dynamic model of the robot manipulator, the initial and final configurations of the robot, and a set of waypoints inside the workspace of the manipulator, one has to find the control inputs, the sequence of waypoints with the corresponding passage times, and the resulting trajectory of the robot that minimizes the energy consumption during the motion. The presence of the waypoint constraints makes this optimal control problem particularly difficult to solve. The mixed-integer optimal control problem has been converted into a mixed-integer nonlinear programming problem first making the unknown passage times through the waypoints part of the state, then introducing binary variables to enforce the constraint of passing once through each waypoint, and finally applying a fifth-degree Gauss–Lobatto direct collocation method to tackle the dynamic constraints. High-degree interpolation polynomials allow the number of variables of the problem to be reduced for a given numerical precision. The resulting mixed-integer nonlinear programming problem has been solved using a nonlinear programming-based branch-and-bound algorithm specifically tailored to the problem. The results of the numerical experiments have shown the effectiveness of the approach.     

Application of Cauchy integrals and singular integral equations in scattered data problems

A new approach is suggested for constructing “smooth” surfaces which contain discontinuities in functional values or derivatives at prescribed locations. The approach is based on solving singular integral equations with Cauchy-type kernels. It is applicable in the interpolation or approximation of scattered data. We investigate, in particular, several two-dimensional biharmonic and triharmonic problems which have smooth solutions except on given line segments, across which different types of discontinuities occur. We also discuss some issues concerning the application of the approach in practical problems.     

An approach for optimization of loading cycles of hydraulic mining excavators

The present paper describes an optimization multi-stage approach for computing the optimal loading cycle of a heavy weight excavator along a predefined trajectory under dynamic constraints such as maximal ensuing forces, accelerations, and maximal allowed hydraulic power. The approach involves the use of splines of 3rd and 5th order for smooth interpolation of the spatial trajectory up to the level of linear and angular accelerations, as well as an SQP optimization routine to find the optimal end-effector motion law along the trajectory, which finally leads to strokes and pressures at the hydraulic actuators as a function of time. The approach can also be extended to other multi-body systems following a predetermined trajectory. The solution scheme can be included in a more general optimization routine aiming to optimize the trajectory itself. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Optimization algorithm for learning consistent belief rule-base from examples

A belief rule-based inference approach and its corresponding optimization algorithm deal with a rule-base with a belief structure called a belief rule base (BRB) that forms a basis in the inference mechanism. In this paper, a new learning method is proposed based on the given sample data for optimally generating a consistent BRB. The focus is given on the consistency of BRB knowing that the consistency conditions are often violated if the system is generated from real world data. The measurement of BRB inconsistency is incorporated in the objective function of the optimization algorithm. This process is formulated as a non-linear constraint optimization problem and solved using the optimization tool provided in MATLAB. A numerical example is demonstrated the effectiveness of the proposed algorithm.     

On cubic Hermite coalescence hidden variable fractal interpolation functions

Hermite interpolation is a very important tool in approximation theory and numerical analysis, and provides a popular method for modeling in the area of computer aided geometric design. However, the classical Hermite interpolant is unique for a prescribed data set,and hence lacks freedom for the choice of an interpolating curve, which is a crucial requirement in design environment. Even though there is a rather well developed fractal theory for Hermite interpolation that offers a large flexibility in the choice of interpolants, it also has the shortcoming that the functions that can be well approximated are highly restricted to the class of self-affine functions. The primary objective of this paper is to suggest a C1-cubic Hermite interpolation scheme using a fractal methodology, namely, the coalescence hidden variable fractal interpolation, which works equally well for the approximation of a self-affine and non-self-affine data generating functions. The uniform error bound for the proposed fractal interpolant is established to demonstrate that the convergence properties are similar to that of the classical Hermite interpolant. For the Hermite interpolation problem, if the derivative values are not actually prescribed at the knots, then we assign these values so that the interpolant gains global C2-continuity. Consequently, the procedure culminates with the construction of cubic spline coalescence hidden variable fractal interpolants. Thus, the present article also provides an alternative to the construction of cubic spline coalescence hidden variable fractal interpolation functions through moments proposed by Chand and Kapoor [Fractals, 15(1)(2007), pp. 41-53].     

The barycentric weights of rational interpolation with prescribed poles

We introduce a method for calculating rational interpolants when some (but not necessarily all) of their poles are prescribed. The algorithm determines the weights in the barycentric representation of the rationals; it simply consists in multiplying each interpolated value by a certain number, computing the weights of a rational interpolant without poles, and finally multiplying the weights by those same numbers. The supplementary cost in comparison with interpolation without poles is about (v + 2)N, where v is the number of poles and N the number of interpolation points. We also give a condition under which the computed rational interpolation really shows the desired poles.     

Behavioral Models for List Decoding

Recently it has been shown that list decoding of Reed-Solomon codes may be translated into a bivariate interpolation problem. The data consist of pairs in a finite field and the aim is to find a bivariate polynomial that interpolates the given pairs and is minimal with respect to some criterion. We present a systems theoretic approach to this interpolation problem. With the data points we associate a set of time series, also called trajectories. For this set of trajectories we construct the Most Powerful Unfalsified Model (MPUM). This is the smallest possible model that explains these trajectories. The bivariate polynomial is then derived from a specific polynomial representation of the MPUM.     

Cataloging graphs by generating them uniformly at random

We describe an algorithm for cataloging graphs by generating them uniformly at random. The method used is based on a recent algorithm by Dixon and Wilf that generates orbit representatives uniformly at random. The approach is refined to graphs with prescribed numbers of edges and vertices, and then applied to obtain the complete list of graphs on 10 vertices.     

Finding a representative nondominated set for multi-objective mixed integer programs

In this paper, we develop algorithms to find small representative sets of nondominated points that are well spread over the nondominated frontiers for multi-objective mixed integer programs. We evaluate the quality of representations of the sets by a Tchebycheff distance-based coverage gap measure. The first algorithm aims to substantially improve the computational efficiency of an existing algorithm that is designed to continue generating new points until the decision maker (DM) finds the generated set satisfactory. The algorithm improves the coverage gap value in each iteration by including the worst represented point into the set. The second algorithm, on the other hand, guarantees to achieve a desired coverage gap value imposed by the DM at the outset. In generating a new point, the algorithm constructs territories around the previously generated points that are inadmissible for the new point based on the desired coverage gap value. The third algorithm brings a holistic approach considering the solution space and the number of representative points that will be generated together. The algorithm first approximates the nondominated set by a hypersurface and uses it to plan the locations of the representative points. We conduct computational experiments on randomly generated instances of multi-objective knapsack, assignment, and mixed integer knapsack problems and show that the algorithms work well.     

Path planning for robots under stochastic uncertainty *

In order to reduce large online measurement and correction expenses, the a priori informations on the random variations of the model parameters of a robot and its working environment are taken into account already at the planning stage. Thus, instead of solving a deterministic path planning problem with a fixed nominal parameter vector, here, the optimal velocity profile along a given trajectory in work space is determined by using a stochastic optimization approach. Especially, the standard polygon of constrained motion-depending on the nominal parameter vector-is replaced by a more general set of admissible motion determined by chance constraints or more general risk constraints. Robust values (with respect to stochastic parameter variations) of the maximum, minimum velocity, acceleration, deceleration, resp., can be obtained then by solving a univariate stochastic optimization problem Considering the fields of extremal trajectories, the minimum-time path planning problem under stochastic uncertainty can be solved now by standard optimal deterministic path planning methods