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
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.
Comments
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. Available here