Abstract
C. Hernandez, W. Yeoh, J. Baier, A. Felner, O. Salzman, H. Zhang, S.-H. Chan and S. Koenig. Multi-Objective Search via Lazy and Efficient Dominance Checks. In International Joint Conference on Artificial Intelligence (IJCAI), pages 7223-7230, 2023.Abstract: Multi-objective search can be used to model many real-world problems that require finding Pareto-optimal paths from a specified start state to a specified goal state, while considering different cost metrics such as distance, time, and fuel. The performance of multi-objective search can be improved by making dominance checking - an operation necessary to determine whether or not a path dominates another - more efficient. This was shown in practice by BOA*, a state-of-the-art bi-objective search algorithm, which outperforms previously existing bi-objective search algorithms in part because it adopts a lazy approach towards dominance checking. EMOA*, a recent multi-objective search algorithm, generalizes BOA* to more-than-two objectives using AVL trees for dominance checking. In this paper, we first propose Linear-Time Multi-Objective A* (LTMOA*), a multi-objective search algorithm that implements more efficient dominance checking than EMOA* using simple data structures like arrays. We then propose LazyLTMOA*, which employs a lazier approach by removing dominance checking during node generation. Our experimental results show that LazyLTMOA* outperforms EMOA* by up to an order of magnitude in terms of runtime.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.