GBFHS: A Generalized Breadth-First Heuristic Search Algorithm

ResearchSpace/Manakin Repository

Show simple item record Barley, Michael en Riddle, P en Linares López, C en Dobson, S en Pohl, I en
dc.contributor.editor Bulitko, V en
dc.contributor.editor Storandt, S en
dc.coverage.spatial Stockholm, Sweden en 2019-02-26T22:38:43Z en 2018-07-14 en
dc.identifier.citation Proceedings of the Eleventh Annual Symposium on Combinatorial Search (SOCS 2018). AAAI Publications. 28-36. 14 Jul 2018 en
dc.identifier.isbn 978-1-57735-802-2 en
dc.identifier.uri en
dc.description.abstract Recently there has been renewed interest in bidirectional heuristic search. New algorithms, e.g., MM, MMe, and NBS, have been introduced which seem much closer to refuting the accepted wisdom that "any front-to-end bidirectional heuristic search algorithm will likely be dominated by unidirectional heuristic search or bidirectional brute-force search". However, MM and MMe can still be dominated by their bidirectional brute-force versions, i.e., they can show a "hump-in-the-middle". We introduce a novel general breadth-first heuristic search algorithm, GBFHS, that unifies both unidirectional and bidirectional search into a single algorithm. It uses knowledge of the edge cost in unit cost domains to stop on first-collision in unidirectional search and in bidirectional search, unlike MM, MMe, and NBS. With no heuristic it expands fewer nodes bidirectionally than Nicholson's blind bidirectional search algorithm. GBFHS expands substantially fewer nodes than MM0, MM, MMe, and NBS. Additionally, GBFHS does not show a "hump-in-the-middle". GBFHS run bidirectionally is not dominated by bidirectional brute-force search, likewise, GBFHS run unidirectionally is not dominated by A*. en
dc.description.uri en
dc.publisher AAAI Publications en
dc.relation.ispartof The Eleventh Annual Symposium on Combinatorial Search en
dc.relation.ispartofseries Proceedings of the Eleventh Annual Symposium on Combinatorial Search (SOCS 2018) en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri en
dc.rights.uri en
dc.title GBFHS: A Generalized Breadth-First Heuristic Search Algorithm en
dc.type Conference Item en
pubs.begin-page 28 en
dc.rights.holder Copyright: Association for the Advancement of Artificial Intelligence (AAAI) en en
pubs.end-page 36 en
pubs.finish-date 2018-07-15 en
pubs.start-date 2018-07-14 en
dc.rights.accessrights en
pubs.subtype Conference Paper en
pubs.elements-id 754759 en Science en School of Computer Science en
pubs.record-created-at-source-date 2018-10-14 en

Full text options

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace

Advanced Search