Shortest Path for K Goals

Proceedings of the International Symposium on Combinatorial Search, 10

Volume

Vol. 10 No. 1 (2017): Tenth Annual Symposium on Combinatorial Search

Extended Abstracts

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.

10.1609/socs.v8i1.18413