Asymptotic Enumeration of Extensional Acyclic Digraphs

The enumeration of extensional acyclic digraphs, which have the property that the outneighbourhoods are pairwise distinct, was considered in a recent article of Policriti and Tomescu. Several asymptotic questions were left as open problems. In this article, we determine the asymptotic number of such digraphs and show that a number of distributional results can be carried over from ordinary acyclic digraphs. In particular, we consider the distribution of the number of sources, the number of arcs, the maximum rank and the number of vertices of maximum rank, thereby also proving some conjectures made by Policriti and Tomescu. Finally, we study a very similar class of acyclic digraphs and provide analogous distributional results.     

Cooperative Control and Potential Games

We present a view of cooperative control using the language of learning in games. We review the game-theoretic concepts of potential and weakly acyclic games, and demonstrate how several cooperative control problems, such as consensus and dynamic sensor coverage, can be formulated in these settings. Motivated by this connection, we build upon game-theoretic concepts to better accommodate a broader class of cooperative control problems. In particular, we extend existing learning algorithms to accommodate restricted action sets caused by the limitations of agent capabilities and group based decision making. Furthermore, we also introduce a new class of games called sometimes weakly acyclic games for time-varying objective functions and action sets, and provide distributed algorithms for convergence to an equilibrium.     

A Visualization Framework and User Studies for Overloaded Orthogonal Drawings

Overloaded orthogonal drawing (OOD) is a recent graph visualization style specifically conceived for directed graphs. It merges the advantages of some popular drawing conventions like layered drawings and orthogonal drawings, and provides additional support for some common analysis tasks. We present a visualization framework called DAGView, which implements algorithms and graphical features for the OOD style. Besides the algorithm for acyclic digraphs, the DAGView framework implements extensions to visualize both digraphs with cycles and undirected graphs, with the additional possibility of taking into account user preferences and constraints. It also supports an interactive visualization of clustered digraphs, based on the use of strongly connected components. Moreover, we describe an experimental user study, aimed to investigate the usability of OOD within the DAGView framework. The results of our study suggest that OOD can be effectively exploited to perform some basic tasks of analysis in a faster and more accurate way when compared to other drawing styles for directed graphs.     

Cluster consensus of high-order multi-agent systems with switching topologies

This paper investigates the cluster consensus problems of generic linear multi-agent systems with switching topologies. Sufficient criteria for cluster consensus, which generalise the results in existing literatures, are derived for both state feedback and observer-based control schemes. By using an averaging method, it is shown that cluster consensus can be achieved when the union of the acyclic topologies contains a directed spanning tree within each cluster frequently enough. We also provide a principle to construct digraphs with inter-cluster cyclic couplings that promote cluster consensus regardless of the magnitude of inter-agent coupling weights. Finally, numerical examples are given to demonstrate the effectiveness of the proposed approaches.     

Counting extensional acyclic digraphs

Transitive sets with n elements were counted by Peddicord in 1962, by the use of Ackermann?s numeric encoding of a (hereditarily finite) set. In this paper we give a combinatorial interpretation of this number by counting extensional acyclic digraphs. In a similar constructive manner, we also obtain the number of weakly extensional acyclic digraphs with a given number of labeled sinks and a given number of sources, or with a given number of vertices of maximum rank.     

Series Parallel Digraphs with Loops

In the conversion of finite automata to regular expressions, an exponential blowup in size can generally not be avoided. This is due to graph-structural properties of automata which cannot be directly encoded by regular expressions and cause the blowup combinatorially. In order to identify these structures, we generalize the class of arc-series-parallel digraphs beyond the acyclic case. The resulting digraphs are shown to be reversibly encoded by linear-sized regular expressions. Also, a characterization of this new class by a set of seven forbidden substructures is given. Automata that require expressions of superlinear size must contain some of these substructures.     

ON THE STRUCTURE OF DIRECTED GRAPHS WITH APPLICATIONS: A Rapprochement with Systems Theory Part I

