Cell-to-cell mapping method for time-optimal trajectory planning of multiple robot arm systems

This paper presents the results obtained by applying the cell-to-cell mapping method to solve the problem of the time-optimal trajectory planning for coordinated multiple robotic arms handling a common object along a specified geometric path. Based on the structure of the time-optimal trajectory control law, the continuous dynamic model of multiple arms is first approximated by a discrete and finite cell-to-cell mapping on a two-dimensional cell space over a phase plane. The optimal trajectory and the corresponding control are then determined by using the cell-to-cell mapping and a simple search algorithm. To further improve the computational efficiency and to allow for parallel computation, a hierarchical search algorithm consisting of a multiple-variable optimization on the top level and a number of cell-to-cell searches on the bottom level is proposed and implemented in the paper. Besides its simplicity, another distinguishing feature of the cell-to-cell mapping methods is the generation of all optimal trajectories for a given final state and all possible initial states through a single searching process. For most of the existing trajectory planning methods, the planning process can be started only when both the initial and final states have been specified. The cell-to-cell method can be generalized to any optimal trajectory planning problem for a multiple robotic arms system.     

Learning Robot Force/Position Control for Repetitive High Speed Applications with Unknown Non–Linear Contact Stiffness

This paper proposes a learning robot force/position control for high speed force trajectory following. Following high speed force trajectories in different repetitve robotic applications is a challenging field in robot force control. If the end–effector should provide a contact force while following a position trajectory in the non–force controlled direction a parallel force / position control is suitable. However, when it comes to high speed tasks this force control method reaches its limit. The problem can be solved by using an iterative learning control method in combination with the parallel force/position control. In this paper the learning force control method is introduced and experimental results are presented. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Trajectory Modeling of Robot Manipulators in the Presence of Obstacles

This paper presents two different strategies for the problem of the optimal trajectory planning of robot manipulators in the presence of fixed obstacles. The first strategy is related to the situation where the trajectory must pass through a given number of points. The second strategy corresponds to the case where only the initial and final points are given. The optimal traveling time and the minimum mechanical energy of the actuators are considered together to build a multiobjective function. The trajectories are defined using spline functions and are obtained through offline computation for online operation. Sequential unconstrained minimization techniques (SUMT) have been used for the optimization. The obstacles are considered as three-dimensional objects sharing the same workspace performed by the robot. The obstacle avoidance is expressed in terms of the distances between potentially colliding parts. Simulation results are presented and show the efficiency of the general methodology used in this paper.     

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     

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)     

Financial scenario generation for stochastic multi-stage decision processes as facility location problems

The quality of multi-stage stochastic optimization models as they appear in asset liability management, energy planning, transportation, supply chain management, and other applications depends heavily on the quality of the underlying scenario model, describing the uncertain processes influencing the profit/cost function, such as asset prices and liabilities, the energy demand process, demand for transportation, and the like. A common approach to generate scenarios is based on estimating an unknown distribution and matching its moments with moments of a discrete scenario model. This paper demonstrates that the problem of finding valuable scenario approximations can be viewed as the problem of optimally approximating a given distribution with some distance function. We show that for Lipschitz continuous cost/profit functions it is best to employ the Wasserstein distance. The resulting optimization problem can be viewed as a multi-dimensional facility location problem, for which at least good heuristic algorithms exist. For multi-stage problems, a scenario tree is constructed as a nested facility location problem. Numerical convergence results for financial mean-risk portfolio selection conclude the paper.     

A learning trajectory for university students regarding the concept of vector

This paper presents and evaluates a hypothetical learning trajectory by which students bridge the transition from elementary to university-level instruction regarding the concept of vector. The trajectory consists of an instructional sequence of five tasks and begins with a problem in context. Each task is carried out with the support of a Virtual Interactive Didactic Scenario, accompanied by exploration and guided learning sheets, in which the problem is introduced through the simulation of the movement of a robotic arm. This proposal was implemented at the beginning of the SARS-CoV-2 pandemic using various digital media. Two teaching experiments were carried out with engineering students at a Mexican public university. We present the hypothetical learning trajectory that should be followed toward solving the task, and contrast it in each case with the students’ actual learning trajectory. The results show that more than 70 % of the students successfully transitioned from the geometrical vector representation of elementary physics to the algebraic one.     

Optimal control and properties of nonlinear multistage dynamical system for planning horizontal well paths

The goal of planning a horizontal well path is to obtain a trajectory that arrives at a given target subject to various constraints. In this paper, the optimal control problem subject to a nonlinear multistage dynamical system (NMDS) for horizontal well paths is investigated. Some properties of the multistage system are proved. In order to derive the optimality conditions, we transform the optimal control problem into one with control constraints and inequality-constrained trajectories by defining some functions. The properties of these functions are then discussed and optimality conditions for optimal control problem are also given. Finally, an improved simplex method is developed and applied to the optimal design for well Ci-16-Cp146 in Oil Field of Liaohe, and the numerical results illustrate the validity of both the model and the algorithm.     

Trajectory planning of redundant manipulators using genetic algorithms

The trajectory planning of redundant robots is an important area of research and efficient optimization algorithms are needed. This paper presents a new technique that combines the closed-loop pseudoinverse method with genetic algorithms. The results are compared with a genetic algorithm that adopts the direct kinematics. In both cases the trajectory planning is formulated as an optimization problem with constraints.     

Local search based heuristics for global optimization: Atomic clusters and beyond

Finding good solutions to large scale, hard, global optimization problems, is a demanding task with many relevant applications. It is well known that, in order to tackle a difficult problem, an algorithm has to incorporate all of the available information on the problem domain. However, as we will show in this paper, some general purpose methods and the ideas on which they are built can provide guidance towards the efficient solution of difficult instances. Most of this paper will be devoted to heuristic techniques applied to the problem of finding a minimum energy configuration of a cluster of atoms in R³${\mathbb{R}}^3$. This is a very relevant problem with a large set of applications which has triggered considerable research efforts in the last decade. We will show how some relatively simple ideas can be used to generate fairly efficient methods which have been employed to discover many new cluster structures. In this paper we will introduce some of the main algorithmic ideas which have proven to be particularly successful in the field of global optimization applied to atomic cluster conformation problems. We will mainly discuss Basin Hopping methods, as well as their population–based variant, and some specific technique based on “direct moves”. These methods, although designed for the specific problem, have a much wider applicability. In fact, one of the aims of this paper is also that of suggesting that similar ideas can be employed in order to design innovative methods even for totally different global optimization problems, like, e.g., circle packing and space trajectory planning.     

A light-propagation model for aircraft trajectory planning

Predicted air traffic growth is expected to double the number of flights over the next 20 years. If current means of air traffic control are maintained, airspace capacity will reach its limits. The need for increasing airspace capacity motivates improved aircraft trajectory planning in 4D (space+time). In order to generate sets of conflict-free 4D trajectories, we introduce a new nature-inspired algorithm: the light propagation algorithm (LPA). This algorithm is a wavefront propagation method that yields approximate geodesic solutions (minimal-in-time solutions) for the path planning problem, in the particular case of air-traffic congestion. In simulations, LPA yields encouraging results on real-world traffic over France while satisfying the specific constraints in air-traffic management.     

A genetic algorithm for robotic assembly line balancing

Flexibility and automation in assembly lines can be achieved by the use of robots. The robotic assembly line balancing (RALB) problem is defined for robotic assembly line, where different robots may be assigned to the assembly tasks, and each robot needs different assembly times to perform a given task, because of its capabilities and specialization. The solution to the RALB problem includes an attempt for optimal assignment of robots to line stations and a balanced distribution of work between different stations. It aims at maximizing the production rate of the line. A genetic algorithm (GA) is used to find a solution to this problem. Two different procedures for adapting the GA to the RALB problem, by assigning robots with different capabilities to workstations are introduced: a recursive assignment procedure and a consecutive assignment procedure. The results of the GA are improved by a local optimization (hill climbing) work-piece exchange procedure. Tests conducted on a set of randomly generated problems, show that the Consecutive Assignment procedure achieves, in general, better solution quality (measured by average cycle time). Further tests are conducted to determine the best combination of parameters for the GA procedure. Comparison of the GA algorithm results with a truncated Branch and Bound algorithm for the RALB problem, demonstrates that the GA gives consistently better results.     

Nonconvex piecewise linear knapsack problems

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.     

Spatial impedance control of two cooperative industrial manipulators

Nowadays robotic manipulators are considered to perform a wide range of tasks. Since robotic systems consisting of multiple manipulators are capable of handling a variety of tasks that cannot be executed by single manipulators, cooperation of multiple manipulators is becoming increasingly interesting in particular for industrial applications. The interaction with other manipulators, respectively the environment, requires an extension of the conventional position control in order to achieve a desired compliance, and thus to limit the interaction wrench so to avoid damaging the involved objects. In this contribution the cooperation of two industrial manipulators, a Stäubli RX130L (6-DOF) and a Stäubli TX90L mounted on a linear axis (constituting a redundant 7-DOF manipulator), is addressed applying an impedance control scheme. The manipulation task is to grasp an object with both manipulators and to follow a prescribed trajectory by simultaneously limiting the contact forces between the manipulators and the object and ensuring a compliant behavior towards the environment. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Convergence analysis of a global optimization algorithm using stochastic differential equations

We establish the convergence of a stochastic global optimization algorithm for general non-convex, smooth functions. The algorithm follows the trajectory of an appropriately defined stochastic differential equation (SDE). In order to achieve feasibility of the trajectory we introduce information from the Lagrange multipliers into the SDE. The analysis is performed in two steps. We first give a characterization of a probability measure (Π) that is defined on the set of global minima of the problem. We then study the transition density associated with the augmented diffusion process and show that its weak limit is given by Π.     

On some methods for entropy maximization and matrix scaling

We describe and survey in this paper iterative algorithms for solving the discrete maximum entropy problem with linear equality constraints. This problem has applications e.g. in image reconstruction from projections, transportation planning, and matrix scaling. In particular we study local convergence and asymptotic rate of convergence as a function of the iteration parameter. For the trip distribution problem in transportation planning and the equivalent problem of scaling a positive matrix to achieve a priori given row and column sums, it is shown how the iteration parameters can be chosen in an optimal way. We also consider the related problem of finding a matrix X, diagonally similar to a given matrix, such that corresponding row and column norms in X are all equal. Reports of some numerical tests are given.     

Omnidirectional walking of legged robots with a failed leg

This paper studies omnidirectional walking of a hexapod robot with a locked joint failure by proposing crab gaits and turning gaits. Due to the reduced workspace of a failed leg, fault-tolerant gaits have limitations in their mobility. As for crab gaits, an accessible range of the crab angle is derived for a given configuration of the failed leg. As for turning gaits, the conditions on turning trajectories guaranteeing fault tolerance are derived for spinning gaits and circling gaits. Based on the principles of fault-tolerant gait planning, periodic crab gaits and turning gaits are proposed in which a hexapod robot realizes tripod walking after a locked joint failure, having a reasonable stride length and stability margin. The proposed fault-tolerant gaits are then applied to an obstacle avoidance problem of a hexapod robot with a locked joint failure. The kinematic constraints of fault-tolerant gaits should be considered in planning the robot trajectory.     

A branch and bound network approach to the canonical constrained entropy problem

In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved.     

The turnpike property in finite-dimensional nonlinear optimal control

Turnpike properties have been established long time ago in finite-dimensional optimal control problems arising in econometry. They refer to the fact that, under quite general assumptions, the optimal solutions of a given optimal control problem settled in large time consist approximately of three pieces, the first and the last of which being transient short-time arcs, and the middle piece being a long-time arc staying exponentially close to the optimal steady-state solution of an associated static optimal control problem. We provide in this paper a general version of a turnpike theorem, valuable for nonlinear dynamics without any specific assumption, and for very general terminal conditions. Not only the optimal trajectory is shown to remain exponentially close to a steady-state, but also the corresponding adjoint vector of the Pontryagin maximum principle. The exponential closedness is quantified with the use of appropriate normal forms of Riccati equations. We show then how the property on the adjoint vector can be adequately used in order to initialize successfully a numerical direct method, or a shooting method. In particular, we provide an appropriate variant of the usual shooting method in which we initialize the adjoint vector, not at the initial time, but at the middle of the trajectory.