23 March 2016 in IEEE Transactions on Automatic Control
In this technical note, we study the controllability of diffusively coupled networks from a graph theoretic perspective. We consider leader-follower networks, where the external control inputs are injected to only some of the agents, namely the leaders. Our main result relates the controllability of such systems to the graph distances between the agents. More specifically, we present a graph topological lower bound on the rank of the controllability matrix. This lower bound is tight, and it is applicable to systems with arbitrary network topologies, coupling weights, and number of leaders. An algorithm for computing the lower bound is also provided. Furthermore, as a prominent application, we present how the proposed bound can be utilized to select a minimal set of leaders for achieving controllability, even when the coupling weights are unknown.
31 January 2022 in IEEE Robotics and Automation Letters
We consider persistent (long-horizon) surveillance over an environment by using energy-constrained unmanned aerial vehicles (UAVs), which are supported by unmanned ground vehicles (UGVs) serving as mobile charging stations. The goal is to periodically visit a set of monitoring points by the UAVs while minimizing the maximum time between the consecutive visits to any of those points. In general, the optimal planning of UAVs and UGVs in such a persistent surveillance scenario is an NP-hard combinatorial optimization problem. Furthermore, the problem also demands a solution strategy that can successfully handle obstacles, especially on the ground, that are unknown a priori in many real-life scenarios. We present a scalable and robust approximate algorithm that is based on 1) forming uniform UAV-UGV teams, 2) decomposing the environment into maximal partitions that can be covered by the UAVs in a single fuel cycle as long as the UAVs are released sufficiently close to the centers of the partitions, 3) maintaining the teams uniformly distributed over a cyclic path traversing those partitions, and 4) having the UAVs in each team cover their current partition and be transported to the next partition while being recharged by the UGV. We support our proposed algorithm with some theoretical results and simulations.
3 February 2021 in IEEE Robotics and Automation Letters
We address the problem of coordinating the trajectories of heterogeneous multi-agent systems under spatio-temporal specifications. In particular, we consider global Signal Temporal Logic (STL) constraints to express the number and type of agents that should be present at specific locations within the desired time windows. We also introduce an integral predicate to specify cumulative progress that can be achieved asynchronously by multiple agents. In order to generate optimal trajectories, we formulate a mixed-integer linear program whose objective is minimizing the agent movement subject to the heterogeneous dynamics of the agents and a global STL specification including the novel integral predicate. We demonstrate the performance of the proposed method via simulations and experiments with drones.
25 November 2015 in IEEE Transactions on Network Science and Engineering
Multi-agent networks are often modeled as interaction graphs, where the nodes represent the agents and the edges denote some direct interactions. The robustness of a multi-agent network to perturbations such as failures, noise, or malicious attacks largely depends on the corresponding graph. In many applications, networks are desired to have well-connected interaction graphs with relatively small number of links. One family of such graphs is the random regular graphs. In this paper, we present a decentralized scheme for transforming any connected interaction graph with a possibly non-integer average degree of k into a connected random m-regular graph for some m E [k; k + 2]. Accordingly, the agents improve the robustness of the network while maintaining a similar number of links as the initial configuration by locally adding or removing some edges.
11 December 2017 in IEEE Transactions on Control of Network Systems
We investigate the use of variable speed limits for resilient operation of transportation networks, which are modeled as dynamical flow networks under local routing decisions. In such systems, some external inflow is injected to the so-called origin nodes of the network. The total inflow arriving at each node is routed to its operational outgoing links based on their current densities of traffic. The density on each link has first order dynamics driven by the difference of its incoming and outgoing flows. A link fails if it reaches its jam density. Such failures may propagate in the network and cause a systemic failure. We show that larger link capacities, i.e., the maximum flows that can be sustained by the links, are not always better for preventing systemic failures under local routing. Accordingly, we propose the use of variable speed limits to operate the links below their capacities, when necessary, to compensate for the lack of global information and coordination in routing decisions. We show that systemic failures under feasible external inflows can always be averted through a proper selection of speed limits if the routing decisions are sufficiently responsive to local congestion and the network is initially uncongested. This is an attractive feature as it provides a practical alternative to building more physical capacity or altering routing decisions that are determined by social behavior.
24 July 2020 in IEEE Transactions on Control of Network Systems
In this paper, we demonstrate that there is a conflicting relation between two crucial properties—controllability and robustness—in linear dynamical networks of diffusively coupled agents. In particular, for any given number of nodes N and diameter D, we identify networks that are maximally robust using the notion of Kirchhoff index and then analyze their strong structural controllability by computing the minimum number of leaders (nodes receiving external control inputs) needed to make such networks controllable under all feasible coupling weights. Then, for any N and D, we obtain a sharp upper bound on the minimum number of leaders needed to design strong structurally controllable networks with N nodes and diameter D. We also discuss that the bound is best possible for arbitrary values of N and D. Moreover, we construct a family of graphs for any N and D such that the graphs have maximal edge sets while being strong structurally controllable with a number of leaders in the proposed bound. We then analyze the robustness of this graph family. The results suggest that optimizing robustness increases the number of leaders needed for strong structural controllability.