The boundary iterative-deepening depth-first search algorithm
Institute of Research Engineers and Doctors
Faculty of Health, Engineering and Science
School of Engineering / Centre for Communications and Electronics Research
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.