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

Uninformed multigoal pathfinding on grid maps

Kai Li Lim, Lee Seng Yeong, Sue Inn Ch'Ng, Kah Phooi Seng, Li Minn Ang

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

6 Citations (Scopus)

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.

Original language	English
Title of host publication	Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014
Editors	Xiaohong Jiang, Shaozi Li, Ying Dai, Yun Cheng
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1552-1556
Number of pages	5
ISBN (Electronic)	9781479931965
DOIs	https://doi.org/10.1109/InfoSEEE.2014.6946181
Publication status	Published - 5 Nov 2014
Externally published	Yes
Event	2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014 - Sapporo City, Hokkaido, Japan Duration: 26 Apr 2014 → 28 Apr 2014

Publication series

Name	Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014
Volume	3

Conference

Conference	2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014
Country/Territory	Japan
City	Sapporo City, Hokkaido
Period	26/04/14 → 28/04/14

Access to Document

10.1109/InfoSEEE.2014.6946181

Cite this

Lim, K. L., Yeong, L. S., Ch'Ng, S. I., Seng, K. P., & Ang, L. M. (2014). Uninformed multigoal pathfinding on grid maps. In X. Jiang, S. Li, Y. Dai, & Y. Cheng (Eds.), Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014 (pp. 1552-1556). Article 6946181 (Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014; Vol. 3). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/InfoSEEE.2014.6946181

Lim, Kai Li ; Yeong, Lee Seng ; Ch'Ng, Sue Inn et al. / Uninformed multigoal pathfinding on grid maps. Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014. editor / Xiaohong Jiang ; Shaozi Li ; Ying Dai ; Yun Cheng. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 1552-1556 (Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014).

@inproceedings{edfd054612cc4036a55a77c22d831560,

title = "Uninformed multigoal pathfinding on grid maps",

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.",

author = "Lim, {Kai Li} and Yeong, {Lee Seng} and Ch'Ng, {Sue Inn} and Seng, {Kah Phooi} and Ang, {Li Minn}",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014 ; Conference date: 26-04-2014 Through 28-04-2014",

year = "2014",

month = nov,

day = "5",

doi = "10.1109/InfoSEEE.2014.6946181",

language = "English",

series = "Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1552--1556",

editor = "Xiaohong Jiang and Shaozi Li and Ying Dai and Yun Cheng",

booktitle = "Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014",

}

Lim, KL, Yeong, LS, Ch'Ng, SI, Seng, KP & Ang, LM 2014, Uninformed multigoal pathfinding on grid maps. in X Jiang, S Li, Y Dai & Y Cheng (eds), Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014., 6946181, Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014, vol. 3, Institute of Electrical and Electronics Engineers Inc., pp. 1552-1556, 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014, Sapporo City, Hokkaido, Japan, 26/04/14. https://doi.org/10.1109/InfoSEEE.2014.6946181

Uninformed multigoal pathfinding on grid maps. / Lim, Kai Li; Yeong, Lee Seng; Ch'Ng, Sue Inn et al.
Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014. ed. / Xiaohong Jiang; Shaozi Li; Ying Dai; Yun Cheng. Institute of Electrical and Electronics Engineers Inc., 2014. p. 1552-1556 6946181 (Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014; Vol. 3).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Uninformed multigoal pathfinding on grid maps

AU - Lim, Kai Li

AU - Yeong, Lee Seng

AU - Ch'Ng, Sue Inn

AU - Seng, Kah Phooi

AU - Ang, Li Minn

PY - 2014/11/5

Y1 - 2014/11/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84913534601&partnerID=8YFLogxK

U2 - 10.1109/InfoSEEE.2014.6946181

DO - 10.1109/InfoSEEE.2014.6946181

M3 - Conference Proceeding

AN - SCOPUS:84913534601

T3 - Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014

SP - 1552

EP - 1556

BT - Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014

A2 - Jiang, Xiaohong

A2 - Li, Shaozi

A2 - Dai, Ying

A2 - Cheng, Yun

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014

Y2 - 26 April 2014 through 28 April 2014

ER -

Lim KL, Yeong LS, Ch'Ng SI, Seng KP, Ang LM. Uninformed multigoal pathfinding on grid maps. In Jiang X, Li S, Dai Y, Cheng Y, editors, Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 1552-1556. 6946181. (Proceedings - 2014 International Conference on Information Science, Electronics and Electrical Engineering, ISEEE 2014). doi: 10.1109/InfoSEEE.2014.6946181

Uninformed multigoal pathfinding on grid maps

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this