Weight Constrained Path Finding with Bidirectional A*

Authors

  • Saman Ahmadi Department of Electrical and Biomedical Engineering, RMIT University, Australia
  • Guido Tack Department of Data Science and Artificial Intelligence, Monash University, Australia
  • Daniel Harabor Department of Data Science and Artificial Intelligence, Monash University, Australia
  • Philip Kilby CSIRO Data61, Australia

Keywords:

Constraint Search, Analysis Of Search Algorithms, Search In Robotics

Abstract

Weight constrained path finding, known as a challenging variant of the classic shortest path problem, aims to plan cost optimum paths whose weight/resource usage is limited by a side constraint. Given the bi-criteria nature of the problem (i.e., the presence of cost and weight), solutions to the Weight Constrained Shortest Path Problem (WCSPP) have some properties in common with bi-objective search. This paper leverages the state-of-the-art bi-objective search algorithm BOBA* and presents WC-BA*, an exact A*-based WCSPP method that explores the search space in different objective orderings bidirectionally. We also enrich WC-BA* with two novel heuristic tuning approaches that can significantly reduce the number of node expansions in the exhaustive search of A*. The results of our experiments on a large set of realistic problem instances show that our new algorithm solves all instances and outperforms the state-of-the-art WCSPP algorithms in various scenarios.

Downloads

Published

2022-07-17