Finite-time coordination in multiagent systems using sliding mode control approach

Finite-time stability in dynamical systems theory involves systems whose trajectories converge to an equilibrium state in finite time. In this paper, we use the notion of finite-time stability to apply it to the problem of coordinated motion in multiagent systems. Specifically, we consider a group of agents described by fully actuated Euler–Lagrange dynamics along with a leader agent with an objective to reach and maintain a desired formation characterized by steady-state distances between the neighboring agents in finite time. We use graph theoretic notions to characterize communication topology in the network determined by the information flow directions and captured by the graph Laplacian matrix. Furthermore, using sliding mode control approach, we design decentralized control inputs for individual agents that use only data from the neighboring agents which directly communicate their state information to the current agent in order to drive the current agent to the desired steady state. Sliding mode control is known to drive the system states to the sliding surface in finite time. The key feature of our approach is in the design of non-smooth sliding surfaces such that, while on the sliding surface, the error states converge to the origin in finite time, thus ensuring finite-time coordination among the agents in the network. In addition, we discuss the case of switching communication topologies in multiagent systems. Finally, we show the efficacy of our theoretical results using an example of a multiagent system involving planar double integrator agents.     

Distributing Finite Automata Through Petri Net Synthesis

The synthesis problem for Petri nets consists in deciding constructively the existence of a Petri net with sequential state graph isomorphic to a given graph. If events are attached to locations, one may set as an additional requirement that the synthesised net should be distributable; i.e. such that events at different locations have no common input place, whence distributed conflicts are avoided. Distributable nets are easily implemented by finite families of automata (one per location) communicating with each other by asynchronous message passing. We show that the general Petri net synthesis problem and its distributed version may both be solved in time polynomial in the size of the given graph. We report on some preliminary experiments of Petri net synthesis applied to the distribution of reactive automata using the tool SYNET. Received November 2000 / Accepted in revised form August 2001     

A framework for the verification of infinite-state graph transformation systems

We propose a technique for the analysis of infinite-state graph transformation systems, based on the construction of finite structures approximating their behaviour. Following a classical approach, one can construct a chain of finite under-approximations (k-truncations) of the Winskel style unfolding of a graph grammar. More interestingly, also a chain of finite over-approximations (k-coverings) of the unfolding can be constructed. The fact that k-truncations and k-coverings approximate the unfolding with arbitrary accuracy is formalised by showing that both chains converge (in a categorical sense) to the full unfolding. We discuss how the finite over- and under-approximations can be used to check properties of systems modelled by graph transformation systems, illustrating this with some small examples. We also describe the Augur tool, which provides a partial implementation of the proposed constructions, and has been used for the verification of larger case studies.     

Switched nonlinear systems with state-dependent dwell-time

The asymptotic convergence of a switched nonlinear system in the presence of disturbances is studied. The system switches among a family of integral input-to-state stable systems. The time between two consecutive switchings is not less than a value τ_D. This dwell-time τ_D is allowed to take different values according to a function whose argument is the state of the system at the switching times. We propose a dwell-time function which depends on the comparison functions which characterize the integral input-to-state stability property and guarantees the state of the switched system to converge to zero under the action of disturbances with “bounded energy”. The main feature of the analysis is that it does not rely on the property for the switching to stop in finite time. The two important cases of locally exponentially stable and feedforward systems are analyzed in detail.     

Infinite vs. finite size-bounded randomized computations

Randomized computations can be very powerful with respect to space complexity, e.g., for logarithmic space, LasVegas is equivalent to nondeterminism. This power depends on the possibility of infinite computations, however, it is an open question if they are necessary. We answer this question for rotating finite automata (rfas) and sweeping finite automata (sfas). We show that LasVegas rfas (sfas) allowing infinite computations, although only with probability 0, can be exponentially smaller than LasVegas rfas (sfas) forbidding them. In particular, we show that even rfas (sfas) with linear expected running time may require exponentially more states than rfas (sfas) running in exponential time. We also strengthen this result, showing that the restriction on time cannot be traded for the more powerful bounded-error randomization. To prove our results, we introduce a technique for proving lower bounds on size of rfas (sfas) that generalizes the notion of generic strings discovered by M. Sipser.     

