Uninformed Multigoal Pathfinding on Grid Maps

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

Research output: Book chapter/Published conference paperConference paper

5 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 languageEnglish
Title of host publicationProceedings 2014 International Conference on Information Science, Electronics and Electrical Engineering
Subtitle of host publicationISEEE 2014
EditorsXiaohong Jiang, Shaozi Li, Ying Dai, Yun Cheng
Place of PublicationUnited States
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages1552-1556
Number of pages5
ISBN (Print)9781479931965
DOIs
Publication statusPublished - 06 Nov 2014
EventInternational Conference on Information Science, Electronics and Electrical Engineering: ISEEE 2014 - Sapporo Prince Hotel, Sapporo City, Hokkaido, Japan
Duration: 26 Apr 201428 Apr 2014
https://web.archive.org/web/20140319233736/http://www.iseee.org:80/index.asp (Conference website)
https://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6917613 (Conference proceedings)

Conference

ConferenceInternational Conference on Information Science, Electronics and Electrical Engineering
CountryJapan
City Sapporo City, Hokkaido
Period26/04/1428/04/14
Other2014 International Conference on Information Science, Electronics and Electrical Engineering (ISEEE 2014) will be held from April 26-28, 2014, Sapporo City, Hokkaido, Japan.

ISEEE 2014 is sponsored by IEEE Sapporo Section, Japan, Xiamen University, and Co-sponsored by Future University Hakodate, Japan, Iwate Prefectural University, Japan, University of Hull, UK, Xiamen University, China, Guangzhou University, China.

Original papers are invited and submitted papers should not be previously published or currently under review for any other publication. All papers accepted will be published in the conference proceedings (ISBN: 978-1-4799-3196-5).
Internet address

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). United States: IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/InfoSEEE.2014.6946181
Lim, Kai Li ; Yeong, Lee Seng ; Ch'ng, Sue Inn ; Seng, Kah Phooi ; Ang, Li-Minn. / 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. United States : IEEE, Institute of Electrical and Electronics Engineers, 2014. pp. 1552-1556
@inproceedings{c35038249526421fa6fd31ae668a90f9,
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 Li-Minn Ang",
year = "2014",
month = "11",
day = "6",
doi = "10.1109/InfoSEEE.2014.6946181",
language = "English",
isbn = "9781479931965",
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",
publisher = "IEEE, Institute of Electrical and Electronics Engineers",
address = "United States",

}

Lim, KL, Yeong, LS, Ch'ng, SI, Seng, KP & 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. IEEE, Institute of Electrical and Electronics Engineers, United States, pp. 1552-1556, International Conference on Information Science, Electronics and Electrical Engineering, 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; Seng, Kah Phooi; Ang, Li-Minn.

Proceedings 2014 International Conference on Information Science, Electronics and Electrical Engineering: ISEEE 2014. ed. / Xiaohong Jiang; Shaozi Li; Ying Dai; Yun Cheng. United States : IEEE, Institute of Electrical and Electronics Engineers, 2014. p. 1552-1556.

Research output: Book chapter/Published conference paperConference paper

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/6

Y1 - 2014/11/6

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 - https://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6917613

UR - https://web.archive.org/web/20140411084227/http://iseee.org:80/ISEEE2014-ConferenceProgram.pdf

UR - https://web.archive.org/web/20131216015138/http://www.iseee.org:80/ISEEE2014%20Call%20for%20Papers.pdf

UR - https://web.archive.org/web/20140421082916/http://www.iseee.org/

U2 - 10.1109/InfoSEEE.2014.6946181

DO - 10.1109/InfoSEEE.2014.6946181

M3 - Conference paper

SN - 9781479931965

SP - 1552

EP - 1556

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

A2 - Jiang, Xiaohong

A2 - Li, Shaozi

A2 - Dai, Ying

A2 - Cheng, Yun

PB - IEEE, Institute of Electrical and Electronics Engineers

CY - United States

ER -

Lim KL, Yeong LS, Ch'ng SI, Seng KP, Ang L-M. 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. United States: IEEE, Institute of Electrical and Electronics Engineers. 2014. p. 1552-1556 https://doi.org/10.1109/InfoSEEE.2014.6946181