dc.contributor.author |
Barley, Michael |
en |
dc.contributor.author |
Riddle, Patricia |
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 |