Convex hull representations of models for computing collisions between multiple bodies

In this paper, we consider a collision detection problem that frequently arises in the field of robotics. Given a set of bodies with their initial positions and trajectories, we wish to identify the first collision that occurs between any two bodies, or to determine that none exists. For the case of bodies having linear trajectories, we construct a convex hull representation of the integer programming model of S.Z. Selim and H.A. Almohamad [European Journal of Operational Research 119 (1) (1999) 121–129], and compare the relative effectiveness in solving this problem via the resultant linear program. We also extend this analysis to model a situation in which bodies move along piecewise linear trajectories, possibly rotating at the end of each linear segment. For this case, we again compare an integer programming approach with its linear programming convex hull representation, and exhibit the effectiveness of solving a sequence of mathematical programs for each time segment over a global programming scheme which considers all segments at once. We provide computational results to illustrate the effect of various numbers of bodies present in the collision scenarios, as well as the times at which the first collision occurs.     

Linear-quadratic control and quadratic differential forms for multidimensional behaviors

This paper deals with systems described by constant coefficient linear partial differential equations (nD-systems) from a behavioral point of view. In this context we treat the linear quadratic control problem where the performance functional is the integral of a quadratic differential form. We look for characterizations of the set of stationary trajectories and of the set of local minimal trajectories with respect to compact support variations, turning out that they are equal if the system is dissipative. Finally we provide conditions for regular implementability of this set of trajectories and give an explicit representation of an optimal controller.     

Fast algorithms for collision and proximity problems involving moving geometric objects

Consider a set of geometric objects, such as points, line segments, or axes-parallel hyperrectangles in ^d, that move with constant but possibly different velocities along linear trajectories. Efficient algorithms are presented for several problems defined on such objects, such as determining whether any two objects ever collide and computing the minimum interpoint separation or minimum diameter that ever occurs. In particular, two open problems from the literature are solved: deciding in o(n²) time if there is a collision in a set of n moving points in ², where the points move at constant but possibly different velocities, and the analogous problem for detecting a red-blue collision between sets of red and blue moving points. The strategy used involves reducing the given problem on moving objects to a different problem on a set of static objects, and then solving the latter problem using techniques based on sweeping, orthogonal range searching, simplex composition, and parametric search.     

A genetic-fuzzy approach for mobile robot navigation among moving obstacles

In this paper, a genetic-fuzzy approach is developed for solving the motion planning problem of a mobile robot in the presence of moving obstacles. The application of combined soft computing techniques — neural network, fuzzy logic, genetic algorithms, tabu search and others — is becoming increasingly popular among various researchers due to their ability to handle imprecision and uncertainties that are often present in many real-world problems. In this study, genetic algorithms are used for tuning the scaling factors of the state variables (keeping the relative spacing of the membership distributions constant) and rule sets of a fuzzy logic controller (FLC) which a robot uses to navigate among moving obstacles. The use of an FLC makes the approach easier to be used in practice. Although there exist many studies involving classical methods and using FLCs they are either computationally extensive or they do not attempt to find optimal controllers. The proposed genetic-fuzzy approach optimizes the travel time of a robot off-line by simultaneously finding an optimal fuzzy rule base and optimal scaling factors of the state variables. A mobile robot cant then use this optimal FLC on-line to navigate in presence of moving obstacles. The results of this study on a number of problem scenarios show that the proposed genetic-fuzzy approach can produce efficient knowledge base of an FLC for controlling the motion of a robot among moving obstacles.     

Shilnikov lemma for a nondegenerate critical manifold of a Hamiltonian system

