GBFHS: A Generalized Breadth-First Heuristic Search Algorithm

ResearchSpace/Manakin Repository

Show simple item record

dc.contributor.author Barley, Michael en
dc.contributor.author Riddle, P en
dc.contributor.author Linares López, C en
dc.contributor.author Dobson, S en
dc.contributor.author Pohl, I en
dc.contributor.editor Bulitko, V en
dc.contributor.editor Storandt, S en
dc.coverage.spatial Stockholm, Sweden en
dc.date.accessioned 2019-02-26T22:38:43Z en
dc.date.issued 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 http://hdl.handle.net/2292/45475 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 https://sites.google.com/view/socs18/ 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 https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.rights.uri https://aaai.org/ocs/index.php/SOCS/SOCS18/about/submissions#copyrightNotice 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
pubs.author-url https://aaai.org/ocs/index.php/SOCS/SOCS18/paper/view/17965 en
pubs.end-page 36 en
pubs.finish-date 2018-07-15 en
pubs.start-date 2018-07-14 en
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en
pubs.subtype Conference Paper en
pubs.elements-id 754759 en
pubs.org-id Science en
pubs.org-id 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

Share

Search ResearchSpace


Advanced Search

Browse