Dynamical structure function identifiability conditions enabling signal structure reconstruction

in The proceedings of the 51st IEEE Conference on Decision and Control (CDC) (2012, December)

Networks of controlled dynamical systems exhibit a variety of interconnection patterns that could be interpreted as the structure of the system. One such interpretation of system structure is a system's ... [more ▼]

Networks of controlled dynamical systems exhibit a variety of interconnection patterns that could be interpreted as the structure of the system. One such interpretation of system structure is a system's signal structure, characterized as the open-loop causal dependencies among manifest variables and represented by its dynamical structure function. Although this notion of structure is among the weakest available, previous work has shown that if no a priori structural information is known about the system, not even the Boolean structure of the dynamical structure function is identifiable. Consequently, one method previously suggested for obtaining the necessary a priori structural information is to leverage knowledge about target specificity of the controlled inputs. This work extends these results to demonstrate precisely the a priori structural information that is both necessary and sufficient to reconstruct the network from input-output data. This extension is important because it significantly broadens the applicability of the identifiability conditions, enabling the design of network reconstruction experiments that were previously impossible due to practical constraints on the types of actuation mechanisms available to the engineer or scientist. The work is motivated by the proteomics problem of reconstructing the Per-Arnt-Sim Kinase pathway used in the metabolism of sugars. [less ▲]

Decentralised minimal-time dynamic consensus

in The proceedings of the 2012 American Control Conference (ACC) (2012)

This paper considers a group of agents that aim to reach an agreement on individually measured time-varying signals by local communication. In contrast to static network averaging problem, the consensus ... [more ▼]

This paper considers a group of agents that aim to reach an agreement on individually measured time-varying signals by local communication. In contrast to static network averaging problem, the consensus we mean in this paper is reached in a dynamic sense. A discrete-time dynamic average consensus protocol can be designed to allow all the agents tracking the average of their reference inputs asymptotically. We propose a minimal-time dynamic consensus algorithm, which only utilises minimal number of local observations of randomly picked node in a network to compute the final consensus signal. Our results illustrate that with memory and computational ability, the running time of distributed averaging algorithms can be indeed improved dramatically using local information as suggested by Olshevsky and Tsitsiklis. [less ▲]

Decentralised minimal-time consensus

in The proceedings of the 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC) (2011)

This study considers the discrete-time dynamics of a network of agents that exchange information according to the nearest-neighbour protocol under which all agents are guaranteed to reach consensus ... [more ▼]

This study considers the discrete-time dynamics of a network of agents that exchange information according to the nearest-neighbour protocol under which all agents are guaranteed to reach consensus asymptotically. We present a fully decentralised algorithm that allows any agent to compute the consensus value of the whole network in finite time using only the minimal number of successive values of its own history. We show that this minimal number of steps is related to a Jordan block decomposition of the network dynamics and present an algorithm to obtain the minimal number of steps in question by checking a rank condition on a Hankel matrix of the local observations. Furthermore, we prove that the minimal number of steps is related to other algebraic and graph theoretical notions that can be directly computed from the Laplacian matrix of the graph and from the underlying graph topology. [less ▲]

Robust dynamical network structure reconstruction

Scientific Conference (2010)

Motivated by biological applications, this paper addresses the problem of network reconstruction from data. Previous work has shown necessary and sufficient conditions for network reconstruction of noise ... [more ▼]

Motivated by biological applications, this paper addresses the problem of network reconstruction from data. Previous work has shown necessary and sufficient conditions for network reconstruction of noise-free LTI systems. This paper assumes that the conditions for network reconstruction have been met but here we additionally take into account noise and unmodelled dynamics (including nonlinearities). Algorithms are therefore proposed to reconstruct dynamical (Boolean) network structure from time-series (steady-state) data respectively in presence of noise and nonlinearities. In order to identify the network structure that generated the data, we compute the smallest distances between the measured data and the data that would have been generated by particular Boolean structures. Information criteria and optimisation technique balancing such distance and model complexity are introduced to search for the true structure. We conclude with biologically-inspired network reconstruction examples which include noise and nonlinearities. [less ▲]

Minimal-time network reconstruction for DTLTI systems

in The proceedings of the 49th IEEE Conference on Decision and Control (CDC) (2010)

This paper considers the problem of obtaining in minimal time the “dynamical network structure” (DNS) from partial state observations of a discrete-time linear time-invariant system. From the DNS, we can ... [more ▼]

This paper considers the problem of obtaining in minimal time the “dynamical network structure” (DNS) from partial state observations of a discrete-time linear time-invariant system. From the DNS, we can not only obtain the network structure of the system at the measurement level, but also estimate the minimal number of hidden states which are not observed directly. First, we discuss when reconstruction of the DNS is and is not possible. Then, we give an algorithm to find the minimal number of successive outputs to find the DNS. Finally, we discuss extensions of the results to non-linear and noisy systems. These results can be directly applied to the decentralised network control problem of multi-agent systems to find network connections of the observed agents. [less ▲]

Decentralized final value theorem for discrete-time LTI systems with application to minimal time distributed consensus

in The proceedings of the Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference (2009)

In this study, we consider an unknown discrete-time, linear time-invariant, autonomous system and characterise, the minimal number of discrete-time steps necessary to compute the asymptotic final value of ... [more ▼]

In this study, we consider an unknown discrete-time, linear time-invariant, autonomous system and characterise, the minimal number of discrete-time steps necessary to compute the asymptotic final value of a state. The results presented in this paper have a direct link with the celebrated final value theorem. We apply these results to the design of an algorithm for minimal-time distributed consensus and illustrate the results on an example. [less ▲]