Uninformed multigoal pathfinding on grid maps

Document Type

Conference Proceeding

Publisher

IEEE

Faculty

Faculty of Health, Engineering and Science

School

School of Engineering

RAS ID

19197

Comments

Lim K.L., Yeong L.S., Ch'Ng S.I., Seng K.P., & Ang L.-M. (2014). Uninformed multigoal pathfinding on grid maps. ISEEE 2014 - Proceedings: 2014 International Conference on Information Science, Electronics and Electrical Engineering. (pp. 1552-1556). Sapporo, Japan. IEEE. © 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Available here

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.

DOI

10.1109/InfoSEEE.2014.6946181

Access Rights

subscription content

Link to Full Text

Share

 
COinS