Bounded-Suboptimal Weight-Constrained Shortest-Path Search via Efficient Representation of Paths


  • Han Zhang University of Southern California
  • Oren Salzman Technion - Israel Institute of Technology
  • Ariel Felner Ben-Gurion University
  • T. K. Satish Kumar University of Southern California
  • Sven Koenig University of Southern California



In the Weight-Constrained Shortest-Path (WCSP) problem, given a graph in which each edge is annotated with a cost and a weight, a start state, and a goal state, the task is to compute a minimum-cost path from the start state to the goal state with weight no larger than a given weight limit. While most existing works have focused on solving the WCSP problem optimally, many real-world situations admit a trade-off between efficiency and a suboptimality bound for the path cost. In this paper, we propose the bounded-suboptimal WCSP algorithm WC-A*pex, which is built on the state-of-the-art approximate bi-objective search algorithm A*pex. WC-A*pex uses an approximate representation of paths with similar costs and weights to compute a (1+ε)-suboptimal path, for a given ε. During its search, WC-A*pex avoids storing all paths explicitly and thereby reduces the search effort while still retaining its (1 + ε)-suboptimality bound. On benchmark road networks, our experimental results show that WC-A*pex with ε = 0.01 (i.e., with a guaranteed suboptimality of at most 1%) achieves a speed-up of up to an order of magnitude over WC-A*, a state-of-the-art WCSP algorithm, and its bounded-suboptimal variant.




How to Cite

Zhang, H., Salzman, O., Felner, A., Kumar, T. K. S., & Koenig, S. (2024). Bounded-Suboptimal Weight-Constrained Shortest-Path Search via Efficient Representation of Paths. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 680-688.