In Part I, certain fundamental structural properties of directed graphs (digraphs) are explored using a unified systemtheoretic approach. In the spirit of general systems theory, a digraph is modelled as a dynamic system with multiple inputs and outputs. The concept of controllability, observability, and the elegant theory of minimal realization, duality, and Kalman's decomposition in linear systems have all found their positions in digraphs. New computation algorithms are derived.

In Part II (Vol, 8, No. 4 of this journal) of this paper, the structure of composite digraphs, and subgraph interaction/decomposition are studied. Applications to computer systems, Markov chains, and to dynamic systems and control are presented.     

Error models for stable hybrid adaptive systems

This paper presents several stable adaptive algorithms for the control of hybrid and discrete systems in which the control parameters are adjusted at rates slower than those at which the systems operate. Continuous algorithms of an integral type, recently suggested in the literature [5] are also shown to belong to this class. From a practical standpoint, the infrequent adjustment of the control parameters makes for more robust adaptive control while from a theoretical point of view, the algorithms are attractive since they provide a unified framework for the design of continuous, hybrid, and discrete adaptive systems. Simulation results are included to indicate the type of responses that can be expected using the different algorithms.     

Unified adaptive control of non-minimum-phase systems Part 1. Weighted control effort and pole placement for stochastic systems

Global convergence of a class of unified adaptive control algorithms for discrete time non-minimum-phase stochastic linear systems is established. It is shown that the algorithms ensure that the system inputs and outputs are sample mean bounded, the minimum variance cost function with weighted control effort achieves its minimum possible values, the weighted factors adjusted on-line eventually converge to expected values, and the closed-loop poles arise at prespecified locations.     

一类异构多智能体系统有向图下的广义平均一致性分析

本文对有向图下离散时间一阶二阶混合的异构多智能体系统广义平均一致性问题进行研究.首先给出了该异构系统广义平均一致性的基本概念.在此基础上,针对平均一致性研究中对交互拓扑为平衡网络的局限,提出了一种基于辅助变量的线性一致性协议,对每一个智能体增加一个辅助变量,用于记录个体的状态更新.采用图论、非负矩阵理论、特征值扰动等方法进行分析证明,表明该协议使得异构多智能体系统在任意强连通有向图下达到广义平均一致性.并对收敛值的性质进行了分析.最后,通过仿真对该结论进行了验证.     

Quasi-Upward Planarity

An upward planar drawing of a directed graph (digraph) is a planar drawing such that all the edges are represented by curves monotonically increasing in the vertical direction. In this paper we introduce and study the concept of quasi-upward planarity. Quasi-upward planarity allows us to extend the upward planarity theory to a large class of digraphs including digraphs that also have directed cycles. First, we characterize the digraphs that have a quasi-upward planar drawing. Second, we give a polynomial time algorithm for computing ``optimal'' quasi-upward planar drawings within a given planar embedding. Further, we apply branch and bound techniques to the problem of computing optimal quasi-upward planar drawings, considering all possible planar embeddings. The paper also contains experimental results about the proposed techniques.     

Recurrent averaging inequalities in multi-agent control and social dynamics modeling

Many multi-agent control algorithms and dynamic agent-based models arising in natural and social sciences are based on the principle of iterative averaging. Each agent is associated to a value of interest, which may represent, for instance, the opinion of an individual in a social group, the velocity vector of a mobile robot in a flock, or the measurement of a sensor within a sensor network. This value is updated, at each iteration, to a weighted average of itself and of the values of the adjacent agents. It is well known that, under natural assumptions on the network’s graph connectivity, this local averaging procedure eventually leads to global consensus, or synchronization of the values at all nodes. Applications of iterative averaging include, but are not limited to, algorithms for distributed optimization, for solution of linear and nonlinear equations, for multi-robot coordination and for opinion formation in social groups. Although these algorithms have similar structures, the mathematical techniques used for their analysis are diverse, and conditions for their convergence and differ from case to case. In this paper, we review many of these algorithms and we show that their properties can be analyzed in a unified way by using a novel tool based on recurrent averaging inequalities (RAIs). We develop a theory of RAIs and apply it to the analysis of several important multi-agent algorithms recently proposed in the literature.     

