Resource Constrained Pathfinding with A* and Negative Weights

• URL: http://arxiv.org/abs/2503.11037v1
• Date: Fri, 14 Mar 2025 03:06:40 GMT
• Title: Resource Constrained Pathfinding with A* and Negative Weights
• Authors: Saman Ahmadi, Andrea Raith, Mahdi Jalili,
• Abstract summary: Constrained pathfinding is a well-studied, yet challenging network optimisation problem.<n>This paper introduces a new resource constrained search framework on the basis of A* to tackle RCSP in large networks.<n>We show up to two orders of magnitude faster performance compared to state-of-the-art RCSP algorithms in the literature.
• Score: 8.899546103635938
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constrained pathfinding is a well-studied, yet challenging network optimisation problem that can be seen in a broad range of real-world applications. Pathfinding with multiple resource limits, which is known as the Resource Constrained Shortest Path Problem (RCSP), aims to plan a cost-optimum path subject to limited usage of resources. Given the recent advances in constrained and multi-criteria search with A*, this paper introduces a new resource constrained search framework on the basis of A* to tackle RCSP in large networks, even in the presence of negative cost and negative resources. We empirically evaluate our new algorithm on a set of large instances and show up to two orders of magnitude faster performance compared to state-of-the-art RCSP algorithms in the literature.

Related papers

• Resource Constrained Pathfinding with Enhanced Bidirectional A* Search [10.100786663811666]
  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.
  arXiv  Detail & Related papers  (2024-12-18T14:29:40Z)
• Joint Admission Control and Resource Allocation of Virtual Network Embedding via Hierarchical Deep Reinforcement Learning [69.00997996453842]
  We propose a deep Reinforcement Learning approach to learn a joint Admission Control and Resource Allocation policy for virtual network embedding. We show that HRL-ACRA outperforms state-of-the-art baselines in terms of both the acceptance ratio and long-term average revenue.
  arXiv  Detail & Related papers  (2024-06-25T07:42:30Z)
• 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)
• Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality [57.91411772725183]
  In this paper, we consider the offline shortest path problem when the state space and the action space are finite. We design the simple value-based algorithms for tackling both offline policy evaluation (OPE) and offline policy learning tasks. Our analysis of these simple algorithms yields strong instance-dependent bounds which can imply worst-case bounds that are near-minimax optimal.
  arXiv  Detail & Related papers  (2022-06-10T07:44:56Z)
• Evolutionary Optimization for Proactive and Dynamic Computing Resource Allocation in Open Radio Access Network [4.9711284100869815]
  Intelligent techniques are urged to achieve automatic allocation of the computing resource in Open Radio Access Network (O-RAN) Existing problem formulation to solve this resource allocation problem is unsuitable as it defines the capacity utility of resource in an inappropriate way. New formulation that better describes the problem is proposed.
  arXiv  Detail & Related papers  (2022-01-12T08:52:04Z)
• Coordinated Online Learning for Multi-Agent Systems with Coupled Constraints and Perturbed Utility Observations [91.02019381927236]
  We introduce a novel method to steer the agents toward a stable population state, fulfilling the given resource constraints. The proposed method is a decentralized resource pricing method based on the resource loads resulting from the augmentation of the game's Lagrangian.
  arXiv  Detail & Related papers  (2020-10-21T10:11:17Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  The paper investigates the general problem of resource allocation for mitigating channel fading effects in Free Space Optical (FSO) communications. Under this framework, we propose two algorithms that solve FSO resource allocation problems.
  arXiv  Detail & Related papers  (2020-07-27T17:38:51Z)
• Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation [49.69139684065241]
  Contextual multi-armed bandit (MAB) achieves cutting-edge performance on a variety of problems. In this paper, we propose a hierarchical adaptive contextual bandit method (HATCH) to conduct the policy learning of contextual bandits with a budget constraint.
  arXiv  Detail & Related papers  (2020-04-02T17:04:52Z)
• 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.