Dynamic motion planning in low obstacle density environments

A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and realistic low obstacle density (L.O.D.) assumption results in linear complexity in the number of obstacles of the free space (Van der Stappen et al., 1997). In this paper we address the dynamic version of the motion planning problem in which a robot moves among polygonal obstacles which move along polylines. The obstacles are assumed to move along constant complexity polylines, and to respect the low density property at any given time. We will show that in this situation a cell decomposition of the free space of size O(n²(n) log² n) can be computed in O(n²(n) log² n) time. The dynamic motion planning problem is then solved in O(n²(n) log³ n) time. We also show that these results are close to optimal.     

Transitions to chaos in squeeze-film dampers

This work reports on a numerical study undertaken to investigate the imbalance response of a rigid rotor supported by squeeze-film dampers. Two types of damper configurations were considered, namely, dampers without centering springs, and eccentrically operated dampers with centering springs. For a rotor fitted with squeeze-film dampers without centering springs, the study revealed the existence of three regimes of chaotic motion. The route to chaos in the first regime was attributed to a sequence of period-doubling bifurcations of the period-1 (synchronous) rotor response. A period-3 (one-third subharmonic) rotor whirl orbit, which was born from a saddle-node bifurcation, was found to co-exist with the chaotic attractor. The period-3 orbit was also observed to undergo a sequence of period-doubling bifurcations resulting in chaotic vibrations of the rotor. The route to chaos in the third regime of chaotic rotor response, which occurred immediately after the disappearance of the period-3 orbit due to a saddle-node bifurcation, was attributed to a possible boundary crisis. The transitions to chaotic vibrations in the rotor supported by eccentric squeeze-film dampers with centering springs were via the period-doubling cascade and type 3 intermittency routes. The type 3 intermittency transition to chaos was due to an inverse period-doubling bifurcation of the period-2 (one-half subharmonic) rotor response. The unbalance response of the squeeze-film-damper supported rotor presented in this work leads to unique non-synchronous and chaotic vibration signatures. The latter provide some useful insights into the design and development of fault diagnostic tools for rotating machinery that operate in highly nonlinear regimes.     

Controllability and observability in the problem of stabilizing steady motions of non-holonomic mechanical systems with cyclic coordinatest

The approach to the solution of stabilization problems for steady motions of holonomic mechanical systems [1, 2] based on linear control theory, combined with the theory of critical cases of stability theory, is used to solve the analogous problems for non-holonomic systems. It is assumed that the control forces may affect both cyclic and positional coordinates, where the number r of independent control inputs may be considerably less than the number n of degrees of freedom of the system, unlike in many other studies (see, e.g., [3–5]), in which as a rule r = n. Several effective new criteria of controllability and observability are formulated, based on reducing the problem to a problem of less dimension. Stability analysis is carried out for the trivial solution of the complete non-linear system, closed by a selected control. This analysis is a necessary step in solving the stabilization problem for steady motion of a non-holonomic system (unlike holonomic systems), since in most cases such a system is not completely controllable.     

Illumination in the presence of opaque line segments in the plane

What is the minimal number of light sources which is always sufficient to illuminate the plane in the presence of n disjoint opaque line segments? For n5, O'Rourke proved that 2n/3 light sources are always sufficient and sometimes necessary, if light sources can be placed on the line segments and thus they can illuminate both sides of a segment.

We prove that 2(n+1)/3 light sources are always sufficient and sometimes necessary, if light sources cannot be placed on the line segments. An O(nlogn) time algorithm is presented which allocates at most 2(n+1)/3 light sources collectively illuminating the plane.     

Area-efficient algorithms for straight-line tree drawings

We investigate several straight-line drawing problems for bounded-degree trees in the integer grid without edge crossings under various types of drawings: (1) upward drawings whose edges are drawn as vertically monotone chains, a sequence of line segments, from a parent to its children, (2) order-preserving drawings which preserve the left-to-right order of the children of each vertex, and (3) orthogonal straight-line drawings in which each edge is represented as a single vertical or horizontal segment.

