Structure Algorithms for Partially Ordered Isotonic Regression

Abstract

An algorithm for isotonic regression is called a structure algorithm if it searches for a “solution partition”—that is, a class of sets on each of which the isotonic regression is a constant. We discuss structure algorithms for partially ordered isotonic regression. In this article we provide a new class of structure algorithms called the isotonic block class (IBC) type algorithms. One of these is called the isotonic block class with recursion method (IBCR) algorithm, which works for partially ordered isotonic regression. It is a generalization of the pooled adjacent violators algorithm and is simpler than the min-max algorithm. We also give a polynomial time algorithm—the isotonic block class with stratification (IBCS) algorithm for matrix-ordered isotonic regression. We demonstrate the efficiency of our IBCR algorithm by using simulation to estimate the relative frequencies of the numbers of level sets of isotonic regressions on certain two-dimensional grids with the matrix order.     

Convergence of fluctuation-splitting schemes for two dimensional scalar conservation laws with a kinetic solver

Summary. The “fluctuation-splitting schemes” (FSS in short) have been introduced by Roe and Sildikover to solve advection equations on rectangular grids and then extended to triangular grids by Roe, Deconinck, Struij... For a two dimensional nonlinear scalar conservation law, we consider the case of a triangular grid and of a kinetic approach to reduce the discretization of the nonlinear equation to a linear equation and apply a particular FSS called N-scheme. We show that the resulting scheme converges strongly in in a finite volume sense. Received February 25, 1997 / Revised version received November 8, 1999 / Published online August 24, 2000     

A Markov time related to a robot-safety device system

We consider a robot-safety device system attended by two different repairmen. The twin-system is characterized by the natural feature of cold standby and an admissible risky state. Apart from tangible results obtained in the previous Literature, we introduce a Markov time called the recovery time of the system. In order to obtain the corresponding distribution, we employ a stochastic process endowed with time dependent state probabilities related to the point availability of a renewable robot without safety device. Finally, as an example, we consider the case of Weibull repair (for the robot) and deterministic repair (for the safety device). We provide several computer-plotted graphs obtained by advanced numerical methods. Received: February 2004 / Revised version: October 2004MSC classification: 60K10     

Competitive on-line coverage of grid environments by a mobile robot

We describe in this paper two on-line algorithms for covering planar areas by a square-shaped tool attached to a mobile robot. Let D be the tool size. The algorithms, called Spanning Tree Covering (STC) algorithms, incrementally subdivide the planar area into a grid of D-size cells, while following a spanning tree of a grid graph whose nodes are 2D-size cells. The two STC algorithms cover general planar grids. The first, Spiral-STC, employs uniform weights on the grid-graph edges and generates spiral-like covering patterns. The second, Scan-STC, assigns lower weights to edges aligned with a particular direction and generates scan-like covering patterns along this direction. Both algorithms cover any planar grid using a path whose length is at most (n+m)D, where n is the total number of D-size cells and mn is the number of boundary cells, defined as cells that share at least one point with the grid boundary. We also demonstrate that any on-line coverage algorithm generates a covering path whose length is at least (2−)l_opt in worst case, where l_opt is the length of the optimal off-line covering path. Since (n+m)D2l_opt, the bound is tight and the STC algorithms are worst-case optimal. Moreover, in practical environments mn, and the STC algorithms generate close-to-optimal covering paths in such environments.     

Frame Based Methods for Unconstrained Optimization

This paper describes a wide class of direct search methods for unconstrained optimization, which make use of fragments of grids called frames. Convergence is shown under mild conditions which allow successive frames to be rotated, translated, and scaled relative to one another.     

The Nitsche mortar method for matching grids in a mixed finite element method

It is well-known that nonmatching grids are often used in finite element methods. Usually, grids are being matched along lines or surfaces that divide a domain into subdomains. Such lines or surfaces are called interfaces. The interface matching means the satisfaction of some continuity conditions when crossing the interface. The direct matching procedures fall into three groups: Methods that use Lagrange multipliers, mortar methods based on the Nitsche technique, and penalty methods.     

Pure 2D picture grammars and languages

