Recognizing polygonal parts from width measurements

Automatic recognition of parts is an important problem in many industrial applications. One model of the problem is: given a finite set of polygonal parts, use a set of “width” measurements taken by a parallel-jaw gripper to determine which part is present. We study the problem of computing efficient strategies (“grasp plans”), with the goal to minimize the number of measurements necessary in the worst case. We show that finding a minimum length grasp plan is -hard, and give a polynomial time approximation algorithm that is simple and produces a solution that is within a log factor from optimal.     

A viscoelastic analogy for solving 2-D electromagnetic problems

Solving a viscoelastic material boundary value problem provides the voltage, electric field and displacement current results to a certain class of electromagnetic problems. By means of the electromagnetic-viscoelastic analogy described herein, a solid mechanics finite element program can analyze a two-dimensional harmonic oscillation (constant frequency) electromagnetic problem for “lossy” dielectric materials. For this special class of electromagnetic field problems, the Maxwell equations reduce to a two-dimensional Laplace equation with complex coefficients. This form identically matches the viscoelasticity field equations.

This paper develops the electromagnetic-viscoelastic analogy from the basic governing field equations. The analogy is implemented in ABAQUS, a general solid mechanics finite element program. Simple one- and two-dimensional examples prove the accuracy and usefulness of the analogy.     

A simple decision model of counterproliferation

We develop a simple decision model of counterproliferation involving a status quo “incumbent” and a nuclear “entrant”. The problem is examined as a one-stage interaction in two phases: nuclear development and deployment. We examine the conditions that will influence the decision to move pre-emptively against a proliferator's nuclear program. Particular attention is given to the role of uncertainty in determining the expected costs of action at different points in the entrant's weapon's development and deployment cycle. The model permits us to determine the optimal time to act given varying levels of information concerning entrant behavior. In conclusion, we examine the tradeoffs between the expected costs of action and the costs of intelligence.     

Quasilinear conflict-controlled processes with additional restrictions

A class of conflict-controlled processes [1–3] with additional (“phase” type) restrictions on the state of the evader is considered. A similar unrestricted problem was considered in [4]. Unlike [5, 6] the boundary of the “phase” restrictions is not a “death line” for the evader. Sufficient conditions for the solvability of the pursuit and evasion problems are obtained, which complement a range of well-known results [5–10].^‡     

Linear optimization over permutation groups

For a permutation group given by a set of generators, the problem of finding “special” group members is NP-hard in many cases, e.g., this is true for the problem of finding a permutation with a minimum number of fixed points or a permutation with a minimal Hamming distance from a given permutation. Many of these problems can be modeled as linear optimization problems over permutation groups. We develop a polyhedral approach to this general problem and derive an exact and practically fast algorithm based on the branch & cut-technique.     

A greedy-algorithm characterization of valuated Δ-matroids

We study a variant of the greedy algorithm for weight functions defined on the system of subsets of a given finite set E and show that this algorithm works exactly for “valuated Δ-matroids.” Examples come from valuation theory.     

Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization

Cell flipping in VLSI design is an operation in which some of the cells are replaced with their “mirror images” with respect to a vertical axis, while keeping them in the same slot. After the placement of all the cells, one can apply cell flipping in order to further decrease the total area, approximating this objective by minimizing total wire length, channel width, etc. However, finding an optimal set of cells to be flipped is usually a difficult problem. In this paper we show that cell flipping can be efficiently applied to minimize channel density in the standard cell technology. We show that an optimal flipping pattern can be found in O(p(n/c)^c) time, where n, p and c denote the number of nets, pins and channels, respectively. Moreover, in the one channel case (i.e. when c = 1) the cell flipping problem can be solved in O(p log n) time. For the multi-channel case we present both an exact enumeration scheme and a mixed-integer program that generates an approximate solution very quickly. We present computational results on examples up to 139 channels and 65000 cells.     

Landmarks in graphs

Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a “graph space”. The robot can locate itself by the presence of distinctively labeled “landmark” nodes in the graph space. For a robot navigating in Euclidean space, visual detection of a distinctive landmark provides information about the direction to the landmark, and allows the robot to determine its position by triangulation. On a graph, however, there is neither the concept of direction nor that of visibility. Instead, we shall assume that a robot navigating on a graph can sense the distances to a set of landmarks.

Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position on the graph is uniquely determined. This suggests the following problem: given a graph, what are the fewest number of landmarks needed, and where should they be located, so that the distances to the landmarks uniquely determine the robot's position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot's position is called a “metric basis”, and the minimum number of landmarks is called the “metric dimension” of the graph. In this paper we present some results about this problem. Our main new results are that the metric dimension of a graph with n nodes can be approximated in polynomial time within a factor of O(log n), and some properties of graphs with metric dimension two.     

