AAAI Publications, Tenth Annual Symposium on Combinatorial Search

Font Size: 
Shortest Path for K Goals
Roni Tzvi Stern, Meir Goldenberg, Ariel Felner

Last modified: 2017-06-05


In this paper we study the k goal search problem (kGS), which is the problem of solving k shortest path problems that share the same start state. Two fundamental heuristic search approaches are analyzed: searching for the k goals one at a time, or searching for all k goals together in a single pass. Key theoretical properties are established and a preliminary experimental evaluation is performed.

Full Text: PDF