More Like this

1. End-to-end decentralized formation control using a graph neural network-based learning method

   https://doi.org/10.3389/frobt.2023.1285412  

   Jiang, Chao; Huang, Xinchi; Guo, Yi (November 2023, Frontiers in Robotics and AI)

   Multi-robot cooperative control has been extensively studied using model-based distributed control methods. However, such control methods rely on sensing and perception modules in a sequential pipeline design, and the separation of perception and controls may cause processing latencies and compounding errors that affect control performance. End-to-end learning overcomes this limitation by implementing direct learning from onboard sensing data, with control commands output to the robots. Challenges exist in end-to-end learning for multi-robot cooperative control, and previous results are not scalable. We propose in this article a novel decentralized cooperative control method for multi-robot formations using deep neural networks, in which inter-robot communication is modeled by a graph neural network (GNN). Our method takes LiDAR sensor data as input, and the control policy is learned from demonstrations that are provided by an expert controller for decentralized formation control. Although it is trained with a fixed number of robots, the learned control policy is scalable. Evaluation in a robot simulator demonstrates the triangular formation behavior of multi-robot teams of different sizes under the learned control policy. 

   more » « less
2. Argo: Architecture-aware graph partitioning

   https://doi.org/10.1109/BigData.2016.7840614  

   Zheng, Angen; Labrinidis, Alexandros; Chrysanthis, Panos K.; Lange, Jack (December 2016, 2016 IEEE International Conference on Big Data)

   The increasing popularity and ubiquity of various large graph datasets has caused renewed interest for graph partitioning. Existing graph partitioners either scale poorly against large graphs or disregard the impact of the underlying hardware topology. A few solutions have shown that the nonuniform network communication costs may affect the performance greatly. However, none of them considers the impact of resource contention on the memory subsystems (e.g., LLC and Memory Controller) of modern multicore clusters. They all neglect the fact that the bandwidth of modern high-speed networks (e.g., Infiniband) has become comparable to that of the memory subsystems. In this paper, we provide an in-depth analysis, both theoretically and experimentally, on the contention issue for distributed workloads. We found that the slowdown caused by the contention can be as high as 11x. We then design an architecture-aware graph partitioner, ARGO , to allow the full use of all cores of multicore machines without suffering from either the contention or the communication heterogeneity issue. Our experimental study showed (1) the effectiveness of ARGO , achieving up to 12x speedups on three classic workloads: Breadth First Search, Single Source Shortest Path, and PageRank; and (2) the scalability of ARGO in terms of both graph size and the number of partitions on two billion-edge real-world graphs. 

   more » « less
3. Distributed Graph Diameter Approximation

   https://doi.org/10.3390/a13090216  

   Ceccarello, Matteo; Pietracaprina, Andrea; Pucci, Geppino; Upfal, Eli (September 2020, Algorithms)

   null (Ed.)

   We present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the graph into disjoint clusters of bounded radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; most importantly, for a large family of graphs, it features a round complexity asymptotically smaller than the one exhibited by a natural approximation algorithm based on the state-of-the-art Δ-stepping SSSP algorithm, which is its only practical, linear-space competitor in the distributed setting. We complement our theoretical findings with a proof-of-concept experimental analysis on large benchmark graphs, which suggests that our algorithm may attain substantial improvements in terms of running time compared to the aforementioned competitor, while featuring, in practice, a similar approximation ratio. 

   more » « less
4. Graph Representation of Computer Network Resources for Precise Allocations

   https://doi.org/10.1109/ICCCN54977.2022.9868852  

   Baxley, Stuart; Gurkan, Deniz; Validi, Hamidreza; Hicks, Illya (July 2022, ICCCN)

   Distributed networked systems form an essential resource for computation and applications ranging from commercial, military, scientific, and research communities. Allocation of resources on a given infrastructure is realized through various mapping systems that are tailored towards specific use cases of the requesting applications. While HPC system requests demand compute resources heavy on processor and memory, cloud applications may demand distributed web services that are composed of networked processing and some memory. All resource requests allocate on the infrastructure with some form of network connectivity. However, during mapping of resources, the features and topology constraints of network components are typically handled indirectly through abstractions of user requests. This paper is on a novel graph representation that enables precise mapping methods for distributed networked systems. The proposed graph representations are demonstrated to allocate specific network components and adjacency requirements of a requested graph on a given infrastructure. Furthermore, we report on application of business policy requirements that resulted in increased utilization and a gradual decrease in idle node count as requests are mapped using our proposed methods. 

   more » « less
5. Stable motion and distributed topology control for multi-agent systems with directed interactions

   https://doi.org/10.1109/CDC.2017.8264165  

   Mukherjee, Pratik; Gasparri, Andrea; Williams, Ryan K. (December 2017, Decision and Control (CDC), 2017 IEEE 56th Annual Conference on)

   In this paper, we study stable coordination in multi- agent systems with directed interactions, and apply the results for distributed topology control. Our main contribution is to extend the well-known potential-based control framework orig- inally introduced for undirected networks to the case of net- works modeled by a directed graph. Regardless of the particular objective to be achieved, potential-based control for undirected graphs is intrinsically stable. Briefly, this can be explained by the positive semidefiniteness of the graph Laplacian induced by the symmetric nature of the interactions. Unfortunately, this energy finiteness guarantee no longer holds when a multi-agent system lacks symmetry in pairwise interactions. In this context, our contribution is twofold: i) we formalize stable coordination of multi-agent systems on directed graphs, demonstrating the graph structures that induce stability for a broad class of coordination objectives; and ii) we design a topology control mechanism based on a distributed eigenvalue estimation algorithm to enforce Lyapunov energy finiteness over the derived class of stable graphs. Simulation results demonstrate a multi-agent system on a directed graph performing topology control and collision avoidance, corroborating the theoretical findings. 

   more » « less