The boundary iterative-deepening depth-first search algorithm

Document Type

Conference Proceeding


Institute of Research Engineers and Doctors


Faculty of Health, Engineering and Science


School of Engineering / Centre for Communications and Electronics Research




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


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.