Institute for Systems Research

The work on Motion Description Languages (MDL) has been an effort to formalize a general-purpose robot programming language that allows one to incorporate both switching logic and differential equations. Extended MDL (MDLe) is a device-independent programming language for hybrid motion control, accommodating hybrid controllers, multi-robot interactions and robot-to-robot communications.

The purpose of this paper is to describe the "MDLe engine," a software tool that implements the MDLe language.

We have designed a basic compiler/software foundation for writing MDLe code. We provide a brief description of the MDLe syntax, implementation architecture, and functionality. Sample programs are presented together with the results of their execution on a set of physical and simulated mobile robots.

Evaluating the demagnetizing field directly requires work of O(N^2) for a grid of N cells and thus it is the bottleneck in computational micromagnetics. A fast hierarchical algorithm using multipole approximation is developed to evaluate the demagnetizing field. We first construct a mesh hierarchy and divide the grid into boxes of different levels. The lowest level box is the whole grid while the highest level boxes are just cells. The approximate field contribution from the cells contained in a box is characterized by the box attributes, which are obtained via multipole approximation. The algorithm computes field contributions from remote cells using attributes of appropriate boxes containing those cells, and it computes contributions from adjacent cells directly. Numerical results have shown that the algorithm requires work of O(NlogN) and at the same time it achieves high accuracy. It makes micromagnetic simulation in three dimensions feasible.

A hierarchical algorithm using multipole approximation speeds up the evaluation of the demagnetizing field, reducing computational cost from O(N^2) to O(NlogN). A hybrid 3D/1D rod model is adopted to compute the magnetostriction: a 3D model is used in solving the LLG equation for the dynamics of magnetization; then assuming that the rod is along z-direction, we take all cells with same z-cordinate as a new cell. The values of the magnetization and the effective field of the new cell are obtained from averaging those of the original cells that the new cell contains. Each new cell is represented as a mass-spring in solving the motion equation.

Numerical results include: 1. domain wall dynamics, including domain wall formation and motion; 2. effects of physical parameters, grid geometry, grid refinement and field step on H-M hysteresis curves; 3. magnetostriction curve.

First, we consider the problem of computing the controllability energyfunction without numerically solving the family of optimal control problems,or the associated Hamilton-Jacobi-Bellman equation, implied in its definition.Stochastically excited systems play a major role in our methodology. Wepresent a stochastic method for computing an estimate of the controllabilityfunction, and show that in certain situations the method provides an exactsolution. The procedure is tested on applications via Monte-Carlo experiments.

Then, we address the problem of numerically determining a Morse transformationfor a function with non-degenerate critical point at 0. We develop analgorithm for computing the desired nonlinear transformation and estimatingthe neighborhood on which the transformed controllability function isquadratic.

In the literature, examples of applied nonlinear balancing have been limited topseudo-balancing of 2-dimensional gradient systems and noting that in the caseof linear systems the energy functions approach reduces to the usual setting ofgramians. We apply our approach to numerically derive, for the first time,balanced representations of nonlinear state-space models. In particular, wepresent applications to a forced damped pendulum system and a forced dampeddouble pendulum system.

In this paper, we propose a hierarchical structure to solve finite horizon stochastic shortest pathproblems in parallel. In general, the approach reducesthe time complexity of the original problem to a logarithm level, which hassignificant practical meaning.

Stochastic optimization is a direct application of the above root finding problem if the SA is driven by a gradient estimate of steady state performance. We study the convergence properties of an SA driven by agradient estimator which observes an increasing number of samples from the Markov chain at each step of the SA's recursion. To show almost sure convergence to the optimizer, a framework of verifiable conditions is introduced which builds on the general SA conditions proposed for the root finding problem.

We also consider a difficulty sometimes encountered in applicationswhen selecting the set used in the projection operator of the SA algorithm.Suppose there exists a well-behaved positive recurrent region of the state process parameter space where the convergence conditions are satisfied; this being the ideal set to project on. Unfortunately, the boundaries of this projection set are not known a priori when implementing the SA. Therefore, we consider the convergence properties when the projection set is chosen to include regions outside the well-behaved region. Specifically, we consider an SA applied to an M/M/1 which adjusts the service rate parameter when the projection set includes parameters that cause the queue to be transient.

Finally, we consider an alternative SA where the recursion is driven by a sample average of observations. We develop conditions implying convergence for this algorithm which are based on a uniform large deviation upper bound and we present specialized conditions implyingthis property for finite state Markov chains.

In this paper, we propose the idea of process planning for small batch manufacturing, i.e., we simultaneously consider multiple parts and exploit opportunities for sharing manufacturing resources such that the process plan will be optimized over the entire set of parts. In particular, we discuss a geometric algorithm for multiple part cutter selection in 2-1/2D milling operations.

We define the 2-1/2D milling operations as covering the target region without intersecting with the obstruction region. This definition allows us to handle the open edge problem. Based on this definition, we first discuss the lower and upper bond of cutter sizes that are feasible for given parts. Then we introduce the geometric algorithm to find the coverable area for a given cutter. Following that, we discuss the approach of considering cutter loading time and changing time in multiple cutter selection for multiple parts. We represent the cutter selection problem as shortest path problem and use Dijkstra's algorithm to solve it. By using this algorithm, a set of cutters is selected to achieve the optimum machining cost for multiple parts.

Our research illustrates the multiple parts process planning approach that is suitable for small batch manufacturing. At the same time, the algorithm given in this paper clarifies the 2-1/2D milling problem and can also help in cutter path planning problem.

In this paper, we give a geometric algorithm to find the optimal cutters for 2-1/2D milling operations. We define the 2-1/2D milling operations as covering the target region without intersecting with the obstruction region. This definition allows us to handle the open edge problem. Based on this definition, we introduced the offsetting and inverse-offsetting algorithm to find the coverable area for a given cutter. Following that, we represent the cutter selection problem as shortest path problem and discuss the lower and upper bond of cutter sizes that are feasible for given parts. The Dijkstra's algorithm is used to solve the problem and thus a set of cutters is selected in order to achieve the optimum machining cost.

We believe the selection of optimum cutter combination can not only save manufacturing time but also help automatic process planning.