On the piano movers' problem: V. The case of a rod moving in three-dimensional space amidst polyhedral obstacles

This paper, a fifth in a series, solves some additional 3-D special cases of the ?piano movers”? problem, which arises in robotics. The main problem solved in this paper is that of planning the motion of a rod moving amidst polyhedral obstacles. We present polynomial-time motion-planning algorithms for this case, using the connectivity-graph technique described in the preceding papers. We also study certain more general polyhedral problems, which arise in the motion planning problem considered here but have application to other similar problems. Application of these techniques to the problem of planning the motion of a general polyhedral body moving in 3-space amidst polyhedral obstacles is also described.     

Motion Planning in Environments with Low Obstacle Density

We present a simple and efficient paradigm for computing the exact solution of the motion planning problem in environments with a low obstacle density. Such environments frequently occur in practical instances of the motion planning problem. The complexity of the free space for such environments is known to be linear in the number of obstacles. Our paradigm is a new cell decomposition approach to motion planning and exploits properties that follow from the low density of the obstacles in the robot's workspace. These properties allow us to decompose the workspace, subject to some constraints, rather than to decompose the higher-dimensional free configuration space directly. A sequence of uniform steps transforms the workspace decomposition into a free space decomposition of asymptotically the same size. The approach leads to nearly optimal O(n \log n) motion planning algorithms for free-flying robots with any fixed number of degrees of freedom in workspaces with low obstacle density. Received October 17, 1995, and in revised form July 8, 1997, and February 23, 1998.     

The complexity of the free space for a robot moving amidst fat obstacles

We propose a new definition of fatness of geometric objects and compare it with alternative definitions. We show that, under some realistic assumptions, the complexity of the free space for a robot, with any fixed number of degrees of freedom moving in a d-dimensional Euclidean workspace with fat obstacles, is linear in the number of obstacles. The complexity of motion planning algorithms depends on the complexity of the robot's free space, and theoretically, the complexity of the free space can be very high. Thus, our result opens the way to devising provable efficient motion planning algorithms in certain realistic settings.     

Heuristic optimization methods for motion planning of autonomous agricultural vehicles

In this paper, two heuristic optimization techniques are tested and compared in the application of motion planning for autonomous agricultural vehicles: Simulated Annealing and Genetic Algorithms. Several preliminary experimentations are performed for both algorithms, so that the best neighborhood definitions and algorithm parameters are found. Then, the two tuned algorithms are run extensively, but for no more than 2000 cost function evaluations, as run-time is the critical factor for this application. The comparison of the two algorithms showed that the Simulated Annealing algorithm achieves the better performance and outperforms the Genetic Algorithm. The final optimum found by the Simulated Annealing algorithm is considered to be satisfactory for the specific motion planning application.     

Motion of a Swinging Atwood’s Machine: Simulation and Analysis with Mathematica

A generalized model of the Atwood machine when one body is constrained to move along a vertical axis while the other one can swing in a plane is considered. Combining symbolic and numerical calculations, we have obtained equations of motion of the system and analyzed their solutions. We have shown that oscillation can completely modify a motion of the system while the simple Atwood machine demonstrates only the uniformly accelerated motion of the bodies. The validity of the results obtained is demonstrated by means of the simulation of motion of swinging Atwood’s machine with the computer algebra system Wolfram Mathematica.     

Modeling and identification of emotional aspects of locomotion

The studies of emotional facial expressions and emotional body language are currently receiving a lot of attention in the cognitive sciences. In this project, we study implicit bodily expression of emotions during standard motions, such as walking forwards.An underlying assumption of our work is that all human motion is optimal in some sense and that different emotions induce different objective functions, which result in different deformations of normal motion.We created a 3D rigid-body model of a human of which we use the forward dynamics simulation in an optimal control context. We performed two kinds of optimizations: (i) reconstruction of dynamic quantities, such as joint torques, of pre-recorded data of emotional walking motions and (ii) forward optimization that generates neutral and varied walking motions using different objective functions. Optimizations are performed with the software package MUSCOD-II, which uses a direct multiple-shooting discretization scheme. The results of this work form the foundation for further analysis of emotional motions using inverse optimal control methods.     

A cutting plane approach to capacitated lot-sizing with start-up costs

We consider a mixed integer model for multi-item single machine production planning, incorporating both start-up costs and machine capacity. The single-item version of this model is studied from the polyhedral point of view and several families of valid inequalities are derived. For some of these inequalities, we give necessary and sufficient facet inducing conditions, and efficient separation algorithms. We use these inequalities in a cutting plane/branch and bound procedure. A set of real life based problems with 5 items and up to 36 periods is solved to optimality.     

Self-propulsion of a body with rigid surface and variable coefficient of lift in a perfect fluid

