אריאל פלנר

אקדמי בכיר

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

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.

שפת פרסום אנגלית
דפים 6291-6298
סטטוס פרסום פורסם - 01.01.2026

ASJC Scopus subject areas

Artificial Intelligence
גישה למסמך
10.24963/ijcai.2026/700
קבצים וקישורים אחרים
Link to publication in Scopus