Let M be a normally hyperbolic symplectic critical manifold of a Hamiltonian system. Suppose M consists of equilibria with real eigenvalues. We prove an analog of the Shilnikov lemma (strong version of the λ-lemma) describing the behavior of trajectories near M. Using this result, trajectories shadowing chains of homoclinic orbits to M are represented as extremals of a discrete variational problem. Then the existence of shadowing periodic orbits is proved. This paper is motivated by applications to the Poincaré’s second species solutions of the 3 body problem with 2 masses small of order µ. As µ → 0, double collisions of small bodies correspond to a symplectic critical manifold M of the regularized Hamiltonian system. Thus our results imply the existence of Poincaré’s second species (nearly collision) periodic solutions for the unrestricted 3 body problem.     

Direct central impact of different elastic bodies of rotation

A direct central collision of two bodies of revolution is studied. A nonstationary mixed boundary-value problem with an unknown moving boundary is formulated. Its solution is represented by a series in term of Bessel functions. An infinite system of Volterra equations of the second kind for the unknown expansion coefficients is derived by satisfying the boundary conditions. The basic characteristics of the collision process are determined depending on the physic-mechanical properties of the bodies. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Optimal control with connected initial and terminal conditions

An optimal control problem with linear dynamics is considered on a fixed time interval. The ends of the interval correspond to terminal spaces, and a finite-dimensional optimization problem is formulated on the Cartesian product of these spaces. Two components of the solution of this problem define the initial and terminal conditions for the controlled dynamics. The dynamics in the optimal control problem is treated as an equality constraint. The controls are assumed to be bounded in the norm of L₂. A saddle-point method is proposed to solve the problem. The method is based on finding saddle points of the Lagrangian. The weak convergence of the method in controls and its strong convergence in state trajectories, dual trajectories, and terminal variables are proved.     

LP-Based Algorithms for Detecting the Collision of Moving Objects

In this paper, we consider the problem of detecting the collision of moving objects in three-dimensional space. We develop two algorithms that use linear programming techniques to detect exact possible collisions between the objects in both time and space when the objects are represented as polyhedral sets in ?² or ?³. The algorithms can handle the case of a rigid body moving on a general path with simultaneous translation and rotation. Computational experience on the developed algorithms is also presented.     

The duality theorem for min-max functions

The set of min-max functions F : ℝⁿ → ℝⁿ is the least set containing coordinate substitutions and translations and closed under pointwise max, min, and function composition. The Duality Conjecture asserts that the trajectories of a min-max function, considered as a dynamical system, have a linear growth rate (cycle time) and shows how this can be calculated through a representation of F as an infimum of max-plus linear functions. We prove the conjecture using an analogue of Howard's policy improvement scheme, carried out in a lattice ordered group of germs of affine functions at infinity. The methods yield an efficient algorithm for computing cycle times.     

Falsification of hybrid systems with symbolic reachability analysis and trajectory splicing

The falsification of a hybrid system aims at finding trajectories that violate a given safety property. This is a challenging problem, and the practical applicability of current falsification algorithms still suffers from their high time complexity. In contrast to falsification, verification algorithms aim at providing guarantees that no such trajectories exist. Recent symbolic reachability techniques are capable of efficiently computing linear constraints that enclose all trajectories of the system with reasonable precision. In this paper, we leverage the power of symbolic reachability algorithms to improve the scalability of falsification techniques. Recent approaches to falsification reduce the problem to a nonlinear optimization problem. We propose to reduce the search space of the optimization problem by adding linear state constraints obtained with a reachability algorithm. An empirical study of how varying abstractions during symbolic reachability analysis affect the performance of solving a falsification problem is presented. In addition, for solving a falsification problem, we propose an alternating minimization algorithm that solves a linear programming problem and a non-linear programming problem in alternation finitely many times. We showcase the efficacy of our algorithms on a number of standard hybrid systems benchmarks demonstrating the performance increase and number of falsifyable instances.     

An approach for solving of a moving boundary problem

