Extending Weighted Heuristic Search to Bi-Objective Search Problems

摘要

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.