Discrete abstractions for robot motion planning and control in polygonal environments

In this paper, we present a computational framework for automatic generation of provably correct control laws for planar robots in polygonal environments. Using polygon triangulation and discrete abstractions, we map continuous motion planning and control problems, specified in terms of triangles, to computationally inexpensive problems on finite-state-transition systems. In this framework, discrete planning algorithms in complex environments can be seamlessly linked to automatic generation of feedback control laws for robots with underactuation constraints and control bounds. We focus on fully actuated kinematic robots with velocity bounds and (underactuated) unicycles with forward and turning speed bounds.     

Quasi-Upward Planarity

Abstract. An upward planar drawing of a directed graph (digraph) is a planar drawing such that all the edges are represented by curves monotonically increasing in the vertical direction. In this paper we introduce and study the concept of quasi-upward planarity. Quasi-upward planarity allows us to extend the upward planarity theory to a large class of digraphs including digraphs that also have directed cycles. First, we characterize the digraphs that have a quasi-upward planar drawing. Second, we give a polynomial time algorithm for computing ``optimal' quasi-upward planar drawings within a given planar embedding. Further, we apply branch and bound techniques to the problem of computing optimal quasi-upward planar drawings, considering all possible planar embeddings. The paper also contains experimental results about the proposed techniques.     

Free lunches on the discrete Lipschitz class

The No-Free-Lunch theorem states that there does not exist a genuine general-purpose optimizer because all algorithms have the identical performance on average over all functions. However, such a result does not imply that search heuristics or optimization algorithms are futile if we are more cautious with the applicability of these methods and the search space. In this paper, within the No-Free-Lunch framework, we firstly introduce the discrete Lipschitz class by transferring the Lipschitz functions, i.e., functions with bounded slope, as a measure to fulfill the notion of continuity in discrete functions. We then investigate the properties of the discrete Lipschitz class, generalize an algorithm called subthreshold-seeker for optimization, and show that the generalized subthreshold-seeker outperforms random search on this class. Finally, we propose a tractable sampling-test scheme to empirically demonstrate the superiority of the generalized subthreshold-seeker under practical configurations. This study concludes that there exist algorithms outperforming random search on the discrete Lipschitz class in both theoretical and practical aspects and indicates that the effectiveness of search heuristics may not be universal but still general in some broad sense.     

Constant Width Planar Computation Characterizes ACC0

We obtain a characterization of ACC⁰ in terms of a natural class of constant width circuits, namely in terms of constant width polynomial size planar circuits. This is shown via a characterization of the class of acyclic digraphs which can be embedded on a cylinder surface in such a way that all arcs flow along the same direction of the axis of the cylinder.     

Decentralized and adaptive control of multiple nonholonomic robots for sensing coverage

This work deals with decentralized control of multiple nonholonomic mobile sensors for optimal coverage of a given area for sensing purposes. We assume a density function over the region to be covered, which can be viewed as a probability density of the phenomena to be sensed. The density function is unknown but assumed to be linearly parameterized with unknown parameter weights. We consider a second‐order dynamic model for the mobile agents and derive decentralized adaptive control laws to achieve optimal coverage of the region. We then consider the case where the dynamic model of the agents are not fully known, and then develop parameter adaptation laws to achieve the optimal coverage objective. We test the derived algorithms using simulations and compare our proposed controllers with kinematics‐based controllers. We find that the feedback control design based on the dynamic model performs significantly better than controllers solely relying on kinematic models. Furthermore, for the unknown dynamics case, our controller outperforms the nonadaptive controller with poor initial parameter estimates.     

Quantized consensus

We study the distributed averaging problem on arbitrary connected graphs, with the additional constraint that the value at each node is an integer. This discretized distributed averaging problem models several problems of interest, such as averaging in a network with finite capacity channels and load balancing in a processor network.We describe simple randomized distributed algorithms which achieve consensus to the extent that the discrete nature of the problem permits. We give bounds on the convergence time of these algorithms for fully connected networks and linear networks.