Browsing by Author "Zhou, Lifeng"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Parsimonious, Risk-Aware, and Resilient Multi-Robot Coordination
    Zhou, Lifeng (Virginia Tech, 2020-05-28)
    In this dissertation, we study multi-robot coordination in the context of multi-target tracking. Specifically, we are interested in the coordination achieved by means of submodular function optimization. Submodularity encodes the diminishing returns property that arises in multi-robot coordination. For example, the marginal gain of assigning an additional robot to track the same target diminishes as the number of robots assigned increases. The advantage of formulating coordination problems as submodular optimization is that a simple, greedy algorithm is guaranteed to give a good performance. However, often this comes at the expense of unrealistic models and assumptions. For example, the standard formulation does not take into account the fact that robots may fail, either randomly or due to adversarial attacks. When operating in uncertain conditions, we typically seek to optimize the expected performance. However, this does not give any flexibility for a user to seek conservative or aggressive behaviors from the team of robots. Furthermore, most coordination algorithms force robots to communicate at each time step, even though they may not need to. Our goal in this dissertation is to overcome these limitations by devising coordination algorithms that are parsimonious in communication, allow a user to manage the risk of the robot performance, and are resilient to worst-case robot failures and attacks. In the first part of this dissertation, we focus on designing parsimonious communication strategies for target tracking. Specifically, we investigate the problem of determining when to communicate and who to communicate with. When the robots use range sensors, the tracking performance is a function of the relative positions of the robots and the targets. We propose a self-triggered communication strategy in which a robot communicates its own position with its neighbors only when a certain set of conditions are violated. We prove that this strategy converges to the optimal robot positions for tracking a single target and in practice, reduces the number of communication messages by 30%. When tracking multiple targets, we can reduce the communication by forming subsets of robots and assigning one subset to track a target. We investigate a number of measures for tracking quality based on the observability matrix and show which ones are submodular and which ones are not. For non-submodular measures, we show a greedy algorithm gives a 1/(n+1) approximation, if we restrict the subset to n robots. In optimizing submodular functions, a common assumption is that the function value is deterministic, which may not hold in practice. For example, the sensor performance may depend on environmental conditions which are not known exactly. In the second part of the dissertation, we design an algorithm for stochastic submodular optimization. The standard formulation for stochastic optimization optimizes the expected performance. However, the expectation is a risk-neutral measure. Instead, we optimize the Conditional Value-at-Risk (CVaR), which allows the user the flexibility of choosing a risk level. We present an algorithm, based on the greedy algorithm, and prove that its performance has bounded suboptimality and improves with running time. We also present an online version of the algorithm to adapt to real-time scenarios. In the third part of this dissertation, we focus on scenarios where a set of robots may fail naturally or due to adversarial attacks. Our objective is to track as many targets as possible, a submodular measure, assuming worst-case robot failures. We present both centralized and distributed resilient tracking algorithms to cope with centralized and distributed communication settings. We prove these algorithms give a constant-factor approximation of the optimal in polynomial running time.
  • Thumbnail Image
    Spatial Temporal Graph Neural Networks for Decentralized Control of Robot Swarms
    Chen, Siji; Sun, Yanshen; Li, Peihan; Zhou, Lifeng; Lu, Chang-Tien (ACM, 2023-11-13)
    Recent research has explored the use of graph neural networks (GNNs) for decentralized control in swarm robotics. However, it has been observed that relying solely on local states is insufficient to imitate a centralized control policy. To address this limitation, previous studies proposed incorporating đŸ-hop delayed states into the computation. While this approach shows promise, it can lead to a lack of consensus among distant flock members and the formation of small localized groups, ultimately resulting in task failure. Our approach is to include the delayed states to build a spatiotemporal GNN model (ST-GNN) by two levels of expansion: spatial expansion and temporal expansion. The spatial expansion utilizes đŸ-hop delayed states to broaden the network while temporal expansion, can effectively predict the trend of swarm behavior, making it more robust against local noise. To validate the effectiveness of our approach, we conducted simulations in two distinct scenarios: free flocking and flocking with a leader. In both scenarios, the simulation results demonstrated that our decentralized ST-GNN approach successfully overcomes the limitations of local controllers. We performed a comprehensive analysis on the effectiveness of spatial expansions and temporal expansions independently. The results clearly demonstrate that both significantly improve overall performance. Furthermore, when combined, they achieve the best performance compared to global solution and delayed states solutions. The performance of ST-GNN underscores its potential as an effective and reliable approach for achieving cohesive flocking behavior while ensuring safety and maintaining desired swarm characteristics.