Guodong Shi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Guodong Shi has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Karl Henrik Johansson
KTH Royal Institute of Technology
13 shared publications - Yiguang Hong
Department of Control Science and Engineering, Tongji University, Shanghai, China
5 shared publications - Mikael Johansson
Division of Decision and Control Systems KTH Royal Institute of Technology Stockholm Sweden
4 shared publications - Alexandre Proutiere
School of EECS KTH Stockholm Sweden
3 shared publications - Youcheng Lou
Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
3 shared publications Amir Payberah
Swedish Institute of Computer Science (SICS) 1 1 3 3 3 2 2 2
1 shared publication
Latest Publications
- Open Access
Cooperative Set Aggregation for Multiple Lagrangian Systems
In this paper, we study the cooperative set tracking problem for a group of Lagrangian systems. Each system observes a convex set as its local target. The intersection of these local sets is the group aggregation target. We first propose a control law based on each system's own target sensing and information exchange with neighbors. With necessary connectivity for both cases of fixed and switching communication graphs, multiple Lagrangian systems are shown to achieve rendezvous on the intersection of all the local target sets while the vectors of generalized coordinate derivatives are driven to zero. Then, we introduce the collision avoidance control term into set aggregation control to ensure group dispersion. By defining an ultimate bound on the final generalized coordinate between each system and the intersection of all the local target sets, we show that multiple Lagrangian systems approach a bounded region near the intersection of all the local target sets while the collision avoidance is guaranteed during the movement. In addition, the vectors of generalized coordinate derivatives of all the mechanical systems are shown to be driven to zero. Simulation results are given to validate the theoretical results.
Open AccessCooperative Set Aggregation for Multiple Lagrangian Systems
In this paper, we study the cooperative set tracking problem for a group of Lagrangian systems. Each system observes a convex set as its local target. The intersection of these local sets is the group aggregation target. We first propose a control law based on each system's own target sensing and information exchange with neighbors. With necessary connectivity for both cases of fixed and switching communication graphs, multiple Lagrangian systems are shown to achieve rendezvous on the intersection of all the local target sets while the vectors of generalized coordinate derivatives are driven to zero. Then, we introduce the collision avoidance control term into set aggregation control to ensure group dispersion. By defining an ultimate bound on the final generalized coordinate between each system and the intersection of all the local target sets, we show that multiple Lagrangian systems approach a bounded region near the intersection of all the local target sets while the collision avoidance is guaranteed during the movement. In addition, the vectors of generalized coordinate derivatives of all the mechanical systems are shown to be driven to zero. Simulation results are given to validate the theoretical results.
- 1 December 2013
- Published by Elsevier in Systems & Control Letters
- Vol. 62 (12) , 1196-1202
Convergence of random sleep algorithms for optimal consensus
- 1 December 2013
- Published by Elsevier in Systems & Control Letters
- Vol. 62 (12) , 1196-1202
Convergence of random sleep algorithms for optimal consensus
- Open Access
Emergent Behaviors over Signed Random Networks in Dynamical Environments
We study asymptotic dynamical patterns that emerge among a set of nodes that interact in a dynamically evolving signed random network. Node interactions take place at random on a sequence of deterministic signed graphs. Each node receives positive or negative recommendations from its neighbors depending on the sign of the interaction arcs, and updates its state accordingly. Positive recommendations follow the standard consensus update while two types of negative recommendations, each modeling a different type of antagonistic or malicious interaction, are considered. Nodes may weigh positive and negative recommendations differently, and random processes are introduced to model the time-varying attention that nodes pay to the positive and negative recommendations. Various conditions for almost sure convergence, divergence, and clustering of the node states are established. Some fundamental similarities and differences are established for the two notions of negative recommendations.
Open AccessEmergent Behaviors over Signed Random Networks in Dynamical Environments
We study asymptotic dynamical patterns that emerge among a set of nodes that interact in a dynamically evolving signed random network. Node interactions take place at random on a sequence of deterministic signed graphs. Each node receives positive or negative recommendations from its neighbors depending on the sign of the interaction arcs, and updates its state accordingly. Positive recommendations follow the standard consensus update while two types of negative recommendations, each modeling a different type of antagonistic or malicious interaction, are considered. Nodes may weigh positive and negative recommendations differently, and random processes are introduced to model the time-varying attention that nodes pay to the positive and negative recommendations. Various conditions for almost sure convergence, divergence, and clustering of the node states are established. Some fundamental similarities and differences are established for the two notions of negative recommendations.
- Open Access
Randomized Consensus with Attractive and Repulsive Links
We study convergence properties of a randomized consensus algorithm over a graph with both attractive and repulsive links. At each time instant, a node is randomly selected to interact with a random neighbor. Depending on if the link between the two nodes belongs to a given subgraph of attractive or repulsive links, the node update follows a standard attractive weighted average or a repulsive weighted average, respectively. The repulsive update has the opposite sign of the standard consensus update. In this way, it counteracts the consensus formation and can be seen as a model of link faults or malicious attacks in a communication network, or the impact of trust and antagonism in a social network. Various probabilistic convergence and divergence conditions are established. A threshold condition for the strength of the repulsive action is given for convergence in expectation: when the repulsive weight crosses this threshold value, the algorithm transits from convergence to divergence. An explicit value of the threshold is derived for classes of attractive and repulsive graphs. The results show that a single repulsive link can sometimes drastically change the behavior of the consensus algorithm. They also explicitly show how the robustness of the consensus algorithm depends on the size and other properties of the graphs.
Open AccessRandomized Consensus with Attractive and Repulsive Links
We study convergence properties of a randomized consensus algorithm over a graph with both attractive and repulsive links. At each time instant, a node is randomly selected to interact with a random neighbor. Depending on if the link between the two nodes belongs to a given subgraph of attractive or repulsive links, the node update follows a standard attractive weighted average or a repulsive weighted average, respectively. The repulsive update has the opposite sign of the standard consensus update. In this way, it counteracts the consensus formation and can be seen as a model of link faults or malicious attacks in a communication network, or the impact of trust and antagonism in a social network. Various probabilistic convergence and divergence conditions are established. A threshold condition for the strength of the repulsive action is given for convergence in expectation: when the repulsive weight crosses this threshold value, the algorithm transits from convergence to divergence. An explicit value of the threshold is derived for classes of attractive and repulsive graphs. The results show that a single repulsive link can sometimes drastically change the behavior of the consensus algorithm. They also explicitly show how the robustness of the consensus algorithm depends on the size and other properties of the graphs.
- 17 May 2013
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 31 (6) , 1061-1071
How Agreement and Disagreement Evolve over Random Dynamic Networks
The dynamics of an agreement protocol interacting with a disagreement process over a common random network is considered. The model can represent the spreading of true and false information over a communication network, the propagation of faults in a large-scale control system, or the development of trust and mistrust in a society. At each time instance and with a given probability, a pair of network nodes interact. At random each of the nodes then updates its state towards the state of the other node (attraction), away from the other node (repulsion), or sticks to its current state (neglect). Agreement convergence and disagreement divergence results are obtained for various strengths of the updates for both symmetric and asymmetric update rules. Impossibility theorems show that a specific level of attraction is required for almost sure asymptotic agreement and a specific level of repulsion is required for almost sure asymptotic disagreement. A series of sufficient and/or necessary conditions are then established for agreement convergence or disagreement divergence. In particular, under symmetric updates, a critical convergence measure in the attraction and repulsion update strength is found, in the sense that the asymptotic property of the network state evolution transits from agreement convergence to disagreement divergence when this measure goes from negative to positive. The result can be interpreted as a tight bound on how much bad action needs to be injected in a dynamic network in order to consistently steer its overall behavior away from consensus.
- 17 May 2013
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 31 (6) , 1061-1071
How Agreement and Disagreement Evolve over Random Dynamic Networks
The dynamics of an agreement protocol interacting with a disagreement process over a common random network is considered. The model can represent the spreading of true and false information over a communication network, the propagation of faults in a large-scale control system, or the development of trust and mistrust in a society. At each time instance and with a given probability, a pair of network nodes interact. At random each of the nodes then updates its state towards the state of the other node (attraction), away from the other node (repulsion), or sticks to its current state (neglect). Agreement convergence and disagreement divergence results are obtained for various strengths of the updates for both symmetric and asymmetric update rules. Impossibility theorems show that a specific level of attraction is required for almost sure asymptotic agreement and a specific level of repulsion is required for almost sure asymptotic disagreement. A series of sufficient and/or necessary conditions are then established for agreement convergence or disagreement divergence. In particular, under symmetric updates, a critical convergence measure in the attraction and repulsion update strength is found, in the sense that the asymptotic property of the network state evolution transits from agreement convergence to disagreement divergence when this measure goes from negative to positive. The result can be interpreted as a tight bound on how much bad action needs to be injected in a dynamic network in order to consistently steer its overall behavior away from consensus.
- Open Access
Distributed Optimization: Convergence Conditions from a Dynamical System Perspective
This paper explores the fundamental properties of distributed minimization of a sum of functions with each function only known to one node, and a pre-specified level of node knowledge and computational capacity. We define the optimization information each node receives from its objective function, the neighboring information each node receives from its neighbors, and the computational capacity each node can take advantage of in controlling its state. It is proven that there exist a neighboring information way and a control law that guarantee global optimal consensus if and only if the solution sets of the local objective functions admit a nonempty intersection set for fixed strongly connected graphs. Then we show that for any tolerated error, we can find a control law that guarantees global optimal consensus within this error for fixed, bidirectional, and connected graphs under mild conditions. For time-varying graphs, we show that optimal consensus can always be achieved as long as the graph is uniformly jointly strongly connected and the nonempty intersection condition holds. The results illustrate that nonempty intersection for the local optimal solution sets is a critical condition for successful distributed optimization for a large class of algorithms.
Open AccessDistributed Optimization: Convergence Conditions from a Dynamical System Perspective
This paper explores the fundamental properties of distributed minimization of a sum of functions with each function only known to one node, and a pre-specified level of node knowledge and computational capacity. We define the optimization information each node receives from its objective function, the neighboring information each node receives from its neighbors, and the computational capacity each node can take advantage of in controlling its state. It is proven that there exist a neighboring information way and a control law that guarantee global optimal consensus if and only if the solution sets of the local objective functions admit a nonempty intersection set for fixed strongly connected graphs. Then we show that for any tolerated error, we can find a control law that guarantees global optimal consensus within this error for fixed, bidirectional, and connected graphs under mild conditions. For time-varying graphs, we show that optimal consensus can always be achieved as long as the graph is uniformly jointly strongly connected and the nonempty intersection condition holds. The results illustrate that nonempty intersection for the local optimal solution sets is a critical condition for successful distributed optimization for a large class of algorithms.
- 14 June 2012
- Published by Springer Nature in Journal of Systems Science and Complexity
- Vol. 25 (3) , 430-440
Target aggregation of second-order multi-agent systems with switching interconnection
- 14 June 2012
- Published by Springer Nature in Journal of Systems Science and Complexity
- Vol. 25 (3) , 430-440
Target aggregation of second-order multi-agent systems with switching interconnection
- Open Access
An Approximate Projected Consensus Algorithm for Computing Intersection of Convex Sets
In this paper, we propose an approximate projected consensus algorithm for a network to cooperatively compute the intersection of convex sets. Instead of assuming the exact convex projection proposed in the literature, we allow each node to compute an approximate projection and communicate it to its neighbors. The communication graph is directed and time-varying. Nodes update their states by weighted averaging. Projection accuracy conditions are presented for the considered algorithm. They indicate how much projection accuracy is required to ensure global consensus to a point in the intersection set when the communication graph is uniformly jointly strongly connected. We show that $\pi/4$ is a critical angle error of the projection approximation to ensure a bounded state. A numerical example indicates that this approximate projected consensus algorithm may achieve better performance than the exact projected consensus algorithm in some cases.Open AccessAn Approximate Projected Consensus Algorithm for Computing Intersection of Convex Sets
In this paper, we propose an approximate projected consensus algorithm for a network to cooperatively compute the intersection of convex sets. Instead of assuming the exact convex projection proposed in the literature, we allow each node to compute an approximate projection and communicate it to its neighbors. The communication graph is directed and time-varying. Nodes update their states by weighted averaging. Projection accuracy conditions are presented for the considered algorithm. They indicate how much projection accuracy is required to ensure global consensus to a point in the intersection set when the communication graph is uniformly jointly strongly connected. We show that $\pi/4$ is a critical angle error of the projection approximation to ensure a bounded state. A numerical example indicates that this approximate projected consensus algorithm may achieve better performance than the exact projected consensus algorithm in some cases. - Open Access
Randomized Gossip Algorithm with Unreliable Communication
In this paper, we study an asynchronous randomized gossip algorithm under unreliable communication. At each instance, two nodes are selected to meet with a given probability. When nodes meet, two unreliable communication links are established with communication in each direction succeeding with a time-varying probability. It is shown that two particularly interesting cases arise when these communication processes are either perfectly dependent or independent. Necessary and sufficient conditions on the success probability sequence are proposed to ensure almost sure consensus or $\epsilon$-consensus. Weak connectivity is required when the communication is perfectly dependent, while double connectivity is required when the communication is independent. Moreover, it is proven that with odd number of nodes, average preserving turns from almost forever (with probability one for all initial conditions) for perfectly dependent communication, to almost never (with probability zero for almost all initial conditions) for the independent case. This average preserving property does not hold true for general number of nodes. These results indicate the fundamental role the node interactions have in randomized gossip algorithms.
Open AccessRandomized Gossip Algorithm with Unreliable Communication
In this paper, we study an asynchronous randomized gossip algorithm under unreliable communication. At each instance, two nodes are selected to meet with a given probability. When nodes meet, two unreliable communication links are established with communication in each direction succeeding with a time-varying probability. It is shown that two particularly interesting cases arise when these communication processes are either perfectly dependent or independent. Necessary and sufficient conditions on the success probability sequence are proposed to ensure almost sure consensus or $\epsilon$-consensus. Weak connectivity is required when the communication is perfectly dependent, while double connectivity is required when the communication is independent. Moreover, it is proven that with odd number of nodes, average preserving turns from almost forever (with probability one for all initial conditions) for perfectly dependent communication, to almost never (with probability zero for almost all initial conditions) for the independent case. This average preserving property does not hold true for general number of nodes. These results indicate the fundamental role the node interactions have in randomized gossip algorithms.
- Open Access
The Role of Persistent Graphs in the Agreement Seeking of Social Networks
This paper investigates the role persistent arcs play for a social network to reach a global belief agreement under discrete-time or continuous-time evolution. Each (directed) arc in the underlying communication graph is assumed to be associated with a time-dependent weight function which describes the strength of the information flow from one node to another. An arc is said to be persistent if its weight function has infinite $\mathscr{L}_1$ or $\ell_1$ norm for continuous-time or discrete-time belief evolutions, respectively. The graph that consists of all persistent arcs is called the persistent graph of the underlying network. Three necessary and sufficient conditions on agreement or $\epsilon$-agreement are established, by which we prove that the persistent graph fully determines the convergence to a common opinion in social networks. It is shown how the convergence rates explicitly depend on the diameter of the persistent graph. The results adds to the understanding of the fundamentals behind global agreements, as it is only persistent arcs that contribute to the convergence.Open AccessThe Role of Persistent Graphs in the Agreement Seeking of Social Networks
This paper investigates the role persistent arcs play for a social network to reach a global belief agreement under discrete-time or continuous-time evolution. Each (directed) arc in the underlying communication graph is assumed to be associated with a time-dependent weight function which describes the strength of the information flow from one node to another. An arc is said to be persistent if its weight function has infinite $\mathscr{L}_1$ or $\ell_1$ norm for continuous-time or discrete-time belief evolutions, respectively. The graph that consists of all persistent arcs is called the persistent graph of the underlying network. Three necessary and sufficient conditions on agreement or $\epsilon$-agreement are established, by which we prove that the persistent graph fully determines the convergence to a common opinion in social networks. It is shown how the convergence rates explicitly depend on the diameter of the persistent graph. The results adds to the understanding of the fundamentals behind global agreements, as it is only persistent arcs that contribute to the convergence.