Construction of the value function in a pursuit-evasion game with three pursuers and one evader

A differential pursuit-evasion game is considered with three pursuers and one evader. It is assumed that all objects (players) have simple motions and that the game takes place in a plane. The control vectors satisfy geometrical constraints and the evader has a superiority in control resources. The game time is fixed. The value functional is the distance between the evader and the nearest pursuer at the end of the game. The problem of determining the value function of the game for any possible position is solved.

Three possible cases for the relative arrangement of the players at an arbitrary time are studied: “one-after-one”, “two-after-one”, “three-after-one-in-the-middle” and “three-after-one”. For each of the relative arrangements of the players a guaranteed result function is constructed. In the first three cases the function is expressed analytically. In the fourth case a piecewise-programmed construction is presented with one switchover, on the basis of which the value of the function is determined numerically. The guaranteed result function is shown to be identical with the game value function. When the initial pursuer positions are fixed in an arbitrary manner there are four game domains depending on their relative positions. The boundary between the “three-after-one-in-the-middle” domain and the “three-after-one” domain is found numerically, and the remaining boundaries are interior Nicomedean conchoids, lines and circles. Programs are written that construct singular manifolds and the value function level lines.     

An Approach to the Subproblem of the Cutting Angle Method of Global Optimization

The solution of the Subproblem of the Cutting Angle Method of Global Optimization for problems of minimizing increasing positively homogeneous of degree one functions is proved to be NP-Complete. For the proof of this fact we formulate another problem which we call “Dominating Subset with Minimal Weight”. This problem is also NP-Complete. An O(n²)-time algorithm is presented for approximate solution of Dominant Subset with Minimal Weight Problem. This problem can be expressed as a kind of Assignment Problem in which it is allowed to assign multiple tasks to a single processor. Experimental analysis of the algorithm is performed using the program implemented in ANSI-C. The results of the analysis show the efficiency of the proposed algorithm.Mathematics Subject Classification (2000): 65K05, 90C27, 68Q25     

Fuzzy logic in measurements

Our main interest in this paper is to translate from “natural language” into “system theoretical language”. This is of course important since a statement in system theory can be analyzed mathematically or computationally. We assume that, in order to obtain a good translation, “system theoretical language” should have great power of expression. Thus we first propose a new frame of system theory, which includes the concepts of “measurement” as well as “state equation”. And we show that a certain statement in usual conversation, i.e., fuzzy modus ponens with the word “very”, can be translated into a statement in the new frame of system theory. Though our result is merely one example of the translation from “natural language” into “system theoretical language”, we believe that our method is fairly general.     

3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.     

Eigenvalue interlacing and weight parameters of graphs

Eigenvalue interlacing is a versatile technique for deriving results in algebraic combinatorics. In particular, it has been successfully used for proving a number of results about the relation between the (adjacency matrix or Laplacian) spectrum of a graph and some of its properties. For instance, some characterizations of regular partitions, and bounds for some parameters, such as the independence and chromatic numbers, the diameter, the bandwidth, etc., have been obtained. For each parameter of a graph involving the cardinality of some vertex sets, we can define its corresponding weight parameter by giving some “weights” (that is, the entries of the positive eigenvector) to the vertices and replacing cardinalities by square norms. The key point is that such weights “regularize” the graph, and hence allow us to define a kind of regular partition, called “pseudo-regular,” intended for general graphs. Here we show how to use interlacing for proving results about some weight parameters and pseudo-regular partitions of a graph. For instance, generalizing a well-known result of Lovász, it is shown that the weight Shannon capacity Θ^* of a connected graph Γ, with n vertices and (adjacency matrix) eigenvalues λ₁ > λ₂ … λ_n, satisfies

where Θ is the (standard) Shannon capacity and v is the positive eigenvector normalized to have smallest entry 1. In the special case of regular graphs, the results obtained have some interesting corollaries, such as an upper bound for some of the multiplicities of the eigenvalues of a distance-regular graph. Finally, some results involving the Laplacian spectrum are derived.     

