Optimal partitioning for multi-vehicle systems using quadratic performance criteria

We consider the problem of characterizing a generalized Voronoi diagram that is relevant to a special class of area assignment problems for multi-vehicle systems. It is assumed that the motion of each vehicle is described by a second order mechanical system with time-varying linear or affine dynamics. The proposed generalized Voronoi diagram encodes information regarding the proximity relations between the vehicles and arbitrary target points in the plane. These proximity relations are induced by an anisotropic (generalized) distance function that incorporates the vehicle dynamics. In particular, the generalized distance is taken to be the minimum control effort required for the transition of a vehicle to an arbitrary target point with a small terminal speed at a fixed final time. The space we wish to partition corresponds to the union of all the terminal positions that can be attained by each vehicle using finite control effort. Consequently, the partition space has lower dimension than the state space of each vehicle. We show that, in the general case, the solution to the proposed partitioning problem can be associated with a power Voronoi diagram generated by a set of spheres in a five-dimensional Euclidean space for the computation of which efficient techniques exist in the relevant literature.     

Decentralized spatial partitioning algorithms for multi-vehicle systems based on the minimum control effort metric

We consider the problem of characterizing a spatial partition of the position space of a team of vehicles with linear time-varying kinematics. The generalized metric that determines the proximity relations between the vehicles and an arbitrary target point in the partition space is the minimum control effort required for each vehicle to reach the latter point with zero miss distance and exactly zero velocity at a prescribed final time. We show that the solution to the generalized Voronoi partitioning problem can be associated with a special class of spatial partitions known as affine diagrams. Because the combinatorial complexity of the affine diagrams is comparable to the one of the standard Voronoi diagrams, their computation does not pose a significant challenge in applications of multi-vehicle systems. Subsequently, we propose an algorithm for the computation of the spatial partition, which is decentralized in the sense that each vehicle can compute an approximation of its own cell independently from the other vehicles from the same team without utilizing a common spatial mesh. Numerical simulations that illustrate the theoretical developments are also presented.     

Fault-tolerant cooperative output regulation for multi-vehicle systems with sensor faults

This paper presents a unified framework of fault diagnosis and fault-tolerant cooperative output regulation (FTCOR) for a linear discrete-time multi-vehicle system with sensor faults. The FTCOR control law is designed through three steps. A cooperative output regulation (COR) controller is designed based on the internal mode principle when there are no sensor faults. A sufficient condition on the existence of the COR controller is given based on the discrete-time algebraic Riccati equation (DARE). Then, a decentralised fault diagnosis scheme is designed to cope with sensor faults occurring in followers. A residual generator is developed to detect sensor faults of each follower, and a bank of fault-matching estimators are proposed to isolate and estimate sensor faults of each follower. Unlike the current distributed fault diagnosis for multi-vehicle systems, the presented decentralised fault diagnosis scheme in each vehicle reduces the communication and computation load by only using the information of the vehicle. By combing the sensor fault estimation and the COR control law, an FTCOR controller is proposed. Finally, the simulation results demonstrate the effectiveness of the FTCOR controller.     

Distributed partitioning algorithms for multi-agent networks with quadratic proximity metrics and sensing constraints

We consider a class of Voronoi-like partitioning problems, in which a multi-agent network seeks to subdivide a subset of an affine space into a finite number of cells in the presence of sensing constraints. The cell of this subdivision that is assigned to a particular agent consists exclusively of points that can be sensed by this agent and are closer to it than to any other agent that can also sense them. The proximity between an agent and an arbitrary point is measured in terms of a non-homogeneous quadratic (generalized) distance function, which does not, in general, enjoy the triangle inequality and the symmetry property. One of the consequences of this fact is that the structure of the sublevel sets of the utilized proximity metric does not conform with that of the sensing region of an agent. Due to this mismatch, it is possible that a point may be assigned to an agent which is different from its “nearest” agent simply because the nearest agent cannot sense this point, unless special care is taken. We propose a distributed partitioning algorithm that enables each agent to compute its own cell independently from the other agents when the only information available to it is the positions and the velocities of the agents that lie inside its sensing region. The algorithm is based on an iterative process that adjusts the size of the sensing region of each agent until the associated cell of the latter corresponds to the intersection of its sensing region with the cell that would have been assigned to it in the absence of sensing constraints. The correctness of the proposed distributed algorithm, which successfully handles the aforementioned issues, is studied in detail.     

Splitting a Delaunay Triangulation in Linear Time

