Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks

• URL: http://arxiv.org/abs/2407.10382v2
• Date: Fri, 31 Jan 2025 18:22:56 GMT
• Title: Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks
• Authors: Zirui Xu, Sandilya Sai Garimella, Vasileios Tzoumas,
• Abstract summary: We provide a communication- and computation-efficient method for distributed submodular optimization in robot mesh networks.<n>Our method, Resource-Aware distributed Greedy (RAG), introduces a new distributed optimization paradigm.<n>RAG's decision-time scales linearly with the network size, while state-of-the-art near-optimal submodular optimization algorithms scale cubically.
• Score: 2.8936428431504164
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide a communication- and computation-efficient method for distributed submodular optimization in robot mesh networks. Submodularity is a property of diminishing returns that arises in active information gathering such as mapping, surveillance, and target tracking. Our method, Resource-Aware distributed Greedy (RAG), introduces a new distributed optimization paradigm that enables scalable and near-optimal action coordination. To this end, RAG requires each robot to make decisions based only on information received from and about their neighbors. In contrast, the current paradigms allow the relay of information about all robots across the network. As a result, RAG's decision-time scales linearly with the network size, while state-of-the-art near-optimal submodular optimization algorithms scale cubically. We also characterize how the designed mesh-network topology affects RAG's approximation performance. Our analysis implies that sparser networks favor scalability without proportionally compromising approximation performance: while RAG's decision time scales linearly with network size, the gain in approximation performance scales sublinearly. We demonstrate RAG's performance in simulated scenarios of area detection with up to 45 robots, simulating realistic robot-to-robot (r2r) communication speeds such as the 0.25 Mbps speed of the Digi XBee 3 Zigbee 3.0. In the simulations, RAG enables real-time planning, up to three orders of magnitude faster than competitive near-optimal algorithms, while also achieving superior mean coverage performance. To enable the simulations, we extend the high-fidelity and photo-realistic simulator AirSim by integrating a scalable collaborative autonomy pipeline to tens of robots and simulating r2r communication delays. Our code is available at https://github.com/UM-iRaL/Resource-Aware-Coordination-AirSim.

Related papers

• DP-LET: An Efficient Spatio-Temporal Network Traffic Prediction Framework [13.65226228907662]
  DP-LET is an efficient feature-temporal network traffic prediction framework. DP-LET consists of a data processing module, a local feature enhancement module, and a Transformer-based prediction module. A real-world cellular traffic prediction demonstrates the practicality of DP-LET.
  arXiv  Detail & Related papers  (2025-04-04T02:52:43Z)
• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  Decentralized training faces significant challenges regarding system design and efficiency. We present FusionLLM, a decentralized training system designed and implemented for training large deep neural networks (DNNs) We show that our system and method can achieve 1.45 - 9.39x speedup compared to baseline methods while ensuring convergence.
  arXiv  Detail & Related papers  (2024-10-16T16:13:19Z)
• Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Design [3.5527561584422465]
  We present AlterNAting COordination and Network-Design Algorithm (Anaconda) Anaconda is a scalable algorithm that also enjoys near-optimality guarantees. We demonstrate in simulated scenarios of area monitoring and compare it with a state-of-the-art algorithm.
  arXiv  Detail & Related papers  (2024-09-02T18:11:33Z)
• Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
  This paper supports robotic parts-to-picker operations in warehousing by optimizing order-workstation assignments, item-pod assignments and the schedule of order fulfillment at workstations. We solve it via large-scale neighborhood search, with a novel learn-then-optimize approach to subproblem generation. In collaboration with Amazon Robotics, we show that our model and algorithm generate much stronger solutions for practical problems than state-of-the-art approaches.
  arXiv  Detail & Related papers  (2024-08-29T20:22:22Z)
• Automatic AI Model Selection for Wireless Systems: Online Learning via Digital Twinning [50.332027356848094]
  AI-based applications are deployed at intelligent controllers to carry out functionalities like scheduling or power control. The mapping between context and AI model parameters is ideally done in a zero-shot fashion. This paper introduces a general methodology for the online optimization of AMS mappings.
  arXiv  Detail & Related papers  (2024-06-22T11:17:50Z)
• Cellular Traffic Prediction Using Online Prediction Algorithms [5.416701003120508]
  This paper investigates the efficacy of live prediction algorithms for forecasting cellular network traffic in real-time scenarios. We apply two live prediction algorithms on machine learning models, one of which is recently proposed Fast LiveStream Prediction (FLSP) algorithm. Our study reveals that the FLSP algorithm can halve the required bandwidth for asynchronous data reporting compared to conventional online prediction algorithms.
  arXiv  Detail & Related papers  (2024-05-08T17:36:14Z)
• SIMPL: A Simple and Efficient Multi-agent Motion Prediction Baseline for Autonomous Driving [27.776472262857045]
  This paper presents a Simple and effIcient Motion Prediction baseLine (SIMPL) for autonomous vehicles. We propose a compact and efficient global feature fusion module that performs directed message passing in a symmetric manner. As a strong baseline, SIMPL exhibits highly competitive performance on Argoverse 1 & 2 motion forecasting benchmarks.
  arXiv  Detail & Related papers  (2024-02-04T15:07:49Z)
• Multi-agent Reinforcement Learning with Graph Q-Networks for Antenna Tuning [60.94661435297309]
  The scale of mobile networks makes it challenging to optimize antenna parameters using manual intervention or hand-engineered strategies. We propose a new multi-agent reinforcement learning algorithm to optimize mobile network configurations globally. We empirically demonstrate the performance of the algorithm on an antenna tilt tuning problem and a joint tilt and power control problem in a simulated environment.
  arXiv  Detail & Related papers  (2023-01-20T17:06:34Z)
• Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination [15.588080817106563]
  We are motivated by the future autonomy that involves multiple robots coordinating in dynamic, unstructured, and adversarial environments. We introduce the first submodular coordination algorithm with bounded tracking regret, ie., with bounded suboptimality with respect to optimal time-varying actions that know the future a priori. Our algorithm generalizes the seminal Sequential Greedy algorithm by Fisher et al. to unpredictable environments, leveraging submodularity and algorithms for the problem of tracking the best expert.
  arXiv  Detail & Related papers  (2022-09-26T05:31:34Z)
• Multi-Agent Reinforcement Learning for Long-Term Network Resource Allocation through Auction: a V2X Application [7.326507804995567]
  We formulate offloading of computational tasks from a dynamic group of mobile agents (e.g., cars) as decentralized decision making among autonomous agents. We design an interaction mechanism that incentivizes such agents to align private and system goals by balancing between competition and cooperation. We propose a novel multi-agent online learning algorithm that learns with partial, delayed and noisy state information.
  arXiv  Detail & Related papers  (2022-07-29T10:29:06Z)
• Intelligent Trajectory Design for RIS-NOMA aided Multi-robot Communications [59.34642007625687]
  The goal is to maximize the sum-rate of whole trajectories for multi-robot system by jointly optimizing trajectories and NOMA decoding orders of robots. An integrated machine learning (ML) scheme is proposed, which combines long short-term memory (LSTM)-autoregressive integrated moving average (ARIMA) model and dueling double deep Q-network (D$3$QN) algorithm.
  arXiv  Detail & Related papers  (2022-05-03T17:14:47Z)
• Online V2X Scheduling for Raw-Level Cooperative Perception [21.099819062731463]
  Cooperative perception of connected vehicles comes to the rescue when the field of view restricts stand-alone intelligence. We present a model of raw-level cooperative perception and formulate the energy minimization problem of sensor sharing scheduling. We propose an online learning-based algorithm with logarithmic performance loss, achieving a decent trade-off between exploration and exploitation.
  arXiv  Detail & Related papers  (2022-02-12T15:16:45Z)
• Parallel Successive Learning for Dynamic Distributed Model Training over Heterogeneous Wireless Networks [50.68446003616802]
  Federated learning (FedL) has emerged as a popular technique for distributing model training over a set of wireless devices. We develop parallel successive learning (PSL), which expands the FedL architecture along three dimensions. Our analysis sheds light on the notion of cold vs. warmed up models, and model inertia in distributed machine learning.
  arXiv  Detail & Related papers  (2022-02-07T05:11:01Z)
• An Adaptive Device-Edge Co-Inference Framework Based on Soft Actor-Critic [72.35307086274912]
  High-dimension parameter model and large-scale mathematical calculation restrict execution efficiency, especially for Internet of Things (IoT) devices. We propose a new Deep Reinforcement Learning (DRL)-Soft Actor Critic for discrete (SAC-d), which generates the emphexit point, emphexit point, and emphcompressing bits by soft policy iterations. Based on the latency and accuracy aware reward design, such an computation can well adapt to the complex environment like dynamic wireless channel and arbitrary processing, and is capable of supporting the 5G URL
  arXiv  Detail & Related papers  (2022-01-09T09:31:50Z)
• SABER: Data-Driven Motion Planner for Autonomously Navigating Heterogeneous Robots [112.2491765424719]
  We present an end-to-end online motion planning framework that uses a data-driven approach to navigate a heterogeneous robot team towards a global goal. We use model predictive control (SMPC) to calculate control inputs that satisfy robot dynamics, and consider uncertainty during obstacle avoidance with chance constraints. recurrent neural networks are used to provide a quick estimate of future state uncertainty considered in the SMPC finite-time horizon solution. A Deep Q-learning agent is employed to serve as a high-level path planner, providing the SMPC with target positions that move the robots towards a desired global goal.
  arXiv  Detail & Related papers  (2021-08-03T02:56:21Z)
• Graph Neural Networks for Decentralized Multi-Robot Submodular Action Selection [101.38634057635373]
  We focus on applications where robots are required to jointly select actions to maximize team submodular objectives. We propose a general-purpose learning architecture towards submodular at scale, with decentralized communications. We demonstrate the performance of our GNN-based learning approach in a scenario of active target coverage with large networks of robots.
  arXiv  Detail & Related papers  (2021-05-18T15:32:07Z)
• Learning Connectivity for Data Distribution in Robot Teams [96.39864514115136]
  We propose a task-agnostic, decentralized, low-latency method for data distribution in ad-hoc networks using Graph Neural Networks (GNN) Our approach enables multi-agent algorithms based on global state information to function by ensuring it is available at each robot. We train the distributed GNN communication policies via reinforcement learning using the average Age of Information as the reward function and show that it improves training stability compared to task-specific reward functions.
  arXiv  Detail & Related papers  (2021-03-08T21:48:55Z)
• Path Design and Resource Management for NOMA enhanced Indoor Intelligent Robots [58.980293789967575]
  A communication enabled indoor intelligent robots (IRs) service framework is proposed. Lego modeling method is proposed, which can deterministically describe the indoor layout and channel state. The investigated radio map is invoked as a virtual environment to train the reinforcement learning agent.
  arXiv  Detail & Related papers  (2020-11-23T21:45:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.