Uninformed pathfinding: A new approach

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

doi:10.1016/j.eswa.2014.10.046

Back

Journal article

Peer reviewed

Uninformed pathfinding: A new approach

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

Expert Systems with Applications, Vol.42(5), pp.2722-2730

2015

DOI: https://doi.org/10.1016/j.eswa.2014.10.046

Files and links (1)

url

https://doi.org/10.1016/j.eswa.2014.10.046View

Published Version

Abstract

Multi-goal search

Parallel search

Pathfinding

Uninformed search

Iterative methods

Bi-directional search

This paper presents a new pathfinding algorithm called the boundary iterative-deepening depth-first search (BIDDFS) algorithm. The BIDDFS compromises the increasing memory usage of the Dijkstra's algorithm, where the memory clears enables the BIDDFS to consume less memory than the Dijkstra's algorithm. The expansion redundancy of the iterative-deepening depth-first search (IDDFS) is also compensated; it is faster than the IDDFS in all of the testing instances conducted. The BIDDFS is further enhanced for bidirectional searching to allow expanding to fewer nodes and reducing pathfinding time. The bidirectional BIDDFS and the parallel bidirectional BIDDFS are also proposed. The proposed BIDDFS is further extended to the multi-goal BIDDFS, which is able to search for multiple goals present on the map in a single search. Simulation examples and comparisons have revealed the good performance of the proposed algorithms.

Details

Title: Uninformed pathfinding: A new approach
Authors: Kai Li Lim (Author) - Sunway University
Kah Phooi Seng (Author) - Edith Cowan University
Lee Seng Yeong (Author) - Sunway University
Li-Minn Ang (Author) - Edith Cowan University
Sue Inn Ch'ng (Author) - Sunway University
Publication details: Expert Systems with Applications, Vol.42(5), pp.2722-2730
Publisher: Elsevier Ltd
Date published: 2015
DOI: 10.1016/j.eswa.2014.10.046
ISSN: 0957-4174; 1873-6793; 0957-4174
Organisation Unit: University of the Sunshine Coast, Queensland; School of Science, Technology and Engineering; Engage Research Lab
Language: English
Record Identifier: 99513788402621
Output Type: Journal article

Metrics

41 Record Views

8 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types: Domestic collaboration; International collaboration
Web Of Science research areas: Computer Science, Artificial Intelligence; Engineering, Electrical & Electronic; Operations Research & Management Science