In this paper we shall study moving boundary problems, and we introduce an approach for solving a wide range of them by using calculus of variations and optimization. First, we transform the problem equivalently into an optimal control problem by defining an objective function and artificial control functions. By using measure theory, the new problem is modified into one consisting of the minimization of a linear functional over a set of Radon measures; then we obtain an optimal measure which is then approximated by a finite combination of atomic measures and the problem converted to an infinite-dimensional linear programming. We approximate the infinite linear programming to a finite-dimensional linear programming. Then by using the solution of the latter problem we obtain an approximate solution for moving boundary function on specific time. Furthermore, we show the path of moving boundary from initial state to final state.     

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.     

Quantization via mirror symmetry

When combined with mirror symmetry, the A-model approach to quantization leads to a fairly simple and tractable problem. The most interesting part of the problem then becomes finding the mirror of the coisotropic brane. We illustrate how it can be addressed in a number of interesting examples related to representation theory and gauge theory, in which mirror geometry is naturally associated with the Langlands dual group. Hyperholomorphic sheaves and (B, B, B) branes play an important role in the B-model approach to quantization.     

Probability chains: A general linearization technique for modeling reliability in facility location and related problems

In this paper, we propose an efficient technique for linearizing facility location problems with site-dependent failure probabilities, focusing on the unreliable p-median problem. Our approach is based on the use of a specialized flow network, which we refer to as a probability chain, to evaluate compound probability terms. The resulting linear model is compact in size. The method can be employed in a straightforward way to linearize similarly structured problems, such as the maximum expected covering problem. We further discuss how probability chains can be extended to problems with co-location and other, more general problem classes. Additional lower bounds as well as valid inequalities for use within a branch and cut algorithm are introduced to significantly speed up overall solution time. Computational results are presented for several test problems showing the efficiency of our linear model in comparison to existing problem formulations.     

Canonical dual approach to solving the maximum cut problem

This paper presents a canonical dual approach for finding either an optimal or approximate solution to the maximum cut problem (MAX CUT). We show that, by introducing a linear perturbation term to the objective function, the maximum cut problem is perturbed to have a dual problem which is a concave maximization problem over a convex feasible domain under certain conditions. Consequently, some global optimality conditions are derived for finding an optimal or approximate solution. A gradient decent algorithm is proposed for this purpose and computational examples are provided to illustrate the proposed approach.     

The bringing of two rigid bodies into collision-free contact by bounded controls in a finite time

The control problem of moving a rigid body onto the surface of another rigid body in such a way that no collision occurs in investigated. For this, phase constraints must be satisfied in the sense that the surface of one body must not overlap the other, and here an important condition must be met: contact of the bodies is ensured by bounded controls and in a finite time. No impact of the rigid bodies occurs at the instant of contact because a strict rule is observed: if any point of one body lies on the surface of the other, then the velocity of the point is directed along this surface (or away from it). To observe this rule, special controls are used. These controls realize assigned accurate values of the coordinates and velocities of the mechanical system in a finite time.     

Time-optimal solution of a linear evolution equation in Banach spaces

The problem is that of finding trajectories of a linear evolution equation connecting two prescribed sets of states, initial and terminal, in the shortest possible time. Necessary conditions for the existence of solutions, i.e., time-optimum trajectories, are given in the form of a maximum principle.     

An implicit representation of chordal comparability graphs in linear time

Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posets of dimension four. Among other uses, this gives an implicit representation of a chordal comparability graph using O(n) integers so that, given two vertices, it can be determined in O(1) time whether they are adjacent, no matter how dense the graph is. We give a linear time algorithm for finding the four linear orders, improving on their bound of O(n²).     

A Midpoint-Radius approach to regression with interval data

In this paper, a revisited interval approach for linear regression is proposed. In this context, according to the Midpoint-Radius (MR) representation, the uncertainty attached to the set-valued model can be decoupled from its trend. The estimated interval model is built from interval input-output data with the objective of covering all available data. The constrained optimization problem is addressed using a linear programming approach in which a new criterion is proposed for representing the global uncertainty of the interval model. The potential of the proposed method is illustrated by simulation examples.