Research map / Learning theory and algorithms / Combinatorial and search optimization
Anchor Search: A Unified Framework for Suboptimal Bidirectional Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces anchor search, a unified framework for unbounded suboptimal bidirectional heuristic search, and uses pattern databases as differential heuristics to supply front-to-front heuristics, evaluated on grid pathfinding, sliding tile puzzle, and Towers of Hanoi.
Problem
Unbounded suboptimal bidirectional heuristic search is relatively unexplored, and front-to-front (F2F) heuristics needed for it are unavailable in domains like Towers of Hanoi.
Approach
A framework parameterized by anchor selection, candidate selection, and direction selection policies, where each frontier expands the candidate state closest (by heuristic) to the opposite frontier's anchor; PDBs are used as differential heuristics to build F2F heuristics.
Key results
- On grid pathfinding (Table 1), AST(10)T uses 3,809 expansions on DAO vs 4,310 for GBFS and 5,283 for BGBFS, with about an order of magnitude lower runtime.
- On 22- and 24-disk TOH with single PDB lookup, AST(10)AF expands 3.3x and 5.9x fewer states than GBFS on average and solves all 100 instances up to 32 disks, where GBFS fails on TOH(32).
- On the sliding tile puzzle, DNR has the fewest expansions (1,003) while AST(10)A has the best runtime (2.54 ms vs 2.13 ms for AST(10)A... see Table 4); AST(10)T and TTBS(L) perform poorly there.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use temporal anchor search AST(10)_T instead of the strongest listed baseline | Bidirectional search · DAO grid maps | expansions: 4,177 -> 3,809 | Helped |
| Use temporal anchor search AST(10)_T instead of GBFS | Bidirectional search · Grid pathfinding | time (ms): 9.10 -> 1.91 (DAO); 25.37 -> 5.53 (SC1); 7.40 -> 0.75 (WC3); 40.90 -> 21.31 (Mazes) | Helped |
| Use AST(10)_AF instead of GBFS | TOH search with DH PDB(0-11) · TOH(22) and TOH(24) | expansions: 1,349,162 -> 413,828; 9,921,693 -> 2,805,473 | Helped |
| Use AST(10)_AF instead of GBFS | TOH search with DH PDB(0-11)×100 + DH PDB(12-15) · TOH(22) and TOH(24) | expansions: 7,612,313 -> 3,861,445; 124,683,519 -> 60,908,811 | Helped |
| Add a weak PDB(12-15) lookup to the strong PDB(0-11) lookup (ablation) | TOH search · TOH(22) and TOH(24) | expansions: 413,828 -> 3,861,445; 2,805,473 -> 60,908,811 | Hurt |
| Add a strong PDB(12-∞) lookup to the strong PDB(0-11) lookup (ablation) | TOH search · TOH(22) and TOH(24) | solution length: 11,811 -> 1,568 (TOH(22)); 33,943 -> 2,421 (TOH(24)) | Mixed |
| Use a second strong PDB lookup (PDB(12-∞)) rather than a weak lookup (PDB(12-15)) (ablation) | AST(10)_AF · TOH(22) and TOH(24) | expansions: 3,861,445 -> 1,157,303; 60,908,811 -> 11,216,110 | Helped |
| Expand only in the forward direction rather than bidirectionally (ablation) | AST(10)_AF · TOH(28) | instances solved: 16 out of 100 | Hurt |
| Use the temporal anchor variant AST(10)_T rather than DNR | Bidirectional search · STP | expansions: 1,186 ± 130 vs 1,003 ± 123 | No clear effect |
Surprising findings
- Temporal anchor search (AST_T) performs poorly on the sliding tile puzzle despite strong grid pathfinding results, contradicting the assumption that expanding near recent opposite-frontier states helps.
- Adding a second, equally weighted PDB lookup reduces performance in unbounded suboptimal search, while GBFS was fastest in the two-lookup setting.
Limitations
- Only three anchor search instances were evaluated; many other policy combinations were not explored.
- PDB-based differential heuristics are not admissible when weighted lookups are combined, and rely on memory-heavy PDBs for large TOH instances.
- Only unbounded suboptimal search is addressed; bounded suboptimality is left for future work.
Experimental setup
Datasets: MovingAI grid maps (Dragon Age: Origins, Starcraft 1, Warcraft 3, mazes) Korf's sliding tile puzzle instances random Towers of Hanoi start/goal states
Benchmarks: MovingAI grid pathfinding maps 4x4 sliding tile puzzle (100 instances) 4-peg Towers of Hanoi (22-32 disks)
Metrics: state expansions runtime (ms/s) solution length
Baselines: GBFS BGBFS DNR TTBS(L) TTBS(F)
Builds on: Greedy Best-First Search d-node retargeting (DNR) TTBS differential heuristics pattern databases
Closest papers by meaning
- Bidirectional Bounded-Suboptimal Heuristic Search with Consistent Heuristics (AAAI 2026 · similarity 0.92)
- A Unifying View on Individual Bounds and Heuristic Inaccuracies in Bidirectional Search (AAAI 2020 · similarity 0.91)
- Suboptimal Search with Dynamic Distribution of Suboptimality (AAAI 2025 · similarity 0.85)
- Rectangle Search: An Anytime Beam Search (AAAI 2024 · similarity 0.84)
- Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems (NeurIPS 2025 · similarity 0.83)
- Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · similarity 0.82)
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.