Weight constrained path finding with bidirectional A*

Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of the International Symposium on Combinatorial Search
EditorsLukás Chrpa, Alessandro Saetti
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages2-10
Number of pages9
ISBN (Electronic)1577358732
Publication statusPublished - 2022
EventInternational Symposium on Combinatorial Search 2022 - Vienna, Austria
Duration: 21 Jul 202223 Jul 2022
Conference number: 15th
https://sites.google.com/unibs.it/socs2022

Publication series

NameFifteenth International Symposium on Combinatorial Search
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number1
Volume15

Conference

ConferenceInternational Symposium on Combinatorial Search 2022
Abbreviated titleSOCS 2022
Country/TerritoryAustria
CityVienna
Period21/07/2223/07/22
Internet address

Keywords

  • Constraint Search
  • Analysis Of Search Algorithms
  • Search In Robotics

Cite this