This paper proposes multigoal implementations of the Dijkstra’s shortest path algorithm and the boundary iterative deepening depth-ﬁrst search (BIDDFS). The algorithms were modiﬁed 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 efﬁciency.
|Title of host publication||Proceedings 2014 International Conference on Information Science, Electronics and Electrical Engineering|
|Subtitle of host publication||ISEEE 2014|
|Editors||Xiaohong Jiang, Shaozi Li, Ying Dai, Yun Cheng|
|Place of Publication||United States|
|Publisher||IEEE, Institute of Electrical and Electronics Engineers|
|Number of pages||5|
|Publication status||Published - 06 Nov 2014|
|Event||International Conference on Information Science, Electronics and Electrical Engineering: ISEEE 2014 - Sapporo Prince Hotel, Sapporo City, Hokkaido, Japan|
Duration: 26 Apr 2014 → 28 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||International Conference on Information Science, Electronics and Electrical Engineering|
|City||Sapporo City, Hokkaido|
|Period||26/04/14 → 28/04/14|
|Other||2014 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).
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