Paper Info
Title
Heuristic search for one-to-many shortest path queries
Abstract
In this paper we study the One-to-Many Shortest Path Problem (OMSPP), which is the problem of solving k shortest path problems that share the same start node. This problem has been studied in the context of routing in road networks. While past work on routing relied on pre-processing the network, which is assumed to be provided explicitly. We explore how OMSPP can be solved with heuristic search techniques, allowing the searched graph to be given either explicitly or implicitly. Two fundamental heuristic search approaches are analyzed: searching for the k goals one at a time, or searching for all k goals as one compound goal. The former approach, denoted kxA*, is simpler to implement, but can be computationally inefficient, as it may expand a node multiple times, by the different searches. The latter approach, denoted kA*, can resolve this potential inefficiency, but implementing it raises fundamental questions such as how to combine k heuristic estimates, one per goal, and what to do after the shortest path to one of the goals has been found. We propose several ways to implement kA*, and characterize the required and sufficient conditions on the available heuristics and how they are aggregated such that the solution is admissible. Then, we analytically compare the runtime and memory requirements of kxA* and kA*, identifying when each approach should be used. Finally, we compare these approaches experimentally on two representative domains, providing empirical support for our theoretical analysis. These results shed light on when each approach is beneficial.
Year
DOI
Venue
2021
10.1007/s10472-021-09775-x
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
Keywords
DocType
Volume
Heuristic search, Path finding
Journal
89
Issue
ISSN
Citations 
12
1012-2443
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Roni Stern133549.62
Meir Goldenberg200.34
Abdallah Saffidine300.68
Ariel Felner400.34