We study the system of a 2D rigid body moving in an unbounded volume of incompressible, vortex-free perfect fluid which is at rest at infinity. The body is equipped with a gyrostat and a so-called Flettner rotor. Due to the latter the body is subject to a lifting force (Magnus effect). The rotational velocities of the gyrostat and the rotor are assumed to be known functions of time (control inputs). The equations of motion are presented in the form of the Kirchhoff equations. The integrals of motion are given in the case of piecewise continuous control. Using these integrals we obtain a (reduced) system of first-order differential equations on the configuration space. Then an optimal control problem for several types of the inputs is solved using genetic algorithms.     

On the Suitability of Different Online Gait Generation Methods for Pre-Defined Footsteps

Detailed dynamical modeling is the basis for simulation and model based control. In this contribution the Projection Equation is used for the modeling of a biped walking machine, resulting in the equations of motion which are needed for gait generation and verification of its stability. For biped robots one main issue is the generation of stable trajectories for the center of mass (CoM). Several different approaches based on the Zero Moment Point (ZMP) scheme have been presented in the past. Due to the complex dynamic structure of bipedal robots most of the considered algorithms use a linear inverted pendulum as a simplified model. This results in a decoupling of the ZMP equations in lateral and forward direction, but limits the trajectories to a constant height of the CoM. An extension of the well known LQR theory by future reference values has been proposed. This model based approach seems to perform quite well, but does not allow the consideration of constraints on the position of the ZMP. This limitation is removed by the use of Model Predictive Control (MPC) with inequality constraints. By extending this approach to a time invariant one the restriction to a constant height of the CoM is no longer necessary. Both methods as well as the time invariant approach for variable CoM heights have been evaluated in simulations and will be experimentally verified on a real robot soon. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Nonlinear free oscillations of a rotating solid body in a Newtonian force field

Nonlinear free oscillations of a rotating axisymmetrical solid body are considered with respect to the center of mass and with the body moving in a Newtonian force field. To construct periodic solutions of nonlinear differential equations of the motion, some algorithms, which are based on a modification of the extension method of solution with respect to a parameter, are used. The stability of nonlinear oscillations of the rotating solid body are studied with respect to stationary motions, some amplitude-frequency characteristics and forms of oscillations of the body are formulated for different values of its inertial parameters.Translated from Dinamicheskie Sistemy, No. 8, pp. 3–8, 1989.     

Operator non-availability periods

In the scheduling literature, the notion of machine non-availability periods is well known, for instance for maintenance. In our case of planning chemical experiments, we have special periods (the week-ends, holidays, vacations) where the chemists are not available. However, human intervention by the chemists is required to handle the starting and termination of the experiments. This gives rise to a new type of scheduling problems, namely problems of finding schedules that respect the operator non-availability periods. These problems are analyzed on a single machine with the makespan as criterion. Properties are described and performance ratios are given for list scheduling and other polynomial-time algorithms.     

A modular and efficient approach to computational modeling and sensitivity analysis of robot and human motion dynamics

In this paper a new class library for the computation of the forward multi-body-system (MBS) dynamics of robots and biomechanical models of human motion is presented. By the developed modular modeling approach the library can be flexibly extended by specific modeling elements like joints with specific geometry or different muscle models and thus can be applied efficiently for a number of dynamic simulation and optimization problems. The library not only provides several methods for solving the forward dynamics problem (like articulated body or composite rigid body algorithms) which can transparently be exchanged. Moreover, the numerical solution of optimal control problems, like in the forward dynamics optimization of human motion, is significantly facilitated by the computation of the sensitivity matrix with respect to the control variables. Examples are given to demonstrate the efficiency of the approach. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Improving the inverse kinematics reconstruction of human movement from motion capture data

Marker based motion capture methods are well known techniques for the acquisition of human motion. For the kinematic and dynamic analysis the recorded data is usually used to drive a rigid body model of the human body. Skin artifacts, which are caused by skin deformation and displacement of markers with respect to the underlying bone, are regarded as the most critical source of error in the inverse kinematics reconstruction of human movement. State-of-the-art algorithms use optimization and multibody models with joint constraints in order to overcome these effects. This work presents an optimization based inverse kinematics approach, which is able to adapt the model kinematics subject-specifically and to compute the time trajectories of kinematic variables from marker data including velocity and acceleration. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Neuron phase shift adaptive to time delay in locomotor control

Based on neurophysiological evidence, theoretical studies have shown that walking can be generated by mutual entrainment of oscillations of a central pattern generator (CPG) and a body. However, it has also been shown that the time delay in the sensorimotor loop destabilizes mutual entrainment, and results in the failure to walk. Recently, it has been reported that if (a) the neuron model used to construct the CPG is replaced by physiologically faithful neuron model (Bonhoeffer–Van der Pol type) and (b) the mechanical impedance of the body (muscle viscoelasticity) is controlled depending on the angle between two legs, the phase relationship between CPG activity and body motion could be flexibly locked according to the loop delay and, therefore, mutual entrainment can be stabilized. That is, locomotor control adaptive to the loop delay can emerge from the coupling between CPG and body. Here, we call this mechanism flexible-phase locking. In this paper, we construct a system of coupled oscillators as a simplified model of a walking system to theoretically investigate the mechanism of flexible-phase locking, and to analyze the simplified model. The analysis suggests that the following are required as the essential mechanism: (i) an asymptotically stable limit cycle of the coupling system of CPG and body and (ii) a sign difference between afferent and efferent coupling coefficients.     

SOKOBAN and other motion planning problems

We consider a natural family of motion planning problems with movable obstacles and obtain hardness results for them. Some members of the family are shown to be PSPACE-complete thus improving and extending (and also simplifying) a previous NP-hardness result of Wilfong. The family considered includes a motion planning problem which forms the basis of a popular computer game called SOKOBAN. The decision problem corresponding to SOKOBAN is shown to be NP-hard. The motion planning problems considered are related to the “warehouseman's problem” considered by Hopcroft, Schwartz and Sharir, and to geometric versions of the motion planning problem on graphs considered by Papadimitriou, Raghavan, Sudan and Tamaki.     

具有可变配送费用和固定配送时刻的单机排序问题

研究了单机环境下生产与配送的协同排序问题.有多个工件需要在一台机器上进行加工,加工完的工件需要分批配送到一个客户.每批工件只能在固定的几个配送时刻出发,不同的配送时刻对应着不同的配送费用.我们的目标是找到生产与配送的协同排序,极小化排序的时间费用与配送费用的加权和.研究了排序理论中主要的四个目标函数,构建了单机情况下的具体模型,分析了问题的复杂性,对于配送费用单调非增的情况给出了它们的最优算法.     

P‖Cmin随机算法研究

本文研究了P‖Cmin的随机算法及其最坏情况界，我们给出了Pm‖Cmin在线排序问题新的随机上界，并给出了P2‖Cmin的最好随机算法，其最坏情况界为2／3。对P2‖Cmin已知工件加工时间递减半在线模型，我们给出了一最坏情况界为6／7的随机算法并证明了它为最好的。     

Passive walking towards running

Passive walking emerges autonomously on a slight slope without an external input of energy. It is known that the walking motion on a steep slope evolves into a chaotic motion. In this paper a biped model for walking and running is presented, and a strategy is proposed to expand the range of stable passive walking by using a chaos-control technique based on the Ott?–?Grebogi?–?Yorke method. The resultant controller is a discrete type so that the input value changes at every step, and the generated walking motion is kept non-chaotic. Fast walking on a steep slope is achieved, and pseudorunning has also been realized in simulations. By adding an input to the biped model, in which the input corresponds to the effect of the artificial gravity field, it has been verified that pseudorunning can be realized on level ground.     

Study on feet forces' distributions,energy consumption and dynamic stability measure of hexapod robot during crab walking

This paper deals with the development of a dynamical model related to crab walking of a hexapod robot to determine the feet forces' distributions, energy consumption and dynamic stability measure considering the inertial effects of the legs on the system, which has not been attempted before. Both forward and inverse kinematic analyses of the robot are carried out with an assigned fixed global frame and subsequent local frames in the trunk body and joints of each leg. Coupled multi-body dynamic model of the robot is developed based on free-body diagram approach. Optimal feet forces and corresponding joint torques on all the legs are determined based on the minimization of the sum of the squares of joint torques, using quadratic programming (QP) method. An energy consumption model is developed to determine the minimum energy required for optimal values of feet forces. To ensure dynamically stable gaits, dynamic gait stability margin (DGSM) is determined from the angular momentum of the system about the supporting edges. Computer simulations have been carried out to test the effectiveness of the developed dynamic model with crab wave gaits on a banking surface. It is observed that when the swing leg touches the ground, impact forces (sudden shoot outs) are generated and their effects are also observed on the joints of the legs. The effects of walking parameters, namely trunk body velocity, body stroke, leg offset, body height, crab angle etc. on power consumption and stability during crab motion for duty factors (DFs) like 1/2, 2/3, 3/4 have also been studied.     

Path planning,modeling and simulation of an autonomous articulated heavy construction machine performing a loading cycle

This research presents path planning and tracking for an articulated large wheel loader during the travel portion of a loading cycle. The study proposes a methodology for path planning, modeling, simulation and control of such vehicles; the analysis focuses on all of these components together and explains the relation among them. The developed methodology for path planning takes into account the dynamics and the performance characteristics of the heavy construction articulated vehicles, it also takes into account the construction working site constraints. The path optimization criterion is based on distance and cusp minimization without neglecting the constraints imposed by the size of the vehicle and its stable turning radius. The proposed path planning methodology is an extension and an improvement for Reeds and Shepp algorithm for a point shortest path calculation. The optimal path is consisted of circular arcs and straight segments, the radius is constant and identical for each arc in the desired path, the radius assumed to be similar to the minimum turning radius of the machine. When optimizing articulated machine path; to best account for machine size and articulation; more than one approach are discussed and compared. The machine is modeled and simulated during tracing the pre-defined planned path. The machine model includes the main frames, tires and a steering controller. The developed PID controller is used to keep machine lateral position within the pre-defined path while traveling with constant speed. The results showed an acceptable optimized path which the machine is able to track closely.