Monte Carlo algorithm for trajectory optimization based on Markovian readings

This paper describes an efficient algorithm to find a smooth trajectory joining two points A and B with minimum length constrained to avoid fixed subsets. The basic assumption is that the locations of the obstacles are measured several times through a mechanism that corrects the sensors at each reading using the previous observation. The proposed algorithm is based on the penalized nonparametric method previously introduced that uses confidence ellipses as a fattening of the avoidance set. In this paper we obtain consistent estimates of the best trajectory using Monte Carlo construction of the confidence ellipse.     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.     

A smoothing sample average approximation method for stochastic optimization problems with CVaR risk measure

This paper is concerned with solving single CVaR and mixed CVaR minimization problems. A CHKS-type smoothing sample average approximation (SAA) method is proposed for solving these two problems, which retains the convexity and smoothness of the original problem and is easy to implement. For any fixed smoothing constant ε, this method produces a sequence whose cluster points are weak stationary points of the CVaR optimization problems with probability one. This framework of combining smoothing technique and SAA scheme can be extended to other smoothing functions as well. Practical numerical examples arising from logistics management are presented to show the usefulness of this method.     

On the numerical solution of stochastic quadratic integral equations via operational matrix method

In this paper, stochastic operational matrix of integration based on delta functions is applied to obtain the numerical solution of linear and nonlinear stochastic quadratic integral equations (SQIEs) that appear in modelling of many real problems. An important advantage of this method is that it dose not need any integration to compute the constant coefficients. Also, this method can be utilized to solve both linear and nonlinear problems. By using stochastic operational matrix of integration together collocation points, solving linear and nonlinear SQIEs converts to solve a nonlinear system of algebraic equations, which can be solved by using Newton's numerical method. Moreover, the error analysis is established by using some theorems. Also, it is proved that the rate of convergence of the suggested method is O(h²). Finally, this method is applied to solve some illustrative examples including linear and nonlinear SQIEs. Numerical experiments confirm the good accuracy and efficiency of the proposed method.     

Reformulation of a stochastic action principle for irregular dynamics

A stochastic action principle for random dynamics is revisited. Numerical diffusion experiments are carried out to show that the diffusion path probability depends exponentially on the Lagrangian action . This result is then used to derive the Shannon measure for path uncertainty. It is shown that the maximum entropy principle and the least action principle of classical mechanics can be unified into where the average is calculated over all possible paths of the stochastic motion between two configuration points a and b. It is argued that this action principle and the maximum entropy principle are a consequence of the mechanical equilibrium condition extended to the case of stochastic dynamics.     

路径跟踪方法求解无界非凸区域上的不动点问题

给出了求解一类无界非凸区域上不动点问题的路径跟踪方法.在适当的条件下,给出了不动点存在性的构造性证明,从而得到了路径跟踪方法的全局收敛性结果.研究结果为计算无界非凸区域上不动点问题提供了一种全局收敛性方法.     

Integration by parts formulas and dilatation vector fields on elliptic probability spaces

Summary. By coupling two arbitrary riemannian connections Γ and Γ˜ on a riemannian manifold M, we perform the stochastic calculus of ɛ-variation on the path space P(M) of the manifold M. The method uses direct calculations on Ito’s stochastic differential equations. In this context, we obtain intertwinning formulas with the Ito map for first order operators on the path space P(M) of M. By a judicious choice of the second connection Γ˜ in terms of the connection Γ, we can prolongate the intertwinning formulas to second order differential operators. Thus, we obtain expressions of heat operators on the path space P(M) of a riemannian manifold M endowed with an arbitrary connection. The integration by parts of the laplacians on P(M) leads us to the notion of dilatation vector field on the path space. Received: 18 April 1995 / In revised form: 18 March 1996     

Path planning for robots under stochastic uncertainty *

In order to reduce large online measurement and correction expenses, the a priori informations on the random variations of the model parameters of a robot and its working environment are taken into account already at the planning stage. Thus, instead of solving a deterministic path planning problem with a fixed nominal parameter vector, here, the optimal velocity profile along a given trajectory in work space is determined by using a stochastic optimization approach. Especially, the standard polygon of constrained motion-depending on the nominal parameter vector-is replaced by a more general set of admissible motion determined by chance constraints or more general risk constraints. Robust values (with respect to stochastic parameter variations) of the maximum, minimum velocity, acceleration, deceleration, resp., can be obtained then by solving a univariate stochastic optimization problem Considering the fields of extremal trajectories, the minimum-time path planning problem under stochastic uncertainty can be solved now by standard optimal deterministic path planning methods     

Deforming star-shaped polygons in the plane

Given a star-shaped polygon in the euclidean plane and a vertex v of the polygon, the author characterizes all those points w in the plane such that when the vertex v moves to w along a straight line path, while all other vertices of the polygon are fixed, the polygon remains star-shaped. An example is given to show that this characterization fails for the star-shaped polyhedral spheres in the 3-dimensional euclidean space.     

A simplicial homotopy algorithm for computing zero points on polytopes

ＡＳＩＭＰＬＩＣＩＡＬＨＯＭＯＴＯＰＹＡＬＧＯＲＩＴＨＭＦＯＲＣＯＭＰＵＴＩＮＧＺＥＲＯＰＯＩＮＴＳＯＮＰＯＬＹＴＯＰＥＳＣＨＥＮＫＡＩＺＨＯＵ（陈开周）;ＹＡＮＧＺＡＩＦＵ（杨再福）;ＬＩＡＮＧＺＨＥＮＧＬＩ（梁正礼）（ＤｅｐａｒｔｍｅｎｔｏｆＡｐ...     

Manifold-valued martingales, changes of probabilities, and smoothness of finely harmonic maps