A new syntactic model, called pure two-dimensional (2D) context-free grammar (P2DCFG), is introduced based on the notion of pure context-free string grammar. The rectangular picture generative power of this 2D grammar model is investigated. Certain closure properties are obtained. An analogue of this 2D grammar model called pure 2D hexagonal context-free grammar (P2DHCFG) is also considered to generate hexagonal picture arrays on triangular grids.     

Locally oriented potential field for controlling multi-robots

In this paper, we present an extension of the boundary value problem path planner (BVP PP) to control multiple robots in a robot soccer scenario. This extension is called Locally Oriented Potential Field (LOPF) and computes a potential field from the numerical solution of a BVP using local relaxations in different patches of the solution space. This permits that a single solution of the BVP endows distinct robots with different behaviors in a team. We present the steps to implement LOPF as well as several results obtained in simulation.     

Computing Discrepancies of Smolyak Quadrature Rules

In recent years, Smolyak quadrature rules (also called quadratures on hyperbolic cross points or sparse grids) have gained interest as possible competition to number theoretic quadratures for high dimensional problems. A standard way of comparing the quality of multivariate quadrature formulas consists in computing theirL₂-discrepancy. Especially for larger dimensions, such computations are a highly complex task. In this paper we develop a fast recursive algorithm for computing theL₂-discrepancy (and related quality measures) of general Smolyak quadratures. We carry out numerical comparisons between the discrepancies of certain Smolyak rules and Hammersley and Monte Carlo sequences.     

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.     

A random forest application to contact‐state classification for robot programming by human demonstration

This paper addresses the non‐parametric estimation of the stochastic process related to the classification problem that arises in robot programming by demonstration of compliant motion tasks. Robot programming by demonstration is a robot programming paradigm in which a human operator demonstrates the task to be performed by the robot. In such demonstration, several observable variables, such as velocities and forces can be modeled, non‐parametrically, in order to classify the current state of a contact between an object manipulated by the robot and the environment in which it operates. Essential actions in compliant motion tasks are the contacts that take place, and therefore, it is important to understand the sequence of contact states made during a demonstration, called contact classification. We propose a contact classification algorithm based on the random forest algorithm. The main advantage of this approach is that it does not depend on the geometric model of the objects involved in the demonstration. Moreover, it does not rely on the kinestatic model of the contact interactions. The comparison with state‐of‐the‐art contact classifiers shows that random forest classifier is more accurate. Copyright © 2015 John Wiley & Sons, Ltd.     

Dynamic region visit routing problem for vehicles with minimum turning radius

In this paper we address the problem of planning optimized routes among dynamically selected target regions for vehicles with a turning radius motion constraint, hereinafter called dynamic Dubins traveling salesman problem with neighborhoods (DDTSPN). Initially, we present a heuristic to solve a simpler version of this problem, called off-line step, where only previously given targets are concerned. We further extend this approach for the more complex case of dynamic scenarios, called on-line step, addressing the inclusion of new targets during the execution of the initial route, whilst minimizing the impact on the total traveled distance. Formal analyzes of our techniques are provided, presenting upper bounds for the total length of the final tour. Results with statistical investigation over a large number of trials in a simulated environment are also provided. Finally, to demonstrate the applicability of our technique in solving the DDTSPN at real-world scenarios, we also report on results of an experiment performed with a real car-like robot.     

Model Based Control of a Parallel Robot – A Comparison of Control Algorithms

In this contribution the control behavior of a special construction of a parallel robot, called multi-axes test facility, is investigated. After a brief discussion of the different tasks of the robot the construction of the robot is briefly presented. To solve the tasks, different control algorithms are derived based on model equations of different complexity of the robot. Depending on the task to be performed by the robot, the controllers compensate the kinematic and/or kinetic coupling of the degrees of freedom of the robot, stabilize the system and achieve the desired spatial motion of each degree of freedom as well as sufficient robustness with respect to parameter uncertainties and load variations. A few results obtained in computer simulations and laboratory experiments are presented and judged with respect to the quality of control, the closeness to reality of the computer simulations, and the amount of costs and work needed to realize the different solutions.     