Compatibilité entre structures d''intervalles et relations d''orde

Compatibility between interval structures and partial orderings.

If H=(X,E) is a hypergraph, n the cardinality of X,I_n the ordered set {1..n} and < an order relation on X, we call F(X,<) the set of the one-to-one functions from X to I_n which are compatible with <. If AI_n we denote by (A) the length of the smallest interval of I_n which contains A.

We first deal with the following problem: Find ƒF(X,<) which minimise . The a_e, eR are positive coefficients.

This problem can be understood as a scheduling problem and is checked to be NP-complete. We learn how to recognize in polynomial time those hypergraphs H=(X,E) which induce an optimal value of z min equal to .

Next we work on a dual question which arises about interval graphs, when some partial orderings on the vertex set of these graphs intend to represent inclusion, overlapping or anteriority relations between closed intervals of the real line.     

Dynamic programming in problems of identifying distributed parameter systems

The problem of identifying the input of a system governed by a “semi-linear” evolution equation of parabolic type, based on the results of observations subject to undefined disturbances, is investigated. Estimates of the input, optimal in the sense of the so-called H_∞-criterion, are obtained. The information function of the system—the value function in an appropriate optimization problem—is evaluated. The relations between the information function and information sets are indicated. Optimality principles adequate to the proposed formulations of the problem are formulated and the corresponding dynamic programming equations are derived. Procedures for regularizing the problem, based on evolution equations of the input estimates, are proposed for the heat-conduction equation.     

Multi-step quasi-Newton methods for optimization

Quasi-Newton methods update, at each iteration, the existing Hessian approximation (or its inverse) by means of data deriving from the step just completed. We show how “multi-step” methods (employing, in addition, data from previous iterations) may be constructed by means of interpolating polynomials, leading to a generalization of the “secant” (or “quasi-Newton”) equation. The issue of positive-definiteness in the Hessian approximation is addressed and shown to depend on a generalized version of the condition which is required to hold in the original “single-step” methods. The results of extensive numerical experimentation indicate strongly that computational advantages can accrue from such an approach (by comparison with “single-step” methods), particularly as the dimension of the problem increases.     

On the converse lagrange theorem in magnetohydrodynamics

The problem of the converse Lagrange theorem /1, 2/ in magnetohydrodynami.es is investigated. The linear problem of the stability of the quiescent state of a viscous incompressible fluid with an infinite conductivity containing a magnetic field is considered. It is shown by the direct Lyapunov method that the system is unstable if the second variation of the potential energy takes negative values. “A priori· lower and upper estimates of the increase in the perturbations are obtained. The lower estimate ensures an exponential increase in the displacements of the fluid particles and the lines of force of the magnetic field from the equilibrium state. The upper estimate shows that the solutions do not increase more rapidly than exponentially. In both cases, the exponents are calculated using the equilibrium state parameters and the initial data for the perturbation fields.

This paper extends the well-known results in /3, 4/ to • magneto-hydrodynamics.     

Greedy approaches for a class of nonlinear Generalized Assignment Problems

The traditional Generalized Assignment Problem (GAP) seeks an assignment of customers to facilities that minimizes the sum of the assignment costs while respecting the capacity of each facility. We consider a nonlinear GAP where, in addition to the assignment costs, there is a nonlinear cost function associated with each facility whose argument is a linear function of the customers assigned to the facility. We propose a class of greedy algorithms for this problem that extends a family of greedy algorithms for the GAP. The effectiveness of these algorithms is based on our analysis of the continuous relaxation of our problem. We show that there exists an optimal solution to the continuous relaxation with a small number of fractional variables and provide a set of dual multipliers associated with this solution. This set of dual multipliers is then used in the greedy algorithm. We provide conditions under which our greedy algorithm is asymptotically optimal and feasible under a stochastic model of the parameters.     

Forcing closed unbounded subsets of ω2

It is shown that there is no satisfactory first-order characterization of those subsets of ω₂ that have closed unbounded subsets in ω₁,ω₂ and GCH preserving outer models. These “anticharacterization” results generalize to subsets of successors of uncountable regular cardinals. Similar results are proved for trees of height and cardinality κ⁺ and for partitions of [κ⁺]², when κ is an infinite cardinal.