DocumentCode
142158
Title
Uninformed multigoal pathfinding on grid maps
Author
Kai Li Lim ; Lee Seng Yeong ; Sue Inn Ch´ng ; Kah Phooi Seng ; Li-Minn Ang
Author_Institution
Dept. of Comput. Sci. & Networked Syst., Sunway Univ., Petaling Jaya, Malaysia
Volume
3
fYear
2014
fDate
26-28 April 2014
Firstpage
1552
Lastpage
1556
Abstract
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.
Keywords
graph theory; tree searching; Dijkstra shortest path algorithm; boundary iterative-deepening depth-first search; multigoal algorithms; multiple start-goal node pairs; open grid maps; operational redundancy; uninformed multigoal pathfinding; Arrays; Buffer storage; Educational institutions; Electronic mail; Redundancy; Routing; Simulation;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Science, Electronics and Electrical Engineering (ISEEE), 2014 International Conference on
Conference_Location
Sapporo
Print_ISBN
978-1-4799-3196-5
Type
conf
DOI
10.1109/InfoSEEE.2014.6946181
Filename
6946181
Link To Document