Weight Constrained Path Finding with Bidirectional A*
| العنوان: | Weight Constrained Path Finding with Bidirectional A* |
|---|---|
| المؤلفون: | Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby |
| المصدر: | Proceedings of the International Symposium on Combinatorial Search. 15:2-10 |
| بيانات النشر: | Association for the Advancement of Artificial Intelligence (AAAI), 2022. |
| سنة النشر: | 2022 |
| الوصف: | 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. |
| تدمد: | 2832-9163 2832-9171 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::be32d0084961d17bacd45a5cd8fb9d35 https://doi.org/10.1609/socs.v15i1.21746 |
| رقم الأكسشن: | edsair.doi...........be32d0084961d17bacd45a5cd8fb9d35 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 28329163 28329171 |
|---|