The boundary iterative-deepening depth-first search algorithm

Kai Li Lim, Kah Phooi Seng, LS Yeong, SI Ch'ng, Li-minn K Ang

Research output: Book chapter/Published conference paperConference paper

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.
Original languageEnglish
Title of host publicationProceedings of the 2nd International Conference on Advances in Computer and Information Technology - ACIT 2013
Place of PublicationUnited States
PublisherInstitute of Research Engineers and Doctors, LLC
Pages119-124
Number of pages6
ISBN (Electronic)9789810762612
DOIs
Publication statusPublished - 04 May 2013
EventSecond International Conference on Advances in Computer and Information Technology: ACIT 2013 - Shangri-La Hotel, Kuala Lumpur, Malaysia
Duration: 04 May 201305 May 2013
https://web.archive.org/web/20130504170854/http://www.theired.org/acit (Conference website)
https://seekdl.org/conferences/details/International-Conference-on-Advances-in-Computer-and-Information-Technology-ACIT-2013 (Conference proceedings)

Conference

ConferenceSecond International Conference on Advances in Computer and Information Technology
CountryMalaysia
CityKuala Lumpur
Period04/05/1305/05/13
OtherThe Second International Conference on Advances in Computer and Information Technology - ACIT 2013 is being organized by Institute of Research Engineers and Doctors (IRED). The aim of the conference is to provide the platform for Students, Engineers, Researchers and Scientists to share the knowledge and ideas in the recent trends in the field of Computer Science and Engineering.
Internet address

Fingerprint

Redundancy
Data storage equipment
Experiments

Cite this

Lim, K. L., Seng, K. P., Yeong, LS., Ch'ng, SI., & Ang, L. K. (2013). The boundary iterative-deepening depth-first search algorithm. In Proceedings of the 2nd International Conference on Advances in Computer and Information Technology - ACIT 2013 (pp. 119-124). United States: Institute of Research Engineers and Doctors, LLC. https://doi.org/10.3850/ 978-981-07-6261-2_26
Lim, Kai Li ; Seng, Kah Phooi ; Yeong, LS ; Ch'ng, SI ; Ang, Li-minn K. / The boundary iterative-deepening depth-first search algorithm. Proceedings of the 2nd International Conference on Advances in Computer and Information Technology - ACIT 2013 . United States : Institute of Research Engineers and Doctors, LLC, 2013. pp. 119-124
@inproceedings{5ad9694cd9734d06978a673cacb94437,
title = "The boundary iterative-deepening depth-first search algorithm",
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.",
keywords = "pathfinding, uninformed search, iterative deepening, boundary search",
author = "Lim, {Kai Li} and Seng, {Kah Phooi} and LS Yeong and SI Ch'ng and Ang, {Li-minn K}",
year = "2013",
month = "5",
day = "4",
doi = "10.3850/ 978-981-07-6261-2_26",
language = "English",
pages = "119--124",
booktitle = "Proceedings of the 2nd International Conference on Advances in Computer and Information Technology - ACIT 2013",
publisher = "Institute of Research Engineers and Doctors, LLC",

}

Lim, KL, Seng, KP, Yeong, LS, Ch'ng, SI & Ang, LK 2013, The boundary iterative-deepening depth-first search algorithm. in Proceedings of the 2nd International Conference on Advances in Computer and Information Technology - ACIT 2013 . Institute of Research Engineers and Doctors, LLC, United States, pp. 119-124, Second International Conference on Advances in Computer and Information Technology, Kuala Lumpur, Malaysia, 04/05/13. https://doi.org/10.3850/ 978-981-07-6261-2_26

The boundary iterative-deepening depth-first search algorithm. / Lim, Kai Li; Seng, Kah Phooi; Yeong, LS; Ch'ng, SI; Ang, Li-minn K.

Proceedings of the 2nd International Conference on Advances in Computer and Information Technology - ACIT 2013 . United States : Institute of Research Engineers and Doctors, LLC, 2013. p. 119-124.

Research output: Book chapter/Published conference paperConference paper

TY - GEN

T1 - The boundary iterative-deepening depth-first search algorithm

AU - Lim, Kai Li

AU - Seng, Kah Phooi

AU - Yeong, LS

AU - Ch'ng, SI

AU - Ang, Li-minn K

PY - 2013/5/4

Y1 - 2013/5/4

N2 - 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.

AB - 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.

KW - pathfinding

KW - uninformed search

KW - iterative deepening

KW - boundary search

UR - https://seekdl.org/conferences/details/International-Conference-on-Advances-in-Computer-and-Information-Technology-ACIT-2013

UR - https://seekdl.org/publication-policy.py

UR - https://web.archive.org/web/20130129033641/http://www.theired.org/acit

U2 - 10.3850/ 978-981-07-6261-2_26

DO - 10.3850/ 978-981-07-6261-2_26

M3 - Conference paper

SP - 119

EP - 124

BT - Proceedings of the 2nd International Conference on Advances in Computer and Information Technology - ACIT 2013

PB - Institute of Research Engineers and Doctors, LLC

CY - United States

ER -

Lim KL, Seng KP, Yeong LS, Ch'ng SI, Ang LK. The boundary iterative-deepening depth-first search algorithm. In Proceedings of the 2nd International Conference on Advances in Computer and Information Technology - ACIT 2013 . United States: Institute of Research Engineers and Doctors, LLC. 2013. p. 119-124 https://doi.org/10.3850/ 978-981-07-6261-2_26