Main contribution of this paper is a unified framework to reduce the upper bound on area for the straight-line drawing problems from O(nlogn) (Crescenzi et al., 1992) to O(nloglogn). This is the first solution of an open problem stated by Garg et al. (1993). We also show that any binary tree admits a small area drawing satisfying any given aspect ratio in the orthogonal straight-line drawing type.

Our results are briefly summarized as follows. Let T be a bounded-degree tree with n vertices. Firstly, we show that T admits an upward straight-line drawing with area O(nloglogn). If T is binary, we can obtain an O(nloglogn)-area upward orthogonal drawing in which each edge is drawn as a chain of at most two orthogonal segments and which has O(n/logn) bends in total. Secondly, we present O(nloglogn)-area (respectively, -volume) orthogonal straight-line drawing algorithms for binary trees with arbitrary aspect ratios in 2-dimension (respectively, 3-dimension). Finally, we present some experimental results which shows the area requirements, in practice, for (order-preserving) upward drawing are much smaller than theoretical bounds obtained through analysis.     

Reporting curve segment intersections using restricted predicates

We investigate how to report all k intersecting pairs among a collection of n x-monotone curve segments in the plane, using only predicates of the following forms: is an endpoint to the left of another? is an endpoint above a segment? do two segments intersect? By studying the intersection problem in an abstract setting that assumes the availability of certain “detection oracles”, we obtain a near-optimal randomized algorithm that runs in expected time. In the bichromatic case (where segments are colored red or blue with no red/red or blue/blue intersections), we find a better algorithm that runs in O((n+k)log_2+k/nn) worst-case time, by modifying a known segment-tree method. Two questions of Boissonnat and Snoeyink are thus answered to within logarithmic factors.     

双自由度非定点斜碰撞振动系统的动力学分析

对两个单摆组成的双自由度、非定点、斜碰撞振动系统的动力学行为进行了详细研究．揭示了在双自由度、非定点、斜碰撞过程中恢复系数、摩擦系数、系统参数和碰撞前后系统状态之间的关系．基于Poincaré映射方法和非定点斜碰撞关系推导出该系统单碰周期n次谐运动存在性判据．根据Floquet理论分析了该系统次谐运动周期解的稳定性问题,给出了Floquet特征乘子的计算公式．通过数值仿真证实了该方法的有效性,同时分析了非定点、斜碰撞系统碰撞点位置的概率分布情况．     

On the stability of space-periodic convective flows in a vertical layer with sinuous boundaries : PMM vol. 43, no. 6, 1979, pp. 998–1007

The problem of convection in a vertical layer with harmonically distorted boundaries is examined by perturbation theory methods for a small amplitude of sinuosity. The solutions obtained are applicable both in the stability region as well as in the supercritical region of the plane-parallel flow. The stability of the solutions found is investigated with respect to a certain class of space-bounded perturbations that are not necessarily space-periodic. The method of amplitude functions [1], generalized to the case of curved boundaries, is used. The Grashof critical number is found as a function of the period of sinuosity and the form of the neutral curve for the space-periodic motions and their stability region are obtained. It is established that if the deformation period of the boundaries is close to the wavelength of the critical perturbation for the plane-parallel flow or is twice as great, then as the Grashof number grows stability loss does not occur and the motion's amplitude changes continuously (cf. [2 — 4]). A comparison is made with the results of the numerical calculation in [5], An attempt was made in [6] to construct a stationary periodic motion in a layer with weakly-deformed boundaries, in the form of series in powers of a small sinuosity amplitude. However, the solution obtained diverges in a neighborhood of the neutral curve of the plane-parallel flow and approximates unstable motion in the supercritical region of the unperturbed problem. Flows under a finite sinuosity amplitude are calculated by the net method in [5] wherein the stability of the flows was investigated as well, but only with respect to perturbations with wave numbers that are multiples of 2π/l, where l is the length of the calculated region.     

Stick motions and grazing flows in an inclined impact oscillator

In this paper, the dynamics of an inclined impact oscillator under periodic excitation are investigated using the flow switchability theory of the discontinuous dynamical systems. Different domains and boundaries for such system are defined according to the impact discontinuity. Based on above domains and boundaries, the analytical conditions of the stick motions and grazing motions for the inclined impact oscillator are obtained mathematically, from which it can be seen that such oscillator has more complicated and rich dynamical behaviors. The numerical simulations are given to illustrate the analytical results of complex motions, and several period-1 motions period-2 motion and chaotic motion of the ball in the inclined impact oscillator are also presented. There are more theories about such impact pair to be discussed in future.     

