Uninformed multigoal pathfinding on grid maps
Kai Li Lim, Lee Seng Yeong, Sue Inn Ch’ng, Kah Phooi Seng, Li-Minn Ang · 2014
This paper proposes multigoal implementations of the Dijkstra's shortest path algorithm and the boundary iterative-deepening depth-first search (BIDDFS). The algorithms were modified to allow for the search of more than one goal in a single expansion pass. The aim of this is to reduce the operational redundancy and hence the time taken for calculating multiple start-goal node pairs. Simulations using multigoal algorithms on 250× 250 open grid maps with nine goals have shown up to a 458% increase in time efficiency.