Planning Spatial Networks

• URL: http://arxiv.org/abs/2106.06768v1
• Date: Sat, 12 Jun 2021 13:01:11 GMT
• Title: Planning Spatial Networks
• Authors: Victor-Alexandru Darvariu, Stephen Hailes, Mirco Musolesi
• Abstract summary: We tackle the problem of goal-directed graph construction. Given a starting graph, a global objective function, and a budget of modifications, the aim is to find a set of edges whose addition to the graph maximally improves the objective. This problem emerges in many networks of great importance for society such as transportation and critical infrastructure networks.
• Score: 4.499055111059408
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We tackle the problem of goal-directed graph construction: given a starting graph, a global objective function (e.g., communication efficiency), and a budget of modifications, the aim is to find a set of edges whose addition to the graph maximally improves the objective. This problem emerges in many networks of great importance for society such as transportation and critical infrastructure networks. We identify two significant shortcomings with present methods. Firstly, they focus exclusively on network topology while ignoring spatial information; however, in many real-world networks, nodes are embedded in space, which yields different global objectives and governs the range and density of realizable connections. Secondly, existing RL methods scale poorly to large networks due to the high cost of training a model and the scaling factors of the action space and global objectives. In this work, we formulate the problem of goal-directed construction of spatial networks as a deterministic MDP. We adopt the Monte Carlo Tree Search framework for planning in this domain, prioritizing the optimality of final solutions over the speed of policy evaluation. We propose several improvements over the standard UCT algorithm for this family of problems, addressing their single-agent nature, the trade-off between the costs of edges and their contribution to the objective, and an action space linear in the number of nodes. We demonstrate the suitability of this approach for improving the global efficiency and attack resilience of a variety of synthetic and real-world networks, including Internet backbone networks and metro systems. We obtain 24% better solutions on average compared to UCT on the largest networks tested, and scalability superior to previous methods.

Related papers

• Generalizability of Graph Neural Networks for Decentralized Unlabeled Motion Planning [72.86540018081531]
  Unlabeled motion planning involves assigning a set of robots to target locations while ensuring collision avoidance. This problem forms an essential building block for multi-robot systems in applications such as exploration, surveillance, and transportation. We address this problem in a decentralized setting where each robot knows only the positions of its $k$-nearest robots and $k$-nearest targets.
  arXiv  Detail & Related papers  (2024-09-29T23:57:25Z)
• Network Interdiction Goes Neural [26.308933674471895]
  Network interdiction problems are optimization problems involving two players. One aims to solve an optimization problem on a network, while the other seeks to modify the network to thwart the first player's objectives.
  arXiv  Detail & Related papers  (2024-05-26T02:34:26Z)
• Hierarchical Multi-Marginal Optimal Transport for Network Alignment [52.206006379563306]
  Multi-network alignment is an essential prerequisite for joint learning on multiple networks. We propose a hierarchical multi-marginal optimal transport framework named HOT for multi-network alignment. Our proposed HOT achieves significant improvements over the state-of-the-art in both effectiveness and scalability.
  arXiv  Detail & Related papers  (2023-10-06T02:35:35Z)
• 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)
• Neighbor Auto-Grouping Graph Neural Networks for Handover Parameter Configuration in Cellular Network [47.29123145759976]
  We propose a learning-based framework for handover parameter configuration. First, we introduce a novel approach to imitate how the network responds to different network states and parameter values. During the parameter configuration stage, instead of solving the global optimization problem, we design a local multi-objective optimization strategy.
  arXiv  Detail & Related papers  (2022-12-29T18:51:36Z)
• DDCNet: Deep Dilated Convolutional Neural Network for Dense Prediction [0.0]
  A receptive field (ERF) and a higher resolution of spatial features within a network are essential for providing higher-resolution dense estimates. We present a systemic approach to design network architectures that can provide a larger receptive field while maintaining a higher spatial feature resolution.
  arXiv  Detail & Related papers  (2021-07-09T23:15:34Z)
• On Topology Optimization and Routing in Integrated Access and Backhaul Networks: A Genetic Algorithm-based Approach [70.85399600288737]
  We study the problem of topology optimization and routing in IAB networks. We develop efficient genetic algorithm-based schemes for both IAB node placement and non-IAB backhaul link distribution. We discuss the main challenges for enabling mesh-based IAB networks.
  arXiv  Detail & Related papers  (2021-02-14T21:52:05Z)
• PC-RGNN: Point Cloud Completion and Graph Neural Network for 3D Object Detection [57.49788100647103]
  LiDAR-based 3D object detection is an important task for autonomous driving. Current approaches suffer from sparse and partial point clouds of distant and occluded objects. In this paper, we propose a novel two-stage approach, namely PC-RGNN, dealing with such challenges by two specific solutions.
  arXiv  Detail & Related papers  (2020-12-18T18:06:43Z)
• Proximity-based Networking: Small world overlays optimized with particle swarm optimization [0.0]
  Small world networks can be incredibly useful in the dissemination and lookup of information within an internet network. We propose a networking scheme that incorporates geographic location in chord for the organization of peers within each node's partitioned key space. The flexibility of our proposed schemes enables a variety of swarm models, and agents.
  arXiv  Detail & Related papers  (2020-06-03T01:40:46Z)

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.