Bidirectional Bounded-Suboptimal Heuristic Search with Consistent Heuristics
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911263669354496 |
|---|---|
| author | Shperberg, Shahaf S. Morad, Natalie Siag, Lior Felner, Ariel Atzmon, Dor |
| author_facet | Shperberg, Shahaf S. Morad, Natalie Siag, Lior Felner, Ariel Atzmon, Dor |
| contents | Recent advancements in bidirectional heuristic search have yielded significant theoretical insights and novel algorithms. While most previous work has concentrated on optimal search methods, this paper focuses on bounded-suboptimal bidirectional search, where a bound on the suboptimality of the solution cost is specified. We build upon the state-of-the-art optimal bidirectional search algorithm, BAE*, designed for consistent heuristics, and introduce several variants of BAE* specifically tailored for the bounded-suboptimal context. Through experimental evaluation, we compare the performance of these new variants against other bounded-suboptimal bidirectional algorithms as well as the standard weighted A* algorithm. Our results demonstrate that each algorithm excels under distinct conditions, highlighting the strengths and weaknesses of each approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_10272 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bidirectional Bounded-Suboptimal Heuristic Search with Consistent Heuristics Shperberg, Shahaf S. Morad, Natalie Siag, Lior Felner, Ariel Atzmon, Dor Artificial Intelligence Recent advancements in bidirectional heuristic search have yielded significant theoretical insights and novel algorithms. While most previous work has concentrated on optimal search methods, this paper focuses on bounded-suboptimal bidirectional search, where a bound on the suboptimality of the solution cost is specified. We build upon the state-of-the-art optimal bidirectional search algorithm, BAE*, designed for consistent heuristics, and introduce several variants of BAE* specifically tailored for the bounded-suboptimal context. Through experimental evaluation, we compare the performance of these new variants against other bounded-suboptimal bidirectional algorithms as well as the standard weighted A* algorithm. Our results demonstrate that each algorithm excels under distinct conditions, highlighting the strengths and weaknesses of each approach. |
| title | Bidirectional Bounded-Suboptimal Heuristic Search with Consistent Heuristics |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2511.10272 |