Efficient Multi-Query Bi-Objective Search via Contraction Hierarchies

Han Zhang, Oren Salzman, Ariel Felner, T. K.Satish Kumar, Carlos Hernández Ulloa, Sven Koenig

פרסום מחקרי: פרסום בכתב עתמאמר מכנסביקורת עמיתים

תקציר

Contraction Hierarchies (CHs) have been successfully used as a preprocessing technique in single-objective graph search for finding shortest paths. However, only a few existing works on utilizing CHs for bi-objective search exist, and none of them uses CHs to compute Pareto frontiers. This paper proposes an CH-based approach capable of efficiently computing Pareto frontiers for bi-objective search along with several speedup techniques. Specifically, we propose a new preprocessing approach that computes CHs with fewer edges than the existing preprocessing approach, which reduces both the preprocessing times (up to 3× in our experiments) and the query times. Furthermore, we propose a partial-expansion technique, which dramatically speeds up the query times. We demonstrate the advantages of our approach on road networks with 1 to 14 million states. The longest preprocessing time is less than 6 hours, and the average speedup in query times is roughly two orders of magnitude compared to BOA*, a state-of-the-art single-query bi-objective search algorithm.

שפה מקוריתאנגלית
עמודים (מ-עד)452-461
מספר עמודים10
כתב עתProceedings International Conference on Automated Planning and Scheduling, ICAPS
כרך33
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ינו׳ 2023
אירוע33rd International Conference on Automated Planning and Scheduling, ICAPS 2023 - Prague, צ'כיה
משך הזמן: 8 יולי 202313 יולי 2023

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1702???
  • ???subjectarea.asjc.1700.1706???
  • ???subjectarea.asjc.1800.1802???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Efficient Multi-Query Bi-Objective Search via Contraction Hierarchies'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי