Resource Constrained Pathfinding with Enhanced Bidirectional A* Search

• URL: http://arxiv.org/abs/2412.13888v1
• Date: Wed, 18 Dec 2024 14:29:40 GMT
• Title: Resource Constrained Pathfinding with Enhanced Bidirectional A* Search
• Authors: Saman Ahmadi, Andrea Raith, Guido Tack, Mahdi Jalili,
• Abstract summary: This research introduces a novel constrained search framework that uses efficient pruning strategies to allow for accelerated and effective RCSP search in large-scale networks.<n>Results show that, compared to the state of the art, our enhanced framework can significantly reduce the constrained search time, achieving speed-ups of over to two orders of magnitude.
• Score: 10.100786663811666
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classic Resource Constrained Shortest Path (RCSP) problem aims to find a cost optimal path between a pair of nodes in a network such that the resources used in the path are within a given limit. Having been studied for over a decade, RCSP has seen recent solutions that utilize heuristic-guided search to solve the constrained problem faster. Building upon the bidirectional A* search paradigm, this research introduces a novel constrained search framework that uses efficient pruning strategies to allow for accelerated and effective RCSP search in large-scale networks. Results show that, compared to the state of the art, our enhanced framework can significantly reduce the constrained search time, achieving speed-ups of over to two orders of magnitude.

Related papers

• Resource Constrained Pathfinding with A* and Negative Weights [8.899546103635938]
  Constrained pathfinding is a well-studied, yet challenging network optimisation problem. This paper introduces a new resource constrained search framework on the basis of A* to tackle RCSP in large networks. We show up to two orders of magnitude faster performance compared to state-of-the-art RCSP algorithms in the literature.
  arXiv  Detail & Related papers  (2025-03-14T03:06:40Z)
• Intelligent Routing Algorithm over SDN: Reusable Reinforcement Learning Approach [1.799933345199395]
  We develop a reusable RL-aware, reusable routing algorithm, RLSR-Routing over SDN. Our algorithm shows better performance in terms of load balancing than the traditional approaches. It also has faster convergence than the non-reusable RL approach when finding paths for multiple traffic demands.
  arXiv  Detail & Related papers  (2024-09-23T17:15:24Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• Deep Reinforcement Learning Based Cross-Layer Design in Terahertz Mesh Backhaul Networks [12.963836913881801]
  Terahertz (THz) mesh networks are attractive for next-generation wireless backhaul systems. The efficient cross-layer routing and long-term resource allocation is yet an open problem in THz mesh networks. This paper proposes a deep reinforcement learning (DRL) based cross-layer design in THz mesh networks.
  arXiv  Detail & Related papers  (2023-10-08T06:36:00Z)
• Efficient Joint-Dimensional Search with Solution Space Regularization for Real-Time Semantic Segmentation [27.94898516315886]
  We search an optimal network structure that can run in real-time for this problem. A novel Solution Space Regularization (SSR) loss is first proposed to effectively encourage the supernet to converge to its discrete one. A new Hierarchical and Progressive Solution Space Shrinking method is presented to further achieve high efficiency of searching.
  arXiv  Detail & Related papers  (2022-08-10T11:07:33Z)
• Enhanced Methods for the Weight Constrained Shortest Path Problem [18.567812400186092]
  The Weight Constrained Shortest Path Problem (WCSPP) is a well-studied, yet challenging, topic in AI. This paper presents two new solution approaches to the WCSPP on the basis of A* search. We empirically evaluate the performance of our algorithms on a set of large and realistic problem instances.
  arXiv  Detail & Related papers  (2022-07-29T15:32:45Z)
• Adaptive Channel Allocation for Robust Differentiable Architecture Search [22.898344333732044]
  Differentiable ARchiTecture Search (DARTS) has attracted much attention due to its simplicity and significant improvement in efficiency. The excessive accumulation of the skip connection, when training epochs become large, makes it suffer from weak stability and low robustness. We propose a more subtle and direct approach that no longer explicitly searches for skip connections in the search stage.
  arXiv  Detail & Related papers  (2022-04-10T13:25:36Z)
• $\beta$-DARTS: Beta-Decay Regularization for Differentiable Architecture Search [85.84110365657455]
  We propose a simple-but-efficient regularization method, termed as Beta-Decay, to regularize the DARTS-based NAS searching process. Experimental results on NAS-Bench-201 show that our proposed method can help to stabilize the searching process and makes the searched network more transferable across different datasets.
  arXiv  Detail & Related papers  (2022-03-03T11:47:14Z)
• Combined Depth Space based Architecture Search For Person Re-identification [70.86236888223569]
  We aim to design a lightweight and suitable network for person re-identification (ReID) We propose a novel search space called Combined Depth Space (CDS), based on which we search for an efficient network architecture, which we call CDNet. We then propose a low-cost search strategy named the Top-k Sample Search strategy to make full use of the search space and avoid trapping in local optimal result.
  arXiv  Detail & Related papers  (2021-04-09T02:40:01Z)
• CATCH: Context-based Meta Reinforcement Learning for Transferrable Architecture Search [102.67142711824748]
  CATCH is a novel Context-bAsed meTa reinforcement learning algorithm for transferrable arChitecture searcH. The combination of meta-learning and RL allows CATCH to efficiently adapt to new tasks while being agnostic to search spaces. It is also capable of handling cross-domain architecture search as competitive networks on ImageNet, COCO, and Cityscapes are identified.
  arXiv  Detail & Related papers  (2020-07-18T09:35:53Z)
• Theory-Inspired Path-Regularized Differential Network Architecture Search [206.93821077400733]
  We study the impact of skip connections to fast network optimization and its competitive advantage over other types of operations in differential architecture search (DARTS) We propose a theory-inspired path-regularized DARTS that consists of two key modules: (i) a differential group-structured sparse binary gate introduced for each operation to avoid unfair competition among operations, and (ii) a path-depth-wise regularization used to incite search exploration for deep architectures that converge slower than shallow ones.
  arXiv  Detail & Related papers  (2020-06-30T05:28:23Z)
• RC-DARTS: Resource Constrained Differentiable Architecture Search [162.7199952019152]
  We propose the resource constrained differentiable architecture search (RC-DARTS) method to learn architectures that are significantly smaller and faster. We show that the RC-DARTS method learns lightweight neural architectures which have smaller model size and lower computational complexity.
  arXiv  Detail & Related papers  (2019-12-30T05:02:38Z)

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.