Uninformed multigoal pathfinding on grid maps

Kai Li Lim; Lee Seng Yeong; Sue Inn Ch'ng; Kah Phooi Seng; Li-Minn Ang

doi:10.1109/InfoSEEE.2014.6946181

Back

Uninformed multigoal pathfinding on grid maps

Conference paper

Peer reviewed

Uninformed multigoal pathfinding on grid maps

Kai Li Lim, Lee Seng Yeong, Sue Inn Ch'ng, Kah Phooi Seng and Li-Minn Ang

2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014, Vol.3, pp.1552-1556

International Conference on Information Science, Electronics and Electrical Engineering, 2014 (Sapporo, Japan, 26-Apr-2014–28-Apr-2014)

Institute of Electrical and Electronics Engineers

2014

DOI: https://doi.org/10.1109/InfoSEEE.2014.6946181

Files and links (1)

url

https://doi.org/10.1109/InfoSEEE.2014.6946181View

Published Version

Abstract

simulation

graph theory

tree searching

seducational institutions

redundancy

routing

arrays

buffer storage

electronic mail

open grid maps

uninformed multigoal pathfinding

Dijkstra shortest path

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.

Details

Title: Uninformed multigoal pathfinding on grid maps
Authors: Kai Li Lim (Author) - Sunway University
Lee Seng Yeong (Author) - Sunway University
Sue Inn Ch'ng (Author) - Sunway University
Kah Phooi Seng (Author) - Edith Cowan University
Li-Minn Ang (Author) - Edith Cowan University
Contributors: Xiaohong Jiang (Editor)
Xiamen da Xue (Editor)
Publication details: 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014, Vol.3, pp.1552-1556
Conference details: International Conference on Information Science, Electronics and Electrical Engineering, 2014 (Sapporo, Japan, 26-Apr-2014–28-Apr-2014)
Publisher: Institute of Electrical and Electronics Engineers
Date published: 2014
DOI: 10.1109/InfoSEEE.2014.6946181; 10.1109/InfoSEEE.2014
ISBN: 9781479931972
Organisation Unit: University of the Sunshine Coast, Queensland; School of Science, Technology and Engineering; Engage Research Lab
Language: English
Record Identifier: 99513889302621
Output Type: Conference paper

Metrics

58 Record Views