Exact Multi-objective Path Finding with Negative Weights


  • Saman Ahmadi RMIT University, Australia
  • Nathan R. Sturtevant University of Alberta, Canada
  • Daniel Harabor Monash University, Australia
  • Mahdi Jalili RMIT University, Australia




The point-to-point Multi-objective Shortest Path (MOSP) problem is a classic yet challenging task that involves finding all Pareto-optimal paths between two points in a graph with multiple edge costs. Recent studies have shown that employing A* search can lead to state-of-the-art performance in solving MOSP instances with non-negative costs. This paper proposes a novel A*-based multi-objective search framework that not only handles graphs with negative costs and even negative cycles but also incorporates multiple speed-up techniques to enhance the efficiency of exhaustive search with A*. Through extensive experiments, our algorithm demonstrates remarkable success in solving difficult MOSP instances, outperforming leading solutions by several factors.




How to Cite

Ahmadi, S., Sturtevant, N. R., Harabor, D., & Jalili, M. (2024). Exact Multi-objective Path Finding with Negative Weights. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 11-19. https://doi.org/10.1609/icaps.v34i1.31455