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 paperpeer-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 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
    Country/TerritoryJapan
    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

    Fingerprint

    Dive into the research topics of 'Uninformed Multigoal Pathfinding on Grid Maps'. Together they form a unique fingerprint.

    Cite this