Research map / Learning theory and algorithms / Combinatorial and search optimization
Tiebreaking Strategies for A* Search: How to Explore the Final Frontier
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use lifo instead of fifo second-level tiebreaking after h | A* with LMcut · IPC 1104 instances | coverage: 558 -> 565 | Helped |
| drop h-based tiebreaking, use lifo only (ablation) | A* with LMcut · IPC 1104 instances | coverage: 565 -> 556 | No clear effect |
| use fifo only (no h, no lifo) (ablation) | A* with LMcut · IPC 1104 instances | coverage: 556 -> 442 | Hurt |
| replace [h, fifo] with depth-based random strategy [h, rd, ro] | A* with LMcut · Zerocost 620 instances | coverage: 256 -> 294.2 | Helped |
| replace [h, lifo] with [h, rd, ro] | A* with LMcut · IPC 1104 instances | coverage: 565 -> 572.8 | Helped |
| random depth instead of first depth (ablation) | [h, ?d, ro] · LMcut Zerocost | coverage: 257.4 -> 294.2 | Helped |
| random depth instead of last depth (ablation) | [h, ?d, ro] · LMcut Zerocost | coverage: 286.6 -> 294.2 | Helped |
| add depth buckets to random tiebreaking (ablation) | [h, ro] · LMcut Zerocost | coverage: 264.9 -> 294.2 | Helped |
| add h-based first-level tiebreaking to [rd, ro] (ablation) | [rd, ro] · LMcut Zerocost | coverage: 279.9 -> 294.2 | Helped |
| epsilon-cost transformation instead of [h, rd, ro] (ablation) | A* with LMcut · LMcut Zerocost | coverage: 294.2 -> 261 | Hurt |
| mangle action names in domain files (ablation) | [h, rd, ro] · Zerocost 620 instances | coverage: 287.2 -> 288.7 | No clear effect |
Closest papers by meaning
- On the Completeness of Best-First Search Variants That Use Random Exploration (AAAI 2016 · similarity 0.87)
- Best-First Width Search: Exploration and Exploitation in Classical Planning (AAAI 2017 · similarity 0.86)
- Envelope-Based Approaches to Real-Time Heuristic Search (AAAI 2020 · similarity 0.86)
- Anchor Search: A Unified Framework for Suboptimal Bidirectional Search (AAAI 2025 · similarity 0.86)
- Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search (AAAI 2025 · similarity 0.85)
- Thought of Search: Planning with Language Models Through The Lens of Efficiency (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.