{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,7,2]],"date-time":"2023-07-02T08:10:49Z","timestamp":1688285449866},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SOCS"],"abstract":"In bi-objective graph search, each edge is annotated with a cost pair, where each cost corresponds to an objective to optimize. We are interested in finding all undominated paths from a given start state to a given goal state (called the Pareto front). Almost all existing works of bi-objective search use single-valued heuristics, which use one number for each objective, to estimate the cost between any given state and the goal state. However, single-valued heuristics cannot reflect the trade-offs between the two costs. On the other hand, multi-valued heuristics use a set of pairs to estimate the Pareto front between any given state and the goal state and are more informed than single-valued heuristics. However, they are rarely studied and have yet to be investigated in explicit state spaces by any existing work. In this paper, we are interested in using multi-valued heuristics to improve bi-objective search algorithms in explicit state spaces. More specifically, we generalize Differential Heuristics (DHs), a class of memory-based heuristics for single-objective search, to bi-objective search, resulting in Bi-objective Differential Heuristics (BO-DHs). We propose several techniques to reduce the memory usage and computational overhead of BO-DHs significantly. Our experimental results show that, with suggested improvement and tuned parameters, BO-DHs can reduce the node expansion and runtime of a bi-objective search algorithm by up to an order of magnitude, paving the way for more effective multi-valued heuristics.<\/jats:p>","DOI":"10.1609\/socs.v16i1.27288","type":"journal-article","created":{"date-parts":[[2023,7,2]],"date-time":"2023-07-02T07:29:46Z","timestamp":1688282986000},"page":"101-109","source":"Crossref","is-referenced-by-count":0,"title":["Towards Effective Multi-Valued Heuristics for Bi-objective Shortest-Path Algorithms via Differential Heuristics"],"prefix":"10.1609","volume":"16","author":[{"given":"Han","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Oren","family":"Salzman","sequence":"additional","affiliation":[]},{"given":"Ariel","family":"Felner","sequence":"additional","affiliation":[]},{"given":"T. K. Satish","family":"Kumar","sequence":"additional","affiliation":[]},{"given":"Shawn","family":"Skyler","sequence":"additional","affiliation":[]},{"given":"Carlos","family":"Hern\u00e1ndez Ulloa","sequence":"additional","affiliation":[]},{"given":"Sven","family":"Koenig","sequence":"additional","affiliation":[]}],"member":"9382","published-online":{"date-parts":[[2023,7,2]]},"container-title":["Proceedings of the International Symposium on Combinatorial Search"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/download\/27288\/27061","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/download\/27288\/27061","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,2]],"date-time":"2023-07-02T07:29:47Z","timestamp":1688282987000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/view\/27288"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,2]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,7,2]]}},"URL":"https:\/\/doi.org\/10.1609\/socs.v16i1.27288","relation":{},"ISSN":["2832-9163","2832-9171"],"issn-type":[{"value":"2832-9163","type":"electronic"},{"value":"2832-9171","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7,2]]}}}