基于粘贴和删除系统的图着色问题分析(英文)

图着色问题是图与组合优化中的一个NP-完全问题．现有算法在求解图着色问题时,计算复杂性随着待解问题规模的增大呈指数增长．粘贴系统和删除系统是分别基于粘贴运算和删除运算的两种语言生成器．文中将图着色问题和图的坏边数结合起来,将图着色问题转化成搜索最长序列的问题,然后利用粘贴系统和删除系统的并行性,得到了图的色数及其所有色类．与已有求解图着色问题的DNA算法相比,新的算法具有较低的复杂性．     

一种用于Marching-Graph图形绘制的快速收敛布局算法

Marching-Graph是一种将图形隐喻技术和空间隐喻技术集成为一体的新的可视化方法.它为用户提供了高度可交互性地图,使用户可访问那些具有地理属性的信息的逻辑结构.它通过有效的人图交互和跨空间浏览为用户提供了一种可视分析和挖掘未知信息的机制,而不是将已知的信息呈现在地图上.然而,传统的力导向布局算法在达到力量均衡配置方面非常慢.为使一个图形布局收敛,它们通常需花费几十秒的时间.因此。当用户快速行进于地理区间时,那些力导向布局算法就不能满足快速绘制一系列图形的要求.提出了一种快速收敛布局方法,当用户在Marching-Graph中通过力导向布局逐步探究一系列图形时,它可以加速交互时间.通过结合辐射树绘图技术和力导向图形绘制方法来取得能量最小化的快速收敛.     

Stable Flocking of Multiple Inertial Agents on Balanced Graphs

In this note, we consider the flocking of multiple agents which have significant inertias and evolve on a balanced information graph. Here, by flocking, we mean that all the agents move with a common velocity while keeping a certain desired internal group shape. We first show that flocking algorithms that neglect agents' inertial effect can cause unstable group behavior. To incorporate this inertial effect, we use the passive decomposition, which decomposes the closed-loop group dynamics into two decoupled systems: a shape system representing the internal group shape and a locked system describing the motion of the center-of-mass. Then, analyzing the locked and shape systems separately with the help of graph theory, we propose a provably stable flocking control law, which ensures that the internal group shape is exponentially stabilized to a desired one, while all the agents' velocities converge to the centroid velocity that is also shown to be time-invariant. This result still holds for slow-switching balanced information graphs. Simulation is performed to validate the theory.     

Stability analysis of switched systems with stable and unstable subsystems: An average dwell time approach

We study the stability properties of switched systems consisting of both Hurwitz stable and unstable linear time-invariant subsystems using an average dwell time approach. We propose a class of switching laws so that the entire switched system is exponentially stable with a desired stability margin. In the switching laws, the average dwell time is required to be sufficiently large, and the total activation time ratio between Hurwitz stable subsystems and unstable subsystems is required to be no less than a specified constant. We also apply the result to perturbed switched systems where nonlinear vanishing or non-vanishing norm-bounded perturbations exist in the subsystems, and we show quantitatively that, when norms of the perturbations are small, the solutions of the switched systems converge to the origin exponentially under the same switching laws.     

联合连通拓扑下的二阶多自主体系统有限时间包容控制

针对具有多领航者的二阶网络化系统群集运动问题,提出了一种有限时间收敛的包容控制算法。在此基础上,运用现代控制理论、代数图论和矩阵论等分析工具对所提出的控制算法进行理论分析,得到了当通信拓扑为动态联合连通时,二阶网络化系统在有限时间内实现群集运动的收敛条件。通过此包容控制算法,使得系统在静态拓扑和联合连通条件下均在有限时间内收敛到目标区域内。最后,应用系统仿真验证了所得结论的正确性。     

Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities

Many vision tasks can be formulated as graph partition problems that minimize energy functions. For such problems, the Gibbs sampler provides a general solution but is very slow, while other methods, such as Ncut and graph cuts are computationally effective but only work for specific energy forms and are not generally applicable. In this paper, we present a new inference algorithm that generalizes the Swendsen-Wang method to arbitrary probabilities defined on graph partitions. We begin by computing graph edge weights, based on local image features. Then, the algorithm iterates two steps: (1) graph clustering - it forms connected components by cutting the edges probabilistically based on their weights; (2) graph relabeling - it selects one connected component and flips probabilistically, the coloring of all vertices in the component simultaneously. Thus, it realizes the split, merge, and regrouping of a "chunk" of the graph, in contrast to Gibbs sampler that flips a single vertex. We prove that this algorithm simulates ergodic and reversible Markov chain jumps in the space of graph partitions and is applicable to arbitrary posterior probabilities or energy functions defined on graphs. We demonstrate the algorithm on two typical problems in computer vision-image segmentation and stereo vision. Experimentally, we show that it is 100-400 times faster in CPU time than the classical Gibbs sampler and 20-40 times faster then the DDMCMC segmentation algorithm. For stereo, we compare performance with graph cuts and belief propagation. We also show that our algorithm can automatically infer generative models and obtain satisfactory results (better than the graphic cuts or belief propagation) in the same amount of time.     

Finite‐time attitude control of multiple rigid spacecraft using terminal sliding mode

This paper investigates the control problem of finite‐time attitude synchronization and tracking for a group of rigid spacecraft in the presence of environmental disturbances. A new fast terminal sliding manifold is developed for multiple spacecraft formation flying under the undirected graph topology. On the basis of the finite‐time control and adaptive control strategies, two novel decentralized finite‐time control laws are proposed to force the spacecraft attitude error dynamics to converge to small regions in finite time, and adaptive control is applied to reject the disturbance. The finite‐time convergence and stability of the closed‐loop system can be guaranteed by Lyapunov theory. Simulation examples are provided to illustrate the feasibility of the control algorithm. Copyright © 2014 John Wiley & Sons, Ltd.     

Nonlinear finite-time bipartite consensus protocol for multi-agent systems associated with signed graphs

In this paper, finite-time multi-agent consensus problems are considered under networks associated with signed graphs whose edge weights can be not only positive but also negative. A nonlinear consensus protocol is proposed to guarantee the states of all agents to converge in a finite time. If the signed graph is structurally balanced, then the final consensus states of all agents are the same in modulus but not in sign. Otherwise, if the signed graph is structurally unbalanced, then the states of all agents converge to zero. Moreover, the final consensus states of agents can be provided uniformly regarding a signed-average quantity that depends on both the initial states of agents and the topology structure of the whole multi-agent network. Numerical simulations illustrate that the protocol is effective in achieving the finite-time consensus of agents under signed graphs and can particularly solve the finite-time average consensus problem of agents when their associated graph has all positive edge weights.     

Minority Games, Local Interactions, and Endogenous Networks

We study a local version of the Minority Game, where agents are placed on the nodes of a directed graph. Agents care about being in the minority of the group of agents they are currently linked to and employ myopic best-reply rules to choose their next-period state. We show that, in this benchmark case, the smaller the size of local networks, the larger long-run population-average payoffs. We then explore the collective behavior of the system when agents can: (i) assign weights to each link they hold and modify them over time in response to payoff signals; (ii) delete badly performing links (i.e., opponents) and replace them with randomly chosen ones. Simulations suggest that, when agents are allowed to weigh links but cannot delete/replace them, the system self-organizes into networked clusters that attain very high payoff values. These clustered configurations are not stable and can easily be disrupted, generating huge subsequent payoff drops. If, however, agents can (and are sufficiently willing to) discard badly performing connections, the system quickly converges to stable states where all agents get the highest payoff, independently of the size of the networks initially in place.JEL Classification:s C72, C73.     

Remeshing-free Graph-based Finite Element Method for Fracture Simulation

Fracture produces new mesh fragments that introduce additional degrees of freedom in the system dynamics. Existing finite element method (FEM) based solutions suffer from increasing computational cost as the system matrix size increases. We solve this problem by presenting a graph-based FEM model for fracture simulation that is remeshing-free and easily scales to high-resolution meshes. Our algorithm models fracture on the graph induced in a volumetric mesh with tetrahedral elements. We relabel the edges of the graph using a computed damage variable to initialize and propagate fracture. We prove that non-linear, hyper-elastic strain energy density is expressible entirely in terms of the edge lengths of the induced graph. This allows us to reformulate the system dynamics for the relabelled graph without changing the size of the system dynamics matrix and thus prevents the computational cost from blowing up. The fractured surface has to be reconstructed explicitly only for visualization purposes. We simulate standard laboratory experiments from structural mechanics and compare the results with corresponding real-world experiments. We fracture objects made of a variety of brittle and ductile materials, and show that our technique offers stability and speed that is unmatched in current literature.     

