---
title: "Extending Weighted Heuristic Search to Bi-Objective Search Problems"
authors:
  - "Hans Kühn Leiva"
  - "Jorge A. Baier"
  - "Carlos Hernández Ulloa"
  - "Oren Salzman"
  - "Ariel Felner"
  - "Sven Koenig"
doi: "10.24963/ijcai.2026/700"
url: "https://ijcai.org/proceedings/2026/700"
pdf: "https://ijcai.org/proceedings/2026/0700.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "6291-6298"
track: "Main Track"
keywords:
  - "Search: Heuristic search"
  - "Search: Combinatorial search and optimisation"
---

# 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

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 6291-6298. DOI: [10.24963/ijcai.2026/700](https://doi.org/10.24963/ijcai.2026/700)

## 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.