Title

The boundary iterative-deepening depth-first search algorithm

Document Type

Conference Proceeding

Publisher

Institute of Research Engineers and Doctors

Faculty

Faculty of Health, Engineering and Science

School

School of Engineering/Centre for Communications and Electronics Research

RAS ID

17157

Comments

This article was originally published as: Lim, K., Seng, K. , Yeong, L., Ch'ng, S., & Ang, L. K. (2013). The boundary iterative-deepening depth-first search algorithm. In Proceedings of the Second International Conference on Advances in Computer and Information Technology - ACIT 2013. (pp. 119-124). Kuala Lumpur, Malaysia: Institute of Research Engineers and Doctors. Original article available here

Abstract

Boundary searches were introduced in pathfinding aiming to find a middle-ground between memory intensive algorithms such as the A* search algorithm and the cycle redundancy of iterative-deepening algorithms such as the IDA*. Boundary search algorithms allocate a small memory footprint during runtime to store frontier nodes between each iteration to reduce redundancy, while expanding nodes in the same manner as iterative-deepening algorithms. The boundary search algorithm fringe search is an informed search algorithm derived from the IDA* for use in known environments. This paper proposes the boundary iterative-deepening depth-first search (BIDDFS) algorithm, which fills the gap made by the fringe search for uninformed search algorithms. The BIDDFS is optimised to perform blind searches in unknown environments, where simulation experiments found that it is up to more than 3 times faster than standard uninformed iterative-deepening algorithms.

Share

 
COinS