This paper is concerned with regularity results for starting points of continuous manifold-valued martingales with fixed terminal value under a possibly singular change of probability. In particular, if the martingales live in a small neighbourhood of a point and if the stochastic logarithm M of the change of probability varies in some Hardy space H_r for sufficiently large r<2, then the starting point is differentiable at M=0. As an application, our results imply that continuous finely harmonic maps between manifolds are smooth, and the differentials have stochastic representations not involving derivatives. This gives a probabilistic alternative to the coupling technique used by Kendall (1994).     

Hybrid Proximal-Type and Hybrid Shrinking Projection Algorithms for Equilibrium Problems,Maximal Monotone Operators,and Relatively Nonexpansive Mappings

In this article, we introduce two hybrid proximal-type algorithms and two hybrid shrinking projection algorithms by using the hybrid proximal-type method and the hybrid shrinking projection method, respectively, for finding a common element of the set of solutions of an equilibrium problem, the set of fixed points of a relatively nonexpansive mapping, and the set of solutions to the equation 0 ∈ Tx for a maximal monotone operator T defined on a uniformly smooth and uniformly convex Banach space. The strong convergence of the sequences generated by the proposed algorithms is established. Our results improve and generalize several known results in the literature.     

A direct variable step block multistep method for solving general third-order ODEs

This paper discusses a direct three-point implicit block multistep method for direct solution of the general third-order initial value problems of ordinary differential equations using variable step size. The method is based on a pair of explicit and implicit of Adams type formulas which are implemented in PE(CE) ^t mode and in order to avoid calculating divided difference and integration coefficients all the coefficients are stored in the code. The method approximates the numerical solution at three equally spaced points simultaneously. The Gauss Seidel approach is used for the implementation of the proposed method. The local truncation error of the proposed scheme is studied. Numerical examples are given to illustrate the efficiency of the method.     

Parametric Estimation of a Boolean Segment Process with Stochastic Restoration Estimation

Abstract

We propose a stochastic restoration estimation (SRE) algorithm to estimate the parameters of the length distribution of a boolean segment process. A boolean segment process is a stochastic process obtained by considering the union of independent random segments attached to random points independently scattered on the plane. Each iteration of the SRE algorithm has two steps: first, censored segments are restored; second, based on these restored data, parameter estimations are updated. With a usually straightforward implementation, this algorithm is particularly interesting when censoring effects are difficult to take into account. We illustrate this method in two situations where the parameter of interest is either the mean of the segment length distribution or the variance of its logarithm. Its application to vine shoot length distribution estimation is presented.     

Calculation of minimal capacity vectors through k minimal paths under budget and time constraints

Reducing the transmission time is an important issue for a flow network to transmit a given amount of data from the source to the sink. The quickest path problem thus arises to find a single path with minimum transmission time. More specifically, the capacity of each arc is assumed to be deterministic. However, in many real-life networks such as computer networks and telecommunication networks, the capacity of each arc is stochastic due to failure, maintenance, etc. Hence, the minimum transmission time is not a fixed number. Such a network is named a stochastic-flow network. In order to reduce the transmission time, the network allows the data to be transmitted through k minimal paths simultaneously. Including the cost attribute, this paper evaluates the probability that d units of data can be transmitted under both time threshold T and budget B. Such a probability is called the system reliability. An efficient algorithm is proposed to generate all of lower boundary points for (d, T, B), the minimal capacity vectors satisfying the demand, time, and budget requirements. The system reliability can then be computed in terms of such points. Moreover, the optimal combination of k minimal paths with highest system reliability can be obtained.     

A sparse graph almost as good as the complete graph on points inK dimensions

A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and the weight of an edge between any two points is the distance between the points under someL _p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε ^−k log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε^−k n).     

Stochastic flows on the boundaries of SL(n,R)

Summary We study the asymptotic stability of the stochastic flows on a class of compact spaces induced by a diffusion process in SL(n, R) or GL(n, R). These compact spaces are called boundaries of SL(n, R), which include SO(n), the flag manifold, the sphereS ⁿ–1 and the Grassmannians. The one point motions of these flows are Brownian motions. For almost every, , we determine the set of stable points. This is a random open set whose complement has zero Lebesgue measure. The distance between any two points in the same component of this set tends to zero exponentially fast under the flow. The Lyapunov exponents at stable points are computed explicitly. We apply our results to a stochastic flow onS ⁿ–2 generated by a stochastic differential equation which exhibits some nice symmetry.Research supported in part by Hou Yin Dong Education Foundation of China On leave from Nankai University, Tianjin, China     

A Krasnosel’skii-type result for planar sets starshaped via orthogonally convex paths

A Krasnosel’skii-type theorem for compact sets that are starshaped via staircase paths may be extended to compact sets that are starshaped via orthogonally convex paths: Let S be a nonempty compact planar set having connected complement. If every two points of S are visible via orthogonally convex paths from a common point of S, then S is starshaped via orthogonally convex paths. Moreover, the associated kernel Ker S has the expected property that every two of its points are joined in Ker S by an orthogonally convex path. If S is an arbitrary nonempty planar set that is starshaped via orthogonally convex paths, then for each component C of Ker S, every two of points of C are joined in C by an orthogonally convex path. Communicated by Imre Bárány     

Weak Convergence of an Iterative Method for Pseudomonotone Variational Inequalities and Fixed-Point Problems

We consider an iterative scheme for finding a common element of the set of solutions of a pseudomonotone, Lipschitz-continuous variational inequality problem and the set of common fixed points of N nonexpansive mappings. The proposed iterative method combines two well-known schemes: extragradient and approximate proximal methods. We derive a necessary and sufficient condition for weak convergence of the sequences generated by the proposed scheme.