Area preserving maps and volume preserving maps between a class of polyhedrons and a sphere

We construct a bijective continuous area preserving map from a class of elongated dipyramids to the sphere, together with its inverse. Then we investigate for which such solid polyhedrons the area preserving map can be used for constructing a bijective continuous volume preserving map to the 3D-ball. These maps can be further used in constructing uniform and refinable grids on the sphere and on the ball, starting from uniform and refinable grids on the elongated dipyramids. In particular, we show that HEALPix grids can be obtained from these maps. We also study the optimality of the logarithmic energy of the configurations of points obtained from these grids.     

Bandwidth and pathwidth of three-dimensional grids

We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case. As a by-product, we also determine the two parameters of multi-dimensional grids with relatively large maximum factors.     

Constrained CVT meshes and a comparison of triangular mesh generators

Mesh generation in regions in Euclidean space is a central task in computational science, and especially for commonly used numerical methods for the solution of partial differential equations, e.g., finite element and finite volume methods. We focus on the uniform Delaunay triangulation of planar regions and, in particular, on how one selects the positions of the vertices of the triangulation. We discuss a recently developed method, based on the centroidal Voronoi tessellation (CVT) concept, for effecting such triangulations and present two algorithms, including one new one, for CVT-based grid generation. We also compare several methods, including CVT-based methods, for triangulating planar domains. To this end, we define several quantitative measures of the quality of uniform grids. We then generate triangulations of several planar regions, including some having complexities that are representative of what one may encounter in practice. We subject the resulting grids to visual and quantitative comparisons and conclude that all the methods considered produce high-quality uniform grids and that the CVT-based grids are at least as good as any of the others.     

A social approach for target localization: simulation and implementation in the marXbot robot

Foraging is a common benchmark problem in collective robotics in which a robot (the forager) explores a given environment while collecting items for further deposition at specific locations. A typical real-world application of foraging is garbage collection where robots collect garbage for further disposal in pre-defined locations. This work proposes a method to cooperatively perform the task of finding such locations: instead of using local or global localization strategies relying on pre-installed infrastructure, the proposed approach takes advantage of the knowledge gathered by a population about the localization of the targets. In our approach, robots communicate in an intrinsic way the estimation about how near they are from a target; these estimations are used by neighbour robots for estimating their proximity, and for guiding the navigation of the whole population when looking for these specific areas. We performed several tests in a simulator, and we validated our approach on a population of real robots. For the validation tests we used a mobile robot called marXbot. In both cases (i.e., simulation and implementation on real robots), we found that the proposed approach efficiently guides the robots towards the pre-specified targets while allowing the modulation of their speed.     

Gaussian free fields for mathematicians

The d-dimensional Gaussian free field (GFF), also called the (Euclidean bosonic) massless free field, is a d-dimensional-time analog of Brownian motion. Just as Brownian motion is the limit of the simple random walk (when time and space are appropriately scaled), the GFF is the limit of many incrementally varying random functions on d-dimensional grids. We present an overview of the GFF and some of the properties that are useful in light of recent connections between the GFF and the Schramm–Loewner evolution. Partially supported by NSF grant DMS0403182.     

Fair upper bounds for the curvature in univariate convex interpolation

In convex interpolation the curvature of the interpolants should be as small as possible. We attack this problem by treating interpolation subject to bounds on the curvature. In view of the concexity the lower bound is equal to zero while the upper bound is assumed to be piecewise constant. The upper bounds are called fair with respect to a function class if the interpolation problem becomes solvable for all data sets in strictly convex position. We derive fair a priori bounds for classes of quadraticC ¹, cubicC ², and quarticC ³ splines on refined grids.     

On variable stepsize Runge-Kutta approximations of a Cauchy problem for the evolution equation

We consider a Cauchy problem for the sectorial evolution equation with generally variable operator in a Banach space. Variable stepsize discretizations of this problem by means of a strongly A(φ)-stable Runge-Kutta method are studied. The stability and error estimates of the discrete solutions are derived for wider families of nonuniform grids than quasiuniform ones (in particular, if the operator in question is constant or Lipschitz-continuous, for arbitrary grids).