Extending Weighted Heuristic Search to Bi-Objective Search Problems

Kühn Leiva, Hans; Baier, Jorge A.; Hernandez Ulloa, Carlos; Salzman, Oren; Felner, Ariel; Koenig, Sven

doi:10.24963/ijcai.2026/700

Extending Weighted Heuristic Search to Bi-Objective Search Problems

Hans Kühn Leiva, Jorge A. Baier, Carlos Hernández Ulloa, Oren Salzman, Ariel Felner, Sven Koenig

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 6291-6298.

https://doi.org/10.24963/ijcai.2026/700

Keywords

Search: Heuristic search
Search: Combinatorial search and optimisation

Abstract

In heuristic search, a well-known technique to speed up search while providing a suboptimality guarantee is to multiply the heuristic function by a weight w > 1. In this paper, we study the theoretical and practical implications of using such a technique in bi-objective heuristic search, a natural academic exercise that has remained unexplored. We introduce Weighted BOA∗ϵ (WBOA∗

ϵ ), a weighted version of the BOA* algorithm, which uses two real parameters: a weight w for the heuristic and an approximation factor ϵ. Higher values of w and ϵ allow for faster computation of approximate Pareto-optimal solution sets. We prove that WBOA∗ ϵ returns a representative solution set containing (w − 1, ϵ)-approximate solutions. We empirically compare it to A*pex, the state-of-the-art approximate bi-objective search algorithm. We find that WBOA∗ ϵ is competitive with A*pex: when using perfect heuristic functions, in road maps WBOA∗ϵ is faster for higher approximation factors, while in grid maps WBOA∗ϵ dominates A*pex. With imperfect heuristic functions, WBOA∗ϵ performs better than A*pex for lower approximation factors, while the opposite is true for larger approximation factors.

Hans Kühn Leiva, Jorge A. Baier, Carlos Hernandez Ulloa, Oren Salzman, Ariel Felner, and Sven Koenig. 2026. Extending Weighted Heuristic Search to Bi-Objective Search Problems. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 6291–6298. https://doi.org/10.24963/ijcai.2026/700

@inproceedings{ijcai2026p700,
  title     = {Extending Weighted Heuristic Search to Bi-Objective Search Problems},
  author    = {Kühn Leiva, Hans and Baier, Jorge A. and Hernandez Ulloa, Carlos and Salzman, Oren and Felner, Ariel and Koenig, Sven},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {6291--6298},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/700},
  url       = {https://doi.org/10.24963/ijcai.2026/700},
}

TY  - CPAPER
TI  - Extending Weighted Heuristic Search to Bi-Objective Search Problems
AU  - Kühn Leiva, Hans
AU  - Baier, Jorge A.
AU  - Hernandez Ulloa, Carlos
AU  - Salzman, Oren
AU  - Felner, Ariel
AU  - Koenig, Sven
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 6291
EP  - 6298
DO  - 10.24963/ijcai.2026/700
UR  - https://doi.org/10.24963/ijcai.2026/700
ER  -