基于事件驱动的多智能体有限时间分群一致控制

针对二阶线性多智能体系统的分群一致控制问题,考虑智能体通信拓扑同时包含协作和对抗关系,提出一种基于事件驱动控制的有限时间分布式领航跟随分群一致性算法,该算法可使多智能体系统在有限时间内实现分群一致,即各子组内的智能体实现状态一致,不同子组收敛至不同一致状态.采用事件驱动控制机制,设计事件驱动函数及事件触发条件,降低智能体控制器更新频率,减少系统能耗.基于代数图论和李雅普诺夫稳定性理论推导出系统的有限时间稳定性条件,通过巧妙构造Lyapunov函数,给出系统有限收敛时间的显式估计,同时证明在所提出的事件驱动机制下,每个智能体相邻触发时间间隔有严格的正下界,即避免了芝诺行为.仿真实验验证了所提出的有限时间事件驱动分群一致控制算法的有效性.     

Robust convergence of discrete‐time delayed switched nonlinear systems and its applications to cascade systems

Systems in real world are always subject to perturbations. This paper addresses the convergence properties of a class of nominal systems with perturbations. It is assumed that the nominal system is a switched nonlinear exponentially stable one with time‐varying delays and that the perturbation exponentially or asymptotically converges to zero. It is revealed that the trajectories of the perturbed system behave as the perturbation, ie, trajectories exponentially or asymptotically converge to zero, depending on the property of perturbation. Applying these results to cascade switched nonlinear systems, it is shown that such systems are exponentially stable if and only if all the subsystems, obtained by removing the coupling terms, are exponentially stable. A similar conclusion is presented for systems being asymptotically stable. Finally, a numerical example illustrates the proposed theoretical results.     

Phase changes in the evolution of the IPv4 and IPv6 AS-Level Internet topologies

In this paper, we investigate the evolution of the IPv4 and IPv6 Internet topologies at the autonomous system (AS) level over a long period of time. We provide abundant empirical evidence that there is a phase transition in the growth trend of the two networks. For the IPv4 network, the phase change occurred in 2001. Before then the network’s size grew exponentially, and thereafter it followed a linear growth. Changes are also observed around the same time for the maximum node degree, the average node degree and the average shortest path length. For the IPv6 network, the phase change occurred in late 2006. It is notable that the observed phase transitions in the two networks are different, for example the size of IPv6 network initially grew linearly and then shifted to an exponential growth. Our results show that following decades of rapid expansion up to the beginning of this century, the IPv4 network has now evolved into a mature, steady stage characterised by a relatively slow growth with a stable network structure; whereas the IPv6 network, after a slow startup process, has just taken off to a full speed growth. We also provide insight into the possible impact of IPv6-over-IPv4 tunnelling deployment scheme on the evolution of the IPv6 network. The Internet topology generators so far are based on an inexplicit assumption that the evolution of Internet follows non-changing dynamic mechanisms. This assumption, however, is invalidated by our results. Our work reveals insights into the Internet evolution and provides inputs to future AS-Level Internet models.     

The subsumption lattice and query learning

The paper identifies several new properties of the lattice induced by the subsumption relation over first-order clauses and derives implications of these for learnability. In particular, it is shown that the length of subsumption chains of function free clauses with bounded size can be exponential in the size. This suggests that simple algorithmic approaches that rely on repeating minimal subsumption-based refinements may require a long time to converge. It is also shown that with bounded size clauses the subsumption lattice has a large branching factor. This is used to show that the class of first-order length-bounded monotone clauses is not properly learnable from membership queries alone. Finally, the paper studies pairing, a generalization operation that takes two clauses and returns a number of possible generalizations. It is shown that there are clauses with an exponential number of pairing results which are not related to each other by subsumption. This is used to show that recent pairing-based algorithms can make exponentially many queries on some learning problems.     

Reconstruction of interval graphs

The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems by limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs.