{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,17]],"date-time":"2026-11-17T12:18:06Z","timestamp":1794917886655,"version":"4.9.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,9]]},"abstract":"<jats:p>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 &gt; 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\u2217\u03f5 (WBOA\u2217\n\u03f5 ), a weighted version of the BOA* algorithm, which uses two real parameters: a weight w for the heuristic and an approximation factor \u03f5. Higher values of w and \u03f5 allow for faster computation of approximate Pareto-optimal solution sets. We prove that WBOA\u2217 \u03f5 returns a representative solution set containing (w \u2212 1, \u03f5)-approximate solutions. We empirically compare it to A*pex, the state-of-the-art approximate bi-objective search algorithm. We find that WBOA\u2217 \u03f5 is competitive with A*pex: when using perfect heuristic functions, in road maps WBOA\u2217\u03f5 is faster for higher approximation factors, while in grid maps WBOA\u2217\u03f5 dominates A*pex. With imperfect heuristic functions, WBOA\u2217\u03f5 performs better than A*pex for lower approximation factors, while the opposite is true for larger approximation factors.<\/jats:p>","DOI":"10.24963\/ijcai.2026\/700","type":"proceedings-article","created":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T22:01:13Z","timestamp":1789596073000},"page":"6291-6298","source":"Crossref","is-referenced-by-count":0,"title":["Extending Weighted Heuristic Search to Bi-Objective Search Problems"],"prefix":"10.24963","author":[{"given":"Hans","family":"K\u00fchn Leiva","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jorge A.","family":"Baier","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile"},{"name":"Centro Nacional de Inteligencia Artificial"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carlos","family":"Hern\u00e1ndez Ulloa","sequence":"additional","affiliation":[{"name":"Universidad San Sebasti\u00e1n"},{"name":"Centro Nacional de Inteligencia Artificial"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oren","family":"Salzman","sequence":"additional","affiliation":[{"name":"Technion \u2013 Israel Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ariel","family":"Felner","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sven","family":"Koenig","sequence":"additional","affiliation":[{"name":"University of California Irvine"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Thirty-Fifth International Joint Conference on Artificial Intelligence {IJCAI-26}","theme":"Artificial Intelligence","location":"Bremen, Germany","acronym":"IJCAI-2026","number":"35","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2026,8,15]]},"end":{"date-parts":[[2026,8,21]]}},"container-title":["Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2026,11,17]],"date-time":"2026-11-17T11:31:22Z","timestamp":1794915082000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2026\/700"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2026,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2026\/700","relation":{},"subject":[],"published":{"date-parts":[[2026,9]]}}}