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). IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/InfoSEEE.2014.6946181