An elementary algorithm for reporting intersections of red/blue curve segments

Let E_r and E_b be two sets of x-monotone and non-intersecting curve segments, E=E_rE_b and |E|=n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E. Our algorithm uses only three simple predicates that allow to decide if two segments intersect, if a point is left or right to another point, and if a point is above, below or on a segment. These three predicates seem to be the simplest predicates that lead to subquadratic algorithms. Our algorithm is almost optimal in this restricted model of computation. Its time complexity is O(nlogn+kloglogn) and it requires O(n) space.     

Flat portions on the boundary of the numerical ranges of certain Toeplitz matrices

We give criterions for a flat portion to exist on the boundary of the numerical range of a matrix. A special type of Teoplitz matrices with flat portions on the boundary of its numerical range are constructed. We show that there exist 2 × 2 nilpotent matrices A₁,A₂, an n  × n nilpotent Toeplitz matrix N_n, and an n  × n cyclic permutation matrix S_n(s) such that the numbers of flat portions on the boundaries of W(A₁⊕N_n) and W(A₂⊕S_n(s)) are, respectively, 2(n - 2) and 2n.     

Periodic motions and bifurcations of a vibro-impact system

Based on the analysis of a two-degree-of-freedom plastic impact oscillator, we introduce a three-dimensional map with dynamical variables defined at the impact instants. The non-linear dynamics of the vibro-impact system is analyzed by using the Poincaré map, in which piecewise property and singularity are found to exist. The piecewise property is caused by the transitions of free flight and sticking motions of two masses immediately after the impact, and the singularity of map is generated via the grazing contact of two masses and corresponding instability of periodic motions. These properties of the map have been shown to exhibit particular types of sliding and grazing bifurcations of periodic-impact motions under parameter variation. Simulations of the free flight and sticking solutions are carried out, and regions of existence and stability of different impact motions are therefore presented in (δ, ω) plane of dimensionless clearance δ and frequency ω. The influence of non-standard bifurcations on dynamics of the vibro-impact system is elucidated accordingly.     

On fat partitioning, fat covering and the union size of polygons

The complexity of the contour of the union of simple polygons with n vertices in total can be O(n²) in general. A notion of fatness for simple polygons is introduced that extends most of the existing fatness definitions. It is proved that a set of fat polygons with n vertices in total has union complexity O(n log log n), which is a generalization of a similar result for fat triangles (Matou ek et al., 1994). Applications to several basic problems in computational geometry are given, such as efficient hidden surface removal, motion planning, injection molding, and more. The result is based on a new method to partition a fat simple polygon P with n vertices into O(n) fat convex quadrilaterals, and a method to cover (but not partition) a fat convex quadrilateral with O(l) fat triangles. The maximum overlap of the triangles at any point is two, which is optimal for any exact cover of a fat simple polygon by a linear number of fat triangles.     

Adaptive control of uncertain coupled mechanical systems with application to base-isolated structures

A problem of feedback stabilization is addressed for a class of uncertain nonlinear mechanical systems with n degrees of freedom and n_c < n control inputs. Each system of the class has the structure of two coupled subsystems with n_c and n_r degrees of freedom, respectively, a prototype being an uncertain base isolated building structure with n degrees of freedom actively controlled via actuators applying forces to specific degrees of freedom of the base movement, n_c < n in number. A nonlinear adaptive feedback strategy is described, which, under appropriate assumptions on the system uncertainties, guarantees a form of practical stability of the zero state. Numerical simulations are also presented to illustrate the application of the control strategy to a base isolated building.     

On a straight-line embedding problem of graphs

Let G be a planar graph with n vertices, v be a specified vertex of G, and P be a set of n points in the Euclidian plane in general position. A straight-line embedding of G onto P is an embedding of G onto whose images of vertices are distinct points in P and whose images of edges are (straight) line segments. In this paper, we classify into five classes those pairs of G and v such that for any P and any p P, G has a straight-line embedding onto P which maps v to p. We then show that all graphs in three of the classes indeed have such an embedding. This result gives a solution to a generalized version of the rooted-tree embedding problem raised by M. Perles.     

Planar segment visibility graphs

Given a set of n disjoint line segments in the plane, the segment visibility graph is the graph whose 2n vertices correspond to the endpoints of the line segments and whose edges connect every pair of vertices whose corresponding endpoints can see each other. In this paper we characterize and provide a polynomial time recognition algorithm for planar segment visibility graphs. Actually, we characterize segment visibility graphs that do not contain the complete graph K₅ as a minor, and show that this class is the same as the class of planar segment visibility graphs. We use and prove the fact that every segment visibility graph contains K₄ as a subgraph. In fact, we prove a stronger result: every set of n line segments determines at least n−3 empty convex quadrilaterals.     

On the instability of a periodic system in the case of internal resonance

The stability of periodic motion is studied in the critical case of n pairs of purely imaginary characteristic indices. It is shown that in the case of resonance, when the ratio of the modulus of one of the characteristic indices to the frequency of the unperturbed motion is an integer, instability usually occurs. The results obtained are used to study the free oscillations of an autonomous quasilinear system when the Andronov-Witt criterion /1/ cannot be used. The instability of free oscillations of the Froude pendulum at the bifurcation point is proved.     

On the problem op n-stationary centers

Among the various problems of celestial mechanics related to the n-body problem, a certain amount of interest attaches to the specific situation wherein a passive gravitational point mass M moves under the assumption that the relative disposition of the other active gravitational masses experiences no large changes.

If the attracting masses are regarded as points and if changes in the relative disposition of the attracting bodies are neglected, one arrives at the problem of the motion of the point M in a field produced by n-stationary attracting centers (the point M here represents the (n+l)-th body).

In addition to the problem of central motion (n = 1), soluble dynamics problems of this category include Euler's case [1] of two (n= 2) stationary Newtonian attracting centers.

This problem, which for a long time was of solely theoretical Interest as an example of an integrable Liouville system [2], has recently been attracting attention in connection with the mechanics of artificial satellites, particularly after it was shown that the potential of an oblate spheroid can be approximated by the potential of two specifically chosen stationary Newtonian attracting centers [3 and 4].

The solution of the problem for n-attracting centers for n ≥ 3 is unknown, except for a single special case of three centers pointed out by Lagrange and considered In greater detail by J.A. Serre [5].

We shall concern ourselves here with problems on the existence of periodic trajectories in the case of n-attracting centers. An arbitrary and not necessarily Newtonian gravitational law will be assumed.

Our analysis is based on the theory of quasiindices of singular force field points as set forth in [60].     

On convex segments in a triangulation

A segment (=1-cell) of a planar triangulation σ is convex if it is common to two triangles (2-cells) whose union is a convex set. We determine the maximal number of convex segments of a triangulation over all triangulations σ having n boundary vertices and m inner vertices (n3,m0).     

Complex economic dynamics: Chaotic saddle, crisis and intermittency

Complex economic dynamics is studied by a forced oscillator model of business cycles. The technique of numerical modeling is applied to characterize the fundamental properties of complex economic systems which exhibit multiscale and multistability behaviors, as well as coexistence of order and chaos. In particular, we focus on the dynamics and structure of unstable periodic orbits and chaotic saddles within a periodic window of the bifurcation diagram, at the onset of a saddle-node bifurcation and of an attractor merging crisis, and in the chaotic regions associated with type-I intermittency and crisis-induced intermittency, in non-linear economic cycles. Inside a periodic window, chaotic saddles are responsible for the transient motion preceding convergence to a periodic or a chaotic attractor. The links between chaotic saddles, crisis and intermittency in complex economic dynamics are discussed. We show that a chaotic attractor is composed of chaotic saddles and unstable periodic orbits located in the gap regions of chaotic saddles. Non-linear modeling of economic chaotic saddle, crisis and intermittency can improve our understanding of the dynamics of financial intermittency observed in stock market and foreign exchange market. Characterization of the complex dynamics of economic systems is a powerful tool for pattern recognition and forecasting of business and financial cycles, as well as for optimization of management strategy and decision technology.