Abstract. Computing the Delaunay triangulation of n points requires usually a minimum of Ω(n log n) operations, but in some special cases where some additional knowledge is provided, faster algorithms can be designed. Given two sets of points, we prove that, if the Delaunay triangulation of all the points is known, the Delaunay triangulation of each set can be computed in randomized expected linear time.     

Voronoi diagrams of moving points in the plane and of lines in space: tight bounds for simple configurations

The combinatorial complexities of (1) the Voronoi diagram of moving points in 2D and (2) the Voronoi diagram of lines in 3D, both under the Euclidean metric, continues to challenge geometers because of the open gap between the Ω(n²) lower bound and the O(n3+?) upper bound. Each of these two combinatorial problems has a closely related problem involving Minkowski sums: (1′) the complexity of a Minkowski sum of a planar disk with a set of lines in 3D and (2′) the complexity of a Minkowski sum of a sphere with a set of lines in 3D. These Minkowski sums can be considered “cross-sections” of the corresponding Voronoi diagrams. Of the four complexity problems mentioned, problems (1′) and (2′) have recently been shown to have a nearly tight bound: both complexities are O(n2+?) with lower bound Ω(n²).In this paper, we determine the combinatorial complexities of these four problems for some very simple input configurations. In particular, we study point configurations with just two degrees of freedom (DOFs), exploring both the Voronoi diagrams and the corresponding Minkowski sums. We consider the traditional versions of these problems to have 4 DOFs. We show that even for these simple configurations the combinatorial complexities have upper bounds of either O(n²) or O(n2+?) and lower bounds of Ω(n²).     

Optimal Parallel Randomized Algorithms for the Voronoi Diagram of Line Segments in the Plane

Abstract. We present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n nonintersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(log n) time with high probability using O(n) processors on a CRCW PRAM. This algorithm is optimal in terms of work done since the sequential time bound for this problem is Ω(n log n) . Our algorithm improves by an O(log n) factor the previously best known deterministic parallel algorithm, given by Goodrich, ó'Dúnlaing, and Yap, which runs in O( log ² n) time using O(n) processors. We obtain this result by using a new ``two-stage' random sampling technique. By choosing large samples in the first stage of the algorithm, we avoid the hurdle of problem-size ``blow-up' that is typical in recursive parallel geometric algorithms. We combine the two-stage sampling technique with efficient search and merge procedures to obtain an optimal algorithm. This technique gives an alternative optimal algorithm for the Voronoi diagram of points as well (all other optimal parallel algorithms for this problem use the transformation to three-dimensional half-space intersection).     

A computational approach to synthesizing guards for hybrid systems

We propose a technique for synthesizing switching guards for hybrid systems to satisfy a given state-based safety constraint. Using techniques from sum of squares (SOS) optimization, we design guards defined by semialgebraic sets that trigger mode switches, and we guarantee that the synthesized switching policy does not allow Zeno executions. We demonstrate our approach on an example of switched affine systems and on an application to traffic ramp metering.     

Independent agents in a globalized world modelled by tissue P systems

For modelling the interactions of independent agents (only interacting via a common environment, but not depending on any direct physical interactions with other agents) in the globalized world, we here consider so-called agent tissue P systems (ATP systems). Based on the model of tissue P systems, such ATP systems consist of cells (independent agents) with specific programs which allow for changing the objects inside the agent or for exchanging objects from inside the agent with objects from the environment through the cell membrane. We investigate the computational power of specific variants of ATP systems, and also discuss the special decidability problem whether or not a given ATP system of a specific type from its initial contents can ever reach a configuration where all objects in the system are contained in a specific subset of the set of objects.     

Parallel algorithms for the solution of certain large sparse linear systems

A couple of approximate inversion techniques are presented which provide a parallel enhancement to several iterative methods for solving linear systems arising from the discretization of boundary value problems. In particular, the Jacobi, Gauss‐Seidel, and successive overrelaxation methods can be improved substantially in a parallel environment by the extensions considered. A special case convergence proof is presented. The use of our approximate inverses with the preconditioned conjugate gradient method is examined and comparisons are made with some recently proposed algorithms in this area that also employ approximate inverses. The methods considered are compared under sequential and parallel hardware assumptions.     

求解非线性方程组的智能优化算法综述

非线性方程组的求解是优化领域的一个重要研究课题.近年来,利用智能优化算法求解非线性方程组已成为一个重要方向.首先介绍非线性方程组的定义;其次,根据智能优化算法求解非线性方程组问题的基本框架,从转化方法和智能优化算法两方面入手,对求解非线性方程组的算法的研究进展进行归纳总结;再次,对非线性方程组的测试函数及评价指标进行描述,对比了5个具有代表性算法的性能,分析了目前利用智能优化算法求解非线性方程组亟待解决的问题;最后,指出值得进一步研究的方向.     

Symplectic spatial integration schemes for systems of balance equations

A method to generate geometric pseudo-spectral spatial discretization schemes for hyperbolic or parabolic partial differential equations is presented. It applies to the spatial discretization of systems of conservation laws with boundary energy flows and/or distributed source terms. The symplecticity of the proposed spatial discretization schemes is defined with respect to the natural power pairing (form) used to define the port-Hamiltonian formulation for the considered systems of balance equations. The method is applied to the resistive diffusion model, a parabolic equation describing the plasma dynamics in tokamaks. A symplectic Galerkin scheme with Bessel conjugated bases is derived from the usual Galerkin method, using the proposed method. Besides the spectral and energetic properties expected from the symplecticity of the method, it is shown that more accurate approximation of eigenfunctions and reduced numerical oscillations result from this choice of conjugated approximation bases. Finally, the obtained numerical results are validated against experimental data from the tokamak Tore Supra facility.     

A series solution to the nash strategy for large scale interconnected systems

Optimum control of a linear large scale dynamic system is formulated as a game problem using individual subsystem quadratic cost functions and an overall Nash solution strategy. Computational complexities of the exact solution for large systems is overcome by parametric series solution based on ?-coupling. Computational virtues of this approach are noted, and the relation of the approximate and exact solutions is examined.     

A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains

We introduce a new method for computing the geodesic Voronoi diagram of point sites in a simple polygon and other restricted polygonal domains. Our method combines a sweep of the polygonal domain with the merging step of a usual divide-and-conquer algorithm. The time complexity is O((n+k) log(n+k)) where n is the number of vertices and k is the number of points, improving upon previously known bounds. Space is O(n+k) . Other polygonal domains where our method is applicable include (among others) a polygonal domain of parallel disjoint line segments and a polygonal domain of rectangles in the L ₁ metric. Received February 15, 1996; revised November 2, 1996.     

Robust prediction-based control for unstable delay systems: Application to the yaw control of a mini-helicopter

We present a discrete-time prediction-based state-feedback controller. It is shown that this controller stabilizes possibly unstable continuous-time delay systems. The stability is shown to be robust with respect to uncertainties in the knowledge on the plant parameters, the system delay and the sampling period. The proposed prediction-based controller has been tested in a real-time application to control the yaw angular displacement of a 4-rotor mini-helicopter.     

A computational model of time for stiff hybrid systems applied to control synthesis

Computation has quickly become of paramount importance in the design of engineered systems, both to support their features as well as their design. Tool support for high-level modeling formalisms has endowed design specifications with executable semantics. Such specifications typically include not only discrete-time and discrete-event behavior, but also continuous-time behavior that is stiff from a numerical integration perspective. The resulting stiff hybrid dynamic systems necessitate variable-step solvers to simulate the continuous-time behavior as well as solver algorithms for the simulation of discrete-time and discrete-event behavior. The combined solvers rely on complex computer code which makes it difficult to directly solve design tasks with the executable specifications. To further leverage the executable specifications in design, this work aims to formalize the semantics of stiff hybrid dynamic systems at a declarative level by removing implementation detail and only retaining ‘what’ the computer code does and not ‘how’ it does it. A stream-based approach is adopted to formalize variable-step solver semantics and to establish a computational model of time that supports discrete-time and discrete-event behavior. The corresponding declarative formalization is amenable to computational methods and it is shown how model checking can automatically generate, or synthesize, a feedforward control strategy for a stiff hybrid dynamic system. Specifically, a stamper in a surface mount device is controlled to maintain a low acceleration of the stamped component for a prescribed minimum duration of time.     

High-order necessary conditions of optimality for nonlinear control systems

For nonlinear affine control systems with unbounded controls, necessary high-order optimality conditions are derived. These conditions are stated in the form of a high-order maximum principle and are expressed in terms of Lie brackets and Newton diagrams.     

The order of merging operations for queries in inverted file systems

In inverted file systems, queries can be written as Boolean expressions of inverted attributes. In response to a query, the system accesses address lists associated with the attributes in the query, merges them, and selects those records that satisfy the search logic. In this paper we consider the minimization of the CPU time needed for the merging operation. The time can possibly be reduced by taking address lists that occur in several product terms as a common factor of these products. This means that the union operation must be performed before the intersection operation. We present formulas which can be used to decide whether the above method is advantageous. The time can also be reduced by choosing the order of intersection operations so that it takes into consideration the occurrences of the address lists in the products and the lengths of the address lists. For choosing the order of intersection operations we give a heuristic algorithm that minimizes the total time needed for intersections.